求解二次分配問(wèn)題的預(yù)處理快速螞蟻系統(tǒng)

吳果林， 李學(xué)遷

（1.桂林航天工業(yè)學(xué)院理學(xué)部，桂林 541004；2.上海理工大學(xué)管理學(xué)院，上海 200093）

二次分配問(wèn)題（quadratic assignment problem，QAP）是由Koopmans等［1］在1957年提出的組合優(yōu)化問(wèn)題.該問(wèn)題可描述為給定n個(gè)設(shè)施和n個(gè)節(jié)點(diǎn)，兩個(gè)n×n的矩陣D＝（drs）和F＝（fij）.其中drs是節(jié)點(diǎn)r和s之間的距離，而fij是設(shè)施i和j之間的流量.QAP是尋找一個(gè)分配方案，使得每一個(gè)設(shè)施分配一個(gè)節(jié)點(diǎn).由于設(shè)施的數(shù)量等于節(jié)點(diǎn)的數(shù)量，故每一個(gè)分配方案相當(dāng)于整數(shù)集｛1，2，…，n｝中的一個(gè)排列.QAP的目標(biāo)是尋找整數(shù)集｛1，2，…，n｝中的一個(gè)排列，最小化目標(biāo)函數(shù)

其中，Φ為整數(shù)集｛1，2，…，n｝所有排列的集合，φ為Φ中的一個(gè)排列（或問(wèn)題的一個(gè)解），φi給出了設(shè)施i在當(dāng)前解φ上的節(jié)點(diǎn).

Sahni等［2］于1976年證明QAP是一個(gè)NP－難的優(yōu)化問(wèn)題，因此當(dāng)問(wèn)題的規(guī)模超過(guò)30時(shí)，尋找問(wèn)題的最優(yōu)解就變得不切實(shí)際，一個(gè)切實(shí)可行的辦法是使用元啟發(fā)式算法以便在合理的時(shí)間內(nèi)找到高質(zhì)量的解.當(dāng)前用于求解QAP的元啟發(fā)式算法有遺傳算法［3］、模擬退火算法［4］、禁忌搜索算法［5－6］、蟻群優(yōu)化算法［7－13］和迭代局部搜索算法［14－15］等.

在過(guò)去的近20年里，蟻群優(yōu)化算法被用于求解許多組合優(yōu)化問(wèn)題［16］.事實(shí)上，對(duì)于二次分配問(wèn)題中結(jié)構(gòu)化的、現(xiàn)實(shí)生活例子，蟻群優(yōu)化算法是已知的求解QAP的最好算法之一.本文調(diào)查分析了快速螞蟻系統(tǒng)（fast ant system，F(xiàn)ANT）［10－11］，給出了預(yù)處理快速螞蟻系統(tǒng)（preprocessing fast ant system，PFANT）.該算法在構(gòu)建問(wèn)題的解時(shí)預(yù)先進(jìn)行了搜索，挑選那些質(zhì)量較優(yōu)的解參與局部搜索，并設(shè)置動(dòng)態(tài)的算法參數(shù)，防止算法陷入局部最優(yōu)解，出現(xiàn)停滯.這種對(duì)FANT算法的改進(jìn)既保持了其運(yùn)行前期收斂速度快的優(yōu)點(diǎn)［11］，拓寬了算法的搜索范圍，又改進(jìn)了解的質(zhì)量.數(shù)值實(shí)驗(yàn)進(jìn)一步表明，預(yù)處理快速螞蟻系統(tǒng)在求解結(jié)構(gòu)化的、現(xiàn)實(shí)生活的例子保持蟻群優(yōu)化算法的優(yōu)越性；在求解隨機(jī)產(chǎn)生無(wú)結(jié)構(gòu)、網(wǎng)格距離例子時(shí)，其性能與求解這兩類例子的最好算法——禁忌搜索算法（robust taboo search，RTS）［6］不相上下.

1 快速螞蟻系統(tǒng)

受螞蟻系統(tǒng)算法的啟發(fā)，Taillard開(kāi)發(fā)了求解QAP的蟻群優(yōu)化算法，稱為快速螞蟻系統(tǒng)［10－11］.在FANT算法中，解的構(gòu)建是由人工螞蟻通過(guò)隨機(jī)地選擇還沒(méi)有分配的設(shè)施i，利用概率選擇規(guī)則將其分配到空閑的節(jié)點(diǎn)j上，即

