遺傳算法與蟻群算法簡介課件

遺傳算法與群智能優(yōu)化算法簡介主要內(nèi)容智能優(yōu)化算法簡介問題的NP-完全特性常用的智能優(yōu)化算法遺傳算法-GeneticAlgorithm群智能優(yōu)化算法蟻群優(yōu)化算法-AntColonyOptimization粒子群優(yōu)化算法-ParticleSwarmOptimization...北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院22022/10/19智能優(yōu)化算法簡介20世紀(jì)80年代以來，一些優(yōu)化算法得到發(fā)展GA、EP、ACO、PSO、SA、TS、ANN及混合的優(yōu)化策略等基本思想：模擬或揭示某些自然現(xiàn)象或過程為用傳統(tǒng)的優(yōu)化方法難以解決的NP-完全問題提供了有效的解決途徑由于算法構(gòu)造的直觀性與自然機(jī)理，因而通常被稱作智能優(yōu)化算法（intelligentoptimizationalgorithms），或現(xiàn)代啟發(fā)式算法（meta-heuristicalgorithms）[智能優(yōu)化算法及其應(yīng)用，王凌，清華大學(xué)出版社，2001]北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院32022/10/19智能優(yōu)化算法簡介-問題的NP-完全特性求解n個(gè)城市的TSP問題。典型的組合優(yōu)化問題，是NP-完全的要準(zhǔn)確求解該問題只能用枚舉類的辦法要枚舉的解的個(gè)數(shù)為(n-1)!例：n=24，則要枚舉的解的個(gè)數(shù)為：

23!=25,852,016,738,884,976,640,000北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院42022/10/19n2425262728293031時(shí)間1s24s10m4.3h4.9d136.5d10.8y325y北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院52022/10/19北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院72022/10/19智能優(yōu)化算法簡介-常用的智能優(yōu)化算法遺傳算法（GeneticAlgorithm，GA）演化規(guī)劃（EvolutionaryProgramming，EP）蟻群優(yōu)化算法（AntColonyOptimization，ACO）粒子群優(yōu)化算法（ParticleSwarmOptimization，PSO）模擬退火算法（SimulatedAnnealing，SA）禁忌搜索算法（TabuSearch，TS）人工神經(jīng)網(wǎng)絡(luò)（ArtificialNeuralNetwork，ANN）…北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院82022/10/19遺傳算法(GeneticAlgorithm)1975年，Holland出版了著名的《AdaptationinNaturalandArtificialSystems》，標(biāo)志著遺傳算法的誕生。在一定程度上解決了傳統(tǒng)的基于符號(hào)處理機(jī)制的人工智能方法在知識(shí)表示、信息處理和解決組合爆炸等方面所遇到的困難基于“適者生存”原則，是并行優(yōu)化算法，其自組織、自適應(yīng)、自學(xué)習(xí)及群體進(jìn)化的能力適合大規(guī)模復(fù)雜優(yōu)化問題將問題求解表示為“染色體”，通過選擇（selection）、交叉（crossover）和變異（mutation）操作的迭代，實(shí)現(xiàn)種群的演化，最后終收斂到“最適應(yīng)環(huán)境”的個(gè)體，從而求得問題的最優(yōu)解（滿意解）北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院102022/10/19遺傳算法-簡單遺傳算法簡單遺傳算法（SimpleGeneticAlgorithms，SGA），又稱基本遺傳算法、標(biāo)準(zhǔn)遺傳算法基于二進(jìn)制編碼，是最基本的遺傳算法，其遺傳進(jìn)化操作過程簡單、容易理解，是其他遺傳算法的雛形和基礎(chǔ)三種基本操作選擇：通常用比例選擇，即選擇概率正比于個(gè)體的適配值，使適配值高的個(gè)體在下一代中被選中的概率大，提高種群平均適配值交叉：交換兩父代個(gè)體的部分信息構(gòu)成后代個(gè)體，使得后代繼承父代的有效模式，有助于產(chǎn)生優(yōu)良個(gè)體變異：隨機(jī)改變個(gè)體中的某些基因，有助于增加種群多樣性，避免早熟收斂北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院112022/10/19北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院122022/10/19隨機(jī)產(chǎn)生N個(gè)個(gè)體構(gòu)成初始種群P(0),令k=0對種群P(k)中各個(gè)體進(jìn)行評價(jià)終止？令m=0從種群中選擇兩個(gè)體rand()>pc將所選個(gè)體作為臨時(shí)個(gè)體對臨時(shí)個(gè)體以概率pm執(zhí)行變異操作，產(chǎn)生兩個(gè)新個(gè)體并放入P(k+1)中，令m=m+2對選中個(gè)體執(zhí)行交叉操作生成兩個(gè)臨時(shí)個(gè)體輸出優(yōu)化結(jié)果m<N？ynynyn遺傳算法-交叉用于組合出新的個(gè)體，在解空間中進(jìn)行有效搜索，同時(shí)降低對有效模式的破壞概率二進(jìn)制編碼的GA通常采用單點(diǎn)交叉和多點(diǎn)交叉。單點(diǎn)交叉：隨機(jī)選定一個(gè)交叉位置，然后對換交叉點(diǎn)后的子串。多點(diǎn)交叉：隨機(jī)選擇多個(gè)位置，然后對換相應(yīng)子串。兩點(diǎn)交叉：北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院142022/10/1910110010001110101100100011101001110001010110011100010101遺傳算法-交叉（續(xù)）實(shí)數(shù)編碼的GA通常采用算術(shù)交叉：雙個(gè)體算術(shù)交叉：x1、x2為父代個(gè)體，α∈(0,1)為隨機(jī)數(shù)

