经典算法研究系列：七、深入浅出遗传算法，透析GA本质
本文参考：维基百科 华南理工大学电子讲义 互联网-------------------------------------------------------------------------------
一、初探遗传算法
Ok，先看维基百科对遗传算法所给的解释：
遗传算法是计算数学中用于解决最优化的搜索算法，是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。
遗传算法通常实现方式为一种计算机模拟。对于一个最优化问题，一定数量的候选解（称为个体）的抽象表示（称为染色体）的种群向更好的解进化。传统上，解用二进制表示（即0和1的串），但也可以用其他表示方法。进化从完全随机个体的种群开始，之后一代一代发生。在每一代中，整个种群的适应度被评价，从当前种群中随机地选择多个个体（基于它们的适应度），通过自然选择和突变产生新的生命种群，该种群在算法的下一次迭代中成为当前种群。
光看定义，可能思路并不清晰，咱们来几个清晰的图解、步骤、公式：
基本遗传算法的框图：
所以，遗传算法基本步骤是：
1） 初始化 t←0进化代数计数器；T是最大进化代数；随机生成M个个体作为初始群体 P（t）；
2） 个体评价 计算P（t）中各个个体的适应度值；
3） 选择运算 将选择算子作用于群体；
4） 交叉运算 将交叉算子作用于群体；
5） 变异运算 将变异算子作用于群体，并通过以上运算得到下一代群体P（t + 1）;
6） 终止条件判断 t≦T：t← t+1 转到步骤2；
t>T：终止 输出解。
好的，看下遗传算法的伪代码实现：
▲Procedures GA： 伪代码
begin
initialize P(0);
t = 0; //t是进化的代数，一代、二代、三代...
while(t <= T) do
for i = 1 to M do //M是初始种群的个体数
Evaluate fitness of P(t); //计算P（t）中各个个体的适应度
end for
for i = 1 to M do
Select operation to P(t); //将选择算子作用于群体
end for
for i = 1 to M/2 do
Crossover operation to P(t); //将交叉算子作用于群体
end for
for i = 1 to M do
Mutation operation to P(t); //将变异算子作用于群体
end for
for i = 1 to M do
P(t+1) = P(t); //得到下一代群体P（t + 1）
end for
t = t + 1; //终止条件判断 t≦T：t← t+1 转到步骤2
end while
end
二、深入遗传算法
1、智能优化算法概述
智能优化算法又称现代启发式算法，是一种具有全局优化性能、通用性强且适合于并行处理的算法。
这种算法一般具有严密的理论依据，而不是单纯凭借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。
遗传算法属于智能优化算法之一。
常用的智能优化算法有：
遗传算法 、模拟退火算法、禁忌搜索算法、粒子群算法、蚁群算法。
（本经典算法研究系列，日后将陆续阐述模拟退火算法、粒子群算法、蚁群算法。）
2、遗传算法概述
遗传算法是由美国的J. Holland教授于1975年在他的专著《自然界和人工系统的适应性》中首先提出的。
借鉴生物界自然选择和自然遗传机制的随机化搜索算法。
模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象。
在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个
体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。
基本遗传算法（Simple Genetic Algorithms，GA)又称简单遗传算法或标准遗传算法），是由Goldberg总结出的一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。
3、基本遗传算法的组成
（1）编码（产生初始种群）
（2）适应度函数
（3）遗传算子（选择、交叉、变异）
（4）运行参数
接下来，咱们分门别类，分别阐述着基本遗传算法的五个组成部分：
1、编码
遗传算法（GA）通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。
正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。
基本遗传算法（SGA）使用二进制串进行编码。
初始种群：基本遗传算法（SGA）采用随机方法生成若干个个体的集合，该集合称为初始种群。
初始种群中个体的数量称为种群规模。
2、适应度函数
遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。
适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，
它的设计应结合求解问题本身的要求而定。
3.1、选择算子
遗传算法使用选择运算对个体进行优胜劣汰操作。
适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。
选择操作的任务就是从父代群体中选取一些个体，遗传到下一代群体。
基本遗传算法（SGA）中选择算子采用轮盘赌选择方法。
Ok，下面就来看下这个轮盘赌的例子，这个例子通俗易懂，对理解选择算子帮助很大。
