改進(jìn)交互式蟻群算法及其應(yīng)用*

黃永青，楊善林，梁昌勇

1.合肥工業(yè)大學(xué) 管理學(xué)院，合肥 230009

2.銅陵學(xué)院 信息技術(shù)與工程管理研究所，安徽 銅陵 244000

改進(jìn)交互式蟻群算法及其應(yīng)用*

黃永青1,2+，楊善林1，梁昌勇1

1.合肥工業(yè)大學(xué) 管理學(xué)院，合肥 230009

2.銅陵學(xué)院 信息技術(shù)與工程管理研究所，安徽 銅陵 244000

HUANG Yongqing,YANG Shanlin,LIANG Changyong.Improved interactive ant colony algorithm and its application.Journal of Frontiers of Computer Science and Technology,2016,10(12)：1720-1728.

交互式蟻群優(yōu)化（interactive ant colony optimization，iACO）是一種利用人來(lái)評(píng)價(jià)解的優(yōu)劣而進(jìn)行系統(tǒng)優(yōu)化的技術(shù)，可以求解性能指標(biāo)不能或者難以數(shù)量化的優(yōu)化問題。分析了交互式蟻群優(yōu)化模型面臨的研究困難。針對(duì)Tanabe等人提出的交互式螞蟻算法性能不足的問題，提出利用全局歷史最優(yōu)解進(jìn)行信息素的更新，并將信息素限定在一定區(qū)間內(nèi)的改進(jìn)交互式蟻群優(yōu)化算法，從人機(jī)交互角度討論了解的構(gòu)造方法和人的評(píng)價(jià)策略。最后，利用函數(shù)優(yōu)化和汽車造型設(shè)計(jì)進(jìn)行了實(shí)驗(yàn)，運(yùn)行結(jié)果表明算法具有較高優(yōu)化性能。

交互式蟻群優(yōu)化；蟻群優(yōu)化；人機(jī)交互；汽車造型

1 引言

蟻群優(yōu)化（ant colony optimization，ACO）自意大利學(xué)者Dorigo提出以來(lái)，已經(jīng)應(yīng)用于求解TSP（traveling salesman problem）等NP難問題[1]，并應(yīng)用于二分社區(qū)網(wǎng)絡(luò)挖掘[2]和記憶式圖像檢索[3]等領(lǐng)域。然而，這些傳統(tǒng)的ACO算法需要建立顯式的目標(biāo)函數(shù)才能求解，當(dāng)性能指標(biāo)難以數(shù)量化時(shí)，算法應(yīng)用受到限制。

交互式進(jìn)化計(jì)算（interactive evolutionary computation，IEC）通過人來(lái)評(píng)價(jià)解對(duì)應(yīng)的系統(tǒng)輸出以確定解的優(yōu)劣，而以進(jìn)化算法在參數(shù)空間中搜索更好的解，已經(jīng)成功應(yīng)用于汽車造型設(shè)計(jì)[4]、基于搜索的軟件工程[5]、產(chǎn)品形態(tài)設(shè)計(jì)[6]、圖書商品個(gè)性化搜索[7]、協(xié)同產(chǎn)品定制[8]等方面。但I(xiàn)EC需要人不斷參與進(jìn)化過程進(jìn)行解的評(píng)價(jià)，一般要求種群規(guī)模和進(jìn)化代數(shù)處在一個(gè)較小水平；由于人評(píng)價(jià)具有不確定性，且其偏好會(huì)隨著評(píng)價(jià)過程的進(jìn)行而調(diào)整改變，這些因素制約了人機(jī)系統(tǒng)的求解性能。因此，IEC的改進(jìn)、用戶疲勞問題和用戶評(píng)價(jià)的不確定性等成為研究熱點(diǎn)。鞏敦衛(wèi)等人[9]根據(jù)組成個(gè)體各基因意義單元值出現(xiàn)的頻率定義個(gè)體的相似度，可以在提高種群規(guī)模情況下適當(dāng)減輕用戶疲勞感，從而使得算法具有較高的搜索性能。另外，還可通過使用符合用戶認(rèn)知規(guī)律的區(qū)間數(shù)評(píng)價(jià)進(jìn)化個(gè)體適應(yīng)值[10]和代理模型等[11-12]方式，來(lái)解決以上問題。但是，目前IEC的搜索算法部分大多集中在遺傳算法。

近幾年來(lái)，交互式蟻群優(yōu)化（interactive ant colony optimization，iACO）的研究為拓展IEC和傳統(tǒng)ACO研究提供了新的思路[13-15]。iACO是一種進(jìn)化個(gè)體適應(yīng)值由人來(lái)評(píng)價(jià)的蟻群優(yōu)化方法，由于利用螞蟻進(jìn)行解的構(gòu)造和其獨(dú)特的信息素更新方式，從而可獲得滿意的求解性能。

