2.3　學習型智能優化算法的框架與流程

本書針對連續優化問題設計并實現了一種求解函數優化問題的學習型遺傳算法；針對離散優化問題設計并實現了求解3類典型離散優化問題的5種學習型智能優化方法；針對實際工程問題設計并實現了求解體系仿真優化問題的學習型遺傳算法、求解衛星地面站系統任務調度的學習型蟻群算法和求解多星任務規劃問題的學習型蟻群算法；這些方法稍加修改就可以推廣到其他復雜優化問題的求解中。

• 求解函數優化問題的學習型遺傳算法。將5種交叉算子、8種變異算子和5種災變（局部優化）算子有效地集成到學習型遺傳算法中，根據算子績效知識為每次操作智能地選擇交叉、變異或災變算子。學習型遺傳算法從演化過程中挖掘算子績效知識，在優化過程中基于算子績效知識盡可能使用那些優化性能高的算子，從而極大地提高了優化性能。采用21個標準測試函數進行實驗，結果表明學習型遺傳算法在優化性能方面優于近期公開發表的3種典型方法。
• 求解非對稱旅行商問題的學習型遺傳算法。在參數績效知識的指導下，采用動態參數決策模型為下次迭代隨機選擇參數組合；使用多次操作取最優策略執行交叉和變異操作；采用種群替換和局部搜索來改進當前種群中的部分個體。在遺傳算法、動態參數決策模型和局部優化的共同作用下，學習型遺傳算法的優化績效得到了極大提高。采用非對稱旅行商問題的16個標準實例進行實驗，結果表明學習型遺傳算法在優化性能方面優于近期公開發表的4種典型方法。
• 求解雙層CARP優化問題的學習型遺傳算法。為了提高初始種群質量，采用兩種擴展啟發式方法來輔助生成初始種群；為了提高遺傳操作效率，采用多種不同算子來實現選擇、交叉和變異操作，同時基于算子績效知識為每次選擇、交叉和變異選擇操作算子；為了進一步提高遺傳操作效率，基于構件順序知識為每次交叉和變異選擇合適的斷點位置；為了保持種群多樣性，采用局部替換程序不斷地向當前種群中注入新的優秀個體。采用雙層CARP優化問題的87個測試實例進行實驗，結果表明學習型遺傳算法在優化性能方面優于其他兩種改進方法。
• 求解雙層CARP優化問題的學習型蟻群算法。為了消除蟻群算法對參數的敏感性，采用動態參數決策模型為每次迭代動態地選擇參數組合；為了提高蟻群算法的效率，基于構件聚類知識和構件順序知識來構建可行解；為了進一步提高蟻群算法的效率，采用2-Opt方法對每次迭代中的最優解進行局部優化。采用雙層CARP優化問題的87個測試實例進行實驗，結果表明學習型蟻群算法在優化性能方面優于其他3種改進方法。
• 求解柔性作業車間調度問題的學習型蟻群算法。在參數績效知識的指導下，采用動態參數決策模型為下次迭代隨機選擇參數組合；從優化過程中不斷抽取構件知識，采用構件知識來指導人工螞蟻的后續尋優過程；采用調度改進操作來改進當前方案集中的部分個體。在蟻群算法、動態參數決策模型、構件知識模型和局部優化模型的共同作用下，學習型蟻群算法的優化績效得到了極大提高。采用柔性作業車間調度問題的15個標準實例進行實驗，結果表明學習型蟻群算法在優化性能方面優于近期公開發表的7種典型方法。
• 求解柔性車間作業調度問題的學習型協同進化算法。各個種群采用不同的進化方法和參數設置來推進各自的演化進程；種群之間通過相互的資源競爭和信息共享，共同推動著整體算法的進化進程。采用柔性作業車間調度問題的15個標準實例進行實驗，結果表明學習型協同進化算法在優化性能方面優于近期公開發表的7種典型方法。
• 求解體系仿真優化問題的學習型遺傳算法。采用量化正交遺傳算法在整個可行域內快速地搜索出一些較優方案；應用靈敏度分析方法對已評估方案進行分析，得到待研究體系各輸入變量的靈敏度知識；應用變量靈敏度知識來指導量化正交遺傳算法繼續在可行域內搜索最優解。數據實例結果表明，本方法是可行的、正確的和有效的。
• 求解衛星地面站系統任務調度的學習型蟻群算法。將蟻群優化和導向局部搜索有效地結合在一起，極大地提高了學習型蟻群算法的優化績效。計算結果表明，學習型蟻群算法能有效地求解衛星地面站系統任務調度問題。
• 求解多星任務規劃問題的學習型蟻群算法。在參數績效知識的指導下，采用動態參數決策模型為下次迭代隨機選擇參數組合；從優化過程中不斷抽取構件知識，采用構件知識來指導人工螞蟻的后續尋優過程。采用多星任務規劃問題的21個測試實例進行實驗，結果表明學習型蟻群算法在優化性能方面優于其他兩種方法。

