全局优化算法：遗传算法

全局优化算法概述

前面讨论过一些迭代算法，包括牛顿法、梯度方法、共轭梯度方法和拟牛顿法，能够从初始点出发，产生一个迭代序列。很多时候，迭代序列只能收敛到局部极小点。因此，为了保证算法收敛到全局最小点，有时需要在全局极小点附近选择初始点。此外，这些方法需要计算目标函数。

全局优化算法又称现代启发式算法，是一种具有全局优化性能、通用性强且适合于并行处理的算法。
这种算法一般具有严密的理论依据，而不是单纯凭借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。
遗传算法属于智能优化算法之一。

常用的全局优化算法有：
遗传算法 、模拟退火算法、禁忌搜索算法、粒子群算法、蚁群算法。

1、染色体编码

实际上遗传算法并不是直接针对约束集中的点进行操作，而是针对这些点的编码后再进行相关变异交叉等操作。具体说来，如约束集 ω 中的点24映射为一个字符串集合– 11000，这些字符串全部都是等长的，称为染色体。基本遗传算法（SGA）使用二进制串进行编码。

2、适应度函数

遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。
适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。

3、选择和进化步骤

在选择步骤中，利用选择操作构造一个新的种群 M(k) ，使其个体数量与种群相等，种群中个体数量称为个体容量，用N表示，M是在P的基础上进行随机处理后得到的，即M中的每个个体以概率

等于 P(k) 中的 x(k) ，其中， F(k)=∑f(x(k)i) ，指的是对整个P进行求和，也就是说，染色体被选中的概率与其适应度函数值大小成正比。

轮盘赌选择方法：

轮盘赌选择法可用如下过程模拟来实现：
(1)在［0, 1］内产生一个均匀分布的随机数r。
(2)若r≤q(1),则染色体x(1)被选中。
(3)若q(k-1)

得到积累概率为：

轮盘赌选择方法的实现步骤:
（1）计算群体中所有个体的适应度值；
（2）计算每个个体的选择概率；
（3）计算积累概率；
（4）采用模拟赌盘操作（即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进行匹配）
来确定各个个体是否遗传到下一代群体中。

4、交叉算子

交叉运算，是指对两个相互配对的染色体依据交叉概率，按某种方式相互交换其部分基因，从而形成两个新的个体。

交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。
基本遗传算法（SGA）中交叉算子采用单点交叉算子。

单点交叉运算

5、变异算子

变异运算，是指改变个体编码串中的某些基因值，从而形成新的个体。
变异运算是产生新个体的辅助方法，决定遗传算法的局部搜索能力，保持种群多样性。
交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。
基本遗传算法（SGA）中变异算子采用基本位变异算子。

基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。
对于二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，
则将其变为1；反之，若原有基因值为1，则将其变为0 。

基本位变异算子的执行过程：

交叉和变异操作目的在于创建一个新的种群，使得新种群目标函数的平均值能够大于上一代种群。总的说来，遗传算法就是针对种群迭代开展交叉和变异操作，产生新种群，直到满足预定的停止条件。

Matlab示例：

选择适应度函数为： f(x)=x+10sin(5x)+7cos(4x) 函数图像为

运行结果为：

最优个体为： 10101111011111011
最优值为：24.8554

相关Matlab代码参考：Github地址

[1].An introduction to optimization-最优化导论[J]. Edwin K.P.Chong.
[2].http://blog.csdn.net/v_JULY_v/article/details/6132775