x1'=αx1+(1-

α)x2

x2'=αx2+(1-

α)x1多個(gè)體算術(shù)交叉：x1,…,x2為父代個(gè)體;αi∈(0,1)且∑αi=1

x'=α1x1+α2x2+…+αnxn

組合優(yōu)化中的置換編碼GA通常采用部分映射交叉(partiallymappingcrossover,PMX)：隨機(jī)選擇兩個(gè)交叉點(diǎn)，交換交叉點(diǎn)之間的片段；對于其他基因，若它不與換過來的片段沖突則保留，若沖突則通過部分映射來確定最后的基因

p1=[264|7358|91] p1'=[234|1876|95]

p2=[452|1876|93] p2'=[412|7358|96]北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院152022/10/19遺傳算法-交叉（續(xù)）單位置次序交叉（C1）類似于OX。選擇一個(gè)交叉位置，保留父代個(gè)體p1交叉位置前的基因，并在另一父代個(gè)體p2中刪除p1中保留的基因，將剩余基因填入p1的交叉位置后來產(chǎn)生后代個(gè)體p1'。如父代個(gè)體同前，交叉位置為4，則后代個(gè)體為p1'=[2647|51893]，p2'=[4521|67389]線性次序交叉（LOX）與OX相比，僅填入基因起始位置不同：首先隨機(jī)確定兩個(gè)交叉位置，并交換交叉點(diǎn)之間的片段；在原先父代中刪除將從另一父代個(gè)體交換過來的基因，然后從第1個(gè)基因位置起依次在兩個(gè)交叉位置外填入剩余基因。如父代個(gè)體和交叉點(diǎn)同前，則片段[7358]和[1876]將交換，在p1中刪除[1876]后剩余[24359]，然后將其填入p1'，得到[243|1876|59]，相應(yīng)地p2'=[421|7358|69]北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院172022/10/19遺傳算法-交叉（續(xù)）基于位置的交叉（PX）與OX類似，只是它不再選取連續(xù)的基因片段，而是隨機(jī)選取一些位置，然后交換被選中位置上的基因，并在原先父代個(gè)體中刪除從另一父代個(gè)體交換過來的基因，接著從第一個(gè)基因位置起依次在未選中位置填入剩余基因。如父代個(gè)體同前，假設(shè)隨機(jī)選取的位置點(diǎn)為2、3、6、8，則后代為p1'=[65

