张砦遗传算法在多目标优化中的应用.ppt

遗传算法在多目标优化中的应用 张砦 目录 一 遗传算法概述二 多目标优化问题三 实例1 Rosenbrock函数最值问题四 实例2 智能组卷问题 一 遗传算法概述 1 1遗传算法的生物学基础1 2遗传算法搜索机制1 3遗传算法的发展1 4基本遗传算法 SGA 1 5遗传算法的特点1 6遗传算法的收敛性分析1 7遗传算法研究的主要问题1 8遗传算法的应用 1 1遗传算法的生物学基础生物在自然界中的生存繁衍 显示出了其对自然环境的自适应能力 受其启发 人们致力于对生物各种生存特性的机理研究和行为模拟 为人工自适应系统的设计和开发提供了广阔的前景 遗传算法 GeneticAlgorithms 简称GAs 所借鉴的生物学基础是生物的遗传和进化 1 生物的所有遗传信息都包含在其染色体中 染色体决定了生物的性状 2 染色体是由基因及其有规律的排列所构成的 遗传和进化过程发生在染色体上 3 生物的繁殖过程是由其基因的复制过程来完成的 4 通过同源染色体之间的交叉或染色体的变异会产生新的物种 使生物呈现新的性状 5 对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多的机会遗传到下一代 1 2遗传算法搜索机制 遗传算法模拟自然选择和自然遗传过程中发生的繁殖 交叉和基因突变现象 染色体的变化 将实际问题的解答描述成染色体的形式 进行类似生物进化现象的操作以求解 对每次迭代中保留的候选解 按某种指标从解群中选取较优的个体 利用遗传算子 选择 交叉和变异 对这些个体进行组合 产生新一代的候选解群 重复此过程 直到满足某种收敛指标为止 1 3遗传算法的发展 1 萌芽期 50年代后期至70年代初期 50年代后期 一些生物学家着手采用电子计算机模拟生物的遗传系统 尽管这些工作纯粹是研究生物现象 但其中已使用现代遗传算法的一些标识方式 1965年 德国的L Rechenberg等人正式提出进化策略的方法 当时的进化策略只有一个个体 而且进化操作也只有变异一种 1965年 美国的L j Fogel正式提出进化规划 在计算中采用多个个体组成的群体 而且只运用变异操作 60年代期间 美国J H Holland在研究自适应系统时 提出系统本身与外部环境相互协调的遗传算法 1968年 J H Holland教授又提出模式理论 它成为遗传算法的主要理论基础 1967年 Bagley发表了关于遗传算法应用的论文 在其论文中首次使用 遗传算法 GeneticAlgorithm 一词 2 成长期 70年代中期至80年代末期 1975年 J H Holland教授的专著 AdaptationinNaturalandArtificialSystem 正式出版 全面地介绍了遗传算法 人们常常把这一事件视作遗传算法问世的标志 Holland也被视作遗传算法的创始人 1975年 De Jong在其博士论文中结合模式定理进行了大量的纯数值函数优化计算实验 树立了遗传算法的工作框架 得到了一些重要且具有指导意义的结论 1987年 美国D Lawrence总结人们长期从事遗传算法的经验 公开出版 GeneticAlgorithmandSimulatedAnnealing 一书 以论文集形式用大量实例介绍遗传算法 1985年 作为Holland的学生 D E Goldberg博士出版专著 GeneticAlgorithms inSearch OptimizationandMachineLearning 全面 系统地介绍遗传算法 使这一技术得到普及与推广 该书被人们视为遗传算法的教科书 1985年 在美国举行第一届遗传算法国际学术会议 InternationalConferenceonGeneticAlgorithms 简称ICGA 与会者交流运用遗传算法的经验 随后 每2年左右都举行一次这种会议 3 发展期 90年代以后 90年代 遗传算法不断地向广度和深度发展 1991年 D Lawrence出版 HandbookofGeneticAlgorithms 一书 详尽地介绍遗传算法的工作细节 1996年Z Michalewicz的专著 遗传算法 数据结构 进化程序 深入讨论了遗传算法的各种专门问题 同年 T Back的专著 进化算法的理论与实践 进化策略 进化规划 遗传算法 深入阐明进化算法的许多理论问题 1992年 Koza出版专著 GeneticProgramming ontheProgrammingofComputerbyMeansofNaturalSelection 该书全面介绍了遗传规划的原理及应用实例 表明遗传规划己成为进化算法的一个重要分支 1994年 Koza又出版第二部专著 GeneticProgramming AutomaticDiscoveryofReusablePrograms 提出自动定义函数的新概念 在遗传规划中引入子程序的新技术 同年 K E Kinnear主编 AdvancesinGeneticProgramming 汇集许多研究工作者有关应用遗传规划的经验和技术 1 4基本遗传算法 SGA 1 4 1基本遗传算法的构成要素 1 染色体编码方法基本遗传算法使用固定长度的二进制符号串来表示群体中的个体 其等位基因由二值符号集 0 1 组成 初始群体中各个个体的基因值用均匀分布的随机数来生成 如 100111001000101101 就可表示一个个体 该个体的染色体长度是18 2 个体适应度评价基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少 为正确计算这个概率 这里要求所有个体的适应度必须为正数或零 这样 根据不同种类的问题 必须预先确定好由目标函数值到个体适应度之间的转换规则 特别是要预先确定好当目标函数值为负数时的处理方法 3 遗传算子基本遗传算法使用下述三种遗传算子 选择运算 使用比例选择算子 交叉运算 使用单点交叉算子 变异运算 使用基本位变异算子 4 基本遗传算法的运行参数基本遗传算法有下述4个运行参数需要提前设定 M 群体大小 即群体中所含个体的数量 一般取20 100 T 遗传运算的终止进化代数 一般取100 500 pc 交叉概率 一般取0 4 0 99 pm 变异概率 一般取0 0001 0 1说明 这4个运行参数对遗传算法的求解结果和求解效率都有一定的影响 但目前尚无合理选择它们的理论依据 在遗传算法的实际应用中 往往需要经过多次试算后才能确定出这些参数合理的取值大小或取值范围 1 4 2基本遗传算法的形式化定义基本遗传算法可定义为一个7元组 GA M F s c m pc pm M 群体大小 F 个体适应度评价函数 s 选择操作算子 c 交叉操作算子 m 变异操作算子 pc 交叉概率 pm 变异概率 1 4 3基本遗传算法的实现 1 编码与解码假设某一参数的取值范围是 umin umax 我们用长度为 的二进制编码符号串来表示该参数 则它总共能够产生2 种不同的编码 参数编码时的对应关系如下 00000000 00000000 0umin00000000 00000001 1umin 00000000 00000010 2umin 2 11111111 11111111 2 1umax 其中 为二进制编码的编码精度 其公式为 假设某一个体的编码是 x blbl 1bl 2 b2b1则对应的解码公式为 例 设 3 0 x 12 1 精度要求 1 10000 由公式 即 217 151001 218x需要18位 0 1 符号表示 如 010001001011010000解码 得 2 个体适应度评价 1 当优化目标是求函数最大值 并且目标函数总取正值时 可以直接设定个体的适应度F X 就等于相应的目标函数值f X 即 F X f X 2 对于求目标函数最小值的优化问题 理论上只需简单地对其增加一个负号就可将其转化为求目标函数最大值的优化问题 即 minf X max f X 但实际优化问题中的目标函数值有正也有负 优化目标有求函数最大值 也有求函数最小值 显然上面两式保证不了所有情况下个体的适应度都是非负数这个要求 3 选择算子作用 从当前代群体中选择出一些比较优良的个体 并将其复制到下一代群体中 比例选择算子 指个体被选中并遗传到下一代群体中的概率与该个体的适应度大小成正比 轮盘选择 轮盘法的基本精神是 个体被选中的概率取决于个体的相对适应度 显然 个体适应度愈高 被选中的概率愈大 但是 适应度小的个体也有可能被选中 以便增加下一代群体的多样性 4 交叉算子作用 通过交叉 子代的基因值不同于父代 交换是遗传算法产生新个体的主要手段 正是有了交换操作 群体的性态才多种多样 单点交叉算子的具体计算过程如下 对群体中的个体进行两两随机配对 每一对相互配对的个体 随机设置某一基因座之后的位置为交叉点 对每一对相互配对的个体 依设定的交叉概率pc在其交叉点处相互交换两个个体的部分染色体 从而产生出两个新的个体 5 变异算子基本位变异算子 最简单和最基本的变异操作算子 对于基本遗传算法中用二进制编码符号串所表示的个体 若需要进行变异操作的某一基因座上的原有基因值为0 则变异操作将该基因值变为1 反之 若原有基因值为1 则变异操作将其变为0 具体执行过程 对个体的每一个基因座 依变异概率pm指定其为变异点 对每一个指定的变异点 对其基因值做取反运算或用其它等位基因值来代替 从而产生出一个新的个体 A 1010101010A 1010001010 变异点 基本位变异 1 4 4算法流程图 1 5遗传算法的特点 1 群体搜索 易于并行化处理 2 不是盲目穷举 而是启发式搜索 3 适应度函数不受连续 可微等条件的约束 适用范围很广 遗传算法的本质 对染色体模式所进行的一系列运算 即通过选择算子将当前种群中的优良模式遗传到下一代种群中 利用交叉算子进行模式重组 利用变异算子进行模式突变 通过这些遗传操作 模式逐步向较好的方向进化 最终得到问题的最优解 1 6遗传算法的收敛性分析 遗传算法要实现全局收敛 首先要求任意初始种群经有限步都能到达全局最优解 其次算法必须由保优操作来防止最优解的遗失 与算法收敛性有关的因素主要包括种群规模 选择操作 交叉概率和变异概率 1 种群规模对收敛性的影响 通常 种群太小则不能提供足够的采样点 以致算法性能很差 种群太大 尽管可以增加优化信息 阻止早熟收敛的发生 但无疑会增加计算量 造成收敛时间太长 表现为收敛速度缓慢 2 选择操作对收敛性的影响 选择操作使高适应度个体能够以更大的概率生存 从而提高了遗传算法的全局收敛性 如果在算法中采用最优保存策略 即将父代群体中最佳个体保留下来 不参加交叉和变异操作 使之直接进入下一代 最终可使遗传算法以概率1收敛于全局最优解 3 交叉概率对收敛性的影响 交叉操作用于个体对 产生新的个体 实质上是在解空间中进行有效搜索 交叉概率太大时 种群中个体更新很快 会造成高适应度值的个体很快被破坏掉 概率太小时 交叉操作很少进行 从而会使搜索停滞不前 造成算法的不收敛 4 变异概率对收敛性的影响 变异操作是对种群模式的扰动 有利于增加种群的多样性 但是 变异概率太小则很难产生新模式 变异概率太大则会使遗传算法成为随机搜索算法 1 7遗传算法研究的主要问题 1 局部最优 2 收敛速度问题 3 正确性问题 4 算法的实现性问题改进 编码方式 遗传算子 控制参数 1 8遗传算法的应用遗传算法提供了一种求解复杂系统优化问题的通用框架 它不依赖于问题的具体领域 对问题的种类有很强的鲁棒性 所以广泛应用于很多学科 下面是遗传算法的一些主要应用领域 1 函数优化函数优化是遗传算法的经典应用领域 也是对遗传算法进行性能评价的常用算例 对于一些非线性 多模型 多目标的函数优化问题 用其他优化方法较难求解 用遗传算法可以方便地得到较好的结果 2 组合优化随着问题规模的增大 组合优化问题的搜索空间也急剧扩大 有时在目前的计算机上用枚举法很难或甚至不可能求出其精确最优解 对这类复杂问题 人们己意识到应把主要精力放在寻求其满意解上 而遗传算法是寻求这种满意解的最佳工具之一 实践证明 遗传算法对于组合优化中的NP完全问题非常有效 例如 遗传算法已经在求解旅行商问题 背包问题 装箱问题 图形划分问题等方面得到成功的应用 3 生产调度问题生产调度问题在很多情况下所建立起来的数学模型难以精确求解 即使经过一些简化之后可以进行求解 也会因简化得太多而使得求解结果与实际相差甚远 而目前在现实生产中也主要是靠一些经验来进行调度 现在遗传算法已成为解决复杂调度问题的有效工具 在单件生产车间调度 流水线生产车间调度 生产规划 任务分配等方面遗传算法都得到了有效的应用 4 自动控制在自动控制领域中很多与优化相关的问题需要求解 遗传算法已在其中得到了初步的应用 并显示出了良好的效果 例如用遗传算法进行航空控制系统的优化 使用遗传算法设计空间交会控制器 基于遗传算法的模糊控制器的优化设计 基于遗传算法的参数辨识 基于遗传算法的模糊控制规则的学习 利用遗传算法进行人工神经网络的结构优化设计和权值学习等 都显示出了遗传算法在这些领域中应用的可能性 5 机器人学机器人是一类复杂的难以精确建模的人工系统 而遗传算法的起源就来自于对人工自适应系统的研究 所以机器人学理所当然地成为遗传算法的一个重要应用领域 例如 遗传算法已经在移动机器人路径规划 关节机器人运动轨迹规划 机器人逆运动学求解 细胞机器人的结构优化和行为协调等方面得到研究和应用 6 图像处理图像处理是计算机视觉中的一个重要研究领域 在图像处理过程中 如扫描 特征提取 图像分割等不可避免地会存在一些误差 这些误差会影响图像处理的效果 如何使这些误差最小是使计算机视觉达到实用化的重要要求 遗传算法在这些图像处理中的优化计算方面找到了用武之地 日前已在模式识别 图像恢复 图像边缘特征提取等方面得到了应用 7 人工生命人工生命是用计算机 机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统 自组织能力和自学习能力是人工生命的两大主要特征 人工生命与遗传算法有着密切的关系 基于遗传算法的进化模型是研究人工生命现象的重要基础理论 虽然人工生命的研究尚处于启蒙阶段 但遗传算法已在其进化模型 学习模型 行为模型 自组织模型等方面显示出了初步的应用能力 并且必将得到更为深入的应用和发展 人工生命与遗传算法相辅相成 遗传算法为人工生命的研究提供了一个有效的工具 人工生命的研究也必将促进遗传算法的进一步发展 8 遗传编程Koza发展了遗传编程的概念 他使用了以LISP语言所表示的编码方法 基于对一种树型结构所进行的遗传操作来自动生成计算机程序 虽然遗传编程的理论尚未成熟 应用也有一些限制 但它已成功地应用于人工智能 机器学习等领域 9 机器学习学习能力是高级自适应系统所应具备的能力之一 基于遗传算法的机器学习 特别是分类器系统 在很多领域中都得到了应用 例如 遗传算法被用于学习模糊控制规则 利用遗传算法来学习隶属度函数 从而更好地改进了模糊系统的性能 基于遗传算法的机器学习可用来调整人工神经网络的连接权 也可用于人工神经网络的网络结构优化设计 分类器系统也在学习式多机器人路径规划系统中得到了成功的应用 二 多目标优化问题描述 1 工程问题大多是多目标优化问题 2 一般没有绝对的最优解 只有可行解 3 可行解有多种组合可能 4 多个目标相互制约 5 求解需要充分了解约束之间的关系 三 实例1 Rosenbrock函数最值问题求Rosenbrock函数的全局最大值计算 maxf x1 x2 100 x12 x22 2 1 x1 2s t 2 048 xi 2 048 xi 1 2 如图所示 该函数有两个局部极大点 分别是 f 2 048 2048 3897 7342和f 2 048 2 0048 3905 9262其中后者为全局最大点 下面介绍求解该问题的遗传算法的构造过程 第一步 确定决策变量及其约束条件 s t 2 048 xi 2 048 xi 1 2 第二步 确定适应度函数 maxf x1 x2 100 x12 x22 2 1 x1 2第三步 确定编码方法 用长度为l0位的二进制编码串来分别表示二个决策变量x1 x2 lO位二进制编码串可以表示从0到1023之间的1024个不同的数 故将x1 x2的定义域离散化为1023个均等的区域 包括两个端点在内共有1024个不同的离散点 从离散点 2 048到离散点2 048 依次让它们分别对应于从0000000000 0 到1111111111 1023 之间的二进制编码 再将分别表示x1和x2的二个10位长的二进制编码串连接在一起 组成一个20位长的二进制编码串 它就构成了这个函数优化问题的染色体编码方法 例如X 00001101111101110001就表示一个个体的基因型 第四步 确定解码方法 解码时先将20位长的二进制编码串切断为二个10位长的二进制编码串 然后分别将它们转换为对应的十进制整数代码 分别记为y1和y2 依据前述个体编码方法相对定义域的离散化方法可知 将代码yi转换为变量xi的解码公式为 例如 对前述个体X 00001101111101110001它由这样的两个代码所组成 y1 55y2 881经上式的解码处理后 得到 x1 1 828x2 1 476 第五步 确定个体评价方法 由式f x1 x2 100 x12 x22 2 1 x1 2可知 Rosenbrock函数的值域总是非负的 并且优化目标是求函数的最大值 故这里可将个体的适应度直接取为对应的目标函数值 并且不再对它作其他变换处理 即有 F x f x1 x2 第六步 设计遗传算子 选择运算使用比例选择算子 交叉运算使用单点交叉算子 变异运算使用基本位变异算子 第七步 确定遗传算法的运行参数 对于本例 设定基本遗传算法的运行参数如下 群体大小 M 80终止代数 T 200交叉概率 pc 0 6变异概率 pm 0 001 下图为其进化过程示例及运行结果 图中两条曲线分别为各代群体中个体适应度的最大值和平均值 a 下图所示分别为初始群体 第5代群体 第10代群体和第100代群体中个体的分布情况 在图 a 中各个个体分布得比较均匀 在图 b 中大量的个体分布在最优点和次最优点附近 b 从图 c 中可以看出 次最优点也被淘汰 c 从图 d 中可以看出 个体更加集中在最优点附近 d 由该组图我们可以看出 随着进化过程的进行 群体中适应度较低的一些个体被逐渐淘汰掉 而适应度较高的一些个体会越来越多 并且它们都集中在所求问题的最优点附近 从而最终就可搜索到问题的最优解 四 实例2 智能组卷问题 问题描述 根据不同约束需求 实现计算机自动试卷 对题库中