蟻群優(yōu)化電纜敷設(shè)系統(tǒng)的研究.pdf

1、電纜敷設(shè)系統(tǒng)的核心是計(jì)算電纜路徑的算法。本文對(duì)電纜敷設(shè)系統(tǒng)的路徑敷設(shè)特點(diǎn)進(jìn)行研究，并對(duì)其進(jìn)行了數(shù)學(xué)建模。電纜敷設(shè)中電纜的布局是若干相互獨(dú)立但又相關(guān)的樹的集合，化整為零后的每一條路徑敷設(shè)是一個(gè)三維空間度約束下的曼哈頓距離Steiner最小生成樹問題。它可以分解為水平面上度約束下的曼哈頓距離Steiner樹與垂直高兩部分。而解決水平面上度約束下的曼哈頓距離Steiner樹的重點(diǎn)在于確定輔助點(diǎn)數(shù)目和位置與度約束的處理兩方面。此問題屬于無法用精

2、確算法求解的NP難題。傳統(tǒng)的方法受瓶頸限制，計(jì)算量很大，而且傳統(tǒng)算法一般只能解決兩個(gè)設(shè)備之間的最短曼哈頓距離，須要引進(jìn)一種智能算法來優(yōu)化改進(jìn)系統(tǒng)性能。鑒于自然界中蟻群的搜索路徑呈樹狀，與電纜敷設(shè)中電纜的布局相符合；同時(shí)，蟻群算法是一種離散優(yōu)化算法，是適合用來在圖中尋找優(yōu)化路徑的機(jī)率型算法，這些都與電纜敷設(shè)的路徑尋優(yōu)相稱，且可以解決三維空間度約束下兩個(gè)及兩個(gè)以上設(shè)備曼哈頓距離Steiner最小生成樹問題，與傳統(tǒng)算法相比，蟻群算法更具優(yōu)勢(shì)。