遗传算法genetic algorithm ga class一介狂书生.pdfVIP

•遗传算法（GeneticAlgorithm，GA）是一种进化算法，其基本原理是仿效生物界中的“物竞天择、适者”的演化法

则，它最初由Michigan大学的J.Holland教授于1967年提出。

•遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过（gene）编码的一

定数目的(individual)组成。因此，第一步需要实现从表现型到型的映射即编码工作。初代种群产生，按照

适者和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中的适应度

（fitness）大小选择，幵借助于自然遗传学的遗传算子（geneticoperators）进行组合交叉和变异，产生出代表新

•遗传算法有三个基本操作：选择（Selection）、交叉（Crossover）和变异（Mutation）。

•（1）选择。选择的目的是为了从当前群体中选出优良的，使它们有机会作为父代为下一代繁衍子孙。根据各个的

适应度值，按照一定的规则或方法从上一代群体中选择出一些优良的遗传到下一代种群中。选择的依据是适应性强的

为下一代贡献一个或多个后代的概率大。

•（2）交叉。通过交叉操作可以得到新一代，新组合了父辈的特性。将群体中的各个随机搭配成对，对每

一个，以交叉概率交换它们之间的部分。

•（3）变异。对种群中的每一个，以变异概率改变某一个或多个座上的值为其他的等位。同生物界中一样，

变异发生的概率很低，变异为新的产生提供了机会。

实际问题参数集

•遗传算法的基本步骤：编码

1)编码：GA在进行搜索之前先将解空间的解数据表示成遗传空间的型串结构数据，初始种群

这些串结构数据的丌同组合便构成了丌同的点。

计算适应度

2)初始群体的生成：随机产生N个初始串结构数据，每个串结构数据称为一个，N个选择适应度高的进行

构成了一个群体。GA以这N个串结构数据作为初始点开始进化。

交叉

3)适应度评估：适应度表明或解的优劣性。丌同的问题，适应性函数的定义方式也丌

变异

同。

新种群

N

满足终止条件？

Y

改善或解决实际问题