2.1　學習型智能優化相關理論

在本節中，首先對相關概念進行了簡單界定，然后提出了學習型智能優化方法的基本框架，最后給出了學習型智能優化方法的運行機制。

2.1.1　知識

知識是對某個主題確信的認識。認知事物的能力是哲學中充滿爭議的中心議題之一，并且擁有它自己的分支——知識論。從更加實用的層次來看，知識通常被某些群體所共享，知識可通過不同方式來操作和管理。盡管知識是日常生活的中心組成部分，但它的確切定義仍是哲學家、社會科學家和歷史學家饒有興趣的話題。根據許多思想家的論述，知識必須具備三個特征：被證實的（justified）、真的（true）和被相信的（believed）⁽¹⁾。根據維基百科、互動百科⁽²⁾和百度百科⁽³⁾中的描述，常見的知識定義方式有以下幾種。

• 知識是一種被確認的信念，通過知識持有者和接收者的信念模式和約束來創造、組織和傳遞。知識是從信息中變化、重構、創造而得到的，其內涵比數據、信息要更廣、更深、更豐富。知識可分為顯性知識（explicit knowledge）和隱性知識（tacit knowledge）。顯性知識可用正規化的、系統化的語言來傳輸；隱性知識擁有個性化特征，很難被正規化和傳播。
• 知識是存在于專業人員身上的技能財產，可分為實證知識、高級技能、系統認知和自我激勵創造力等。
• 知識是資訊、文化脈絡及經驗的組合。
• 知識是企業的無形資產。
• 知識是用以輔助決策的事實、模式、概念、意見及直覺的集合體。
• 知識是從人類活動中所獲取的真理、原則、思想及資訊。
• 知識是經驗累積的記錄，事實組織的系統化，對事實的理解，一種理解的行為或狀態，人的已知和未知。
• 知識是與經驗、上下文（context）、解釋和思考（reflection）結合在一起的信息。知識是一種流動性質的綜合體，包括結構化的經驗和價值，經過文字化的資訊，專家獨特的見解。知識是一種可隨時幫助人們決策與行動的高價值信息。
• 《博弈圣經》中將知識定義為識別萬物實體與性質的是與不是。
• 《中國大百科全書·教育》中將知識表述為：就內容而言，是客觀事物屬性與聯系的反映，是客觀世界在人腦中的主觀映象。就反映活動形式而言，有時表現為主體對事物的感性知覺或表象（感性知識）；有時表現為關于事物的概念或規律（理性知識）。

由上述定義可知，知識是抽象的，是借由某種形式而呈現出來的、可互相傳達的概念。本書更多地關注一些顯性知識，即能明確表達的知識。顯性知識可通過口頭傳授、教科書、參考資料、報紙雜志、專利文獻、視聽媒體、軟件和數據庫等方式獲取，也可通過語言、書籍、文字、數據庫等編碼方式傳播。本書中用到的顯性知識，都可采用計算機語言來表示和存儲；同時，其他模型可通過給定方式對這些知識進行更新和應用。

2.1.2　知識模型

知識模型是指描述某一領域產品相關專家知識的信息模型。知識模型將專家知識、產品設計過程知識和環境知識等明確地表示于產品信息模型中，支持系統中智能模塊的信息表達和傳遞。知識模型通常基于系統功能和結構知識構建，通過符號或流程圖來描述。知識模型主要研究形式化和結構化的知識。

為了更加有效地利用知識，必須采用合適的技術來完成對相關知識的表達、獲取、存儲和應用。在本書中，知識模型主要完成以下功能：知識表達、知識獲取、知識存儲和知識應用。鑒于此，本書將知識模型定義為：為完成知識表達、知識獲取、知識存儲和知識應用而使用的技術、方法和手段的集合體。

知識表達就是如何采用計算機語言將用于解決問題的結構化信息表示出來。本書采用一維或多維數組來表示知識。用于表示知識的數組一般都具有特定含義，即數組中的每個元素都是可解釋的（具有明確含義）。

知識獲取就是采用特定方法來獲得一些感興趣的知識。在學習型智能優化方法中，知識獲取主要是指從智能優化方法的演化過程中挖掘（學習）有用知識。一般用到的知識獲取手段包括統計方法、機器學習和數據挖掘等。本書僅采用統計方式來完成對不同類型知識的挖掘。

知識存儲就是采用特定方式將一些感興趣的知識存儲起來。本書采用一維或多維數組來表示感興趣的知識，知識存儲就相對簡單。只要在相關程序中將表示知識的數組以全局變量形式定義出來，任何模型在任何時段都可訪問或更新這些數組。

