遗传算法理论及用于求解实际问题.pptVIP

3.1 遗传算法的基本概念 3.2 遗传编码 3.3 适应值函数 3.4 遗传操作 3.5 初始化群体 3.6 控制参数的选取 3.7 算法的终止准则 3.8 遗传算法的基本理论 3.9 遗传算法简例 3.10遗传算法的应用领域 3.1 遗传算法的基本概念 基本思想使用模拟生物和人类进化的方法求解复杂的优化问题，因而也称为模拟进化优化算法。 遗传算法将择优与随机信息交换结合在一起，在每一代中，使用上代中最好的，即最适应环境的位或片段，形成新的人工生物集。 遗传算法是一个迭代过程，在每次迭代中都保留一组候选解，并按某种优劣指标进行排序，然后按某种指标从中选出一些解，利用遗传算子，即下面要讲到的遗传操作，对其进行运算以产生新一代的一组解。重复上述过程，直到满足指定的收敛要求为止。 3.1.1 遗传算法的基本概念 定义3.1 个体: 个体是一个数据结构，用来描述基本的遗传结构。 定义3.2 适应性：每个个体有一对应的适应值。在优化问题中，适应值来自于一个估计函数。 定义3.3 群体:由个体组成的集合。 定义3.4 遗传操作：遗传操作作用于群体而产生新的群体。 标准的代遗传操作一般包括选择(或复制)，交叉(或重组)和变异三种基本形式。 一个简单的遗传操作实例 3.1.2 遗传算法的基本流程 遗传算法涉及五大要素： 参数编码 初始群体设定 适应度函数设计 遗传操作设计 控制参数设定 遗传算法的执行过程 选择编码策略，把参数集合Ｘ和域转换为相应编码空间Ｓ； 定义适应值函数f(X); 定义遗传策略，包括选择群体大小、选择、交叉、变异方法以及确定交叉概率Ｐｃ、变异概率Ｐｍ等遗传参数； 随机初始化生成群体Ｐ(t); 计算群体中个体的适应值f(X); 按照遗传策略，运用选择、交叉和变异操作作用于群体，形成下一代群体； 判断群体性能是否满足某一指标，或者已完成预定迭代次数，不满足则返回步骤6），或者修改遗传策略再返回步骤6）。 3.2 遗传编码 3.2.1 二进制编码 3.2.2 Gray编码 3.2.3 实数编码 3.2.4 有序编码 3.2.5 结构式编码 3.2.1 二进制编码 在二进制编码过程中，首先要确定二进制串的长度l，串长l取决于变量的定义域及计算所需的精度。 例3.2 变量x的定义域为[－2，5]，要求其精度为10-6，则我们需将[－2，5]分成至少7 000 000个等长小区域，而每个小区域用一个二进制串表示。于是串长至少等于23，这是因为： 4194304=2227000000223= 8388608 这样，计算中的任何一个二进制串（b22b21…b0）都对应[-2，5]中的一个点。 3.2.2 Gray编码 Gray编码即是将二进制码通过如下变换进行转换得到的码。 设有二进制串（β1β2…βn），对应的Gray串为（γ1γ2…γn），则从二进制码到Gray码的变换为 其中?表示模2加法。 从一个Gray码到二进制串的变换为 例3.3 二进制串1101011对应的Gray串为101110。 3.2.3 实数编码 为了克服二进制编码的缺点，对于问题的变量是实向量的情形，直接可以采用十进制进行编码，这样可以直接在解的表现形式上进行遗传操作，从而便于引入与问题领域相关的启发式信息以增加系统的有哪些信誉好的足球投注网站能力 例3 作业调度问题（JSP）的种群个体编码常用m×n的矩阵Y=[yij]，i=1，2，…，m，j=1，2，…，n（n为从加工开始的天数，m为工件的优先顺序）。表示工件i在第j日的加工时间。下表是一个随机生成的个体所示。 3.2.4 有序编码 对很多组合优化问题，目标函数的值不仅与表示解的字符串中各字符的值有关，而且与其所在字符串中的位置有关。这样的问题称为有序问题。 若目标函数的值只与表示解的字符串中各字符的位置有关而与其具体的字符值无关，则称为纯有序问题，如采用顶点排列的旅行商问题。 例3.4 有10个城市的TSP问题，城市序号为{1，2，…，10}，则编码位串表示对城市采用按序号升序方法访问行走路线。 1 3 5 7 9 2 4 6 8 10 表示按特定“1 →3 →5 →7 →9 →2 →4 →6 →8 →10 →1”依次访问各个城市。 3.2.5 结构式编码 对很多问题其更自然的表示是树或图的形式，这时采用其它形式的变可能很困难。这种将问题的解表达成树或图的形式的编码称为结构式编码。 3.3 适应值函数 适应值函数构成了个体的生成环境。根据个体的适应值可以决定它在此环境下的生存能力。 若SL表示位串空间，SL上的适应值函数可表示为f : SL→R+，f为实值函数，R+表示非负实数集合。 针对进化过程中关于遗传操作的控制的