蟻群算法基于網(wǎng)格化分策略的連續(xù)域改進分析

摘 要：空間函數(shù)優(yōu)化是蟻群算法中常遇到的問題，針對這一問題基于網(wǎng)格劃分策略提出了一種改進方式。該算法通過利用特殊的信息更新策略，使得信息素在更新時無需使用具體的目標(biāo)函數(shù)值，在這種狀態(tài)下目標(biāo)函數(shù)差異化就不會令結(jié)果出現(xiàn)問題，既不會帶來不利影響。并且在計算中網(wǎng)格點可以直接將信息素作為轉(zhuǎn)移概率使用。

關(guān)鍵詞：蟻群算法；網(wǎng)格法；信息素

引言

近年來，面向連續(xù)空間優(yōu)化問題求解的蟻群優(yōu)化（ACO）算法吸引了廣大研究者的研究興趣，在算法模型及應(yīng)用方面，有了長遠(yuǎn)的進展。連續(xù)蟻群算法模型最早由Bilchev等人提出，它先使用GA對參數(shù)空間進行全局搜索以得到一個較好解，然后利用蟻群算法對該解進行局部優(yōu)化。然而，在目前連續(xù)域蟻群算法模型中，大多要根據(jù)被優(yōu)化系統(tǒng)的目標(biāo)函數(shù)來進行信息素的更新和轉(zhuǎn)移概率的計算。當(dāng)解對應(yīng)的目標(biāo)函數(shù)值之間數(shù)量相差大時，顯然會使某些局優(yōu)路徑上的信息素累積過快；而當(dāng)局部最優(yōu)解與全局最優(yōu)解的目標(biāo)函數(shù)值相差不大時，又會造成對應(yīng)路徑上的信息素難以區(qū)分，從而使算法陷入局部最優(yōu)的可能性極大增加。本文借鑒Kong模型的信息素更新方法，并使用網(wǎng)格劃分策略，提出一種面向連續(xù)域優(yōu)化問題求解的連續(xù)域改進蟻群算法（IACA）。

1 設(shè)計分析

1.1 IACA模型

依照算法模型的改進可以將連續(xù)域改進法進行以下描述：首先將連續(xù)優(yōu)化問題解x的分量取值范圍予以確定，即xit≤x≤xiu（i=1，2，……，n）。并將變量平均分為N分。那么在n維空間中變回形成構(gòu)成網(wǎng)格的（N+1）n個點，從而對參數(shù)空間完成具體的劃分，具體如圖1所示。

圖1 參數(shù)空間網(wǎng)格劃分示意圖

在IACA中，問題的求解需要通過m只螞蟻相互協(xié)作予以完成，每只螞蟻都會選擇一個點從網(wǎng)格的第一列爬行到n列構(gòu)建解。當(dāng)螞蟻選擇第i列點時，需要根據(jù)N+1點上對信息素分布狀態(tài)隨機予以選擇。

在計算中，選擇概率的確定需要以算法的運行時刻作為基礎(chǔ)，螞蟻在構(gòu)建解的過程中，一個時刻為一個完整解的構(gòu)建。如果螞蟻選擇了第i列中的某一點，那么在網(wǎng)格的劃分中可以將點記為（ij），即可以將xij表述為xil+jxhi，并可以將其信息素初始值設(shè)置為1.0/N+1。

為了保證IACA信息素更新中信息素滿足要求，所有的信息素相加結(jié)果為1，則該路徑上單信息素便等于選擇概率。

在蟻群算法中，整個研究結(jié)構(gòu)中最為重要的策略便是在信息素更新中使用全局歷史最優(yōu)解，在IACA中該方式也是主要的使用方法。當(dāng)m螞蟻將m個解構(gòu)建出后，便可以將全局歷史最優(yōu)解確定出來，繼而對每一列進行信息素的更新。

？子ij（t+m）=（1-？籽）？子ij（t）+？駐？子ij（t+m）

？駐？子ij（t+m）=？籽？撞ij∈x？棕x

