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

賀盼博 鄔春學(xué)

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

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

DOI：10.11907/rjdk.181308

中圖分類號：TP319

文獻標(biāo)識碼：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引言

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

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

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

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

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

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

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

1模型建立與分析

1.1算法基本規(guī)則

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

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

1.2模型優(yōu)化

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

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

1.3遺傳算子

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

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

1.4選擇

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

1.5交叉

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

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

1.6突變

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

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

2模型仿真與分析

2.1模型驗證

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

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

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

2.2模型應(yīng)用

為了更直觀地表示結(jié)果，本文使用XAML和c#編程[14-15]。就表面編程而言，它通?？稍诔绦虻臉I(yè)務(wù)層之間加以區(qū)分，該層實現(xiàn)用于后處理結(jié)果的計算邏輯和負責(zé)應(yīng)用程序外觀的圖形層。業(yè)務(wù)層和圖形層的一部分用C#編寫，而XAML明確用于圖形問題和窗口的整體外觀。

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

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

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

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

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

3結(jié)語

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

參考文獻：

[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]張應(yīng)輝，劉養(yǎng)碩.基于幀差法和背景差法的運動目標(biāo)檢測[J].計算機技術(shù)與發(fā)展，2017，27（2）：25-28.

（責(zé)任編輯：杜能鋼）