遗传算法的基本构成

在遗传算法中，每个问题的解被称为染色体的串，通常表示为位串，每个染色体称之为个体。遗传算法求解问题的过程是：首先产生一个个体的初始群体（通常是随机产生的），然后对初始群体进行演化，即反复执行以下操作——根据每个个体的适应值选择产生一个中间代（每个个体可以多次被选择），适应值较高的个体被选择的可能性较大；然后对从中间代中随机地选取的每一对个体按照杂交概率pc 进行杂交，杂交的目的在于交换个体间的信息，经杂交后，每一对个体产生两个子个体，将这些子个体放入一个新的中间代，如果一对个体没有被杂交，则将它们直接放入新的中间代（其概率为1-pc），最后对新的中间代的每一个个体按照变异概率pm 进行变异，变异算子的目的是引入个体的多样性，以防止早熟收敛。经变异后，得到下一代群体。初始群体经过若干代的演化后，遗传算法收敛到适应值最高的个体，这样可以得到问题的最优解或近似最优解。遗传算法将最后群体中适应值最高的个体作为优化问题的解。

简单遗传算法的形式描述如下：

通常设计一个遗传算法的基本步骤如下：

（1）确定解的编码方案。通常遗传算法求解问题不是直接作用在问题的解空间上，而是利用解的某种编码表示。选择何种编码表示有时会对算法的性能、效率等产生很大的影响。

（2）设计适应度函数。适应值是对解的质量的一种度量，遗传算法在求解过程中，基本上不利用外部信息，而仅利用群体中个体的适应值来进行搜索，所以适应度函数的选取至关重要，直接影响到算法的收敛速度及性能。适应度函数通常以目标函数或费用函数的形式来表示。(www.xing528.com)

（3）选择策略的确定。优胜劣汰的选择机制使得适应值较大的个体有较高的存活概率，不同的选择策略对算法的性能有较大的影响。

（4）遗传算子的设计。

（5）控制参数的选取。

（6）确定算法的终止准则。