知識應用就是采用特定方法將知識應用到優化問題的求解中。在學習型智能優化方法中，知識應用就是如何采用知識來指導后續演化（優化）過程。在2.2節中將介紹學習型智能優化方法中用到的幾類知識及其應用方式。

2.1.3　遺傳算法

遺傳算法和蟻群算法是兩種比較典型的智能優化方法，本書基于遺傳算法和蟻群算法構建了多種不同的學習型智能優化方法，因此分別對遺傳算法和蟻群算法的研究現狀進行了綜述。遺傳算法（genetic algorithm，GA）是借鑒生物界進化規律（適者生存和優勝劣汰遺傳機制）而演化出來的一類隨機搜索算法^[60-62]。遺傳算法由美國Michigan大學的Holland教授于20世紀70年代首次提出^[63]，非常適合于處理傳統優化方法難以解決的復雜的和非線性的優化問題^[64-67]。遺傳算法是一類具有魯棒性的搜索算法，主要有以下特點：以決策變量的編碼作為運算對象，直接以適應度作為搜索信息，使用概率搜索技術，使用多個點的搜索信息，具有隱含并行性。遺傳算法的基本運算流程如圖2.1所示。

2.1.3.1　遺傳算法的基本理論

遺傳算法的基本理論主要以收斂性分析（群體收斂到全局最優解的概率）為主，可分為基于隨機過程的收斂性研究和基于模式理論的收斂性分析^[68]。

（1）基于隨機過程的收斂性研究。對于有限編碼空間和有限群體，遺傳算法的搜索過程可表示為離散時間的馬爾可夫鏈模型，從而可采用隨機過程理論進行嚴密分析。Rudolph用齊次有限馬爾可夫鏈證明標準遺傳算法收斂不到全局最優解^[69]，若采用保留最優個體的選擇機制，則改進遺傳算法全局收斂。Eiben等用馬爾可夫鏈證明保留最優個體遺傳算法的依概率全局收斂^[70]。Qi等用馬爾可夫鏈證明浮點編碼遺傳算法是收斂的^{[68]，[71]，[72]}，但此結果是基于種群規模無窮大的假設。Fogel分析了沒有變異算子的遺傳算法的漸近收斂性^[73]。Suzuki用馬爾可夫鏈狀態轉移矩陣的特征根分析了遺傳算法的收斂行為^[74]。田軍用馬爾可夫鏈和隨機攝動理論證明了遺傳算法進入最小能量集的條件^[75]。張講社等用馬爾可夫鏈研究了基于擴展串的等價遺傳算法的收斂性^[76]。

（2）基于模式理論的收斂性分析。由Holland提出的模式定理^[77]可稱為遺傳算法進化動力學的基本定理，積木塊假設^[77]描述了遺傳算法的重組功能，模式定理和積木塊假設構成了遺傳算法具備發現全局最優解的充分條件，也是分析遺傳算法進化行為的基本理論，統稱為模式理論。孫艷豐對模式定理進行了分析：模式定理揭示經過選擇、交叉和變異后，模式H第k+1代的數目與第k代的數目的關系，并討論了無交叉時的模式定理^[78]。Srinivas討論了自適應交叉和變異概率下模式定理的表示方法^[79]。Bertoni等擴展了模式理論的研究成果^[80]。

最近，一些學者對模式定理的正確性提出了質疑。馬豐寧通過測試黎曼函數和相應的理論分析，指出模式定理推導中的錯誤，并提出了新模式定理^[81]。張鈴等也得出類似結論，并對模式定理進行了修正^[82]。Grefenstette指出模式定理不能保證適應度變換的唯一性^[83]。Muhlenbein指出了模式定理中計算模式適應度時存在的問題^[84]。Radcliffe通過對模式定理的分析，指出遺傳算法并不總比隨機搜索算法好^[85]。Vose也論述了模式定理中存在的一些問題^[86]。

遺傳算法收斂性的研究成果，要么基于群體無窮大的假設，要么基于分析簡單的或特殊的遺傳算法，在實際應用中的可操作性較差。一般遺傳算法的收斂性分析及如何構造一個收斂的遺傳算法，仍是該領域亟待解決的重要理論問題。遺傳算法的其他理論問題還包括^[87]：欺騙問題、維數分析、BGA（breeder genetic algorithm）理論、可分離函數、Walsh函數分析、傅里葉分析和二次動力系統等。

2.1.3.2　遺傳算法的改進