式中，τij為分配設(shè)施i到節(jié)點(diǎn)j上的權(quán)重；Ni為設(shè)施i可分配的節(jié)點(diǎn).

FANT算法不同于其它蟻群優(yōu)化算法的地方主要是人工螞蟻的數(shù)量和信息素更新管理.FANT算法僅使用一個(gè)人工螞蟻，單個(gè)人工螞蟻導(dǎo)致該算法快速尋找到一個(gè)質(zhì)量較好的解歸咎于局部搜索算法的引入和相當(dāng)特殊的參數(shù)設(shè)置.另一個(gè)不同于其它蟻群優(yōu)化算法，是信息素更新管理，F(xiàn)ANT算法不使用信息素蒸發(fā).初始所有的信息素都設(shè)置為1，每一次迭代后信息素更新方式為

式中，Jφ為當(dāng)前解φ的目標(biāo)函數(shù)值；Jφib為迭代最優(yōu)解φib的目標(biāo)函數(shù)值；r和R為兩個(gè)參數(shù).r的值在算法運(yùn)行過(guò)程中可以發(fā)生改變，初始值設(shè)為1，而R為固定常數(shù).除按式（2）的更新規(guī)則更新信息素之外，信息素與參數(shù)r還將在兩種情況下發(fā)生改變：a.如果迭代最優(yōu)解φib發(fā)生改變，則參數(shù)與所有的信息素全都重新設(shè)置為1；b.當(dāng)人工螞蟻構(gòu)建的解與迭代最優(yōu)解φib相同時(shí)，參數(shù)將增加1個(gè)單位且所有的信息素設(shè)為r.

設(shè)信息素矩陣為Γ＝（τij）n×n，初始，令r＝1，τij＝r（i，j＝1，2，…，n），迭代最優(yōu)解為φib，則FANT重復(fù)執(zhí)行如下步驟（算法1）：

步驟1 利用式（1）構(gòu)建問(wèn)題的當(dāng)前解φ；

步驟2 利用局部搜索技術(shù)改進(jìn)當(dāng)前解φ，為方便計(jì)仍記為φ；

步驟3 如果Z（φ）＜Z（φib），則φib＝φ，并設(shè)r＝1，τij＝r（i，j＝1，2，…，n）；

步驟4 按式（2）的更新方式更新信息素矩陣Γ.

2 預(yù)處理快速螞蟻系統(tǒng)

從前面的敘述可以看出，F(xiàn)ANT試圖設(shè)計(jì)一種能夠整合重點(diǎn)搜索迭代最優(yōu)解和解構(gòu)建時(shí)探索性的算法.也就是說(shuō)，一方面通過(guò)信息素更新，F(xiàn)ANT不斷地增加迭代最優(yōu)解的權(quán)重，使得算法在迭代最優(yōu)解鄰域選擇問(wèn)題的解；另一方面，當(dāng)算法出現(xiàn)停滯時(shí)（FANT以構(gòu)建解等于迭代最優(yōu)解作為判斷標(biāo)準(zhǔn)），重新設(shè)置信息素，并令r＝r＋1，降低迭代最優(yōu)解與算法構(gòu)建解所對(duì)應(yīng)節(jié)點(diǎn)信息素增加的比重，減少迭代最優(yōu)解所對(duì)應(yīng)節(jié)點(diǎn)的權(quán)重，拓寬解的搜索范圍，增加算法構(gòu)建解的探索性.然而，從實(shí)驗(yàn)的結(jié)果來(lái)看，F(xiàn)ANT算法解的質(zhì)量并沒(méi)有達(dá)到預(yù)期效果，只是在算法運(yùn)行的初期，F(xiàn)ANT總體上比其它算法要好一些，在算法運(yùn)行的后期，其解的質(zhì)量比其它算法要劣［11］.即FANT算法初期收斂速度快，后期易出現(xiàn)停滯.出現(xiàn)這種現(xiàn)象，與FANT算法信息素更新策略有關(guān).由于FANT算法在每次出現(xiàn)新的迭代最優(yōu)解時(shí)，信息素重新設(shè)置為1，迭代最優(yōu)解對(duì)應(yīng)的節(jié)點(diǎn)信息素設(shè)為R，算法始終在迭代最優(yōu)解鄰域?qū)ふ覇?wèn)題的解，故算法運(yùn)行初期收斂速度快.易見(jiàn)，這樣處理的結(jié)果是算法容易陷于局部最優(yōu)解，產(chǎn)生停滯.盡管FANT算法設(shè)計(jì)了跳出局部最優(yōu)解的策略（當(dāng)人工螞蟻構(gòu)建的解與迭代最優(yōu)解φib相同時(shí)，參數(shù)將增加1個(gè)單位且所有的信息素設(shè)為r），但這種方式所需迭代次數(shù)太多，代價(jià)太高.關(guān)于這一點(diǎn)，可從下面的分析看出.

