船體裝配線劃線路徑規(guī)劃的蟻群算法

1、第33卷第10期2012年10月哈爾濱工程大學(xué)學(xué)報JournalofHarbinEngineeringUniversityVol3310Oct2012船體裝配線劃線路徑規(guī)劃的蟻群算法112吳俊杰，紀(jì)卓尚，常會青（1大連理工大學(xué)船舶CAD工程中心，遼寧大連116024；2中遠(yuǎn)船務(wù)集團(tuán)工程有限公司技術(shù)中心，遼寧大連116113）摘要：船體零件裝配線劃線作業(yè)是與船體零件切割作業(yè)同時進(jìn)行的，是現(xiàn)代造船模式中的一個重要環(huán)節(jié)將船體零件劃線路徑規(guī)劃問題作為廣義旅行商問題進(jìn)行分析，針對劃線路徑的特殊性，建立提出了改進(jìn)的蟻群算法的路徑規(guī)劃模型，采用最大最小蟻群算法進(jìn)行優(yōu)化，分析了算法中各參數(shù)取值對算法性能的影響

2、，并同遺傳算法作了比較實驗結(jié)果表明，基于蟻群算法的優(yōu)化模型可以有效減少劃線路徑空走距離實際應(yīng)用表明可有效地減少作業(yè)時間，提高船廠生產(chǎn)效率關(guān)鍵詞：船體零件；配線劃線；蟻群算法；旅行商問題；路徑規(guī)劃doi：103969/jissn1006-7043201111059網(wǎng)絡(luò)出版地址：http：/wwwcnkinet/kcms/detail/231390U201209271001015html中圖分類號：U67199文獻(xiàn)標(biāo)志碼：A7043（2012）10-1205-06文章編號：1006-Antcolonyalgorithmformark-linepathplanningWUJunjie1，JIZhuo

3、shang1，CHANGHuiqing2（1ShipCADEngineeringCenter，DalianUniversityofTechnology，Dalian116024，China；2TechnicalCenter，COSCOShipyardGroupCompanyLtd，Dalian116113，China）Abstract：Hullpartsmark-linemarking，whichisdonewiththenumericalcontrolcuttingoperationsatthesametime，wasoneoftheimportanttachesinmodernshipbu

4、ildingThemarkingpathplanningproblemwouldberegar-dedasthetravelingsalesmanproblemAccordingtothespecialofthemarkingpath，aplanningmodelwaspro-posedbasedonanimprovedantcolonyoptimizationalgorithmandmax-minantsystemwasappliedtooptimizetheproblemByanalysisandsimulation，thebestvaluerangeandcombinatorialopt

5、imizationsettingsofparameterswasgivenThenthecomparisonwithgeneticalgorithmswasgivenThesimulationresultsshowthattheoptimizationmodeliseffective，whichcaneffectivelyreducetheidlemarkingpathKeywords：shiphullparts；mark-linemarking；antcolonyalgorithm；travelingsalesmanproblem；pathplanning隨著數(shù)控切割技術(shù)的日益完善和船舶制造

6、工藝的不斷改善，數(shù)控切割機(jī)已成為各大船企必不可少的一個生產(chǎn)設(shè)備數(shù)控劃線槍作為數(shù)控切割機(jī)的一個重要功能部件，主要是在鋼板上劃出零件的加工裝配線以及其他為后續(xù)服務(wù)的線條符號在對國線、劃線順序是按照裝配線所在內(nèi)船廠的調(diào)研中發(fā)現(xiàn)，零件的切割順序來規(guī)劃的，存在較長的劃線空走路程，造成劃線作業(yè)時間的浪費目前國內(nèi)外公開發(fā)表的文獻(xiàn)中尚未見對劃線路徑規(guī)劃的系統(tǒng)性研究船體零件劃線路徑規(guī)劃可看作廣義的旅行商問題11-219-2710：01收稿日期：2011-網(wǎng)絡(luò)出版時間：2012-基金項目：公益性行業(yè)（農(nóng)業(yè)）科研專項基金資助項目（201003024），男，博士；作者簡介：吳俊杰（1980-），男，教授，博士生導(dǎo)師紀(jì)