為了維持群體的可進化性并最終搜索到全局最優解，遺傳算法必須采用合適的運算形式（編碼、計算流程、種群規模、種群初始化策略、GA算子和終止條件等），這就是遺傳策略研究與設計的主要內容。

（1）參數設置的改進。參數確定包括靜態方法和動態方法，靜態方法指參數事先就確定好，算法執行過程中不變；動態方法指參數在算法執行過程中根據情況進行動態調整，以適應環境變化。由于參數設置關系到遺傳算法的精度、可靠性和計算時間等諸多因素，因此許多學者通過研究參數設置來提高求解質量和系統性能。孫艷豐證明，當采用自然數編碼時，從理論上可以證明遺傳算法最優群體規模的存在性，并給出相應的計算方法^[88]。Srinivas等提出采用自適應交叉和變異概率來維持群體多樣性，并保證遺傳算法的收斂性^[79]。Fogarty研究了變異概率對整數編碼的影響^[89]。Whitley采用父代個體之間的Hamming距離來設置變異概率^[90]。

（2）編碼方式的改進。目前主要的編碼技術有：一維染色體編碼（包括二進制編碼、實數編碼和格雷編碼等）、多參數映射編碼、可變染色體長度編碼、二倍體（多倍體）編碼和樹形編碼等。Janikow等給出二進制編碼和實數編碼的實驗比較^[71]。孟慶壽提出對稱編碼^[91]，并通過優良型保護、希望型成員移民和部分基因保留等措施，來加快算法的收斂速度。Fogel提出了動態變量編碼，通過對DeJong的5個函數進行測試，發現動態變量編碼比普通二進制編碼的優化效果好很多^[92]。Goldberg等用動態背包問題進行比較研究，實驗表明雙倍體編碼比單倍體編碼的跟蹤能力強^[93]。張曉繢等研究了二進制和十進制編碼在搜索能力和保持群體穩定性上的差異，結果表明二進制編碼比十進制編碼的搜索能力強，但前者不能保持群體穩定性^[94]。Antonisse從理論上證明了Holland在推導最小字符集編碼規則時存在的錯誤，指出大符號集編碼設計可提供更多模式^[95]。

（3）選擇算子的改進。常用的選擇方法有：精華選擇、重組選擇、均分選擇、適應性調整、線性排序、比例選擇和自適應選擇等。Potts等概括了大約20多種選擇方法^[96]。為了防止算法過早收斂，Potts提出微進化結構和人工選擇等來改進遺傳算法。Kuo等采用分裂選擇方法^[97]使新遺傳算法比傳統遺傳算法在優化欺騙函數上具有更好的特性。B?ck在研究各種選擇機制的基礎上提出了擴展選擇和偏置選擇^[98]。

（4）交叉算子的改進。常用的交叉技術有：單點交叉、兩點交叉、均勻交叉、多點交叉、啟發式交叉、順序交叉和混合交叉等。Potts概括大約20多種已有交叉技術^[96]。Qi等對遺傳算法的交叉多樣性進行了分析^[71]，[72]，通過建立相應的數學模型解釋了在多維連續空間和大規模群體中使用均勻交叉算子是如何探索新的解空間的。

（5）變異算子的改進。常用的變異方式有：基本變異算子、逆轉算子和自適應變異算子等。Potts總結了三種新的變異技術：管理變異、變化變異概率和單值運算^[96]。張良杰等人通過引入i位改進子空間的概念，采用模糊推理技術來確定選取變異概率的一般性原則^[99]。Qi等通過連續遺傳算法的理論分析，提出隨時間變化的變異技術^[71]，[72]，即根據群體平均適應性值來確定變異變化率。

（6）遺傳算法的局部改進。由于遺傳算法涉及精度、可靠性、計算時間、探索與開發等諸多問題，通過改進遺傳算法本身在某種程度上可以提高遺傳算法的性能。遺傳算法的局部改進包括^[100]：分層遺傳算法、變區域多層遺傳算法、正交多目標最優化遺傳算法、具有空間平滑技術的遺傳算法、基于災變的多群體遺傳算法、基于共生策略的多模式進化算法和具有年齡結構的遺傳算法等。

（7）混合遺傳算法。混合遺傳算法將遺傳算法與基于領域知識的啟發式搜索技術相結合來求解優化問題^[101-106]。將全局搜索能力強的遺傳算法和局部搜索能力強的啟發式搜索方法相結合的混合遺傳算法能夠產生很好的優化效果^[107-112]。設計混合遺傳算法有三條指導性原則：采用原有算法中的編碼技術、吸收原有算法的優點和改造遺傳算子。混合遺傳算法的框架如圖2.2所示。常見的混合遺傳算法包括^{[113]，[100]}：將模擬退火算法與遺傳算法相結合；在簡單遺傳算法中加入局部搜索機制；用來解決模糊尋優問題的模糊遺傳算法；結合可變多面體法和正交遺傳算法的混合算法；將最速下降法和遺傳算法相結合的混合方法等。

