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

《进化计算算法在路径优化中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、进化计算算法在路径优化中的应用　　笔者主要想要研究优化领域中和路径优化相关的问题。在研究路径优化问题时，主要运用的优化算法是遗传算法。该算法在进化计算中，是应用范围最广的，和其他的算法相比，遗传算法更有优势。笔者针对遗传算法存在的问题对遗传算法进行了修改，提出了一些优化遗传算法的建议，并在实际运用中证明了通过优化，遗传算法可以更好的解决优化路径问题。　　【关键词】路径优化遗传算法问题　　1遗传算法　　1.1遗传算法的基本思想　　遗传算法是在上世纪70年代被提出来的。遗传算法是从达尔文的遗传定律受到的启迪，达尔文遗传定律包括自然选择，主要是对生物进行筛选，和适者生存主

2、要是来完成生物的进化。这也是遗传算法所运用的原理，最开始遗传算法是为了解释自然界中生物为了适应环境，而不断进化的复杂过程。后来仿照生物进化的过程，将遗传算法引入了优化算法中。该算法主要是为了服务于优化计算。一个问题的解决方法很多，需要优化选择最优解的时候，遗传算法将这个问题的原始状态看作是一个种群，其中的每一种状态都将编码为染色体。初始群体会在条件的约束下，不断进化，最终得出最优解，从而产生新的种群。从最后一个种群中找出最优解，解码成问题的最优路径，就是遗传算法在实践中的运用。　　1.2遗传算法的步骤　　遗传算法利用自然法则中进化的过程创建模型，其具体的计算方法如下

3、：　　（1）将原始数据构造成染色体。最终构成的染色体需要满足问题的约束条件。遗传算法对直接解决具体问题是不管用的，而是要先将和问题相关的实例编码成染色体的形式。在求最优解的过程中，可以有数种不同的编码方式，但原则是必须符合约束条件，否则会影响计算的准确性。　　（2）在选择初始染色体的时候，应该秉承随机的原则。原始种群代表的是进化初始阶段的种群，初始群体要有多少?盗浚?要根据实际情况来定。　　（3）每个染色体在不停进化的时候，优化度都会不断提高。优化度是用来评价染色体好坏的标准，遗传算法的目的，就是要找出染色体中最优的那一个。　　（4）进化的过程，有复制、交叉和变异等

4、形式的运算，进化将产生子群体。其中主要运用了适者生存的自然法则，交叉，复制主要是来自繁殖，而变异则代表着基因突变。　　（5）若达到了终止条件，则将结果输出。得到最优解。　　2进化计算　　2.1计算的概念　　计算实质上是一种物理过程，在自然界的方方面面都存在着计算，无论是花的形状，还是天然晶体的结构，当然也包括生物的进化过程，社会的发展，宇宙的演变等。人们从自然界中获得了很多灵感。　　2.2进化计算　　进化计算也是从达尔文的遗传定律中获得的启发，通过仿照生物进化的过程，设计出来的计算方法。进化计算今年来的发展非常迅速，时常有新的算法出现。因此笔者无法对下一个具体的定义

5、。进化计算目前还是一个比较抽象的概念，进化计算主要可以分为以下几种：遗传算法，进化策略，进化规划等。近几年这些算法都在飞速的发展，并且在众多领域都有运用的实例，成为了进化计算框架中非常重要的部分。　　3进化算法中的遗传算法解决路径优化问题的具体方法　　3.1实验方法　　确定一系列特定的需要访问的位置，从仓库调用一定数量的车辆来访问这些位置。那么怎么选择，才是车辆的最优路径，使车辆可以按照一定的顺序来访问各个位置，不仅能满足特定的约束条件，还能使车辆花费的时间最短，路径最优。　　3.2使用改进的遗传算法来计算最优路径　　笔者提出一种改良后的的遗传算法，将遗传算法中的编

6、码机制改为自然数编码机制，该机制的优点是非常的直观。再利用三复本锦标赛的方法来进化解。经过实验证明了改进后的算法能更好的求解出最优路径。　　3.3具体计算步骤　　3.3.1对染色体进行编码　　采用的新的编码机制使得编码的过程十分直接，对各种规模的问题都可以应对。并且要设立特殊位置，作为基因位。而访问特定位置的顺序就是所需要求的解（要包括不可行解）。每个基因位都有其需要满足的约束条件。如位置地点、需要到达的时间等。例如，若问题的解路线为：　　1：0→2→6→5→0　　路线　　2：0→8→3→7→1→0　　找最优解的时候，先将车辆要经过的位置的头和尾连接在一起，这样可以

7、将染色体编码成256173849。这样做的缺点是缺少路线分界点，但是之后要交叉操作的时候会更加方便。只要在解码最优解的时候，按照顺序将节点插入到路线中去，就可以解决了。如果有的点时间满足不了，或是其他约束条件满足不了，就可以新增一条路径从插入点插入。根据进化的的思想，路线最优的时候，就会使访问的总费用和时间降低，因此进化过程中将尽量的往原有的路线中插入位置点。　　3.4实验结论　　通过改良的遗传算法，可以解决企业、邮政快递、高速公路配货过程中找寻最优路径的问题。其他行业关于最优路径的问题也能得到解决。研究该遗传算法有助于提高相关企业的利润、企业也能为顾客提高更好