摘要： 智能優化算法又稱現代啟發式算法，是一種具有全局優化性能、通用性強且適合于并行處理的算法。這種算法一般具有嚴密的理論依據，而不是單純憑借專家經驗，理論上可以在一定的時間內找到最優解或...

智能優化算法又稱現代啟發式算法，是一種具有全局優化性能、通用性強且適合于并行處理的算法。這種算法一般具有嚴密的理論依據，而不是單純憑借專家經驗，理論上可以在一定的時間內找到最優解或近似最優解。常用的智能優化算法有：遺傳算法 、模擬退火算法、禁忌搜索算法、粒子群算法、蟻群算法。

本文主要為大家帶來遺傳算法和蟻群算法的詳細解讀。

1. 遺傳算法

遺傳算法（Genetic algorithm, GA），模擬生物在自然環境中遺傳和進化的自適應（對遺傳參數的自適應調整）全局優化（隨機變異不斷尋找全局最優解）算法，基本思想是“優勝劣汰”，是應用最廣泛和效果最顯著的智能優化算法。

1.1 編碼方法

算法模型通過對個體（individual，也即solution）進行二進制編碼（01編碼）、自然數編碼、實數編碼和樹型編碼。在對個體進行適應度計算時需要進行解碼，實現問題的解空間與算法搜索空間的相互轉換。

1.2 適應度函數

每個個體都有一個適應度函數（Fitness），對這個個體的優劣進行定量評價，適應度函數是算法執行“適者生存、優勝劣汰”的依據。適應度函數需要根據目標函數進行設置，令g(x)g(x)表示目標函數，令G(x)G(x)表示適應度函數，從目標函數g(x)g(x)映射到適應度函數G(x)G(x)的過程稱為標定。

對于最大值優化問題，可直接將g(x)g(x)設定為適應度函數G(x)G(x)，即G(x)=g(x)G(x)=g(x)；對于最小值優化問題，G(x)=-\min g(x)G(x)=?ming(x)；在遺傳算法規定中，適應度函數為正值，但上述二式無法保證，因此需要加上最小值或者最大值以及分段函數。

1.3 選擇操作

選擇（Selection）是從當前群體中選擇適應度函數值大的個體，這些優良個體有可能作為父代繁殖下一代，個體適應度函數越大，被選擇作為父代的概率越大（有可能！）

選擇算法有很多，最基本的是輪盤賭算法：

P_i =\frac{F_i}{\sum_{i=1}^{N}F_i}Pi=∑i=1NFiFi

其中，P_iPi表示個體被選擇的概率；F_iFi表示個體的適應度函數值；NN表示種群規模。

根據選擇概率P_iPi將圓盤形賭輪分為NN份，第ii個扇形的中心角為2\pi P_i2πPi。隨機產生0到1之間服從均勻分布的數rr，落在第ii個扇形的累計概率為Q_i = \sum_{j=1}^i P_jQi=∑j=1iPj，則選擇個體ii，重復NN次，就可以選擇NN個個體。

1.4 交叉操作

兩個個體通過交叉（Crossover）互換染色體部分基因而重組產生新的個體，也就是產生新解。交叉前需要進行隨機配對。

一般情況下，對二進制編碼的個體采用點交叉的方法，也就是在兩個配對字符串隨機選擇一個或者多個交叉點，互換部分子串從而產生新的字符串

兩個個體是否進行交叉操作由交叉概率決定，較大的交叉概率可以使遺傳算法產生更多新解，保持群體多樣性，并能防止算法過早成熟，但是交叉概率過大會使算法過多搜索不必要的解區域，消耗過多的計算時間，一般取值在0.9左右。

1.5 變異操作

生物進化中，某些染色體可能會發生基因突變（Mutation），從而產生新的染色體，這也是產生新解的另外一種重要方式。交叉操作相當于進行全局探索，變異操作相當于進行局部開發，這也是智能優化算法必備的兩種搜索能力。

個體能否變異取決于變異概率，過低會使得部分有用基因無法進入染色體，不能提高解的質量；過大會使子代喪失父代優良基因，導致算法失去從過去搜索經驗的學習能力，一般情況下，變異概率取值為0.005左右。

值得注意的是，Rudolph通過馬爾科夫鏈相關理論證明僅采用選擇、交叉和變異三個操作的遺傳算法不能收斂到全局最優解，而采用精英保留策略的遺傳算法是全局收斂的。

算法的整體流程如下圖所示：

1.6 算法分析

一個好的智能算法，關鍵在于全局探索和局部開發能力的平衡。全局探索的目的是對解空間進行更全面的探索，局部開發主要目的是對已知區域進行更精細的搜索，希望獲得質量更好的新解。

遺傳算法可以通過設置選擇壓力實現全局探索和局部開發的平衡。在算法運行初始階段，設置較小的選擇壓力可以使算法具有較好的全局探索能力，進行廣域搜索；算法運行后期，設置較大的選擇壓力可以使算法進行比較精細的局部搜索。

選擇壓力的設置可以從適應度函數標定和選擇策略。

適應度函數標定，在算法早期，應當縮小個體適應度差距，減少淘汰率；算法運行最后階段，擴大個體適應度差距，保證算法能在高適應度個體對應解區域進行集中搜索，加快算法收斂速度。常用方法有：

• 線性尺度變換 H= aF bH=aF b

• \sigmaσ截斷法 H= F (\hat F - c\sigma)H=F (F^?cσ)

• 冪律尺度變換 H= F^\alphaH=Fα

選擇策略，低選擇壓力可選擇多種類型的個體，加強對未知解區域的搜索，避免算法陷入局部極值，但算法優化速度會變得緩慢；高選擇壓力可選擇優良個體，加快優化速度但群體多樣性會下降，減少搜索到全局最優值的概率。除了輪盤賭算法外，選擇策略還有：

• 分級選擇法

• 錦標賽選擇法

• Boltzmann選擇法

2. 蟻群算法

2.1 蟻群優化算法