2.3.1　求解函數優化問題的學習型遺傳算法框架與流程

函數優化問題是遺傳算法的經典應用領域，也是對遺傳算法進行性能評價的常用算例。遺傳算法是求解函數優化問題的一種非常有力的工具，大量理論分析和實際應用都表明遺傳算法能有效地求解函數優化問題。遺傳算法從點的群體開始搜索，對初始點集要求不高；遺傳算法不是直接在參變量集上實施，而是利用參變量集的某種編碼；遺傳算法利用個體適應度值信息，無需導數或其他輔助信息，在搜索過程中不容易陷入局部最優；即使適應度函數是不連續的、非規則的或有噪聲的，遺傳算法也能以較大概率找到全局最優解。實踐表明，遺傳算法求解函數優化問題的計算效率比較高、適用范圍相當廣。與傳統優化方法相比，遺傳算法具有簡單通用、魯棒性強、適于并行處理以及高效、實用等優點。

雖然遺傳算法對函數優化問題的求解非常有效，但在應用遺傳算法求解函數優化問題時，以下問題還有待進一步研究：發展一些啟發式策略，引入領域知識，對搜索過程給予指導或引導；最大限度地減少參數環境對遺傳算法性能和結果質量的影響；研究遺傳算法的選擇策略，使之具有更廣泛的適用性，避免早熟；進一步研究遺傳算法的并行性和并行計算問題，以提高計算效益；研究其他一些性能更好的編碼方式；研究遺傳算法中的智能化問題，如智能選擇操作算子、自主挖掘領域知識和智能應用領域知識來提高優化性能等。

遺傳算法經過選擇、交叉和變異的迭代搜索過程，最終收斂于最優狀態。選擇操作使適應度值高的個體有較高的復制概率，能加快遺傳算法的收斂速度；交叉算子通過基因重組產生新的更優個體，尋優搜索過程主要通過它來實現；變異算子通過某些基因位的變異而產生一些有效的基因信息。傳統遺傳算法的交叉、變異算子只是采用某種特定操作，來完成遺傳算法中各代染色體的演化過程。采用一種特定交叉、變異算子的遺傳算法對于解決一些問題非常有效，而對解決另外一些問題就無能為力了。

下面通過具體實驗來說明各種算子在求解不同優化問題時的性能差異。本部分實驗中用到的兩個測試函數分別為

函數F₁（X）和函數F₂（X）的優化目標都為最小化目標函數值；函數F₁（X）的可行空間為[–10，10]³，函數F₂（X）的可行空間為[–5.12，5.12]²⁵；在函數F₂（X）中，A表示一個比較大的正數，M表示一正整數。本部分的實驗結果如圖2.6～圖2.8所示。假設采用某算子執行特定操作的總次數為T_total，采用該算子執行特定操作的成功次數為T_succ，則采用該算子執行特定操作的成功率可表示為。

圖2.6展示了采用不同交叉算子求解函數F₁（X）和F₂（X）的成功率。本書共采用5種交叉算子（具體信息參見第3.2節）來求解函數F₁（X）和F₂（X）的最優解。從圖2.6中可以看出，第一種交叉算子（CR₁）、第三種交叉算子（CR₃）和第四種交叉算子（CR₄）在求解函數F₁（X）時成功率比較高，即這三種交叉算子非常適于求解函數F₁（X）的最優解；第一種交叉算子（CR₁）和第五種交叉算子（CR₅）在求解函數F₂（X）時成功率比較高，即這兩種交叉算子非常適于求解函數F₂（X）的最優解。

圖2.7展示了采用不同變異算子求解函數F₁（X）和F₂（X）的成功率。本書共采用8種變異算子（具體信息參見第3.2節）來求解函數F₁（X）和F₂（X）的最優解。從圖2.7中可以看出，第一種變異算子（MU₁）和第二種變異算子（MU₂）在求解函數F₁（X）時成功率比較高，即這兩種變異算子非常適于求解函數F₁（X）的最優解；第一種變異算子（MU₁）、第二種變異算子（MU₂）和第四種變異算子（MU₄）在求解函數F₂（X）時成功率比較高，即這三種變異算子非常適于求解函數F₂（X）的最優解。