2437891]，p2'=[26

4185793]。循環(huán)交叉（CX）北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院182022/10/19遺傳算法-變異二進(jìn)制或十進(jìn)制用另一種基因替換某一位置或某些位置上的基因?qū)崝?shù)編碼采用擾動(dòng)的方式：x‘=x+ηξ，其中η為擾動(dòng)幅度，ξ為擾動(dòng)變量組合優(yōu)化互換、逆序、插入等北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院192022/10/19遺傳算法-函數(shù)優(yōu)化示例求整數(shù)函數(shù)f(x)=x2在區(qū)間[0,31]上取最大值的點(diǎn)用基本遺傳算法求解問題是求最大值點(diǎn)，目標(biāo)函數(shù)可取為x2。用5位的二進(jìn)制位串表示個(gè)體，對應(yīng)區(qū)間[0,31]上的32個(gè)整數(shù)。隨機(jī)地選取4個(gè)位串作為初始種群，位串與對應(yīng)的整數(shù)如下： 01101 13 11000 24 01000 8 10011 19北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院202022/10/19根據(jù)目標(biāo)函數(shù)，對每個(gè)位串計(jì)算適值為每個(gè)位串指定一個(gè)與其適應(yīng)值成正比的繁殖概率根據(jù)遺傳操作生成下一代種群假設(shè)選擇的兩對父代個(gè)體分別為1和2，2和4北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院212022/10/19編號(hào)位串參數(shù)值目標(biāo)函數(shù)值選擇概率101101131690.144211000245760.4923010008640.055410011193610.309總計(jì)11701.000交叉過程（假設(shè)使用單點(diǎn)交叉，交叉概率pc=0.95）

位串1、2： 011|01 011|00

110|00 110|01

