APS 算法分析之五基因算法 基因算法 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) =...
