全局优化（避免陷入局部极值-扩大种群规模）

编码à求解à解码

智能优化方法通常包括进化计算和群智能等两大类方法是一种典型的元启发式随机优化方法

适应度函数（物竞天择）

进化算法的概念详细介绍基本遗传算法这是进化算法的基本框架。然后介绍双倍体、双种群、自适应等比较典型的改进遗传算法及其应用。

编码方案：怎样把优化问题的解进行编码。

适应度函数：怎样根据目标函数构建适应度函数。

选择策略：优胜劣汰。

控制参数：种群的规模、算法执行的最大代数、执行不同遗传操作的概率等。

遗传算子：选择、交叉、变异。

算法终止准则：规定一个最大的演化代数，或算法在连续多少代以后解的适应值没有改进。

遗传算法genetic algorithmsGA

一类借鉴生物界自然选择和自然遗传机制的随机搜索算法,非常适用于处理传统搜索方法难以解决的复杂和非线性优化问题。  

遗传算法可广泛应用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。

适者生存 目标值比较大的解被选择的可能性大

个体Individual 解

染色体Chromosome 解的编码字符串、向量等

基因Gene 解的编码中每一分量

适应性Fitness 适应度函数值 

群体Population 根据适应度值选定的一组解解的个数为群体的规模 

婚配Marry 交叉Crossover选择两个染色体进行交叉产生一组新的染色体的过程

变异Mutation 编码的某一分量发生变化的过程

遗传算法的基本思想   在求解问题时从多个解开始然后通过一定的法则进行逐步迭代以产生新的解。

设自变量介于0-31，求其二次函数的最大值

表达问题的字符串相当于遗传学中的染色体。每个字符串称作个体。每一遗传代次中个体的组合称为群体。

用二进制数表示x值。由于x的最大值（31）只需5位二进制数，以利用5位二进制数组成个体。

2、形成初始群体

  随机产生初始群体，即随机生成一组任意排列的字符串。群体中个体的数目通常也是固定的。

假设得出拥有4个个体的初始群体，即：01101、11000、01100、10011。它们的x值相应为：13、24、8、19

表1  遗传算法的第0代

3.计算适应度。

    衡量字符串（染色体）好坏的指标是适应度（Fitness），它通常也就是遗传算法中的目标函数。适应度是今后优胜劣汰的主要判据。

适应度低的下一代不产生，最高的出现两次

4、复制（Reproduction）。

选择的依据是个体适应度的大小，适应度大的个体接受复制，使之繁殖；适应度小的个体则予删除，使之死亡。

      这样，就产生下一代新群体，如表2所示。新群体的4个个体分别是01101、11000、11000、10011。

平均适应度明显增加，由原来的293增至421。体现优胜劣汰原则，使群体素质不断得到改善。

5、交叉（Crossover）。

   通过复制产生新群体，其总体性能得到改善，然而却不能产生新的个体。

   对染色体（字符串）的某些部分进行交叉换位。被交换的母体都选自经过复制产生的新一代个体（优胜者）。

    本例中，利用随机配对的方法，决定1号和2号个体、3号和4号个体分别交叉，如表2第5列所示。再利用随机定位的方法，确定这两对母体交叉换位的位置分别从字符串左数第三位字符及第二位字符之后。所得的新个体如下表所示：  

6、变异（Mutation）。

   遗传算法模仿生物学中基因变异的方法，将个体字符串某位符号进行逆变，即由1变为0或由0变为1。例如，下式左侧的个体于第3位变异，得到新个体如右侧所示：

  个体是否进行变异以及在哪个字符变异，都由事先给定的变异概率决定。通常，变异概率很小，约为0.01

    7、终止。

   反复执行上述（3）-（6）项工作，直至得出满意的最优解。

从随机生成的初始可行解出发，利用复制、交叉、变异等操作，遵循优胜劣汰的原则，不断循环执行，逐渐逼近全局最优解。

遗传算法的五个基本要素：

参数编码

初始群体的设定

适应度函数的设计

遗传操作设计