位串2、4： 110|00 110|11 100|11 100|00變異過程（假設(shè)變異概率pm=0.05，且此處無變異）評價(jià)第二代種群北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院222022/10/19編號(hào)位串參數(shù)值目標(biāo)函數(shù)值10110012144211001256253110112772941000016256總計(jì)1754遺傳算法-改進(jìn)編碼方式的改進(jìn)二進(jìn)制編碼使得個(gè)體串很長（特別是精度要求較高的時(shí)候）根據(jù)需要采用格雷編碼、浮點(diǎn)數(shù)編碼、自然數(shù)編碼等對遺傳操作的改進(jìn)改進(jìn)選擇策略、交叉算子、變異算子對控制參數(shù)的自適應(yīng)調(diào)整，如自適應(yīng)調(diào)整交叉概率和變異概率等對執(zhí)行策略的改進(jìn)混合遺傳算法、小生境技術(shù)、免疫遺傳算法、單親遺傳算法、并行遺傳算法北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院242022/10/19遺傳算法-欺騙問題完全欺騙問題一致欺騙問題序列欺騙問題基本欺騙問題具體請參考：李敏強(qiáng),寇紀(jì)淞.遺傳算法的模式欺騙性分析.中國科學(xué)(E輯),2002,32(1):95-102.北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院252022/10/19遺傳算法-主要特點(diǎn)處理參數(shù)集合的編碼，而不是參數(shù)本身始終保持整個(gè)種群而不是個(gè)體的進(jìn)化；即使某個(gè)體在某時(shí)刻丟失了有用的特性，這種特性也會(huì)被其它個(gè)體保留并發(fā)展下去只需要知道問題本身所具有的目標(biāo)函數(shù)的信息，且不受連續(xù)、可微等條件的約束，因而具有廣泛的適用性啟發(fā)式搜索，可適用于有噪聲和多峰值的復(fù)雜空間北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院272022/10/19主要內(nèi)容智能優(yōu)化算法簡介問題的NP-完全特性常用的智能優(yōu)化算法遺傳算法-GeneticAlgorithm群智能優(yōu)化算法蟻群優(yōu)化算法-AntColonyOptimization粒子群優(yōu)化算法-ParticleSwarmOptimization…北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院282022/10/19群智能優(yōu)化算法群智能優(yōu)化算法是一種近年來新興的優(yōu)化方法，其模擬社會(huì)性動(dòng)物的各種群體行為，利用群體中個(gè)體間的信息交互和合作來實(shí)現(xiàn)尋優(yōu)目的群智能優(yōu)化算法包括很多算法，如人工蜂群算法和人工魚群算法等，不過研究比較深入、應(yīng)用比較廣泛的是蟻群優(yōu)化算法和粒子群優(yōu)化算法。也有人將遺傳算法和差分演化算法（DifferentialEvolutionAlgorithm）歸入群智能優(yōu)化算法中。北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院292022/10/19與基于梯度的優(yōu)化算法不同，群智能優(yōu)化算法依靠的是概率搜索，其優(yōu)點(diǎn)是：無集中控制約束，不會(huì)因個(gè)別個(gè)體而影響整個(gè)問題的求解，確保了系統(tǒng)的魯棒性以非直接的信息交流方式確保了系統(tǒng)的擴(kuò)展性并行分布式算法模型對問題定義的連續(xù)性無特殊要求算法實(shí)現(xiàn)簡單北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院302022/10/19主要內(nèi)容智能優(yōu)化算法簡介問題的NP-完全特性常用的智能優(yōu)化算法遺傳算法-GeneticAlgorithm群智能優(yōu)化算法蟻群優(yōu)化算法-AntColonyOptimization粒子群優(yōu)化算法-ParticleSwarmOptimization…北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院312022/10/19蟻群優(yōu)化算法(AntColonyOptimization)蟻群優(yōu)化算法（螞蟻算法），是一種分布式智能模擬算法由M.Dorigo于1992年在他的博士論文中提出，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為基本思想是模擬螞蟻依賴信息素進(jìn)行通信而顯示出的社會(huì)行為是一種隨機(jī)的通用試探法，可用于求解各種不同的組合優(yōu)化問題初始的蟻群優(yōu)化算法是基于圖的蟻群系統(tǒng)，過程如下（以求解對稱的TSP問題為例）：北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院322022/10/19問題的描述：n個(gè)城市N={1,2,…,n}，任兩城市的邊 A={(i,j)|i,j∈N}，城市間的距離為D=(dij)n×n設(shè)有m只螞蟻，其出發(fā)城市可隨機(jī)確定路徑的構(gòu)造為TSP圖中的每一條弧(i,j)賦信息素初值τij(0)，通常的做法是隨機(jī)生成一個(gè)解，設(shè)其目標(biāo)值為f0，則τij(0)=1/f0設(shè)置城市間的啟發(fā)式信息ηij，通常ηij

=1/dij設(shè)第k只螞蟻在城市i，則其根據(jù)下面的概率選擇下一個(gè)城市：

其中另外，每一螞蟻有一個(gè)表list，用于記錄其訪問過的城市；當(dāng)訪問了所有的城市后，就可以在其經(jīng)過的路徑上更新信息素北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院332022/10/19α與β表示信息素與啟發(fā)式信息的相對重要程度，通常α

=1或2，β

=2或3

表示螞蟻k可選的城市集合，即其還未訪問過的城市集合信息素更新策略（局部更新）所有螞蟻周游完成后更新信息素：首先以一定的比例(1-ρ)減少每條邊上的信息素（

表示信息素的揮發(fā)），然后更新各自路徑上的信息素，即更新信息素的方式為其中信息素的揮發(fā)機(jī)制可以避免信息素大量積累，也體現(xiàn)了生物界的“遺忘”現(xiàn)象；

表示螞蟻k在邊(i,j)上留下的信息素，如果螞蟻沒有經(jīng)過該邊，則其留下的信息素為0，即

