幾種智能算法概述及其應(yīng)用

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

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

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

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

5、型 設(shè)群體規(guī)模為N，目標(biāo)搜索空間為D維。 11 , T iiiiD Xvvv 1,2,i iN 11 , T iiiiD Vvvv 1,2,iN 11 , T iiiiD Pppp 表示第個(gè)粒子的位置。 表示i的飛翔速度 表示i自身搜索到的最優(yōu)點(diǎn) 1 1 12 2 11 kkkkkk ididdididdgdid kkk ididid vvc rpxc rpx xxv 智能算法概述 2、粒子群算法基本模型 學(xué)習(xí)因子c1： c1=0，則只有社會(huì)， 沒有自我 學(xué)習(xí)因子c2： c2=0，則只有自我， 沒有社會(huì) 智能算法概述 2、粒子群算法改進(jìn)加入慣性權(quán)重 由基本粒子群算法模型 中粒子位置進(jìn)化方程可看

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

7、的狀態(tài)概率大 12 EE 121 12 BB E -E -=1-exp - k T E1 P E = EP E = Eexp - Z Tk T 智能算法概述 3、模擬退火算法流程 初始化：初始溫度T（充分大），初始解狀態(tài)S（算法迭代的 起點(diǎn)），每個(gè)T值的迭代次數(shù)L 對做第三至第六步： 對當(dāng)前解隨機(jī)擾動(dòng)，產(chǎn)生新解S 計(jì)算增量，其中為評價(jià)函數(shù) 若0則接受S為新的當(dāng)前解，否則以概率接 受S作為新的當(dāng)前解 如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序 Sf 21 SSdfff exp/dfT 1,kL 智能算法概述 4、蟻群算法背景 單個(gè)的螞蟻為了避免自己迷路，它 在爬行時(shí)，同時(shí)也會(huì)釋放一種特殊的分 泌物信息素，信息素濃度越高，表 示對應(yīng)路徑越短。當(dāng)一條路上的信息素 越來越多，后來的螞蟻選擇這條路徑的 概率也就越來越大，從而進(jìn)一步增加了 該路徑的信息素濃度。 智能算法概述 4、蟻群算法模型 蟻群轉(zhuǎn)移概率公式信息更新公式 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 k