啟發(fā)法 Metaheuristics講解分析

通用啟發(fā)法Metaheuristics章節(jié)大綱前言專有名詞模擬退火法禁忌搜尋法基因算法粒子群最佳化算法蟻群最佳化算法p.2/4714.1

前言通用啟發(fā)法（metaheuristic）一般用以求解組合性最佳化（combinatorialoptimization）問(wèn)題，以在合理時(shí)間求得近似最佳解近年來(lái)通用啟發(fā)法已成為作業(yè)研究最重要方法之一Metaheuristic是由兩個(gè)希臘字而來(lái)；meta是指超越更高階，而heuristic來(lái)自heuriskein，代表發(fā)現(xiàn)通用啟發(fā)法的概念經(jīng)常是由觀察自然界所獲得的想法五種常用的通用啟發(fā)法模擬退火法（simulatedannealing；SA）禁忌搜尋法（tabusearch；TS）基因算法（geneticalgorithms；GA）粒子群最佳化算法（particleswarmoptimization；PSO）蟻群最佳化算法（antcolonyoptimization；ACO）p.3/47通用啟發(fā)法的優(yōu)點(diǎn)可對(duì)不同問(wèn)題，設(shè)計(jì)適合的算法，因此其所能求解的問(wèn)題十分廣泛均有跳脫區(qū)域最佳解的機(jī)制，經(jīng)常可找到近似最佳解，甚至全域最佳解對(duì)于問(wèn)題復(fù)雜度較高、問(wèn)題規(guī)模較大時(shí)，經(jīng)?？色@得良好的求解質(zhì)量及求解效率即使對(duì)問(wèn)題特性不十分了解，仍可使用，因此經(jīng)常是最佳化方法或特定算法的有效替代方案。p.4/47通用啟發(fā)法的缺點(diǎn)因經(jīng)常需針對(duì)問(wèn)題而設(shè)計(jì)，較少現(xiàn)有套裝軟件，因此使用時(shí)需具有一定的程序撰寫(xiě)能力僅能求得近似最佳解，而無(wú)法保證為最佳解。僅是一種廣義的啟發(fā)法，相較最佳化方法，較缺乏理論基礎(chǔ)對(duì)于相同的問(wèn)題，可設(shè)計(jì)不同的通用啟發(fā)法；即使同一種通用啟發(fā)法（如GA），亦可發(fā)展不同的演算程序必須設(shè)定一些（有時(shí)相當(dāng)多）所需要的參數(shù)值p.5/4714.2

專有名詞1/2

組合最佳化（combinatorialoptimization）：由一個(gè)以上的離散變量組合為極大化或極小化的問(wèn)題搜尋空間（searchspace）：在搜尋最佳解的過(guò)程中，決策變量所能搜尋的范圍或數(shù)值可行解（feasiblesolution）：符合所有限制式的解不可行解（infeasiblesolution）：違反任何一個(gè)限制式的解最佳解（optimalsolution）：具最佳目標(biāo)函數(shù)值的可行解近似最佳解（near-optimalsolution）：具接近最佳目標(biāo)函數(shù)值的可行解區(qū)域最佳解（localoptimum）：鄰近可行解中的最佳解p.6/4714.2

專有名詞2/2全域最佳解（globaloptimum）：所有可行解中的最佳解初始解（initialsolution）：可隨機(jī)產(chǎn)生或以特定算法產(chǎn)生移步（move）：從一個(gè)可行解移至另一個(gè)新的可行解鄰近搜尋（neighborhoodsearch）又稱區(qū)域搜尋（localsearch）移步法則一般使用插入(insert)、任意兩點(diǎn)交換（interchange）或相鄰兩點(diǎn)交換（adjacentinterchange）等常用的鄰近解選擇方式：改善目標(biāo)值的鄰近解、部份鄰近解中最佳者、全部鄰近解中最佳者。停止條件（terminationcondition）：常用的有最大搜尋次數(shù)（迭代次數(shù)）或連續(xù)未改善的次數(shù)p.7/47常用變量的定義p.8/4714.3模擬退火法模擬退火法（simulatedannealing；SA）最早于1953年由N.Metropolis等學(xué)者所提出基本概念是模擬物理界熱處理的退火（annealing）過(guò)程；當(dāng)固體加熱至一定的溫度并熔化成液態(tài)后，再緩慢降溫凝結(jié)成固態(tài)的情形，此時(shí)分子便可重新排列呈預(yù)期的穩(wěn)定狀態(tài)1983年Kirkpatrick等學(xué)者將此算法應(yīng)用于網(wǎng)絡(luò)組合最佳化問(wèn)題，始引起學(xué)術(shù)界的重視SA使用最陡坡降法（steepestdescentmethod），使最終解收斂于一個(gè)區(qū)域最佳解，并使用隨機(jī)過(guò)程法將其跳脫區(qū)域最佳解p.9/47模擬退火法步驟（極小化問(wèn)題）p.10/47SA算法的說(shuō)明及特性SA算法的說(shuō)明：

