.,遺傳算法與群智能優(yōu)化算法簡介,.,2,2020/5/26,主要內(nèi)容,智能優(yōu)化算法簡介問題的NP-完全特性常用的智能優(yōu)化算法遺傳算法-GeneticAlgorithm群智能優(yōu)化算法蟻群優(yōu)化算法-AntColonyOptimization粒子群優(yōu)化算法-ParticleSwarmOptimization.,.,3,2020/5/26,智能優(yōu)化算法簡介,20世紀80年代以來，一些優(yōu)化算法得到發(fā)展GA、EP、ACO、PSO、SA、TS、ANN及混合的優(yōu)化策略等基本思想：模擬或揭示某些自然現(xiàn)象或過程為用傳統(tǒng)的優(yōu)化方法難以解決的NP-完全問題提供了有效的解決途徑由于算法構(gòu)造的直觀性與自然機理，因而通常被稱作智能優(yōu)化算法（intelligentoptimizationalgorithms），或現(xiàn)代啟發(fā)式算法（meta-heuristicalgorithms）智能優(yōu)化算法及其應用，王凌，清華大學出版社，2001,.,4,2020/5/26,智能優(yōu)化算法簡介-問題的NP-完全特性,求解n個城市的TSP問題。典型的組合優(yōu)化問題，是NP-完全的要準確求解該問題只能用枚舉類的辦法要枚舉的解的個數(shù)為(n-1)!例：n=24，則要枚舉的解的個數(shù)為：23!=25,852,016,738,884,976,640,000,1s,24s,10m,4.3h,4.9d,136.5d,10.8y,325y,.,5,2020/5/26,.,6,2020/5/26,.,7,2020/5/26,.,8,2020/5/26,智能優(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)絡（ArtificialNeuralNetwork，ANN）,.,9,2020/5/26,主要內(nèi)容,智能優(yōu)化算法簡介問題的NP-完全特性常用的智能優(yōu)化算法遺傳算法-GeneticAlgorithm群智能優(yōu)化算法蟻群優(yōu)化算法-AntColonyOptimization粒子群優(yōu)化算法-ParticleSwarmOptimization,.,10,2020/5/26,遺傳算法(GeneticAlgorithm),1975年，Holland出版了著名的AdaptationinNaturalandArtificialSystems，標志著遺傳算法的誕生。在一定程度上解決了傳統(tǒng)的基于符號處理機制的人工智能方法在知識表示、信息處理和解決組合爆炸等方面所遇到的困難基于“適者生存”原則，是并行優(yōu)化算法，其自組織、自適應、自學習及群體進化的能力適合大規(guī)模復雜優(yōu)化問題將問題求解表示為“染色體”，通過選擇（selection）、交叉（crossover）和變異（mutation）操作的迭代，實現(xiàn)種群的演化，最后終收斂到“最適應環(huán)境”的個體，從而求得問題的最優(yōu)解（滿意解）,.,11,2020/5/26,遺傳算法-簡單遺傳算法,簡單遺傳算法（SimpleGeneticAlgorithms，SGA），又稱基本遺傳算法、標準遺傳算法基于二進制編碼，是最基本的遺傳算法，其遺傳進化操作過程簡單、容易理解，是其他遺傳算法的雛形和基礎三種基本操作選擇：通常用比例選擇，即選擇概率正比于個體的適配值，使適配值高的個體在下一代中被選中的概率大，提高種群平均適配值交叉：交換兩父代個體的部分信息構(gòu)成后代個體，使得后代繼承父代的有效模式，有助于產(chǎn)生優(yōu)良個體變異：隨機改變個體中的某些基因，有助于增加種群多樣性，避免早熟收斂,.,12,2020/5/26,隨機產(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é)果,mf(1*),f(00*)f(11*),f(01*),f(10*)f(*0*)f(*1*),f(0*0)f(1*1),f(0*1),f(1*0)f(*0)f(*1),f(*00)f(*11),f(*01),f(*10)即競爭力強的低階模式的有效基因位為“0”，那么該類模式在群體中的數(shù)量將按指數(shù)增長，包含“0”的1，2階模式使GA搜索偏離最優(yōu)解，就形成了3階模式欺騙問題。,.,27,2020/5/26,遺傳算法-主要特點,處理參數(shù)集合的編碼，而不是參數(shù)本身始終保持整個種群而不是個體的進化；即使某個體在某時刻丟失了有用的特性，這種特性也會被其它個體保留并發(fā)展下去只需要知道問題本身所具有的目標函數(shù)的信息，且不受連續(xù)、可微等條件的約束，因而具有廣泛的適用性啟發(fā)式搜索，可適用于有噪聲和多峰值的復雜空間,.,28,2020/5/26,主要內(nèi)容,智能優(yōu)化算法簡介問題的NP-完全特性常用的智能優(yōu)化算法遺傳算法-GeneticAlgorithm群智能優(yōu)化算法蟻群優(yōu)化算法-AntColonyOptimization粒子群優(yōu)化算法-ParticleSwarmOptimization,.,29,2020/5/26,群智能優(yōu)化算法,群智能優(yōu)化算法是一種近年來新興的優(yōu)化方法，其模擬社會性動物的各種群體行為，利用群體中個體間的信息交互和合作來實現(xiàn)尋優(yōu)目的群智能優(yōu)化算法包括很多算法，如人工蜂群算法和人工魚群算法等，不過研究比較深入、應用比較廣泛的是蟻群優(yōu)化算法和粒子群優(yōu)化算法。也有人將遺傳算法和差分演化算法（DifferentialEvolutionAlgorithm）歸入群智能優(yōu)化算法中。,.,30,2020/5/26,與基于梯度的優(yōu)化算法不同，群智能優(yōu)化算法依靠的是概率搜索，其優(yōu)點是：無集中控制約束，不會因個別個體而影響整個問題的求解，確保了系統(tǒng)的魯棒性以非直接的信息交流方式確保了系統(tǒng)的擴展性并行分布式算法模型對問題定義的連續(xù)性無特殊要求算法實現(xiàn)簡單,.,31,2020/5/26,主要內(nèi)容,智能優(yōu)化算法簡介問題的NP-完全特性常用的智能優(yōu)化算法遺傳算法-GeneticAlgorithm群智能優(yōu)化算法蟻群優(yōu)化算法-AntColonyOptimization粒子群優(yōu)化算法-ParticleSwarmOptimization,.,32,2020/5/26,蟻群優(yōu)化算法(AntColonyOptimization),蟻群優(yōu)化算法（螞蟻算法），是一種分布式智能模擬算法由M.Dorigo于1992年在他的博士論文中提出，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為基本思想是模擬螞蟻依賴信息素進行通信而顯示出的社會行為是一種隨機的通用試探法，可用于求解各種不同的組合優(yōu)化問題初始的蟻群優(yōu)化算法是基于圖的蟻群系統(tǒng)，過程如下（以求解對稱的TSP問題為例）：,.,33,2020/5/26,問題的描述：n個城市N=1,2,n，任兩城市的邊A=(i,j)|i,jN，城市間的距離為D=(dij)nn設有m只螞蟻，其出發(fā)城市可隨機確定路徑的構(gòu)造為TSP圖中的每一條弧(i,j)賦信息素初值ij(0)，通常的做法是隨機生成一個解，設其目標值為f0，則ij(0)=1/f0設置城市間的啟發(fā)式信息ij，通常ij=1/dij設第k只螞蟻在城市i，則其根據(jù)下面的概率選擇下一個城市：其中另外，每一螞蟻有一個表list，用于記錄其訪問過的城市；當訪問了所有的城市后，就可以在其經(jīng)過的路徑上更新信息素,與表示信息素與啟發(fā)式信息的相對重要程度，通常=1或2，=2或3,表示螞蟻k可選的城市集合，即其還未訪問過的城市集合,.,34,2020/5/26,信息素更新策略（局部更新）所有螞蟻周游完成后更新信息素：首先以一定的比例(1-)減少每條邊上的信息素（表示信息素的揮發(fā)），然后更新各自路徑上的信息素，即更新信息素的方式為其中信息素的揮發(fā)機制可以避免信息素大量積累，也體現(xiàn)了生物界的“遺忘”現(xiàn)象；表示螞蟻k在邊(i,j)上留下的信息素，如果螞蟻沒有經(jīng)過該邊，則其留下的信息素為0，即其中，表示螞蟻k構(gòu)造的路徑的長度，Q是一常數(shù)（比如1）此機制體現(xiàn)了：構(gòu)造的路徑越短，螞蟻留下的信息素越多；某邊經(jīng)過的螞蟻越多，其上積累的信息素也就越多,.,35,2020/5/26,全局更新：對于一次迭代中最好的那只螞蟻，單獨更新其經(jīng)過路徑上的信息素上面的蟻群優(yōu)化算法的不足信息素的累積造成“停滯”現(xiàn)象：螞蟻基本上走同一條路徑要得到更好的優(yōu)化能力往往需要與局部搜索算法結(jié)合：對最好的路徑執(zhí)行局部搜索蟻群算法的改進精英策略：對已發(fā)現(xiàn)的最好路徑給予額外的增強，從而增大較好路徑的選擇概率負反饋機制：螞蟻走過一條邊時，立即減少該邊上的信息素，以減少該邊再次被選中的概率Max-Min螞蟻系統(tǒng)：將信息素的濃度限制在min,max的范圍內(nèi)，避免搜索停滯T.Stutzle,H.Hoos,MAX-MINAntSystem,FGCS,2000,16:889-914,.,36,2020/5/26,蟻群優(yōu)化算法-較成功的算法,.,37,2020/5/26,蟻群優(yōu)化算法-較成功的應用,.,38,2020/5/26,蟻群優(yōu)化算法-較成功的應用(續(xù)),M.Dorigo,T.Stutzle著,張軍等譯,蟻群優(yōu)化,清華大學出版社,2007.,.,39,2020/5/26,主要內(nèi)容,智能優(yōu)化算法簡介問題的NP-完全特性常用的智能優(yōu)化算法遺傳算法-GeneticAlgorithm群智能優(yōu)化算法蟻群優(yōu)化算法-AntColonyOptimization粒子群優(yōu)化算法-ParticleSwarmOptimization,.,40,2020/5/26,粒子群優(yōu)化算法(ParticleSwarmOptimization),粒子群優(yōu)化算法（ParticleSwarmOptimization,PSO,也稱為微粒群優(yōu)化算法）是由Kennedy和Eberhart于1995年提出來的所謂粒子是指不考慮群體中的成員的質(zhì)量和體積，只考慮速度和加速狀態(tài),.,41,2020/5/26,設第i個粒子表示為Xi=(xi1,xi2,xiD)，有最好適應值的位置記為Pi=(pi1,pi2,piD)，也稱為Pbest。設符號g表示群體中所有粒子經(jīng)歷過的最好位置，也稱為gbest。設Vi=(vi1,vi2,viD)表示粒子i的速度。在每一代，粒子i的第d維(1dD)根據(jù)如下方程變化：vid=wvid+c1rand1()(pid-xid)+c2rand2()(pgd-xid)xid=xid+vid其中w為慣性權(quán)重，c1和c2為加速常數(shù)，rand1()和rand2()為在0,1內(nèi)選取的隨機函數(shù)。此外，微粒的速度vid的上限為Vmax。,粒子群優(yōu)化算法-基本原理,.,42,2020/5/26,(1)初始化：隨機生成一群規(guī)模為m的微粒，包括位置和速度(2)評價：計算每個微粒的適應度(3)更新Pbest：對每個微粒，將其適應值與其經(jīng)歷過的最好位置做比較，如果較好，則將其位置作為該微粒的當前最好位置Pbest(4)更新gbest：對每個微粒，將其適應值與全局最好位置做比較，如果較好，則將其記為gbest(5)更新vid和xid：根據(jù)上述公式改變微粒的速度和位置(6)如達到滿意的適應值或預設的最大代數(shù)Gmax，則結(jié)束，否則轉(zhuǎn)(2),粒子群優(yōu)化算法-基本過程,.,43,2020/5/26,粒子群優(yōu)化算法-參數(shù)設置,最