杭州电子科技大学：《人工智能导论》课程教学资源（PPT课件讲稿）第四讲 遗传算法

第西遗传算法

Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 第四讲 遗传算法

遗传算法基本概念 基本概念 发展历史，基本概念，遗传操作 基本步骤 遗传算法基本步骤 基本步骤、算法参数 基本遗传算法应用 基本遗传算法应用举例 个 函数求极值 旅行商问题求解 旅行商问题求解 遗传算法参数设定 总结 总结 遗传算法的特点与优势 angzhou Dianzi University杭州电子科技大学 Schoolo时Computer Science and Technology计算机学院周文晖

Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 基本概念 旅行商问题求解 基本步骤 基本遗传算法应用 总结 遗传算法基本概念 发展历史， 基本概念，遗传操作 … 遗传算法基本步骤 基本步骤、算法参数 基本遗传算法应用举例 旅行商 问题求解 遗传算法参数设定… 总结 ？ 遗传算法的特点与优势 函数求极值

遗传算法基本概念 基本概念 发展历史，基本概念，遗传操作… 基本步骤 遗传算法基本步骤 基本步骤、算法参数 基本遗传算法应用 基本遗传算法应用举例 个 函数求极值 旅行商问题求解 旅行商问题求解 遗传算法参数设定 总结 总结 遗传算法的特点与优势 angzhou Dianzi University杭州电子科技大学 Schoolo时Computer Science and Technology计算机学院周文晖

Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 基本概念 旅行商问题求解 基本步骤 基本遗传算法应用 总结 遗传算法基本概念 发展历史， 基本概念，遗传操作 … 遗传算法基本步骤 基本步骤、算法参数 基本遗传算法应用举例 旅行商 问题求解 遗传算法参数设定… 总结 ？ 遗传算法的特点与优势 函数求极值

遗传算法发展历史 遗传算法的诞生 1、1967年，Holland学生J.D.Bagley?在博士论文中首次提出“遗传算法(Genetic Algorithms)”; 2、1971年，R.B.Hollstien在他的博士论文中首次把遗传算法用于函数优化； 3、1975年，Holland出版了他的著名专著《自然系统和人工系统的自适应》 (Adaptation in Natural and Artificial Systems),这是第一本系统论述遗传算法的专著； 4、K.A.De Jong完成了他的博士论文《一类遗传自适应系统的行为分析》 (An Analysis of the Behavior of a Class of Genetic Adaptive System) angzhou Dianzi University杭州电子科技大学 Sckool of Computer3 Science and Technology计算机学院周文晖

Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 遗传算法发展历史 遗传算法的诞生 1、1967年，Holland学生J. D. Bagley在博士论文中首次提出“遗传算法（Genetic Algorithms）”； 2、 1971年，R.B.Hollstien在他的博士论文中首次把遗传算法用于函数优化； 3、 1975年，Holland出版了他的著名专著《自然系统和人工系统的自适应》 （Adaptation in Natural and Artificial Systems），这是第一本系统论述遗传算法的专著； 4、 K.A.De Jong完成了他的博士论文《一类遗传自适应系统的行为分析》 （An Analysis of the Behavior of a Class of Genetic Adaptive System）

基本概念 个体 ·个体就是模拟生物个体，对问题中对象（一般就是问题的解）的一种称呼。 ·一个个体也就是搜索空间中的一个点。 种群 ·种群(population)就是模拟生物种群，由若干个体组成的群体 ·它一般是整个搜索空间的一个很小的子集 angzhou Dianzi University杭州电子科技大学 Sckool of Computer3 Science and Technology计算机学院周文晖

Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 基本概念 个体 • 个体就是模拟生物个体，对问题中对象（一般就是问题的解）的一种称呼。 • 一个个体也就是搜索空间中的一个点。 种群 • 种群(population)就是模拟生物种群, 由若干个体组成的群体. • 它一般是整个搜索空间的一个很小的子集

基本概念一 适应度与适应度函数 适应度(fitness) ·借鉴生物个体对环境的适应程度，对问题中的个体对象所设计的表征其 优劣的一种测度。 适应度函数(fitness function) ·是问题中全体个体与其适应度之间的一个对应关系。 ·通常为实值函数。 ·该函数就是遗传算法中指导搜索的评价函数。 angzhou Dianzi University杭州电子科技大学 Sckool of Computer3 Science and Technology计算机学院周文晖

Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 基本概念——适应度与适应度函数 适应度(fitness) • 借鉴生物个体对环境的适应程度, 对问题中的个体对象所设计的表征其 优劣的一种测度。 适应度函数(fitness function) • 是问题中全体个体与其适应度之间的一个对应关系。 • 通常为实值函数。 • 该函数就是遗传算法中指导搜索的评价函数

基本概念一染色体与基因 染色体(chromosome)与基因(gene) •染色体是问题中个体的某种字符串形式的编码表示。 ·字符串中的字符称为基因。 例如： ·个体 染色体 9 1001 。(2,5,6)--010101110 angzhou Dianzi University杭州电子科技大学 Sckool of Computer3 Science and Technology计算机学院周文晖

Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 基本概念——染色体与基因 染色体（chromosome）与基因（gene） • 染色体是问题中个体的某种字符串形式的编码表示。 • 字符串中的字符称为基因。 例如： • 个体 染色体 • 9      ‐‐‐‐ 1001 • （2，5，6） ‐‐‐‐ 010 101 110

基本概念一遗传操作 遗传操作亦称遗传算子(genetic operator) 关于染色体的运算。 遗传算法中有三种遗传操作： ·选择-复制(selection-reproduction) ·交叉(crossover,亦称交换、交配或杂交) ·变异(mutation,亦称突变) Hangzhou Dianzi University杭州电子科技大学 Schoolo可Computer Science and Technology计算机学院周文晖

Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 基本概念——遗传操作 遗传操作亦称遗传算子(genetic operator) 关于染色体的运算。 遗传算法中有三种遗传操作: • 选择-复制(selection-reproduction) • 交叉(crossover，亦称交换、交配或杂交) • 变异(mutation，亦称突变)

选择-复制 对于一个规模为N的种群S,按每个染色体x,∈S的选择概率P(x,)所决定的选中机 会，分N次从S中随机选定N个染色体，并进行复制。 这里的选择概率P(x)的计算公式为： P(x)= f(x;) ∑fx,) 1 Hangzhou Dianzi University杭州电子科技大学 Sckool of Computer3 Science and Technology计算机学院周文晖

Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 选择‐复制 对于一个规模为N 的种群 S,按每个染色体xi∈S 的选择概率P(xi)所决定的选中机 会, 分N次从S中随机选定N个染色体, 并进行复制。 这里的选择概率P(xi)的计算公式为:    N j j i i f x f x P x 1 ( ) ( ) ( )

交叉 交叉：互换两个染色体某些位上的基因。 例如，设染色体s1=01001011,s2=10010101,交换其后4位基因，即 01001011,10010101 01000101,10011011 s1'=01000101,s2'=10011011 可以看做是原染色体s1和s2的子代染色体。 Hangzhou Dianzi University杭州电子科技大学 Sckool of Computer3 Science and Technology计算机学院周文晖

Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 交叉 交叉: 互换两个染色体某些位上的基因。 例如, 设染色体 s1=01001011, s2=10010101, 交换其后4位基因, 即 s1′=01000101, s2′=10011011 可以看做是原染色体s1和s2的子代染色体