在IEC領(lǐng)域，對(duì)iACO的研究才剛剛起步，文獻(xiàn)[13]研究了一種交互式螞蟻算法模型，利用每一代中較好的2～3個(gè)解進(jìn)行信息素的更新，并應(yīng)用于成套服裝的選擇。作為一種實(shí)用的IEC技術(shù)，Tanabe等人是國(guó)外IEC領(lǐng)域最早[13]研究iACO模型的作者。文獻(xiàn)[14]則針對(duì)軟件工程中早期設(shè)計(jì)問題，提出一種構(gòu)造“屬性、方法和類”的iACO方法，可以對(duì)信息系統(tǒng)中的類及其含有哪些屬性和方法進(jìn)行設(shè)計(jì)。文獻(xiàn)[15]也提出一種iACO模型，并應(yīng)用于汽車造型設(shè)計(jì)。

由于iACO是近幾年發(fā)展的模型，有必要分析iACO模型研究面臨的挑戰(zhàn)問題，并針對(duì)文獻(xiàn)[13]中的iACO算法存在著易陷入局部?jī)?yōu)化、性能偏低的問題，給出本文的改進(jìn)iACO模型。

2 iACO模型研究的挑戰(zhàn)

在傳統(tǒng)ACO模型中，螞蟻群體的規(guī)模大，迭代步數(shù)多，其求解性能較優(yōu)。而在iACO模型中，受到人的評(píng)價(jià)能力（人容易疲勞）、顯示器展示個(gè)體表現(xiàn)型數(shù)目或系統(tǒng)輸出的特殊性（如音頻個(gè)體）等因素的影響，螞蟻數(shù)目一般只有幾個(gè)至20個(gè)個(gè)體，迭代步數(shù)也只有十多步或幾十步，因此在這種苛刻條件下，使得iACO模型具有滿意的求解性能是研究者面臨的巨大挑戰(zhàn)。一些提高iACO模型的策略被采用，如要求當(dāng)前代構(gòu)造的解均不同[15]，或者新構(gòu)造的解與之前構(gòu)造的所有解均不同[13]。另外，一些傳統(tǒng)ACO算法的各種改進(jìn)策略對(duì)iACO模型性能的提高有正面的作用，如將信息素限制在適當(dāng)?shù)膮^(qū)間內(nèi)[14]。

類似于IEC，iACO用戶疲勞問題也是廣大研究者面臨的核心問題。在IEC中，用戶不斷地打分和比較分值相近（如70分與71分）個(gè)體之間的差異，會(huì)使用戶容易疲勞。顯然，IEC克服用戶疲勞問題的相關(guān)研究，會(huì)對(duì)iACO模型研究有著很好的借鑒意義。其實(shí)，由于iACO模型自身的特點(diǎn)，使得用戶有時(shí)不必給出進(jìn)化個(gè)體具體的評(píng)價(jià)值，而只需指出用戶滿意的解或判定當(dāng)前最好解即可[13,15]，這大大減小了用戶的評(píng)價(jià)疲勞。

iACO模型構(gòu)造出來(lái)后，會(huì)利用某個(gè)應(yīng)用領(lǐng)域的實(shí)際問題進(jìn)行性能測(cè)試。但這些問題常常有較強(qiáng)的實(shí)踐背景，因此在IEC領(lǐng)域還缺乏基準(zhǔn)的測(cè)試問題或案例，來(lái)評(píng)估這些交互式算法的性能。例如，在基于搜索的軟件工程領(lǐng)域，由于缺乏基準(zhǔn)的軟件設(shè)計(jì)問題，Smith等人[14]利用自己設(shè)計(jì)的3個(gè)不同規(guī)模問題進(jìn)行算法性能的測(cè)試。文獻(xiàn)[15]通過構(gòu)造一個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)來(lái)評(píng)估算法性能，為設(shè)計(jì)標(biāo)準(zhǔn)測(cè)試案例提供了思路。另外，通過問卷，與以往算法結(jié)果進(jìn)行比較，也可以測(cè)試和了解算法的性能與有效性。

最優(yōu)參數(shù)選擇是智能算法研究的難點(diǎn)，iACO模型也存在同樣的問題。目前，文獻(xiàn)中大多通過實(shí)驗(yàn)試探，得到算法的最優(yōu)參數(shù)。但iACO用戶評(píng)價(jià)值具有不確定性，用戶偏好會(huì)調(diào)整改變，如何尋找魯棒性的參數(shù)是值得研究的問題。

3 改進(jìn)的交互式蟻群算法設(shè)計(jì)

3.1 交互式螞蟻算法模型

文獻(xiàn)[13]提出了一種交互式螞蟻算法（interactive ant system，iAS）模型，并應(yīng)用于成套服裝（分為夾克、T恤、褲子和鞋子4部分）的選擇。因?yàn)樵谠搯栴}中沒有啟發(fā)式信息，所以第k只螞蟻選擇一套服裝第i個(gè)部分的第 j個(gè)款式的概率和信息素更新公式分別如下[13]：