設(shè)FANT在t次迭代產(chǎn)生的迭代最優(yōu)解φib，信息素矩陣為Γ＝（τij）n×n，τij＝r且r＝1，進(jìn)一步假設(shè)此解φib為局部最優(yōu)解，算法出現(xiàn)停滯.下面計(jì)算FANT算法跳出局部最優(yōu)解所需迭代的次數(shù).由于FANT算法采用當(dāng)?shù)a(chǎn)生的解與迭代最優(yōu)解φib相同時(shí)，重新設(shè)置信息素r，降低迭代最優(yōu)解權(quán)重的方法，改變停滯現(xiàn)象.為此，先計(jì)算第一次當(dāng)前解與迭代最優(yōu)解φib相同（即第t＋k1次迭代產(chǎn)生的解等于迭代最優(yōu)解φib）時(shí)，F(xiàn)ANT算法所需迭代次數(shù)，記為k1.根據(jù)FANT算法，每次迭代時(shí)，當(dāng)前解對(duì)應(yīng)節(jié)點(diǎn)的信息素增加1；迭代最優(yōu)解φib對(duì)應(yīng)節(jié)點(diǎn)的信息素增加R.故第t＋k1次迭代時(shí)，信息素矩陣Γ每一行元素和都為n＋k1（R＋1），迭代最優(yōu)解φib對(duì)應(yīng)的每一個(gè)節(jié)點(diǎn)的信息素應(yīng)小于等于k1（R＋1）＋1（此值為每次迭代時(shí)當(dāng)前解等于迭代最優(yōu)解時(shí)信息素的值）.設(shè)在第t＋k1次迭代時(shí)，迭代最優(yōu)解作為當(dāng)前解的概率P，由概率乘法公式

則P應(yīng)滿足

表1給出了QAP規(guī)模為25，50，100，選擇概率為0.1，0.5，0.9，重新設(shè)置信息素為1，2，…，6時(shí)，F(xiàn)ANT算法所需迭代的次數(shù)，R的取值均為6.

表1 跳出局部最優(yōu)解的迭代次數(shù)Tab.1 Iterations times of jumping out of local optimal solution

從表1可以看出，要以較高的概率跳出局部最優(yōu)解，算法所需的迭代次數(shù)非常多.以QAP規(guī)模50為例，若以0.9的概率取得局部最優(yōu)解，算法至少需要迭代1 656次.由于算法每次迭代所需的時(shí)間為O（503），故算法跳出局部最優(yōu)解的時(shí)間花費(fèi)至少為1 656×O（503），這個(gè)數(shù)值已經(jīng)超過(guò)RTS［6］算法求解QAP規(guī)模為50的迭代1 000×50次所需的時(shí)間（RTS每次迭代所需的時(shí)間為O（502）），而RTS算法迭代1 000×50次得到問(wèn)題的解常常作為其它算法求QAP時(shí)比較的參照文獻(xiàn)［8，14－15］.也就是說(shuō)，對(duì)于規(guī)模為50的QAP實(shí)例而言，F(xiàn)ANT算法以0.9的概率跳出局部最優(yōu)解的時(shí)間大于RTS算法1 000×50次迭代的時(shí)間.由表1不難得出，QAP其它規(guī)模的例子同樣也有類似的結(jié)果.綜上所述，F(xiàn)ANT算法設(shè)計(jì)跳出局部最優(yōu)解的策略所需迭代次數(shù)太多，算法后期很少改進(jìn)算法解的質(zhì)量.

