賀盼博 鄔春學

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

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

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引言

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

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

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

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

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

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

本文認為遺傳算法非常適用于研究路徑規(guī)劃問題，它能解決許多復雜問題。本文對遺傳算法進行優(yōu)化改進，以實現(xiàn)變電站位置分布的路徑規(guī)劃方案。目標是：①減少所有路徑的耗時和距離；②降低運輸成本；③以界面顯示更多細節(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））；②從初始值計算目標函數(shù)值；③根據(jù)獲得的信息，通過個體變異、組合等方法不斷更新候選解域；④將新的候選解決方案代入下一次迭代（pop（t+1））。算法基本規(guī)則見圖1。

1.2模型優(yōu)化

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

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

1.3遺傳算子

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

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

1.4選擇

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

1.5交叉

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

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

1.6突變

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

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

2模型仿真與分析

2.1模型驗證

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

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

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

2.2模型應用

為了更直觀地表示結(jié)果，本文使用XAML和c#編程[14-15]。就表面編程而言，它通?？稍诔绦虻臉I(yè)務層之間加以區(qū)分，該層實現(xiàn)用于后處理結(jié)果的計算邏輯和負責應用程序外觀的圖形層。業(yè)務層和圖形層的一部分用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)碩.基于幀差法和背景差法的運動目標檢測[J].計算機技術(shù)與發(fā)展，2017，27（2）：25-28.

（責任編輯：杜能鋼）