圖2.8展示了采用不同災變（局部搜索）算子求解函數F₁（X）和F₂（X）的成功率。本書共采用5種災變算子（具體信息參見3.2節）來求解函數F₁（X）和F₂（X）的最優解。從圖2.8中可以看出，第四種災變算子（ZB₄）和第五種災變算子（ZB₅）在求解函數F₁（X）時成功率比較高，即這兩種災變算子非常適于求解函數F₁（X）的最優解；第一種災變算子（ZB₁）、第四種災變算子（ZB₄）和第五種災變算子（ZB₅）在求解函數F₂（X）時成功率比較高，即這三種災變算子非常適于求解函數F₂（X）的最優解。

根據以上分析，在設計求解函數優化問題的遺傳算法時，一方面要保證盡可能地使用成功率較高的操作算子來執行遺傳操作，另一方面也要保證操作算子的隨機性和多樣性。因此可考慮以下兩個問題：盡可能將多種操作算子集成到遺傳算法中；基于操作算子的成功率來動態地選擇需要使用的操作算子。

鑒于此，提出了一種求解函數優化問題的學習型遺傳算法^[181]，其特點是融合了多種交叉、變異和災變算子。求解函數優化問題的學習型遺傳算法^[181]的優化框架如圖2.9所示，該算法根據算子績效知識智能地選擇交叉、變異和災變算子，在不影響搜索過程隨機性的前提下收斂于全局最優解。學習型遺傳算法可表示為

學習型遺傳算法（KGA）中的五元體可解釋如下：

• SE表示選擇操作；
• CR表示交叉操作，CR={CR₁，CR₂，…，CR₅}；
• MU表示變異操作，MU={MU₁，MU₂，…，MU₈}；
• ZB表示災變操作，ZB={ZB₁，ZB₂，…，ZB₅}；
• FV表示適應度函數評價。

2.3.2　求解非對稱旅行商問題的學習型遺傳算法框架與流程

近年來，遺傳算法從理論到實踐都取得了許多重要成果。遺傳算法具有良好的全局搜索能力，是解決各種優化問題的最有效方法。遺傳算法在旅行商問題上的應用研究，對于構造合適的遺傳算法框架、建立有效的遺傳操作及有效地解決旅行商問題等方面具有重要意義。

遺傳算法具有良好的全局搜索能力，但通常需要較長時間才能收斂到全局最優解^{[182]，[183]}。局部搜索技術在可行空間的某個小區域內能快速地找到局部最優解，但全局搜索能力較弱。同時，一些優化策略（optimization strategy）對于求解復雜組合優化問題非常有效^[184-186]。鑒于此，可考慮將局部搜索技術和優化策略有效地融入遺傳算法，以最大限度地提高優化績效。

為了提高遺傳算法的優化績效，部分學者嘗試將一些優化策略融入遺傳算法中，取得了比較滿意的實驗結果^[187-189]。大部分優化策略中包含了實際問題的領域知識，可有效地輔助遺傳算法來提高優化績效。從這種意義上來講，優化策略可看作是一種知識模型。將知識模型（如優化策略）和智能搜索模型（如遺傳算法）結合起來能有效地搜索到優化問題的（準）最優解。將智能優化模型和知識模型有效結合起來的混合優化方法，在求解組合優化問題中的效果已被眾多學者多次以實際問題加以驗證^[190-192]。

求解非對稱旅行商問題的學習型遺傳算法^[193]的優化框架如圖2.10所示。在該框架中，智能優化模型為遺傳算法，知識模型為局部優化操作和動態參數決策模型。根據各種渠道的反饋信息，學習型遺傳算法采用交叉和變異機制不斷地調整非對稱旅行商問題的可行方案。局部優化操作從學習型遺傳算法的演化過程中抽取一些較優個體，采用局部優化操作改進后再將改進個體插入到當前種群中。動態參數決策模型從學習型遺傳算法的演化過程中抽取一些參數知識，然后應用參數知識來指導改進遺傳算法的后續演化過程。學習型遺傳算法^[193]采用知識模型和智能優化模型相結合的集成建模思路，以智能優化模型為基礎，同時突出知識模型的作用，將智能優化模型和知識模型進行優化組合、優勢互補，以提高學習型智能優化方法的效率。

求解非對稱旅行商問題的學習型遺傳算法^[193]的優化流程如圖2.11所示。在每次迭代之前，學習型遺傳算法根據參數組合的優化績效，采用動態參數決策模型為本次迭代隨機選擇參數組合。與標準遺傳算法相似，學習型遺傳算法依然包括種群初始化、選擇、交叉和變異4個基本操作；與標準遺傳算法不同的是，學習型遺傳算法在交叉和變異操作中均采用了多次操作取最優的策略。當完成一次迭代后，學習型遺傳算法采用種群替換操作和3種局部搜索操作來改進當前種群中部分個體的質量。在遺傳算法、動態參數決策模型和局部優化操作的共同作用下，學習型遺傳算法在求解非對稱旅行商問題時優于其他幾種方法。

