陳孟輝 劉俊麟 徐健鋒 李向軍

摘 要：帝國(guó)競(jìng)爭(zhēng)算法是一種局部搜索能力較強(qiáng)的群智能優(yōu)化算法，但過度的局部搜索會(huì)導(dǎo)致多樣性丟失并陷入局部最優(yōu)。針對(duì)這一問題提出基于多樣化搜索的帝國(guó)競(jìng)爭(zhēng)算法（MSSICA）。將國(guó)家定義為一條可行解，將王國(guó)定義成四種特性不同的組合人造解方式。在搜索時(shí)使用區(qū)塊機(jī)制保留各自的優(yōu)勢(shì)解片段，并對(duì)不同的帝國(guó)使用差異化的組合人造解方式以搜索不同解空間的有效可行解信息。在陷入局部最優(yōu)時(shí)，使用多樣化搜索策略注入均勻分布的可行解替換較無優(yōu)勢(shì)的解以提升多樣性。實(shí)驗(yàn)結(jié)果顯示，多樣化搜索策略可以有效地改善帝國(guó)算法的求解多樣性，并提升求解質(zhì)量與穩(wěn)定性。

關(guān)鍵詞：組合性問題;人造解;帝國(guó)競(jìng)爭(zhēng)算法;全局搜索

中圖分類號(hào)：TP301.6

文獻(xiàn)標(biāo)志碼：A

Abstract：? The imperialist competitive algorithm is a swarm intelligence optimization algorithm with strong local search ability， but excessive local search will lead to the loss of diversity and fall into local optimum. Aiming at this problem， an Imperialist Competitive Algorithm based on Multiple Search Strategy （MSSICA） was proposed. The country was defined as a feasible solution and the kingdoms were defined as fourmechanisms of combinatorial artificial chromosome with different characteristics. The block mechanism was used to retain the dominant solution fragment?during search and differentiated mechanisms? of combinatorial artificialchromosomewas used for different empires to search the effective and feasible solution information of different solution spaces. When it come to the local optimum， the multiple search strategy was used to inject a uniformly distributed feasible solution to replace a less advantageous solution to enhance the diversity. Experimental? results show that the multiple search strategy can effectively improve diversity of the imperialist competitive algorithm and improve the quality and stability of the solution.Key words：? combinatorial problem; artificial chromosome; imperialist competitive algorithm; global search

0 引言

旅行商問題（Traveling Salesman Problem， TSP）[1-3]是經(jīng)典的NP-Hard組合優(yōu)化問題，它的描述如下：設(shè)一位商人需要到N個(gè)城市推銷商品，依次不重復(fù)地訪問每個(gè)城市，最終回到起始城市，求解其訪問路線的最短回路。生活中常見的電路板布線問題、最短物流配送問題、車間調(diào)度問題等，都可抽象為TSP從而進(jìn)行求解，因此研究TSP具有較高的實(shí)際價(jià)值和理論意義。

該類問題的求解主要有完全算法和近似算法兩大方向。完全算法如動(dòng)態(tài)規(guī)劃法等可以保證搜索到最優(yōu)解，但由于其時(shí)間復(fù)雜度過高，在大規(guī)模問題上往往難以滿足性能要求。而近似算法如啟發(fā)式算法[4-6]等只能找到近似解，不過可以在多項(xiàng)式時(shí)間內(nèi)結(jié)束，但對(duì)于較為復(fù)雜的非線性問題，容易陷入局部最優(yōu)。因此，如何有效優(yōu)化啟發(fā)式算法，改善其全局搜索能力，成為廣大學(xué)者關(guān)注和研究的熱點(diǎn)。

