【正文】 簽字日期： 年 月 日 摘要摘 要蟻群優(yōu)化算法是一種群體智能算法，是自然界中螞蟻群落在尋找食物過程的模擬，是一種新興的智能進(jìn)化算法，是專門解決離散的棘手的問題，在許多應(yīng)用中，充分展示了其優(yōu)點(diǎn)，在算法的改進(jìn)方面也取得了很好的成果。根據(jù)蟻群算法的特點(diǎn)，本文提出了基于目標(biāo)函數(shù)梯度的模擬退火蟻群算法和夾角優(yōu)化的蟻群算法。2. 簡要介紹了蟻群算法的基本原理、算法步驟及流程，最后分析了算法的優(yōu)缺點(diǎn)等。蟻群算法是一種新興的群智能概率型搜索算法，在解決這類問題中起到了重要作用，本文在常規(guī)的蟻群算法基礎(chǔ)上對(duì)其做了兩方面的改進(jìn)。在優(yōu)化過程中，根據(jù)目標(biāo)函數(shù)的梯度動(dòng)態(tài)地控制信息素濃度和回火過程，并以旅行商問題為例，根據(jù)數(shù)值實(shí)驗(yàn)結(jié)果對(duì)新算法的全局收斂性和解的質(zhì)量進(jìn)行了評(píng)測(cè)。這種情況下，研究者們對(duì)一些社會(huì)性動(dòng)物[25]（螞蟻、蜜蜂、魚、鳥等）的自組織行為產(chǎn)生了興趣，許多學(xué)者利用數(shù)學(xué)建模和計(jì)算機(jī)仿真技術(shù)，產(chǎn)生了“群智能”。來自公開文獻(xiàn)的資料顯示，在國際群體智能計(jì)算領(lǐng)域，蟻群算法已經(jīng)成為一個(gè)熱門的研究方向。隨著社會(huì)的進(jìn)步，特別是智能理論和應(yīng)用算法研究和發(fā)展，學(xué)者們已經(jīng)取得了很大進(jìn)展，試圖將其應(yīng)用于現(xiàn)實(shí)實(shí)踐中，并取得了意想不到的成果。所以，進(jìn)行計(jì)算時(shí)，通過計(jì)算方向夾角余弦值，從起始點(diǎn)開始尋找與其連接的線段形成較小夾角的那條路線，依次尋找，便可求出最短路徑。3. 闡述了模擬退火算法的基本原理和算法流程，然后介紹基于目標(biāo)函數(shù)梯度的模擬退火蟻群混合算法的基本原理和算法流程，并給出新算法對(duì)TSP問題優(yōu)化的實(shí)驗(yàn)結(jié)果。螞蟻在尋找食物的過程中，如果從巢到食物源的距離很短，那么螞蟻從巢到食物源，然后再返回巢的時(shí)間就短，這表明，在同一時(shí)間內(nèi)，較短路徑的螞蟻會(huì)分泌和積累更多的信息素。當(dāng)時(shí)，如圖1(b) 所示，只螞蟻從出發(fā)，以相同的概率選擇和，因此，各方向有只螞蟻行走。當(dāng)時(shí)，如圖1(f) 所示，前只螞蟻又回到點(diǎn)并再次面臨向左還是向右的選擇，此時(shí)，經(jīng)過的螞蟻數(shù)量為，而經(jīng)過的螞蟻數(shù)量為，明顯的信息素多于，這條路線會(huì)出現(xiàn)更多的螞蟻。在整個(gè)算法過程，人工模擬螞蟻不同于真實(shí)螞蟻的是：螞蟻具有記憶性，也就是說一只螞蟻選擇過的路徑在下次搜索時(shí)就不會(huì)再被選擇，為了方便計(jì)算，我們建立禁忌表來代表螞蟻訪問過的城市。根據(jù)具體情況可以有不同的表達(dá)方式。目前來看，蟻群算法在許多領(lǐng)域都有廣泛的應(yīng)用并取得了良好的成果，但是它自身也存在一些缺陷。(3) 可以隨意地與多種啟發(fā)式算法自由組合，以提高解的性能。(4) 容易出現(xiàn)停滯，搜索到一定程度，所有個(gè)體的解決方案完全相同，沒有進(jìn)一步搜索解空間，不利于找到更好的解決方案。該算法的基本思想是從一給定解開始的，從鄰域中隨機(jī)生成另一個(gè)解，接受準(zhǔn)則允許的目標(biāo)函數(shù)惡化在有效范圍內(nèi)，它由一控制參數(shù)決定，算法由初始解和控制參數(shù)初值開始反復(fù)進(jìn)行“生成新解—計(jì)算目標(biāo)函數(shù)值的差—接受或拒絕”這一迭代過程，它對(duì)應(yīng)著固體在某恒定高溫下趨于熱平衡的過程，減少了控制參數(shù)，系統(tǒng)越來越趨于平衡狀態(tài)，最終的系統(tǒng)狀態(tài)對(duì)應(yīng)于優(yōu)化問題的整體最優(yōu)解，需要指出的是，由于固體退火緩慢冷卻可以使固體在所有溫度下達(dá)到熱平衡，因此，控制參數(shù)必須緩緩衰減才能保證優(yōu)化問題趨于整體最優(yōu)解。模擬退火算法的流程圖如下：圖3 模擬退火算法流程圖Fig3 The flowchart of simulated annealing algorithm 基于目標(biāo)函數(shù)梯度的模擬退火蟻群算法 混合算法的基本原理通過以上對(duì)蟻群算法和模擬退火算法基本原理的研究可知，蟻群算法的優(yōu)點(diǎn)是正反饋、自組織、分布式，缺點(diǎn)是易限于局部最優(yōu)解，收斂速度慢。 算法流程考慮到模擬退火算法和蟻群算法各自的特點(diǎn)，許多學(xué)者先后提出了基于模擬退火算法和蟻群算法的混合智能優(yōu)化算法[16]。本文提出了一種基于目標(biāo)函數(shù)梯度的模擬退火蟻群混合算法，在優(yōu)化過程中，根據(jù)目標(biāo)函數(shù)的梯度動(dòng)態(tài)地控制信息素濃度和回火過程，并根據(jù)數(shù)值實(shí)驗(yàn)結(jié)果對(duì)新算法的全局收斂性和解的質(zhì)量進(jìn)行了評(píng)測(cè)。因此，為了解決這個(gè)問題，我們?cè)谒惴ㄖ幸牖鼗饳C(jī)制，回火是指將溫度略微升高后再降溫的策略。當(dāng)小于設(shè)定的閾值(通常取為)時(shí)，根據(jù)(2)式加強(qiáng)信息素；當(dāng)大于設(shè)定的閾值(通常取為)時(shí)，采用回火策略。最新研究成果表明，上述TSP問題的理論最優(yōu)解為15377km，常規(guī)模擬退火蟻群混合算法的最優(yōu)解為15601。4 夾角優(yōu)化的蟻群算法及在路徑規(guī)劃中的應(yīng)用4夾角優(yōu)化的蟻群算法及在路徑規(guī)劃中的應(yīng)用 對(duì)路徑規(guī)劃問題的描述根據(jù)規(guī)劃的目的是不同的，路徑規(guī)劃可分為多車輛路徑規(guī)劃和單個(gè)車輛路徑規(guī)劃[2124]，前者主要用于車隊(duì)調(diào)度和交通管制，后者多用于各種導(dǎo)航系統(tǒng)，主要研究的問題是在給定的城市道路網(wǎng)中如何尋找從起始點(diǎn)到目標(biāo)點(diǎn)的一段最佳行駛路線，即最短路線。在如何解決路徑規(guī)劃問題這方面，近年來國內(nèi)外學(xué)者已經(jīng)做了大量的研究[26]，這其中包括蟻群算法、人工勢(shì)場法、啟發(fā)式搜索算法、神經(jīng)網(wǎng)絡(luò)算法、模糊算法、遺傳算法[27]等等。這些算法都是圍繞全局收斂和提高算法收斂速度這兩點(diǎn)進(jìn)行的，但是這兩者是矛盾的統(tǒng)一體，不可能同時(shí)達(dá)到，因此要更好地改進(jìn)蟻群算法必須充分考慮它的啟發(fā)信息。解決路徑規(guī)劃問題，起始點(diǎn)和目標(biāo)點(diǎn)的位置是已知的，如路徑規(guī)劃是顯示在圖7，我們可以考慮空間幾何關(guān)系作為啟發(fā)式信息。那么對(duì)可行路徑的優(yōu)化模型為：，其中表示路徑點(diǎn)和之間的路線長度。假設(shè)城市道路網(wǎng)絡(luò)平面示意圖如圖8所示：圖8 方向夾角啟發(fā)信息Fig8 The angle between the direction of heuristic information不妨設(shè)所求路線是起點(diǎn)到終點(diǎn)的一條最短路，我們認(rèn)為與夾角越小的路徑段越有可能是全局最優(yōu)路徑的一部分，由于和相連接的點(diǎn)是點(diǎn)和點(diǎn)，不難看出，有向線段和的夾角小于線段和線段之間的夾角，因此，首先選擇節(jié)點(diǎn)；同理，與相連的節(jié)點(diǎn)是和，優(yōu)先選擇節(jié)點(diǎn)；同理，優(yōu)先選擇。 基本原理在本文的路徑規(guī)劃問題中，由于為路徑點(diǎn)和之間的有向路徑線段長度，為連接起始點(diǎn)和目標(biāo)點(diǎn)的有向線段，為與之間的夾角，與夾角越小的線段就越可能是最優(yōu)路線的一部分，也就是說越小，選擇該路徑的概率就越大，所以，進(jìn)行計(jì)算時(shí)，通過計(jì)算方向夾角余弦值，從起始點(diǎn)開始尋找與其連接的線段形成較小夾角的那條路線，依次尋找，便可求出最短路徑。為了有效地解決這個(gè)問題，算法在式(15)中加入了這一項(xiàng)，適當(dāng)縮小了各個(gè)可選路徑線段啟發(fā)信息數(shù)量的差異，對(duì)啟發(fā)信息數(shù)量較小的路徑段，相對(duì)增加其選擇概率[32]，加強(qiáng)蟻群算法的全局搜索能力。圖10為夾角優(yōu)化蟻群算法的流程圖：圖10 夾角優(yōu)化蟻群算法流程圖Fig10 the flowchart of ant colony optimization angle 實(shí)例與分析為了檢驗(yàn)夾角優(yōu)化蟻群算法的性能，下面用此算法在200*200的二維空間中尋找一條從起點(diǎn)S(20,180)到終點(diǎn)T(160,90)的最優(yōu)路徑，該二維空間中存在4個(gè)障礙物，障礙物1的4個(gè)頂點(diǎn)坐標(biāo)分別為(40,140。 30,40。 180,170。圖11中分別給出了常規(guī)蟻群算法和夾角優(yōu)化蟻群算法所得的最優(yōu)路徑，其中虛線所示為常規(guī)蟻群算法的最優(yōu)路徑，實(shí)線所示為夾角優(yōu)化蟻群算法的最優(yōu)路徑。本文在蟻群算法的基礎(chǔ)上進(jìn)一步做了兩方面的改進(jìn)：首先對(duì)蟻群算法和模擬退火算法進(jìn)行結(jié)合形成模擬退火蟻群混合算法，又加入目標(biāo)函數(shù)的梯度這一因素，對(duì)這種混合算法進(jìn)行了創(chuàng)新和改進(jìn)；另外，在利用常規(guī)的蟻群算法解決路徑規(guī)劃問題的基礎(chǔ)上，又考慮到方向夾角的因素對(duì)路徑規(guī)劃問題中的蟻群算法進(jìn)行改進(jìn)，形成夾角優(yōu)化的蟻群算法。參考文獻(xiàn)參考文獻(xiàn)[1] Dorigo M. Optimization, learning and natural algorithms [D]. PhD thesis, Dipartimento di Elettronica, Politeico di Milano, Italy, 1992: 140.[2] Bonabeau E, Dorigo M, Theraulaz G. Inspiration for optimization from social insect behavior [J]. Nature, 2000, 406(6): 3942.[3] Michael J B K, JeanBernarrd B, Laurent K. Antlike task and recruitment in cooperation robots [J]. Nature, 2000, 406(31): 992995.[4] Jackson D E, Holbe M, Ratnieks F L W. Trail geometry gives polarity to ant foraging networks [J]. Nature, 2004, 432(7019): 907909.[5] N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller, E. Teller. Equation of State Calculations by Fast Computing Machines [J]. J. Chem. Phys, 1953, 21(6): 10871092.[6] S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi. Optimization by simulated annealing [J]. Science, 1983, 220(4598): 671680.[7] Carter J H. The immune system as a model for pattern recognition and classification. Journal of the American Medical Informatics Association, 2000, 7(1):2841. [8] Castiglione F, Motta S, Nicosia G. Pattern recognition by primary and secondary response of an artificial immune system. Theory in Biosciences, 2001, 120(2):93106. [9] White J A, Garrett S M. Improved pattern recognition with artificial clonally selection. Lecture Notes in Computer Science, 2003, 2787:181193.[10] Tang Z, Tashima K, Cao Q P. Pattern recognition system using a clonally selectionbased immune network. Systems and Computers in Japan, 2003, 34(12):5663.[11] Foukia N, Hassas S, Fenet S et al. Combining immune systems and social insect metaphors: a paradigm for distributed intrusion