基于多约束条件的改进遗传算法路径规划

贺盼博 邬春学

摘要：变电站位置确定是一个典型的最短路径问题，在实际处理中需要考虑功率、负载、损耗等多个因素。将不同元启发式算法和搜索方法中的元素进行混合，提出一种基于多约束条件的改进遗传算法，用于解决上述路径规划问题。使用相同例子对不同算法进行模拟仿真，得出蚁群成本平均为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.

（责任编辑：杜能钢）