2007年Atashpaz-Gargari等[7-9]受到人類社會(huì)政治演化過程的啟發(fā)，從帝國(guó)間的殖民競(jìng)爭(zhēng)到最終稱霸的過程中提出了帝國(guó)競(jìng)爭(zhēng)算法（Imperialist Competitive Algorithm， ICA）。Forouharfard等[10]在接駁式轉(zhuǎn)運(yùn)問題上的實(shí)驗(yàn)數(shù)據(jù)顯示，該算法在求解效果、收斂速度和運(yùn)行時(shí)間上都比基因算法更優(yōu)越，但依然存在搜索空間分布不均、搜索后期帝國(guó)多樣性降低導(dǎo)致過早收斂等明顯缺陷。針對(duì)上述問題，國(guó)內(nèi)外很多學(xué)者基于帝國(guó)競(jìng)爭(zhēng)算法提出了不同的改進(jìn)方法。孟洪潮[11]采用拉丁超立方抽樣改善帝國(guó)初始化階段，引入人工蜂群算法中引領(lǐng)蜂與跟隨蜂之間的信息反饋機(jī)制，但在迭代到一定次數(shù)后，蜜蜂容易在局部最優(yōu)解的鄰域附近發(fā)生停滯。Chang等[12]使用區(qū)塊機(jī)制，在搜索過程中保留優(yōu)勢(shì)解序列區(qū)塊，有效加速收斂，但優(yōu)化效果有限且在大型復(fù)雜例題效果仍然不盡如人意。此類啟發(fā)式算法求解組合性問題效果的關(guān)鍵在于算法的全局搜索與局部搜索的能力：當(dāng)算法的設(shè)計(jì)偏重于局部搜索時(shí)，易導(dǎo)致演化的群體過度偏向局部的優(yōu)勢(shì)解區(qū)域，雖然可以快速提升解的質(zhì)量，但過多的局部?jī)?yōu)勢(shì)解將使解群體的多樣性不足;如果沒有避免陷入局部?jī)?yōu)化的機(jī)制，則解群體將難以獲得全局范圍內(nèi)的其他優(yōu)勢(shì)解。

為改善帝國(guó)競(jìng)爭(zhēng)算法的全局搜索性能，保留搜索過程中的優(yōu)勢(shì)片段構(gòu)建區(qū)塊，根據(jù)區(qū)塊信息對(duì)不同的解群體使用不同的搜索策略，組合出不同的人造解注入母體。

本文所提出的基于多樣化搜索策略的帝國(guó)競(jìng)爭(zhēng)算法（Imperialist Competitive Algorithm based on Multiple Search Strategy， MSSICA），

可以在演化群體陷入局部?jī)?yōu)化時(shí)，保留該世代具有優(yōu)勢(shì)的解，注入均勻分布的可行解替換較無優(yōu)勢(shì)的解，以在后續(xù)世代有效地探索不同解空間的信息，改善帝國(guó)競(jìng)爭(zhēng)算法的全局搜索能力。

1 帝國(guó)競(jìng)爭(zhēng)算法

帝國(guó)競(jìng)爭(zhēng)算法的基本假設(shè)：在ICA中，每一個(gè)國(guó)家代表一個(gè)可能的候選解，國(guó)家的強(qiáng)弱則由解的優(yōu)劣定義。根據(jù)各個(gè)國(guó)家的興盛程度可將國(guó)家分為帝國(guó)與殖民地兩大類，每一個(gè)殖民地隸屬于某一個(gè)帝國(guó)。王國(guó)由一個(gè)帝國(guó)和其控制的所有殖民地構(gòu)成，每一個(gè)殖民地的國(guó)力受到所屬帝國(guó)的統(tǒng)治影響而日益強(qiáng)盛，即同化作用。若殖民地的國(guó)力高過所屬帝國(guó)的國(guó)力，該殖民地就會(huì)取代原本的所屬帝國(guó)成為新的帝國(guó)，而原先的帝國(guó)則淪為殖民地。

帝國(guó)彼此之間也會(huì)互相競(jìng)爭(zhēng)，王國(guó)中最弱的殖民地被其他帝國(guó)搶奪，即競(jìng)爭(zhēng)作用。

當(dāng)?shù)蹏?guó)內(nèi)沒有殖民地時(shí)，代表該帝國(guó)已經(jīng)滅亡。如此重復(fù)帝國(guó)競(jìng)爭(zhēng)，帝國(guó)個(gè)數(shù)會(huì)逐漸減少，直至剩下最后一個(gè)帝國(guó)，此帝國(guó)為ICA所搜索的最優(yōu)解。

帝國(guó)競(jìng)爭(zhēng)算法的主要步驟如下：?1）國(guó)家初始化。定義國(guó)家為要優(yōu)化的目標(biāo)變量值數(shù)組：

通常，在遺傳算法中，這個(gè)數(shù)組被稱為染色體。在N維優(yōu)化變量問題中，國(guó)家是N維數(shù)組，代價(jià)函數(shù)定義為：

