基于多約束條件的改進遺傳算法路徑規劃

賀盼博 鄔春學

摘要：變電站位置確定是一個典型的最短路徑問題，在實際處理中需要考慮功率、負載、損耗等多個因素。將不同元啟發式算法和搜索方法中的元素進行混合，提出一種基于多約束條件的改進遺傳算法，用于解決上述路徑規劃問題。使用相同例子對不同算法進行模擬仿真，得出蟻群成本平均為15.1024s，代數為21，適應值為0.0079134753。改進的遺傳成本為19.2347s，代數為38，適應值為0.014756211。模擬退火成本為36.4933s，代數為47，適應值為0.0174145624。標準遺傳成本34.2537s，代數為68，適應值為0.0195278781。以上數據證明改進的遺傳算法在搜索效率、收斂速度和最終結果上具有一定優勢。

關鍵詞：變電站位置；多約束條件；改進遺傳算法

DOI：10.11907/rjdk.181308

中圖分類號：TP319

文獻標識碼：A文章編號：1672-7800（2018）007-0180-04

Abstract：Substationlocationdeterminationisatypicalshortestpathproblem.Inpath-designing，itshouldconsideradditionalinformationsuchasshortcircuitcurrentsorpowers，generationandloaddata，inertia，gridlossesandsoon.Inordertosolvethiscomplexmulti-objectivecombinatorialoptimizationproblem，thispapermixesthedifferentMetaheuristicswiththeelementsinthesearchmethod，proposesanimprovedgeneticalgorithmbasedonmulti-constraintconditions，andusesthesameexamplefordifferentalgorithms.Simulationsimulationsshowthattheaverageantcolonycostis15.1024secondsandthealgebrais21，andtheadaptationvalueis0.0079134753.Theimprovedgeneticcostwas19.2347seconds，thealgebrawas38，andthefitnessvaluewas0.014756211.Thesimulatedannealingcostwas36.4933secondsandthealgebrawas47.Thefitnessvaluewas0.0174145624.Thestandardgeneticcostwas34.2537seconds，thealgebrawas68，andthefitnessvaluewas0.0195278781.Theexperimentalresultsshowthattheimprovedgeneticalgorithmhassomeadvantagesinthemulti-constraintcondition，thesearchefficiencyandtheconvergencespeed.

KeyWords：positionofsubstations，multipleconstraints，improvegeneticalgorithm，routeplan

0引言

在確定變電站位置的路徑規劃中，有一個無法避免的現實問題，那即電線、路線、城市這三者之間的關系。理想狀態下，電線數量應少于實際路線數量，實際路線數量少于需要供給的城市數量。許多研究人員試圖解決這個問題，將節省開支作為出發點，尋找解決和提高運輸效率的最佳路徑規劃。

遺傳算法是一種具有良好全局搜索能力和多目標隱式并行計算特點的啟發式搜索方法。大部分優化算法都是單點搜索算法，很容易陷入局部最優解。但遺傳算法是一種多點搜索算法，更有可能搜索全局，獲得全局最優解。在整個搜索過程中，遺傳算法不同于貪婪算法，在使用沖擊搜索計算時不依賴于問題的梯度，但標準遺傳算法有其固有缺陷，如早熟收斂、本地搜索能力較差等。因此，在實際應用中需要對其進行優化。

王竺[1]首先提出了基于二叉樹的智能生成路由算法，彌補了路由形成缺陷，提高了路由規劃質量，但關于二叉樹旁路障礙處理方案并不完善，且計算效率太低。

王穎、劉維廷[2]提出了一種基于改進蟻群算法的路徑規劃方法，但改進的人工繪制路線耗時太多，而且不夠準確，導致應用范圍受限。蟻群算法的計算量過大，數據需要大量成本支持，容易出現停滯現象。

鄒春明、趙俊超[3]提出了一種基于懲罰PSO方法處理多約束群橋梁水域的航線規劃方法。對于簡單抽象如圓柱縱向等間隔的障礙物，可以很快解決簡單航線規劃問題。但當進入多維函數的極值時，其沖突特性和障礙路徑平滑的要求，會導致很容易出現局部最優解或搜索停滯現象。

Bandyopadhyay[4]提出了基于多重優化的模擬退火算法，但在處理這個問題的步驟精度方面有缺陷：劃分太粗糙找不到最優解，劃分太細又導致計算量過大。

本文認為遺傳算法非常適用于研究路徑規劃問題，它能解決許多復雜問題。本文對遺傳算法進行優化改進，以實現變電站位置分布的路徑規劃方案。目標是：①減少所有路徑的耗時和距離；②降低運輸成本；③以界面顯示更多細節，幫助用戶了解更多細節信息。

