基本概念一 适应度与适应度函数 适应度(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的子代染色体