大数据中遗传算法求解车间调度问题的示例分析

这篇文章主要介绍大数据中遗传算法求解车间调度问题的示例分析，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！

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

给大家举个生动形象的例子先让大家对遗传算法有一个直观的感受，比如说有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。

以上是“大数据中遗传算法求解车间调度问题的示例分析”这篇文章的所有内容，感谢各位的阅读！希望分享的内容对大家有帮助，更多相关知识，欢迎关注亿速云行业资讯频道！