2.3.3　求解雙層CARP優化問題的學習型遺傳算法框架與流程

在求解雙層CARP優化問題的學習型遺傳算法^[194]中，為了提高初始種群質量，采用兩種擴展啟發式方法來輔助生成初始種群；為了提高遺傳操作效率，采用多種算子來實現學習型遺傳算法的選擇、交叉和變異操作，同時基于算子績效知識為每次選擇、交叉和變異操作選擇操作算子；為了進一步提高遺傳操作效率，基于構件順序知識為每次交叉和變異操作選擇合適的斷點位置；為了保持種群多樣性，采用局部替換程序不斷地向當前種群中注入新的優秀個體。

求解雙層CARP優化問題的學習型遺傳算法^[194]的優化框架如圖2.12所示。學習型遺傳算法采用知識模型和智能優化模型相結合的集成建模思路，以智能優化模型（遺傳算法）為基礎，同時突出知識模型（構件順序知識的抽取和應用、算子知識的抽取和應用、經典啟發式方法的有效融入）的作用，將智能優化模型和知識模型進行優化組合、優勢互補，以提高學習型智能優化方法的效率。

求解雙層CARP優化問題的學習型遺傳算法^[194]的優化流程如圖2.13所示。與標準遺傳算法相比，學習型遺傳算法具有以下幾個顯著特點。

• 構件順序知識的抽取和應用。為了防止當前個體中的優良子序列在交叉或變異操作中被破壞，使用構件順序知識為交叉或變異操作選擇斷點位置。如果某弧段序列在已獲得準最優解中出現的次數非常多，則應以較小概率在該弧段序列之間選擇斷點位置；反之，則應以較大概率在該弧段序列之間選擇斷點位置。
• 算子知識的抽取和應用。基于算子績效知識為下一步操作動態地選擇操作算子，既保證了盡可能使用成功率較高的操作算子來執行遺傳操作，又保證了操作算子的隨機性和多樣性。
• 經典啟發式方法的有效融入。為了最大限度地提高優化績效，將3種經典啟發式方法有效地融入學習型遺傳算法中。采用啟發式方法ERPS（extended random path-scanning）和ERUH（extended random ulusoy's heuristic）來生成一些初始種群，可極大地提高初始種群的質量；采用啟發式方法2-Opt來執行變異操作，可極大地提高變異操作的成功率。

2.3.4　求解雙層CARP優化問題的學習型蟻群算法框架與流程

將基因型知識表述、知識學習方法和智能優化方法有效地集成起來，可在求解質量和計算時間兩個方面極大地提高優化績效^[18]。將知識模型和智能優化模型有效地結合起來求解組合優化問題，已不再單純停留在理論概念的層面上，而且在實踐中被證明是非常有效的^[190-192]。

求解雙層CARP優化問題的學習型蟻群算法的優化框架如圖2.14所示。學習型蟻群算法從功能上分為兩個模塊：智能優化模型（蟻群算法）和知識模型。智能優化模型負責從廣闊的可行解空間中搜索并識別出一些準最優解；知識模型從已獲得準最優解中學習可用知識，然后采用知識來指導后續優化過程。學習型蟻群算法的優化流程如圖2.15所示，其優化過程可概括如下。

• 宏觀配置優化。本階段將確定倉庫的最優位置及數目。具體求解過程參見5.2.2節。

• 相關知識的初始化。在本階段中，記錄構件順序知識、構件聚類知識和算子知識的矩陣被初始化。
• 動態參數調整。根據參數組合的優化績效為下次迭代隨機選擇一個參數組合。
• 可行方案的構造。在已有知識的指導下采用蟻群優化機制構建一組可行方案。
• 可行方案的改進。采用2-Opt方法對每次迭代中的最優解進行局部優化。
• 相關知識的更新。采用已獲得的準最優解來更新構件順序知識、構件聚類知識和算子知識。

在求解雙層CARP優化問題的學習型蟻群算法^[195]中，為了消除蟻群算法對參數的敏感性，采用動態參數決策模型為每次迭代動態選擇參數組合；為了提高蟻群優化效率，基于構件聚類知識和構件順序知識來構建可行解；為了進一步提高蟻群優化效率，采用2-Opt方法對每次迭代中的最優解進行局部優化。

