文档介绍：第4章遗传算法 基本概念 选择算子 交叉算子 变异算子 基本遗传算法 基本实现技术 遗传算法应用第4章遗传算法?生物进化?自然法则?优胜劣汰?适者生存?有性繁殖?基因通过有性繁殖不断进行混合和重组?遗传算法?从生物界按照自然选择和有性繁殖、遗传变异的自然进化现象中得到启发,而设计的一种优化搜索算法第4章遗传算法?应用?函数优化?组合优化:旅行商、图形化分…?生产调度:车间调度、生产规划…?自动控制:控制器、参数辨识…?机器人智能控制:机器人路径规划、运动轨迹规划…?图像处理与模式识别:特征提取、图像分割…?人工生命:进化模型、学****模型、行为模型…?遗传程序设计?机器学****基本概念?个体?个体就是模拟生物个体而对问题中的对象(一般就是问题的解)的一种称呼?一个个体也就是搜索空间中的一个点?种群?种群(population) 就是模拟生物种群而由若干个体组成的群体?它一般是整个搜索空间的一个很小的子集?通过对种群实施遗传操作,使其不断更新换代而实现对整个论域空间的搜索 基本概念?适应度(fitness) ?借鉴生物个体对环境的适应程度,而对问题中的个体对象所设计的表征其优劣的一种测度?适应度函数(fitness function ) ?问题中的全体个体与其适应度之间的一个对应关系?一般是一个实值函数?该函数就是遗传算法中指导搜索的评价函数 基本概念?染色体(chromosome ) ?染色体是由若干基因组成的位串(生物学) ?个体对象由若干字符串组成来表示(遗传算法) ?遗传算法(ic algorithm) ?染色体就是问题中个体的某种字符串形式的编码表示?染色体以字符串来表示?基因是字符串中的一个个字符个体染色体 9 ---- 1001 (2,5,6)---- 010 101 110 基本概念?遗传算子(ic operator) ?选择(selection) ?交叉(crossover) ?变异(mutation) 选择算子选择算子?模拟生物界优胜劣汰的自然选择法则的一种染色体运算?从种群中选择适应度较高的染色体进行复制,以生成下一代种群算法: ?个体适应度计算?在被选集中每个个体具有一个选择概率?选择概率取决于种群中个体的适应度及其分布?个体适应度计算,即个体选择概率计算?个体选择方法?按照适应度进行父代个体的选择 选择算子?个体适应度计算?按比例的适应度计算(proportional fitness assignment) ?基于排序的适应度计算(rank-based fitness assignment) ?个体选择方法?***赌选择(roulette wheel selection) ?随机遍历抽样(stochastic universal sampling) ?局部选择(local selection) ?截断选择(truncation selection) ?锦标赛选择(tournament selection) 按比例的适应度计算算法: 对一个规模为 N的种群 S,按每个染色体 x i?S的选择概率 P(x i)所决定的选中机会,分 N次从 S中随机选择 N个染色体,并进行复制其中: ?f为适应度函数?f(x i)为x i的适应度 1 ( ) ( ) ( ) iiNjj f x P x f x ???优胜劣汰 ,随机选中概率越大 ,选中次数越多