1模型建立與分析

1.1算法基本規則

啟發式算法的核心思想是根據一定的規則隨機構造候選解空間，并通過連續迭代和比較直到找到全局最優解。在每次迭代過程中，元啟發式算法都以一定概率接受次優解，從而避免了局部最優解。

元啟發式算法是啟發式算法的改進，是隨機算法和局部搜索算法的產物。它基于直覺或經驗，以可接受的成本（計算時間和空間）給出問題的可行解，步驟如下：①從一個或多個候選解作為初始值開始（pop（t））；②從初始值計算目標函數值；③根據獲得的信息，通過個體變異、組合等方法不斷更新候選解域；④將新的候選解決方案代入下一次迭代（pop（t+1））。算法基本規則見圖1。

1.2模型優化

文獻[5]指出路線規劃問題最重要的是選擇合適的算法。遺傳算法是一種具有良好的全局搜索能力和多目標隱式并行計算特點的啟發式搜索方法，但存在早熟收斂、局部搜索能力差等缺陷。鑒于這些問題，本文試圖作如下改進：①使用掃描搜索方法修改初始階段；②為了避免好的基因組中斷，評估單個基因；③改進突變操作，增強局部搜索能力。

屬于染色體的每個個體都包含表示路徑經過的節點ID的正整數序列。染色體的每條路線都是可變的，每個基因代表一條路徑，后面跟著路徑點編碼順序。

1.3遺傳算子

算子是隨機創建的。由每個點確定數量，每個染色體代表一個有效路線，可以用一組數字表示，每個數字代表一個基因。數字足以編碼染色體，因為在問題中只有一個變量是站點之間的距離。群體初始化為默認數量，初始路徑代表第一條染色體。

然后計算適應度，將染色體表示為最佳染色體。精煉3000個循環以計算總體，其中每個迭代包含交叉和樹的突變。

1.4選擇

強選擇因子具有一定的局限性，它可能導致附近解的理想狀態僅選擇最適合雜交的染色體，從而迫使GA搜索過早結束。同樣，弱選擇因子也有自身的局限。如果選擇因子較弱，選擇范圍很有可能影響混合交叉的適應性，從而影響GA對求解空間的判斷[7-8]。綜合考慮，本文采用傳統輪盤的無盤選擇方式，將其用于染色體選擇，選出評估值最高的染色體，將它對應的適應值升高，用于新的染色體形成和變異，這有助于子集的復制和繁殖，擴大了新一代子集樣本。

1.5交叉

算法中使用雜合交叉，其中用來產生隨機向量的載體來自初代父母基因，并且選擇二代親本中評估因子為0的基因為載體，將兩者鏈接在一起產生子代[9-10]。

例如D1、D2是親本，其中D1=[abcdefgh]，D2=[12345678]，平衡因子為[10101001]，產生的子代為child1=[a2c4e67h]。

1.6突變

突變過程發生在交叉過程之后，將后代釋放到空間中。突變的概率稱為突變率，通過搜索空間的隨機漫游，突變率會大大提高，更有利于尋找到最適合變化的染色體[11]。適應性突變，再加上隨機生成最后有效或者無效的子代，使適用的區域選擇可能性相對平等。沿著每一個路徑進行挑選，這樣可最大限度地保證直接限制范圍的公正性。

突變將會在每個循環中重復3次，確保最終的目標是從第一代染色體產生的子代。盡最大可能找到期待結果，然后通過測試兩個站之間的路線確定最后的染色體。在任何兩個基因（點）之間沒有直接路線的情況下，所產生的新染色體是無效的。如果新染色體好，則計算適應度函數[12-13]。如果適應度函數值優于好的染色體，則新染色體為最優，循環結束，如圖2所示。

2模型仿真與分析

2.1模型驗證

使用蟻群算法模擬退火和標準遺傳算法計算相同例子進行測試，表1和圖3顯示最終答案。

表1和圖3顯示了幾種算法的明顯不同之處，蟻群成本平均為15.1024s，代數為21，適應值為0.0079134753。改進的遺傳成本為19.2347s，代數為38，適應值為0.0147562111。模擬退火成本為36.4933s，代數為47，適應值為0.0174145624。標準遺傳成本34.2537s，代數為68，適應值為0.0195278781。

通過表1和圖3的比較，證明改進的遺傳算法在搜索效率、收斂速度和最終結果上具有一定優勢。

2.2模型應用

為了更直觀地表示結果，本文使用XAML和c#編程[14-15]。就表面編程而言，它通常可在程序的業務層之間加以區分，該層實現用于后處理結果的計算邏輯和負責應用程序外觀的圖形層。業務層和圖形層的一部分用C#編寫，而XAML明確用于圖形問題和窗口的整體外觀。