2.3.5　求解柔性作業車間調度問題的學習型蟻群算法框架與流程

求解柔性作業車間調度問題時，一方面需要考慮機器分配問題，另一方面還要考慮工序調度問題；機器分配問題和工序調度問題的同時考慮，無疑增加了柔性作業車間調度問題的求解難度。同時，在柔性作業車間調度問題中，滿足各種約束條件的可行方案數量巨大；很難對這些可行方案進行逐個驗證，以獲得待求解問題的最優調度；眾多可行方案也使得柔性作業車間調度問題成為一類非常具有挑戰性的問題。

最新研究表明：將知識表達（knowledge representation）、學習方式（learning methodology）和智能優化方法（intelligent optimization approach）有效結合起來，可在求解質量（solution quality）和計算時間（computational time）上獲得極大改進^[18]。可將知識表達和學習方式統一到知識模型中，即知識的表達、獲取、存儲和應用等操作都由知識模型來完成。將知識模型和智能優化模型結合起來，是求解柔性作業車間調度問題的一種有效方法。

求解柔性作業車間調度問題的學習型蟻群算法^[196]的優化框架如圖2.16所示。在該框架中，智能優化模型為蟻群算法，知識模型為局部優化模型、構件知識（構件指派機器知識和構件指派順序知識）模型和動態參數決策模型。根據各種渠道的反饋信息，學習型蟻群算法通過工序指派、工序排序和調度改進等操作不斷地產生一些新的可行方案。局部優化模型從優化過程中抽取一些較優個體，采用調度改進操作將它們改進后再插入到可行方案集中。構件知識模型從優化過程中抽取構件指派機器知識和構件指派順序知識，然后應用構件知識來指導人工螞蟻構建可行方案。動態參數決策模型從優化過程中抽取一些參數知識，然后應用參數知識來指導蟻群算法的后續優化過程。求解柔性作業車間調度問題的學習型蟻群算法^[196]采用知識模型和智能優化模型相結合的集成建模思路，以智能優化模型為基礎，同時突出知識模型的作用，將智能優化模型和知識模型進行優化組合、優勢互補，以提高學習型智能優化方法的效率。

求解柔性作業車間調度問題的學習型蟻群算法^[196]的優化流程如圖2.17所示。在每次迭代之前，學習型蟻群算法根據參數組合的優化績效，采用動態參數模型為本次迭代隨機選擇參數組合。學習型蟻群算法通過構件知識模型從優化過程中不斷地抽取構件知識，然后采用構件知識來指導人工螞蟻在后續優化過程中構建可行方案。當完成一次迭代后，學習型蟻群算法采用調度改進操作來改進當前可行方案集中的部分個體。在蟻群算法、動態參數決策模型、構件知識模型和局部優化模型的共同作用下，學習型蟻群算法在求解柔性作業車間調度問題時優于其他幾種方法。

2.3.6　求解柔性作業車間調度問題的學習型協同進化算法框架與流程

達爾文的進化理論過分強調生存斗爭（繁殖過剩所引起的種內斗爭），忽略了生物種群之間其他方面的種種聯系。大部分現有進化模型都存在著這樣的不足：未能很好地反映出整個生物系統復雜的自適應進化過程。生物系統的演化可看作是多個子系統局部相互作用的協同進化過程，生物界就是一種大規模協同動力學系統。在自然界中，不同地域的生物有著不同的特點和進化程度，它們都從自然界中爭取資源為己所用；另外，這些生物之間又通過信息交換取長補短、共同進步。學習型協同進化算法就是借鑒自然界中的這一現象設計出來的。整個算法由計算環境中的多個普通種群和一個優良種群構成，各個普通種群進行競爭，從計算環境中得到計算資源；一旦某個種群獲得計算資源，它便進行一次自己的進化進程。各個普通種群將進化得到的優良個體貢獻出來，組成優良種群；普通種群可從優良種群中獲取優良個體，以改善本種群的品質。在學習型協同進化算法中，各個種群均采用不同的優化方法和參數設置來推進各自的進化進程；同時，這些種群又通過相互的資源競爭和信息共享，共同推動著整體算法的演化進程。

求解柔性作業車間調度問題的學習型協同進化算法的基本框架如圖2.18所示。在圖2.18中，A類遺傳算法、B類遺傳算法、C類遺傳算法和D類遺傳算法分別代表4種采用不同參數組合進行演化的遺傳算法；A類蟻群算法、B類蟻群算法、C類蟻群算法和D類蟻群算法分別代表4種采用不同參數組合進行優化的蟻群算法。在學習型協同進化算法中，主要通過各種不同的遺傳算法和蟻群算法來完成各個普通種群的演化。各種遺傳算法（蟻群算法）的不同，可體現在進化機制、優化算子和控制參數等方面的差異。下面將從4個方面來重點說明學習型協同進化算法和傳統進化算法的區別。