以上算法每次迭代僅執(zhí)行一次移步。也可在每次迭代中執(zhí)行數(shù)次移步（即鄰近搜尋）可接受較現(xiàn)行解差的解，接受的機(jī)率則由接受函數(shù)決定。因Tn隨著n增加而降低，因此接受機(jī)率逐漸降低可用最大搜尋次數(shù)或連續(xù)未改善次數(shù)為停止條件，亦可用溫度小于預(yù)設(shè)值為停止條件SA的特性：允許接受較現(xiàn)行解差的鄰近可行解，以跳脫區(qū)域最佳解以機(jī)率方式?jīng)Q定是否接受較差的解接受函數(shù)由溫度（控制參數(shù)）決定，因溫度隨著迭代次數(shù)增加而降低，因此接受機(jī)率會(huì)逐漸降低。p.11/47SA應(yīng)用于旅行推銷(xiāo)員問(wèn)題(TSP)從城市1出發(fā)，必須拜訪每個(gè)城市且僅能拜訪一次，然后再回到城市1，最佳路徑為何？p.12/47SA應(yīng)用于旅行推銷(xiāo)員問(wèn)題(TSP)Sol:p.13/47SA應(yīng)用于旅行推銷(xiāo)員問(wèn)題(TSP)Sol:p.14/4714.4

禁忌搜尋法禁忌搜尋法（tabusearch；TS）亦稱塔布搜尋法，最早是由FredGlover于1989年所提出。兩種記憶方式短期記憶將最近的移步（move）記錄于禁忌名單（tabulist；TL）中，避免重覆搜尋而落入?yún)^(qū)域最佳解，并加入免禁準(zhǔn)則（aspirationlevel），讓較佳移步不受TL限制長(zhǎng)期記憶一方面使用加強(qiáng)性（intensification）策略，專注于較佳的區(qū)域中，另一方面使用分散性（diversification）策略，以探索新的求解空間p.15/4714.4

禁忌搜尋法TS求解極小化問(wèn)題的執(zhí)行步驟（僅含短期記憶）p.16/47TS應(yīng)用于旅行推銷(xiāo)員問(wèn)題使用效果較佳的插入法產(chǎn)生初始解：由節(jié)點(diǎn)（城市）1開(kāi)始，選擇與節(jié)點(diǎn)1最近的節(jié)點(diǎn)。由節(jié)點(diǎn)1與節(jié)點(diǎn)形成回路（即）R。任取回路R以外的節(jié)點(diǎn)，將該節(jié)點(diǎn)插入R中，并選擇插入后之回路路徑最短者，將此新的回路取代原來(lái)的R。重覆執(zhí)行步驟2，直到回路R包含所有的節(jié)點(diǎn)為止。p.17/47TS應(yīng)用于旅行推銷(xiāo)員問(wèn)題Sol:p.18/47TS應(yīng)用于旅行推銷(xiāo)員問(wèn)題Sol:p.19/4714.5

