基于GA的调度算法中最关键是对各个算子的设计，包括染色体编码、适应度函数、选择算子、交叉算子和变异算子。
1.染色体编码
对于一个Petri网（本文是其子类DTPN），若存在激发序列σ=t1，t2，…，tn-1，tn，使得m0[σ＞mf，则σ是一条染色体，其中m0是初始标识，mf是结束标识，t1，t2，…，tn-1，tn∈T。
2.适应度函数
采用多目标优化定义适应度函数，定义f3=w1f1+w2f2，其中f1表示整个加工工程中的重组费用。Petri网模型中重组相关变迁的发生将可能改变加工工序的加工状态，根据染色体的变迁序列和生产线的初始状态和上述4.2.1一节中的计算方法可以计算得到f1；f2表示E/T约束惩罚函数，根据DTPN，从染色体σ可以计算出每个工件的加工完成时间。从而同样根据4.2.1小节中的计算方法计算得到f2。w1，w2表示不同的目标优化权重，本书中w1，w2均为0.5。
由于遗传算法要求越好的解有越大的适应度，因此，取适应度函数为：
其中，Cmax是一个合适的输入值。
3.选择算子
采用期望值方法作为选择算子。即群体中每一个个体在下一代生存的期望数目为：
其中，n为父代群体的数量。
4.交叉算子
（1）将群体中的染色体随机配对，设σ和σ′为配对的两条父染色体。
（2）按照σ和σ′所代表的激发序列对转移逐个激发，生成中间Mark。
（3）在σ和σ′中查找具有相同Mark的基因座，并将每一对具有相同Mark的基因座记录下来。
（4）在查找到的具有相同Mark的基因座对中，随机选取一对，将初始状态与这对基因座之间的基因片断（即激发序列）进行交换。
图4-3 交叉算子流程图
图4-3为交叉算子流程图。图4-4为染色体交叉过程，父代染色体σ和σ′有两对基因座对应的Mark相同，即Ma=M′a以及Mb=M′b，经随机选择，选取（Mb，M′b）这对基因座，然后交换初始状态与这对基因座之间的基因片断。
(www.xing528.com)
图4-4 染色体交叉过程
注：M0，M′0是Petri网模型的初始状态。
5.变异算子
由于采用激发序列作为染色体编码，若随机改变激发序列中的一个转移，极有可能会导致该染色体为不可行解。本书采用在进行变异时就保证不会产生不可行解的方法，变异流程图如图4-5所示，算法步骤如下（其中，Open Table、CloseTable和Result Table表示存放Mark及其属性的表）：
（1）初始化，Open Table清空，CloseTable清空，Result Table清空。
（2）从染色体σ中随机选择一个基因座，将该基因座所对应的Mark放入Open Table。
（3）如果Open Table不空，转（4），否则转（9）。
（4）从Open Table中移去第一个标识m且放入到CloseTable上。
（5）若m是目标标识，则放入Result Table中。
（6）找出标识m下使能的变迁。
（7）对于每一个使能的变迁，产生其后续标识，并设置所有从后续标识到m的指针。计算后续标识m′的g（m′）、h（m′）和f（m′）。
（8）将m′放入Open Table中，并且根据f（m′）的递增顺序，重新排列Open Table中的标识的顺序，选取前N个标识，然后转到（3）。
（9）从Result Table中取出每一个标识，得到生成该标识的转移和父标识，如此递归得到一个激发序列，从中取出满足时间约束条件并且适应度值最优的激发序列，然后转到（10）如果不存在满足时间约束条件的激发序列，转到（11）。
（10）将染色体σ的变异基因座之前的激发序列与第（10）步中得到的激发序列连接，得到新染色体σ′，该染色体即为变异后的染色体。变异结束。
（11）如果运行次数小于K，转到（2），否则，转到（12）。
（12）此次变异操作失败。
上述算法中，f（m）=g（m）+h（m）。f（m）为成本估计，g（m）为上述“与算法相关的主要参变量定义”一节中定义的f3，h（m）为从标识m到目标标识的最优路径的成本估计，本书中h（m）=-dep（m），其中dep（m）是标识m在可达图中的深度，即从初始标识到达标识m的激发变迁的次数。
图4-5 变异算子流程图
由于变异算子只是遗传算法迭代过程中的一步，上述变异算子中的N和K不宜取太大，否则影响遗传算法的效率。此处推荐N=5，K=5。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