7、卓尚（1938-E-mail：shipcad163com通信作者：吳俊杰，（TSP）目前求解TSP問題的算法有很多，如模擬退火算法、遺傳算法、禁忌搜索法、蟻群算法、神經(jīng)網(wǎng)絡(luò)1-4蟻群算法是受蟻群行算法以及各種混合算法為特征啟發(fā)而得出的一種群體智能算法，具有并發(fā)強(qiáng)魯棒性、正反饋性等特點，在解決組合優(yōu)化問性、題上有良好的適應(yīng)性國內(nèi)外的研究者主要集中在解決TSP問題中蟻群模型的改進(jìn)、信息素的更新方式及與其它智能算法的結(jié)合將船體零件劃線路徑并建立了蟻群算法優(yōu)化規(guī)劃問題處理為TSP問題，模型，提出了相應(yīng)的算法策略，最終有效地減少了劃線空走路徑1船體零件劃線路徑規(guī)劃分析船體零件劃線作業(yè)，是根據(jù)數(shù)控劃線指令

8、，從待切鋼板的一個角點出發(fā)，對板上的所有裝配線進(jìn)行劃線，最后再回到出發(fā)點如圖1（a）所示為一張鋼板切割圖，圖1（b）所示為劃線路徑圖劃線空程為313m將每條劃線的起點和終點進(jìn)行標(biāo)號，則劃線作業(yè)路徑可表示為以下有序數(shù)列：Path=0，（1，2），（3，4），（12，11），（9，10），（7，8），（6，5），（15，16），（14，13），（21，22），（18，17），（19，20），（24，23），（31，32），（34，33），（35，36），（30，29），（27，28），25），（37，38），（41，42），（43，44），（40，39），0（26，第10期吳俊杰，等：船體裝配線劃

9、線路徑規(guī)劃的蟻群算法·1207·法以來，大批學(xué)者對其進(jìn)行了充分的研究，提出了許多對基本蟻群算法進(jìn)行改進(jìn)的算法，其中最大最小螞蟻系統(tǒng)（MMAS）具有最優(yōu)性能，已被應(yīng)用在各種TSP問題的求解并取得了良好的效果5-13用最大最小蟻群算法求解TSP問題的基本迭代流程是：1）初始化城市n，螞蟻數(shù)量m，信息素?fù)]發(fā)系數(shù)（01），取任意一只螞蟻按貪婪法生成的一個路徑長度Lbest，置t=02）將所有城市對（i，j）間路徑的信息素ij（t）初始化為按式（2）確定的max：111Lbest3）將m只螞蟻隨機(jī)放到n座城市max=（2）題中，每一條劃線也都可能被螞蟻選為出發(fā)城市而對于每一條劃線的2

10、個端點，在算法初始化時被選中的概率也是同等的因此，在算法初始化時m只螞蟻被隨機(jī)的放置于2n座城市信息素是螞蟻選擇路徑的重要依據(jù)在劃線路徑規(guī)劃問題中，存在螞蟻必走路徑，即劃線本身因?qū)τ趧澗€兩端點之間的路徑，信息素此在初始化時，而對于劃線之間的路徑，信息素初始化初始化為零，為maxmax的值由式（2）得出222路徑轉(zhuǎn)移規(guī)則不失一般性，假設(shè)劃線AB的2個端點分別為A和B當(dāng)點A被第k只螞蟻選為下一到達(dá)城市后，點A被加入禁忌表tabuk中因為劃線AB為必經(jīng)路徑，點B為點A的下一必經(jīng)之點，所以B也應(yīng)被加入第k只螞蟻的禁忌表tabuk中，同時置點B為當(dāng)前城市對于劃線之間路徑的轉(zhuǎn)移則按式（3）進(jìn)行223信息素

