单亲进化遗传算法在配送中心选址中的应用

1、-580-1引言随着市场经济体制的日臻完善和我国加入WTO ,我国的物流业得到了迅猛发展。在物流系统中,配送中心或流通中心、仓库、销售店等设施设置地点的选择是物流系统优化的一个具有战略意义的问题,其中配送中心的位置显得更加重要。物流配送中心是货物从制造商、厂商至零售商之间的中间贮存据点,是集中和分散、促进货物迅速流转的仓库。不同地区、不同品种的货物通过物流中心的调节与保管,按不同需求重新组合,发往收货者手中。配送中心地址的合理选择,不仅可以缩短配送距离,加快配送速度,降低配送成本,提高服务质量,而且可以促进生产和消费两种流量的有机协调与配合,使整个物流系统处于平衡发展的状态。由于配送中心在物流

2、系统中所处的重要地位,大批科研人员对这一问题展开了深入细致的研究,建立了一系列的选址模型与算法,这些模型及算法实现起来相当复杂。因此,在解决实际配送中心选址问题时,往往借助于启发式算法来达到或非常接近最优解。在运用遗传算法进行选址的研究中,现有的研究成果大都运用传统的遗传算法,使用PMX 、CX 、OX 等交叉算子,这些算子不仅实施起来很困难,而且要求要有多样性的种群,很容易在最优解附近早熟收敛。鉴于这种原因,本文使用一种新的改进遗传算法单亲进化遗传算法,提出对备选地址已定的选址模型,使用单亲进化遗传算法,实现各点间往返路径最优化,使备选的任意两点彼此到达对方的总费用最少;然后以优化的路径表示