1）為了提高帝國(guó)競(jìng)爭(zhēng)算法的收斂速度，采用區(qū)塊機(jī)制挖掘出有效的區(qū)塊，即通過保留搜索過程中有效的可行解片段以保留優(yōu)勢(shì)信息。

2）定義四種不同的組合人造解（Artificial Chromosome， AC）的機(jī)制，即根據(jù)概率模型所提供的信息，使用不同的策略人工產(chǎn)生解，以避免陷入局部最優(yōu)，增加母體中可行解的多樣性。

3）將國(guó)家定義為一條可行解，即一個(gè)滿足要求的城市序列。將王國(guó)定義成四種特性不同的組合人造解方式，將母體劃分成四個(gè)不同的王國(guó)。每一個(gè)王國(guó)會(huì)分布在不同的解空間上，形成四個(gè)不同的搜尋范圍。初始的四個(gè)王國(guó)會(huì)分配到相同數(shù)量的殖民地，且各王國(guó)會(huì)依照特定組合人造解機(jī)制，通過競(jìng)爭(zhēng)作用，占領(lǐng)更多殖民地創(chuàng)造多樣性母體以供競(jìng)爭(zhēng)。

4）根據(jù)高競(jìng)爭(zhēng)優(yōu)勢(shì)群體的概率信息，改變搜索解的方向進(jìn)行全局搜索，有效拓展解空間，提高求解的質(zhì)量與多樣性。

2.1 概率模型

為了能有效地利用帝國(guó)競(jìng)爭(zhēng)算法搜索過程中的可行解信息，本文根據(jù)兩個(gè)城市的相連關(guān)系構(gòu)建優(yōu)勢(shì)矩陣。根據(jù)優(yōu)勢(shì)矩陣在世代迭代中挖掘出區(qū)塊信息，并根據(jù)適應(yīng)度更新優(yōu)勢(shì)矩陣。

構(gòu)建優(yōu)勢(shì)矩陣：首先將優(yōu)勢(shì)矩陣初始值設(shè)為0，將當(dāng)前世代母體中的解依照適應(yīng)度函數(shù)值升冪排列挑選優(yōu)秀解集合μ，用μ更新優(yōu)勢(shì)矩陣，將每條解在路徑上存在存在相鄰關(guān)系的城市記錄到優(yōu)勢(shì)矩陣，且所對(duì)應(yīng)的位置累加1。

其中：Xkij表示解序列的路徑中的城市相連關(guān)系;i與j代表城市序號(hào)（i≠j），i， j=1，2，…，n（n代表城市數(shù)目）;k代表解序列的號(hào)碼;m代表被選出用來更新矩陣的解的數(shù)目;t代表目前世代數(shù)。因本文的問題是對(duì)稱路線的旅行商問題，故Cij（t）=Cji（t），優(yōu)勢(shì)矩陣是對(duì)稱型矩陣。

2.2 區(qū)塊挖掘與組合人造解

在經(jīng)典帝國(guó)競(jìng)爭(zhēng)算法的演化過程中，各個(gè)國(guó)家通過競(jìng)爭(zhēng)作用和同化作用會(huì)不斷出現(xiàn)可行解片段，這些固定出現(xiàn)的可行解片段往往就是具有優(yōu)勢(shì)的可行解片段。為了加速收斂，本文引入?yún)^(qū)塊概念，即在演化過程中具有較高適應(yīng)度函數(shù)值的可行解片段，對(duì)任一可行解可記為S={X1，X2，…，Xn}，區(qū)塊可表示為任一Xij=1（i， j=1，2，…，n）且為連續(xù)序列。使用區(qū)塊機(jī)制其主要目的是在迭代時(shí)保留高適應(yīng)度函數(shù)值的片段，以此減少迭代次數(shù)從而顯著提高搜索效率。

區(qū)塊挖掘是根據(jù)優(yōu)勢(shì)矩陣隨機(jī)選擇一個(gè)起始城市，以起始城市為出發(fā)點(diǎn)，將優(yōu)勢(shì)矩陣轉(zhuǎn)換成概率，任意概率大于閾值的路徑記為有效路徑。若所有城市概率均小于閾值，則以路徑最短的記為有效路徑。根據(jù)目前可供挑選的有效路徑，以輪盤選擇法挑選一條路徑作為本次產(chǎn)生的區(qū)塊。