其中，表示螞蟻k構(gòu)造的路徑的長度，Q是一常數(shù)（比如1）此機(jī)制體現(xiàn)了：構(gòu)造的路徑越短，螞蟻留下的信息素越多；某邊經(jīng)過的螞蟻越多，其上積累的信息素也就越多北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院342022/10/19全局更新：對于一次迭代中最好的那只螞蟻，單獨(dú)更新其

經(jīng)過路徑上的信息素上面的蟻群優(yōu)化算法的不足信息素的累積造成“停滯”現(xiàn)象：螞蟻基本上走同一條路徑要得到更好的優(yōu)化能力往往需要與局部搜索算法結(jié)合：對最好的路徑執(zhí)行局部搜索蟻群算法的改進(jìn)精英策略：對已發(fā)現(xiàn)的最好路徑給予額外的增強(qiáng)，從而增大較好路徑的選擇概率負(fù)反饋機(jī)制：螞蟻?zhàn)哌^一條邊時(shí)，立即減少該邊上的信息素，以減少該邊再次被選中的概率Max-Min螞蟻系統(tǒng)：將信息素的濃度限制在[min,max]的范圍內(nèi)，避免搜索停滯[T.Stutzle,H.Hoos,MAX-MINAntSystem,FGCS,2000,16:889-914]

北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院352022/10/19蟻群優(yōu)化算法-較成功的算法北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院362022/10/19算法名稱提出者年份AntSystem(AS)Dorigoetal.1991ElitistASDorigoetal.1992Ant-QGambardella,Dorigo1995AntColonySystemDorigo,Gambardella1996Max-MinASStutzle,Hoos1996Rank-BasedASBullnheimeretal.1997AntsManiezzo1999BWASCordonetal.2000Hyper-CubeASBlumetal.2001蟻群優(yōu)化算法-較成功的應(yīng)用北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院372022/10/19問題類型問題名稱作者年份路徑規(guī)劃旅行商問題Dorigoetal.1991,1996Dorigo,Gambardella1997Stutzle,Hoos1997,2000車輛路徑規(guī)劃Gambardellaetal.1999Reimannetal.2004有序排列Gambardella,Dorigo2000分配問題二次分配Stutzle,Hoos2000Maniezzo1999課表編排Sochaetal.2002,2003圖著色Costa,Hertz1997蟻群優(yōu)化算法-較成功的應(yīng)用(續(xù))北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院382022/10/19問題類型問題名稱作者年份調(diào)度問題工程調(diào)度Merkleetal.2002開放車間Blum2005子集問題集覆蓋Lessingetal.2004其他約束滿足Solnon2000,2002分類規(guī)則Parpinellietal.2002Martensetal.2006貝葉斯網(wǎng)絡(luò)Camposetal.2002蛋白質(zhì)折疊Shmygelska,Hoos2005M.Dorigo,T.Stutzle著,張軍等譯,《蟻群優(yōu)化》,清華大學(xué)出版社,2007.主要內(nèi)容智能優(yōu)化算法簡介問題的NP-完全特性常用的智能優(yōu)化算法遺傳算法-GeneticAlgorithm群智能優(yōu)化算法蟻群優(yōu)化算法-AntColonyOptimization粒子群優(yōu)化算法-ParticleSwarmOptimization…北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院392022/10/19粒子群優(yōu)化算法(ParticleSwarmOptimization)粒子群優(yōu)化算法（ParticleSwarmOptimization,PSO,也稱為微粒群優(yōu)化算法）是由Kennedy和Eberhart于1995年提出來的所謂粒子是指不考慮群體中的成員的質(zhì)量和體積，只考慮速度和加速狀態(tài)北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院402022/10/19

設(shè)第i個(gè)粒子表示為Xi

=(xi1,xi2,…,xiD)，有最好適應(yīng)值的位置記為Pi=(pi1,pi2,…,piD)，也稱為Pbest。設(shè)符號(hào)g表示群體中所有粒子經(jīng)歷過的最好位置，也稱為gbest。設(shè)Vi=(vi1,vi2,…,viD)表示粒子i的速度。在每一代，粒子i的第d