類似于遺傳算法的處理，為保留全局歷史最優(yōu)解，該iAS模型使用精英保留策略，即用戶選擇的若干滿意解（2至3個(gè)），直接保留到下一代。

3.2 改進(jìn)的iACO模型

在文獻(xiàn)[13]中，對(duì)問題的一般性描述和螞蟻構(gòu)筑解方式的介紹不夠，本文將給予補(bǔ)充，并在此基礎(chǔ)上給出相應(yīng)的改進(jìn)措施。

在iACO模型中，設(shè)潛在解為x=(x1,x2,…,xp),其中變量x（ii=1,2,…,p）有ni種取值。本文考慮一類無(wú)約束的隱性目標(biāo)優(yōu)化問題：

max f(x)

因?yàn)楸粌?yōu)化系統(tǒng)目標(biāo)函數(shù)與決策變量間的數(shù)量關(guān)系難以建立，所以利用人來(lái)評(píng)價(jià)問題解對(duì)應(yīng)的系統(tǒng)輸出，并將其評(píng)價(jià)值作為目標(biāo)函數(shù)值。

將信息素直接放置在各決策變量上，把變量xij上的信息素水平記為τij(i=1,2,…,p，j=1,2,…,ni）。螞蟻在第i維決策變量上選擇第 j個(gè)取值的選擇概率如下：

螞蟻在參數(shù)空間中的行走路線如圖1所示。

Fig.1 Trails of ants in pheromone space圖1 螞蟻在信息素空間中的行走路線

各點(diǎn)上的信息素初始值可設(shè)置為：

其中，τ0是初始信息素水平。

m只螞蟻在一次迭代中構(gòu)造m個(gè)解，為了提高算法搜索效率，每構(gòu)造一個(gè)新解，要求其與之前所有代構(gòu)造的所有解均不一樣。然后將當(dāng)前代構(gòu)造的m-1個(gè)解與上一代用戶選擇的最好解一并輸出，交給用戶評(píng)價(jià)，以確定當(dāng)前全局歷史最優(yōu)解Sgb，并進(jìn)行信息素更新操作，更新公式如下：

其中,i=1,2,…,p,j=1,2,…,ni,ρ是信息素殘留系數(shù)，Q是Sgb所在最優(yōu)路徑上的信息素增量。為了防止某些路徑上的信息素過高或過低造成的螞蟻過度偏向選擇某些路徑，將信息素限制在適當(dāng)區(qū)間內(nèi)，即：

3.3 用戶評(píng)價(jià)方式

在IEC中，用戶評(píng)價(jià)方式有全體評(píng)價(jià)和部分評(píng)價(jià)兩種。全體評(píng)價(jià)就是要求用戶評(píng)價(jià)每一代所有進(jìn)化個(gè)體的適應(yīng)值；部分評(píng)價(jià)只需要用戶評(píng)價(jià)部分其感興趣個(gè)體的具體適應(yīng)值，而未評(píng)價(jià)個(gè)體的適應(yīng)值則根據(jù)距離或代理模型等進(jìn)行適應(yīng)值估計(jì)。因此，IEC用戶的評(píng)價(jià)任務(wù)是非常繁重的。

相比較而言，本文iACO用戶的評(píng)價(jià)則簡(jiǎn)易許多，這主要是由iACO模型的特點(diǎn)決定的。因?yàn)槟Ｐ椭兄桓鶕?jù)迄今歷史最優(yōu)解Sgb進(jìn)行信息素的更新，并且更新時(shí)不需要具體的用戶評(píng)價(jià)值，所以用戶不必評(píng)價(jià)每一代中進(jìn)化個(gè)體的具體優(yōu)劣值，而只要指出哪一個(gè)個(gè)體是迄今歷史最優(yōu)解Sgb就可以了。同時(shí)，在后面實(shí)際實(shí)驗(yàn)系統(tǒng)中，將上一代用戶選擇的Sgb放在界面的第一位，讓用戶方便和其他新構(gòu)造的m－1個(gè)解進(jìn)行比較。經(jīng)過這樣處理后，用戶評(píng)價(jià)簡(jiǎn)單而又輕松，大大降低了用戶的評(píng)價(jià)疲勞。

3.4 算法參數(shù)的討論

對(duì)iACO模型，其中相關(guān)參數(shù)具有如下性質(zhì)：

定理 iACO算法迭代到第n代時(shí)，任意一條路徑上的信息素大小為：

證明 先不考慮最大最小信息素約束，若信息素τij所在的路徑(i,j)始終為最優(yōu)路徑，則由式（5）～（7）可知：

若信息素τij所在的路徑(i,j)始終為非優(yōu)路徑，易知：

而一般路徑(i,j)上的信息素在第n代時(shí)處于以上兩種情況之間，同時(shí)又滿足最大最小信息素的限制，從而可得定理結(jié)論。 □

證明 顯然始終沒有選中成為優(yōu)化路徑上的信息素最快取到最小信息素值，即有：

推論2若取τ0=τmax，則當(dāng)Q≤(1-ρ)τmax時(shí)，最優(yōu)路徑上的信息素不會(huì)超過τmax。

