《遗传算法基于路径优化问题应用的改进探索研究》由会员分享，可在线阅读，更多相关《遗传算法基于路径优化问题应用的改进探索研究（4页珍藏版）》请在金锄头文库上搜索。
1、本文作者(张立营),请您在阅读本文时尊重作者版权。遗传算法基于路径优化问题应用的改进探索研究摘要：遗传算法是一种应用很广泛的智能优化算法，对遗传算法进行了分析研究，针对遗传算法的一些缺陷提出了相应的改进方法。在上述研究基础上，基于遗传算法，研究了物流系统中的库存优化问题及车辆路径问题。将车辆路径问题看做是组合优化问题，并应用遗传算法进行求解。关键词：路径优化；遗传算法；禁忌搜索算法引言随着经济快速发展、信息化时代的来临，尤其是网络购物等新型购物方式的发展壮大使得物流业迅速成为人们日常所不可缺少的行业。与此同时物流业之间的竞争也迅速加剧。而物流业也与其他服务业一样除了服务质量的竞争以外关键在于成
2、本的竞争。物流企业成本绝大部分在于运输过程中产生，有效地路径优化能够帮助物流企业很好的解决成本节约问题。从而遗传算法等高效简洁的优化算法成为人们越来越关注的对象。一、研究背景近年来，随着人工智能应用领域的不断扩大，传统的基于符号处理的人工智能方法在知识表示、信息处理和解决组合爆炸等方面遇到的困难越来越明显，从而使得寻求一种适合于大规模问题并具有自组织、自适应、自学习能力的算法成为有关学科的一个研究目标。遗传算法（genetic algorithms，简称 GA）是J.Holland 与 1975 年提出的。GA 是基于“适者生存”的一种高度并行、随机和自适应的优化算法，它将问题的求解表示成“染
3、色体”的适者生存过程，通过“染色体”群的一代代不断进化，包括复制、交叉和变异等操作，最终收敛到“最适应环境”的个体，从而求得问题的最优解或满意解。二、遗传算法GA 是一种通用的优化算法，其编码技术和遗传操作比较简单，优化不受限制性条件的约束，其两个显著性特点是隐含并行性和全局解空间搜索。它是一类随机优化算法，但它不是简单的随机比较搜索，而是通过对染色体的评价和对染色体中基因的作用，有效地利用已有信息来指导搜索有希望改善优化质量的状态。遗传算法主要借鉴了生物进化的一些特征，它的主要生物进化特征体现在：（1）进化发生在解的编码上。这些编码用生物术语称为染色体。由于一开始要进行编码，优化问题的一切性
4、质都通过编码来研究。编码和解码是遗传算法的一个主题。（2）自然选择规律决定哪些染色体产生超过平均数的后代。而在遗传算法中，通过优化问题的目标而人为地构造适应函数以达到好的染色体产生超过平均数的后代。（3）当染色体结合时，双亲的遗传基因结合使得子女保持有父母的特征。（4）染色体结合以后，随机的变异会造成子代与父代产生不同的特征。遗传算法主要包含以下处理步骤：第一是对优化问题的解编码。此外，称一个解的编码为一个染色体，组成编码的元素成为基因。编码的目的主要是用于优化问题的表现形式和利于之后遗传算法中的计算。第二是适应函数的构造和应用。适应函数基本上依据优化问题的目标函数而定。适应函数确定以后，自然
5、选择规律是以适应函数值的大小决定的概率分布来确定哪些染色体适应生存，哪些被淘汰。生存下来的染色体就组成了一个种群，形成一个可以繁衍下一代的种群。第三是染色体的结合。双亲的遗传基因之间的结合是通过编码之间的交配（crossover）达到下一代的产生。遗传算法作为一个全局性优化算法具有很大的优越性，具体体现在：（1）遗传算法适合求解那些带有多参数、多变量、多目标和在多区域但连通性较差的 NP难（非多项式确定性问题）优化问题。对多参数、多变量的 NP 难优化问题，通过解析求解或计算求最优解的可能性很小，主要依赖于数值求解。遗传算法就是一种数值求解的算法，具有普遍性并且对目标函数的性质几乎没有要求，并
6、且它可以一次记录多个解。（2）遗传算法在求解很多组合优化问题时，不需要有很强的技巧和对问题有非常深入的了解。如路线调度问题、排序等。遗传算法再给这些问题的决策变量编码后，起计算过程是比较简单的，并且可以较快的得到一个满意解。（3）遗传算法同求解问题的其他启发式算法有较好的兼容性。当然遗传算法也不可避免地存在着它的不足之处：（1）存在编码不规范及表示不准确等问题。（2）单一的遗传编码不能全面地将优化问题的约束表示出来。（3）大量研究也表明，GA 存在早熟、算法参数敏感等缺点，取得良好的性能需要依赖较大的种群并对算法进行精心设计。采用遗传算法等智能优化算法来求解带能力约束的车辆路径问题 （Capa
7、citated Vehicle Routing Problem，即 CVRP），一般能在较短的计算时间内获得质量较高的近似解。三、问题描述CVRP 可描述如下:配送中心有 m 辆货车，每辆车的能力为 q；配送中心需为 n 个客户提供货物配送任务，每个客户的需求量为 gi（i=1，2，n），gi 有 1 个配送中心和 8 个商店，商店 0 表示配送中心，配送中心有两辆载重量为8 吨的货车，要求合理安排车辆行驶路径，使总运输距离最小。商店之间的相互距离及各商店的商品需求量（见表 1、表 2）： 表 1 各需求点对货物需求量 单位：吨表 2 配送中心与各需求点之间的距离单位：KM四、算法改进 在现有
8、遗传算法中，个体的染色体编码还需要用到最优车辆数。这两种编码方案有三个缺点:（1）由于染色体维数变长，使组合空间变大，从而降低了搜索到最优解的几率。（2）由染色体解码后获得的子路径有可能不满足车辆的能力约束。（3）需要预先知道最优解所需车辆数。为了避免上述缺点，本文提出一种新的双层染色体编码方案 Double Layers Chromos Coding Shema，DLCCS）。标准遗传算法中染色体是单层的。而在DLCCS 中，染色体是两层的，其构成为：第一层是 n 维向量 L1，代表 n 个客户的一种排列。第二层是一个维数可变的向量 L2，在 L2 中存放的元素代表每辆车所服务的第一个客户在
9、 Ll 中的顺序号，需根据车辆的能力限制计算得出。以上节的例为例，用自然数 18 代表 8 个客户，其需求量分别为（1，2，1，2，1，4，2，2），车辆的能力约束为 8 个单位。假定某个体的第一层染色体为 L1（4，l，3，7，2，6，5，8），第二层染色体的计算过程如下:（1）第一辆车编为 0 号车，其第一个客户为客户 4，在 L1 中的顺序号为 0，因此第二层染色体暂时为 LZ（0）。编号顺序都从 0 开始，这便于编程实现，因为在很多编程语言中，都将数组的起始编号设为 0。（2）继续让 0 号车服务后面的客户，直到超出车辆的能力约束，在本例中，0 号车可以服务前 5 个客户，到第 6 个
10、客户，由于违反车辆的能力约束，需派出 1 号车（第二辆车）。1 号车所服务的第一个客户为客户 6，其在 Ll 中的顺序号为 5，将其加入 LZ，第二层染色体变成 L2（0，5）。（3）继续应用步骤 2，直到所有的客户都得到服务为止。设置遗传算法的种群规模为 60，交叉概率为 0.8，变异概率为 0.05。在计算机上用 MATLAB 优化软件求得标准遗传算法与改进后的遗传算法结果（如表 3 所示）。 由表 3 可以看出，改进后的遗传算法比标准的遗传算法收敛性要好得多，并且在运算速度以及占用内存方面也有很大优势。参考文献：1张远昌.物流运输与配送管理M.北京:中国纺织出版社，2004.2荣耀华.传
11、统物流与现代物流M.北京:中国物资出版社，2007.3叶耀华，陈霖，朱晓梅.一种带时间窗口和在前约束的车辆路线问题及其算法J.系统工程理论与实践，2000，(3).4程世平.物流管理M.合肥:合肥工业大学出版社，2007.5王凌.智能优化算法及其应用M.北京:清华大学出版社，施普林格出版社，2001.6邢文训，谢金星，等.现代优化计算方法:第 2 版M.北京:清华大学出版社，2005.7Dantizg G，Ramser J.The truck dispatching problem，Management Science，1959，(6):80-91.8李军，郭耀煌.物流配送车辆优化调度理论与方法M.北京:中国物资出版社，2001:11.9Holland J H.Adaption in natural and artificial systems.MIT Press，1975.责任编辑 安世友
