1、幾種智能算法概述及其應用 匯報內容 幾種智能算法概述 1.遺傳算法 2.粒子群算法 3.模擬退火算法 4.蟻群算法 智能算法概述 1、遺傳算法 遺傳算法（GeneticAlgorithm，GA）是一種進化算法，其基本 原理是仿效生物界中的“物競天擇、適者生存”的演化法則。遺傳 算法的做法是把問題參數編碼為染色體， 再利用迭代的方式進行選擇、交叉以及 變異等運算來交換種群中染色體的信息， 最終生成符合優化目標的染色體。 智能算法概述 染色體：生物遺傳物質主要載體。 基因：擴展生物性狀的遺傳物質 的功能單元和結構單位。 基因座：染色體中基因的位置。 等位基因：基因所取的值。 生物遺傳概念遺產算法中

2、的應用 適者生存目標值比較大的解被選擇的可能性大 個體可能解 染色體解的編碼（字符串、向量等） 基因解中每一分量的特征 適應性適應函數值 群體根據適應函數值選定的一組解（解的個數為群 體的規模） 婚配交叉選擇兩個染色體進行交叉產生一組新的染 色體的過程 變異編碼的某一分量發生變化的過程 1、遺傳算法 智能算法概述 遺傳算法流程 遺傳算法改進方向 1、遺傳算法與非線性規劃結合2、與BP神經網絡結合3、基于量子遺傳算 法尋優4、多種群遺傳算法5、多層編碼遺傳算法 1、遺傳算法 智能算法概述 TSP（旅行商問題）問 題描述與結果： 已知n個城市互相之 間距離，某人從某城市 出發訪問每個城市且僅 一次

3、，如何安排才能使 其所走路線最短 1、遺傳算法 智能算法概述 制孔路徑優化 在飛機裝配線上用機器 人帶動末端執行器進行制 孔，執行器由初始位置依 次移動到每一孔位，最后 返回初始位置，目標為所 走路徑最短，時間最少 產品生產安排 一個周期內生產n種 產品，開銷包括制造成 本以及產品轉換開支， 因此生產成本與生產順 序有關，目標為使轉換 成本最低 1、遺傳算法 智能算法概述 2、粒子群算法產生背景 粒子群算法（Particle Swarm Optimization， PSO）源于 對鳥類捕食行為的研究，一群鳥隨機分布在一個區域中，在這 片區域只有一塊食物，鳥類捕食時，所有鳥都不知道食物在哪 里，

4、但是他們知道當前位置距離食物 還有多遠，那么找到食物最簡單有效 的策略就是搜尋當前距離食物最近的 鳥的周圍區域。 智能算法概述 2、粒子群算法基本思想 每個潛在解都是搜索空間的一只鳥，稱之為“粒子”，所有粒子 都有一個由被優化函數決定的適應值，還有一個速度決定其飛行方 向及距離。粒子們追隨當前最優粒子在解空間搜索，然后通過迭代 找到最優解。在每一次的迭代中，粒子根據兩個極值來更新自己： 粒子本身變化過程中的最優解，稱為個體極值 整個種群目前找到的最優解，稱為全局極值 有時為了避免陷入局部最優，可使用整體中一部分作為粒子鄰居， 則所有鄰居中的極值就是局部極值。 智能算法概述 2、粒子群算法基本模

5、型 設群體規模為N，目標搜索空間為D維。 11 , T iiiiD Xvvv 1,2,i iN 11 , T iiiiD Vvvv 1,2,iN 11 , T iiiiD Pppp 表示第個粒子的位置。 表示i的飛翔速度 表示i自身搜索到的最優點 1 1 12 2 11 kkkkkk ididdididdgdid kkk ididid vvc rpxc rpx xxv 智能算法概述 2、粒子群算法基本模型 學習因子c1： c1=0，則只有社會， 沒有自我 學習因子c2： c2=0，則只有自我， 沒有社會 智能算法概述 2、粒子群算法改進加入慣性權重 由基本粒子群算法模型 中粒子位置進化方程可看

6、 出，不同時刻位置由飛行 速度決定，因此飛行速度 大小直接影響算法的全局 收斂性。 慣性權重分類： 1. 固定權重，種群規模 越大，所需權重越小 2. 時變權重 3. 隨機權重 智能算法概述 3、模擬退火算法背景 退火是指將固體加熱到足夠高的溫度，使分子呈現隨機 排列狀態，然后逐步降溫使之冷卻，最后分子以低能狀態排 列，固體達到某種穩定狀態。該過 程屬于熱力學范疇，主要由三部分 組成：加溫過程、等溫過程以及冷 卻過程。 智能算法概述 3、模擬退火算法 由統計力學研究表明，在溫度T，分子滯留在狀態r的概率 滿足波茲曼概率分布 其中，為狀態r的能量，為概率分布的標準化因子 當時 即分子停留在能量小

7、的狀態概率大 12 EE 121 12 BB E -E -=1-exp - k T E1 P E = EP E = Eexp - Z Tk T 智能算法概述 3、模擬退火算法流程 初始化：初始溫度T（充分大），初始解狀態S（算法迭代的 起點），每個T值的迭代次數L 對做第三至第六步： 對當前解隨機擾動，產生新解S 計算增量，其中為評價函數 若0則接受S為新的當前解，否則以概率接 受S作為新的當前解 如果滿足終止條件則輸出當前解作為最優解，結束程序 Sf 21 SSdfff exp/dfT 1,kL 智能算法概述 4、蟻群算法背景 單個的螞蟻為了避免自己迷路，它 在爬行時，同時也會釋放一種特殊的分 泌物信息素，信息素濃度越高，表 示對應路徑越短。當一條路上的信息素 越來越多，后來的螞蟻選擇這條路徑的 概率也就越來越大，從而進一步增加了 該路徑的信息素濃度。 智能算法概述 4、蟻群算法模型 蟻群轉移概率公式信息更新公式 Ant cycle systemAnt quantity systemAnt density system , , , 0, k k k s Ji i ji j if jJi i si spi j otherwise 1 11 ,0 ij ijijij n k ij k tt /, 0, ij k