證明 由假設(shè)知Q≤(1-ρ)τmax=(1-ρ)τ0從而有

即最優(yōu)路徑上的信息素不會(huì)超過τmax。 □

本文iACO模型一共涉及5個(gè)參數(shù)，以上定理和推論為設(shè)置算法參數(shù)提供了理論指導(dǎo)，同時(shí)通過多次實(shí)驗(yàn)獲得優(yōu)化參數(shù)。

對(duì)于初始信息素水平τ0，其值越大，則會(huì)在算法運(yùn)行的初始若干代內(nèi)保證各條路徑上的信息素具有一個(gè)較高的水平，但隨著信息素的揮發(fā)，其作用逐漸減弱。在式（6）中，其右邊第1項(xiàng)與第2項(xiàng)分別表示信息素?fù)]發(fā)和強(qiáng)化過程，參數(shù)ρ與Q的作用與傳統(tǒng)ACO類似。

由推論1可知，殘留系數(shù)ρ的取值不易過小，否則信息素?fù)]發(fā)過快，非優(yōu)路徑上信息素會(huì)很快取到最小信息素值τmin。經(jīng)過實(shí)驗(yàn)，殘留系數(shù)ρ最優(yōu)取值區(qū)間為[0.10,0.74]，實(shí)驗(yàn)中取ρ=0.50。

由推論2可知，當(dāng)取τ0=τmax時(shí)，參數(shù)Q值越大，使得優(yōu)化路徑上信息素水平很快累積到最大信息素取值τmax，從而會(huì)弱化初始信息素水平τ0的作用，使算法易陷入局部?jī)?yōu)化。經(jīng)過實(shí)驗(yàn)發(fā)現(xiàn)，τ0與Q配合起來(lái)設(shè)置較好，其優(yōu)化值較容易獲得，實(shí)驗(yàn)中取τ0= τmax=26,Q=1。

最小信息素水平τmin的取值不能過大，這樣會(huì)使各路徑上的信息素水平過于平均，不利于搜索。經(jīng)過實(shí)驗(yàn)測(cè)試發(fā)現(xiàn)，τmin取值在區(qū)間[0.01,0.08]時(shí)，具有較好的綜合性能。實(shí)驗(yàn)中，取τmin=0.022。

注意，以上定理和推論對(duì)參數(shù)設(shè)置具有一般性指導(dǎo)意義，其具體參數(shù)取值，是以4.1節(jié)函數(shù)優(yōu)化實(shí)驗(yàn)得到的優(yōu)化參數(shù)。實(shí)際上，在遇到不同類型或不同領(lǐng)域模型時(shí)，由于問題規(guī)模、全局最優(yōu)解與局部最優(yōu)解分布及參數(shù)空間形狀等不同，搜索難度會(huì)不同，算法優(yōu)化參數(shù)也會(huì)有所不同，需要根據(jù)實(shí)際問題進(jìn)行測(cè)試以得到合適的參數(shù)。

3.5 算法步驟

iACO算法的具體實(shí)現(xiàn)過程如下：

步驟1初始化。設(shè)定算法參數(shù),均勻放置初始信息素。

步驟2解的構(gòu)建。先完成當(dāng)前代一個(gè)解的構(gòu)建：為保證一定的隨機(jī)性，當(dāng)生成的隨機(jī)數(shù)rand＜P0（P0為一較小值）時(shí)，以隨機(jī)方式構(gòu)建直至找到一個(gè)與之前所有代解均不同的新解；否則(rand≥P0)，螞蟻根據(jù)各條路徑上的信息素水平，按選擇概率公式（4）通過從圖1所示的路徑來(lái)完成一個(gè)解的構(gòu)建（要求同前）。若是第一代，則一共構(gòu)建m個(gè)解，輸出到用戶界面上；若代數(shù)大于1，則僅需要構(gòu)建m－1個(gè)解，并與之前用戶選擇的全局歷史最優(yōu)解Sgb一起顯示在用戶界面上（Sgb的位置排在第一）。

步驟3用戶評(píng)價(jià)。用戶比較當(dāng)前代解的優(yōu)劣，重新確定迄今全局歷史最優(yōu)解Sgb。

步驟4終止判定。若滿足終止條件，則輸出結(jié)果，結(jié)束算法；否則按式（6）～（8）對(duì)信息素進(jìn)行更新操作，轉(zhuǎn)步驟2。

另外，在步驟2中設(shè)置算法停滯標(biāo)志flag，即在構(gòu)造當(dāng)前解時(shí)，若與之前所構(gòu)造的解重復(fù)5 000次，則認(rèn)定算法陷入停滯，提前終止算法，并輸出相關(guān)提示。實(shí)驗(yàn)中，P0取0.05。

4 仿真實(shí)驗(yàn)

4.1 函數(shù)優(yōu)化實(shí)驗(yàn)