控制参数设定（交叉、变异概率）

   一维染色体编码方法将问题空间的参数编码为一维排列的染色体的方法。

1 二进制编码

高维时串很长

二进制编码用若干二进制数表示一个个体将原问题的解空间映射到位串空间 B={0，1}上然后在位串空间上进行遗传操作。

优点：遗传操作如交叉、变异等易实现算法处理的模式数最多

缺点：算法的搜索效率低。

2  Gray 编码

Gray编码:将二进制编码通过一个变换进行转换得到的编码。

任意两个连续的两个整数的编码值之间只有一个位是不同的，其他位都完全相同。克服了二进制编码的Hamming悬崖问题（解空间连续的二进制编码差异很大）。

采用实数表达法不必进行数制转换可直接在解的表现型上进行遗传操作。

求解高维或复杂优化问题时采用。

把每个参数先进行二进制编码得到子串再把这些子串连成一个完整的染色体。  多参数映射编码中的每个子串对应各自的编码参数所以可以有不同的串长度和参数的取值范围。

1.初始种群的产生

把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。

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

2.  种群规模的确定

群体规模太小，遗传算法的优化性能不太好，易陷入局部最优解。

 群体规模太大，计算复杂。

一般种群规模设置为20-100

适应度函数与问题的目标函数是不完全一致的.将目标函数映射成求最大值形式而且函数值非负的适应度函数是必要的.

若目标函数为最大化问题，则（适应度函数就等于目标函数）

 若目标函数为最小化问题，则（转换为求极大值）

将目标函数转换为求最大值的形式,且保证函数值非负！

2.适应度函数的尺度变换

妨碍适应度值高的个体产生，从而影响遗传算法正常工作的问题统称为欺骗问题（deceptive problem）。

过早收敛：缩小这些个体的适应度，以降低这些超级个体的竞争力。

停滞现象：个体间适应度无明显差异。改变原始适应值的比例关系，以提高个体之间的竞争力。

适应度函数的尺度变换（fitness scaling）或者定标：对适应度函数值域的某种映射变换。

（1）线性变换：

a,b的取值设定需满足

对不太大的群体M=50-100，Cmult可以在1.2-2.0的范围内取值

P36

（2）幂函数变换法

（3）指数变换法：

1.个体选择概率分配方法

 选择操作也称为复制（reproduction）操作：从当前群体中按照一定概率选出优良的个体，使有机会繁殖下一代子孙。

 判断个体优良与否的准则是各个个体的适应度值

个体选择概率分配方法

各个个体被选择的概率和其适应度值成比例。

个体i被选择的概率为（M为群体规模大小）：

群体成员按适应值大小从好到坏依次排列

按转盘式选择的方式选择父体

 1.2.非线性排序

概率：

可用其他非线性函数来分配选择概率

2.选择个体方法

（1）转盘赌选择

按个体的选择概率产生一个轮盘，轮盘每个区的角度与个体的选择概率成比例。

 产生一个随机数，它落入转盘的哪个区域就选择相应的个体交叉。

（2）锦标赛选择方法

从群体中随机选择个体，将其中适应度最高的个体保存到下一代。这一过程反复执行，直到保存到下一代的个体数达到预先设定的数量为止。

随机竞争方法（stochastic tournament）：每次按赌轮选择方法选取一对个体，然后让这两个个体进行竞争，适应度高者获胜。如此反复，直到选满为止。 

3）最佳个体保存方法

把群体中适应度最高的个体不进行交叉而直接复制到下一代中，保证遗传算法终止时得到的最后结果一定是历代出现过的最高适应度的个体

基本的交叉算子：一点交叉、二点交叉

遗传算法的特点：

可直接对结构对象进行操作。

利用随机技术指导对一个被编码的参数空间进行高效率搜索。

采用群体搜索策略，易于并行化。

仅用适应度函数值来评估个体，并在此基础上进行遗传操作，使种群中个体之间进行信息交换。

多参数级联编码

交叉0.1

变异0.01

计算函数极值的遗传算法实现过程

f(x)的最大值