（1）機制設計。學習型協同進化算法使用多個種群同時推進演化進程，可有效地保證演化過程中種群的多樣性，能對求解空間進行更有效的搜索，更傾向于收斂到全局最優解。學習型協同進化算法借鑒生態學中的種群協同理論，將種群間自動調節和自適應調整的思想充分應用于算法設計中。根據生態學對種群相互關系的劃分，一般有以下關系：捕食者與被捕食者、寄生物與寄主、競爭和互惠共生，這些關系可概括為兩種協同進化模型，即競爭協同模型和合作協同模型。最新研究成果表明：采用生態模型和協同進化結構來擴展進化算法是一種非常有效的方法。協同進化可分為競爭協同進化和合作協同進化，前者通過演化使得個體更有競爭力，后者通過演化尋找最佳個體使得系統構造得更好。許多研究表明：競爭協同導致“軍備競賽”，多個種群通過交互機制有效地提高了系統性能。鑒于此，基于競爭協同模型提出了一種學習型協同進化算法。

（2）問題表示。在進化算法中，一般采用二進制編碼或實數編碼來表示種群中的個體。種群結構是進化算法演化的基礎，種群規模直接影響著進化算法的優化績效。為了獲得較好的演化性能，一般需要采用較大的種群規模。隨著種群規模的增大，計算量按多項式增長，而算法性能卻并不同比例增長。Ficici等認為：種群結構在協同進化算法中起著非常重要的作用^[197]。Kim等提出基于主種群和寄生種群的協同進化算法，分別采用了鄰近演化、聯賽競爭和局部杰出者等組合策略^[198]。曹先彬等構造了基于生態種群競爭模型的新協同進化模式^[199]。為了提高學習型協同進化算法的優化性能，本書采用多種群表示方法來維持演化過程中種群的多樣性。

（3）演化操作。在Potter的協同進化模型中，多個遺傳算法程序并行運行；通過組合多個程序所獲得的局部解而構成協同進化算法的全局解^[200]。He等提出了設計混合變異策略的博弈論方法，實驗表明該方法是有效的^[201]。Ficici等在協同進化算法中，利用演化博弈論來研究選擇方法的動態均衡^[202]。本書通過集成現有算法中的幾種優勢操作算子，利用混合策略思想結合具體問題設計學習型協同進化算法，來提高優化性能。

（4）算法實現。1997年，Potter給出了一個通用的合作協同進化算法框架；以一般進化算法框架為基礎，將種群分為若干子種群，進一步考慮子種群之間基于合作關系的協同進化^[203]。在Potter提出的合作協同進化框架的基礎上，本書構建了學習型協同進化算法的基本框架。學習型協同進化算法采用多種群協同優化方法來不斷演化當前種群。多種群優化方法通過各個種群之間的相互競爭和良種共享來提高算法的優化效率。

求解柔性作業車間調度問題的學習型協同進化算法^[204]的優化框架如圖2.19所示。在學習型協同進化算法中，用到了三類知識：精英個體知識，將普通種群中的一些精英個體共享到優良種群中，通過良種更新和良種遷移策略來實現普通種群和優良種群之間的交互；構件知識，從優良種群中抽取構件指派機器知識和構件指派順序知識，應用構件指派機器知識和構件指派順序知識來指導人工螞蟻構建可行方案；參數知識，采用不同優化方法和參數配置來實現各個普通種群的演化，以較高概率給競爭力指數高的種群賦予計算資源。學習型協同進化算法^[204]采用知識模型和智能優化模型相結合的集成建模思路，以智能優化模型為基礎，同時突出知識模型的作用，將智能優化模型和知識模型進行優化組合、優勢互補，以提高學習型智能優化方法的效率。

2.3.7　求解體系仿真優化問題的學習型遺傳算法框架與流程

