车辆路径问题的混合遗传粒子群算法.doc

《车辆路径问题的混合遗传粒子群算法.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、....车辆路径问题的混合遗传—粒子群算法——HFUT论文翻译作业摘要：通常的遗传算法，具体的解并不在他们的生命周期内进化：它们被创建，评估，可能被选作为新解决方案的父代，然后被销毁。然而对Memetic算法和基因局部搜索的研究表明，如果解能够被允许在其生命周期内进行演化，性能可能会提高。我们建议，解的提高可以通过对父代解的知识存储来获取帮助，以有效地让父代教他们的后代如何改善适应性。本文中，具体解通过应用粒子群算法来进化，即每个解都要按照PSO的基本原则进行物理运动，直到被要求去作为一个父代。因此，每个父代的知识，特别是一个非常适合父代，就有可能被转移到其后

2、代以及整个群体的子代中去，通过这种方式提出的算法有可能更有效的搜索解空间。这种想法被应用到一个经典的组合优化问题，即车辆路径问题，当应用于两个经典的基准实例集合时具有很好的效果。1.简介在过去的十几年中，由于先进的信息系统设计智能范例利用，自然启发智力变得越来越流行。其中最流行的自然启发方法是对动物和微生物的团队行为的表示，如群智能（鸟群或鱼群启发粒子群优化）、人工免疫系统、蜂群的性能优化、蚁群等等。但自然启发方法最流行的是遗传算法，它的应用十分广泛，在遗传算法和更普遍的进化计算的背景下，也实现了许多新的思想。通常的遗传算法，我们有一些离散的阶段，即群的初始化

3、，父代的选择，交叉算子，变异算子和每一代的更换。但两代之间又发生什么呢？如果我们想有一个完整的进化算法，我们将要观察每个个体在其生命周期内的行为。在父代试图帮助他们的子女来学习和发展，而使其变得更具有竞争性，并有更多的可能性生存，来成为下一代的父代。有许多不同的方法可以用来完成一个进化算法，一种方法是独立的观察每个个体，个体间无任何交流与影响。在遗传算法的情况下，其实现是使用单一或更复杂的局部搜索策略。另一种方法是让个体之间有一个相互作用。在本文中，这种互动利用粒子群优化算法来实现。在每一代中，所有的个体（父代和子女）被视为一个单一的群体，他们通过向群的最优部

4、分运动来努力提高自己的解决方案（即后代学习他们的父代）。因此，在本文中我们着重于每个个体如何利用粒子群来进化。在每次的粒子群优化阶段结束时，整个群适者生存，并转移到下一阶段的遗传算法，即遗传算法的父代选择阶段。在算法的进化部分应用PSO算法的优势是，与其他超启发式算法相比，对于群体中的每个个体只有两种变量在迭代中需要计算，即位置和速度。经常用Memetic算法（带有局部搜索阶段的遗传算法）来代替典型的遗传算法使用的原因是，纯粹的遗传算法很难有效的探索解空间。全局优化算法与局部优化算法的结合往往能够提高算法的性能。在本文中，我们用了一个全局搜索算法即PSO代替局

5、部搜索算法来分别改进每个个体。因此每个个体并不通过自身来改善解，而是利用整个群体的解的知识。我们的另一个目标是在较短的计算时间内得到进可能好的结果。这个目标使我们使用两个不同的程序，一是加速技术（扩张邻域搜索-ENS），另一个用于产生尽可能好的初始解（MPNS-GRASP）。因此，遗传算法和一个非常快的局部搜索策略的PSO算法相结合，如扩大邻域搜索策略（[Marinakis等，2005]和[Marinakis等，2005年），将产生非常快速和有效的算法，并将减少解决大规模的车辆路径算法的计算时间，以及更多的困难的组合优化问题。本文下面的组织结构为：下一节将具体

6、描述车辆路径问题，第三部分中，算法hybridgenetic–PSO–GRASP–ENS(HybGENPSO)被提出并详细描述。实验结果将在第四部分展示和分析，最后一部分得出结论以及对未来的展望。w...v....2.车辆路径问题VRP和CVRP问题经常被描述为，车辆基于中心仓库，要求到达地理位置不同客户以满足客户的需求。令G=(V,E)表示一个图，其中V={i1,i2,…in}表示定点集合，(i1代表仓库客户位置表示为i2,…,in)，E={(il,im):il,imV}表示边的集合。每个客户必须被分配一个确切的车辆，每辆车分配的载量不能超过其容量（Qk），

7、如果每辆车都是同质的则容量相等记为Q。需求ql以及服务时间stl分配给每个客户节点il。仓库节点的需求量q1和服务时间st1设置为0，il和im之间的运输费用记为Clm。Tk表示车辆k被允许的路线上的最大时间。该问题是建立一个低成本的，对每一辆车都可行的路线。一条路线是一个地点的序列，车辆必须根据它提供的服务来访问路线，如果边(il,im)被车辆k经过则置变量为1，否则为0。车辆必须在仓库处结束其行程。下面我们用数学公式来描述VRP问题。目标函数（1）指出，总距离要尽量减少。等式（2）和（3）确保每个有需求的节点会得到一个车辆的服务。（4）表示路线的连续性，即

8、一辆车进入需求节点后必须从该节点出来。