第３Ｏ卷第１２期 文章编号：１００６—９３４８（２０１３）１２—０１４０—０４ 计算机仿真 ２０１３年１２月 改进遗传算法求解ＶＲＰ问题 周生伟 ，蒋同海 ，张荣辉 （１．中国科学院新疆理化技术研究所，新疆乌鲁木齐８３００１１； ２．中国科学院大学，北京１０００４９） 摘要：物流配送车辆路径问题（Ｖｅｈｉｃｌｅ Ｒｏｕｔｉｎｇ Ｐｒｏｂｌｅｍ，ＶＲＰ）是一类具有广泛应用的ＮＰ—Ｈａｒｄ问题，是解决物流配送效率 的关键，传统方法寻找最优解的效率低、耗时长，往往找不到满意的解，导致物流成本过高。为了提高ＶＲＰ寻优效率，降低 物流运送成本，对基本遗传算法改进求解ＶＲＰ问题。首先建立ＶＲＰ的数学模型，然后基于贪婪随机自适应算法（Ｇｒｅｅｄｙ Ｒａｎｄｏｍｉｚｅｄ Ａｄａｐｔｉｖｅ Ｓｅａｒｃｈ Ｐｒｏｃｅｄｕｒｅ，ＧＲＡＳＰ）改进遗传算法的邻域搜索能力，生成遗传算法初始种群，最后利用遗传算法 从ＧＲＡＳＰ生成的初始种群中找到最优解。计算结果表明，所采用的改进遗传算法可以更好的求解车辆路径问题，有效降低 物流运送成本。 关键词：车辆路径问题；遗传算法；随机贪婪自适应搜索过程；物流；邻域搜索 中图分类号：ＴＰ３０１．６ 文献标识码：Ｂ Ｉｍｐｒｏｖｅｄ Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ ｆｏｒ ＶＲＰ ＺＨＯＵ Ｓｈｅｎｇ—ｗｅｉ ，ＪＩＡＮＧ Ｔｏｎｇ—ｈａｉ ，ＺＨＡＮＧ Ｒｏｎｇ—ｈｕｉ （１．Ｘｉｎｊｉａｎｇ Ｔｅｃｈｎｉｃａｌ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｐｈｙｓｉｃｓ ａｎｄ Ｃｈｅｍｉｓｔｒｙ，Ｃｈｉｎｅｓｅ Ａｃａｄｅｍｙ ｏｆ Ｓｃｉｅｎｃｅｓ Ｕｒｕｍｑｉ Ｘｉｎｊｉａｎｇ ８３００１ １，Ｃｈｉｎａ； ２．Ｇｒａｄａｔｅ Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈｉｎｅｓｅ Ａｃａｄｅｍｙ ｏｆ Ｓｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ １０００４９，Ｃｈｉｎａ） ＡＢＳＴＲＡＣＴ：Ｔｈｅ ｖｅｈｉｃｌｅ ｒｏｕｔｉｎｇ ｐｒｏｂｌｅｍ ｗｈｏｓｅ ｓｏｌｕｔｉｏｎ ｉｓ ａ ｋｅｙ ｔｏ ｉｍｐｒｏｖｅ ｅｆｉｃｉｆｅｎｃｙ ｏｆ ｌｏｇｉｓｔｉｃｓ ｐｒｏｂｌｅｍ ｉｓ ａ ｃｌａｓ— ｓｉｃａｌ ＮＰ—ｈａｒｄ ｐｒｏｂｌｅｍ．ａｎｄ ｉｔ ｉｓ ｕｓｕａｌｌｙ ｄｉｆｉｆｃｕｌｔ ｆｏｒ ｔｒａｄｉｔｉｏｎａｌ ｍｅｔｈｏｄｓ ｔｏ ｏｂｔａｉｎ ｓａｔｉｓｆｙｉｎｇ ｓｏｌｕｔｉｏｎｓ ＳＯ ａｓ ｔｏ ｈｉｇｈ ｌｏｇｉｓｔｉｃｓ ｃｏｓｔｉｎｇ．Ｉｎ ｔｈｉｓ ｐａｐｅｒ，ｉｎ ｏｒｄｅｒ ｔｏ ｒｅｄｕｃｅ ｌｏｇｉｓｔｉｃｓ ｃｏｓｔｓ，ｔｈｅ ｈｙｂｒｉｄ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｗａｓ ｓｅｌｅｃｔｅｄ ｔｏ ｓｏｌｖｅ ｔｈｅ ＶＲＰ ｐｒｏｂｌｅｍ．Ｔｈｉｓ ｐａｐｅｒ ｅｓｔａｂｌｉｓｈｅｄ ｔｈｅ ＶＲＰ ｍａｔｈｅｍａｔｉｃ ｍｏｄｅｌ ａｔ ｆｉｒｓｔ．Ｓｅｃｏｎｄ，ｔｈｅ ｉｍｐｒｏｖｅｍｅｎｔ ｕｓｉｎｇ Ｇｒｅｅｄｙ Ｒａｎｄｏｍｉｚｅｄ Ａｄａｐｔｉｖｅ Ｓｅａｒｃｈ Ｐｒｏｃｅｄｕｒｅ（ＧＲＡＳＰ）ｗａｓ ｆｏｃｕｓｅｄ ｏｎ ｔｈｅ ｌｏｃａｌ ｓｅａｒｃｈ ａｂｉｌｉｔｙ ｏｆ ｂａｓｉｃ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｔｏ ｇｅｎｅｒａｔｅ ｔｈｅ ｉｎｉｔｉａｌ ｓｏｌｕｔｉｏｎ．Ｔｈｅ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｗａｓ ｕｓｅｄ ｔｏ ｆｉｎｄ ｔｈｅ ｂｅｓｔ ｓｏｌｕｔｉｏｎ ｆｒｏｍ ｔｈｅ ｉｎｉｔｉａｌ ｓｏｌｕｔｉｏｎｓ ｉｎ ｔｈｅ ｅｎｄ．Ｔｈｅ ｃａｌｃｕｌａｔｉｏｎ ｒｅｓｕｌｔ ｓｈｏｗｓ ｔｈａｔ ｔｈｉｓ ｉｍｐｒｏｖｅｄ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｃａｎ ｓｏｌｖｅ ｔｈｅ ｖｅｈｉｃｌｅ ｒｏｕｔｉｎｇ ｐｒｏｂｌｅｍ ｂｅｔｔｅｒ ｔｈａｎ ｔｈｅ ｂａｓｉｃ ｏｎｅ ａｎｄ ｒｅｄｕｃｅ ｌｏｇｉｓｔｉｃｓ ｃｏｓｔｉｎｇ ｅｆｆｅｃｔｉｖｅｌｙ． ＫＥＹＷＯＲＤＳ：Ｖｅｈｉｃｌｅ ｒｏｕｔｉｎｇ ｐｒｏｂｌｅｍ；Ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ；Ｇｒｅｅｄｙ ｒａｎｄｏｍｉｚｅｄ ａｄａｐｔｉｖｅ ｓｅａｒｃｈ ｐｒｏｃｅｄｕｒｅ（ＧＲＡＳＰ）； Ｌｏｇｉｓｔｉｃｓ；Ｌｏｃａｌ ｓｅａｒｃｈ 出的，经过几十年的发展，其应用领域已经越来越广。ＶＲＰ １ 引言 随着我国社会经济的不断发展，物流行业发展迅速，运 输成本成为了物流行业成本花费最大的一部分，所以，车辆 路径问题（ＶＲＰ）的研究在物流配送过程中的作用越来越重 要。车辆路径问题最早是由Ｄａｎｔｉｎｇ和Ｒａｍｓｅｒ于１９５９年提 问题一般描述为：一定数量的客户，各自有不同数量的货物 需求，配送中心向客户提供货物，由一个车队负责分送货物， 组织适当的行车路线，目标是使得客户的需求得到满足，并 能在一定的约束下，达到诸如路程最短、成本最小、耗费时间 最短等目的。 ＶＲＰ问题解法比较丰富，基本上可以分为精确算法和启 发式算法两大类，由于ＶＲＰ问题的ＮＰ—Ｈａｒｄ属性，运用精 基金项目：国家自然科学基金（１１１４７１２８）；中国科学院西部之光博士 专项（ＸＢＢＳ２０１１１９）；新疆维吾尔自治区科技支疆项目（２０１２９１１１５） 收稿日期：２０１３一Ｏ１—２４修回日期：２０１３—０３—０６ １４０一 确算法求解，计算量会随着问题规模的增大而呈指数增 加…。由于传统方法效果不佳，近三十年来涌现出的一些智 能算法，如模拟退火算法、遗传算法、神经网络及这些算法的 —混合算法、改进算法等被用来求解ＶＲＰ问题并取得了良好 的效果 。 号为 （ ＝１，２，…，ｍ）；令 表示两个节点之间的运输成 本，定义如下变量： ｒ１ 一遗传算法是模拟生物进化过程搜索最优解的方法，于 １９７５年提出，有采用随机选择，对搜索空问无特殊要求等优 （如车辆 经客户ｉ驶向客户 ） １－０ （其他情况） ｒ１ （如客户ｉ的需求由车辆ｋ满足） 点，多被用来解决ＶＲＰ问题。目前对遗传算法的研究多集 中于对遗传算法操作算子的改进，基本改进手段是对遗传算 法基本操作算子（选择算子、交叉算子、变异算子）改进或者 基本操作算子加一种改进的操作算子作为改进的遗传算法， 对遗传算法初始种群的改进讨论的并不是很多，所以论文用 “ 【０ （其他情况） 所以车辆路径问题的数学模型如下： ｍｉｎＺ＝ Ｓ．￡． ｃ ｉ ＝ｏ ｌ ０ ｋ １ ＧＲＡＳＰ算法改进遗传算法的初始种群。ＧＲＡＳＰ算法是一种 适合用来求解组合优化问题的启发式算法，是一种迭代的两 （２） 阶段算法 。第一阶段用于生成初始种群，第二阶段对生成 的初始种群进行改进，经多次迭代找出最优解。遗传算法存 在局部搜索能力较弱的缺点，改进遗传算法的初始种群生成 可以提高遗传算法的局部搜索能力，这是用ＧＲＡＳＰ改进遗 传算法提高ＶＲＰ问题最优解的关键所在。通过基准测试实 例的实验，结果表明，改进了初始种群生成的基本遗传算法 可以有效提高ＶＲＰ解的质量。 ２ ＶＲＰ问题模型 物流配送车辆路径问题一般指特定位置和需求量的客 户点，调用一定数量的车辆，从中心仓库出发，选择最优的行 车路线，使车辆有序的访问个客户点，在满足特定的约束条 件（如客户的需求，车辆的载重限制）下，使得货物最快到达 客户点并使运输费用最低。 基于以上考虑，要如下要求要实现： １）所有配送车辆从配送中心出发，最后回到配送中心。 ２）每个客户只被一辆车服务，每辆车只能走一条路线。 ３）每条运输线路上，客户总需求量不能超过车辆载重 总和。 ４）车辆不能有重复的形式路线。 对于以上要求，一般地，把ＶＲＰ问题描述为：配送中心 有ｍ辆货车，每一辆车的运载能力均为ｑ；配送中心需为ｎ 个客户提供货物配送服务，每个客户的需求量为ｇ （ｉ＝１，２， …，ｎ），ｇ ＜ｇ，求满足货运要求的运行费用最少的车辆调度 方案。 这里须预先对所需要的车辆数进行估计，论文采用以下 公式确定车辆数： ＝［ ｉ＝１ 其中［］表示Ｇａｕｓｓ整数函数，表示不大于括号内数字的最 大整数，０＜ｏ／＜１是对装卸车的复杂性程度及约束多少的一 个参数估计。一般情况下，装卸车越复杂，约束越多， 值越 小，表示一辆车所能容纳的货物量越小 ｊ。 基于以上数学描述，结合图论中的最短路径问题，建立 ＶＲＰ问题的数学模型。首先作如下规定，令配送中心的编号 为０号节点，客户的编号为ｉ（ｉ＝１，２，…，ｎ），配送车辆的编 ∑ Ｙ ≤ｑ， ∑ ＝１（３） ：１ ∑ 毋＝强 Ｊ：１…２．．Ｉｎ （４） ∑ ＝Ｙ ｉ＝１…２． （５） ＝０或１ ｉ， ＝１，２，…，ｎ （６） ｍ＝０或１ ｉ＝１，２，…，ｎ （７） 在上述数学模型中，式（２）表示每条配送路线上的总客 户需求量不大于车辆的运载能力；式（３）表示配送任务由ｍ 辆车完成并且每个客户的配送任务仅由一辆车完成；式（４） 和（５）则确保到达客户的车必须离开该客户；式（６）和（７）表 示变量的取值满足定义的要求¨ 。 ３ ＧＲＡＳＰ算法 ＧＲＡＳＰ是一种适合用来求解组合优化问题的启发式算 法，ＧＲＡＳＰ算法的每次迭代过程包含两个阶段：构造阶段和 局域搜索阶段。构造阶段由贪心随机算法产生一个初始可 行解；局域搜索阶段利用局部搜索算法对构造阶段产生的 解改进。每次迭代的局部最优解中的最好局域解为全局满 意解 Ｊ。 ３．１构造阶段 构造阶段产生初始解并在不断迭代的过程中形成可行 方案。每一次迭代利用贪婪函数值形成候选元素的受限候 选列表（ＲＣＬ），并随机选择一个元素加人方案。贪婪函数 用于衡量候选元素加入方案后的代价，从ＲＣＬ中选择完一 个元素后，需重新计算剩余候选元素的贪婪函数值，并形成 新的ＲＣＬ。从ＲＣＬ中随机选择元素的方法使得每个构造阶 段可以产生不同的可行方案；当所求问题的所有调度元素 都处理完成后就中止迭代，返回产生的可行解 。 ’。构造 阶段伪代码如下： ｐｒｏｃｅｄｕｒｅ Ｇｒｅｅｄｙ Ｒａｎｄｏｍｉｚｅｄ Ｃｏｎｓｔｒｕｃｔｉｏｎ（０【，Ｓｅｅｄ） １）Ｓｏｌｕｔｉｏｎ ： ２） Ｉｎｉｔｉａｌｉｚｅ ｔｈｅ ｃａｎｄｉｄａｔｅ ｓｅｔ：Ｃ Ｅ： ３） Ｅｖａｌｕａｔｅ ｔｈｅ ｉｎｃｒｅｍｅｎｔａｌ ｃｏｓｔ Ｃ（ｅ）ｆｏｒ ａｌｌ ｅ∈Ｃ： ４）ｗｈｉｌｅ Ｃ≠ ｄｏ 一１４１～ ５） ６） ｍｌｎ＋－－ｍｉｎ｛ｃ（ｅ）ｌ ｅ∈Ｃ｝； ｅ…＋＿Ｉ ｍａｘ｛ｃ（ｅ）Ｉ ｅ∈Ｃ｝； 一种群染色体采取整数串编码，整数的排列顺序表示车辆 访问顾客的顺序。利用ＧＲＡＳＰ算法的构造阶段产生问题的 ７） ８） ＲＣＬ一｛ｅ∈Ｃ １ ｅ（ｅ）≤ｃ…＋ｏ１．（ｅ…一ｅ…）｝； Ｓｅｌｅｃｔ ａｎ ｅｌｅｍｅｎｔ ｓ ｆｒｏｍ ｔｈｅ ＲＣＬ ａｔ ｒａｎｄｏｍ： 个可行解作为遗传算法的初始种群。操作前，需要计算种 群内部全部个体适应度，以个体所对应的行驶距离的倒数作 为个体的适应度，个体对应的行驶距离越长，其适应度越低。 ４．２选择、交叉、变异操作 ９） Ｓｏｌｕｔｉｏｎ ＳｏｌｕｔｉｏｎＵ｛ｓ｛； １０） Ｕｐｄａｔｅ ｔｈｅ ｃａｎｄｉｄａｔｅ ｓｅｔ Ｃ； １１） Ｒｅｅｖａｌｕａｔｅ ｔｈｅ ｉｎｃｒｅｍｅｎｔａｌ ｃｏｓｔｓ ｃ（ｅ）ｆｏｒ ａｌｌ ｅ∈Ｃ； １２） ｅｎｄ： １３） ｒｅｔｕｒｎ Ｓｏｌｕｔｉｏｎ： ｅｎｄ Ｇｒｅｅｄｙ Ｒａｎｄｏｍｉｚｅｄ Ｃｏｎｓｔｒｕｃｔｉｏｎ． 选择算子采用轮盘赌选择，适应度大的个体被选中用于 交叉操作的概率也大。 对于交叉操作，如果单纯的使用一般的交叉算子往往会 产生大量的不可行解或者导致优良基因段丢失。从而影响遗 ３．２局部搜索阶段：混合邻域搜索技术 传算法的搜索效果，所以采用文献［２］中交叉操作方法保证 种群的多样性。由于物种变异的可能性较小，所以变异操作 构造阶段产生的解不一定是最优的，因此需要一个局部 搜索来改善构造出的解。ＧＲＡＳＰ的局部搜索算法就是以一 在遗传算法中只起辅助作用，对种群以变异概率Ｐ 进行染 种迭代的方式不断地用当前解的邻域中较好解替代当前解， 直到不能找到较好解时停止。本文的邻域搜索技术采用２一 ｏｐｌ和３一ｏｐｔ相结合的混合邻域搜索技术 川 。局部搜索 阶段的伪代码如下： Ｐｒｏｃｅｄｕｒｅ ＬＯＣＡＬＳＥＡＲＣＨ 色体变异，对于自然数编码的染色体，论文采用逆转变异。 具体变异过程如下例所示：随机产生一个染色体Ｅ的两个变 异点，将变异段逆转得到染色体Ｅ１ Ｅ＝１ ２ Ｊ ３ ４ ５ ６ ７ Ｉ ８ ９一Ｅ１＝１ ２ ｉ ７ ６ ５ ４ ３ ｉ ８ ９ ４．３邻域搜索操作 本文结合ＧＲＡＳＰ算法的第二个阶段即局部搜索阶段设 Ｆｏｒ ｉ＝０ ｔ Ｏ ｎ一１ ２一Ｏｐｔ Ｓｅａｒｃｈ（ ｔ） Ｆｏｒ ｉ＝０ ｔ Ｏ ｎ一１ ｄｏ 汁了ＧＲＡＳＰ领域搜索算子，该算子将２一Ｏｐｔ和３一Ｏｐｔ算 法相结合对当前染色体的每条子路径进行优化，通过改变子 ３一Ｏｐｔ Ｓｅａｒｃｈ（ ｔ） Ｅｎｄ ｆｏｒ 路径中客户的服务顺序来缩短行驶距离。通过邻域搜索算 子可以在种群中最优个体的邻域空间做进一步搜索以期望 能找到适应度更好的个体。 Ｅｎｄ ｆｏｒ Ｅｎｄ Ｌ０ＣＡＩ ＳＥＡＲＣＨ ５仿真结果 ４改进的遗传算法 遗传算法模拟生物进化过程中发生的繁殖、交叉和基因 突变现象，在每次迭代中都保留一组候选解，并按某种指标 从解群中选取较优的个体，利用遗传算子对这些个体进行组 合，产生新一代的候选解群，重复此过程，直到满足某种收敛 指标为止。遗传算法有较强的全局搜索能力，但是容易出现 早熟、收敛速度慢等问题，为解决这一缺点，引入邻域搜索算 法。论文结合ＧＲＡＳＰ算法设计了一种ＧＲＡＳＰ邻域搜索算 为了验证论文提出算法的有效性，对Ｓｏｌｏｍｏｎ ＶＲＰ问题 标准测试数据进行仿真测试。测试数据从ｈｔｔｐ：∥ｂｒａｎｃｈａｎｄ— ｃｕｔ．ｏｒｇ，／ＶＲＰｄａｔａ下载得到。设置改进遗传算法参数为：选择 概率Ｐ ＝３０％，交叉概率Ｐ ＝３０％，变异概率Ｐ ＝２０％。 对基准测试实例Ｅ—ｎ２２一ｋ４和Ｅ—ｎ３３一ｋ４测试，测试 结构见表１和表２。在实例名中，ｎ后数字表示问题的规模， 它的值等于客户数加一（包括配送中心），ｋ后边的数字表示 最优解使用的车辆数。改变改进遗传算法的种群规模Ｍ和 子，该ＧＲＡＳＰ邻域搜索算子可以克服遗传算法局部搜索能 力差的弱点。 ４．１编码方式、初始种群、适应度函数 迭代次数ＧＥＮ，在每组参数下，分别对每个测试实例进行１０ 次计算，结果如１和表２所示。 表１ Ｅ—ｎ２２一ｋ４计算结果 一１４２— 表２ Ｅ—ｒｄ３一ｋ４计算结果 试验结果表明，种群规模Ｍ和迭代次数ＧＥＮ对解的质 量影响较大。在同等种群规模下，随迭代次数越多，车辆行 驶距离越来越接近最优解，而且最优解的出现具有随机性， 止遗传算法陷入局部最优解，可以有效提高遗传算法解的 质量。 ３）论文实验讨论了在基本操作算子固定的情况下，初始 这主要是因为遗传算法存在随机性，虽然论文改进了遗传算 种群Ｍ和迭代次数ＧＥＮ对实验结果的影响，并给出了几个 法初始种群的生成，但ＧＲＡＳＰ对初始解的处理仍具有随机 性，所以具体的优化过程在每次运行时会有所不同。 由表２和表３可以看出，当Ｍ和ＧＥＮ较小时，解的质量 较差，随着Ｍ和ＧＥＮ的增大，解的质量随之提高。表２中， 当Ｍ增大到１００，ＧＥＮ增大到１０００时，也可以获取最优解， 但是获取最优解的几率较低，各次计算结果之间的差值也较 大。当Ｍ为１００，ＧＥＮ增大１００００时，获取最优解的几率大 增。所以，随着问题规模的增大，增加种群规模和迭代次数 可以增加获取最优解的概率，减少结果值和最优解之间的偏 差。当Ｍ和ＧＥＮ都增大到一定值时，Ｍ和ＧＥＮ对运行结果 的影响变小。 比较表２和表３，在客户数增大，Ｍ和ＧＥＮ相同的情况 下，问题规模增大，搜索空间增大，解的质量下降，此时，即使 增大种群规模和迭代次数，效果也并不好，这是由于问题的 本质是ＮＰ—Ｈａｒｄ导致搜索空间急剧增大所引起的。 论文基于ＧＲＡＳＰ改进遗传算法对中等规模的ＶＲＰ问 题有较好的适应性，在增大Ｍ和ＧＥＮ的条件下，可以有效的 求解问题，所以，在实际应用中，对中等和小规模的ＶＲＰ问 题，可调试适当的Ｍ和ＧＥＮ的值，有效求解ＶＲＰ问题，当问 题规模较小时，为了减少运算代价，可适当降低Ｍ和ＧＥＮ的 值，当Ｍ和ＧＥＮ较大时，为了提高求解精度，应适当凋大Ｍ 和ＧＥＮ的值。 ６结论 把遗传算法与ＧＲＡＳＰ算法结合，设计了一种改进的遗 传算法求解￣ＲＰ问题，总结具有如下几个特点： １）目前对用改进遗传算法求解ＶＲＰ问题多集中于对遗 传算法操作算子的研究上，很多研究人员对基本的遗传算法 操作算子进行了改进，还有研究人员利用其它的学科领域知 识产生新的操作算子 “ ，论文采用的改进遗传算法的关注 重点则在于初始种群的产生上，利用ＧＲＡＳＰ算法的第一阶 段即初始解构造阶段产生初始种群，利用ＧＲＡＳＰ算法的第 二阶段初步改进初始种群，然后利用遗传算法逼近最优解， 该方法是目前研究采用不多的。 ２）利用ＧＲＡＳＰ在进化初始阶段就产生多样化的解，最 大的提高就是解决基本遗传算法局部搜索能力差的问题，防 基本结论。 通过对标准测试实例的实验可以看出基于ＧＲＡＳＰ的改 进遗传算法可以有效的求解中等规模和小规模的ＶＲＰ问 题。当然，由于ＶＲＰ问题的困难属性，如何寻找更好的优化 方法，还有待进一步的研究。 参考文献： ［１］黄小燕，等．改进遗传操作ＰＳＯ算法及其在ＶＲＰ中的应用 ［Ｊ］．计算机仿真，２００９，２６（１１）：２９４—２９８． ［２］ 蔡蓓蓓，张兴华．混合量子遗传算法及其在ＶＲＰ中的应用 ［Ｊ］．计算机仿真，２０１０，２７（７）：２６７—２７０． ［３］ 廖良才，王栋，周峰．基于混合遗传算法的物流配送车辆调度 优化问题求解方法ｆＪ］．系统工程，２００８，２８（６）：２７—３１． ［４］ Ｇｅｏｎｗｏｏｋ Ｊｅｏｎ，Ｈｅｒｍａｎ Ｒ Ｌｅｅｐ，Ｊａｅ Ｙｏｕｎｇ Ｓｈｉｍ．Ａ ｖｅｈｉｃｌｅ ｍｎ－ ｔｉｎｇ ｐｒｏｂｌｅｍ ｓｏｌｖｅｄ ｂｙ ｕｓｉｎｇ ａ ｈｙｂｒｉｄ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ［Ｊ］．Ｃｏｍ— ｐｕｔｅｒｓ＆Ｉｎｄｕｓｔｒｉｌａ Ｅｎ￣ｎｅｅｒｉｎｇ．２００７．５３：６８０—６９２． ［５］ Ｚｉａｕｄｄｉｎ Ｕｒｓａｎｉ，ｅｔ ａ１．Ｌｏｃａｌｉｚｅｄ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｖｅｈｉｃｌｅ ｍｕ－ ｔｉｎｇ ｐｒｏｂｌｅｍ ｗｉｔｈ ｔｉｍｅ ｗｉｎｄｏｗｓ［Ｊ］．Ａｐｐｌｉｅｄ Ｓｏｆｔ Ｃｏｍｐｕｔｉｎｇ， ２０１１，１１：５３７５—５３９０． ［６］ Ｙｖｅｓ Ｒｏｃｈａｔ，Ｅｒｉｃ Ｄ Ｔａｉｌｌａｒｄ．Ｐｍｂａｂｉｌｉｓｔｉｅ ｄｉｖｅｒｓｉｉｆｃａｔｉｏｎ ａｎｄ ｉｎ－ ｔｅｎｓｉｉｆｃａｔｉｏｎ ｉｎ ｌｏｃａｌ ｓｅａｒｃｈ ｆｏｒ ｖｅｈｉｃｌｅ ｒｏｕｔｉｎｇ ｐｒｏｂｌｅｍ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆＨｅｕｒｉｓｔｉｃ，１９９５，１：１４７—１６７． ［７］郑雅燕，朱文兴．ＴＳＰ问题的一种改进的ＧＲＡＳＰ算法［Ｊ］．计 算机工程与科学，２００８，３０（１１）：６０～６４． ［８］ Ｙａｎｎｉｓ Ｍａｒｉｎａｋｉｓ．Ｍｕｈｉｐｌｅ ｐｈａｓｅ ｎｅｉｇｈｂｏｒｈｏｏｄ ｓｅａｒｃｈ—ＧＲＡＳＰ ｆｏｒ ｔｈｅ ｃａｐａｅｉｔａｔｅｄ ｖｅｈｉｃｌｅ ｍｕｔｉｎｇ ｐｒｏｂｌｅｍ［Ｊ］．Ｅｘｐｅｒｔ Ｓｙｓｔｅｍｓ ｗｉｔｈ Ａｐｐｌｉｃａｔｉｏｎｓ，２０１２，３９：６８０７—６８１５． ［９］Ｔｈｏｍａｓ Ａ Ｆｅｏ，Ｍａｕｒｉｃｉｏ Ｇ Ｃ Ｒｅｓｅｎｄｅ．Ｇｒｅｅｄｙ ｒａｎｄｏｍｉｚｅｄ ａｄａｐ． ｔｉｒｅ ｓｅａｒｃｈ ｐｒｏｃｅｄｕｒｅｓ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｇｌｏｂａｌ Ｏｐｔｉｍｉｚａｔｉｏｎ，１９９５，６ （１９９５）：１０９—１３４． ［１０］ Ｙａｎｎｉｓ Ｍａｒｉｎａｋｉｓ，Ａｔｈａｎａｓｉｏｎ Ｍｉｇｄａｌａｓ．Ｅｘｐａｎｄｉｎｇ ｎｅｉｇｈｂｏｒｈｏｏｄ ＧＲＡＳＰ ｆｏｒ ｔｈｅ ｔｒａｖｅｌｉｎｇ ｓａｌｅｓｍａｎ ｐｒｏｂｌｅｍ［Ｊ］．Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｏｐｔｉｍｉｚａｔｉｏｎ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ，２００５，３２（２００５）：２３１—２５７． ［１ １］ Ｊａｉｌ Ｋｙｔ／￣ｊｏｋｉ，ｅｔ ａ１．Ａｎ ｅｆｆｉｃｉｅｎｔ ｖａｒｉａｂｌｅ ｎｅｉｇｈｂｏｒｈｏｏｄ ｓｅａｒｃｈ ｈｅｕｒｉｓｔｉｃ ｆｏｒ ｖｅｒｙ ｌａｒｇｅ ｓｃｌａｅ ｖｅｈｉｃｌｅ ｒｏｕｔｉｎｇ ｐｒｏｂｌｅｍｓ［Ｊ］．Ｃｏｒｎ— ｐｕｔｅｒｓ＆Ｏｐｅｒａｔｉｏｎｓ Ｒｅｓｅａｒｃｈ，２００７．３４：２７４３—２７５７． ［１２］ 田延硕，刘晓云．一种提高局部搜索能力的混合遗传算法 ［ｎ （下转第１５７页ｌ 一１４３— ２）极大的降低了汽车发动机罩拓扑设计的计算复杂度， 平均降低４％。 ３）机罩的承受压力系数，最低提高ｌ，最高提升２．３。 参考文献： ［１］丁晓红，等．薄板结构的加强筋自适应成长设计法［Ｊ］．中国 机械工程，２００５，１６（１２）：１０５７—１０６０． 表２本文算法实验数据表 ［２］荣见华，唐国金，杨振兴．一种三维结构拓扑优化方法［Ｊ］．固 体力学学报，２００５，２６（３）：２８９—２９７． ［３］ 隋允康，杨德庆，孙焕纯．统一骨架与连续体结构拓扑优化的 ＩＣＭ理论与方法［Ｊ］．计算力学学报，２０００，１７（１）：２８—３３． ［４］ 陈塑寰，麻凯．板壳加筋结构的组合优化［Ｊ］．吉林大学学报， ２００８，３８（２）：３８８—３９２． ［５］荣见华，等．渐进结构优化设计的现状与进展［Ｊ］．长沙交通 学院学报，２００１，１７（３）：１６—２３． ［６］ 刘海江，赵磊，李运．应用拓扑优化方法的发动机罩板结构轻 量化研究［Ｊ］．现代制造工程，２００９，３３（９）：４—７． ［７］周春平，常锦昕．基于单元生死功能的转向架构架拓扑优化设 计［Ｊ］．计算机仿真，２０１０，（５）：２６７—２７０． ［８］Ｔａｍ Ｈ Ｎｇｕｙｅｎ，ｅｔ ａ１．Ａ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｐａｒａｄｉｇｍ ｆｏｒ Ｍｕｌｔｉｒｅｓｏｌｕ— ｔｉｏｎ Ｔｏｐｏｌｏｇｙ Ｏｐｔｉｍｉｚａｔｉｏｎ（ＭＴＯＰ）［Ｊ］．Ｓｔｒｕｃｔｕｒａｌ ａｎｄ Ｍｕｌｔｉｄｉｓ－ 对上述实验数据进行对比可以得知，利用本文算法进行 汽车发动机罩拓扑设计，极大的降低了汽车发动机罩拓扑设 计的计算复杂度，平均降低４％，机罩的承受压力系数，最低 ｅｉｐｌｉｎａｒｙ，Ｏｐｔｉｍｉｚａｔｉｏｎ，２０１０，４１（４）：５２５—５３９． ［９］Ｇ Ａｌｌａｉｒｅ，Ｆ Ｊｏｕｖｅ，Ｈ Ｍａｉｌｌｏｔ．Ｔｏｐｏｌｏｇｙ Ｏｐｔｉｍｉｚａｔｉｏｎ ｆｏｒ Ｍｉｎｉｍｕｍ Ｓｔｒｅｓｓ Ｄｅｓｉｇｎ ｗｉｔｈ ｔｈｅ Ｈｏｍｏｇｅｎｉｚａｔｉｏｎ Ｍｅｔｈｏｄ［Ｊ］．Ｓｔｒｕｃｔｕｒａｌ ａｎｄ Ｍｕｌｔｉｄｉｓｃｉｐｌｉｎａｒｙ Ｏｐｔｉｍｉｚａｔｉｏｎ，２００４，２８（２）：８７—９８． 提高１，最高提升２．３，这总体上提高了汽车发动机罩的安全 性能，保证了汽车的安全。 ［１０］ Ｍｉ—Ｙｏｕ Ｐａｒｋ，Ｙｏｕｎｇｉｎ Ｐａｒｋ，Ｙｏｕｎ—ｓｉｋ Ｐａｒｋ．Ｒａｉｓｉｎｇ Ｎａｔｕｒａｌ Ｆｒｅｑｕｅｎｃｉｅｓ ｏｆ Ａ Ｓｔｒｕｃｔｕｒｅ Ｖｉｎ Ｓｕｒｆａｃｅ—ｇｒｏｏｗｉｎｇ Ｔｅｃｈｎｉｑｕｅ ［Ｊ］．Ｓｔｒｕｃｔｕｒａｌ ａｎｄ Ｍｕｈｉｄｉｓｃｉｐｌｉｎａｒｙ Ｏｐｔｉｍｉｚａｔｉｏｎ，２００７，３４ ５结束语 本文提出了一种基于有限元模型的汽车发动机罩拓扑 （６）：４９１—５０５． 设计优化方法。建立汽车发动机罩有限元模型，从而获取汽 车发动机罩的设计变量，为汽车发动机罩拓扑设计提供了准 ［作者简介］ 冯 颖（１９７９一），女（汉族），湖南衡阳人，硕士，讲 师，主要研究方向：工业产品造型设计，产品设计， 人机交互等。 确的数据基础。计算设计域水平集的空间位置，从而实现汽 车发动机罩拓扑设计优化处理。通过实验可得如下结论： １）本文算法是可行的，它可以满足系统的安全性要求。 （上接第１４３页） 电子科技大学学报，２００６，３５（２）：２３２—２３４． ［１３］王小平，曹立明．遗传算法一理论、应用与软件实现［Ｍ］．西 安：西安交通大学出版社，２００２． ［１４］ 李军，郭耀煌，物流配送车辆优化调度理论与方法［Ｍ］．北 京：中国物资出版社，２００１． ［１５］ Ｂｒｕｃｅ Ｌ Ｇｏｌｄｅｎ，Ｓ Ｒａｇｈａｖａｎ，Ｅｄｗａｒｄ Ａ Ｗａｓｉｌ．Ｔｈｅ ｖｅｈｉｃｌｅ Ｆｏｒｔ— ＿ ［周士技蒋福研术海生同究县。伟海 生人（１，９主８６７３要一研），究男作（领汉者域族简为）介，计新山］ 算疆东机维省吾应泰尔用安族、市物自人联治，硕网区 ，研究员，博士研究生导师，主要研究领域 为计算机控制技术、双语教育、感知网络集成应用。 ｔｉｎｇ ｐｒｏｂｌｅｍ［Ｍ］．ＮｅｗＹｏｒｋ：Ｓｐｒｉｎｇｅｒ—Ｖｅｒｌａｇ Ｎｅｗ Ｙｏｒｋ Ｉｎｃ，２０１０． 张荣辉（１９８１一），男（汉族），江西省广丰市人，博士、副研究员，主 要研究领域为控制理论及应用、物联网关键技术。 一１５７—
