遗传算法（一）：基本原理

一、问题描述

  在使用计算机解决实际问题时，我们通常将一个问题用数学方法表示为一个函数描述，通常我们期望得到的是一个函数在一定取值范围内的最值或者极值，例如最大利润或是最大质量。然而由于实际问题的复杂性，我们所抽象出来的函数模型往往不是单变量函数，更多的是二元甚至多元函数。为了更清楚简洁地展示和表达，我们以一个生活中最常见的由三角函数和幂函数组成的二元函数为例。例如利润与广告曝光率x（0<=X<=20） 和人们需量y（0<=X<=20）之间满足一定的关系：。
  F(x,y)=sinx+cosy+0.01x^2+0.1y+1因此我们希望得到利润函数F(x,y)=sinx+cosy+0.01x^2+0.1y+1在区间[0,20]内的局部最优解 Fmax(x0,y0)=Zmax=88.017其中x属于[0,20],y属于[0,20]。

二、实验原理

  通过对传统优化算法和遗传算法对比，遗传算法有如下优点是传统算法无法替代的：
1、直接对结构对象操作，不存在求导和函数连续性的限定；
2、遗传算法不是从单个点，而是从一个点地群体开始搜索；
3、具有内在的隐并行性和较好的全局寻优能力；
4、采用概率化寻优方法，能自动获取搜索过程中的有关知识并用于指导
优化，自适应地调整搜索方向，不需要确定地规则；
5、鲁棒性相对传统算法更强；
6、遗传算法的基本思想简单运行方式和实现步骤规范，便于具体使用；
综上考虑，我们在解决此问题时使用遗传算法。

2.1遗传算法（Genetic Algorithm）的概念：

  遗传算法是模拟生物在自然环境中的遗传和进化过程中形成的一种自适应优化概率的搜索算法。

2.2 GA来源及基本思想：

  遗传算法是一种启发式算法，其基本思想主要模拟生物学中的遗传概念。
2.2.1、从代表问题可能解集中得到一个初始种群。
2.2.2、初始种群产生后，按照优胜劣汰的原则，根据个体适应度值
选择优秀个体，进行复制、交叉、变异，产生出代表新解集
的群体。
2.2.3、对新群体进行挑选等一系列遗传操作，如此往复，逐代演化
产生出越来越好的近似解
生物遗传与遗传算法的类比：

2.3主要流程：

2.4遗传算法设计需考虑的五个问题：

2.4.1.个体编码：编码过程是问题空间向编码空间的映射过程

编码与解码需要考虑的三个问题：
（1）染色体的可行性：通过编码空间的染色体解码后的解是否
（2）位于问题的可行域中
（3）染色体的合法性：通过编码空间的染色体解码后的解是否为问题的一 个解
（4）映射的唯一性
具体方法：

2.4.2群体初始化
产生初始种群的方法通常有两种：
一种是完全随机的方法产生的，它适合于对问题的解无任何先验知识的情况。
另一种是根据某些先验知识转变为必须满足的一组要求，然后在满足这些要求的解中再随机地选取样本。

2.4.3个体评价

适应函数一般由目标函数变换而成；
以染色体适应值的大小来确定该染色体被遗传到下一代群体中的概率。
染色体适应值越大，该染色体被遗传到下一代的概率也越大；
反之，染色体的适应值越小，该染色体被遗传到下一代的概率也越小；
群体中的每个染色体都需要计算适应值；
因此适应函数的选取至关重要，直接影响到GA的收敛速度以及能否找到最优解。

2.4.4遗传操作

  亦称遗传算子(genetic operator)，就是关于染色体的运算。遗传算法中有三种遗传操作:

1.选择-复制(selection-reproduction)
以轮盘赌为例:

2.交叉(crossover，亦称交换、交配或杂交)
以单点交叉为例：
随机产生一个交叉点
在交叉点位置分离双亲染色体
互换交叉点位置右边的基因码

3.变异(mutation，亦称突变)
以变异概率Pm改变染色体的某一个基因,当以二进制编码时，变异的基因由0变成1，或者由1变成0。

2.4.5参数设置

群体规模N :

• 影响算法的搜索能力和运行效率。
• 若N设置较大，一次进化所覆盖的模式较多，可以保证群体的多样性，从而提高算法的搜索能力，但是由于群体中染色体的个数较多，势必增加算法的计算量，降低了算法的运行效率。
• 若N设置较小，虽然降低了计算量，但是同时降低了每次进化中群体包含更多较好染色体的能力。

交叉概率Pc :

• 决定了进化过程种群参加交配的染色体平均数目。
• 取值一般为0.4至0.99。
• 也可采用自适应方法调整算法运行过程中的交配概率。

变异概率Pm:

• 增加群体进化的多样性，决定了进化过程中群体发生变异的基因平均个数。
• Pm的值不宜过大。因为变异对已找到的较优解具有一定的破坏作用，如果Pm的值太大，可能会导致算法目前处于的较好的搜索状态倒退回原来较差的情况。
• Pm的取值一般为0.001至0.1之间。
• 也可采用自适应方法调整算法运行过程中的Pm值。

适应值评价:

• 影响算法对种群的选择，恰当的评估函数应该能够对染色体的优劣做出合适的区分，保证选择机制的有效性，从而提高群体的进化能力。
• 评估函数的设置同优化问题的求解目标有关。
• 评估函数应满足较优染色体的适应值较大的规定。
• 为了更好地提高选择的效能，可以对评估函数做出一定的修正。

终止条件:

• 决定算法何时停止运行，输出找到的最优解，采用何种终止条件，跟具体问题的应用有关。
• 可以使算法在达到最大进化代数时停止，最大进化代数一般可设置为100~1000，根据具体问题可对该建议值作相应的修改。
• 也可以通过考察找到的当前最优解是否达到误差要求来控制算法的停止。
• 或者是算法在持续很长的一段进化时间内所找到的最优解没有得到改善时，算法可以停止。