基因算法基因算法（geneticalgorithms；GA）最早是由JohnHolland于1975年提出主要想法源自于達(dá)爾文「物競(jìng)天擇，適者生存」的進(jìn)化論作法簡(jiǎn)介一個(gè)染色體代表一個(gè)解，由一連串的基因（gene）所組成各染色體的基因值由0或1表示，并以合適度函數(shù)（fitnessfunction）評(píng)估染色體模擬問(wèn)題的適合度接著將現(xiàn)階段的染色體運(yùn)用選?。╯election）、交配（crossover）及突變（mutation）三種運(yùn)算，模仿自然界的生物演化過(guò)程，以產(chǎn)生新染色體現(xiàn)階段的染色體為母代（parents），下階段的新染色體為子代（children），每一個(gè)世代（generation）染色體的集合為族群（population）p.20/47基因算法步驟p.21/47基因算法說(shuō)明編碼：一般采用兩種方法：二元編碼法和順序編碼法合適度函數(shù)：用以評(píng)估每個(gè)染色體的優(yōu)劣。若為極大化問(wèn)題，可直接作為合適度函數(shù)；若為極小化問(wèn)題，則可轉(zhuǎn)換：合適度函數(shù)值目標(biāo)函數(shù)值，其中max值一般選擇目前母代染色體中最大的目標(biāo)函數(shù)值選?。荷鲜鏊惴▋H以簡(jiǎn)單的方式選取最好的兩個(gè)染色體。一般常用的方法有：輪盤(pán)法（roulettewheelselection）和余數(shù)抽樣法（remainderstochasticsamplingwithoutreplacement）。p.22/47基因算法說(shuō)明(續(xù))交配：上述算法直接將最好的二個(gè)染色體進(jìn)行交配。一般常會(huì)先依交配率計(jì)算母代要進(jìn)行交換之解的個(gè)數(shù)。常用方式有：?jiǎn)吸c(diǎn)交配（one-pointcrossover）兩點(diǎn)交配（two-pointcrossover）位置交配（positionbasedcrossover）突變：藉由引進(jìn)新的基因樣式，跳脫區(qū)域最佳解。一般會(huì)先依突變率（mutationrate）計(jì)算母代要進(jìn)行突變之解的個(gè)數(shù)。常用方式有：相鄰兩點(diǎn)突變（adjacenttwo-pointmutation）任意兩點(diǎn)突變（arbitrarytwo-pointmutation）任意三點(diǎn)突變（arbitrarythree-pointmutation）移動(dòng)（shift）p.23/47基因算法的特性每次搜尋是多點(diǎn)方式，而非單點(diǎn)搜尋。交配及突變的運(yùn)算加入了機(jī)率機(jī)制，而非確定性法則。根據(jù)問(wèn)題的特性編碼，以編碼的結(jié)果執(zhí)行。合適度函數(shù)對(duì)于算法的速度和效果均很重要。特別適合于多目標(biāo)、非線性、甚至無(wú)法確定有可行解的問(wèn)題。具有高度的問(wèn)題獨(dú)立性，即使對(duì)問(wèn)題的特性不是十分了解，也可直接以GA求解。p.24/47GA應(yīng)用于旅行推銷(xiāo)員問(wèn)題使用順序編碼法定義每個(gè)染色體。隨機(jī)產(chǎn)生5個(gè)初始解作為第一代的族群，并評(píng)估各染色體之合適度函數(shù)值（路徑長(zhǎng)度）：選?。哼x取合適度值最大的兩個(gè)解：第2個(gè)及第5個(gè)染色體。交配：使用單點(diǎn)交配方式隨機(jī)產(chǎn)生一點(diǎn)，從母代重新組合基因，以繁衍產(chǎn)生兩個(gè)新的子代，如下圖所示。p.25/47GA應(yīng)用于旅行推銷(xiāo)員問(wèn)題子代染色體1編號(hào)2之染色體124853712485736161編號(hào)5之染色體173658241子代染色體2編號(hào)5之染色體173658217365244181編號(hào)2之染色體124853761p.26/47GA應(yīng)用于旅行推銷(xiāo)員問(wèn)題突變：假設(shè)依突變率，子代染色體2需進(jìn)行突變。使用任意兩點(diǎn)改變法進(jìn)行突變，如下圖所示：替代：將新的二個(gè)子代解，取代母代第3與4個(gè)染色體（最差的兩個(gè)解），取代后新的族群如下表所示：上述僅完成一個(gè)世代。例繼續(xù)執(zhí)行到第4世代時(shí)，所有的染色體皆為，其路徑長(zhǎng)度為906.9，表示收斂。但GA仍繼續(xù)做到n=100為止。子代染色體2173652481新子代染色體2123657481p.27/4714.6