挖掘出區(qū)塊后將這些具有高競(jìng)爭(zhēng)優(yōu)勢(shì)的信息結(jié)合為人造解。本文采用四種不同的組合人造解機(jī)制，通過將人造解注入母體來提高求解質(zhì)量。

四種方式的具體描述如下：

方式一 使用輪盤選擇法根據(jù)優(yōu)勢(shì)矩陣的概率選擇。首先，隨機(jī)選擇初始城市，其余位置根據(jù)優(yōu)勢(shì)矩陣的概率用輪盤選擇法選擇，已被挑選進(jìn)入人造解的城市不再參與選擇。在區(qū)塊比對(duì)部分，每當(dāng)人造解添加新的城市時(shí)，會(huì)將該城市與區(qū)塊數(shù)據(jù)庫中的區(qū)塊進(jìn)行比對(duì)，若區(qū)塊中含有該城市且另一與其相連的城市未被選擇，則將該區(qū)塊復(fù)制到人造解中;若另一與其相連的城市已被挑選到人造解，則該區(qū)塊無效，從復(fù)制后的下個(gè)連接城市開始繼續(xù)選擇下一個(gè)城市，直到完成人造解。

方式二 根據(jù)最短距離進(jìn)行選擇。首先，隨機(jī)產(chǎn)生初始城市，其余位置根據(jù)最短距離選擇，已被挑選進(jìn)入人造解的城市不再參與選擇。在區(qū)塊比對(duì)部分，采用的比對(duì)方法與方式一相同，直到完成人造解。

方式三 首先從區(qū)塊數(shù)據(jù)庫隨機(jī)復(fù)制區(qū)塊到暫存區(qū)塊數(shù)據(jù)庫。隨機(jī)產(chǎn)生初始城市，其余位置根據(jù)優(yōu)勢(shì)矩陣的概率用輪盤選擇法選擇，已被挑選進(jìn)入人造解的城市不再參與選擇。在區(qū)塊比對(duì)部分，使用暫存區(qū)塊數(shù)據(jù)庫對(duì)比，其他與方式一相同，直到完成人造解。

方式四 首先從區(qū)塊數(shù)據(jù)庫隨機(jī)復(fù)制區(qū)塊到暫存區(qū)塊數(shù)據(jù)庫。隨機(jī)產(chǎn)生初始城市，其余位置根據(jù)最短距離選擇，已被挑選進(jìn)入人造解的城市不再參與選擇。在區(qū)塊比對(duì)部分，采用的比對(duì)方法與方式三相同，直到完成人造解。

四種組合人造解機(jī)制根據(jù)兩個(gè)不同策略來篩選資源：

1）根據(jù)城市篩選。

方式一與方式三都應(yīng)用輪盤選擇法選擇下一相連城市，以輪盤選擇法選擇的特性來增加人造解的多樣性;

方式二與方式四都是用最短距離選擇下一個(gè)相連城市，以此提高人造解的收斂速度。

2）根據(jù)資源篩選。

方式一與方式二都使用相同的資源，確保人造解的質(zhì)量來取得更佳的資源;

方式三與方式四則為了避免陷入局部最優(yōu)和增加解的多樣性，隨機(jī)采用已挖掘的區(qū)塊資源。

經(jīng)過人造解的注入和各國(guó)家的演化機(jī)制，母體中會(huì)產(chǎn)生許多新的子代，本文使用精英保留策略，篩選原始母體與子代的精英可行解，選擇出新的母體進(jìn)入下一世代演化。首先，將原始母體與新產(chǎn)生的子代，放入選擇池，將選擇池中所有的可行解按照適應(yīng)度函數(shù)升冪排序，取前N名解組合成為新母體進(jìn)入下一世代演化，其余部分使用隨機(jī)可行解填充，增加母體中可行解的多樣性，避免陷入局部最優(yōu)化。

在本文中，王國(guó)被定義成四種特性不同的組合人造解方式，各個(gè)王國(guó)通過競(jìng)爭(zhēng)作用搶奪殖民地。若更多的國(guó)家（可行解）使用該方式組合人造解，將更大程度地積累優(yōu)勢(shì)進(jìn)入下一世代迭代。