為了獲得客觀的比較結(jié)果,利用無(wú)約束的函數(shù)優(yōu)化實(shí)驗(yàn)來(lái)模擬iACO模型的求解過程，即將iACO用戶評(píng)價(jià)改為函數(shù)計(jì)算，本文用以下測(cè)試函數(shù)進(jìn)行模擬實(shí)驗(yàn)。

為了說(shuō)明方便，將文獻(xiàn)[13]和文獻(xiàn)[15]中兩類交互式螞蟻算法分別記為iAS1和iAS2。對(duì)以上函數(shù)實(shí)驗(yàn)數(shù)據(jù)，分別使用標(biāo)準(zhǔn)遺傳算法GA、iAS1、iAS2和iACO算法進(jìn)行求解，得到在不同種群規(guī)模情況下的優(yōu)化結(jié)果如表1所示。在表1中，每個(gè)算法獨(dú)立執(zhí)行10 000次并統(tǒng)計(jì)結(jié)果；3類算法最大迭代代數(shù)均設(shè)定為100；iAS1和iACO算法在構(gòu)造新解時(shí)，記錄與之前構(gòu)造解的重復(fù)次數(shù)，若重復(fù)次數(shù)達(dá)到5 000次，則判定算法陷入停滯，算法尋優(yōu)失??；GA、iAS1和iACO算法均采用精英保留策略。iAS2對(duì)陷入停滯有相應(yīng)的處理方法，其進(jìn)化采用文獻(xiàn)[15]的方式，為了比較的合理性，在統(tǒng)計(jì)信息時(shí)每一代以采用精英保留策略的種群作為統(tǒng)計(jì)對(duì)象。GA的交叉概率取0.8,變異概率取0.07；iAS1算法每一代選擇3個(gè)最好解保留到下一代。

Table 1 Results of 4 algorithms for function optimization表1 4類算法對(duì)函數(shù)的優(yōu)化結(jié)果

從表1中可以看出，在不同種群規(guī)模情況下，GA搜索平均收斂代數(shù)接近60代，搜索到最優(yōu)解的成功率在52%以內(nèi)，性能較低。iAS1算法收斂代數(shù)令人滿意，但成功率偏低，整體性能較低。iAS2算法在種群規(guī)模12以上時(shí)，成功率接近或達(dá)到100%，收斂代數(shù)較iAS1算法偏大。本文的改進(jìn)算法iACO在10 000次搜索均找到最優(yōu)解，成功率為100%；在使用相同規(guī)模的種群情況下，其收斂代數(shù)介于iAS1和iAS2算法之間，在20代左右，綜合性能表現(xiàn)良好。

為了進(jìn)一步了解以上4類算法的進(jìn)化收斂情況，分別運(yùn)行算法統(tǒng)計(jì)每代的最好解適應(yīng)值和種群平均適應(yīng)值，得到結(jié)果分別如圖2和圖3所示。由圖可以看出，3類蟻群算法的收斂速度均比GA快，適合精細(xì)化搜索；GA算法運(yùn)行代數(shù)長(zhǎng)，收斂慢，性能偏低；iAS1算法表現(xiàn)出較好的收斂性能，但由表1知該算法易陷入停滯；iACO則表現(xiàn)出較好的綜合性能。

為了測(cè)試以上4類算法對(duì)一般函數(shù)的優(yōu)化性能，下面使用文獻(xiàn)[16]的基于網(wǎng)格劃分策略的連續(xù)域蟻群優(yōu)化方法進(jìn)行測(cè)試，并將文獻(xiàn)[16]中的蟻群優(yōu)化策略分別改為本文的iAS1、iAS2和iACO算法的優(yōu)化策略即可。所測(cè)試的函數(shù)優(yōu)化問題如下：

Fig.2 Evolution of the best fitness value of 4 algorithms to optimizef1function圖2 4類算法優(yōu)化 f1函數(shù)時(shí)最好解進(jìn)化情況

Fig.3 Evolution of average fitness value of 4 algorithms to optimizef1function圖3 4類算法優(yōu)化 f1函數(shù)時(shí)平均適應(yīng)值進(jìn)化情況

例2 min f2(X)=-[x1sin(9πx2)-x2cos(25πx1)+20]，其中x1,x2∈[-10,10]。

例4 min f4(X)=-[21.5+x1sin(4πx1)+x2sin(20πx2)，其中x1∈[-3.0,12.1],x2∈[4.1,5.8]。

在優(yōu)化時(shí)涉及到的螞蟻數(shù)目等算法參數(shù)請(qǐng)參考文獻(xiàn)[16]的設(shè)置，其余涉及本文算法的參數(shù)使用本文設(shè)置。其中有變動(dòng)的參數(shù)包括：GA的交叉與變異概率分別取0.9和1/Li，Li表示函數(shù) fi(i=2,3,4)中個(gè)體的二進(jìn)制編碼長(zhǎng)度，GA種群規(guī)模取30，進(jìn)化最大代數(shù)為1 000代；函數(shù) f2的等分?jǐn)?shù)N=33。記錄4類算法分別優(yōu)化以上3個(gè)函數(shù)時(shí)每代最好解，并將前300代的結(jié)果分別展示在圖4～圖6中。鑒于300代以后的優(yōu)化結(jié)果在圖中基本是重疊的，故未畫出。

