第一章前言幾種典型的改進蟻群算法綜述目錄TOC\o"1-3"\h\u7122幾種典型的改進蟻群算法綜述 1150861.1帶精英策略的螞蟻系統(tǒng) 1245261.2蟻群系統(tǒng) 2250261.3最大最小螞蟻系統(tǒng) 3257551.4基于排序螞蟻系統(tǒng) 3近年來，為了提升蟻群算法求解TSP的性能，不少學(xué)者提出了改進版本的蟻群算法，接下來將對當(dāng)前四種經(jīng)典改進蟻群算法做個簡要介紹。1.1帶精英策略的螞蟻系統(tǒng)帶精英策略的螞蟻系統(tǒng)(AntSystemWithElitistStrategy,ASelite)作為一種典型的改進蟻群算法，其提升算法性能的手段來源于優(yōu)化算法信息素更新規(guī)則。精英策略最早出現(xiàn)于遺傳算法中，是為了避免算法中較優(yōu)個體的丟失而選擇直接將其保留至下一代中，有效避免較優(yōu)基因被破壞從而提升算法的性能。蟻群算法的精英策略則略有不同，算法中定義尋找最優(yōu)路徑的若干數(shù)量的螞蟻稱為精英螞蟻，算法會對精英螞蟻獲取的路徑給以額外的信息素，加大最優(yōu)路徑上信息素，加速算法尋優(yōu)，具體方式如下：(2-7)(2-8)式中，見公式(2-3)，表示采用精英策略對路徑進行額外信息素增益，表示精英螞蟻的數(shù)目，表示最優(yōu)解所對應(yīng)的路徑，表示最優(yōu)解的路徑長度。帶精英策略的螞蟻系統(tǒng)通過加大最優(yōu)路徑上的信息素，能夠有效提升算法求解速度，縮短了算法收斂的時間，但算法往往受到精英螞蟻數(shù)目的影響。一般來說，精英螞蟻數(shù)目設(shè)置過小，算法性能提升不夠明顯，相反，精英螞蟻數(shù)目設(shè)置過大，容易導(dǎo)致算法因過快集中于次最優(yōu)解周圍搜索而陷入早熟收斂，因此選擇一個合適的精英螞蟻數(shù)目對該算法尤為重要。1.2蟻群系統(tǒng)蟻群系統(tǒng)(AntColonySystem,ACS)最早由M.Dorigo提出[61]，是當(dāng)前算法性能最為有效的改進蟻群算法之一，它和基本蟻群算法之間區(qū)別主要包括以下幾點：采用偽隨機比例公式作為螞蟻選擇下個城市的策略，與基本蟻群算法狀態(tài)轉(zhuǎn)移規(guī)則相比存在不同的是，螞蟻將以一定的概率直接從的最大值來選擇下個城市，而不再是單純地使用輪盤賭法，減少了算法搜索的隨機性，提升了算法尋優(yōu)的速度。算法偽隨機比例公式S如下：(2-9)式中，q表示(0,1)之間的隨機數(shù)，q0是(0,1)之間的常數(shù)，即當(dāng)滿足時，算法直接從剩余城市中選擇最大值作為下個城市，否則依據(jù)(見公式(2-1))選擇下個城市。引入信息素局部更新規(guī)則，一旦螞蟻完成一次城市選擇，立馬對之前所走路徑的信息素進行更新，更新方式具體如下：(2-10)(2-11)式中，表示局部信息素揮發(fā)速率，表示算法初始信息素，設(shè)置方式如公式(2-11)所示，其中N表示城市總數(shù)目，表示采用最近鄰啟發(fā)式算法得到的路徑長度。算法在局部信息素更新的作用下，有效減少之間搜索過路徑上的信息素，加大算法搜索其他路徑的概率，從而提升算法搜索的多樣性，改善算法的性能。為了提升算法尋優(yōu)速度，算法只選取全局最優(yōu)解進行全局信息素更新，更新方式如下：(2-12)蟻群系統(tǒng)通過改進全局信息素更新和狀態(tài)轉(zhuǎn)移規(guī)則、引入局部信息素更新，減少了算法運行時間，極大地提升了算法收斂速度，由于算法只對全局最優(yōu)解進行信息素更新，算法因搜索多樣性不足易陷入局部最優(yōu)。不僅如此，先驗知識概率對算法性能有著一定的影響，如選取過大，算法將過大集中于次優(yōu)解周圍探索從而發(fā)生早熟收斂，選取過小，算法狀態(tài)轉(zhuǎn)移規(guī)則退化為基本蟻群算法狀態(tài)轉(zhuǎn)移規(guī)則，算法性能下降。因此需要對進行合理選取。1.3最大最小螞蟻系統(tǒng)最大最小螞蟻系統(tǒng)(Max-MinSystem,MMAS)最早由ThomasStutzle提出[62]，是目前最常用的蟻群算法之一，其與基本蟻群算法存在如下區(qū)別：引入信息素上下界，即為了避免算法搜索過程中因路徑上信息素差異過大致使算法陷入局部最優(yōu)或發(fā)生早熟收斂，則需要對各個路徑上的信息素設(shè)置在。初始信息素設(shè)置為。為了同時兼顧算法多樣性和收斂速度，最大最小螞蟻系統(tǒng)只選取一個解用以信息素更新，這個解來源于全局最優(yōu)解或循環(huán)最優(yōu)解，這和基本蟻群算法信息素更新方式存在很大不同，基本蟻群算法中會對所有螞蟻獲取的路徑進行信息素更新。本節(jié)算法信息素更新方式如下：(2-13)式中，代表全局最優(yōu)解或循環(huán)最優(yōu)解的長度。最大最小螞蟻系統(tǒng)最大的特點是將算法運行過程中的信息素值限制在內(nèi)，從而有效避免算法因各個路徑信息素差異過大而陷入局部最優(yōu)。1.4基于排序螞蟻系統(tǒng) 為了提升蟻群算法求解TSP的性能，近年來，有學(xué)者提出了基于優(yōu)化排序螞蟻系統(tǒng)(Rank-BasedVersionofAntSystem,ASrank)[63]。ASrank的核心思想是首先對所有螞蟻得到的解進行評價并按照優(yōu)劣性進行排序，選擇部分數(shù)量的較優(yōu)解進行全局信息素更新，其中信息素增益與解的優(yōu)劣性正相關(guān)。定義表示較優(yōu)解數(shù)目，信息素更新方式具體如下：(2-14)(2-15)其中，見公式(2-8)，表示t時刻排序為r的螞蟻得到的解，為對應(yīng)的路徑長度。基于優(yōu)化排序的螞蟻系統(tǒng)，只選取較優(yōu)的個解用以信息素更新，綜合考慮了算法搜索多樣性和收斂速度，有利于算法朝著全局最