11、的更新MMAS把各路徑上的信息素軌跡量限制在4）某時刻t時，各螞蟻按下式?jīng)Q定的概率選擇下一座城市：p=kijtt·ij（t）ij（t）kallowedktik（t）·（t）tik，jallowedk；其他（3）0，cj），allowedk是第k只螞蟻下一步式中：ij=1/d（ci，可以選擇的城市的集合：allowedk=0，1，2，n1tabuk5）當(dāng)所有螞蟻完成一次周游后，找出迄今為止若解達(dá)到要求或迭代次數(shù)已滿，轉(zhuǎn)7），否的最優(yōu)解，則轉(zhuǎn)6）6）對目前為止最短路徑的螞蟻按下式更新各個城市間信息素：bestij（t+n）=（1）·ij（t）+ij其中，bestijm

12、in，max區(qū)間內(nèi)，避免了早熟收斂行為，增加了最優(yōu)解搜索能力但是也存在一些不足之處首先，MMAS只對本次迭代最優(yōu)解或迄今為止最優(yōu)解的螞使得多數(shù)路徑上的信息素量長蟻進(jìn)行信息素更新，影響最優(yōu)解的搜索速度其次，在一時間保持相同，次迭代中產(chǎn)生的最差解，對產(chǎn)生最優(yōu)解不會有很大所以應(yīng)減小這些路徑上的信息素，使較多的的幫助，螞蟻更快集中到較好的路徑上以加快最優(yōu)解的搜索針對這些不足，該文算法在每次迭代中分別對全局部最優(yōu)螞蟻按式（4）進(jìn)行信息素的局最優(yōu)螞蟻、更新，而對局部最差螞蟻則按式（6）進(jìn)行信息素的更新：worstij（t+n）=（1）·ij（t）+ij（6）式中：ij路徑worst（4）=1/L

13、best，Lbest為本次迭代的最短路徑或迄今為止的最短路徑按式（2）和式（5）更新信息素的上下界max和min：min=2max·（1best1nLbest（n2）·bestn=1/Lworst，Lworst為本次迭代中的最差（5），判斷信息素ij是否在范圍min，max若ijmin，則ij=min，若ijmax，則ij=max，返回3）7）結(jié)束迭代，輸出最優(yōu)解22劃線路徑優(yōu)化的蟻群算法模型對于城市規(guī)模為n的旅行商問題，蟻群算法的這樣在每次迭代后增加全局最優(yōu)螞蟻和局部最減少局部最差螞蟻路徑的信息優(yōu)螞蟻路徑的信息素、素，加強(qiáng)了正反饋的效果，同時也增加了解的多樣性224變異算

14、子在船體零件劃線規(guī)劃問題中，每條劃線的方向不同，則劃線路徑長度也大相徑庭因此通過改變劃可以改變最優(yōu)解的性能引入遺傳算法中線的方向，的變異算子，對一次迭代后得到的局部最優(yōu)路徑進(jìn)行變異操作若在變異后得到了優(yōu)于局部最優(yōu)路徑的新路徑，則更新最優(yōu)螞蟻的路徑信息，否則繼續(xù)進(jìn)行下一次變異具體步驟如下：1）隨機(jī)選擇局部最優(yōu)路徑中的任意一條劃線AB規(guī)模也是n對于有n條劃線的船體零件劃線路徑規(guī)劃問題，因為每條劃線都有2個頂點與其對應(yīng)，相當(dāng)于每條劃線都對應(yīng)著旅行商問題中的2個城市，因此劃線路徑規(guī)劃問題的規(guī)模是2n221算法初始化對于旅行商問題中的n座城市，在初始化時m只螞蟻被隨機(jī)放置到n座城市在劃線路徑規(guī)劃問2）改