Fig.4 Evolution of the best fitness value of 4 algorithms to optimizef2function圖4 4類算法優(yōu)化 f2函數(shù)時(shí)最好解進(jìn)化情況

Fig.5 Evolution of the best fitness value of 4 algorithms to optimizef3function圖5 4類算法優(yōu)化 f3函數(shù)時(shí)最好解進(jìn)化情況

Fig.6 Evolution of the best fitness value of 4 algorithms to optimizef4function圖6 4類算法優(yōu)化 f4函數(shù)時(shí)最好解進(jìn)化情況

由于文獻(xiàn)[16]的求解思想是先在參數(shù)空間內(nèi)打網(wǎng)格，使用ACO算法求解當(dāng)前的最好解；然后以當(dāng)前最好解為中心進(jìn)行網(wǎng)格劃分，再使用ACO算法求解，如此往復(fù)直到求解到合適的精度停止。每做一次網(wǎng)格劃分，即為一個(gè)周期；并且隨著周期的增長(zhǎng)，變量x的取值范圍會(huì)越來(lái)越小，因此iAS1、iAS2和iACO算法統(tǒng)計(jì)的當(dāng)前代最好解在圖中表現(xiàn)出階躍性和周期性。

從圖4～圖6中可以看出，GA在優(yōu)化函數(shù) f4時(shí)，初始收斂性能好于其他3類算法，但在中后期收斂性能不及iACO算法。iACO算法在優(yōu)化函數(shù)f2和 f3時(shí)的收斂性能要好于GA、iAS1和iAS2算法，綜合優(yōu)化性能最優(yōu)。

4.2 汽車造型設(shè)計(jì)實(shí)驗(yàn)

為驗(yàn)證算法的實(shí)用性和運(yùn)行性能，使用汽車造型設(shè)計(jì)系統(tǒng)[4,15]進(jìn)行測(cè)試。iACO的系統(tǒng)進(jìn)化界面如圖7所示。其中，用戶若在上一代選擇了nb個(gè)滿意解，則在進(jìn)化界面上的前nb個(gè)系統(tǒng)輸出即為其上一代選擇的滿意解，本文算法nb=1；文獻(xiàn)[13]算法使用精英保留策略，nb=3。

Fig.7 System interface of iACO圖7 iACO系統(tǒng)進(jìn)化界面

3類算法分別獨(dú)立運(yùn)行10次進(jìn)行比較，結(jié)果如表2所示。其中，3類算法的種群規(guī)模均取12，最大進(jìn)化代數(shù)為30代，其他參數(shù)設(shè)置同4.1節(jié)。標(biāo)準(zhǔn)iGA算法的平均比較次數(shù)中，每一代中的相同個(gè)體不記入評(píng)價(jià)次數(shù)。

Table 2 Results of 3 algorithms for car styling design表2 3類算法對(duì)汽車造型設(shè)計(jì)的優(yōu)化結(jié)果

從表2中可以看出，iGA用戶平均評(píng)價(jià)次數(shù)約230次，遠(yuǎn)高于其他3類算法；iGA的平均收斂代數(shù)比iAS1和iACO算法高出近10代，比iAS2算法也要高出近6代。同時(shí)，iGA用戶必需給出每一個(gè)個(gè)體的具體適應(yīng)值，因此用戶評(píng)價(jià)的負(fù)擔(dān)是非常繁重的，故iGA的整體性能低。iAS1與iACO算法平均進(jìn)化代數(shù)相近，但iAS1用戶要求每一代選定3個(gè)最為滿意的解，因此其評(píng)價(jià)次數(shù)要比iACO多出近2.8倍；由于iAS2算法要比較全局歷史最優(yōu)解、當(dāng)前代最優(yōu)解和上一次信息素重新初始化后的最優(yōu)解之間的優(yōu)劣，故其用戶評(píng)價(jià)次數(shù)與iAS1算法相近?？傮w來(lái)看，基于蟻群搜索的iAS1、iAS2與iACO用戶每一代只需要選擇其滿意的1至3個(gè)解，而不必給出選定解的具體評(píng)價(jià)值，因此操作簡(jiǎn)單而又輕松，極大地降低了用戶疲勞。不難看出，4類算法中iACO具有最好的運(yùn)行性能。

需要指出的是，和傳統(tǒng)智能算法一樣，本文算法也會(huì)有陷入局部?jī)?yōu)化的可能，若陷入局部?jī)?yōu)化，則判定算法尋優(yōu)失敗，需要重新運(yùn)行算法。

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