在使用計算機仿真技術研究體系的過程中，仿真模型僅是對問題的直觀描述，仿真運行只能提供一定條件下的可行方案，并不能給出體系的最優解。需要將優化技術嵌入到仿真過程中，以便在仿真環境下使輸出響應不斷地得到改進，從而實現體系性能的優化。仿真優化就是指非枚舉地從可能值中找到最佳輸入變量值，使得輸出結果為滿意解或最優解的過程。仿真優化研究基于仿真的目標優化問題，即基于模型仿真給出的輸入輸出關系通過優化算法得到最佳輸入量。仿真優化的目標是在仿真試驗中獲得最多信息的同時，耗費資源最少，使用戶更加容易地進行決策。仿真優化的難點如下：存在不確定因素，單次仿真僅給出對應某輸入的一次性能估計，通常存在誤差；系統仿真過程較費時，且缺少與優化模塊的合理接口，使得整個優化過程很慢；輸入變量空間大，且連續量、離散量和邏輯量共存，優化涉及多目標，并存在多極小，以致難以高效地實現全局優化。鑒于仿真優化的工程背景和上述難點，它一直是不同領域理論和工程人員共同關注的重要課題。

仿真優化效率在很大程度上依賴于優化過程中所采用的搜索技術。現有搜索算法在一定程度上把待求解問題的領域知識隱含地加入算法，并沒有大量直接地挖掘、存儲和應用待求解問題的相關領域知識，還不能最有效地得到優化問題滿意解。鑒于此，提出了一種求解體系仿真優化問題的學習型遺傳算法^[205]。該方法試圖通過較少次數的體系仿真，使得待研究體系的輸出結果為滿意解或最優解，學習型遺傳算法的優化框架如圖2.20所示。

在求解體系仿真優化問題的學習型遺傳算法^[205]中，主要用到了兩類知識：精英個體知識，從當前種群中選取若干精英個體，然后采用靈敏度分析方法從這些精英個體中挖掘各變量對輸出結果的敏感程度；構件知識，從已獲得的精英個體中挖掘變量靈敏度知識，基于變量靈敏度知識來指導學習型遺傳算法的后續演化。求解體系仿真優化問題的學習型遺傳算法^[205]采用知識模型和智能優化模型相結合的集成建模思路，以智能優化模型為基礎，同時突出知識模型的作用，將智能優化模型和知識模型進行優化組合、優勢互補，以提高學習型智能優化方法的效率。

在求解體系仿真優化問題的學習型遺傳算法^[205]中，首先采用量化正交遺傳算法在整個可行域內快速地搜索出一些較優解（方案）；然后應用靈敏度分析方法對已評估方案進行分析，得到待研究體系各輸入變量的靈敏度知識；接下來應用變量靈敏度知識來指導量化正交遺傳算法繼續在可行域內搜索最優解；通過這樣的多次迭代，在經過較少次數的體系仿真后，得到待研究體系的最優解。

2.3.8　求解衛星地面站系統任務調度的學習型蟻群算法框架與流程

衛星地面站系統任務調度問題是一個基于約束的資源優化問題，即在給定時間內向需要執行的任務分配地面站及執行時間。該問題的優化目標可描述為：在給定時間內完成最多的任務或最大化完成任務的權重值之和（考慮任務權重時）。該問題的難點在于：資源（地面站）相對于某個特定活動（任務）來講，只有一個或幾個可用時間窗口（衛星和地面站之間滿足任務要求的時間區段）；其調度過程既包括了資源指派問題，又包含了時間窗口的分配問題。

各國學者通常采用人工智能方法來求解衛星地面站系統任務調度問題，如貪婪算法^[206]、動態規劃方法^[207]、啟發式搜索方法^[208]和約束滿足方法^[209]等。如何更加快速有效地求解該問題，依然是擺在人們面前的一個嚴峻挑戰。本書提出了一種有效求解該問題的基于蟻群優化（ant colony optimization）^[210]和導向局部搜索（guided local search）^[211]的學習型蟻群算法。

求解衛星地面站系統任務調度的學習型蟻群算法^[212]的優化框架如圖2.21所示。該算法主要用到了精英個體知識，即從蟻群算法的優化過程中選取精英個體，然后采用導向局部搜索對該精英個體進行改進，最后采用改進的精英個體來更新蟻群算法中的信息素水平。求解衛星地面站系統任務調度的學習型蟻群算法^[212]采用知識模型和智能優化模型相結合的集成建模思路，以智能優化模型為基礎，同時突出知識模型的作用，將智能優化模型和知識模型進行優化組合、優勢互補，以提高學習型智能優化方法的效率。

在蟻群算法中，人工螞蟻按照狀態轉移規則逐步構造可行解，將一些隨機性引入優化結果中。因此，通過蟻群優化算法很難快速得到優化問題的全局最優解。如果要快速得到優化問題的全局最優解，則需要采用局部搜索技術來輔助蟻群優化過程。本書將蟻群算法和局部搜索方法有效集成起來，提出了求解衛星地面站系統任務調度的學習型蟻群算法^[212]，學習型蟻群算法的優化流程如圖2.22所示。