2.3 多樣化搜索策略

在搜索過程中，如果持續(xù)不斷地按照一個(gè)方向搜索，很容易陷入局部最優(yōu)，導(dǎo)致不斷地重復(fù)搜索。因此，本文算法將母體中競(jìng)爭(zhēng)優(yōu)勢(shì)較小的解舍棄，并用隨機(jī)產(chǎn)生的可行解補(bǔ)充，增加母體中可行解的多樣性，避免陷入局部最優(yōu)化，對(duì)下一世代的區(qū)塊挖掘和組合人造解具有指導(dǎo)作用。

在算法后期，如果持續(xù)搜索不同的區(qū)域，可能會(huì)產(chǎn)生較多噪聲，進(jìn)而影響求解方向與質(zhì)量。因此當(dāng)世代數(shù)達(dá)一定比例時(shí)，將清空優(yōu)勢(shì)矩陣，恢復(fù)到最初的搜索范圍，以具有競(jìng)爭(zhēng)優(yōu)勢(shì)的解來領(lǐng)導(dǎo)求解方向。

2.4 算法步驟

綜上所述，本文提出的MSSICA步驟如下：

Step1 初始化解：隨機(jī)產(chǎn)生N條初始可行解作為母體（N為母體大?。xn為優(yōu)勢(shì)解的百分比。

更新概率矩陣：根據(jù)適應(yīng)度函數(shù)（Fitness）

計(jì)算每一條可行解的適應(yīng)度，采用前N×n個(gè)具較高優(yōu)勢(shì)的解更新概率模型。

Step3 區(qū)塊挖掘：根據(jù)概率模型，組合出具有優(yōu)勢(shì)的區(qū)塊。

Step4 組合人造解：使用四種方式組合人造解，產(chǎn)生N條人造解注入母體。

Step5 競(jìng)爭(zhēng)作用：強(qiáng)盛的帝國(guó)從較弱小的帝國(guó)搶奪殖民地，篩選出母體和子代中具有競(jìng)爭(zhēng)優(yōu)勢(shì)的解，成為新的母體進(jìn)入下一世代演化。

Step6 判斷最優(yōu)解是否更新，若未更新跳轉(zhuǎn)到Step7，若已經(jīng)更新且若未達(dá)到結(jié)束條件則重復(fù)執(zhí)行Step2～6直至滿足停止條件時(shí)算法結(jié)束。

Step7 判斷K是否達(dá)到閾值，達(dá)到閾值時(shí)使用多樣化搜索策略更新優(yōu)勢(shì)矩陣，改變探索信息的范圍，舍棄母體中較無優(yōu)勢(shì)的可行解，并隨機(jī)生成可行解填充，并重復(fù)執(zhí)行Step2～6。

MSSICA時(shí)間復(fù)雜度分析如下：

定義變量N為產(chǎn)生的初始解個(gè)數(shù)，t為演化的總世代數(shù)，X（X≤N）為優(yōu)勢(shì)解的數(shù)量，m為城市數(shù)量。

1）初始化解。由于此階段僅進(jìn)行一次，故T（n）=O（N）。

2）更新概率矩陣。本文求解的問題是對(duì)稱型的TSP，對(duì)每個(gè)優(yōu)勢(shì)解需要計(jì)算m2/2次城市間距離信息，因此每個(gè)世代T（n）=O（X×m2/2）=O（X×m2）。

3）區(qū)塊挖掘。區(qū)塊隨機(jī)從每個(gè)可能的城市挖掘，故每個(gè)世代T（n）≤O（m）。

4）組合人造解。產(chǎn)生數(shù)量為N的人造解，T（n）=O（N）。

5）競(jìng)爭(zhēng)作用。重新分配帝國(guó)與帝國(guó)間的國(guó)家數(shù)量，所以每個(gè)世代T（n）=O（N）。

6）多樣化搜索。假設(shè)執(zhí)行了K次執(zhí)行多樣化搜索，且K≤T，每次將會(huì)進(jìn)行再次產(chǎn)生N個(gè)隨機(jī)解并重置概率矩陣，故T（n）=O（t×（N+1））=O（t×N）。

所以MSSICA執(zhí)行t個(gè)世代的時(shí)間復(fù)雜度為：

