遗传算法

课前测验

遗传算法 (GA) 基于一种进化式方法，通过模拟种群的进化过程来为给定问题找到最优解。这种方法由 John Henry Holland 于1975年提出。

遗传算法基于以下理念：

• 问题的有效解可以表示为基因
• 交叉允许我们将两个解结合起来，生成一个新的有效解
• 使用某种适应度函数进行选择，以筛选出更优的解
• 引入变异以打破优化过程的稳定性，从而摆脱局部最小值

如果你想实现遗传算法，需要以下步骤：

• 找到一种方法，用基因 g∈Γ 编码问题的解
• 在基因集合 Γ 上定义适应度函数 fit: Γ→R，函数值越小表示解越优。
• 定义交叉机制，将两个基因结合生成一个新的有效解 crossover: Γ2→Γ。
• 定义变异机制 mutate: Γ→Γ。

在许多情况下，交叉和变异是操作基因的简单算法，比如处理数字序列或位向量。

遗传算法的具体实现可能因情况而异，但总体结构如下：

1. 选择初始种群 G⊂Γ
2. 随机选择将在此步骤执行的操作：交叉或变异
3. 交叉：

• 随机选择两个基因 g₁, g₂ ∈ G
• 计算交叉结果 g=crossover(g₁,g₂)
• 如果 fit(g)<fit(g₁) 或 fit(g)<fit(g₂)，用 g 替换种群中的对应基因。

4. 变异 - 随机选择一个基因 g∈G，并用 mutate(g) 替换它
5. 从步骤2开始重复，直到适应度函数值足够小，或达到步骤数限制。

常见任务

遗传算法通常解决以下任务：

1. 排程优化
2. 最优装箱
3. 最优切割
4. 加速穷举搜索