求解旅行商問題的多樣化搜索帝國競爭算法

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

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

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

中圖分類號：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個城市推銷商品，依次不重復(fù)地訪問每個城市，最終回到起始城市，求解其訪問路線的最短回路。生活中常見的電路板布線問題、最短物流配送問題、車間調(diào)度問題等，都可抽象為TSP從而進(jìn)行求解，因此研究TSP具有較高的實(shí)際價值和理論意義。

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

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

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

本文所提出的基于多樣化搜索策略的帝國競爭算法（Imperialist Competitive Algorithm based on Multiple Search Strategy， MSSICA），

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

1 帝國競爭算法

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

帝國彼此之間也會互相競爭，王國中最弱的殖民地被其他帝國搶奪，即競爭作用。

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

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

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

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

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

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

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

2.1 概率模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 多樣化搜索策略

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

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

2.4 算法步驟

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本章將通過旅行商問題編程實(shí)現(xiàn)進(jìn)行驗(yàn)證，以此顯示該算法對于組合性問題具有優(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個中小型測試?yán)}，并與BBICAHybird、BBEA、RABNET（Real-valued Antibody NETwork）[15]、SME[16]進(jìn)行比較。

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

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

4 結(jié)語

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

該策略在可能陷入局部最優(yōu)時保留母體中具有競爭優(yōu)勢的國家并舍棄母體中其他國家，然后以隨機(jī)產(chǎn)生國家的方式填滿母體。在可行解空間里由隨機(jī)產(chǎn)生國家的方式在不同的解空間進(jìn)行搜索，由概率模型及區(qū)塊的方式記錄正確信息，有效增加求解的多樣性且不失去原有的求解質(zhì)量。最后通過與同類算法比較，驗(yàn)證了本文所提出的基于多樣化搜索策略的帝國競爭算法具備良好的全局搜索效果，也代表著本文方法可有效應(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] 李明， 雷德明. 基于新型帝國競爭算法的高維多目標(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)的混合帝國競爭算法[J]. 價值工程， 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.