周海燕

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

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

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

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

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

1.1 GEP算法工作原理

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

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

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

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

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

1.3 GEP算法基本步驟

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

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

⑶保留最好個(gè)體；

⑷選擇操作；

⑸變異；

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

⑺重組（1-點(diǎn)重組2-點(diǎn)重組多基因重組）；

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

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

2.1 基本思想

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

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

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

（1）編碼與適應(yīng)值函數(shù)。結(jié)合待解決問(wèn)題，采用十進(jìn)制實(shí)數(shù)編碼，適應(yīng)值函數(shù)結(jié)合目標(biāo)函數(shù)而定。在 TSP問(wèn)題中以城市的遍歷次序作為遺傳算法的編碼，例如：（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為遍歷所有城市的路徑長(zhǎng)度。

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

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

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

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

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

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

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

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

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

2.3 算法流程

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

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

步驟3 螞蟻的禁忌表索引號(hào)k=1；

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

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

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

步驟7 若k

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

步驟9 按照2.2中的方法進(jìn)行變異運(yùn)算；

步驟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é)束并輸出程序計(jì)算結(jié)果，否則清空禁忌表并跳轉(zhuǎn)到步驟2。

3 實(shí)驗(yàn)結(jié)果與分析

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

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

4 結(jié)束語(yǔ)

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

[參考文獻(xiàn)]

[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)的智能模型庫(kù)關(guān)鍵技術(shù)研究[D].成都：四川大學(xué)博士論文，2006.

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

[5]唐常杰，張?zhí)鞈c，左吉力，等.基于基因表達(dá)式編程的知識(shí)發(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]李敏強(qiáng)，寇紀(jì)淞，林丹，等.遺傳算法的基本理論與應(yīng)用[M].北京：科學(xué)出版社，2002.336～343.

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