3 對(duì)比實(shí)驗(yàn)

本章將通過旅行商問題編程實(shí)現(xiàn)進(jìn)行驗(yàn)證，以此顯示該算法對(duì)于組合性問題具有優(yōu)秀的求解能力。實(shí)驗(yàn)環(huán)境為： Ubuntu 18.04 LTS操作系統(tǒng)，2 * Intel Core i9-9900k處理器，64GB內(nèi)存，編程環(huán)境為Jetbrains Rider 2018.1 EAP與.NET Core 2.1。從TSPLIB95數(shù)據(jù)庫（https：//wwwproxy.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp）中選擇21個(gè)中小型測(cè)試?yán)}，并與BBICAHybird、BBEA、RABNET（Real-valued Antibody NETwork）[15]、SME[16]進(jìn)行比較。

本文所研究的啟發(fā)式算法的時(shí)間開銷不會(huì)隨數(shù)據(jù)復(fù)雜度呈指數(shù)增長(zhǎng)，而是取決于演化的世代數(shù)，且本文所比較的BBICAHybird等算法中并未載明其運(yùn)行時(shí)間。因此實(shí)驗(yàn)采用統(tǒng)一的參數(shù)，即母體數(shù)為100，世代數(shù)為城市數(shù)量×50，區(qū)塊長(zhǎng)度為2。

本文以誤差率（Error Rate， ER）作為各算法比較的基準(zhǔn)，且在各例題中進(jìn)行30次實(shí)驗(yàn)并取平均值。其中誤差率分為平均解誤差率（Mean Error Rate，MER）和最優(yōu)解誤差率（Best Error Rate，BER），其計(jì)算公式分別為：

其中：Best表示該例題上使用該算法的最優(yōu)解;Mean表示該例題上使用該算法的平均解;Opt代表該例題目前已知的最優(yōu)解。

由表1可知，MSSICA在復(fù)雜度較小的例題中并不算出色;但在中型例題上，其求解能力甚為優(yōu)越，以整體性能來看，求解質(zhì)量明顯優(yōu)于其他方法。在求解穩(wěn)定性方面，以30次實(shí)驗(yàn)次數(shù)所求得平均值的平均誤差率來看，所求得的解優(yōu)于其他方法，這也表明了MSSICA擁有穩(wěn)定的求解能力。

在復(fù)雜度較高的例題上，若沒有良好的全局搜索能力，往往容易陷入局部最優(yōu)解。因此，為了驗(yàn)證MSSICA具有良好的全局搜索能力及穩(wěn)定的求解能力，從TSPLIB數(shù)據(jù)庫選擇3個(gè)大型例題進(jìn)行測(cè)試。

如表2的實(shí)驗(yàn)數(shù)據(jù)所示，MSSICA在復(fù)雜度較大的三個(gè)例題上，相較BBICAHybird及BBEA而言，在同等的時(shí)間復(fù)雜度下具有較好的求解質(zhì)量和求解穩(wěn)定性。

4 結(jié)語

本文改善了帝國(guó)競(jìng)爭(zhēng)算法的國(guó)家調(diào)配機(jī)制及王國(guó)內(nèi)的搜索策略，提出了多樣化搜索策略。

該策略在可能陷入局部最優(yōu)時(shí)保留母體中具有競(jìng)爭(zhēng)優(yōu)勢(shì)的國(guó)家并舍棄母體中其他國(guó)家，然后以隨機(jī)產(chǎn)生國(guó)家的方式填滿母體。在可行解空間里由隨機(jī)產(chǎn)生國(guó)家的方式在不同的解空間進(jìn)行搜索，由概率模型及區(qū)塊的方式記錄正確信息，有效增加求解的多樣性且不失去原有的求解質(zhì)量。最后通過與同類算法比較，驗(yàn)證了本文所提出的基于多樣化搜索策略的帝國(guó)競(jìng)爭(zhēng)算法具備良好的全局搜索效果，也代表著本文方法可有效應(yīng)用于旅行商等組合性問題。

在后續(xù)的研究中將繼續(xù)關(guān)注此類問題，并使用一些新型的啟發(fā)式算法求解該類問題并提高其全局搜索能力; 另一方面，將使用分布式架構(gòu)，設(shè)計(jì)有效的并行算法以提高算法的效率。

