文档介绍：本章主要内容
概述
遗传算法
微粒群算法
蚁群算法
第1页/共73页
第一页，共74页。
概述
进化计算(Evolutionary Computation)是通过模拟自然界中生物进化机制进行搜索的一种算法。
算法的一般框架
遗传算子：
◆ 选择（Selection）：
- 从旧的种群中选择适应度高的染色体，放入匹配集（缓冲区），为以后染色体交叉、变异，产生新的染色体作准备。
- 选择方法：适应度比例法（***赌法），即按各染色体适应度大小比例来决定其被选择数目的多少。某染色体被选的概率：
第13页/共73页
第十三页，共74页。
遗传算法的一般框架
遗传算子：
◆ 交叉（Crossover）：
- 随机选择二个染色体(双亲染色体)，随机指定一点或多点，将两者部分码值进行交换，可得二个新的染色体(子辈染色体)。
新的子辈染色体: A’ 11010001
B’ 01011110
第14页/共73页
第十四页，共74页。
遗传算法的一般框架
遗传算子：
◆ 变异（Mutation）：
- 模拟生物在自然界环境变化，引起基因的突变。
- 在染色体二进制编码中，1变成0，或0变成1
- 变异产生染色体的多样性，避免进化中早期成熟，陷入局部极值点，变异的概率很低。
A 1 0 1 0 0 1 1 0
A’ 1 0 1 1 0 1 1 0
第15页/共73页
第十五页，共74页。
遗传算法的一般框架
遗传参数设置：
◆ N：群体大小，即群体中所含个体的数量，一般取20~100
◆ T：GA的终止进化代数，一般取100~500
◆ Pc：交叉概率，~
◆ Pm：变异概率，~
第16页/共73页
第十六页，共74页。
遗传算法的一般框架
遗传算法进行问题求解的过程：
◆ 初始化群体
◆ 计算群体中每个个体的适应度值
◆ 按由个体适应度值所决定的某个规则选择进入下一代的个体
◆ 按概率Pc进行交叉操作
◆ 按概率Pm进行变异操作
◆ 若没有满足某种停止条件，就转到第2步，否则进入下一步
◆ 输出群体中适应度值最优的染色体作为问题的满意解或最优解
第17页/共73页
第十七页，共74页。
第18页/共73页
第十八页，共74页。
遗传算法的一般框架
遗传算法应用举例：
例4-1 利用遗传算法求解区间[0,31]上的二次函数y=x2的最大值。
y=x2
31 X
Y
分析：
原问题可转化为在区间[0, 31]中搜索能使y取最大值的点a的问题。那么，[0, 31] 中的点x就是个体，函数值f(x)恰好就可以作为x的适应度，区间［0, 31］就是一个解空间 。这样, 只要能给出个体x的适当染色体编码，该问题就可以用遗传算法来解决。
第19页/共73页
第十九页，共74页。
遗传算法的一般框架
遗传算法应用举例：
解：(1) 设定种群规模，编码染色体，产生初始种群。
将种群规模设定为4，用5位二进制数编码染色体，取下列个体组成初始种群S1:
s1= 13 (01101), s2= 24 (11000)
s3= 8 (01000), s4= 19 (10011)
(2) 定义适应度函数：f (x)=x2
(3) 计算各代种群中的各个体的适应度, 并对其染色体进行遗传操作，直到适应度最高的个体(即31（11111）)出现为止。
第20页/共73页
第二十页，共74页。
遗传算法的一般框架
遗传算法应用举例：
首先计算种群S1中各个体的适应度f (si) ：
f (s1) = f(13) = 132 = 169， f (s2) = f(24) = 242 = 576
f (s3) = f(8) = 82 = 64， f (s4) = f(19) = 192 = 361
再计算种群S1中各个体的选择概率：
P(s1) = P(13) =