周海燕

摘 要：蟻群算法具有分布式并行全局搜索能力，通過信息素的積累和更新收斂于最優(yōu)路徑上，但初期信息素匱乏，求解速度慢。針對此問題，本文提出了一種先用基因表達(dá)式編程生成信息素分布，再利用蟻群算法求優(yōu)化解的新的混合算法。并通過求解復(fù)雜TSP問題的仿真數(shù)據(jù)實驗驗證了這種基于基因表達(dá)式編程的混合蟻群算法的高效性。

關(guān)鍵詞：蟻群算法；基因表達(dá)式編程；GEP

Hybrid ant colony algorithm based on gene expression programming

Zhou haiyan

（Shool of Computer and Information Engineering，Guangxi Teachers Education University，Nanning 530023，China）

Abstract：Ant colony algorithm has capability of distributed parallel global search ，converges to the optimal path by accumulating and updating the pheromone，but lack of initial pheromone，slow convergence speed.To solve this problem，This paper presents a new hybrid algorithm which generate pheromone distribution by gene expression programming first，then take advantage of the ant colony algorithms to find optimal solutions.By solving complex TSP problem of simulation data experiments ，it proved the the efficiency of the hybrid ant colony algorithm based on gene expression programming.

Key words：Ant colony algorithm；gene expression programming；GEP

葡萄牙進化生物學(xué)家Ferreira通過借鑒生物遺傳的基因表達(dá)規(guī)律，將遺傳算法GA（Genetic Algorithm ）和遺傳編程GP（Genetic Programming）的優(yōu)點融合在其中，經(jīng)過五年時間的研究，在2000年提出了進化計算家族中的革命性的新成員基因表達(dá)式編程GEP（gene expression programming）。

基因表達(dá)式編程GEP是借鑒生物界的自然選擇和遺傳機制，在GA和GP的基礎(chǔ)上發(fā)展起來的全新的隨機搜索和優(yōu)化算法。它雖然具有跟傳統(tǒng)GA和GP相似的計算機理，但是在個體的編碼方法和結(jié)果的表現(xiàn)上有著明顯的區(qū)別。在GEP中，計算機程序被編碼成固定長度的線性符號串（染色體），然后在進行個體適應(yīng)度計算時，被表示成不同形狀和大小的表達(dá)樹，從而解決問題。這種把基因型（染色體）和表現(xiàn)型（表達(dá)式樹）既分離又互相轉(zhuǎn)化的結(jié)合，使得GEP克服了GA損失功能復(fù)雜性的可能性和GP難以再產(chǎn)生新的變化的可能性，提高了解決問題的能力和效率。Ferreira指出基因表達(dá)式編程的效率比傳統(tǒng)的遺傳算法和遺傳編程高出100～60000倍，實現(xiàn)了又一次跨學(xué)科的革新。

蟻群算法是通過信息素的累積和更新而收斂于最優(yōu)路徑，具有分布、并行、全局收斂能力。但初期信息素匱乏、導(dǎo)致算法速度慢，為了克服蟻群算法的缺陷。為此首先利用基因表達(dá)式編程的隨機搜索、快速性、全局收斂性產(chǎn)生有關(guān)問題的初始信息素分布。然后，充分利用蟻群的并行性、正反饋機制以及求解效率高等特征。這樣融合后的算法，在時間效率和求解效率都比較好的啟發(fā)式算法。

1 基因表達(dá)式編程簡介

1.1 GEP算法工作原理

跟所有的演化算法一樣，GEP算法的基本步驟也是從隨機產(chǎn)生的一定數(shù)量的染色體個體（初始種群）開始；然后對這些染色體進行表達(dá)，依據(jù)一個適應(yīng)度樣本集（問題的輸入）計算出每個個體的適應(yīng)度；最后個體按照適應(yīng)度值被選擇，進行遺傳操作，產(chǎn)生具有新特性的后代。該過程一直重復(fù)若干代，直到發(fā)現(xiàn)一個最優(yōu)解。