2.1.3.3　遺傳算法的應用

遺傳算法提供了一種求解復雜優化問題的通用框架，它不依賴于問題的具體領域，從而廣泛地應用于多種學科領域^[114-119]。

（1）函數優化。函數優化是遺傳算法的經典應用領域，也是對遺傳算法進行性能評價的常用算例。對于一些非線性、多模型、多目標的函數優化問題，遺傳算法可以方便地得到較好結果。

（2）組合優化。對于組合優化問題，應把主要精力放在尋求滿意解上，遺傳算法是尋求滿意解的最佳工具之一。遺傳算法已在求解旅行商問題、背包問題、裝箱問題、布局優化問題、圖形劃分問題等各種NP-難問題上得到了成功應用^[120-124]。

（3）生產調度。遺傳算法已成為解決復雜調度問題的有效工具，在單件（流水線）生產車間調度、生產規劃和任務分配等方面^[125-130]，遺傳算法都得到了有效的應用。

（4）自動控制。遺傳算法在自動控制領域已得到初步應用。如采用遺傳算法進行航空控制系統的優化、基于遺傳算法的模糊控制器設計、基于遺傳算法的參數辨識、利用遺傳算法進行人工神經網絡的結構設計和權值學習等。

（5）機器人學。遺傳算法已被成功地用于移動機器人路徑規劃、關節機器人運動軌跡規劃、機器人逆運動學求解、細胞機器人的結構優化和行為協調等方面。

（6）圖像處理。遺傳算法可用于圖像處理中的優化計算，目前已在模式識別（包括漢字識別）、圖像恢復、圖像邊緣特征提取等方面得到了廣泛應用。

（7）人工生命。遺傳算法已在人工生命的進化模型、學習模型、行為模型、自組織模型等方面顯示出了初步的應用能力。

（8）遺傳編程。遺傳編程（genetic programming）采用樹型結構來表示計算機程序，運用遺傳算法的思想，通過自動生成計算機程序來解決問題。

（9）機器學習。基于遺傳算法的機器學習，特別是分類器系統，在很多領域中都得到了應用。如采用遺傳算法學習模糊控制規則，可更好地改進模糊系統的性能。

（10）數據挖掘。現有研究表明，遺傳算法是一種非常有效的數據挖掘方法。

2.1.3.4　遺傳算法的發展趨勢

遺傳算法是多學科結合與滲透的產物，已經發展成一種自組織、自適應的綜合技術，廣泛應用在計算機科學、工程技術和社會科學等領域。遺傳算法的發展趨勢可總結為以下幾個方面^[131-133]。

（1）分布并行遺傳算法。對分布并行遺傳算法的研究表明，只要通過保持多個群體和恰當控制群體間的相互作用來模擬并行執行過程，即使不使用并行計算機，也能提高算法的執行效率。

（2）遺傳神經網絡。遺傳算法與神經網絡相結合，已被成功地應用于多個實際的工程領域。在很多現實系統中，信號是模糊的，數據是有噪聲的，一般很難正確給出每個執行的定量評價。采用遺傳算法就能克服這些困難，顯著提高系統性能。

（3）借鑒自然現象提出新的算法模型。從生物進化或自然界的各種現象中獲得新啟發，提出新方法或對現有算法進行改進，如二倍體顯性技術、小生境技術等。

（4）其他發展趨勢^[133]。發展一些啟發式策略對遺傳算法的搜索過程給予指導；補充和擴展遺傳算法與其他算法的混合方法，擴展遺傳算法的功能和應用；加強遺傳算法的應用研究，針對具體問題深入研究遺傳算法都是特別值得提倡的工作。

2.1.4　蟻群算法

蟻群算法是模擬現實世界蟻群覓食行為的一種新型仿生算法，具有本質并行性、協同工作機制、魯棒性和易于與其他啟發式算法相結合等特點。蟻群算法不需要提供任何關于環境的先驗信息，通過蟻群的群體學習能力及正反饋效應來達到全局尋優目的。蟻群算法特別適合于在離散優化問題的方案空間上進行多點非確定性搜索，已成功應用于旅行商問題、二次分配問題等多個離散組合優化問題^[134-138]。蟻群算法的基本運算流程如圖2.3所示。

