遺傳算法與蟻群算法簡介.ppt

《遺傳算法與蟻群算法簡介.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、遺傳算法與群智能優(yōu)化算法簡介主要內(nèi)容智能優(yōu)化算法簡介問題的NP-完全特性常用的智能優(yōu)化算法遺傳算法-GeneticAlgorithm群智能優(yōu)化算法蟻群優(yōu)化算法-AntColonyOptimization粒子群優(yōu)化算法-ParticleSwarmOptimization...北京交通大學(xué)計算機與信息技術(shù)學(xué)院22021/9/2智能優(yōu)化算法簡介20世紀(jì)80年代以來，一些優(yōu)化算法得到發(fā)展GA、EP、ACO、PSO、SA、TS、ANN及混合的優(yōu)化策略等基本思想：模擬或揭示某些自然現(xiàn)象或過程為用傳統(tǒng)的優(yōu)化方法難以解決的NP-完全問題提供了有效的解決途徑

2、由于算法構(gòu)造的直觀性與自然機理，因而通常被稱作智能優(yōu)化算法（intelligentoptimizationalgorithms），或現(xiàn)代啟發(fā)式算法（meta-heuristicalgorithms）[智能優(yōu)化算法及其應(yīng)用，王凌，清華大學(xué)出版社，2001]北京交通大學(xué)計算機與信息技術(shù)學(xué)院32021/9/2智能優(yōu)化算法簡介-問題的NP-完全特性求解n個城市的TSP問題。典型的組合優(yōu)化問題，是NP-完全的要準(zhǔn)確求解該問題只能用枚舉類的辦法要枚舉的解的個數(shù)為(n-1)!例：n=24，則要枚舉的解的個數(shù)為：23!=25,852,016,738,884

3、,976,640,000北京交通大學(xué)計算機與信息技術(shù)學(xué)院42021/9/2n2425262728293031時間1s24s10m4.3h4.9d136.5d10.8y325y北京交通大學(xué)計算機與信息技術(shù)學(xué)院52021/9/2北京交通大學(xué)計算機與信息技術(shù)學(xué)院62021/9/2北京交通大學(xué)計算機與信息技術(shù)學(xué)院72021/9/2智能優(yōu)化算法簡介-常用的智能優(yōu)化算法遺傳算法（GeneticAlgorithm，GA）演化規(guī)劃（EvolutionaryProgramming，EP）蟻群優(yōu)化算法（AntColonyOptimization，ACO）粒子群

4、優(yōu)化算法（ParticleSwarmOptimization，PSO）模擬退火算法（SimulatedAnnealing，SA）禁忌搜索算法（TabuSearch，TS）人工神經(jīng)網(wǎng)絡(luò)（ArtificialNeuralNetwork，ANN）…北京交通大學(xué)計算機與信息技術(shù)學(xué)院82021/9/2主要內(nèi)容智能優(yōu)化算法簡介問題的NP-完全特性常用的智能優(yōu)化算法遺傳算法-GeneticAlgorithm群智能優(yōu)化算法蟻群優(yōu)化算法-AntColonyOptimization粒子群優(yōu)化算法-ParticleSwarmOptimization…北京交通大學(xué)

5、計算機與信息技術(shù)學(xué)院92021/9/2遺傳算法(GeneticAlgorithm)1975年，Holland出版了著名的《AdaptationinNaturalandArtificialSystems》，標(biāo)志著遺傳算法的誕生。在一定程度上解決了傳統(tǒng)的基于符號處理機制的人工智能方法在知識表示、信息處理和解決組合爆炸等方面所遇到的困難基于“適者生存”原則，是并行優(yōu)化算法，其自組織、自適應(yīng)、自學(xué)習(xí)及群體進化的能力適合大規(guī)模復(fù)雜優(yōu)化問題將問題求解表示為“染色體”，通過選擇（selection）、交叉（crossover）和變異（mutation）操

6、作的迭代，實現(xiàn)種群的演化，最后終收斂到“最適應(yīng)環(huán)境”的個體，從而求得問題的最優(yōu)解（滿意解）北京交通大學(xué)計算機與信息技術(shù)學(xué)院102021/9/2遺傳算法-簡單遺傳算法簡單遺傳算法（SimpleGeneticAlgorithms，SGA），又稱基本遺傳算法、標(biāo)準(zhǔn)遺傳算法基于二進制編碼，是最基本的遺傳算法，其遺傳進化操作過程簡單、容易理解，是其他遺傳算法的雛形和基礎(chǔ)三種基本操作選擇：通常用比例選擇，即選擇概率正比于個體的適配值，使適配值高的個體在下一代中被選中的概率大，提高種群平均適配值交叉：交換兩父代個體的部分信息構(gòu)成后代個體，使得后代繼承父代

7、的有效模式，有助于產(chǎn)生優(yōu)良個體變異：隨機改變個體中的某些基因，有助于增加種群多樣性，避免早熟收斂北京交通大學(xué)計算機與信息技術(shù)學(xué)院112021/9/2北京交通大學(xué)計算機與信息技術(shù)學(xué)院122021/9/2隨機產(chǎn)生N個個體構(gòu)成初始種群P(0),令k=0對種群P(k)中各個體進行評價終止？令m=0從種群中選擇兩個體rand()>pc將所選個體作為臨時個體對臨時個體以概率pm執(zhí)行變異操作，產(chǎn)生兩個新個體并放入P(k+1)中，令m=m+2對選中個體執(zhí)行交叉操作生成兩個臨時個體輸出優(yōu)化結(jié)果m

8、率大，即被選中用來繁殖下一代的概率大。常用的選擇方法有：比例選擇（輪盤選擇）基于排名的選擇：由好到壞排序，然后以一定方式給每一個體分配選擇概率（線性、非線性等方式，要求好的個體被