盡管有上述不足，但FANT算法仍然是求解QAP的非常有競(jìng)爭(zhēng)力的算法，文獻(xiàn)［12－13］給出了兩種改進(jìn)的FANT算法.事實(shí)上，仔細(xì)分析算法1的流程不難發(fā)現(xiàn)，步驟2是對(duì)步驟1產(chǎn)生的解利用局部搜索進(jìn)行改進(jìn)，而改進(jìn)后解質(zhì)量的好壞很大程度取決于步驟1產(chǎn)生解的質(zhì)量.因此，可以對(duì)步驟1進(jìn)行改進(jìn)，如對(duì)步驟1產(chǎn)生的解進(jìn)行預(yù)處理，以便較高質(zhì)量的解參與步驟2的搜索改進(jìn).由于步驟1構(gòu)建解是不斷通過(guò)隨機(jī)選擇一個(gè)設(shè)施由概率選擇式（1）分配一個(gè)節(jié)點(diǎn)得到，故對(duì)于每一個(gè)設(shè)施i分配的節(jié)點(diǎn)φi，可以比較與前次迭代產(chǎn)生的解所對(duì)應(yīng)的設(shè)施i的節(jié)點(diǎn)φ′i是否相同.若φi≠φ′i，將前次迭代解對(duì)應(yīng)的兩個(gè)節(jié)點(diǎn)φi，φ′i的位置進(jìn)行交換，再比較交換后解的質(zhì)量；若質(zhì)量?jī)?yōu)于交換前的，則設(shè)施i分配節(jié)點(diǎn)φi，否則設(shè)施i還是分配原來(lái)的節(jié)點(diǎn)φ′i.上述方法通過(guò)不斷地重復(fù)，最終得到改進(jìn)的迭代解.易見(jiàn)，改進(jìn)后的迭代解剔除了那些迭代過(guò)程中產(chǎn)生的質(zhì)量較劣的解，使得每次迭代產(chǎn)生的解始終以較好的解參與步驟2的局部搜索，減少一些無(wú)為的迭代與局部搜索，保證更好質(zhì)量的解產(chǎn)生.當(dāng)然，上述改進(jìn)也易使算法快速陷入局部最優(yōu)解，產(chǎn)生停滯.為防止或減少該現(xiàn)象的發(fā)生，在算法每次得到一個(gè)新的迭代最優(yōu)解時(shí)重新設(shè)置一個(gè)新的r值，記為r（t），區(qū)別于原算法每次重新設(shè)置r都等于1.

另一方面，由算法1可知，F(xiàn)ANT算法采用固定參數(shù)R的策略，這種固定參數(shù)的策略對(duì)于規(guī)模較小的QAP例子容易過(guò)早陷入局部最優(yōu)解.而對(duì)于規(guī)模較大的QAP例子由于迭代最優(yōu)解的權(quán)重較輕，算法收斂速度較慢.為此，文獻(xiàn)［13］給出了一種變參數(shù)的FANT算法，實(shí)驗(yàn)證明，改進(jìn)了的算法求解QAP的質(zhì)量有較大的提高.借鑒文獻(xiàn)［13］的思想，為進(jìn)一步簡(jiǎn)化運(yùn)算，針對(duì)不同規(guī)模QAP采用不同的參數(shù)R的策略，記為R（n）.因此，改進(jìn)后的算法信息素更新方式為

綜上所述，可以對(duì)FANT算法作如下兩點(diǎn)改進(jìn)：其一，在FANT算法解的構(gòu)建步，對(duì)每一個(gè)設(shè)施分配的節(jié)點(diǎn)進(jìn)行預(yù)處理，判斷該分配是否改進(jìn)上一次迭代解的質(zhì)量，若改善，則分配該節(jié)點(diǎn)，否則，保留原迭代解分配的節(jié)點(diǎn)；其二，在FANT算法信息素更新步，由式（3）取代式（2）作為算法的信息素更新策略.改進(jìn)后的FANT算法稱為預(yù)處理快速螞蟻系統(tǒng)（PFANT），其算法流程為：

設(shè)信息素矩陣為Γ＝（τij）n×n，初始令r（0）＝1，τij＝r（0）（i，j＝1，2，…，n），初始解為φ，迭代最優(yōu)解為φib，則PFANT重復(fù)執(zhí)行步驟（算法2）為：

步驟1 考查由式（1）分配的每一個(gè)節(jié)點(diǎn)的能否改進(jìn)上一次迭代解φ的質(zhì)量.若改善，則分配該節(jié)點(diǎn)；否則，保留原迭代解分配的節(jié)點(diǎn).為方便計(jì)構(gòu)建后的解記為φ；

步驟2 利用局部搜索技術(shù)改進(jìn)當(dāng)前解φ，仍記為φ；

步驟3 如果Z（φ）＜Z（φib），則φib＝φ，重新設(shè)置信息素τij＝r（t）（i，j＝1，2，…，n，t＝1，2，…）；