蟻群算法是基于真實螞蟻的群體合作行為提出的，大部分蟻群算法都包括^[139]：群體中所有個體相互交流的通信機制（信息量跡，pheromone trials）；每個個體所記錄的當前遍歷序列；利用當前信息進行路徑選擇的隨機選擇策略。蟻群算法中的人工螞蟻^[140]與現實世界中的真實螞蟻有以下不同：人工螞蟻生活在離散空間環境下；人工螞蟻具有記憶能力；人工螞蟻具有視覺能力；人工螞蟻更新信息素時不反映真實蟻群的行為；人工螞蟻具有智能性（預測未來和局部優化等）^[141]。

2.1.4.1　螞蟻系統

1991年，Dorigo博士等首次提出螞蟻系統（ant system）^[142]。螞蟻系統有三種基本模型：蟻周模型（ant-cycle system）、蟻密模型（ant-density system）、蟻量模型（ant-quantity system）。在求解旅行商問題（traveling salesman problem，TSP）時，蟻周模型是三種模型中性能最好的，因此主要從蟻周模型的角度來討論螞蟻系統。

螞蟻系統的基本步驟是：

（1）初始化各條邊上的信息素強度及各個螞蟻的禁忌表；

（2）每只螞蟻按照概率規則，在禁忌表的制約下選擇下一個要到達的結點，直到最終形成一條可行路徑；

（3）更新各條邊上的信息素，先進行信息素揮發操作，再根據各螞蟻產生的路徑長度獲取螞蟻所釋放的信息素；

（4）所有螞蟻都完成信息素更新操作后，記錄當前最短路徑，對禁忌表及信息素增加值進行重新計算，并轉到第（2）步。

依次循環下去，直到滿足算法的終止準則為止。

在初始化階段，每條邊上的信息素被初始化為一個較小數值τ₀；每只螞蟻的禁忌表被初始化為該螞蟻所在的結點（禁忌表長度為1）；每只螞蟻在各條邊上釋放信息素的量被初始化為0。在螞蟻系統中，每只螞蟻均按照以下概率

來確定下一步要到達的城市。其中，p_ij（t）表示螞蟻在t時刻由城市i選擇城市j的概率，τ_ij（t）表示在t時刻邊（i，j）上的信息素，α是信息素的權重，η_ij表示邊（i，j）的啟發因子（在TSP問題中常被設置為邊（i，j）距離的倒數），β是啟發因子的權重，A是不在螞蟻禁忌表中的城市集合。當所有螞蟻都找到一條可行路徑后，螞蟻系統就按照以下方式

開始執行信息素的更新。其中，ρ表示信息素的揮發因子，Δτ_ij（t，t+1）表示所有螞蟻在邊（i，j）上所釋放的信息素總和。螞蟻k在t到t+1時間內在邊（i，j）上所釋放的信息素為

這里，Q表示一個常量，L_k表示螞蟻k構建的可行路徑Tour_k的長度，（i，j）∈Tour_k表示螞蟻k構建的可行路徑Tour_k中包含邊（i，j）。

2.1.4.2　蟻群系統

1996年，Dorigo博士在螞蟻系統的基礎上提出了蟻群系統（ant colony system，ACS）^[140]。蟻群系統的基本思想是：將m只螞蟻按規則放置于n個節點，每只螞蟻通過狀態轉移規則創建一條可行路徑；每只螞蟻通過局部更新規則對自己所建路徑上的邊進行信息素局部更新；當所有螞蟻都完成路徑構造之后，再對最佳路徑上的邊進行信息素全局更新。蟻群系統較螞蟻系統的改進之處主要體現在以下三個方面。

（1）蟻群系統全局更新僅針對當前最好路徑上的邊

其中，Δτ_G為當前最好路徑Tour_B長度的倒數，（i，j）∈Tour_B表示邊（i，j）包含于當前最好路徑Tour_B中。

（2）蟻群系統在螞蟻創建路徑時所使用的狀態轉移規則不同于螞蟻系統

S表示按照公式（2.1）從集合A中隨機選取下一步要到達的城市，q∈（0，1）是隨機數，q₀∈（0，1）是常量，它在算法的求解效率與運行效率之間起著平衡作用。

（3）蟻群系統在對信息素進行更新時，除了進行全局更新外，還要進行信息素的局部更新。信息素局部更新規則如下：

這里，Δτ_L通常被設置為τ₀。

2.1.4.3　最大-最小螞蟻系統

