APS算法分析之五基因算法

1、APS算法分析之五基因算法基因算法GA(GeneticAlgorithm)是基于自然系统的进化过程，算法创立一初始化方案的人种，基于初始化方案，算法再产生新的一个人种，通过许多代的连续过程，方案的质量被改善，算法结束于当达到一特别的中断规则(如.当加工时间已经达到)，它实际上是随机搜寻算法。它已经用于许多优化问题，如销售员旅行问题，货柜包装问题，排程问题，顺序问题，设施布局问题等。和本地搜索策略不同的是，GAnTabu搜索(TS)在搜索中比较一最较差的目标函数值，接受临时的方案来克服本地优化，找到全局优化。然而，因为，GA和TS是探索法，可能不是最佳的方案，但是，大部分情况下，至少可以找到一个

2、非常好可行的方案。GA是随机搜寻算法，因为用较差目标函数值的方案用特别的可能性是可以接受的。因此，用一个一样的初始方案开始，和一样的参数设置，也可能导致不同的方案。而用确定性搜索算法如TS就会导致同样的方案。基本概念：人种保持在内存为进一步改善的一列数字集，新列数字使用特别的基因运作产生。选择是根据它们的适应性来选择出“父代”基本基因运作： 复制 交叉 变异一人种的数字串选择可以用一特别的数字串的进化函数产生后一代。进化函数反映染色体的“适应”。比如：在车间流水线排序问题 N任务必须在M机器排程 每一任务包含m工序 每一工序需要不同的机器 所有任务在同样的加工订单上处理特别假设：1 ,所有任务

3、在零时间可以得到2 ,工序的准备时间包含在加工时间里3 ,对所有机器所有工序的顺序已定义4 ，目标：最小化时间跨度GR-案例2个任务，5T工序和7台机器：- 图不：123452345(12024£«1012- 准备时间和加工时间用方格的长度来表示.如,在第2台机器，工序1和工序4有W小时;工序2,3,和工序5杳1小时- 总时间跨度是口2345）：12小时GA-案例初始化人(第一代)：-4排列 1W452Q跨度11 12345整度12 24531跨度：13 23541-=跨度：15 选择:选择那一事仁科例)用作犍代.=二适应函数二适度值排列的范围适应函数：对一人种的目标函数值

4、的所有成员，如计算跨度。从这个较低的跨度被决定和得到最高的适应值fmax.,从不同的人种结果中的每一成员的适应值到它的前辈的索引清单中的适应值。这个作法就保证了为一较低跨度的排程选择的可能性是高的。缩减规模d影响到选择的可能性。必须的条件是：fmin>0.适应值(用fmax=20,d=5=>fmin=5):* f(13452)=20* f(12345)=15* f(24531)=10* f(23541)=5* 整个人种的适应值：50(在人种里的所有个体的适应合计)复制/选择大部分公用的复制/选择概率是给定的。是排列的适应值和共计种群的适应值的商*我们的案例，我们得到* 概率（134

5、52）=20/50=0.4* 概率（12345）=15/50=0.3* 概率（24531）=10/50=0.2* 概率（23541）=5/50=0.1在下一代里，保留一个复制操作者选择的机会。它是成比例列出适应。就像排列的选择如一个孩子一个父亲。用较低跨度排列，比那些用低的适应值有一较高生存/选择可能性。那么（0,1）-随机变量产生，如果低于0.4,那么排列选择13452,如果在0.4和0.7,之间，那么12345被选择。如果在0.7和0.9之间，那么24531被选择，如果大于0.9,那么排列23541被复制。交叉 选择两个父项结构，从选择的个体中 产生一二进制串m长度 对子项1:拿所有父项1

6、的位置，在二进制串里用“1”，对子项2:拿所有父项2的位置，在二进制串里用“0” 父项1的其它因素被存，作为在父项2里出现时。然后，他们被插入子项1的自由位置。对子项2也是同样的过程。例如： 选择12345（父项1）和24531（父项2） 二进制字串：01101 子项1:-23-5;子项2:2-3- 子项1:42315;子项2:21435有许多不同交叉操作者。这里，“基于同样订单的交叉”被显示。父项1:1-4->在父项2出现：4-1-父项2:-45-1->在父项1出现1:-14-51 .选择一个体的父项2 .选择随机两个位置，在这个父项排列中3 .在这个间隔里的新顺序值是随机产生的。如父项:12345两个位置：2和4老的顺序：234->新顺序：423=>新排列J:14235GA.总结Ooo°OOOOOO00- k代- 在k代里为复制选择排冽- 在k代里为交叉选择排列- 在k代里为变异选择排列- 在k代里不选择排列,中止条件：