第4章基于遗传算法的随机优化搜索 4,1基本概念潼 4.2基本遗传算法潼 4.3遗传算法应用举例潼 4.4遗传算法的特点与优势
第4章 基于遗传算法的随机优化搜索 4.1 基本概念 4.2 基本遗传算法 4.3 遗传算法应用举例 4.4 遗传算法的特点与优势
4.1基本概念 个体与种群蕌 ●个体就是模拟生物个体而对问题中的对象 (一般就是问题的解)的一种称呼,一个个 体也就是搜索空间中的一个点 ●种群( population)就是模拟生物种群而由若 干个体组成的群体,它一般是整个搜索空间 的一个很小的子集
4.1 基本概念 1. 个体与种群 ● 个体就是模拟生物个体而对问题中的对象 (一般就是问题的解)的一种称呼,一个个 体也就是搜索空间中的一个点。 ● 种群(population)就是模拟生物种群而由若 干个体组成的群体, 它一般是整个搜索空间 的一个很小的子集
2.适应度与适应度函数蕌 ●适应度ftne就是借鉴生物个体对环境的 适应程度而对问题中的个体对象所设计的 表征其优劣的一种测度。 ●适应度函数( fitness function)就是问题中的 全体个体与其适应度之间的一个对应关系 它一般是一个实值函数。该函数就是遗传算 法中指导搜索的评价函数
2. 适应度与适应度函数 ● 适应度(fitness)就是借鉴生物个体对环境的 适应程度,而对问题中的个体对象所设计的 表征其优劣的一种测度。 ● 适应度函数(fitness function)就是问题中的 全体个体与其适应度之间的一个对应关系。 它一般是一个实值函数。该函数就是遗传算 法中指导搜索的评价函数
3.染色体与基因蕌 染色体( chromosome)就是问题中个体的 某种字符串形式的编码表示。字符串中的字符 也就称为基因(gene)。 例如: 个体 染色体 1001 (2,5,6) 010101110
3. 染色体与基因 染色体(chromosome)就是问题中个体的 某种字符串形式的编码表示。字符串中的字符 也就称为基因(gene)。 例如: 个体 染色体 9 ---- 1001 (2,5,6)---- 010 101 110
4.遗传操作蕌 亦称遗传算子( genetic operator),就是关 于染色体的运算。遗传算法中有三种遗传操作 ●选择-复制( selection- reproduction) ●交叉( crossover,亦称交换、交配或杂交) ●变异( mutation,亦称突变)
4. 遗传操作 亦称遗传算子(genetic operator),就是关 于染色体的运算。遗传算法中有三种遗传操作: ● 选择-复制(selection-reproduction) ● 交叉(crossover,亦称交换、交配或杂交) ● 变异(mutation,亦称突变)
选择-复制通常做法是:对于一个规模为N 的种群S按每个染色体x1∈S的选择概率P(x)所决 定的选中机会,分N次从S中随机选定N个染色体, 并进行复制。 这里的选择概率P(x)的计算公式为 P(x1)= f(x) ∑f(x
选择-复制 通常做法是:对于一个规模为N 的种群S,按每个染色体xi∈S的选择概率P(xi)所决 定的选中机会, 分N次从S中随机选定N个染色体, 并进行复制。 N j j i i f x f x P x 1 ( ) ( ) ( ) 这里的选择概率P(xi)的计算公式为
交叉就是互换两个染色体某些位上的基因。 例如,设染色体S1=01001011,S2=10010101 交换其后4位基因,即 0100:1011001}0101 010010101,100111011 S1'=01000101,S2=10011011 可以看做是原染色体S1和S2的子代染色体
交叉 就是互换两个染色体某些位上的基因。 s1 ′=01000101, s2 ′=10011011 可以看做是原染色体s1和s2的子代染色体。 例如, 设染色体 s1=01001011, s2=10010101, 交换其后4位基因, 即
变异就是改变染色体某个(些)位上的基因。 例如,设染色体S=11001101 将其第三位上的0变为1,即 S=1100110111101101=s。 s'也可以看做是原染色体s的子代染色体
变异 就是改变染色体某个(些)位上的基因。 例如, 设染色体 s=11001101 将其第三位上的0变为1, 即 s=11001101 →11101101= s′ 。 s′也可以看做是原染色体s的子代染色体
4.2基本遗传算法 生成初始种群 计算适应度 <终止? 结束) 选择-复制 交叉 变异 遗传算法基本流程框图 生成新一代种群
4.2 基本遗传算法 遗传算法基本流程框图 生成初始种群 计算适应度 选择-复制 交叉 变异 生成新一代种群 终止 ? 结束
算法中的一些控制参数: 种群规模 ■最大换代数 ■交叉率 crossover rate)就是参加交叉运算的 染色体个数占全体染色体总数的比例,记为Pe 取值范围一般为0.4~0.99。蕌 变异率 mutation rate)是指发生变异的基因位 数所占全体染色体的基因总位数的比例,记为 Pn,取值范围一般为0.0001~0.1
算法中的一些控制参数: ■ 种群规模 ■ 最大换代数 ■ 交叉率(crossover rate)就是参加交叉运算的 染色体个数占全体染色体总数的比例,记为Pc , 取值范围一般为0.4~0.99。 ■ 变异率(mutation rate)是指发生变异的基因位 数所占全体染色体的基因总位数的比例,记为 Pm,取值范围一般为0.0001~0.1