《车辆路径问题的混合遗传粒子群算法》由会员分享，可在线阅读，更多相关《车辆路径问题的混合遗传粒子群算法（10页珍藏版）》请在金锄头文库上搜索。
1、车辆路径问题的混合遗传粒子群算法HFUT 论文翻译作业摘要：通常的遗传算法，具体的解并不在他们的生命周期内进化：它们被创建，评估，可能被选作为新解决方案的父代，然后被销毁。然而对Memetic算法和基因局部搜索的研究表明，如果解能够被允许在其生命周期内进行演化，性能可能会提高。我们建议，解的提高可以通过对父代解的知识存储来获取帮助，以有效地让父代教他们的后代如何改善适应性。本文中，具体解通过应用粒子群算法来进化，即每个解都要按照PSO的基本原则进行物理运动，直到被要求去作为一个父代。因此，每个父代的知识，特别是一个非常适合父代，就有可能被转移到其后代以及整个群体的子代中去，通过这种方式提出的算
2、法有可能更有效的搜索解空间。这种想法被应用到一个经典的组合优化问题，即车辆路径问题，当应用于两个经典的基准实例集合时具有很好的效果。1.简介在过去的十几年中，由于先进的信息系统设计智能范例利用，自然启发智力变得越来越流行。其中最流行的自然启发方法是对动物和微生物的团队行为的表示，如群智能（鸟群或鱼群启发粒子群优化）、人工免疫系统、蜂群的性能优化、蚁群等等。但自然启发方法最流行的是遗传算法，它的应用十分广泛，在遗传算法和更普遍的进化计算的背景下，也实现了许多新的思想。通常的遗传算法，我们有一些离散的阶段，即群的初始化，父代的选择，交叉算子，变异算子和每一代的更换。但两代之间又发生什么呢？如果我们
3、想有一个完整的进化算法，我们将要观察每个个体在其生命周期内的行为。在父代试图帮助他们的子女来学习和发展，而使其变得更具有竞争性，并有更多的可能性生存，来成为下一代的父代。有许多不同的方法可以用来完成一个进化算法，一种方法是独立的观察每个个体，个体间无任何交流与影响。在遗传算法的情况下，其实现是使用单一或更复杂的局部搜索策略。另一种方法是让个体之间有一个相互作用。在本文中，这种互动利用粒子群优化算法来实现。在每一代中，所有的个体（父代和子女）被视为一个单一的群体，他们通过向群的最优部分运动来努力提高自己的解决方案（即后代学习他们的父代）。因此，在本文中我们着重于每个个体如何利用粒子群来进化。在每
4、次的粒子群优化阶段结束时，整个群适者生存，并转移到下一阶段的遗传算法，即遗传算法的父代选择阶段。在算法的进化部分应用PSO算法的优势是，与其他超启发式算法相比 ，对于群体中的每个个体只有两种变量在迭代中需要计算，即位置和速度。经常用Memetic算法（带有局部搜索阶段的遗传算法）来代替典型的遗传算法使用的原因是，纯粹的遗传算法很难有效的探索解空间。全局优化算法与局部优化算法的结合往往能够提高算法的性能。在本文中，我们用了一个全局搜索算法即PSO代替局部搜索算法来分别改进每个个体。因此每个个体并不通过自身来改善解，而是利用整个群体的解的知识。我们的另一个目标是在较短的计算时间内得到进可能好的结果
5、。这个目标使我们使用两个不同的程序，一是加速技术（扩张邻域搜索-ENS），另一个用于产生尽可能好的初始解（ MPNS-GRASP）。因此，遗传算法和一个非常快的局部搜索策略的PSO算法相结合，如扩大邻域搜索策略（Marinakis等，2005和Marinakis等，2005年），将产生非常快速和有效的算法，并将减少解决大规模的车辆路径算法的计算时间，以及更多的困难的组合优化问题。本文下面的组织结构为：下一节将具体描述车辆路径问题，第三部分中，算法hybrid genetic PSO GRASP ENS (HybGENPSO)被提出并详细描述。实验结果将在第四部分展示和分析，最后一部分得出结论以
6、及对未来的展望。2.车辆路径问题VRP和CVRP问题经常被描述为，车辆基于中心仓库，要求到达地理位置不同客户以满足客户的需求。令 G=(V,E) 表示一个图， 其中 V=i1,i2,in 表示定点集合， (i1 代表仓库客户位置表示为 i2,in) ，E=(il,im):il,imV表示边的集合。每个客户必须被分配一个确切的车辆，每辆车分配的载量不能超过其容量（Qk），如果每辆车都是同质的则容量相等记为Q。需求ql以及服务时间stl分配给每个客户节点il。仓库节点的需求量q1和服务时间st1设置为 0，il和im之间的运输费用记为Clm。Tk表示车辆k被允许的路线上的最大时间。该问题是建立一个
7、低成本的，对每一辆车都可行的路线。一条路线是一个地点的序列，车辆必须根据它提供的服务来访问路线，如果边(il,im)被车辆k经过则置变量为1，否则为0。车辆必须在仓库处结束其行程。下面我们用数学公式来描述VRP问题。目标函数（1）指出，总距离要尽量减少。等式（2）和（3）确保每个有需求的节点会得到一个车辆的服务。（4）表示路线的连续性，即一辆车进入需求节点后必须从该节点出来。公式（5）表示车辆的容量约束，式子（6）表示总共的时间约束。式子（7）和（8）保证了车辆的供应能力没被超出。VRP问题首先由丹捷格和拉姆瑟（1959）提出。由于这是一个NP -难问题，提出了大批近似技术。这些技术大体可分为
8、两大类：一是经典启发式算法，主要发展于1960年至1990年，以及最近15年才发展的超启发式算法，该算法可以根据使用的策略不同来分类。禁忌搜索策略是比较常用的技术，很多研究人员提出了很多有效的禁忌搜索算法的变种。一些有趣的高效的算法也被提出，基于自适应记忆的概念，将高质量的VRP解存在里面，并在解得过程中用更好的解来代替它。模拟退火，贪婪随机自适应搜索过程和阈值接收算法也有效地应用于VRP求解。在过去10多年中，自然启发超启发式算法已用于VRP问题的求解过程。最常用的自然启发算法是遗传算法，蚁群优化，蜜蜂交配优化，以及其他进化技术。读者可以很容易从现存的论文书籍中找到对这些算法的详细描述。3.
9、 应用于VRP问题一种混合算法（Hybrid geneticPSOGRASPENS） 3.1 Hybrid geneticPSOGRASPENS（HybGENPSO）的整体描述该算法结合了遗传算法，MPNS-GRASP算法，邻域扩张搜索策略和粒子群优化算法。接下来，将列出算法的提纲。初始化（1）创建初始种群的P个个体，使用的多阶段邻域搜索 - GRASP（MPNS - GRASP）。（2）评价每个个体的适应性。（3）运用粒子群优化策略改善每个个体的适应性。主算法（1）设置generations为0.（2）如果不满足终止条件，继续循环2.1 如果父代仍在选择和交配，继续循环2.1.1 通过轮盘赌
10、的方式从群体中选择两个作为父代2.1.2 对两个父代进行交叉操作，首先将两个父代的共同特征克隆到后代，然后使用ENS的算法完成后代。2.1.3 通过突变操作（扩张邻域搜索）改进后代，并将其结果插入到群体中。2.2 END DO2.3 通过粒子群优化策略，提高新群体中每个个体（父代和后代）的适应性。2.4 根据适应性函数对子代和父代进行排序，然后选择与初始群体数目相等的个体作为新群体。2.5代的数目加一。（3）END DO（4）返回最好的个体3.2 路径表示在为某一问题设计遗传算法时，第一步就是设计合适的候选解的表示。例如Vrp情况下，每个个体（旅行）通过旅行的路径来表示，即通过一个特殊的点序列
11、。有了这种表示，有2n种方式来表示相同的旅行，其取决于哪个节点被放置在位置1和旅行走向哪个方向，其中n是节点数。该算法，与1号节点固定在了每一个人，总是克服代表性位置1，因此，同一旅游多种编码的障碍，克服了很多冗余的解决方案的代表性。在提出的算法中，表示每个个体时，1号节点就被固定于位置1，这样就可以克服相同旅行有多个编码的障碍，克服解表示的冗余。3.3群初始化-MPNS-GRASP通常的遗传算法，随机产生初始化群，其中不能确保包含好的候选解，为防止这种情况，一种贪心随机自适应搜索算法的修改版本，多阶段邻域搜索-GRASP被用于初始化群体。GRASP是一种迭代的两阶段搜索算法。每次迭代由两个阶
12、段构成，构建阶段和局部搜索阶段，在构建阶段中，用一个随机贪心函数来构建一个初始解。该随机技术每次迭代中都产生一个可行的解，该解通过经过局部搜索阶段来提高。最后的结果就是所有迭代过程中最优的解。构建过程可被描述为一个逐步的过程，它一次增加一个元素到一个非完整解。下一个要被加入的元素通过排序所有元素来选择，根据贪心函数，将一个最好的元素放于有限候选列表RCL中，然后从表中随机选择。这个RCL由可能最好的D元素构成。最后RCL每次迭代都通过用不属于RCL中的边替换掉包含在巡回中的边来调整，命名为第（D+m）条边，其中m表示目前迭代的次数。用于解决VRP问题的贪心算法是一个简单的过程。在第二阶段，局部
13、搜索从这些点初始化，最终结果是整个搜索过程的最优解。MPNS-GRASP介绍了应用多目标函数来替代经典方法中的简单贪心函数的灵活性，而且组合贪心算法也是可行的。算法开始于一个贪心算法，如果结果没有改善，则利用一个多目标贪心函数来替代。基于这些贪心函数忽略VRP问题的边约束，可解决一个TSP问题。因此可以通过增加边约束来讲一个TSP问题转化为VRP问题。更精确一点，第一辆车从代表仓库的节点出发，并基于TSP的解来移到下一个节点，检查车辆的容量或最大路线长度是否满足约束。不满足任一约束则车辆返回仓库节点，开始一个新的路线。经典算法的第二阶段，简单局部搜索局受限于获得好解的机会，因此MPNS-GRA
14、SP经常用扩张邻域搜索来代替，这是一种很灵活的局部搜索策略。3.4 适应度函数的计算在VRP中，每个个体初始适应度与每个旅行的路线长度有关。每个个体S的适应值由下式计算：Fitnesss=Jmax-Js+1其中Jmax是群体中最大花费的个体的目标函数值，Js是当前个体的函数值。注意，选择个体去交配的可能性依赖于其适应值，并且花费最高的个体的适应值为0，它永远不会被选择，因此，加1来保证最坏的解不会完全剔除。3.5 选择概率选择机制用于选择父代的染色体，并构建杂交池。在以后的进化中更适应的染色体有较高的几率存活。本文中，我们使用简单常用的轮盘赌方式来作为选择机制。3.6 交叉算子我们提出一个交叉
15、操作来首先标示父代个体的共同特征，然后将其复制到后代。交叉操作是一种自适应记忆过程。开始时，自适应记忆被作为解决VRP问题禁忌搜索超启发算法的一部分提出来的。该过程存储了好解的特征。每发现一个新的好解，自适应记忆就会更新。对于我们来说，第一代的自适应记忆为空。为了向其中加入一个或部分解，有几种更可能行：（1）加入其中的候选解是前面最好的解，但它的花费至少比目前最好的解坏10%。（2）加入其中的候选解是群体中的一员，其花费同样至少比最优解坏10%。（3）一条路径与最优解及很多个体的相同详加分析，在交叉操作中，点是由自适应记忆各个个体以及最优解中随机选择的。因此首先选择两个交叉算子（Cr1，Cr2
16、）来控制用于自适应记忆、个体和最优解的部分参数。如果解之间有相同的部分则相同的部分遗传与下一代，否则Cr1、Cr2的值与一个随机数产生器的输出比较，randi(0,1)。如果随机数不大与Cr1，则相应的值从最好的解中遗传，若介于两者之间，遗传的值为自适应记忆中的随机的一个解，否则从其他个体的解中随机选择。因此如果子代解表示为Oi(t)，最优个体解bii(t)，自适应记忆解adi(t)，一个其他个体的解pi(t)：每次迭代自适应记忆基于最优解来更新，交叉操作后，计算子代的适应度函数，如果比父代好，变量被选择为下一代，否则父代至少多存活一代。3.7扩张邻域搜索本文用的局部搜索方法为扩张邻域搜索，ENS是一种超启发式算法，可以用来解决很多组合优化问题。该算法的主要特征：（a）运用圈限制局部搜索移动策略。（b）有在不同局部