GEP的核心技術(shù)就是將變異過程和評估過程完全分開。它的變異過程使用定長的線性符號串，而評估過程采用表達(dá)式樹ET（Expression Tree），兩者之間可以通過規(guī)則進行相互轉(zhuǎn)化。對每個具體問題來說，算法執(zhí)行之前必須確定產(chǎn)生染色體的符號，即選擇適合問題解的函數(shù)集和終點集；確定基因的結(jié)構(gòu)及基因的頭長，每個染色體中的基因數(shù)和各基因的連接運算符號；最后還要選擇一個適應(yīng)度函數(shù)，確定遺傳控制參數(shù)。

1.2 GEP的基因結(jié)構(gòu)

GEP遺傳操作的基本單位是染色體，染色體由一個或多個基因構(gòu)成?；蛴删€性定長的字符串組成。GEP的基因型個體由定長的頭部和尾部組成，頭部元素∈{函數(shù)集F}∪{終結(jié)符集T}，尾部元素∈{終結(jié)符集T}（其中函數(shù)集F由求解問題需要的所有函數(shù)運算符組成，終止符集T由描述問題的解的已知符號變量或常數(shù)組成），并且頭部長度h和尾部長度t須滿足以下關(guān)系：

其中nmax為函數(shù)集F的最大操作數(shù)目，在個體表現(xiàn)型中表現(xiàn)為樹型結(jié)構(gòu)中節(jié)點的最大分支數(shù)，這一設(shè)計使得基于基因型個體的遺傳操作都具有很好的合法性。GEP的個體表現(xiàn)型被稱為ET樹。ET樹是通過順序掃描基因型個體的字符，按照層次順序構(gòu)成。例如，若定義函數(shù)集F={*，/，+，-，Q}（依次為乘除加減和開方運算），終止符集T={c，d，e，f}，則nmax=2，取頭部長h=5由式（1）得到尾部長t=6假定有基因型個體：Q/+-cfed，它可以轉(zhuǎn)化為如圖1所示的ET樹：

1.3 GEP算法基本步驟

⑴輸入相關(guān)參數(shù)，創(chuàng)建初始化群體；

⑵計算每個個體的適應(yīng)度函數(shù)，若不符合結(jié)束條件，繼續(xù)下一步，否則結(jié)束；

⑶保留最好個體；

⑷選擇操作；

⑸變異；

⑹插串操作（IS插串RIS插串Gene插串）；

⑺重組（1-點重組2-點重組多基因重組）；

⑻若達(dá)到設(shè)定最大進化代數(shù)或計算精度，則進化結(jié)束，否則轉(zhuǎn)到步驟2）。

2 基于基因表達(dá)式編程的混合蟻群算法

2.1 基本思想

蟻群算法是群集智能算法的一種，它屬于自然計算中的一類，模擬的是生物系統(tǒng)——社會系統(tǒng)，即利用群體與環(huán)境以及個體之間的互動行為來搜尋最優(yōu)解。GEP算法則屬于演化計算一個重要分支，它模擬基因進化過程，利用種群進化來搜尋最優(yōu)解。首先利用GEP算法的隨機搜索、快速性、全局收斂性在大范圍內(nèi)尋找一組粗略解，然后以這組粗略解為蟻群算法的初始路徑，利用螞蟻算法的并行性、正反饋機制以及求解效率高等特性求解出最優(yōu)解。

2.2 基于GEP算法的混合蟻群算法原理及流程

GEP算法一開始，先隨機的產(chǎn)生種群。對于TSP問題，種群里面的每一個個體（或叫染色體）都代表一組城市的排列，其質(zhì)量高低用一個適應(yīng)函數(shù)來評價。每一個個體按照一定的概率，通常是按照適應(yīng)值被選擇進行交叉、倒串、插串、變異產(chǎn)生新的下一代種群。適應(yīng)值高的個體更有機會來繁殖下一代，隨著連續(xù)的繁殖，種群趨于收斂于高的那些種群，從而找到可能的最優(yōu)解。