由于約束和數據非常大，必須對它們進行分類，并保存在不同的文件中，見圖4。

模型適用于變電站之間的路徑規劃，就圖解而言，線路的起點和終點必須重新計算，因為必須在變電站處增加一個額外的“線路適配器”。變電站之間的不同約束以不同顏色表示，見圖5。

最終結果見圖6，不僅可以看到優化路線，還可直觀顯示其它約束條件。

使用改進算法進行路線規劃，不僅鏈接到每個站點，而且清楚地顯示了用戶需要的限制。將計算數據與公司數據庫進行比較，結果見表2。

實驗結果接近實際，表明本文方法具有一定的參考價值。

3結語

改進優化的遺傳算法，對多約束路徑規劃問題很實用，減少了先前的先驗經驗缺陷，提高了算法收斂速度，提高了搜索效率。改進遺傳算法消除了搜索初始最優解時浪費的時間，工作流程可描述為一個組合、分割和遺傳操作過程。由于精度和效率的不同需求，組合和分割的次數可以多次，具有一定的實用性。

參考文獻：

[1]LIUJL，HANX.Discussionongeneticalgorithmtechnology[J].IntelligentComputerandApplications，2009（5）：142-143.

[2]WANGY，LIUWT.Pathplanningofshipsbasedonimpprovedantcolonyalgorithm[J].ModernElectronicsTechnique，2010（21）：186-188.

[3]ZOUCM，ZHAOJC，YANGK.Routeplanninginmulti-bridgewaterareaundermulticonstrainsbasedonpenalty-PSO[J].Navigationofchina，2016（2）：67-70.

[4]BANDYOPADHYAYS，SAHAS，MAULIKU，etal.Asimulatedsnnealing-basedmultiobjectiveoptimizationalgorithm：AMOSA[EB/OL].http：//www.doc88.com/p-6921568900573.html

[5]EvolutionaryComputation，IEEETransactionson[EB/OL].http：//blog.sciencenet.cn/home.php？do=blog&id;=1111172&mod;=space&uid;=2374

[6]WANGZ，LISJ，ZHANGLH，etal.Amethodforautomaticroutingbasedonroutebinarytree[J].GeomaticsandInformationScienceofWuhanUniversity，2010（4）：407-410.

[7]MOHAMMEDMA，AHMADMS，MOSTAFASA.Usinggeneticalgorithminimplementingcapacitatedvehicleroutingproblem[J].InternationalConferenceonIEEEComputer&InformationScience;，2012，1（6）：257-262.

[8]MIRANDADM，CONCEICSV.Thevehicleroutingproblemwithhardtimewindowsandstochastictravelandservicetime[J].ExpertSystemApplication，2016（64）：104-116.

[9]ABDULAMEERM，MALAYSIAUT，SURYANAN，etal.Convertdatabasestructureintostarschemastructurefordatawarehouse[EB/OL].http：//www.doc88.com/p-6651592362232.html.

[10]PIERREDM，ZAKARIAN.Partiallyoptimizedcyclicshiftcrossoverformulti-objectivegeneticalgorithmsforthemulti-objectivevehicleroutingproblemwithtime-windows[C].IEEESymposiumonComputationalIntelligenceinMulti-CriteriaDecision-Making，2014：106-115.

[11]JABERMM，GHANIMKA，SuryanaN，etal.Flexibledatawarehouseparameters：towardbuildinganintegratedarchitecture[J].InternationalJournalofComputerTheoryandEngineering，2015，7（5）：349-350.

[12]MAHMOUDIM，ZHOUX.Findingoptimalsolutionsforvehicleroutingproblemwithpickupanddeliveryserviceswithtimewindows：adynamicprogrammingapproachbasedonstate-space-timenetworkrepresentations[J].TransportationResearchPartB，2016（89）：19-42.

[13]ARUNKUMARN，RAMKUMARK，VENKATARAMANV.Automaticdetectionofepilepticseizuresusingnewentropymeasures[J].JournalofMedicalImagingandHealthInformatics，2016，6（3）：724-730.

[14]ARUNKUMARN，RAMKUMARK，VENKATARAMANV.Automaticdetectionofepilepticseizuresusingpermutationentropy，tsallisentropyandkolmogorovcomplexity[J].JournalofMedicalImagingandHealthInformatics，2016，6（2）：526-531.

[15]張應輝，劉養碩.基于幀差法和背景差法的運動目標檢測[J].計算機技術與發展，2017，27（2）：25-28.

（責任編輯：杜能鋼）