粒子群最佳化算法粒子群最佳化算法（ParticleSwarmOptimization;PSO）由J.Kennedy與R.C.Eberhart于1995年所提出的一種演化式算法（evolutionaryalgorithm；EA）基于模擬鳥(niǎo)群覓食的行為鳥(niǎo)群在搜尋食物過(guò)程，會(huì)記憶自己過(guò)去最好的經(jīng)驗(yàn)并分享給同伴當(dāng)每次決定下一個(gè)搜尋的位置時(shí)，每只鳥(niǎo)會(huì)考量自己過(guò)去最好之經(jīng)驗(yàn)及其他同伴給予的最好經(jīng)驗(yàn)，調(diào)整飛行速度，飛到下一個(gè)位置每只鳥(niǎo)(即粒子particle)，粒子1在決定下一個(gè)搜尋的位置時(shí)，它會(huì)依自己過(guò)去學(xué)習(xí)的經(jīng)驗(yàn)，考慮朝向過(guò)去走過(guò)的路徑中距離食物最近的位置前進(jìn)，但它也會(huì)藉由群體（swarm）同伴分享的信息，考慮朝向同伴中最好經(jīng)驗(yàn)的位置前進(jìn)因此，粒子1會(huì)綜合「學(xué)習(xí)的經(jīng)驗(yàn)」與「群體的信息」，朝向虛線箭頭前進(jìn)到下一個(gè)位置。透過(guò)每個(gè)粒子一次一次的學(xué)習(xí)并分享給予其他粒子，PSO得以尋找到相當(dāng)不錯(cuò)的解p.28/4714.6

粒子群最佳化算法粒子群最佳化算法的圖示p.29/47PSO算法之步驟p.30/47PSO算法的說(shuō)明與特性算法說(shuō)明特性所需的參數(shù)設(shè)定較少。屬多點(diǎn)（群體）搜尋，而非單點(diǎn)搜尋。具有記憶性，應(yīng)用記憶過(guò)去表現(xiàn)及群體最佳的解，互相交換正向信息。以機(jī)率性法則更新速度，而非確定性法則。較適合連續(xù)型最佳化問(wèn)題，但亦可用于離散型最佳化問(wèn)題。p.31/47PSO算法求解范例p.32/47PSO算法求解范例p.33/47PSO算法求解范例p.34/47PSO算法求解范例p.35/4714.7

蟻群最佳化算法蟻群最佳化算法（antcolonyoptimization；ACO）于1992年由Dorigo模擬蟻群實(shí)際行為而來(lái)基本概念針對(duì)蟻群如何溝通，以及建立食物源與巢穴之間最短的路線進(jìn)行研究。當(dāng)螞蟻在覓食時(shí)，所走過(guò)的路徑會(huì)留下一種稱之為費(fèi)洛蒙（pheromone）的化學(xué)物質(zhì)，讓蟻群藉由費(fèi)洛蒙的濃度來(lái)判斷應(yīng)該行進(jìn)的路線。當(dāng)費(fèi)洛蒙濃度愈強(qiáng)，該路線被螞蟻選擇的機(jī)率也愈大；若一段時(shí)間不再有螞蟻經(jīng)過(guò)該路徑并貢獻(xiàn)費(fèi)洛蒙時(shí)，其費(fèi)洛蒙濃度便會(huì)降低。最終所有螞蟻會(huì)因費(fèi)落蒙的引導(dǎo)，均選擇行進(jìn)較短的路徑。p.36/4714.7

蟻群最佳化算法（極大化問(wèn)題）p.37/4714.7

蟻群最佳化算法（極大化問(wèn)題）p.38/47ACO算法之說(shuō)明參數(shù)設(shè)定：包括螞蟻個(gè)數(shù)、費(fèi)洛蒙蒸發(fā)比例、費(fèi)洛蒙量（pheromonetrails）與貪婪法則（greedyheuristic）之相對(duì)重要性參數(shù)，以及控制「開(kāi)發(fā)」與「探索」之相對(duì)比例的參數(shù)q0。狀態(tài)轉(zhuǎn)移法則：狀態(tài)轉(zhuǎn)移法則在開(kāi)發(fā)（exploitation）和探索（exploration）之間提供了一個(gè)平衡機(jī)制。所謂「開(kāi)發(fā)」（q<=q0）是螞蟻參考過(guò)去所經(jīng)歷的較佳路徑，以獲得更好的解；「探索」（q>q0）則是欲發(fā)現(xiàn)未曾嘗試過(guò)的解，以避免陷入?yún)^(qū)域最佳解。貪婪法則：ACO的螞蟻不同于