第6章遗传算法及其应用

1、人工智能原理及应用人工智能原理及应用问题求解策略问题求解策略问题求解策略问题求解策略ABCDCDEEDECECD常常面临常常面临组合爆炸组合爆炸问题求解策略问题求解策略ABCDCDEEDECECD问题求解策略问题求解策略ABCDEAACBDEA问题求解策略问题求解策略大多数进化算法属大多数进化算法属于非确定性算法于非确定性算法ABCDEAABCEDAACEDBAACEBDA问题求解策略问题求解策略元启发算法元启发算法问题求解策略问题求解策略ABCDE群体智能群体智能群体智能群体智能群体智能群体智能群体智能群体智能群体智能群体智能群体智能群体智能问题求解策略问题求解策略问题求解策略问题求解策略“

2、任何控制与决策问题本任何控制与决策问题本质上均可归结为优化问质上均可归结为优化问题。题。”Yu-Chi Ho遗传算法的基本概念遗传算法的基本概念 遗传算法的基本概念遗传算法的基本概念 遗传算法的基本概念遗传算法的基本概念 遗传算法的基本概念遗传算法的基本概念 遗传算法的基本概念遗传算法的基本概念 遗传算法的基本概念遗传算法的基本概念 10Njjiiffp遗传算法的基本概念遗传算法的基本概念 10Njjiiffp遗传算法的基本概念遗传算法的基本概念 遗传算法的基本概念遗传算法的基本概念 01101011001111000110110000110111遗传算法的基本概念遗传算法的基本概念 0110

3、101100111100011100001110 1 011遗传算法的基本概念遗传算法的基本概念 遗传算法的基本概念遗传算法的基本概念 遗传算法的基本概念遗传算法的基本概念 遗传算法的基本概念遗传算法的基本概念 适应度评估初始化种群终止？输出最优解YN选择交叉变异遗传算法的应用遗传算法的应用 适应度评估初始化种群终止？输出最优解YN选择交叉变异l背包容量: 35l物品重量: 10, 12, 8, 7, 6, 8l物品价值: 15, 13, 12, 9, 8, 7110000 (28)011000 (25)001100 (21)000110 (17)110000 (28)011000 (25)1

4、10100 (37)001000 (12)011010 (33)110010 (36)011100 (34)110100 (37)110000 (28)011110 (42)110110 (45)011100 (34)110110 (45)011010 (33)遗传算法的应用遗传算法的应用 适应度评估初始化种群终止？输出最优解YN选择交叉变异l背包容量: 35l物品重量: 10, 12, 8, 7, 6, 8l物品价值: 15, 13, 12, 9, 8, 7遗传算法的应用遗传算法的应用 4786146153232154354678785321 2678遗传算法的应用遗传算法的应用 45821

5、6373648 7521部分匹配交叉部分匹配交叉(PMX)4786153232154678遗传算法的应用遗传算法的应用 478XX53X321X46XX顺序交叉顺序交叉(OX)8XX47X532XX43X168214765327843516遗传算法的应用遗传算法的应用 182 3 7 6 5 4遗传算法的应用遗传算法的应用 程序演示程序演示遗传算法的应用遗传算法的应用 遗传算法的应用遗传算法的应用 遗传算法的数学基础遗传算法的数学基础 01101011001111101100* 1*1*1 *11*1 遗传算法的数学基础遗传算法的数学基础 01101011001111101100* 1*1*1

6、 *11*1 n: 群体规模群体规模l: 串的长度串的长度遗传算法的数学基础遗传算法的数学基础 01101011001111101100* 1*1*1 *11*1 n: 群体规模群体规模l: 串的长度串的长度1iiinjjffPnff11(,1)mmiiiifm H tnPf遗传算法的数学基础遗传算法的数学基础 n: 群体规模群体规模l: 串的长度串的长度1iiinjjffPnff111(,1)(, )(, ) mmiiiimiifm H tnPffm H tm H tf遗传算法的数学基础遗传算法的数学基础 n: 群体规模群体规模l: 串的长度串的长度1iiinjjffPnff11(,1)()

7、 (, )mmiiiifm H tnPff Hm H tf平均适应度越高的平均适应度越高的模式，增长越快模式，增长越快遗传算法的数学基础遗传算法的数学基础 n: 群体规模群体规模l: 串的长度串的长度1iiinjjffPnff(,1)(, )(1()m H tm H tH()()f HfHf遗传算法的数学基础遗传算法的数学基础 n: 群体规模群体规模l: 串的长度串的长度1iiinjjffPnff(,1)(,0)(1()tm H tm HH ()()f HfHf平均适应度高平均适应度高(低低)的模式将呈指数的模式将呈指数级增长级增长(减少减少)遗传算法的数学基础遗传算法的数学基础 n: 群体规

8、模群体规模l: 串的长度串的长度PC: 交叉概率交叉概率(,1)(, )(1()m H tm H tH1100* 1*1*1 *11*1 ()()/(1)dCP HP L Hl()1()/ (1)sCP HP L Hl 遗传算法的数学基础遗传算法的数学基础 ()(,1)(, )(1()(1)1CL Hm H tm H tHPl1100* 1*1*1 *11*1 n: 群体规模群体规模l: 串的长度串的长度PC: 交叉概率交叉概率遗传算法的数学基础遗传算法的数学基础 ()(,1)(, )(1()(1)1CL Hm H tm H tHPl1100* 1*1*1 *11*1 n: 群体规模群体规模l: 串的长度串的长度PC: 交叉概率交叉概率n: 群体规模群体规模l: 串的长度串的长度PC: 交叉概率交叉概率PM: 变异概率变异概率遗传算法的数学基础遗传算法的数学基础 ()(,1)(, )(1()(1()1CML Hm H tm H tHPP O Hl1100* 1*1*1 *11*1 平均适应度高、平均适应度高、低阶、短的模式低阶、短的模式将呈指数级增长将呈指数级增长遗传算法的数学基础遗传算法的数学基础 1100*