式中i是揮發(fā)系數(shù)，式1表示為信息素的揮發(fā)，式2則是信息素的強化，且該強化是針對最優(yōu)解路徑上的信息素強化過程中，除此之外，其他路徑上的信息素僅做揮發(fā)操作。即非最優(yōu)解路徑中的信息在進行更新的過程中，式1第二項取值為0。另外，為了保證更新以后每一個網(wǎng)格中的信息素之和最終為1，那么式中的？棕x取值為1。

若算法循環(huán)一個周期后，找出每一列矩陣中信息量最大的一點，并截取其對應(yīng)的行數(shù)，將變量取值范圍縮小，對解的第i個分量取值范圍進行有效更新。

待變量取值范圍更新后，將信息素進行重新初始化后依照縮小后的區(qū)域再次進行搜索，若同條件不滿足停止條件，則繼續(xù)循環(huán)計算更新，直到滿足條件為止。

1.2 IACA信息素特征

通過上述信息素更新規(guī)則可以看出，通過IACA能夠?qū)⑺新窂街械男畔⑺刈鳛檫x擇概率。

1.3 IACA算法步驟

該計算系統(tǒng)的算法步驟如下：

（1）對算法參數(shù)進行設(shè)定，其中需要劃分參數(shù)空間，將初始信息素均勻放置，進行循環(huán)計算。

（2）對每條路徑中的信息素水平進行評估，并依照實際狀態(tài)，螞蟻依照圖1所示構(gòu)建解，并且會構(gòu)建出m個無重復(fù)的解，同時將目標(biāo)函數(shù)值計算出來，確定當(dāng)代歷史最優(yōu)解。繼而從第二代開始，將最優(yōu)解同全局最優(yōu)解進行比較，取最優(yōu)值。

（3）如果計算滿足終止條件則將最優(yōu)解輸出，計算接觸，若不滿足終止條件則跳入下一步。

（4）依照上述公式，對信息素進行重復(fù)更新。Nc=Nc+1。

（5）如果Nc同其最大值相比較小，那么則跳回（2）步驟重新計算，反之則找出信息量最大的點所 的行，對其分量取值范圍進行縮小，同時對信息素進行初始化，循環(huán)次數(shù)為0，轉(zhuǎn)至（2）步驟。

上述步驟分析中不難看出，IACA算法在時間上具有復(fù)雜性，該時間復(fù)雜度高主要是因為，首先，該算法會涉及到目標(biāo)函數(shù)值計算結(jié)果中其解的構(gòu)造，其次，在計算中需要對信息素進行不斷的更新，最后，還需要對解的空間進行不斷的劃分。1代表了算法的時間復(fù)雜度，具體計算出來可以表述為O（s·m·（N+1）·n·Ncmax），式中s是結(jié)果達到計算所需要的精度所需要的計算周期數(shù)。

2 結(jié)束語

文章主要是針對蟻群算法進行改進，主要依照一種網(wǎng)格劃分策略進行算法的優(yōu)化，這是一種面向連續(xù)優(yōu)化問題繼而求解的方式，即IACA。通過IACA算法可以針對信息素進行一種特殊的更新，從而使用轉(zhuǎn)移概率直接表述路徑點信息素，如此一來，在對信息素進行更新的過程中就不會使用到具體的目標(biāo)函數(shù)值，以此降低了函數(shù)值在計算過程中其差異性給計算帶來的不良影響。通過連續(xù)函數(shù)的優(yōu)化，最終得到最優(yōu)解，從而確定解。同傳統(tǒng)的計算方式相比，IACA算法能夠得到相同或者更優(yōu)解，且效率更高。從而可以證明，在發(fā)現(xiàn)最優(yōu)解上，IACA算法具有卓越的能力，其應(yīng)用前景相比較其他方式更加廣闊。

參考文獻

[1]葛燕，逢海平，孟友新，等.求解連續(xù)空間優(yōu)化問題的Powell蟻群算法[J].哈爾濱工業(yè)大學(xué)學(xué)報，2009，41（12）：239-242.

[2]康卓，李艷，劉博，等.求解函數(shù)優(yōu)化問題的兩種異步并行算法[J].武漢大學(xué)學(xué)報：理學(xué)版，2002，48（1）：33-36.