进化计算算法在路径优化中的应用

段嘉腾

笔者主要想要研究优化领域中和路径优化相关的问题。在研究路径优化问题时，主要运用的优化算法是遗传算法。该算法在进化计算中，是应用范围最广的，和其他的算法相比，遗传算法更有优势。笔者针对遗传算法存在的问题对遗传算法进行了修改，提出了一些优化遗传算法的建议，并在实际运用中证明了通过优化，遗传算法可以更好的解决优化路径问题。

【关键词】路径优化 遗传算法 问题

1 遗传算法

1.1 遗传算法的基本思想

遗传算法是在上世纪70年代被提出来的。遗传算法是从达尔文的遗传定律受到的启迪，达尔文遗传定律包括自然选择，主要是对生物进行筛选，和适者生存主要是来完成生物的进化。这也是遗传算法所运用的原理，最开始遗传算法是为了解释自然界中生物为了适应环境，而不断进化的复杂过程。后来仿照生物进化的过程，将遗传算法引入了优化算法中。该算法主要是为了服务于优化计算。一个问题的解决方法很多，需要优化选择最优解的时候，遗传算法将这个问题的原始状态看作是一个种群，其中的每一种状态都将编码为染色体。初始群体会在条件的约束下，不断进化，最终得出最优解，从而产生新的种群。从最后一个种群中找出最优解，解码成问题的最优路径，就是遗传算法在实践中的运用。

1.2 遗传算法的步骤

遗传算法利用自然法则中进化的过程创建模型，其具体的计算方法如下：

（1）将原始数据构造成染色体。最终构成的染色体需要满足问题的约束条件。遗传算法对直接解决具体问题是不管用的，而是要先将和问题相关的实例编码成染色体的形式。在求最优解的过程中，可以有数种不同的编码方式，但原则是必须符合约束条件，否则会影响计算的准确性。

（2）在选择初始染色体的时候，应该秉承随机的原则。原始种群代表的是进化初始阶段的种群，初始群体要有多少數量，要根据实际情况来定。

（3）每个染色体在不停进化的时候，优化度都会不断提高。优化度是用来评价染色体好坏的标准，遗传算法的目的，就是要找出染色体中最优的那一个。

（4）进化的过程，有复制、交叉和变异等形式的运算，进化将产生子群体。其中主要运用了适者生存的自然法则，交叉，复制主要是来自繁殖，而变异则代表着基因突变。

（5）若达到了终止条件，则将结果输出。得到最优解。

2 进化计算

2.1 计算的概念

计算实质上是一种物理过程，在自然界的方方面面都存在着计算，无论是花的形状，还是天然晶体的结构，当然也包括生物的进化过程，社会的发展，宇宙的演变等。人们从自然界中获得了很多灵感。

2.2 进化计算

进化计算也是从达尔文的遗传定律中获得的启发，通过仿照生物进化的过程，设计出来的计算方法。进化计算今年来的发展非常迅速，时常有新的算法出现。因此笔者无法对下一个具体的定义。进化计算目前还是一个比较抽象的概念，进化计算主要可以分为以下几种：遗传算法，进化策略， 进化规划等。近几年这些算法都在飞速的发展，并且在众多领域都有运用的实例，成为了进化计算框架中非常重要的部分。

3 进化算法中的遗传算法解决路径优化问题的具体方法

3.1 实验方法

确定一系列特定的需要访问的位置，从仓库调用一定数量的车辆来访问这些位置。那么怎么选择，才是车辆的最优路径，使车辆可以按照一定的顺序来访问各个位置，不仅能满足特定的约束条件，还能使车辆花费的时间最短，路径最优。

3.2 使用改进的遗传算法来计算最优路径

笔者提出一种改良后的的遗传算法，将遗传算法中的编码机制改为自然数编码机制，该机制的优点是非常的直观。再利用三复本锦标赛的方法来进化解。经过实验证明了改进后的算法能更好的求解出最优路径。

3.3 具体计算步骤

3.3.1 对染色体进行编码

采用的新的编码机制使得编码的过程十分直接，对各种规模的问题都可以应对。并且要设立特殊位置，作为基因位。而访问特定位置的顺序就是所需要求的解（要包括不可行解）。每个基因位都有其需要满足的约束条件。如位置地点、需要到达的时间等。例如，若问题的解路线为：

1：0→2→6→5→0

路线

2：0→8→3→7→1→0

找最优解的时候，先将车辆要经过的位置的头和尾连接在一起，这样可以将染色体编码成256173849。这样做的缺点是缺少路线分界点，但是之后要交叉操作的时候会更加方便。只要在解码最优解的时候，按照顺序将节点插入到路线中去，就可以解决了。如果有的点时间满足不了，或是其他约束条件满足不了，就可以新增一条路径从插入点插入。根据进化的的思想，路线最优的时候，就会使访问的总费用和时间降低，因此进化过程中将尽量的往原有的路线中插入位置点。

3.4 实验结论

通过改良的遗传算法，可以解决企业、邮政快递、高速公路配货过程中找寻最优路径的问题。其他行业关于最优路径的问题也能得到解决。研究该遗传算法有助于提高相关企业的利润、企业也能为顾客提高更好的服务，人们的需求也能得到最大程度得到满足。因此该算法的推广和运用是非常有意义的。

4 总结

笔者提出了优化路径的优化算法，并通过实验。对改良的遗传算法的作用进行了验证。最终实验结果证明了该算法是十分有效的。

参考文献

[1]黄岚，王康平，周春光，原媛，庞巍.基于蚂蚁算法的混合方法求解旅行商问题[J].吉林大学学报（理学版），2012（04）.

[2]王凌著.智能优化算法及其应用[M].北京：清华大学出版社，2016.

[3]彭新娟基于进化计算的最大相似双聚类分析及其应用[D].长沙：湖南大学，2013.

作者单位

广州现代信息工程职业技术学院 广东省广州市 510663