遗传算法的基本原理

遗传算法的基本原理

遗传算法本质上是对染色体模式所进行的一系列运算，即通过选择算子将当前种群中的优良模式遗传到下一代种群中，利用交叉算子进行模式重组，利用变异算子进行模式突变。

步骤

基本框架

1.编码

由于遗传算法不能直接处理问题空间的参数,因此必须通过编码将要求解的问题表示成遗传空间的染色体或者个体。这一转换操作就叫做编码，也可以称作（问题的）表示（representation）。

评估编码策略常采用以下3个规范： 

（a)完备性(completeness):问题空间中的所有点(候选解)都能作为GA空间中的点(染色体)表现。 

（b)健全性(soundness): GA空间中的染色体能对应所有问题空间中的候选解。 

（c)非冗余性(nonredundancy):染色体和候选解一一对应。

2.适应度函数

进化论中的适应度，是表示某一个体对环境的适应能力，也表示该个体繁殖后代的能力。遗传算法的适应度函数也叫评价函数，是用来判断群体中的个体的优劣程度的指标，它是根据所求问题的目标函数来进行评估的。

遗传算法在搜索进化过程中一般不需要其他外部信息，仅用评估函数来评估个体或解的优劣，并作为以后遗传操作的依据。由于遗传算法中，适应度函数要比较排序并在此基础上计算选择概率，所以适应度函数的值要取正值。由此可见，在不少场合，将目标函数映射成求最大值形式且函数值非负的适应度函数是必要的。

适应度函数的设计主要满足以下条件：

（a）单值、连续、非负、最大化

（b) 合理、一致性 

（c）计算量小 

（d）通用性强。 

在具体应用中，适应度函数的设计要结合求解问题本身的要求而定。适应度函数设计直接影响到遗传算法的性能。

3.初始群体选取

遗传算法中初始群体中的个体是随机产生的。一般来讲，初始群体的设定可采取如下的策略:

（a)根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。

（b)先随机生成一定数目的个体，然后从中挑出最好的个体加到初始群体中。这种过程不断迭代，直到初始群体中个体数达到了预先确定的规模。