參考文獻(xiàn)（References）

[1] GOLDBERG D E， LINGLE R， Jr. Alleles， Loci， and the traveling salesman problem [C]// Proceedings of the 1st International Conference on Genetic Algorithms. Hillsdale： L. Erlbaum Associates Inc.， 1985： 154-159.

[2] ISMKHAN H， ZAMANIFAR K. Developing improved greedy crossover to solve symmetric traveling salesman problem[EB/OL].[2018-10-10]. https：//arxiv.org/ftp/arxiv/papers/1209/1209.5339.pdf.

[3] 袁豪. 旅行商問題的研究與應(yīng)用[D]. 南京： 南京郵電大學(xué)， 2017： 5-6. （YUAN H. Research and application of traveling salesman problem [D]. Nanjing： Nanjing University of Posts and Telecommunications， 2017： 5-6.）

[4] ARSHAD S， YANG S. A hybrid genetic algorithm and inver over approach for the travelling salesman problem[C]// Proceedings of the 2010 IEEE Congress on Evolutionary Computation. Piscataway： IEEE， 2010： 1-8.

[5] 王艷， 王秋萍， 王曉峰. 基于改進(jìn)螢火蟲算法求解旅行商問題[J]. 計(jì)算機(jī)系統(tǒng)應(yīng)用， 2018， 27（8）： 219-225. （WANG Y， WANG Q P， WANG X F. Solving traveling salesman problem based on improved firefly algorithm[J]. Computer Systems & Applications， 2018， 27（8）： 219-225.）

[6] KIRKPATRICK S， GELATT C D， VECCHI M P. Optimization by simulated annealing[J]. Science， 1983， 220（4598）： 671-680.

[7] ATASHPAZ-GARGARI E， LUCAS C. Imperialist competitive algorithm： an algorithm for optimization inspired by imperialistic competition[C]// Proceedings of the 2007 IEEE Congress on Evolutionary Computation. Piscataway： IEEE， 2007： 4661-4666.

[8] 李明， 雷德明. 基于新型帝國(guó)競(jìng)爭(zhēng)算法的高維多目標(biāo)柔性作業(yè)車間調(diào)度[J].控制理論與應(yīng)用， 2019， 36（6）：893-901. （LI M， LEI D M. Novel imperialist competitive algorithm for many-objective flexible job shop scheduling[J]. Control Theory and Applications， 2019， 36（6）：893-901.）

[9] KAVEH A， TALATAHARI S. Optimum design of skeletal structures using imperialist competitive algorithm[J]. Computers & Structures， 2010， 88（21）： 1220-1229.

[10] FOROUHARFARD S， ZANDIEH M. An imperialist competitive algorithm to schedule of receiving and shipping trucks in cross-docking systems[J]. The International Journal of Advanced Manufacturing Technology， 2010， 51（9/10/11/12）： 1179-1193.

[11] 孟洪潮. 多策略改進(jìn)的混合帝國(guó)競(jìng)爭(zhēng)算法[J]. 價(jià)值工程， 2018， 37（14）： 193-195. （MENG H C. Improved imperialist competitive algorithm based on quantum behavior[J]. Value Engineering， 2018， 37（14）： 193-195.）

[12] CHANG P， HUANG W， WU J， et al. A block mining and re-combination enhanced genetic algorithm for the permutation flowshop scheduling problem[J]. International Journal of Production Economics， 2013， 141（1）： 45-55.

[13] CHEN M H， CHEN S H， CHANG P C. Imperial competitive algorithm with policy learning for the traveling salesman problem[J]. Soft Computing， 2017， 12（7）： 1863-1875.

[14] HUANG W H， CHANG P C， WANG L C， et al. A fast block-based evolutional algorithm for combinatorial problems[J]. International Journal of Computer， Electrical， Automation， Control and Information Engineering， 2012， 6（7）： 889-895.

[15] PASTI R， de CASTRO L N. A neuro-immune network for solving the traveling salesman problem[C]// Proceedings of the 2006 IEEE International Joint Conference on Neural Networks. Piscataway： IEEE， 2006： 3760-3766.

[16] SOMHOM S， MODARES A， ENKAWA T. A self-organizing model for the travelling salesman problem[J]. Journal of the Operational Research Society， 1997， 48（9）： 919-928.