要求求解精度到6位小数

表现型：x

基因型：二进制编码（串长取决于求解精度）

按编码原理：假设要求求解精度到6位小数，区间长度为2-(-1)＝3，即需将区间分为3/0.000001=3×106等份。

所以编码的二进制串长应为22位。

产生的方式：随机

产生的结果：长度为22的二进制串

产生的数量：种群的大小（规模），如30，50

3.计算适应度 直接用目标函数作为适应度函数

     1.解码：将个体s转化为[-1,2]区间的实数：

        s= → x=0.637197

2．算x的函数值（适应度）：

        f(x)=xsin(10πx)+2.0=2.586345

4.遗传操作 选择：比例选择法；

交叉：单点交叉；

变异：小概率变异

5.模拟结果 设置的参数：

     种群大小50；交叉概率0.75；变异概率0.05；最大代数200。

得到的最佳个体：

     smax=;

     xmax=1.8506;

     f(xmax)=3.8503;

模拟结果

     进化的过程：

TSP具有广泛的应用背景和重要理论价值，特别在机器人运动规划中得到许多应用，例如：移动机器人的全局路径规划问题（如右上图）、焊接机器人的任务规划问题

但是，巡回旅行商问题中可能的路径数目与城市数目N呈指数型增长，所有的旅程路线组合数为

其已经被证明属于NP难题。

关于遗传算法操作算子的验证

对于上表，有（验证）以下基本结论：

（1）遗传算法搜索求解能力与四个因素有关：群体规模、选择算子、交叉率和变异率 。

（2）从主到次依次为：交叉率——群体规模——选择算子——变异率。

（3）A3-B2-C1-D3是优选方案。

双倍体遗传算法

双种群遗传算法

自适应遗传算法

双倍体遗传算法

双倍体遗传算法采用显性和隐性两个染色体同时进行进化，提供了一种记忆以前有用的基因块的功能。

  双倍体遗传算法采用显性遗传。

（1）编码/解码：两个染色体（显性、隐性）  

（2）复制算子：计算显性染色体的适应度，按照显性染色体   的复制概率将个体复制到下一代群体中。 

（3）交叉算子：两个个体的显性染色体交叉、隐性染色体也同时交叉。            

（4）变异算子：个体的显性染色体按正常的变异概率变异；隐性染色体按较大的变异概率变异。   

（5）双倍体遗传算法显隐性重排算子：个体中适应值较大的染色体设为显性染色体，适应值较小的染色体设为隐性染色体。

P100

双种群遗传算法

基本思想

 在遗传算法中使用多种群同时进化，并交换种群之间优秀个体所携带的遗传信息，以打破种群内的平衡态达到更高的平衡态，有利于算法跳出局部最优。

 多种群遗传算法：建立两个遗传算法群体，分别独立地运行复制、交叉、变异操作，同时当每一代运行结束以后，选择两个种群中的随机个体及最优个体分别交换。

2. 双种群遗传算法的设计

（1）编码/解码设计

（2）交叉算子、变异算子

（3）杂交算子：产生一个随机数num，随机选择A中num个个体与A中最优个体，随机选择B中num个个体与B中最优个体，交换两者

自适应遗传算法

AGA：当种群各个体适应度趋于一致或者趋于局部最优时，使Pc、Pm增加，以跳出局部最优；而当群体适应度比较分散时，使Pc、Pm减少，以利于优良个体的生存。

对于适应度高于群体平均适应值的个体，选择较低的Pc、Pm，使得该解得以保护进入下一代；对低于平均适应值的个体，选择较高的Pc、Pm值，使该解被淘汰。

2. 自适应遗传算法的步骤

（1） 编码/解码设计。

（2） 初始种群产生：N（N 是偶数）个候选解，组成初始解集。

（3） 定义适应度函数为，计算适应度fi。

（4） 按轮盘赌规则选择N 个个体，计算              。

（5）将群体中的各个个体随机搭配成对，共组成N/2对， 对每一对个体，按照自适应公式计算自适应交叉概率Pc，随机产生R(0,1)，如果R