《 ERP高级计划》书的解读-APS算法分析之五基因算法 GA（蔡颖）

基因算法 GA （Genetic Algorithm)是基于自然系统的进化过程，算法创立一初始化方案的人种 ，基于初始化方案, 算法再产生新的一个人种，通过许多代的连续过程，方案的质量被改善 ，算法结束于当达到一特别的中断规则  (如. 当加工时间已经达到)，它实际上是随机搜寻算法 。

它已经用于许多优化问题，如销售员旅行问题，货柜包装问题，排程问题，顺序问题，设施布局问题等。

和本地搜索策略不同的是，GA和 Tabu 搜索 (TS) 在搜索中比较一最较差的目标函数值，接受临时的方案来克服本地优化，找到全局优化。然而，因为，GA 和TS 是探索法，可能不是最佳的方案，但是，大部分情况下，至少可以找到一个非常好可行的方案。

GA是随机搜寻算法，因为用较差目标函数值的方案用特别的可能性是可以接受的。因此，用一个一样的初始方案开始，和一样的参数设置，也可能导致不同的方案。而用确定性搜索算法如TS就会导致同样的方案。

基本概念：人种保持在内存为进一步改善的一列数字集 ，新列数字使用特别的基因运作产生。 选择是根据它们的适应性来选择出“父代”

基本基因运作：

• 复制

• 交叉

• 变异

一人种的数字串选择可以用一特别的数字串的进化函数产生后一代。进化函数反映染色体的“适应”。

比如：

在车间流水线排序问题

• N 任务必须在 M 机器排程

• 每一任务包含 m 工序

• 每一工序需要不同的机器

• 所有任务在同样的加工订单上处理

特别假设 :

                       1，所有任务在零时间可以得到

                       2，工序的准备时间包含在加工时间里

                       3，对所有机器所有工序的顺序已定义

                       4，目标: 最小化时间跨度

适应函数:

对一人种的目标函数值的所有成员，如计算跨度。从这个较低的跨度被决定和得到最高的适应值fmax.，从不同的人种结果中的每一成员的适应值到它的前辈的索引清单中的适应值。这个作法就保证了为一较低跨度的排程选择的可能性是高的。缩减规模d影响到选择的可能性。必须的条件是： fmin > 0.
适应值 (用 fmax=20, d=5 => fmin=5):
*f(13452) = 20
*f(12345) = 15
*f(24531) = 10
*f(23541) = 5
*整个人种的适应值: 50 (在人种里的所有个体的适应合计)
　

复制 / 选择

• 大部分公用的复制/选择概率是给定的。是排列的适应值和共计种群的适应值的商

• 我们的案例, 我们得到

*概率(13452) = 20/50 = 0.4
*概率(12345) = 15/50 = 0.3
*概率(24531) = 10/50 = 0.2
*概率(23541) = 5/50 = 0.1

在下一代里，保留一个复制操作者选择的机会。它是成比例列出适应。就像排列的选择如一个孩子一个父亲。
用较低跨度排列，比那些用低的适应值有一较高生存/选择可能性。
那么 (0,1)-随机变量产生，如果低于 0.4, 那么排列选择 13452，如果在 0.4 和 0.7, 之间，那么 12345 被选择。如果在0.7 和0.9之间, 那么 24531被选择，如果大于0.9, 那么排列 23541 被复制。

交叉

• 选择两个父项结构，从选择的个体中

• 产生一二进制串m长度

• 对子项 1: 拿所有父项1的位置，在二进制串里用“1”，对子项2：拿所有父项2的位置，在二进制串里用“0”

• 父项1的其它因素被存，作为在父项2里出现时。然后，他们被插入子项1的自由位置。对子项2也是同样的过程 。

例如:

• 选择 12345 (父项 1) 和 24531 (父项 2)
• 二进制字串: 01101
• 子项 1: - 2 3 - 5; 子项 2: 2 - - 3 -
• 子项 1: 4 2 3 1 5; 子项2: 2 1 4 3 5

有许多不同交叉操作者。这里，“基于同样订单的交叉”被显示。

父项 1: 1 - - 4 - ->在父项2 出现: 4 - - 1 -
父项2: - 4 5 - 1 -> 在父项1出现 1: - 1 4 - 5


变异
1. 选择一个体的父项
2. 选择随机两个位置，在这个父项排列中
3. 在这个间隔里的新顺序值是随机产生的。

如
父项: 12345
两个位置: 2 和 4
老的顺序 : 2 3 4 -> 新顺序: 4 2 3

=> 新排列: 1 4 2 3 5

GA的优势：

• 基于在排序里的高性能

• 专注于排程问题(没有太多的基于限制的约束 ）

APS的GA: 主要应用在生产计划与详细排程，可以产生唯一可行的方案 。最小化时间和优化排序 (目标: 最小化冲突）。

本文由作者向AMT提供
蔡颖 专栏