2.3.9　求解多星任務規劃問題的學習型蟻群算法框架與流程

成像衛星是利用星載遙感器從太空中獲取地面圖像信息的對地觀測衛星，具有覆蓋范圍廣、運行時間長、不受國界和空域限制、無須考慮人員安全等獨特優勢。成像衛星主要分為光學成像衛星和雷達（微波）成像衛星兩大類，光學成像衛星采用可見光、紅外、多光譜相機成像，而雷達成像衛星采用SAR遙感器進行成像。可見光成像衛星具有空間分辨率高等優點，但不能全天候、全天時工作；雷達成像衛星不受白天、黑夜及云霧的影響，具有一定的穿透能力。目前，成像衛星在災害防治、環境保護、城市規劃及農業、氣象等許多領域都發揮了重要作用，也得到了世界各國的高度重視。

在成像衛星技術發展之初，由于衛星載荷能力有限，用戶任務也相對較少，任務的成像時間和成像角度都相對固定，衛星管理控制比較簡單，任務規劃問題也不突出。隨著成像衛星技術的發展和地面影像數據需求的增加，衛星開始需要調整遙感設備的側視角度選擇地面目標進行成像，在安排成像過程中必須考慮多種成像約束以保證衛星安全可靠的運行和成像計劃的順利實施。成像衛星高速運行于近地軌道，對地面實施成像受到衛星同目標的可見時間窗限制；衛星成像設備在一定時間內姿態調整的能力有限，在成像任務之間進行動作轉換需要滿足多種約束條件。一般而言，不能對一次任務規劃時間范圍內所有的任務請求進行成像，衛星每次執行的任務是任務數據集合的一個子集，不能滿足用戶提出的所有任務請求。

為了緩解這種供求矛盾，越來越多的成像衛星出現在空間中執行對地觀測的任務。但是盡管在軌運行的衛星數量不斷增加，相對于迅速增長的影像數據需求，有限的成像衛星資源仍然顯得異常寶貴。為了充分利用成像衛星資源，需要針對用戶成像需求，對多顆成像衛星進行統一管理，均衡考慮各種因素，傳統的手工或簡單推理計算已不能滿足衛星日常管理和指揮控制的需求，必須借助于先進的優化方法和工具才能較好管理和分配衛星資源，以最大化滿足用戶日益增長的成像需求。

求解多星任務規劃問題時，需要解決以下兩個問題：一是衛星資源分配問題，即從多顆衛星的多個遙感器資源中指派一個遙感器去響應用戶的成像需求；二是觀測任務合成問題，在給定時段安排到某遙感器的觀測任務可能有多個，需要采用任務合成手段來確定該遙感器在給定時段去觀測哪些目標。衛星資源分配問題和觀測任務合成問題的同時考慮，無疑增加了多星任務規劃問題的求解難度。同時，在多星任務規劃問題中，滿足各種約束條件的可行方案數量巨大，很難對這些可行方案進行逐個驗證，以獲得待求解問題的最優規劃方案；眾多可行方案也使得多星任務規劃問題成為一類非常具有挑戰性的問題。

求解多星任務規劃問題的學習型蟻群算法的優化框架如圖2.23所示。在該框架中，智能優化模型為蟻群算法，知識模型為構件知識模型和動態參數決策模型。根據各種渠道的反饋信息，學習型蟻群算法通過任務指派、任務合成和調度改進等操作不斷地產生一些新的可行方案。構件知識模型從優化過程中抽取構件指派機器知識和構件聚類知識，然后應用構件知識來指導人工螞蟻構建可行方案。動態參數決策模型從優化過程中抽取一些參數知識，然后應用參數知識來指導蟻群算法的后續優化過程。求解多星任務規劃問題的學習型蟻群算法采用知識模型和智能優化模型相結合的集成建模思路，以智能優化模型為基礎，同時突出知識模型的作用，將智能優化模型和知識模型進行優化組合、優勢互補，以提高學習型智能優化方法的效率。

求解多星任務規劃問題的學習型蟻群算法的優化流程如圖2.24所示。在每次迭代之前，學習型蟻群算法根據參數組合的優化績效，采用動態參數模型為本次迭代隨機選擇參數組合。學習型蟻群算法通過構件知識模型從優化過程中不斷地抽取構件知識，然后采用構件知識來指導人工螞蟻在后續優化過程中構建可行方案。當完成一次迭代后，學習型蟻群算法采用鄰域調整操作來改進當前可行方案集中的部分個體。在蟻群算法、動態參數決策模型和構件知識模型的共同作用下，學習型蟻群算法在求解多星任務規劃問題時優于其他兩種方法。