（1）編碼與適應(yīng)值函數(shù)。結(jié)合待解決問題，采用十進制實數(shù)編碼，適應(yīng)值函數(shù)結(jié)合目標(biāo)函數(shù)而定。在 TSP問題中以城市的遍歷次序作為遺傳算法的編碼，例如：（7，4，9，5，6，1，2，8，10）代表從城市7出發(fā)，經(jīng)由城市4-9-5-6-1-2-8-10，最后又回到城市4的一條路徑。適應(yīng)值函數(shù)取為：

其中L為遍歷所有城市的路徑長度。

（2）種群生成與染色體選擇。利用隨機函數(shù)生成一定數(shù)量的十進制實數(shù)編碼種群，根據(jù)適應(yīng)值函數(shù)選擇一對染色體父串進行交配。在此利用輪盤式選擇策略（roulette wheel selection）進行選擇，根據(jù)適應(yīng)函數(shù)值選擇準(zhǔn)備進行交配的染色體父串。

⑶變異算子。變異作用在單個染色體上，對染色體的每一位進行隨機測試，當(dāng)滿足變異概率時，講重新產(chǎn)生該位的編碼。如果變異位在基因頭部，可以重新選擇所有的符號，否則只能選擇終結(jié)符。

⑷倒串算子。倒串算子作用于染色體某個基因的頭部，它隨機地在基因頭部選擇一段子串，然后以該子串中間字符為對稱中心各字符位置順序?qū)φ{(diào)。

⑸插串算子。插串是GEP所特有的遺傳算子。它隨機在基因中選擇一段子串，然后將該子串插入頭部隨機指定的一個位置（但不能是第一個位置），將頭部的其他符號向后順延，超過頭部長度的編碼將被截去。

⑹單點重組。單點重組作用在兩個父代染色體上，隨機選擇一個交叉位置，互換交叉點后面的染色體部分，得到兩個子代染色體。

⑺信息素的初值設(shè)置。根據(jù)GEP算法的執(zhí)行，得到了一定的路徑信息素。另外，為了防止算法過早收斂，陷入局部最優(yōu)解，這里采用最大-最小螞蟻系統(tǒng)（MMAS）中的方法，即將各路徑信息素初值設(shè)為最大值τmax。綜合這兩部分，信息素的初值τs設(shè)置為：

其中：τc是一個常數(shù)，相當(dāng)于MMAS算法中的τmin，τG是遺傳算法求解出的最優(yōu)解所轉(zhuǎn)換的信息素值。

⑻信息素的更新.采用蟻周模型進行信息素的更新公式如公式（2.3），路徑上的軌跡更新方程為公式（2.4）。

τij（t）為t時刻邊e（i，j）上外激素的強度，Δτkij表示第K只螞蟻在本次循環(huán)中留在路徑ij上的信息素，Δτij表示本次循環(huán)中路徑ij上的信息增量，ρ表示軌跡的持久性。

2.3 算法流程

步驟1參數(shù)初始化。令時間t=0，循環(huán)次數(shù)nc=0，設(shè)置最大初循環(huán)次數(shù)ncmax，信息素Q，將m只螞蟻置于n個元素（城市）組成的集合C中，令有向圖上每條邊（i，j）的初始化信息量τij（t）=const，且初始時刻Δτij（0）=0，其中const為常數(shù)；

步驟2 循環(huán)次數(shù)nc=nc+1；

步驟3 螞蟻的禁忌表索引號k=1；

步驟4 螞蟻數(shù)目k=k+1；

步驟5 螞蟻個體根據(jù)狀態(tài)轉(zhuǎn)移式計算的概率選擇元素（城市）并前進，j∈{c-tabuk}；

步驟6 修改禁忌表指針，將螞蟻移動到新的元素（城市），并把該元素（城市）移動到該螞蟻個體的禁忌表中；

步驟7 若k

步驟8 選出本次循環(huán)中的最優(yōu)路徑和次優(yōu)路徑，按照交叉算子中的方法進行交叉運算，并保留最優(yōu)路徑，記其為L；

步驟9 按照2.2中的方法進行變異運算；

步驟10 根據(jù)式（2.3）、（2.4）、（2.5）局部更新每條路徑上的信息量；

步驟11 根據(jù)式（2.3）、（2.4）、（2.5）全局更新每條路徑上的信息量；

步驟12 若滿足結(jié)束條件，即如果循環(huán)次數(shù)nc≥ncmax，則循環(huán)結(jié)束并輸出程序計算結(jié)果，否則清空禁忌表并跳轉(zhuǎn)到步驟2。

3 實驗結(jié)果與分析

本文通過對TSPLIB數(shù)據(jù)庫中Oliver30問題和Eil51問題進行仿真研究，平均運行30次作為仿真結(jié)果，來驗證GEP蟻群混合算法的有效性。實驗中所采取的各項參數(shù)如下：α=1，β=6，Q=140，Oliver30問題中螞蟻數(shù)目m=20，設(shè)置最大循環(huán)次數(shù)300次；在Eil51問題中螞蟻數(shù)目m=30，設(shè)置最大循環(huán)次數(shù)600次。實驗數(shù)據(jù)結(jié)果如表1所示。

對實驗結(jié)果的數(shù)據(jù)進行分析可以看出，本文提出的算法求出的平均解和最優(yōu)解都要優(yōu)于基本的蟻群算法的求解結(jié)果，同時本文算法收斂性能也比基本蟻群算法好，本文給出的一類融入GEP算法的蟻群算法的全局性和收斂性比基本蟻群算法都有所提高，因此是一種有效的改進算法。

4 結(jié)束語

蟻群算法是一種新型的進化算法，它與其它進化算法同樣存在易陷入局部最優(yōu)值，存在過早收斂的現(xiàn)象。本文通過融入GEP算法，引入交叉算子和變異算子擴大了算法的搜索空間，同時在交叉運算中保留解中的公共最優(yōu)路徑加快了算法的收斂速度，改進后蟻群算法可以提高算法的全局搜索能力和收斂性能。通過對TSP問題的仿真表明本文算法是一種有效的改進算法。

[參考文獻]

[1]Li M，Wang H，Li P.Tasks mapping in multi-core based system：Hybrid ACO&GA approach[C].Beijing，China：Proceedings of the 5th International Conference on ASIC，2003：355-340.

[2]Pilat M L，White T.Using genetic algorithms to optimize ACS-TSP [C].Brussels，Belgium：Proceedings of 3rd International Workshop on ant Algorithms/ANTS2002，LNCS，2002：282-287.

[3]元昌安.基于GEP的函數(shù)發(fā)現(xiàn)的智能模型庫關(guān)鍵技術(shù)研究[D].成都：四川大學(xué)博士論文，2006.

[4]左劼.基因表達(dá)式核心技術(shù)研究[D].成都，四川大學(xué)計算機學(xué)院，2004.

[5]唐常杰，張?zhí)鞈c，左吉力，等.基于基因表達(dá)式編程的知識發(fā)現(xiàn)沿革、成果和發(fā)展方向，2004，24（10）：7-10.

[6]Li Minqiang，Kou Jisong，Lin Dan，et al.The theory and ap -plication of genetic algorithm [M].Beijing：Science Press，2002.

[7]李敏強，寇紀(jì)淞，林丹，等.遺傳算法的基本理論與應(yīng)用[M].北京：科學(xué)出版社，2002.336～343.

[8]丁建立，陳增強，袁著祉.遺傳算法與螞蟻算法的融合[J].計算機研究與發(fā)展，2003，40（9）：1351-1356.