本文深入分析了iACO模型的研究難點(diǎn)，并討論解決思路。針對(duì)Tanabe等人提出的交互式螞蟻算法模型的不足，提出了一個(gè)改進(jìn)iACO模型，給出其求解問題的一般性描述、螞蟻構(gòu)造解的方式、轉(zhuǎn)移概率的計(jì)算與信息素的更新方法；模型運(yùn)用全局歷史最優(yōu)解進(jìn)行信息素更新，并將信息素限定在適當(dāng)區(qū)間內(nèi)；對(duì)模型參數(shù)進(jìn)行了理論分析；從人機(jī)交互的特點(diǎn)出發(fā)，設(shè)計(jì)了合理的用戶評(píng)價(jià)策略；最后，利用函數(shù)優(yōu)化和汽車造型設(shè)計(jì)進(jìn)行了實(shí)驗(yàn)比較，結(jié)果表明本文算法具有較高的運(yùn)行性能，有著良好的應(yīng)用前景。

iACO算法進(jìn)一步研究的問題有：提高算法的性能；用戶疲勞問題處理；將算法應(yīng)用到其他相關(guān)實(shí)踐領(lǐng)域。

[1]Marco D,Thomas S.Ant colony optimization[M].Cambridge,USA:MIT Press,2004.

[2]Xu Yongcheng,Chen Ling.Community detection on bipartite networks based on ant colony optimization[J].Journal of Frontiers of Computer Science and Technology,2014,8 (3):296-304.

[3]Chen Guangpeng,Yang Yubin.Memory-type image retrieval method based on ant colony algorithm[J].Journal of Frontiers of Computer Science and Technology,2011,5(1):32-37.

[4]Meng Weidong,Huang Yongqing,Lu Qing,et al.Adaptive interactive genetic algorithm oriented to car styling design[J]. Computer Engineering and Applications,2012,48(21):240-243.

[5]Simons C L,Parmee I C.Elegant,object-oriented software design via interactive evolutionary computation[J].IEEE Transactions on Systems,Man,and Cybernetics:Part C, 2012,42(6):1779-1805.

[6]Yang Yanpu,Liu Qiong.Product form design method driven by design intent[J].Computer Integrated Manufacturing Systems,2015,21(4):867-874.

[7]Sun Xiaoyan,Lu Yina,Gong Dunwei,et al.Interactive genetic algorithm with CP-nets preference surrogate and application in personalized search[J].Control and Decision, 2015,30(7):1153-1161.

[8]Dou Runliang,Zong Chao,Nan Guofang.Multi-stage interactive genetic algorithm for collaborative product customization[J].Knowledge-Based Systems,2016,92:43-54.

[9]Gong Dunwei,Chen Jian,Sun Xiaoyan.Novel interactive genetic algorithm for estimating individual fitness based on similarity[J].Control Theory&Applications,2013,30(5): 558-566.

[10]Gong Dunwei,Guo Guangsong,Lu Li,et al.Adaptive inter-active genetic algorithms with interval fitness of evolutionary individuals[J].Progress in Natural Science,2008,18(3): 359-365.

[11]Sun Xiaoyan,Chen Shanshan,Gong Dunwei,et al.Weighted multi-output Gaussian process-based surrogate of interactive genetic algorithm with individuals interval fitness[J]. ActaAutomatica Sinica,2014,40(2):172-184.

[12]Sun Xiaoyan,Gong Dunwei,Jin Yaochu,et al.A new surrogate-assisted interactive genetic algorithm with weighted semisupervised learning[J].IEEE Transactions on Cybernetics, 2013,43(2):685-698.

[13]Tanabe R,Gonsalves T,Itoh K.Interactive ACO algorithm toward practical IEC application fields[C]//Advanced Methods,Techniques,and Applications in Modeling and Simulation:Proceedings in Information and Communications Technology,2011 Asia Simulation Conference,Seoul,Nov 2011:308-315.

[14]Simons C L,Smith J,White P.Interactive ant colony optimization(iACO)for early liftcycle software design[J]. Swarm Intelligence,2014,8(2):139-157.

[15]Huang Yongqing,Zhang Xiangde,Li Xudong.Interacitve ant system[J].Control and Decision,2012,27(4):609-612.

[16]Huang Yongqing,Hao Guosheng,Zhong Zhishui,et al.Improved ant colony algorithm based on grid strategy for continuous space optimization[J].Computer Engineering and Applications,2013,49(9):61-64.

附中文參考文獻(xiàn)：

[2]徐永成,陳崚.基于蟻群優(yōu)化的二分網(wǎng)絡(luò)社區(qū)挖掘[J].計(jì)算機(jī)科學(xué)與探索,2014,8(3):296-304.

[3]陳光鵬,楊育彬.利用蟻群算法的記憶式圖像檢索方法[J].計(jì)算機(jī)科學(xué)與探索,2011,5(1):32-37.

[4]孟偉東,黃永青,陸青,等.面向汽車造型設(shè)計(jì)的自適應(yīng)交互式遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(21):240-243.

[6]楊延璞,劉瓊.設(shè)計(jì)意圖驅(qū)動(dòng)的產(chǎn)品形態(tài)設(shè)計(jì)方法[J].計(jì)算機(jī)集成制造系統(tǒng),2015,21(4):867-874.