15、變劃線AB的方向，即交換劃線AB兩端點A和B的位置3）比較變異前后的路徑，若得到更優(yōu)路徑則替換當(dāng)前局部最優(yōu)路徑4）變異次數(shù)若已達(dá)到最大變異次數(shù)m則結(jié)束，否則轉(zhuǎn)1）操作引入變異算子提高了螞蟻在一次搜索中搜索到更優(yōu)路徑的能力，同時增加了解的多樣性3劃線路徑優(yōu)化的蟻群算法描述船體裝配線劃線路徑優(yōu)化的蟻群算法（MLA-CO）主要步驟如下：1）令時間t和迭代次數(shù)Nc為0，設(shè)置螞蟻數(shù)量m和最大循環(huán)次數(shù)Ncmax，初始化環(huán)境信息2）將m只螞蟻隨機(jī)放置于2n個點3）按式（3）計算的概率用輪盤賭法選擇下一個路徑點4）當(dāng)所有螞蟻完成一次周游后，找出本次迭代的局部最優(yōu)解、局部最差解及迄今為止的全局最優(yōu)并對局部最優(yōu)解

16、進(jìn)行變異運算若最優(yōu)解達(dá)到要解，求或迭代次數(shù)已滿，則轉(zhuǎn)6），否則轉(zhuǎn)5）5）對全局最優(yōu)解、局部最優(yōu)解和局部最差解按式（4）和式（6）更新信息素按式（2）和式（5）更新信息素的上下界題并修改相應(yīng)的信息素返回2）6）結(jié)束迭代，輸出最佳路徑4算法參數(shù)的組合分析及仿真實驗選取圖1和圖3所示板材切割圖作為仿真數(shù)據(jù)圖1中共有劃線22條，包含原點相當(dāng)于46座城包含原點相當(dāng)于74座市規(guī)模圖3中有劃線36條，城市大量的研究表明蟻群算法中相關(guān)參數(shù)的不同選擇對算法的性能有至關(guān)重要的影響，但其選取的目前尚沒有理論上的依據(jù)，通常根據(jù)實驗方法和原則，而定通過一系列的仿真實驗研究，來確定算法中參數(shù)的最佳選取規(guī)則，以利于蟻群算法

17、在實際中的應(yīng)用第10期吳俊杰，等：船體裝配線劃線路徑規(guī)劃的蟻群算法·1209·被搜索過的路徑上的信息量的變化比較均勻，信息正反饋的作用不明顯，并且會使收斂速度減慢反之，螞蟻數(shù)量少會使搜索的隨機(jī)性減弱，算法的全局容易出現(xiàn)過早停滯的現(xiàn)象由圖4結(jié)果表性能降低，明螞蟻數(shù)量n/2mn（n為劃線總數(shù)）時，算法的各項性能相對較為平穩(wěn)42啟發(fā)式因子的選擇關(guān)于蟻群算法中啟發(fā)式因子及對算法性能可以通過仿真實的影響及其在實際應(yīng)用中的選擇，驗來分析和確定相關(guān)算法參數(shù)取為：信息素殘留系數(shù)=09，螞蟻數(shù)量分別取為10和20，和取值范圍為010，010，所選取的和以01的步長遞增，最大迭代次數(shù)為500對

18、每一個、組合，分析算法所能達(dá)到的最優(yōu)解及達(dá)到最優(yōu)解所需的迭代次數(shù)Nc，實驗10次取平均值進(jìn)行比較實驗結(jié)果如圖5所示（d）啟發(fā)因子對收斂代數(shù)的影響（n=37）圖5Fig5優(yōu)化結(jié)果Theoptimizationresult由圖5可知，當(dāng)信息啟發(fā)式因子過大時，螞蟻搜索的隨機(jī)性選擇先前走過的路徑的可能性增加，減弱，容易使蟻群的搜索過程過早陷于局部最優(yōu)；當(dāng)過小時，路徑上的信息素ij在搜索過程中的重要性未給予足夠重視，螞蟻完全依賴期望信息的引導(dǎo)易導(dǎo)致陷入無休止的隨機(jī)搜索中當(dāng)期望進(jìn)行搜索，啟發(fā)式因子過大時，螞蟻在某個局部點上選擇局部最短路徑的可能性越大，雖然搜索的速度得以加快，但蟻群在最優(yōu)路徑的搜索過程中隨

