摘要： 智能優(yōu)化算法又稱現(xiàn)代啟發(fā)式算法，是一種具有全局優(yōu)化性能、通用性強(qiáng)且適合于并行處理的算法。這種算法一般具有嚴(yán)密的理論依據(jù)，而不是單純憑借專家經(jīng)驗，理論上可以在一定的時間內(nèi)找到最優(yōu)解或...

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

本文主要為大家?guī)磉z傳算法和蟻群算法的詳細(xì)解讀。

1. 遺傳算法

遺傳算法（Genetic algorithm, GA），模擬生物在自然環(huán)境中遺傳和進(jìn)化的自適應(yīng)（對遺傳參數(shù)的自適應(yīng)調(diào)整）全局優(yōu)化（隨機(jī)變異不斷尋找全局最優(yōu)解）算法，基本思想是“優(yōu)勝劣汰”，是應(yīng)用最廣泛和效果最顯著的智能優(yōu)化算法。

1.1 編碼方法

算法模型通過對個體（individual，也即solution）進(jìn)行二進(jìn)制編碼（01編碼）、自然數(shù)編碼、實數(shù)編碼和樹型編碼。在對個體進(jìn)行適應(yīng)度計算時需要進(jìn)行解碼，實現(xiàn)問題的解空間與算法搜索空間的相互轉(zhuǎn)換。

1.2 適應(yīng)度函數(shù)

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

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

1.3 選擇操作

選擇（Selection）是從當(dāng)前群體中選擇適應(yīng)度函數(shù)值大的個體，這些優(yōu)良個體有可能作為父代繁殖下一代，個體適應(yīng)度函數(shù)越大，被選擇作為父代的概率越大（有可能！）

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

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

其中，P_iPi表示個體被選擇的概率；F_iFi表示個體的適應(yīng)度函數(shù)值；NN表示種群規(guī)模。

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

1.4 交叉操作

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

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

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

1.5 變異操作

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

個體能否變異取決于變異概率，過低會使得部分有用基因無法進(jìn)入染色體，不能提高解的質(zhì)量；過大會使子代喪失父代優(yōu)良基因，導(dǎo)致算法失去從過去搜索經(jīng)驗的學(xué)習(xí)能力，一般情況下，變異概率取值為0.005左右。

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

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

1.6 算法分析

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

遺傳算法可以通過設(shè)置選擇壓力實現(xiàn)全局探索和局部開發(fā)的平衡。在算法運(yùn)行初始階段，設(shè)置較小的選擇壓力可以使算法具有較好的全局探索能力，進(jìn)行廣域搜索；算法運(yùn)行后期，設(shè)置較大的選擇壓力可以使算法進(jìn)行比較精細(xì)的局部搜索。

選擇壓力的設(shè)置可以從適應(yīng)度函數(shù)標(biāo)定和選擇策略。

適應(yīng)度函數(shù)標(biāo)定，在算法早期，應(yīng)當(dāng)縮小個體適應(yīng)度差距，減少淘汰率；算法運(yùn)行最后階段，擴(kuò)大個體適應(yīng)度差距，保證算法能在高適應(yīng)度個體對應(yīng)解區(qū)域進(jìn)行集中搜索，加快算法收斂速度。常用方法有：

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

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

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

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

• 分級選擇法

• 錦標(biāo)賽選擇法

• Boltzmann選擇法

2. 蟻群算法

2.1 蟻群優(yōu)化算法