步驟4 按式（3）的更新方式更新信息素矩陣Γ.

3 數(shù)值實(shí)驗(yàn)

這一部分選擇QAPLIB中的例子運(yùn)行PFANT和FANT算法.實(shí)驗(yàn)的硬件環(huán)境為Pentium（R）4 2.5GHz處理器，80GB硬盤(pán)，256MB內(nèi)存，Microsoft Windows SP3操作系統(tǒng)，開(kāi)發(fā)工具為VC＋＋6.0.對(duì)于FANT算法，參數(shù)R＝6；PFANT算法參數(shù)R＝［2n］，其中［］為取整運(yùn)算，參數(shù)r隨著迭代最優(yōu)解φib的改變?cè)?與2之間不斷地取值.實(shí)驗(yàn)以RTS算法迭代1 000n次所需的時(shí)間作為迭代終止條件.實(shí)驗(yàn)采用QAPLIB中的例子按文獻(xiàn)［17］分為4類.第一類，隨機(jī)產(chǎn)生無(wú)結(jié)構(gòu)問(wèn)題，這類問(wèn)題是根據(jù)均勻分布隨機(jī)產(chǎn)生距離流量矩陣的問(wèn)題.第二類，隨機(jī)產(chǎn)生網(wǎng)格距離問(wèn)題，這類問(wèn)題的距離來(lái)源于一個(gè)網(wǎng)格，節(jié)點(diǎn)與節(jié)點(diǎn)的距離定義為網(wǎng)格上節(jié)點(diǎn)之間的曼哈頓距離.第三類，現(xiàn)實(shí)問(wèn)題，這類問(wèn)題是從實(shí)際問(wèn)題抽象出來(lái)的.第四類，模擬現(xiàn)實(shí)問(wèn)題，因?yàn)榈谌惉F(xiàn)實(shí)問(wèn)題規(guī)模較小，所以這類問(wèn)題是根據(jù)現(xiàn)實(shí)問(wèn)題的特點(diǎn)隨機(jī)產(chǎn)生的較大規(guī)模的問(wèn)題.另外，考慮到規(guī)模小于20的問(wèn)題容易求解，這里只測(cè)試規(guī)模大于等于20的問(wèn)題，數(shù)值實(shí)驗(yàn)結(jié)果見(jiàn)表2.表中給出的結(jié)果是超出已知最優(yōu)解的百分比，最好的結(jié)果用斜粗體表示.

表2 PFANT算法的測(cè)試結(jié)果Tab.2 Testing result of the PFANT algorithm

盡管算法解的質(zhì)量很大程度依賴所求例子［17］，但從表2仍然不難發(fā)現(xiàn)，PFANT算法解的質(zhì)量較FANT算法有較大幅度的提升，總體上要優(yōu)于FANT算法，例外的只有Tai 35a，Tai 80a，Tai 50b，Tai 80b.對(duì)比RTS算法，在RTS算法求解有較大優(yōu)勢(shì)的隨機(jī)產(chǎn)生無(wú)結(jié)構(gòu)與網(wǎng)格距離例子中，PFANT算法總體上質(zhì)量也稍優(yōu)于RTS算法；至于現(xiàn)實(shí)問(wèn)題及模擬現(xiàn)實(shí)問(wèn)題，PFANT算法全面優(yōu)于RTS算法，例外的只有Tai 50b，Tai 80b.相對(duì)MMAS［8］，ILS［14］，HILS［15］算法在現(xiàn)實(shí)問(wèn)題及模擬現(xiàn)實(shí)問(wèn)題優(yōu)于RTS算法，在隨機(jī)產(chǎn)生無(wú)結(jié)構(gòu)及網(wǎng)格距離問(wèn)題遜于RTS算法而言，PFANT算法求解QAP上有較大提高.

其次，考察FANT與PFANT算法跳出局部最優(yōu)解時(shí)重新設(shè)置信息素的次數(shù)，表3（見(jiàn)下頁(yè)）給出了兩算法求解上述4類問(wèn)題的結(jié)果.從表3明顯可以看出，上述4類問(wèn)題的每一個(gè)例子，PFANT算法重新設(shè)置的次數(shù)都小于或等于FANT算法.出現(xiàn)這種情況的原因是由于PFANT算法在每次迭代構(gòu)建問(wèn)題的解時(shí)都預(yù)先進(jìn)行了搜索，剔除了那些質(zhì)量較劣的解參與局部搜索.在相同的迭代時(shí)間內(nèi)，算法能在局部最優(yōu)解更廣的鄰域內(nèi)搜索，增加發(fā)現(xiàn)更優(yōu)的局部最優(yōu)解的機(jī)會(huì)，減少了重新設(shè)置信息素的次數(shù).

