找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

遗传算法求解车间调度问题(附MATLAB代码)

admin 2019-10-13 06:00 150人围观 C++相关





首先声明本文参考数据魔术师公众号的《遗传算法求解混合流水车间调度问题(附C++代码)》和《MATLAB 智能算法30个案例分析》


今天小编为大家讲解遗传算法求解车间调度问题。小编最开始接触的智能优化算法就是遗传算法,刚开始学习的时候小编查阅了网上各种讲解遗传算法的教程,最后还借了一本关于遗传算法的书籍,现在想想当时是多么的蠢,网上看教程的时候看了各种概念、各种流程和各种改进方法,看了一段时间依然是不会用,于是小编痛定思痛,买了一本《MATLAB 智能算法30个案例分析》的书籍(注意小编不是为这本书做广告),最主要的是这本书里面有现成的MATLAB代码,其实学习任何代码小编觉得都是先模仿再超越,如果最开始的时候就能自己编出来,那小编只能佩服。



废话不说,接下来小编带大家快速入门遗传算法。

文章目录:

1. 关于遗传算法的一个小故事

2. 遗传算法操作流程

3. 车间调度问题描述

4. 遗传算法求解车间调度问题方法

5. matlab源代码分享


1. 关于遗传算法的一个小故事

无论是遗传算法,还是什么其他智能优化算法无非都是一个框架,目的都是搜索某一问题的“最优解”,这里为什么加双引号,因为这类智能优化算法都有一个缺陷,那就是搜索的过程中容易陷入“局部最优”。

给大家举个生动形象的例子先让大家对遗传算法有一个直观的感受,比如说有6只公鸡5只母鸡1000米赛跑,第1个100米,2只公鸡2只母鸡分别位于前四名,这时剩下的4只公鸡3只母鸡肯定要想办法追上前面4只鸡,于是就想出“交叉”和“变异”两种方法,1只公鸡和1只母鸡“交叉”孕育出1个公鸡仔和1个母鸡仔,孕育结束后父代和母代不幸罹难,一共有3对鸡能通过“交叉”的方式繁衍出后代,那剩下的1只公鸡怎么办,这只公鸡发生基因突变,也就是“变异”成一只新的公鸡了.(大家请注意前4名的鸡没有发生变化,后7名的鸡发生“交叉”和“变异”后,鸡的总数还是11);第2个100米,同样还是有2只公鸡和2只母鸡位于前四名,只不过这里的前四名可能已经不是第1个100米前四名的那4只鸡,同样剩下的7只鸡依然进行“交叉”和“变异”,目的是能让自己跑得更快;……;一直到第10个100米,最后冲刺阶段,毕竟是赛跑理论上来说只能有1个冠军(不考虑并列第一),那么最后夺得冠军的那只鸡就是跑得最快,这只鸡可能是一开始的那11只鸡的一只,也可能是经过某些鸡之间“交叉”和“变异”繁衍出来的,总之这只鸡是最强的。这其实就是所谓的“优胜略汰”,跑得慢的鸡会被淘汰,只不过在淘汰之前会完成繁衍。


2. 遗传算法操作流程

接下来给出遗传算法的框架:

1、初始化:依据每个种群的特征随机生成第一代种群的全部个体;

2、求个体适应度:计算每个个体的适应度;

3、选择过程:依据一定的选择规范,选出一部分优秀个体参与交叉和变异操作;

4、交叉过程:群体中两两配对,交换部分染色体基因,完成交叉操作;

5、变异过程:随机改变个体中的部分基因,来实现变异操作;

6、终止判断:若新一代种群满足终止条件,停止算法迭代,记录此时的最优解为问题的最优解;否则,迭代次数加1,返回步骤2;





3. 车间调度问题描述

车间调度是指根据产品制造的合理需求分配加工车间顺序,从而达到合理利用产品制造资源、提高企业经济效益的目的。车间调度问题从数学上可以描述为有n个待加工的零件要在m台机器上加工。已知各工件的加工时间,优化目标是如何确定工件的加工顺序以及每阶段工件在机器上的分配情况,使得最大完工时间极小化。


4. 遗传算法求解车间调度问题方法

1.个体编码

当待加工的工件总数为k,工件ni的加工工序共为mj时,则个体表示为长度为

,染色体前半部分表示所有工件在机器上的加工工序,后半部分表示工件每道工序的加工机器序号。如个体



该个体表达了4个加工工序都是2次的工件在3台机器上的加工顺序。其中前8位表示工件的加工顺序,为工件2->工件4->工件3->工件1->工件1->工件2->工件3->工件4;9到16位表示加工机器,依次为机器2->机器1->机器3->机器3->机器2->机器2->机器1->机器3。

2. 适应度值

染色体的适应度值为全部工件的完成时间,适应度值计算公式为



其中,time指全部任务完成时间。全部工件完成时间越短,该染色体越好。

3. 选择操作

采用轮盘赌法选择适应度较好的染色体,个体选择概率为



其中,

表示染色体i在每次选择中被选中的概率

4.交叉操作

交叉操作首先从种群中随机选取两个染色体,并取出每个染色体的前

位进行交叉。操作方法如下:交叉位置为5,只对个体前

位进行交叉。



交叉后某些工件的工序多余(子代1的工件2,子代2的工件3),某些工件的工序缺失(子代1的工件3,子代2的工件2),因此,把工件工序多余的操作变为工件工序缺失的操作,并按交叉前个体的操作机器来调整后一半的加工机器。

5. 变异操作

变异算子首选从种群中选取变异个体,然后选择变异位置pos1和pos2,最后把个体中pos1和pos2位的加工工序以及对应的加工机器序号兑换,如下所示,变异位置为2和4。





5. matlab源代码分享(后台回复“GA车间调度”提取代码)

链接:https://pan.baidu.com/s/1CdfOSZlsdwPkk3NJo7gMDQ

提取码:2egc


----------------------------------------------------------------------------------------------------------------------
我们尊重原创,也注重分享,文章来源于微信公众号:优化算法交流地,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
----------------------------------------------------------------------------------------------------------------------

鲜花

握手

雷人

路过

鸡蛋

yafeilinux和他的朋友们微信公众号二维码

微信公众号

专注于Qt嵌入式Linux开发等。扫一扫立即关注。

Qt开源社区官方QQ群二维码

QQ交流群

欢迎加入QQ群大家庭,一起讨论学习!

我有话说......