【文章內(nèi)容簡(jiǎn)介】 比較大。簡(jiǎn)單來(lái)說(shuō)，蟻群算法的基本原理在于以下三點(diǎn)：(1) 螞蟻能連續(xù)不斷地釋放信息素；(2) 螞蟻能感知小范圍區(qū)域內(nèi)狀況；(3) 螞蟻釋放出的信息素隨時(shí)間逐步減少。在此，我們可以使用圖像來(lái)說(shuō)明螞蟻的搜索原則和機(jī)制：. 圖1 螞蟻路徑尋優(yōu)過(guò)程Fig1 The procedure of searching the shortest path如圖1所示，表示蟻穴，表示事物，表示障礙物，螞蟻從到有兩條路徑，分別是和，長(zhǎng)度分別是和，并對(duì)螞蟻可以走的距離做出規(guī)定，即單位時(shí)間內(nèi)螞蟻?zhàn)咭粋€(gè)單位長(zhǎng)度，剛開(kāi)始所有道路上都沒(méi)有信息素，所以螞蟻?zhàn)畛踹x擇路徑的概率是一樣的。當(dāng)時(shí)，如圖1(b) 所示，只螞蟻從出發(fā)，以相同的概率選擇和，因此，各方向有只螞蟻行走。當(dāng)時(shí)，如圖1(c) 所示，沿著的第一組螞蟻到達(dá)并準(zhǔn)備返回，而第二組在的中點(diǎn)處。當(dāng)時(shí)，如圖1(d) 所示，兩組螞蟻在點(diǎn)相遇，且和的信息素?cái)?shù)量相同，此時(shí)，第一組返回的只螞蟻到達(dá)點(diǎn)并以等概率分別走向、第二組螞蟻依然走向。當(dāng)時(shí)，如圖1(e) 所示，沿著返回的只螞蟻到達(dá)，另只在中點(diǎn)處，還有第二組中在中點(diǎn)和點(diǎn)處各只螞蟻。當(dāng)時(shí)，如圖1(f) 所示，前只螞蟻又回到點(diǎn)并再次面臨向左還是向右的選擇，此時(shí)，經(jīng)過(guò)的螞蟻數(shù)量為，而經(jīng)過(guò)的螞蟻數(shù)量為，明顯的信息素多于，這條路線會(huì)出現(xiàn)更多的螞蟻。按照這個(gè)過(guò)程不斷循環(huán)下去，路徑越短，信息素積累就越多，久而久之，它們信息素?cái)?shù)量的差距將越來(lái)越明顯，路徑將會(huì)有更多的螞蟻出現(xiàn)，如果時(shí)間足夠長(zhǎng)，最終所有的螞蟻都會(huì)毫無(wú)偏向地選擇這條路線。 蟻群算法的算法流程蟻群算法是一種廣義型的隨機(jī)優(yōu)化方法[17]，像其他模型進(jìn)化算法，是通過(guò)候選解組成的群體，以確定最優(yōu)解的進(jìn)化過(guò)程，選擇一條搜索路徑最初只是隨機(jī)的概率，重復(fù)這個(gè)過(guò)程，成為一個(gè)有規(guī)律的搜索，并逐步接近“更好的”解決方案。最終達(dá)到全局最優(yōu)。在整個(gè)算法過(guò)程，人工模擬螞蟻不同于真實(shí)螞蟻的是：螞蟻具有記憶性，也就是說(shuō)一只螞蟻選擇過(guò)的路徑在下次搜索時(shí)就不會(huì)再被選擇，為了方便計(jì)算，我們建立禁忌表來(lái)代表螞蟻訪問(wèn)過(guò)的城市。旅行商問(wèn)題的解決有效使用了蟻群算法，下面介紹其基本算法：已知有只螞蟻,座城市,表示城市到之間的距離，表示到的可見(jiàn)度，表示時(shí)刻在路上的信息素強(qiáng)度，也可以把理解為訪問(wèn)完城市之后立刻訪問(wèn)城市的期望程度，表示啟發(fā)式信息可，也就是說(shuō)，從路徑直接走到的期望程度與兩條路徑之間的距離成反比。每只螞蟻按照如下過(guò)程建構(gòu)一條行走路線：(1) 根據(jù)某些規(guī)則，它們會(huì)依照概率選擇一個(gè)城市作為起點(diǎn)，我們把螞蟻放到該城市；(2) 螞蟻利用啟發(fā)式信息和信息素強(qiáng)度，以一定的概率選擇下一個(gè)允許訪問(wèn)的城市（表示螞蟻下一個(gè)要走的城市），這里用禁忌表來(lái)控制不允許訪問(wèn)的城市（設(shè)表示第只螞蟻的禁忌表，表示中第個(gè)元素）；(3) 螞蟻行走一周返回起始城市后，在每一條路徑上會(huì)留下信息素。初始時(shí)刻，每條路徑上的信息素相等可設(shè)為常數(shù)，即，螞蟻在運(yùn)動(dòng)過(guò)程中根據(jù)信息素?cái)?shù)量的變化而移動(dòng)，我們用表示在時(shí)刻螞蟻由路徑轉(zhuǎn)移到的概率，則： (1)由于信息素隨著時(shí)間發(fā)生改變，故螞蟻完成一次循環(huán)后，各路上的信息素也將進(jìn)行更新： (2) (3) (4)其中，和分別表示信息素和可見(jiàn)度的影響性，表示信息素的殘留系數(shù)，表示第只螞蟻在路徑上的信息素，表示路徑上的信息素增長(zhǎng)量，表示第只螞蟻?zhàn)咄暌蝗Φ穆肪€長(zhǎng)度，為常數(shù)。根據(jù)具體情況可以有不同的表達(dá)方式。曾給出了三種不同類型，分別為、它們的區(qū)別在于不同的表達(dá)(4)，在模型中： (5)在模型[14]中： (6) 我們通常把第一種模型看作基本的模型，因?yàn)樗紤]的是整體信息，解決問(wèn)題的性能相對(duì)好。經(jīng)過(guò)以上的分析，蟻群算法的基本步驟總結(jié)如下：(1) 初始化參數(shù)，將只螞蟻放在個(gè)結(jié)點(diǎn)上；(2) 據(jù)式(1)計(jì)算每只螞蟻移動(dòng)到下一結(jié)點(diǎn)的概率，并根據(jù)其概率進(jìn)行選擇下一個(gè)結(jié)點(diǎn)；(3) 螞蟻遍歷一周后計(jì)算路徑長(zhǎng)度，按式(3)更新信息素增量；(4) 所有路徑的信息素更新按式(2)進(jìn)行；(5) 重復(fù)2至4步，直至滿足迭代終止條件輸出最好解。綜上分析可知，蟻群算法的基本流程圖如下：圖2 蟻群算法流程圖Fig2 The flowchart of ant colony algorithm 蟻群算法的優(yōu)缺點(diǎn)蟻群算法是一種典型的概率算法[18]，隨機(jī)性較強(qiáng)，況且各參數(shù)的設(shè)定通常由試驗(yàn)方法確定與人的經(jīng)驗(yàn)密切相關(guān)，缺乏一定的精確性。目前來(lái)看，蟻群算法在許多領(lǐng)域都有廣泛的應(yīng)用并取得了良好的成果，但是它自身也存在一些缺陷。下面對(duì)蟻群算法的優(yōu)缺點(diǎn)進(jìn)行簡(jiǎn)單地歸納總結(jié)。蟻群算法的優(yōu)點(diǎn)：(1) 與其它啟發(fā)式優(yōu)化算法相比，蟻群算法具有較強(qiáng)的魯棒性。2 蟻群算法的原理及過(guò)程31(2) 具有本質(zhì)并行性，易于并行實(shí)現(xiàn)。(3) 可以隨意地與多種啟發(fā)式算法自由組合，以提高解的性能。蟻群算法的缺點(diǎn)：(1) 如果不能恰當(dāng)?shù)卦O(shè)置參數(shù)，很容易導(dǎo)致慢收斂速度和質(zhì)量較差的解。(2) 基本蟻群算法計(jì)算量大，需要很久才能求出解。(3) 初始信息素的缺乏，會(huì)導(dǎo)致收斂速度慢，并且易陷入局部最優(yōu)。(4) 容易出現(xiàn)停滯，搜索到一定程度，所有個(gè)體的解決方案完全相同，沒(méi)有進(jìn)一步搜索解空間，不利于找到更好的解決方案。3 基于目標(biāo)函數(shù)梯度的模擬退火蟻群算法3基于目標(biāo)函數(shù)梯度的模擬退火蟻群算法 模擬退火算法的基本原理和算法流程模擬退火算法是基于迭代算法的一種啟發(fā)式隨機(jī)搜索算法[19]，最早的思想由等人于1953年提出[20]。它源于物理中對(duì)固體退火過(guò)程的模擬，分為升溫、平衡、冷卻三個(gè)階段，先將固體加溫至充分高，再讓其漸漸冷卻，升溫時(shí)粒子變?yōu)闊o(wú)序狀內(nèi)能增大，冷卻時(shí)粒子變得有序，內(nèi)能逐漸減小。由此過(guò)程，可將模擬退火算法應(yīng)用于求解組合優(yōu)化問(wèn)題，此時(shí)，將內(nèi)能模擬為目標(biāo)函數(shù)，溫度對(duì)應(yīng)于控制參數(shù)，并用冷卻控制表控制算法進(jìn)程。該算法的基本思想是從一給定解開(kāi)始的，從鄰域中隨機(jī)生成另一個(gè)解，接受準(zhǔn)則允許的目標(biāo)函數(shù)惡化在有效范圍內(nèi)，它由一控制參數(shù)決定，算法由初始解和控制參數(shù)初值開(kāi)始反復(fù)進(jìn)行“生成新解—計(jì)算目標(biāo)函數(shù)值的差—接受或拒絕”這一迭代過(guò)程，它對(duì)應(yīng)著固體在某恒定高溫下趨于熱平衡的過(guò)程，減少了控制參數(shù)，系統(tǒng)越來(lái)越趨于平衡狀態(tài)，最終的系統(tǒng)狀態(tài)對(duì)應(yīng)于優(yōu)化問(wèn)題的整體最優(yōu)解，需要指出的是，由于固體退火緩慢冷卻可以使固體在所有溫度下達(dá)到熱平衡，因此，控制參數(shù)必須緩緩衰減才能保證優(yōu)化問(wèn)題趨于整體最優(yōu)解。在判斷新解是否被接受，我們通常使用準(zhǔn)則來(lái)判斷是否為新解：若目標(biāo)函數(shù)值的差，則接受作為當(dāng)前解；否則，若，則接受作為新解，否則舍棄。模擬退火算法的基本流程如下：(1) 參數(shù)初始化。給定初始溫度（足夠大）和退火速度，初始解及目標(biāo)函數(shù)；(2) 隨機(jī)擾動(dòng)產(chǎn)生新解，計(jì)算；(3) 若，作為當(dāng)前解；否則，若，為新解，否則舍棄，仍為當(dāng)前解；(4) 對(duì)進(jìn)行緩慢降溫，重復(fù)步驟2至3，直至滿足迭代條件。模擬退火算法的流程圖如下：圖3 模擬退火算法流程圖Fig3 The flowchart of simulated annealing algorithm 基于目標(biāo)函數(shù)梯度的模擬退火蟻群算法 混合算法的基本原理通過(guò)以上對(duì)蟻群算法和模擬退火算法基本原理的研究可知，蟻群算法的優(yōu)點(diǎn)是正反饋、自組織、分布式，缺點(diǎn)是易限于局部最優(yōu)解，收斂速度慢。模擬退火算法的優(yōu)點(diǎn)是算法簡(jiǎn)單、魯棒性強(qiáng)、具有全局搜索能力，特別適用于復(fù)雜的非線性問(wèn)題，缺點(diǎn)是對(duì)初始解有很強(qiáng)的依賴性，當(dāng)系統(tǒng)不使用反饋信息，在一定程度上的解是大量的冗余迭代造成的，精確率低。因此根據(jù)各自的優(yōu)缺點(diǎn)可以將兩種智能優(yōu)化算法根據(jù)某種法則相融合或在某種優(yōu)化算法中引入其它優(yōu)化思想，形成混合優(yōu)化算法，可以充分發(fā)揮智能算法各自的優(yōu)點(diǎn)，揚(yáng)長(zhǎng)避短，以便取得時(shí)間性能和優(yōu)化性能的雙贏，提高算法各方面的性能。模擬退火算法和蟻群算法混合的基本思路是：第一，利用模擬退火算法得到一些更好的解，在其路徑上留下信息素，其它東西不變；第二，根據(jù)蟻群算法讓螞蟻進(jìn)行一次周游；第三，采用模擬退火算法在鄰域內(nèi)尋找另外一個(gè)解，找到的這個(gè)解有可能變壞，為了簡(jiǎn)化計(jì)算可限定一個(gè)目標(biāo)函數(shù)變壞的范圍，若路徑長(zhǎng)度差，接受新解，否則舍棄。 算法流程考慮到模擬退火算法和蟻群算法各自的特點(diǎn)，許多學(xué)者先后提出了基于模擬退火算法和蟻群算法的混合智能優(yōu)化算法[16]。許智宏提出一種模擬退火蟻群并行算法[17]。劉波提出了一種基于模擬退火機(jī)制的蟻群算法，該算法在高溫階段以高概率加入更新集，在低溫階段采用回火策略[18]。常規(guī)的模擬退火蟻群算法不考慮目標(biāo)函數(shù)的變化率，只是采用固定的更新信息素的方法和降溫的方法，這就有可能產(chǎn)生冗余迭代，并且在一定程度上影響了解的質(zhì)量。本文提出了一種基于目標(biāo)函數(shù)梯度的模擬退火蟻群混合算法，在優(yōu)化過(guò)程中，根據(jù)目標(biāo)函數(shù)的梯度動(dòng)態(tài)地控制信息素濃度和回火過(guò)程，并根據(jù)數(shù)值實(shí)驗(yàn)結(jié)果對(duì)新算法的全局收斂性和解的質(zhì)量進(jìn)行了評(píng)測(cè)。該混合算法充分考慮了目標(biāo)函數(shù)的梯度，當(dāng)目標(biāo)函數(shù)的梯度較小時(shí)，加強(qiáng)當(dāng)前最優(yōu)解對(duì)應(yīng)的信息素，這相當(dāng)于在“平坦”之處加快搜索速度，使算法加快收斂；當(dāng)目標(biāo)函數(shù)的梯度過(guò)大時(shí)，引入回火策略[19]，即在“陡峭”之處放緩搜索速度，以提高解的質(zhì)量。并用改進(jìn)的算法求解旅行商問(wèn)題，結(jié)果表明，與常規(guī)的模擬退火蟻群算法相比，新算法的收斂速度和解的質(zhì)量均得到很大的改善。在本文中，設(shè)退火函數(shù)為（），在完成一輪搜索與信息素更新后，進(jìn)行退火即降溫，降溫過(guò)程中，當(dāng)系統(tǒng)溫度較高時(shí)，較差的解將以較高的概率進(jìn)入更新集，導(dǎo)致路徑上的信息素分布更加廣泛，避免出現(xiàn)早熟；隨著的降低，接受較差解的概率將逐漸減小，導(dǎo)致路徑上的信息素分布集中，算法將快速收斂，我們鼓勵(lì)過(guò)早收斂，采用較小的，這樣可以縮短找到更好解的時(shí)間以提高效率，但是，這樣會(huì)增大落入局部極值點(diǎn)的風(fēng)險(xiǎn)。因此，為了解決這個(gè)問(wèn)題，我們?cè)谒惴ㄖ幸牖鼗饳C(jī)制，回火是指將溫度略微升高后再降溫的策略?；鼗鸬臏囟确秶O(shè)為，若，將溫度升高至，重新進(jìn)行算法迭代，當(dāng)再次時(shí)，這一過(guò)程稱為回火過(guò)程，重復(fù)此過(guò)程，可以根據(jù)設(shè)定進(jìn)行多次回火，回火次數(shù)設(shè)為，最大回火次數(shù)?？紤]目標(biāo)函數(shù)梯度的具體方法是：定義 (7)其中 (8) (9)表示向量的第個(gè)分量。對(duì)于離散優(yōu)化問(wèn)題，不存在梯度，則 (10) (11) (12)其中，分別表示父代和子代個(gè)體。當(dāng)小于設(shè)定的閾值(通常取為)時(shí)，根據(jù)(2)式加強(qiáng)信息素；當(dāng)大于設(shè)定的閾值(通常取為)時(shí)，采用回火策略?；谀繕?biāo)函數(shù)梯度的模擬退火蟻群混合算法的流程如下：步驟1 初始化參數(shù)：；步驟2 利用模擬退火算法計(jì)算出一個(gè)較優(yōu)解，在這個(gè)路徑上留下信息素；步驟3 按上述方式，根據(jù)目標(biāo)函數(shù)梯度加強(qiáng)信息素，并采用回火策略；步驟4 將只螞蟻放在個(gè)結(jié)點(diǎn)處，并對(duì)每只螞蟻按式(1)的概率選擇下一個(gè)結(jié)點(diǎn)，完成一次循環(huán)；步驟5 在鄰域內(nèi)找另外一個(gè)解，若，接