1997年，Stutzle等人提出了最大-最小螞蟻系統（max-min ant system，MMAS）^[143]。MMAS的基本思路：將各邊上信息素的濃度控制在[τ_min，τ_max]范圍之內，這里τ_min和τ_max是算法中信息素所能取到的下限和上限。在初始化時，將各邊信息素的數值初始化為τ_max；最大-最小螞蟻系統會增強當前循環中最優路徑上的信息素強度，其他邊上的信息素由于揮發作用而進一步減少；這樣就加劇了各邊信息素的差異，提高了算法的運行效率。與螞蟻系統相比，MMAS的改進之處主要體現在以下方面：

（1）MMAS只對當前循環中所產生的最短路徑進行信息素的更新操作，這樣做使得算法在最短路徑附近搜索，從而逐步找出全局最優解。

（2）為了避免算法過快地收斂于局部最優解，MMAS將各邊上的信息素濃度控制在比較固定的范圍之內，這是該算法的主要特點。

（3）MMAS將各邊上的信息素初始化為上限τ_max。根據實驗結果^[143]，將各邊上的信息素濃度初始化為τ_max可以提高算法的效率。

（4）為了擴展蟻群的搜索空間，MMAS還引入了平滑機制（smoothing）。平滑機制就是盡可能縮小各邊上的信息素差異。平滑機制可表述為

這里，δ∈[0，1]表示平滑強度，和τ_ij（t）分別表示平滑之后與平滑之前邊（i，j）上的信息素數值。

2.1.4.4　蟻群優化算法

1999年，Dorigo博士等提出了蟻群優化算法（ant colony optimization，ACO）^[144]，該算法給出了蟻群算法的一個標準框架。ACO對蟻群算法的實現進行了高度概括，將蟻群算法概括為螞蟻行為、信息素揮發和守護操作（daemon actions）。

螞蟻行為可描述為一群螞蟻同時異步地在問題空間上移動。移動依賴于啟發信息和信息素所決定的選擇策略及問題本身的限制條件。螞蟻在構造解的過程中或完成解的構造后，會對當前構造的解進行評估，然后依據解的好壞來釋放一定數量的信息素到當前構造的路徑上。這些信息素將進一步指導后續螞蟻的路徑構造。

信息素揮發可描述為圖中各邊上的信息素隨著時間而逐漸消失。信息素揮發可避免算法過快地收斂于局部最優解，同時也有利于螞蟻對新空間進行搜索，進而找出更好的解。

守護操作可描述為實現螞蟻不能完成的集中控制任務。如局部搜索策略、僅對最短路徑再次進行信息素的全局更新等。

2.1.4.5　蟻群算法的改進

蟻群算法的改進可概括為4個方面^[145]：信息素更新方式的改進、路徑選擇策略的改進、與其他算法的結合和多重蟻群算法。

（1）信息素更新方式的改進。采用錦標賽競爭策略更新信息素可取得很好效果^[146]；通過精英策略來改進信息素更新方式，能極大地提高算法性能^[147]；基于排序思想按比例在經過的路徑上釋放信息素，能顯著地提高解的精度^[148]。一些學者對蟻群算法的信息素更新方式進行了大幅修改，取得了非常滿意的結果^{[140]，[143]}。

（2）路徑選擇策略的改進。主要體現在：通過減小算法陷入局部最優解的概率來提高算法的優化性能，如采用偽隨機比例規則（pseudo-random proportional rule）來構建路徑^{[140]，[149]}。在偽隨機比例規則的作用下，使用狀態轉移規則來指導螞蟻的尋優過程，可較快地找到可接受的解；以一定概率接受當前系統的累積狀態（選擇當前轉移概率最大的城市），可有效地提高算法的收斂速度。

（3）與其他算法的結合。利用蟻群算法良好的耦合能力，將蟻群算法和遺傳算法結合起來，采用遺傳算法生成信息素初始分布，利用蟻群算法來獲得精確解，能夠實現兩種算法的優勢互補^[150-153]。吳慶洪等提出了具有變異特征的蟻群算法^[154]，采用逆轉變異方式，隨機進行變異，增大進化時所需的信息素，克服了蟻群算法收斂較慢的問題。陳燁基于交叉算子提出了改進算法^[155]，進一步提高了算法性能。Dorigo等通過研究多個螞蟻的協同效應，提出了蟻群算法與Q學習機制結合而成的Ant-Q算法^[156]，有效地解決了進化速度慢及陷入局部最優解的問題。Gambardella等提出了ACS-3-Opt算法^[157]，將蟻群算法與3-Opt局部搜索算法進行耦合，有效地提高了蟻群算法的求解精度和計算效率。蟻群算法的另一種改進是將蟻群算法和神經網絡相結合^[158]，使得神經網絡的廣泛映射能力和蟻群算法的快速全局收斂性能相互補充，呈現出單一算法所不具有的特性。

