一种改进的遗传算法在企业生产调度上的应用.docx

          一种改进的遗传算法在企业生产调度上的应用                    一种改进的遗传算法在企业生产调度上的应用摘 要：本文提出了一种改进的遗传算法来解决生产调度问题即Flow-shop问题，算法采用了交叉变异等遗传操作和保存最优解相结合的方法，保证了最优解的搜索能力和解的全局收敛性实验证明了本算法的可行性关键词：遗传算法；流水车间调度；加工序列：TP311 ：A ：1引言Flow-shop问题可以描述如下：n个工件要被加工，需要经过m道工序（机器）这些机器完成每一个工件的加工需要一定的时间各工件的工序一样，但在每道工序上的加工时间可不相同，当最后一个工件完成时，可得出总的计划加工时间因此，问题的关键就是求得耗费时间最少的加工顺序安排方案根据车间实际情况，做出基本假定：各个工件在每道工序上加工时必须与各个工件的传递序列保持一致2、求解Flow-shop问题遗传算法分析鉴于遗传算法具有并行搜索、鲁棒性强和搜索效率高等优点，本文采用并改进基本遗传算法，合理设计染色体编码、适应度函数、遗传算子、参数选择等1）遗传算法染色体编码遗传算法是基于码串来工作的，算法采用易于理解和操作的自然数编码方式。

编码直接反映了加工顺序，是计算个体适应度的依据例如，对于染色体编码12…6，表示工件加工的顺序是：工件1→工件2→…→工件62）适应度函数对于无限中间存储方式，n个工件m台机器的流水车间调度问题的完工时间可以用数组c表示，令tjik表示工件ji在机器k上加工的时间，令c(ji,k)表示工件ji在机器k上的加工完成时间，则c(j1,1)= tj11，令{j1,j2,…,jn}表示工件的调度，那么有：c(j1,k)= c(j1,k-1) +tj1k ; k=2,…,mc(ji,1)= c(ji-1,1)+ tji1 ; i=2,…,n若tjik≠0则c(ji,k)=max{c(ji-1, k), c(ji,k -1)}+tjik; i=2,…,n ;k=2,…,m若tjik=0则c(ji,k)= c(ji,k -1)最大流程时间为Cmax= c(jn,m)调度目标就是确定{j1,j2,…,jn}，使得Cmax最小[3]取适应度函数Fi=1/Cmax(i)Cmax(i)是第i个染色体所代表的一个调度的最大流程时间约束条件表示同一工件必须按工艺顺序在前一台机器上加工后才能进入下一台机器，并且同一台机器加工完前一个工件才能开始下一个工件，根据此模型可编制好时间计算程序，计算出每条染色体所代表的加工总时间。

3）选择算子选择就是用适应性强的个体替代适应性弱的个体，本文采用赌轮盘[1]方式来实现选择算子，其基本思想是：各个个体被选中的概率与其适应度大小成正比 （4）交叉算子交叉是最主要的遗传操作本文在顺序交叉基础上作了一些改进，产生子代的方法是：取父代p1的r位后的部分放到p2之后生成m2，取p2的r位后的部分放到p1之后生成m1，再从m1前部开始逐个删去匹配部分包含的基因得到子代c1，同样从m2前部开始逐个删去匹配部分包含的基因得到子代c2r,r1, r2为随机数)p1=73281465；p2=51437682；r=5；m1=73281465|682；m2=51437682|465；c1=73145|682； c2=13782|465；（5）变异算子变异的目的是产生(创造)解群体的多样性，变异的本质就是产生(创造)出新的基因设选取的父代个体为p1，只需将父代个体p1编码的第r1位与第r2位的基因互换, 得到子代c1p1=73281465；r1=2； r2=5；c1=71283465；（6）反转算子将父代个体p编码的r1至r2位之间的部分顺序颠倒得到中间个体m再对中间个体m与父代个体比较，如果m比父代个体优则用个体m替代父代个体。

p=7|3281|465；r1=2； r2=5； m=7|1823|465（7）算法描述算法描述如下：step1：初始化,确定群体规模N,变异概率pm,交叉概率pc, 反转概率pi，迭代次数g,随机产生一个均匀分布的初始群体;step2：计算每个个体的适应度;step3：取4个最优的个体保存起来;step4：迭代次数g为0则转到step11;step5：进行选择操作;step6：以交叉概率pc进行交叉操作;step7：以变异概率pm进行变异操作; step8：计算子代每个个体的适应度; 并以反转概率pi进行反转操作;step9：取子代中4个最优的个体与父代的4个最优个体比较,从8个中取4个最优的个体保存起来;step10：迭代次数g减1, 转到step4;step11：输出最优个体及其适应值;3、仿真实例仿真实验是在Intel P4 1.7G CPU,256MB内存计算机上进行，程序用VC++编制计算中采用的有关数据如下：群体规模20，交叉概率0.8，变异概率0.003，反转概率0.5，群体更新50代结束适应度函数Fi=1/Cmax(i)以某零部件加工车间为例，设一个5个工件，5台机器的生产加工调度问题，工件的加工时间如图1所示，i表示第i个工件,k表示第k道工序。

将时间矩阵送入遗传算法模块进行计算，返回计算结果，程序运行效果如表1所示程序运行时间不到半秒　　 | 14 12 14 12 10 | | 12 14 10 10 10 | T(i,k)= | 12 16 10 10 00 | | 14 12 09 00 12 | | 14 10 10 14 12 | 图1工件的加工时间 表1 遗传算法运行效果方案 工件加工顺序 总工时1 1-3-5-2-4 992 1-2-5-3-4 993 5-1-2-3-4 1014 2-5-1-3-4 1014、结束语本文改进了遗传算法来解决实际生产中的调度问题，算法采用了丰富的局部搜索方式和保存最优解相结合的方法，较好地把握了局部搜索与全局搜索之间的平衡实验表明了算法的有效性和实用性Reference:[1]史忠植.知识发现[M].北京:清华大学出版社,265-294[2]周根贵.数据仓库与数据挖掘[M].浙江大学出版社[3]柳毅等.利用DNA遗传算法求解Flow-shop调度问题[J].计算机工程与应用,2005.17:85-87（作者单位：河北北方学院计算机系）  -全文完-。