表3 FANT與PFANT算法重新設(shè)置信息素的次數(shù)Tab.3 The times of resetting pheromone in the FANT and PFANT algorithm

4 結(jié) 論

盡管FANT算法在信息素更新管理與解的構(gòu)建方面較其它蟻群優(yōu)化算法作了較大的改進(jìn)，為求解不規(guī)則QAP例子最有競(jìng)爭(zhēng)性的算法之一［9］，但也有明顯的缺點(diǎn)（如算法前期收斂速度較快，后期速度較慢，易發(fā)生停滯現(xiàn)象等）.通過(guò)分析FANT算法跳出迭代最優(yōu)解的策略，指出算法易發(fā)生停滯現(xiàn)象的原因，并提出了改進(jìn)的方法，得到一種求解QAP的新算法——預(yù)處理快速螞蟻系統(tǒng)（PFANT）.理論與實(shí)驗(yàn)分析表明，PFANT算法較大程度地改進(jìn)FANT算法的缺點(diǎn)，拓寬了算法迭代最優(yōu)解鄰域的搜索范圍，減少了重新設(shè)置信息素的次數(shù)，改善了QAP解的質(zhì)量.

［1］ Koopmans T C，Berkmann M J.Assignment problems and the location of economic activities［J］.Econometrica，1957，25（1）：53－76.

［2］ Sahni S，Gonzalez T.P－Complete approximation problems［J］.Journal of the Association of Computing Machinery，1976，23（3）：555－565.

［3］ Ahuja R K，Orlin J B，Tiwari A.A greedy genetic algorithm for the quadratic assignment problem［J］.Computers and Operations Research，2000，27（10）：917－934.

［4］ Connolly D T.An improved annealing scheme for the QAP［J］.European Journal of Operational Research，1990，46（1）：93－100.

［5］ Skorin－Kapov J.Tabu search applied to the quadratic assignment problem［J］.ORSA Journal on Computing，1990，2（1）：33－45.

［6］ Taillard E D.Robust taboo search for the quadratic assignment problem［J］.Parallel Computing，1991，17（4／5）：443－455.

［7］ Maniezzo V，Colorni A.The ant system applied to the quadratic assignment problem［J］.IEEE Transactions on Knowledge and Data Engineering，1999，11（5）：769－778.

［8］ Stützle T，Hoos H H.MAX－MIN ant system［J］.Future Generation Computer Systems，2000，16（8）：889－914.

［9］ Gambardella L M，Taillard E D，Dorigo M.Ant colonies for the quadratic assignment problem［J］.Journal of the Operational Research Society，1999，50（2）：167－176.

［10］ Taillard E D.FANT：fast ant system.Technical report IDSIA－46－98［R］.Lugano：IDSIA，1998.

［11］ Taillard E D，Gambardella L M.Adaptive memories for the quadratic assignment problems.Technical ReportIDSIA－87－97［R］.Lugano：IDSIA，1997.

［12］ 吳果林，劉登峰.改進(jìn)的快速蟻群系統(tǒng)求解二次分配問(wèn)題［J］.桂林航天工業(yè)學(xué)院學(xué)報(bào)，2012，17（4）：424－427.

［13］ 吳果林.變參數(shù)的快速螞蟻系統(tǒng)求解二次分配問(wèn)題［J］.科學(xué)技術(shù)與工程，2013，13（7）：324－328.

［14］ Stützle T.Iterated local search for the quadratic assignment problem［J］.European Journal of Operational Research，2006，174（3）：1519－1539.

［15］ Hussin M S，Stützle T.Hierarchical iterated local search for the quadratic assignment problem［J］.Lecture Notes in Computer Science，2009，5818：115－129.

［16］ 馬良，項(xiàng)培軍.螞蟻算法在組合優(yōu)化中的應(yīng)用［J］.管理科學(xué)學(xué)報(bào)，2004，4（2）：32－37.

［17］ Taillard E D.Comparison of iterative searches for the quadratic assignment problem［J］.Location Science，1995，3（2）：87－105.