单亲遗传算法的改进及用于城市垃圾回收路线优化

杨帆

摘 要：改进垃圾收集转运方式能够有效地提高垃圾转运效率，文章对现有的单亲遗传算法进行改进，提出了择优插入、精英保留等策略。改进后的算法可以进一步优化垃圾收运路线，提高收运效率，并将其运用到实际的垃圾收运路线优化中。

关键词：单亲遗传算法；垃圾回收路线优化；改进

中图分类号：R124.3 文献标志码：A 文章编号：2095-2945（2017）23-0077-02

1 概述

据《中国统计年鉴》（2014年），中国共有建制城市657个，城市生活垃圾清运量已经达到17860.2万吨[1]。制定合理的垃圾收运方案，及时清运垃圾，可以减少垃圾回收清运费用，并减少对环境的污染。

从目标函数和建模思路来看，城市垃圾收运路线的优化问题为车辆调度问题，属于组合优化问题。其实质是对一系列装货点和（或）卸货点，组织适当的行车线路，使车辆有序地通过它们，在满足一定的约束条件，如车辆容量、行驶里程、时间等限制因素，达到一定的目标如路程最短、费用最少、使用车辆数量尽量少等。

王文梅[2]提出利用单亲遗传算法对垃圾回收路线进行优化，本文针对这一算法进行了改进，很大程度上避免了传统遗传算法存在的“早熟收敛”等问题。本算法从传统物流路线优化方面得到启发，并通过java语言编译，形成一套新的“垃圾回收路线优化算法”。

2 单亲遗传算法的优化

遗传算法（Genetic Algorithm，GA）是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法[3]，即适者生存、优胜劣汰的遗传机制。目前的基本遗传算法是由Goldberg统一了各种编码方式和遗传算子[4]，只使用了选择、交叉、变异三种基本遗传算子构成完备的算子集合，其遗传过程简单，容易理解，是其他遗传算法的基础，不仅给各种遗传算法提供了一个基本框架，同时也具有很高的应用价值。

本文对单亲遗传算法进行了以下改进：

（1）“择优插入法”产生初始群体

初始群体染色体的好坏对于整个群体的进化效率有很大的影响。本算法在产生初始群体的时候，采用“择优插入法”，提高收敛效率。

（2）选择精英保留策略

在选择操作中加入精英保留策略，即在使用变异、交叉算子之前先选出适应度值最大的个体保存在最优解中。在本算法的每个群体的第一个位置为“精英保留区”，每次进行遗传操作时，如果得到的个体适应度值比“精英保留区”中的个体的适应度大的时候，就复制该个体到“精英保留区”中，这样每一代出现的最优个体都会被保留。

（3）遗传迭代终止规则

若连续Q代内都满足条件| fgmax-f（g-1）max|≤ε，其中 ε为适当小的正数，fgmax为第g代种群内个体的最大适应度值，f（g-1）max为第g-1代种群内个体的最大适应度值。一般进化结果趋于平稳时，则可以认为是一个最优解。所以本算法为了减少运行时间，增大开发效率，优化了停机规则。

3 实验结果验证及分析

本文算法倒位变异概率为0.75，变异概率为0.02。程序用java编写。

与其他文献中的结果对比：

按文献[5]可将问题描述为：在某市有12个垃圾收集点，1个垃圾集中处置点，收集点的垃圾量、各个收集点之间的距离（单位：公里）如表1所示。这些收集点由垃圾处置点处的载重量为8吨的垃圾收集车收集，要求合理完成安排车辆的行车路线，使得行程最短。

文献[5]中使用的是单亲遗传算法的多点换位算子，选择算子使用的是保留最佳个体方法；文献[3]中使用的是带“放哨”的遗传算法。表2显示了当进化100代时文献[5]中的单亲遗传算法、保留最佳个体的基因移位变异算法、保留最佳个体的基因倒位算法和文献[3]中的算法，以及本优化算法之间的比较。

本文算法從三个方面对单亲遗传算法进行了改进，取得了较好的结果，达到了缩短运输距离及高效节能的目标。

4 结论

本文将传统的单亲遗传算法进行了优化，主要从初始种群的创建、精英保留策略和遗传迭代终止规则进行了优化，并与参考文献的结果进行了比较，验证了本算法的可行性。本文算法存在的不足是没有考虑到存在多个处置点的情况，没有考虑车辆不同载重量的情况，没有将油耗情况结合起来，只是考虑路径长短的问题。

参考文献：

[1]中华人民共和国国际统计局.中国统计年鉴2015年[M].北京：中国统计出版社，2015.

[2]王文梅.基于单亲遗传算法的城市垃圾收运路线优化的研究[D].西南交通大学，2005.

[3]晏梦君.遗传算法在派送路线优化系统中的应用[D].吉林大学，2005.

[4]张超群，郑建国，钱洁.遗传算法编码方式比较[J].计算机应用研究，2011（3）：819-822.

[5]李茂军，朱陶业，童调生.单亲遗传算法与传统遗传算法的比较[J].系统工程，2001，19（1）：61-65.endprint