（4）多重蟻群算法。隨著蟻群算法的不斷改進、逐步發展完善及工程應用對算法要求的不斷提高，研究重點必然轉向使用幾個蟻群協同解決問題的多重蟻群算法。傳統蟻群算法中只有一個蟻群，沒有充分挖掘蟻群算法的本質并行性及分布式計算等優良特性；多重蟻群算法通過使用正、負兩種信息素效應，利用蟻群群體層的交互作用，使得蟻群能夠更好地交換問題解決過程的規劃信息，同時保持蟻群在搜索過程中的多樣性。

2.1.4.6　蟻群算法的應用

蟻群算法已在許多組合優化問題中獲得了成功應用^{[151]，[152]，[159-166]}，這些問題可分為兩類：靜態組合優化問題，參數特性在求解過程中不發生變化，如TSP（traveling salesman problem），QAP（quadratic assignment problem），SOP（sequential ordering problem），VRP（vehicle routing problem），JSSP（job-shop scheduling problem）等；動態組合優化問題，參數特性在求解過程中發生變化，如網絡路由問題等。

（1）在TSP中的應用。TSP是蟻群算法應用最早、最多的一類組合優化問題。Colorni等首先將蟻群算法應用于TSP中^[142]。Gambardella等基于蟻群算法和Q學習算法^[157]設計了Ant-Q算法^[156]，并用來求解TSP問題。Dorigo等對Ant-Q算法進行了簡化，并采用2-Opt和3-Opt局部搜索算法對螞蟻構造的解進行改進，在求解TSP問題時得到了很好的求解效果^[140]。Bullnheimer等基于排序思想提出了一種求解TSP問題的改進蟻群算法（AS）^[148]。Stutzle等基于蟻群算法設計了求解TSP問題的MMAS算法，并采用2-Opt等局部搜索算法來改進由螞蟻構造的解^[168]。陳燁將交叉算子引入蟻群算法中，并采用改進算法來求解TSP問題^[155]。吳慶洪等在蟻群算法中引入變異機制，并采用2-Opt來改進由螞蟻構造的解，使得該方法在求解TSP問題時具有較快的收斂速度^[154]。吳斌等將相遇算法與分段算法相結合，提出一種求解TSP問題的改進蟻群算法^[169]。王穎等通過自適應調整蟻群算法中的相關參數，在保證收斂速度的前提下極大地提高了求解質量^[170]。馬良等將ACS應用推廣到多目標TSP問題中^[171]。

（2）在QAP中的應用。QAP是蟻群算法在組合優化領域的另一個典型應用。鑒于QAP和TSP的相似性，很多學者將求解TSP的蟻群算法進行調整和改進后再來求解QAP問題。Maniezzo等提出了一種求解QAP問題的改進蟻群算法，采用禁忌搜索方法對螞蟻構造的解進行局部優化^[172]，針對QAP設計了Ants-QAP算法^[173]。Stutzle等研究了MMAS在QAP中的應用^[168]。Tailland等針對QAP設計了FANT算法，算法中僅使用一只螞蟻，在算法執行過程中對信息素更新的學習步長作自適應調整^[174]。Gambardella等針對QAP設計了HAS-QAP算法，該方法沒有將信息素濃度用在解的構造過程中，而是用在了對解的改進過程中^[175]。Talbi等設計的Ant-Tabu算法與HAS-QAP具有相似結構^[176]，但采用并行機制實現。

（3）在網絡路由問題中的應用。蟻群算法在動態組合優化問題中的應用主要集中在網絡通信方面，特別是網絡路由選擇問題上。網絡路由選擇問題可簡單描述為在一個代表通信網絡的全連接圖中求解任何兩個節點的最短路徑問題。雖然在靜態環境下該問題可通過多項式算法求解^[177]，但在節點間流量隨時間變化情況下，該問題的求解變得非常困難。Caro等針對網絡路由問題設計了算法Ant-Net^[178]，取得了比較滿意的結果。

2.1.4.7　蟻群算法的發展趨勢

蟻群算法在解決離散優化問題上的卓越性能，以及在解決連續優化問題上的初露鋒芒，吸引了眾多研究者的關注，并提出了許多有效的改進方法，使得蟻群算法發展很快，但還有很多方面有待完善，需要進行深入研究^{[145]，[159]}。

