基于改进遗传算法的混合车间调度问题研究1(21)

基于改进遗传算法的混合车间调度问题研究

基于改进遗传算法的混含卞问生产调度问题研究

式有３种：基因重组，基因突变和染色体变异．基因重组是控制物种性状的今音发生重新组合。基因突变是指基因分子机构的改变。染色体变异是指染色体在

’

机构上或数目上的变化。

２．３．２遗传算法的基本流程

遗传算法是一类随机优化算法，但它不是简单的随机比较搜索，而是通过对染色体中基因的作用，有效地利用已有信息来指导搜索有希望改善优化质量的状态。标准遗传算法的主要步骤可以描述如下：

（１）随机产生一组初始个体构成初始种群，并评价每一个体的适配值

（ｆｉｔｎｅｓｓｖａｌｕｅ）。

（２）判断算法收敛准则是否满足。若满足的输出搜索结果；否则执行以下步骤。

（３）根据适配值大小以一定方式执行复制操作。

（４）按交叉概率ｐ，执行交叉操作。

（５）按变异概率ｐ，执行变异操作。

（６）返回步骤（２）。

上述算法中，适配值是对染色体（个体）进行评价的一种指标，是ＧＡ进行优化所用的主要信息，它与个体的目标值存在一种对应关系；复制操作通常采用比例复制，即复制概率正比于个体的适配值，如此意味着适配值高的个体在下一代中复制自身的概率大，从而提高了种群的平均适配值；交叉操作通过交换两父代个体的部分信息构成后代个体，使得后代继承父代的有效模式，从而有助于产生优良个体；变异操作通过随机改变个体中某些基因而产生新个体，有助于增加种群的多样性，避免早熟收敛。

标准遗传算法流程图描述，如图２．１所示。

遗传算法的基本流程如下所示：

Ｉｎｐｕｔ￡＝ＣｒｏｓｓｏＶｅｒＰｒｏｂａｂｉｌｉｔｙ

只＝ＭｕｔａｔｉｏｎＰｒｏｂａｂｉｌｉｔｙ

Ⅳ＝ＰｏｐｕｌａｔｉｏｎＳｉｚｅ

Ⅳ二。＝ＭａｘｉｍｕｍＮｕｍｂｅｒ

Ｂｅｇｉｎ、．ｏｆＧｅｎｅｒａｔｉｏｎｓ

ｆ＝Ｏ；

Ｉｎｉｔｉａｌｉｚｅ

ＥＶａｌｕａｔｅｐ（ｆ）ｐ（ｆ）

Ｗｈｉｌｅ（Ｎｏｔｔｅｒｍｉｎａｔｉｏｎｃｏｎｄｉｔｉｏｎ）

｛ｆ＝ｆ＋１