叢　爽，賈亞軍
中國科學技術大學自動化系，安徽合肥

摘　　　要：針對進化策略收斂速度快但容易陷入早熟收斂以及較大較小螞蟻系統求解能力強但收斂速度較慢的特點，將進化策略與較大較小螞蟻系統融合，并利用較大較小螞蟻系統求出每一步迭代的較優解，再對迭代出較優解進行進化策略中的變異操作來加快解的收斂速度。將所提出的算法應用到中國旅行商問題（ＣＴＳＰ）的實際應用中，其結果顯示出優越性。

關　鍵　詞：進化策略；蟻群算法；較大較小蟻群系統；中國旅行商問題

１　引　言
２０世紀６０年代初，德國的Ｒｅｃｈｅｎｂｅｒｇ等人提出了進化策略，其優點是［１�玻常荩壕哂写蠓秶�全局搜索的能力；并行算法；搜索使用適應度函數作為評價函數，過程簡單。但它同時也有自身的缺點：對于系統中上一代解的信息利用不夠，當求解到一定范圍時往往做大量無用的冗余迭代，即容易陷入早熟收斂，求較優解效率較低。蟻群算法是一種基于種群的模擬進化啟發式算法。它是在對自然界中真實蟻群的集體行為研究的基礎上，于２０世紀９０年代由意大利學者Ｄｏｒｉｇｏ等人首先提出。其優點是［４�玻担荩合伻核惴ㄗ鳛閷ο伻阂捠承袨榈某橄螅�體現了群體行為的分布式特征；它是一種自組織算法；它是一種正反饋的算法。蟻群算法在解決一些小規模的ＴＳＰ問題時表現尚可令人滿意。但隨著問題規模的擴大，由于初期信息素的匱乏，很難在可接受的循環次數內找到較優解，收斂速度較慢。近年來不斷有學者提出了許多改進算法［５］，如帶精英策略的螞蟻系統（ＡＳｅｌｉｔｅ），蟻群系統（ＡＣＳ），較大－較小螞蟻系統（ＭＭＡＳ）等。針對進化策略和較大較小螞蟻系統各自的優缺點，本文將進化策略與較大較小螞蟻系統融合，利用ＭＭＡＳ生成迭代較優解，對迭代較優解采用進化策略中的變異操作，并將其應用到中國旅行商問題（ＣＴＳＰ）中。

登錄網站后可下載文件