《改进的遗传算法在物流配送中的应用概要.doc》由会员分享，可在线阅读，更多相关《改进的遗传算法在物流配送中的应用概要.doc（2页珍藏版）》请在三一文库上搜索。
1、改进的遗传算法在物流配送中的应用 摘 要 我们在物流配送系统的研究中，对物流配送的数学模型以及所采 用的算法进行了深入的探讨，并取得了一定的成果。遗传算法的改进，一定程 度上避免了早熟现象的发生，提高了遗传算法用于求解物流配送问题的效率。 关键词 物流配送 遗传算法 早熟 种群物流配送是指按客户的订货要求，在配送中心进行分货、配货，并将配好 的货物及时送达客户手中。目前我国大部分物流配送企业，仍依赖人工经验采 用人工安排的方式，从而导致企业运输资源无法充分利用，增加了企业的运行 成本或者根本无法满足客户的要求，从而限制了物流配送企业的进一步发展。 对物流配送优化问题进行深入研究，建立即时反映客
2、户需求的自动化车辆调度 及路线安排系统，是提升服务质量、提高资源利用率、降低企业成本的重要课 题。对一个大型配送中心来讲，客户数量往往很多，要精确计算最优配送路径 是一件非常困难的事，现在有人利用遗传算法来求解配送路径优化问题 , 已经取 得了一些研究成果，但实际应用却不是十分的理想 , 究其原因, 主要是由于传统 的遗传算法 , 存在着局部搜索能力不强 , 容易出现早熟而造成的。为了提高遗传 算法的搜索能力 ,避免在算法进化的早期出现收敛 , 文章对传统的遗传算法进行 了改进，经大量的实验表明 : 改进的遗传算法较传统的遗传算法在物流配送优化 中，求解效率有了非常明显的提高 , 完全能适应网
3、络配送的要求。一、数学模型设配送中心有m台相同的配送车辆要向n个客户配送货物，客户i到客户 j 的距离为 dij ，客户 i 到配送中心的距离为 di0 ，客户 i 的需求量为 qi ，车辆 的最大载重量为乙最大行驶距离为D,最大装载体积为V,成本为CO+kx(其中 x 为距离)，按费用最低为优化目标 , 其数学模型为：。约束条件 :(1) 每台配送车辆的最大行驶距离不能超过 D;(2) 每台配送车辆 的最大装载体积不能超过 V;(3) 配送车辆总数不能超过 m。二、改进的遗传算法1. 遗传算法将每个客户按十进制从 1到 n 进行编号, 随机对换编号的位置 , 组成初始群 体, 计算适应度时，
4、需要在编码的开始和结束位置插入 O, 并在编码之间按车辆 的载重量插入若干0,其中0表示配送中心。遗传运算分别采用联赛选择，循环 交叉(CX)和对换变异。2. 遗传算法的改进定义 1:进化的初期 , 算法的主要任务是全局寻优 , 称这个时期为寻优期。进 化的后期 , 算法的主要任务是局部收敛 , 称这个时期为收敛期。寻优期一般为总 进化代数的三分之二 , 收敛期一般为总进化代数的三分之一。定义 2:设个体 A=X1,X2,Xn- 1,Xn,称 A =Xn,X*1,X2, X1 为 A 的逆 序。改进的遗传算法在寻优期采用较大的交叉和变异概率，在收敛期采用较小 的交叉和变异概率。由于交叉和变异概
5、率只与遗传代数有关，因此不会影响算 法的效率，同时也能较好的抑制早熟现象的发生。交叉运算前，先要对种群两两配对，如果将两个相同的个体进行配对，那 么交叉运算就失去了作用。改进的遗传算法为了避免这种情况的发生，先对种 群进行试配对，若在某次试配中，经几次试配对均不成功，可重新产生一个新 个体，从新个体以及新个体的逆序中选择一个适应度高的个体来替代其中的一 个个体，这样可以保证每对个体它们的基因物质不会完全相同。出现早熟的原因往往是由于种群中出现了某些超级个体，随着模拟生物演 化过程的进行，这些超级个体的基因物质很快占据了种群的统治地位 ，导致种群 中由于缺乏新鲜的基因物质而不能找到全局最优值。改
6、进的遗传算法在进化的 过程中不断用一些新鲜的个体来替代适应度低的个体，使得种群中始终含有新鲜 的基因物质，不至于算法过早收敛，每个新个体可从随机产生的个体及它的逆序 中选择一个适应度高的个体。在寻优期增加的新个体的数量可适当多些（一般 为种群的20%左右），促使算法尽快收敛，在收敛期加入的新个体的数量可适当 少些（一般为种群的5%左右）或不再增加新个体。三、仿真实验实验数据来自文献的实例2，变异概率为0.01,交叉概率为0.8,初始群体 规模为80,总进化代数为200,共进行了 100次实验。从表中可以看到，改进的遗传算法，在不降低速度的前提下，每次实验基 本都可以求出优秀解，说明经改进的遗传
7、算法对物流配送问题的求解能力有了 很大程度的提高。四、结束语遗传算法作为一种优化算法有着广泛应用前景，但同时也存在着很多有待 解决的问题。文章针对传统的遗传算法提出的几项改进措施，一定程度上克服 了早熟现象，增强了对物流配送问题的求解能力。文章作为基本遗传算法的改 进设计，他的优劣性还需要在实践中进一步的检验。参考文献：1 阎 庆 鲍远律:新型遗传模拟退火算法求解物流配送路径问题J.计算机应用，2004,24（S1） 2612632 郎茂祥胡思继:用混和遗传算法求解物流配送路径优化问题的研究J.中国管理科学,2002,10（5）.51563 陈国良 王熙法等：遗传算法及其应用M.北京：人民邮电出版社,2001 年2月761434 何信:多目标物流配送路经优化聚类-遗传混合算法J.商场现代 化,2006 8（上旬刊）总第475期120121本站关键词：毕业论文