19、機(jī)性減弱，易于陷入局部最優(yōu)適當(dāng)?shù)倪x擇及的取值范圍，如取0815、取1525，即便參數(shù)的組合不同，蟻群算法均能獲得較好的解，并且性能非常接近（a）啟發(fā)因子對最優(yōu)解的影響（n=23）43實例選取大連某船廠已建造的114500DWT散貨船通過MLACO和遺傳算和52000DWT散貨船為例，法分別進(jìn)行優(yōu)化遺傳算法參數(shù)選取：群體大小M=40，雜交概率Pc=08，變異概率Pm=005，終止條件為種群中80%的個體已完全是同一個體優(yōu)化后統(tǒng)計結(jié)果如表1，結(jié)果表明MLACO算法比遺傳算法更能有效地減少裝配線劃線空走路徑表1Table1（b）啟發(fā)因子對收斂代數(shù)的影響（n=23）DWTL/m結(jié)果統(tǒng)計Statisti

20、coftheresultsL1/m7445049972L2/m6324835671r1/%2730r2/%39501145001043124600071672L1-注：L-優(yōu)化前劃線空走長度，遺傳算法優(yōu)化后劃線空L2-r1-走長度，蟻群算法優(yōu)化后劃線空走長度，遺傳算法優(yōu)化劃r2-線空走減少率，遺傳算法優(yōu)化劃線空走減少率5結(jié)束語（c）啟發(fā)因子對最優(yōu)解的影響（n=37）本文提出了一種適用于船體裝配線劃線路徑優(yōu)化的蟻群算法優(yōu)化模型研究了算法中螞蟻算量、啟發(fā)式因子的選擇對算法性能的影響實例表明，與遺·1210·哈爾濱工程大學(xué)學(xué)報第33卷傳算法相比，蟻群算法優(yōu)化模型更能有效地減少劃線

21、空走路徑，降低能源損耗；減少劃線作業(yè)時間，提高生產(chǎn)效率本文的研究成果已經(jīng)成功在國內(nèi)船廠并取得了良好的經(jīng)濟(jì)效益得到應(yīng)用，GenerationComputerSystems，2000，16（8）：889-9147DORIGOM，GAMBARDELLALMAntcolonysystem：acooperativelearningapproachtothetravelingsalesmanproblemJIEEETransonEvolutionaryComputation，1997，1（1）：53-668BONABEAUE，DORIGOM，THERAULAZGInspirationforoptimiza

22、tionfromsocialinsectbehaviourJNature，2000，406（6）：39-429THOMASS，DORIGOMAshortconvergenceproofforaclassofantcolonyoptimizationalgorithmsJIEEETrans2002，6（4）：358-365onEvolutionaryComputation，10VERBEECKK，NOWEAColoniesoflearningautomataJIEEETransonSystems，Man，andCyberneticsPartB，2002，32（6）：772-78011鐘珞，趙先明

23、，夏紅霞求解最小MPR集的蟻群算法J智能系統(tǒng)學(xué)報，2011，6（2）：166-171與仿真ZHONGLuo，ZHAOXianming，XIAHongxiaAnantcol-onyalgorithmandsimulationforsolvingminimumMPRJCAAITransactionsonIntelligentSystems，2011，sets6（2）：166-17112印峰，王耀南，劉煒，等個體速度差異的蟻群算法設(shè)計J智能系統(tǒng)學(xué)報，2009，4（6）：528-533及仿真YINFeng，WANGYaonan，LIUWei，etalDesignandsimulationofanant

24、colonyalgorithmbasedonindividualCAAITransactionsonIntelligentvelocitydifferencesJSystems，2009，4（6）：528-53313趙百軼，張利軍，賈鶴鳴基于四叉樹和改進(jìn)蟻群算法J應(yīng)用科技，2011，38（10）：23-28的全局路徑規(guī)劃ZHAOBaiyi，ZHANGLijun，JIAHemingGlobalpathplanningbasedonquadtreeandimprovedantcolonyopti-mizationalgorithmJAppliedScienceandTechnology，2011，38（10）：23-28參考文獻(xiàn)：1趙文彬，孫志毅，李虹一種求解TSP問題的相遇蟻群J計算機(jī)工程，2004，30（12）：136-138算法ZHAOWenbin，SUNZhiyi，LIHongAmeetingantcolonyopti