3、为父体,从各基因所在的结点为起点,截取所有基因片段,求以各基因为起点的基因片段值总和,选取最佳基因片段组合,结合各点固定建设费,确定配送中心最佳地址。这一算法对于改进物流系统布局,提高物流系统科学决策水平具有一定意义。2PEGA 简介近年来,TGA (traditional genetic algorithm 即传统遗传算法发展迅速,具有运算简单、收敛速度快等优点,但仍存在对复杂问题搜索效率低,易陷入“早熟收敛”等缺点。本文使用的遗传算法是一种改进的单亲遗传算法,所有的进化过程均在一条染色体上进行,它采用“路径表达”的序号编码方式,利用父体所提供的有效边的信息,使用保留最小边的方法进行个体进化

4、。收稿日期:2004-06-07。基金项目:国家自然科学基金项目(10171095;国家863计划基金项目(2002AA103061。作者简介:祝延军(1973-,男,山东临清人,硕士,研究方向为近似算法;胡纯德(1973-,男,湖北洪湖人,硕士,研究方向为近似算法;高随祥(1962-,男,陕西延安人,教授,博士,研究方向为组合最优化。2005年3月计算机工程与设计Mar.2005第26卷第3期Vol.26No.3单亲进化遗传算法在配送中心选址中的应用祝延军,胡纯德,高随祥(中国科学院研究生院,北京100039摘要:为更好地实现配送中心优化选址,在分析物流配送中心的作用及现存的用传统遗传算法进

5、行选址的基础上,提出应用单亲进化遗传算法求解选址模型。首先,利用父体所提供的有效边的信息,使用保留最小边的方法对个体进行进化,求得费用最低的优化路径;然后以优化路径作为父体,求解从各基因为始点的基因片段值之和,选择最佳基因片段组合,得到问题的解,该算法可以有效、快速地求得配送中心选址问题的全局最优解。关键词:单亲进化遗传算法;基因片段组合;配送中心;优化选址中图法分类号:TP301文献标识码:A 文章编号:1000-7024(200503-0580-03Application of partheno evolution genetic algorithm in location of dist

6、ribution centerZHU Yan-jun,HU Chun-de,GAO Sui-xiang(Graduate School of Chinese Academy of Sciences,Beijing 100039,China Abstract :To better optimize location of physical distribution center.On the basis of analyzing the function and existed location method of physical distribution centre by TGA (tra

7、ditional genetic algorithm ,it is put forward to use PEGA (partheno evolution genetic algorithm to solve location model.At first,PEGA utilizes effective limbic information from father-body,uses the way of preserving the least limbic to evolution and gains optimal path which transport costs is the lo

8、west.Secondly,using the gained optimal path as father -body,the sum of genetic paragraphs is worked out which comes from the same gene,the best combination of genetic paragraph is selected and reachs the solution of the problem is given.It can effectively and fast get the best overall solution.Key w

9、ords :PEGA;combination of genetic paragraph;distribution centre;optimal locationComputer Engineering and Design-581-我们引用文献5中的两个概念,对PEGA 算法基本思想阐述如下。概念1在PEGA 中,按一定方式移动一条染色体上某些位置的基因过程,被移动的基因的位置是随机产生的,称为基因换位操作。概念2基因分组定界操作:按一定的阈值,进行路径拆链,形成一个个子串,各子串之间的路径长度一定大于阈值。传统遗传算法中的交叉算子和变异算子,主要考虑结点(区域的相对位置与次序,而忽略了连接结

10、点的边。根据文献11,结点所处的位置并不重要,而它与其它结点相连所组成的边可以为我们构造更好的解指明方向。可见,连接结点之间的边非常重要。PEGA 算法尽可能地利用父体所提供的有效边的信息,使用保留最小边信息的方法进行个体优化。3配送中心选址模型及选址实现3.1问题描述给定某一地区备选物流配送中心及其所属仓库的地址集合,要求选出一定数目的地址建立配送中心,其它剩余地址设置配送中心所属仓库,从而建立一个完备优化的配送区域,实现配送中心到仓库间的物品配送,使得在选出地点建立的配送中心与各仓库形成的配送系统总配送费最低。其中假设系统满足如下一些条件:所有设定的地址区域都具备优越的交通、运输、信息等条

11、件;所设各区域的配送资源情况一样;物流中心容量可以满足各仓库的需求;仓库需求的物品一次运输完成,所在点对间运输速度一样,均为常数;系统总费用只考虑固定设施建设费用及管理费用、运输途中的运输费用。假定有n 个备选地址,已确定从中选出m 个配送中心S 1,S 2,S m 现欲求m 个最佳地址作为配送中心,以使总配送费用最小,则有规划模型如下4:min+ 1=+2,+ 1=1,2, ,+1, 容量+1+1=1,2,= 设置费+1¿ªÊ¼YN设置进化代数,并定为终止条件(如N=5000N>5000按以下步骤获得运输费用最少的优化路径Step1机产生初始种,

12、并机产生未匹配的父体;Step2在父体中机产生子串,进行基因们操作;Step3基因分组定界;Step4基因换位,定最优后代输出最佳染色体,即获得运输费用最低的优化路径按以下步骤的定配送中心的最佳地址Step1最优后代为父体,求各基因为点基因片段值之和;Step2选择最佳基因片段组合,定配送中心最佳地址输出最佳基因所在的结点,获得问题的解表111个区域之间的运输费用表示12345678910111020192982033821222922302321252737125140402119372210717332730802121379049261001211径表示”的序号编码方式如下:步骤2在父体

13、中随机产生一个子串,进行基因换位操作。如:P:125|6983|471011生成的子代为C:6983125471011步骤3基因分组定界。首先根据表1,判断父体染色体中各个基因(区域所构成的边的大小,选出最大边长(MAX、最小边长(MIN并算出平均边长(AVE,按公式ave=(MAX+4AVE+MIN/6对这3类边长进行加权平均,所得值作为阈值。然后,保留最小边,并将大于阈值的边进行破坏,即基因分组定界操作。在此例中,最大边长是37,最小边长是10,平均边长是23,所以得阈值ave=23 (这里做取整计算,以下同。所以破坏6和9、8和3、5和4、4和7、7和10之间的边。P1:6|98|312

14、5|4|7|1011步骤4基因换位,确定最优后代。鉴于传统遗传变异算子常常收敛于最优点附近,而达不到最优点,导致种群早熟、进化陷于停滞的情况,很自然的想法就是在最优点附近采样,从中找到新的点,其适值比当前最优点往往要好。所以,在这一步骤中,对标记后的染色体,我们采用邻域技术,将各个子串作为新的基因(或基因片段进行换位,产生不同的基因组合,评估所有的新个体,选出最好的作为后代。步骤5返回步骤3,循环直到满足结束条件(即达到进化代数或得到最优解为止。步骤6得到最优后代。所得路径上总的运输费用为157。步骤7指定所得最优后代为父体,求解以各基因为起点截取的基因片段值总和。求解基因片段总和的方法,如表

15、2所示。步骤8选取最佳基因片段组合,结合各点固定建设费,确定配送中心最佳地址。经步骤7,选择基因片段总值与固定建设费之和(见表3最小的基因所在的地址,作为配送中心最佳地址。如在本例中,要从11个地址中选择1个配送中心,我们就从父体P2中选择基因7;如果要选择3个配送中心,我们就从中选择基因7、2、4;其余各基因所在的结点可设置为配送中心所属仓库的地址。4.2实验分析为了说明该算法的可靠性和有效性,并能够直观反映出它的遗传进化特征,我们对文献4运用的算例进行了测试。算例如下:有一物流网络,从12个结点中选出3个作为配送中心的地址,各点(从1到12设置配送中心的费用各为11、16、14、14、15

16、、13、18、12、11、14、16、11个单位;各结点的距离如表4所示。用本文的算法,与用文献4运行得到同样的结果相比,本文运行速度比文献4快数十倍;再仍用其算例,将上述数据随机产生20组10到20之间的数作为结点之间的运输费用,每组用本文算法进化20代,有97%达到最优解;同样的运算操作,文献4的算法仅有50%达到最优。可以看出,PEGA是一种更有效的求解物流配送中心选址问题的全局最优解的更好算法。5结论物流配送中心在物流网络中起着非常重要的作用,合理选择物流中心地址,可以节约费用,促进系统优化,提高服务质量,能使综合效益不断提升。本文应用单亲进化遗传算法,结合确定性配送模型构造了求解配送

17、中心优化选址的新方法,这一方法所有的进化过程均在一条染色体(单亲父体上进行,表2以基因3为起点的基因片段统计基因片段基因片段值3119391239530395448395425639542764395427881395427861003954278611110 395427861110122 3954278611101138基因片段值总和780表3统计综合费用247611001576378012001980449211001592556417002264658611001686747610001476851011001610964812001848表4配送点间距2056545771091050

18、7810101312960649106670295498010627904613100491105120(下转第662页-582-tHandlerNextNext先用SQL语句将实验标准的实验目的从数据库中搜出来,这样我们就可以得到实验目的的数目,NumRows就是这个数目;同时可以算出表格的行数(因为表格的列数是两列。然后用两个FOR循环,分别添加TableRow和TableCell,这样我们就可以把表格动态画好。然后我们又用两个FOR循环对画好的每个单元格动态添加CheckBox控件,每个CheckBox控件的Text属性就是每个实验目的项。根据需要,每按压一下CheckBox控件就要在表

19、格的右端显示本实验目的对应的实验项目,也就是说要对每个Check-Box控件编写Click事件。因为CheckBox控件是动态添加的,因此对应的Click事件不能自动生成。我们可以用AddHandler objCB.CheckedChanged、AddressOf EventHandler语句动态添加Click事件,当点击CheckBox控件时,系统会自动运行这一段代码。Click事件要完成的功能由方法EventHandler来完成,我们只需编写方法EventHandler的代码。5结束语本文介绍的冰箱测试管理系统现正用于海尔企业内部网,极大地方便了研发部门、质量管理部门、实验部门之间的沟通和

20、协作,满足了国际化大企业高速发展的需要。该系统借鉴了以往管理系统与测试系统的优点,在性能和功能上都有很大改进,为同类系统提供了良好的范例。该系统不仅可用于电冰箱、家电产品的测试管理,而且可用于大型工厂、酿酒厂、食品加工厂的温度测试管理,有着很广阔的应用前景。参考文献:1甘勇,宋寅卯.全数字网络化冰箱制冷性能分布式计算机测试系统的设计J.郑州轻工业学院学报,2002,17(2:79.2刘勇,郭忠文.一种C/S与B/S相结合的电冰箱抽样测试系统J.计算机工程与设计,2003,24(9:14-15.3郭忠文,贾忠伟,唐功友.基于Intranet的冰箱抽样测试系统J.计算机工程,2002,28(9:1

21、79-181.摆脱了传统遗传算法运用交叉算子的麻烦,利用父体所提供的有效边的信息,使用保留最小边的方法进行个体优化。与传统的遗传算法相比,弥补了不足,简化了算法。实验证明了该算法应用于物流配送中心优化选址问题上的有效性。参考文献:1金若南,张文杰.现代综合物流管理M.北京:中国铁道出版社,1994.167.2许哲荣,胡黄德.国际物流研讨会论文集:A集C.多产品配送中心场址规划与选择,1999.3Bagley J D.The behavior of adaptive system which employ ge-netic and correlation algorithmsJ.Dissertarion Abstracts Inter-national,1967,(28:2.4姜大立,杜文.基于遗传算法的物流配送中心选址模型J.实用物流技术,1997,(5:4.5马欣,朱双东,杨斐.旅行商问题的一种改进遗传算法J.计算机仿真,2003,20(4:366潘正君,康立山,陈毓屏.演化计算M.北京:清华大学出版社,1998.7王战权,杨东援,汪超.配送中心选址的遗传算法研究J.物流技术,2001,(3:11-14.8贺国先,刘凯.优化物流中心配送方案的遗传算法J.系统工程理论与实践