1、电气与信息工程学院电气与信息工程学院第第1111讲讲 机器学习机器学习-遗传算法遗传算法2电气与信息工程学院电气与信息工程学院机器学习机器学习信息科学导论信息科学导论2个体与种群个体与种群 个体就是模拟生物个体而对问题中的对象（一般就是个体就是模拟生物个体而对问题中的对象（一般就是问题的解）的一种称呼，一个个体也就是搜索空间中的问题的解）的一种称呼，一个个体也就是搜索空间中的一个点。一个点。种群种群(population)就是模拟生物种群而由若干个体组就是模拟生物种群而由若干个体组成的群体成的群体,它一般是整个搜索空间的一个很小的子集。它一般是整个搜索空间的一个很小的子集。11.1 11.1
2、基本概念基本概念2电气与信息工程学院电气与信息工程学院机器学习机器学习信息科学导论信息科学导论3适应度与适应度函数适应度与适应度函数 适应度适应度(fitness)就是借鉴生物个体对环境的适应程度就是借鉴生物个体对环境的适应程度,而而对问题中的个体对象所设计的表征其优劣的一种测度。对问题中的个体对象所设计的表征其优劣的一种测度。适应度函数适应度函数(fitness function)就是问题中的全体个体与其就是问题中的全体个体与其适应度之间的一个对应关系。它一般是一个实值函数。该适应度之间的一个对应关系。它一般是一个实值函数。该函数就是遗传算法中指导搜索的评价函数。函数就是遗传算法中指导搜索的
3、评价函数。11.1 11.1 基本概念基本概念2电气与信息工程学院电气与信息工程学院机器学习机器学习信息科学导论信息科学导论4染色体与基因染色体与基因染色体（染色体（chromosome）就是问题中个体的某种字符串）就是问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因（形式的编码表示。字符串中的字符也就称为基因（gene）。）。例如：例如：个体个体 染色体染色体 9 -1001（2，5，6）-010 101 11011.1 11.1 基本概念基本概念2电气与信息工程学院电气与信息工程学院机器学习机器学习信息科学导论信息科学导论5遗传操作遗传操作亦称遗传算子亦称遗传算子(gene
4、tic operator)，就是关于染色体的运，就是关于染色体的运算。遗传算法中有三种遗传操作算。遗传算法中有三种遗传操作:选择选择-复制复制(selection-reproduction)交叉交叉(crossover，亦称交换、交配或杂交，亦称交换、交配或杂交)变异变异(mutation，亦称突变，亦称突变)11.1 11.1 基本概念基本概念2电气与信息工程学院电气与信息工程学院机器学习机器学习信息科学导论信息科学导论6选择选择-复制复制通常做法是：对于一个规模为通常做法是：对于一个规模为N的种群的种群S,按按每个染色体每个染色体xiS的选择概率的选择概率P(xi)所决定的选中机会所决定的
5、选中机会,分分N次从次从S中随机选定中随机选定N个染色体个染色体,并进行复制。并进行复制。NjjiixfxfxP1)()()(这里的选择概率这里的选择概率P(xi)的计算公式为的计算公式为11.1 11.1 基本概念基本概念2电气与信息工程学院电气与信息工程学院机器学习机器学习信息科学导论信息科学导论7交叉交叉 就是互换两个染色体某些位上的基因。就是互换两个染色体某些位上的基因。s1=01000101,s2=10011011可以看做是原染色体可以看做是原染色体s1和和s2的子代染色体。的子代染色体。例如例如,设染色体设染色体 s1=01001011,s2=10010101,交换其后交换其后4位
6、位基因基因,即即11.1 11.1 基本概念基本概念2电气与信息工程学院电气与信息工程学院机器学习机器学习信息科学导论信息科学导论8 变异变异 就是改变染色体某个就是改变染色体某个(些些)位上的基因。位上的基因。例如例如,设染色体设染色体 s=11001101将其第三位上的将其第三位上的0变为变为1,即即 s=11001101 11101101=s。s也可以看做是原染色体也可以看做是原染色体s的子代染色体。的子代染色体。11.1 11.1 基本概念基本概念2电气与信息工程学院电气与信息工程学院机器学习机器学习信息科学导论信息科学导论9 遗传算法基本流程框图遗传算法基本流程框图生成初始种群计算适
7、应度选择-复制交叉变异生成新一代种群终止?结束11.2 11.2 基本遗传算法基本遗传算法2电气与信息工程学院电气与信息工程学院机器学习机器学习信息科学导论信息科学导论10 算法中的一些控制参数：算法中的一些控制参数：种群规模种群规模 最大换代数最大换代数 交叉率交叉率(crossover rate)就是参加交叉运算的染色体个就是参加交叉运算的染色体个数占全体染色体总数的比例，记为数占全体染色体总数的比例，记为Pc,取值范围一般为取值范围一般为0.40.99。变异率变异率(mutation rate)是指发生变异的基因位数所占是指发生变异的基因位数所占全体染色体的基因总位数的比例，记为全体染色
8、体的基因总位数的比例，记为Pm，取值范围一取值范围一般为般为0.00010.1。11.2 11.2 基本遗传算法基本遗传算法2电气与信息工程学院电气与信息工程学院机器学习机器学习信息科学导论信息科学导论11步步1 在搜索空间在搜索空间U上定义一个适应度函数上定义一个适应度函数f(x)，给定种群给定种群规模规模N，交叉率交叉率Pc和变异率和变异率Pm，代数代数T；步步2 随机产生随机产生U中的中的N个个体个个体s1,s2,sN，组成初始种群组成初始种群S=s1,s2,sN，置代数计数器置代数计数器t=1；步步3 计算计算S中每个个体的适应度中每个个体的适应度f()；步步4 若终止条件满足，则取若
9、终止条件满足，则取S中适应度最大的个体作为所中适应度最大的个体作为所求结果，算法结束。求结果，算法结束。11.2 11.2 基本遗传算法基本遗传算法2电气与信息工程学院电气与信息工程学院机器学习机器学习信息科学导论信息科学导论12 步步5 按选择概率按选择概率P(xi)所决定的选中机会，每次从所决定的选中机会，每次从S中随机选定中随机选定1个个体并将其染色体复制，共做个个体并将其染色体复制，共做N次，然后将复制所得的次，然后将复制所得的N个染色体组成群体个染色体组成群体S1；步步6 按交叉率按交叉率Pc所决定的参加交叉的染色体数所决定的参加交叉的染色体数c，从，从S1中随机中随机确定确定c个染
10、色体，配对进行交叉操作，并用产生的新染色体代个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体替原染色体，得群体S2；步步7 按变异率按变异率Pm所决定的变异次数所决定的变异次数m，从，从S2中随机确定中随机确定m个染个染色体，分别进行变异操作，并用产生的新染色体代替原染色色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体体，得群体S3；步步8 将群体将群体S3作为新一代种群，即用作为新一代种群，即用S3代替代替S，t=t+1，转步，转步3。11.2 11.2 基本遗传算法基本遗传算法2电气与信息工程学院电气与信息工程学院机器学习机器学习信息科学导论信息科学导论13
11、例例 利用遗传算法求解区间利用遗传算法求解区间0,31上的二次函数上的二次函数y=x2的的最大值。最大值。y=x2 31 XY11.3 11.3 遗传算法应用举例遗传算法应用举例2电气与信息工程学院电气与信息工程学院机器学习机器学习信息科学导论信息科学导论14 分析分析 原问题可转化为在区间原问题可转化为在区间0,31中搜索能使中搜索能使y取最大取最大值的点值的点a的问题。那么，的问题。那么，0,31 中的点中的点x就是个体就是个体,函数函数值值f(x)恰好就可以作为恰好就可以作为x的适应度，区间的适应度，区间0,31就是一个就是一个(解解)空间空间。11.3 11.3 遗传算法应用举例遗传算
12、法应用举例解解(1)设定种群规模设定种群规模,编码染色体，产生初始种群。编码染色体，产生初始种群。将种群规模设定为将种群规模设定为4；用；用5位二进制数编码染色体；取下列位二进制数编码染色体；取下列个体组成初始种群个体组成初始种群S1:s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)2电气与信息工程学院电气与信息工程学院机器学习机器学习信息科学导论信息科学导论15(2)定义适应度函数定义适应度函数,取适应度函数：取适应度函数：f(x)=x2(3)计算各代种群中的各个体的适应度计算各代种群中的各个体的适应度,并对其染色体进并对其染色体进行遗传操作
13、行遗传操作,直到适应度最高的个体直到适应度最高的个体(即即31（11111）)出现出现为止。为止。11.3 11.3 遗传算法应用举例遗传算法应用举例2电气与信息工程学院电气与信息工程学院机器学习机器学习信息科学导论信息科学导论16 首先计算种群首先计算种群S1中各个体中各个体 s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)的适应度的适应度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=36111.3 11.3 遗传
14、算法应用举例遗传算法应用举例2电气与信息工程学院电气与信息工程学院机器学习机器学习信息科学导论信息科学导论17再计算种群再计算种群S1中各个体的选择概率。中各个体的选择概率。NjjiixfxfxP1)()()(选择概率的计算公式为选择概率的计算公式为 由此可求得由此可求得 P(s1)=P(13)=0.14 P(s2)=P(24)=0.49 P(s3)=P(8)=0.06 P(s4)=P(19)=0.3111.3 11.3 遗传算法应用举例遗传算法应用举例2电气与信息工程学院电气与信息工程学院机器学习机器学习信息科学导论信息科学导论18 赌轮选择示意赌轮选择示意s40.31s20.49s10.1
15、4s30.06 赌轮选择法赌轮选择法11.3 11.3 遗传算法应用举例遗传算法应用举例2电气与信息工程学院电气与信息工程学院机器学习机器学习信息科学导论信息科学导论19在算法中赌轮选择法可用下面的子过程来模拟在算法中赌轮选择法可用下面的子过程来模拟:在在0,1区间内产生一个均匀分布的随机数区间内产生一个均匀分布的随机数r。若若rq1,则染色体则染色体x1被选中。被选中。若若qk-1rqk(2kN),则染色体则染色体xk被选中。被选中。其中的其中的qi称为染色体称为染色体xi(i=1,2,n)的积累概率的积累概率,其计算公式为其计算公式为 ijjixPq1)(11.3 11.3 遗传算法应用举
16、例遗传算法应用举例2电气与信息工程学院电气与信息工程学院机器学习机器学习信息科学导论信息科学导论20选择选择-复制复制 设从区间设从区间0,1中产生中产生4个随机数如下个随机数如下:r1=0.450126,r2=0.110347 r3=0.572496,r4=0.98503 染色体染色体 适应度适应度选择概率选择概率积累概率积累概率选中次数选中次数s1=01101 169 0.14 0.14 1s2=11000 576 0.49 0.63 2s3=01000 64 0.06 0.69 0s4=10011 361 0.31 1.00 111.3 11.3 遗传算法应用举例遗传算法应用举例2电气与
17、信息工程学院电气与信息工程学院机器学习机器学习信息科学导论信息科学导论21于是，经复制得群体：于是，经复制得群体：s1=11000（24）,s2=01101（13）s3=11000（24）,s4=10011（19）11.3 11.3 遗传算法应用举例遗传算法应用举例交叉交叉 设交叉率设交叉率pc=100%，即，即S1中的全体染色体都参加交叉运算。中的全体染色体都参加交叉运算。设设s1与与s2配对，配对，s3与与s4配对。分别交换后两位基因，得配对。分别交换后两位基因，得新染色体：新染色体：s1=11001（25）,s2=01100（12）s3=11011（27）,s4=10000（16）2电气
18、与信息工程学院电气与信息工程学院机器学习机器学习信息科学导论信息科学导论22变异变异 设变异率设变异率pm=0.001。这样，群体这样，群体S1中共有中共有 540.001=0.02位基因可以变异。位基因可以变异。0.02位显然不足位显然不足1位，所以本轮遗传操作不做变异。位，所以本轮遗传操作不做变异。于是，得到第二代种群于是，得到第二代种群S2：s1=11001（25）,s2=01100（12）s3=11011（27）,s4=10000（16）11.3 11.3 遗传算法应用举例遗传算法应用举例2电气与信息工程学院电气与信息工程学院机器学习机器学习信息科学导论信息科学导论23 第二代种群第二
19、代种群S2中各染色体的情况中各染色体的情况 染色体染色体 适应度适应度选择概率选择概率积累概率积累概率 估计的估计的选中次数选中次数s1=11001 625 0.36 0.36 1s2=01100 144 0.08 0.44 0s3=11011 729 0.41 0.85 2s4=10000 256 0.15 1.00 111.3 11.3 遗传算法应用举例遗传算法应用举例2电气与信息工程学院电气与信息工程学院机器学习机器学习信息科学导论信息科学导论24 假设这一轮选择假设这一轮选择-复制操作中，种群复制操作中，种群S2中的中的4个染色体都个染色体都被选中，则得到群体：被选中，则得到群体：s1
20、=11001（25）,s2=01100（12）s3=11011（27）,s4=10000（16）做交叉运算，让做交叉运算，让s1与与s2，s3与与s4 分别交换后三位基因，得分别交换后三位基因，得 s1=11100（28）,s2=01001（9）s3=11000（24）,s4=10011（19）这一轮仍然不会发生变异。这一轮仍然不会发生变异。11.3 11.3 遗传算法应用举例遗传算法应用举例2电气与信息工程学院电气与信息工程学院机器学习机器学习信息科学导论信息科学导论25于是，得第三代种群于是，得第三代种群S3：s1=11100（28）,s2=01001（9）s3=11000（24）,s4=
21、10011（19）11.3 11.3 遗传算法应用举例遗传算法应用举例 第三代种群第三代种群S3中各染色体的情况中各染色体的情况 染色体染色体 适应度适应度选择概率选择概率积累概率积累概率 估计的估计的选中次数选中次数s1=11100 784 0.44 0.44 2s2=01001 81 0.04 0.48 0s3=11000 576 0.32 0.80 1s4=10011 361 0.20 1.00 12电气与信息工程学院电气与信息工程学院机器学习机器学习信息科学导论信息科学导论26 设这一轮的选择设这一轮的选择-复制结果为：复制结果为：s1=11100（28）,s2=11100（28）s3
22、=11000（24）,s4=10011（19）做交叉运算，让做交叉运算，让s1与与s4，s2与与s3 分别交换后两位基因，得分别交换后两位基因，得 s1=11111（31）,s2=11100（28）s3=11000（24）,s4=10000（16）这一轮仍然不会发生变异。这一轮仍然不会发生变异。11.3 11.3 遗传算法应用举例遗传算法应用举例2电气与信息工程学院电气与信息工程学院机器学习机器学习信息科学导论信息科学导论27 于是，得第四代种群于是，得第四代种群S4：s1=11111（31）,s2=11100（28）s3=11000（24）,s4=10000（16）显然，在这一代种群中已经出
23、现了适应度最高的染色体显然，在这一代种群中已经出现了适应度最高的染色体s1=11111。于是，遗传操作终止，将染色体于是，遗传操作终止，将染色体“11111”作为最终作为最终结果输出。结果输出。然后，将染色体然后，将染色体“11111”解码为表现型，即得所求的最解码为表现型，即得所求的最优解：优解：31。将将31代入函数代入函数y=x2中，即得原问题的解，即函数中，即得原问题的解，即函数y=x2的最的最大值为大值为961。11.3 11.3 遗传算法应用举例遗传算法应用举例2电气与信息工程学院电气与信息工程学院机器学习机器学习信息科学导论信息科学导论28YYy=x2 8 13 19 24 X第
24、一代种群及其适应度第一代种群及其适应度y=x2 12 16 25 27 XY第二代种群及其适应第二代种群及其适应度度y=x2 9 19 24 28 XY第三代种群及其适应第三代种群及其适应度度y=x2 16 24 28 31 X第四代种群及其适应第四代种群及其适应度度11.3 11.3 遗传算法应用举例遗传算法应用举例2电气与信息工程学院电气与信息工程学院机器学习机器学习信息科学导论信息科学导论29遗传算法的主要特点遗传算法的主要特点 遗传算法一般是直接在解空间搜索遗传算法一般是直接在解空间搜索,而不像图搜索而不像图搜索那样一般是在问题空间搜索那样一般是在问题空间搜索,最后才找到解。最后才找到
25、解。遗传算法的搜索随机地始于搜索空间的一个点集遗传算法的搜索随机地始于搜索空间的一个点集,而不像图搜索那样固定地始于搜索空间的初始节点或终止节而不像图搜索那样固定地始于搜索空间的初始节点或终止节点点,所以遗传算法是一种随机搜索算法。所以遗传算法是一种随机搜索算法。11.4 11.4 遗传算法的特点与优势遗传算法的特点与优势2电气与信息工程学院电气与信息工程学院机器学习机器学习信息科学导论信息科学导论30 遗传算法总是在寻找优解遗传算法总是在寻找优解,而不像图搜索那样并非总是而不像图搜索那样并非总是要求优解要求优解,而一般是设法尽快找到解而一般是设法尽快找到解,所以遗传算法又是一种所以遗传算法又
26、是一种优化搜索算法。优化搜索算法。遗传算法的搜索过程是从空间的一个点集遗传算法的搜索过程是从空间的一个点集(种群种群)到另一到另一个点集个点集(种群种群)的搜索的搜索,而不像图搜索那样一般是从空间的一个而不像图搜索那样一般是从空间的一个点到另一个点地搜索。点到另一个点地搜索。因而它实际是一种并行搜索因而它实际是一种并行搜索,适合大适合大规模并行计算规模并行计算,而且这种种群到种群的搜索有能力跳出局部而且这种种群到种群的搜索有能力跳出局部最优解。最优解。11.4 11.4 遗传算法的特点与优势遗传算法的特点与优势2电气与信息工程学院电气与信息工程学院机器学习机器学习信息科学导论信息科学导论31遗
27、传算法的适应性强遗传算法的适应性强,除需知适应度函数外除需知适应度函数外,几乎不几乎不需要其他的先验知识。需要其他的先验知识。遗传算法长于全局搜索遗传算法长于全局搜索,它不受搜索空间的限制性它不受搜索空间的限制性假设的约束假设的约束,不要求连续性不要求连续性,能以很大的概率从离散的、多极能以很大的概率从离散的、多极值的、值的、含有噪声的高维问题中找到全局最优解。含有噪声的高维问题中找到全局最优解。11.4 11.4 遗传算法的特点与优势遗传算法的特点与优势2电气与信息工程学院电气与信息工程学院机器学习机器学习信息科学导论信息科学导论32遗传算法的应用遗传算法的应用遗传算法在人工智能的众多领域便
28、得到了广泛应用。例如，遗传算法在人工智能的众多领域便得到了广泛应用。例如，机器学习、聚类、控制（如煤气管道控制）、规划（如生机器学习、聚类、控制（如煤气管道控制）、规划（如生产任务规划）、设计（如通信网络设计、布局设计）、调产任务规划）、设计（如通信网络设计、布局设计）、调度（如作业车间调度、机器调度、运输问题）、配置（机度（如作业车间调度、机器调度、运输问题）、配置（机器配置、分配问题）、组合优化（如器配置、分配问题）、组合优化（如TSP、背包问题）、背包问题）、函数的最大值以及图像处理和信号处理等等。函数的最大值以及图像处理和信号处理等等。另一方面，人们又将遗传算法与其他智能算法和技术相结另一方面，人们又将遗传算法与其他智能算法和技术相结合，使其问题求解能力得到进一步扩展和提高。例如，将合，使其问题求解能力得到进一步扩展和提高。例如，将遗传算法与模糊技术、神经网络相结合，已取得了不少成遗传算法与模糊技术、神经网络相结合，已取得了不少成果。果。11.4 11.4 遗传算法的特点与优势遗传算法的特点与优势