[7]孫曉燕,陸宜娜,鞏敦衛(wèi),等.基于CP-nets的偏好感知交互式遺傳算法及其個(gè)性化搜索[J].控制與決策,2015,30 (7):1153-1161.

[9]鞏敦衛(wèi),陳健,孫曉燕.新的基于相似度估計(jì)個(gè)體適應(yīng)值的交互式遺傳算法[J].控制理論與應(yīng)用,2013,30(5):558-566.

[11]孫曉燕,陳姍姍,鞏敦衛(wèi),等.基于區(qū)間適應(yīng)值交互式遺傳算法的加權(quán)多輸出高斯過程代理模型[J].自動(dòng)化學(xué)報(bào), 2014,40(2):172-184.

[15]黃永青,張祥德,李旭東.交互式螞蟻算法[J].控制與決策,2012,27(4):609-612.

[16]黃永青,郝國(guó)生,鐘志水,等.基于網(wǎng)格劃分策略的連續(xù)域改進(jìn)蟻群算法[J].計(jì)算機(jī)工程與應(yīng)用,2013,49(9):61-64.

HUANG Yongqing was born in 1974.He received the Ph.D.degree in management science and engineering from Hefei University of Technology in 2007.Now he is a professor at Tongling University.His research interests include evolutionary computing and ant colony optimization,etc.

黃永青（1974—），男，湖北黃梅人，2007年于合肥工業(yè)大學(xué)管理科學(xué)與工程專業(yè)獲得博士學(xué)位，合肥工業(yè)大學(xué)博士后，現(xiàn)為銅陵學(xué)院計(jì)算機(jī)系教授，主要研究領(lǐng)域?yàn)檫M(jìn)化計(jì)算,蟻群優(yōu)化等。

YANG Shanlin was born in 1948.He is an academician of China Academy of Engineering,and professor and Ph.D.supervisor at Hefei University of Technology.His research interests include decision science and technology, data mining and artificial intelligence,etc.

楊善林（1948—），男，安徽安慶人，中國(guó)工程院院士，合肥工業(yè)大學(xué)教授、博士生導(dǎo)師，主要研究領(lǐng)域?yàn)闆Q策科學(xué)與技術(shù)，數(shù)據(jù)挖掘，人工智能等。

LIANG Changyong was born in 1965.He is a professor and Ph.D.supervisor at Hefei University of Technology. His research interests include decision analysis,data mining and artificial intelligence,etc.

梁昌勇（1965—），男，安徽肥西人，博士，合肥工業(yè)大學(xué)教授、博士生導(dǎo)師，主要研究領(lǐng)域?yàn)闆Q策分析，數(shù)據(jù)挖掘，人工智能等。

Improved InteractiveAnt ColonyAlgorithm and ItsApplication*

HUANG Yongqing1,2+,YANG Shanlin1,LIANG Changyong1
1.School of Management,Hefei University of Technology,Hefei 230009,China
2.Institute of Information Technology and Engineering Management,Tongling University,Tongling,Anhui 244000,China
+Corresponding author:E-mail:yongqinghuangbs@sina.com

Interactive ant colony optimization(iACO)is a technique that optimizes target systems based on human evaluation.It can be used to solve the systems whose optimization indices are unable or difficult to be quantificated. Firstly,this paper analyzes the difficulties faced by iACO model.Nextly,aiming at the low performance of interactive ant system that is put forward by Tanabe et al.,this paper proposes an improved iACO algorithm.The pheromone in the proposed model is updated with the best ant and limited to a certain range.The method of constructing solutions and evaluating strategies from the perspective of human-computer interaction are discussed.Finally,the results of the experiments of function optimization and car styling draft design show that the proposed algorithm has higher optimization performance.

10.3778/j.issn.1673-9418.1509093

A

TP18

*The National Natural Science Foundation of China under Grant Nos.71271072,71331002(國(guó)家自然科學(xué)基金);the Postdoctoral Science Foundation of China under Grant No.2014M560508(中國(guó)博士后科學(xué)基金);the Fundamental Research Funds for the Central Universities of China under Grant No.2013HGBH0029(中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金);the Specialized Research Fund for the Doctoral Program of Higher Education of China under Grant No.20110111110006(高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金);the Natural Science Foundation of Anhui Province under Grant No.1208085MG121(安徽省自然科學(xué)基金);the Research Foundation of Educational Commission ofAnhui Province under Grant Nos.KJ2012A269,SK2015A537(安徽省教育廳重點(diǎn)項(xiàng)目);the Scientific Research Foundation of Tongling University under Grant No.2014tlxyxs31(銅陵學(xué)院科研項(xiàng)目).

Received 2015-09,Accepted 2016-01.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-01-04,http://www.cnki.net/kcms/detail/11.5602.TP.20160104.0953.002.html

Key words:interactive ant colony optimization;ant colony optimization;human-computer interaction;car styling