（1）加強蟻群算法各種改進方法的綜合研究。現有研究工作主要針對蟻群算法的不同部分進行修改，蟻群算法各個參數的相互作用及最優配置、各種方法的綜合使用及各種改進方法的相互作用等都是未來研究的重點。

（2）加強蟻群算法與其他算法的耦合。蟻群算法具有很強的耦合性，易與其他進化算法或局部搜索算法相結合，將蟻群算法與神經網絡、遺傳算法、模擬退火算法等相融合，必將成為今后蟻群算法新的研究熱點。

（3）加強蟻群算法與應用的結合。盡管蟻群算法在眾多領域得到了推廣，但大多數研究僅局限于仿真試驗，應當充分挖掘蟻群算法在實際應用中的潛力，對現有應用領域進行深化研究，進一步擴大其應用范圍。

（4）采用Multi-Agent技術來改進蟻群算法。在蟻群系統中，可賦予人工螞蟻更多的智能性和學習能力。可考慮對螞蟻進行分工，不同螞蟻具有不同能力并完成不同任務。在具體實現方面，可將每只螞蟻看作一個Agent，然后再設法尋求所有螞蟻之間的彼此協調，最終共同實現系統整體目標。如何設計程序框架使得基于Multi-Agent的蟻群框架具有廣泛的適用性也需要深入研究。

2.1.5　學習型智能優化的基本框架

在現有智能優化方法中，還沒有大量直接地挖掘、存儲和應用待求解問題的相關領域知識，因此還不能更加有效地得到優化問題的最優解。在現實生活中，實際系統的規模越來越大，約束條件越來越多，系統結構越來越復雜，多準則、非線性、不可微、不確定已成為這些復雜系統的基本特征。探尋適合大規模計算且具有智能特征的問題求解方法已成為相關學科的研究熱點和重要研究方向。

本書認為在求解復雜優化問題時，可從優化過程中直接挖掘一些待求解問題的相關知識，然后應用知識來指導后續優化過程。本書更多地關注一些顯性知識，即能明確表達的知識。本書中用到的顯性知識，都可采用計算機語言來表示和存儲；其他模型也可通過給定方式對這些知識進行更新和應用。

本書把學習型智能優化方法定義為：將智能優化模型和知識模型有效結合起來的混合智能優化方法。在學習型智能優化方法中，智能優化模型按照“鄰域搜索”策略對優化問題的可行空間進行搜索；知識模型從前期的優化過程中挖掘出有用知識，然后采用知識來指導智能優化方法的后續優化過程。將智能優化模型和知識模型有效地結合起來，極大地提高了學習型智能優化方法的優化績效。

鑒于此，本書提出一類學習型智能優化方法，該方法采用知識模型和智能優化模型相結合的集成建模思路，以智能優化模型為基礎，同時突出知識模型的作用，將智能優化模型和知識模型進行優化組合、優勢互補，以提高學習型智能優化方法的效率。學習型智能優化方法的基本框架如圖2.4所示。

在求解一些實際復雜工程問題（如軍事、交通、工程和網絡等領域的優化問題）時，應考慮將人機交互功能引入學習型智能優化方法中。由于本書內容所限，暫時還沒有考慮把人機互動（人在回路）功能加入到學習型智能優化方法中。在后續著作中，可考慮將人機交互功能引入學習型智能優化方法。

2.1.6　學習型智能優化的運行機制

學習型智能優化方法的運行機制如圖2.5所示。圖2.5的頂部刻畫了智能優化方法的優化進程。智能優化方法按照“鄰域搜索”機制對優化問題的可行空間進行搜索；經過逐步迭代，智能優化方法最終收斂到最適應環境的個體。圖2.5的底部刻畫了知識模型的作用。知識模型從前期優化過程中挖掘或抽取有用知識，然后應用知識來指導后續優化過程。

在學習型智能優化方法的運行過程中，由于初始階段可供學習的樣本太少，挖掘出來的知識可信度不高，對后續優化過程的指導作用也不明顯；隨著迭代的逐步推進，挖掘出來的知識可信度越來越高，對后續優化過程的指導作用也越來越明顯。與智能優化方法相比，在知識模型的輔助下，學習型智能優化方法要么能更加快速地收斂到一個滿意解；要么能收斂于一個質量更高的滿意解。

在學習型智能優化方法的優化過程中，知識模型和智能優化模型都起著非常重要的作用。智能優化模型是基礎，按照“鄰域搜索”機制對優化問題的可行空間進行搜索；知識模型是核心，從前期優化過程中挖掘有用知識，應用知識來指導后續優化過程。將智能優化模型和知識模型有效地集成起來，極大地提高了學習型智能優化方法的優化績效。