发布时间 : 星期四 文章进化计算算法在路径优化中的应用更新完毕开始阅读59ea715df02d2af90242a8956bec0975f465a439
进化计算算法在路径优化中的应用
笔者主要想要研究优化领域中和路径优化相关的问题。在研究路径优化问题时，主要运用的优化算法是遗传算法。该算法在进化计算中，是应用范围最广的，和其他的算法相比，遗传算法更有优势。笔者针对遗传算法存在的问题对遗传算法进行了修改，提出了一些优化遗传算法的建议，并在实际运用中证明了通过优化，遗传算法可以更好的解决优化路径问题。
【关键词】路径优化 遗传算法 问题 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。这样做的缺点是缺少路线分界点，但是之后要交叉操作的时候会更加方便。只要在解码最优解的时候，按照顺序将节点插入到路线中去，就可以解决了。如果有的点时间满足不了，或是其他约束条件满足不了，就可以新增一条路径从插入点插入。根据进化的的思想，路线最优的时候，就会使访问的总费用和时间降低，因此进化过程中将尽量的往原有的路线中插入位