基于遗传算法与并行计算的电磁场逆问题研究.pdf

浙江大学硕士学位论文 摘要 以电磁设备优化设计为主的电磁场逆问题 由于其突出的工程应用价值 自 诞生以来就一直是电磁场应用研究领域的热点问题 随着计算机技术的发展和电 磁场数值计算理论 方法的不断丰富与完善 以及工程技术发展的客观需求 电 磁场逆问题的应用前景必定更为可观 本文针对遗传算法及其在电磁场优化设计中的应用展开了深入研究 为改进 标准遗传算法算法早熟和局部寻优能力不足 提出自适应对偶种群遗传算法 引 入适应于当前种群最优解的对偶种群和新的子代产生规则 典型数学问题测试结 果表明改进后的遗传算法最优解质量高 收敛速度快 稳定性好 以超导磁储能系统优化设计问题为例 对其数学模型进行深入的研究 采用 基本有限元算法求解s m e s 系统优化设计的正问题 将改进遗传算法运用到 s m e s 系统优化设计问题 取得较好的优化结果 一般地 电磁场逆问题求解由于函数适应度计算通过数值方法实现 整个优 化过程计算时间冗长 为解决这一问题 在改进算法的基础上结合并行计算 分 别采用 级主从并行模式和二级主从并行模式处理改进算法 在l i n u x 平台下基 于c 和m p i 编程开发并行遗传算法 仿真结果表明 相较于串行遗传算法 并 行遗传算法具有更快的求解速度 优化时间的并行加速比几乎是线性的 充分说 明本文方法对电磁场逆问题实际应用的价值和理论研究的借鉴意义 关键词 遗传算法自适应对偶种群并行计算超导磁储能优化设计 浙江大学硕士学位论文 a b s t r a c t i n v e r s ep r o b l e m si ne l e c t r o m a g n e t i e sa sk n o wa so p t i m i z a t i o no fe l e c t r o m a g n e t i ce q u i p m e n t si sa l w a y st h eh o ti s s u e s i n c e i t sa d v a n c e di ne l e c t r o m a g n e t i c s a p p l i c a t i o nf i l e d s b yv i r t u eo fd e v e l o p m e n t si nc o m p u t e r s c i e n c ea n de l e c t r o m a g n e t i c sm e t h o d so fn u m e r i c a la n a l y s i s i n v e r s ep r o b l e m si ne l e c t r o m a g n e t i ch a sa w o n d e r f u lp r o s p e c t t h i sp a p e rd i s c u s s e st h ei n v e r s ep r o b l e m si ne l e c t r o m a g n e t i cp a r t i c u l a r l y t h e n t a k e st e a mw o r k s h o pp r o b l e m2 2a st y p i c a li s s u e w eu s et h ef i n i t ee l e m e n tm e t h o d t o c a l c u l a t et h ef u c t i o nf i t n e s so fp r o b l e m2 2 a sap o p u l a t i o n b a s e da l g o r i t h m g e n e t i c a l g o r i t h m o nt h eo n eh a n d h a si n t r i n s i cp a r a l l e lc h a r a c t e r i s t i c s w h i c hi sp e r f e c t m a t c h e df o rp a r a l l e lc o m p u t a t i o n o nt h eo t h e rh a n d i n f e a s i b l el o c a ls e a r c ha b i l i t y c a u s e db yp r e m a t u r em a k es o l u t i o n se a s i l yt r a p p e di nt h el o c a lo p t i m u m c o n s i d e r i n g a b o v ea d v a n t a g e sa n dd i s a d v a n t a g e s a l li m p r o v e dg e n e t i ca l g o r i t h mw i t ha d a p t i v e a d j o i n tp o p u l a t i o ni sp r o p o s e d t oc i r c u m v e n tp r e m a t u r ea n di m p r o v es e a r c ha b i l i t y t e s t i n gp r o p o s e da l g o r i t h m w i t ht y p i c a lm a t h e m a t i c a lp r o b l e m s i ta c h i e v e sb e t t e r s o l u t i o na n dl e s sr u n n i n g t i m es t e a d i l y t h e nu s et h ei m p r o v e da l g o r i t h mt oo p t i m i z e s m e ss y s t e ma n da c h i e v eab e t t e ro p t i m i z a t i o nr e s u l t g e n e r a l l y i n v e r s ep r o b l e m si ne l e c t r o m a g n e t i c sa r ek n o w n t oh a v ee x p e n s i v e e v a l u a t i o n sa n dt i m e c o n s u m i n gi t e r a t i o np r o c e s s i no r d e rt oh i g h p e r f o r m a n c e c a l c u l a t i o no fp r o b l e m2 2 w ei n t r o d u c ep a r a l l e lg e n e t i ca l g o r i t h m t h ep a r a l l e l i z a t i o n o ft h ep r o p o s e da l g o r i t h mi si m p l e m e n t e db yo n e l e v e lm a s t e r s l a v ep a r a l l e l i z a t i o n a n dt w o 1 e v e lo n e r e s p e c t i v e l y p r o g r a m m i n gb a s eo nca n dm p ii nl i n u xo p e r a t i o n s y s t e m s i m u l a t i o nr e s u l t si l l u s t r a t ep a r a l l e lg e n e t i ca l g o r i t h mg e tm o r ef a s t e ro p t i m i z a t i o ns p e e d w h i c he x p l a i n e st h em e t h o do ft h i sp a p e rh a sn o to n l yg r e a tt h e o r e t i c a l m e a n i n gb u ta l s oe n g i n e e r i n ga p p l i c a t i o nv a l u e k e yw o r d s g e n e t i ca l g o r i t h m a d a p t i v ea d j o i n tp o p u l a t i o n p a r a l l e lc o m p u t a t i o n t e a m w o r k s h o pp r o b l e m 2 2 d e s i g no p t i m i z a t i o n i i 浙江大学硕士学位论文 目录 摘要 l a b s t r a c t i i 目录 i l l 第一章绪论 1 1 1 课题的背景及意义 1 1 2 国内外研究现状 2 1 2 1 遗传算法的现状与发展趋势 2 1 2 2 并行计算的现状与发展趋势 3 1 3 本文的主要研究内容 5 第2 章遗传算法及其改进 8 2 1 遗传算法 8 2 1 1 遗传算法的原理 8 2 1 2 遗传算法的实现 1 0 2 2 遗传算法的改进 1 6 2 3 改进遗传算法的验证 2 0 2 4 小结 2 4 第3 章基于m p i 的并行遗传算法及其应用 2 5 3 1 并行计算理论和并行语言实现方式 2 5 3 1 1 并行计算机 2 5 3 1 2 并行编程模型 2 6 3 1 3m p i 并行语言 2 8 3 1 4m p i c h 平台的搭建 2 9 3 2 并行遗传算法 3 0 3 3 改进遗传算法的并行处理 3 4 3 3 1 一级主从p g a 及运行结果 3 4 3 3 2 二级主从p g a 及运行结果 3 8 3 3 3 相关并行计算技术 4 3 3 4d 结 4 6 第4 章并行遗传算法在电磁场逆问题中的应用 4 8 i i i 浙江大学硕士学位论文 4 1s m e s 系统优化设计问题 4 8 4 2s m e s 正问题的求解 5 1 4 2 1 解析解法 s 1 4 2 2 有限元法 5 2 4 3 运用改进遗传算法求解s m e s 优化设计问题 5 8 4 4 运用并行遗传算法求解s m e s 优化设计问题 6 1 4 5 小结 6 3 第5 章总结与展望 6 5 参考文献 6 7 文章发表录用情况 7 0 i v 浙江大学硕士学位论文 第一章绪论 1 1 课题的背景及意义 电磁场逆问题是指确定电磁场装置的理想性能参数或指标 要达到这一目标 需要通过装置的优化设计来完成 在优化设计过程中 必定涉及电磁场的数值计 算 因此称为电磁场逆问题 尽管 与电磁场逆问题相关的研究成果还不是非常 成熟 理论也未必足够坚实 然而由于其突出的工程应用价值 使得上世纪8 0 年代中期开始电磁场逆问题成为电磁场应用研究的热点 自1 9 8 7 年开始 历届 电磁场计算国际学术会议c o m p u m a g 都将电磁场逆问题列为今后电磁场数值 计算的一个重要分支 电磁场逆问题大多归结为有约束的多目标规划问题 无论对转化后多目标函 数的电磁场逆问题 还是对单目标函数的电磁场逆问题 其标量优化的目标函数 多为多极值点的非凸规划问题 对于电磁场逆问题的求解 初始研究阶段 直接 将优化变量引入方程中作为未知量来求解 然而 这种处理方式不足之处在于 具有解析解的工程电磁场问题凤毛麟角 甚至部分问题的优化变量与场量之间根 本不具有显示的关系 之后 取而代之的是将电磁场逆问题分解为一系列正问题 利用一定的优化方法进行迭代求解 因此 电磁场逆问题的研究主要围绕电磁场 的数值计算和优化方法两个主题 以及由此展开的若干相关问题 全局优化算法 的研究又是其核心问题 优化算法包含基于导数的传统数值优化算法和智能优化 算法两类 传统数值优化算法有梯度法 二阶梯度法 牛顿法 二次规划 序列 线性规划 内点法等方法 这些算法基于导数进行数值优化 难以适应电磁场优 化设计数学模型 而且很难找到其全局最优解 人们通过长期的探索 通过对自 然现象 社会活动 物理过程等的分析总结 提出了计算电磁场逆问题的智能算 1 浙江大学硕士学位论文 法 如模拟退火算法 遗传算法 禁忌算法 蚁群算法 神经网络算法等等 以 本身的计算规模而言 相较于电磁场正问题 电磁场逆问题的求解具有计算量大 占用计算机内存和c p u 时间多 计算冗长等问题 逆问题求解通常要迭代几百 次甚至上千次 每次迭代至少需要一次电磁场数值计算 对计算资源要求极高 与确定类的传统优化算法相比 这些随机类进化算法的缺点在于收敛速度慢 因 此 如何改进这类算法的搜索效率提高收敛速度 是电磁场逆问题标量优化算法 的工作重点所在 随着计算机技术与通信网络技术的不断进步 以及软件工具的逐步完善 以 并行计算为代表的高性能计算成为科学界与工程界的研究热点 在某些领域 计 算机性能甚至成为产业进步的关键所在 为实现快速准确求解电磁场逆问题 除 改进优化算法提高迭代过程中搜索效率之外 并行计算技术将是一种新的有效方 案 因此 本文选择具备固有并行性的遗传算法 对其作出改进 并结合并行计 算 提高求解电磁场逆问题的速度与质量 1 2 国内外研究现状 1 2 1 遗传算法的现状与发展趋势 遗传算法自1 9 7 5 年由h o l l a n d 提出 l 作为一种新的全局优化算法 具有应 用广泛 鲁棒性强 适于并行处理等优点 遗传算法擅长全局搜索 然而局部寻 优能力不足 并且容易早熟 为弥补其不足之处 各领域研究者从算法本身结构 和结合其他算法两个方向对遗传算法着手改进 部分工作取得令人满意的结果 从算法本身结构考虑 文酬2 1 提出一种自适应遗传算法 其交叉概率变异概 率适应于种群个体相识度和种群适应度相识度 使算法搜索更加高效灵活 文献 2 浙江大学硕士学位论文 1 3 作者从自然进化因变异和灾难引起的种群消失现象 提出自适应种群消失遗传 算法 a d a p t i v ep o p u l a t i o nd i s a p p e a r a n c eg e n e t i ca l g o r i t h m 避免算法早熟 摆脱初 始参数对算法收敛的影响 文献问提出二阶段遗传算法 通过控制参数的更改 在第一阶段全局随机搜索 第二阶段局部细化搜索 结合其他优化算法 文献 5 1 1 6 采用遗传算法与禁忌算法结合 求解最佳i p 网 络节点分布问题 多目标灵活车间作业进度表问题等组合优化问题 文献 7 8 1 结 合模拟退火算法 增加退火特性 在迭代过程中逐步缩小搜索域 加强局部寻优 能力 利用模拟退火算法的m e t r o p o l i s 接受准则控制算法早熟 文献 9 1 0 1 考虑蚁 群算法容易陷入局部极值点且由于初期信息素的缺乏导致整体收敛速度过慢 将 遗传算法的遗传操作加入到蚁群算法的每代种群迭代过程中 加强全局寻优能力 且通过变异操作使算法跳出局部极值点 在验证算法效果后 分别将其运用到配 电网规划问题和油田注水问题 遗传算法从提出到现在已经经历3 0 多年的研究发展 目前己广泛运用于组 合优化 自动控制 人工智能 生产调度 图像处理和模式识别 机器学习等问 题 为改善算法性能除了上面细述的改进方法外 国内外学者一直致力于对编码 类型 选择方法 交叉模型 控制参数 动态策略 自适应策略等的研究 然而 类似于遗传算法的随机类搜索算法 需要对大量候选解反复计算适应值 算法有 其局限性 算法并不能保证对任何问题都能到达最佳效果 正因如此 如何在这 些研究成果的基础上继续深入探索 不断改进创新 对于电磁场逆问题的研究非 常必要 1 2 2 并行计算的现状与发展趋势 市场需求是推动并行计算机发展的主要动力 大量实际应用部门 例如数值 3 浙江大学硕士学位论文 天气预报 石油勘探 地震数据处理 大型事务处理 生物信息等 都需要每秒 执行万亿次乃至数百万亿次浮点运算 并行计算是满足需求的唯一可行途径 自1 9 7 2 年诞生首台并行计算机i l l i a ci v 以来一系列s i m d 类型的阵列机 向量机先后诞生 吸引了大量专家学者从事并行计算机研制和并行程序设计 为 8 0 年代并行计算机的蓬勃发展奠定基础 到了8 0 年代 以m i m d 并行计算机的 研制为主 共享存储多处理机开始诞生并得到稳定的发展 以超立方体结构连接 的分布式存储m i m d 结构原型机开始出现 在分布式存储体系结构中 处理机 间的消息传递和消息长度 处理机间的距离有较大关系 因此互联网络最优拓扑 结构和数据包路由选择算法的研究引起广泛关注 在这一阶段 真正具备强大计 算能力的并行计算机开始出现 比如适合中粒度并行的m e i k o 系统 超立方体 连接的分布存储m i m d 并行计算机i n t e ri p s c 8 6 0 9 0 年代 网络通信技术的快 速发展为解决共享式存储的内存访问瓶颈问题提供了可能 分布式存储m p p 系 统并行计算机开始占据主流位置 同时为了让共享存储并行计算机具有可扩展 性 以适应高性能计算的需求 分布共享存储的思想开始被人们接受 2 0 0 0 年 至今 高性能计算得到了前所未有的大发展 按目前主要的应用领域分类 当前 的并行计算机大致可以分为以微机机群为代表的通用性并行计算系统和面向重 大应用而定制的m p p 系统 正是借助于计算机技术与通信网络技术的不断发展以及软件工具的成熟 使 并行处理技术迅速发展成为可能 并行计算已经成为高性能计算的必由之路 目 前 并行技术已经被广泛运用到智能算法中 以提高算法的求解速度与质量 文 献 1 1 在变量分类的基础上使用并行粒子群优化算法求解计及网络剩余容量经济 指标的电网规划新模型 文献 1 2 提出了模拟退火算法与遗传算法相结合的分布 式混合算法 并在局域网内的3 台p c 上并行仿真 验证了算法的有效性和速度 4 浙江大学硕士学位论文 并行计算亦不乏在电磁场数值计算方面的应用 文献 1 3 运用区域分解法对 二维静电场问题模型进行区域划分 运用并行共轭梯度法对有限元线性方程组进 行并行求解 取得了较高的效率加速比 提高有限元法的计算速度 与前者类似 文献 1 4 1 同样采用区域分解的方法对时域有限差分法实现并行计算 并行计算处理问题有如下特征 1 将工作分离成离散部分 有助于同时解决 2 随时并及时地执行多个程序指令 3 多计算资源下解决问题的耗时要少于单个 计算资源下的耗时 并行计算是管理多个处理器或多个进程同时执行指令和处理 数据 相比较串行计算而言 计算时间将大大的缩短 正因为并行计算多个进程 协同计算 对于研究者而言如何分配进程的计算任务管理不同进程使之协同工作 完成计算任务是并行计算的核心问题 目前 并行计算在电磁场数值计算领域已有较为广泛的应用 然而在电磁场 逆问题方面的研究运用较少 电磁场逆问题计算时间冗长 即使采用并行计算 求解部分大规模工程问题仍旧需要几天甚至几十天的时间 但是随着并行技术理 论的深入和计算机工业的发展 并行计算在电磁场逆问题的应用一定具有广阔的 前景 1 3 本文的主要研究内容 计算量大 计算时间冗长是电磁场逆问题一大特点 也是推广其中部分工程 问题投入实际生产的瓶颈所在 为解决这一问题 本文以电力系统中的超导电力 装置 s 砸s 系统的优化设计为例 选择具备固有并行性的遗传算法 先通过 改进遗传算法在保留其全局搜索优势的同时提高算法的局部搜索能力 并避免算 法的早熟 其次 引入并行技术处理改进后的遗传算法 提高超导磁储能系统优 化设计的求解时间与求解质量 浙江大学硕士学位论文 为达到上述研究目的 在电磁场数值计算 电磁场逆问题优化算法以及算法 并行处理方面做了相关工作 主要研究内容包括 一 对遗传算法进行改进 具体包括 1 深入研究遗传算法不足之处t 标准遗传算法局部寻优不足和早熟现象 分析造成算法不足的原因 2 针对其不足之处改进算法 提出自适应对偶种群遗传算法 算法引入 适应于父代最优个体的对偶种群和新的子代产生规则 适应于当前迭代次数的自 适应终止规则 3 在m a t l a b 平台下编程开发算法程序 用多个典型数学函数检验改进算 法的有效性 最终将改进算法运用到s m e s 系统优化设计问题中 二 实现改进遗传算法的并行处理 1 深入学习并行计算理论和m p i c h 语言 完成l u n i x 下m p i c h 软件平 台的搭建 2 分别设计一级主从并行和二级主从并行模式处理改进后的遗传算法 一级主从并行模式是纯粹的任务分配 从进程只负责函数适应度计算 进程间没 有个体信息交流 二级主从并行模式各进程组按改进后遗传算法的指令分别运行 一个子种群 进程组之间存在信息交换 3 采用m p i c 编写一级主从并行和二级主从并行遗传算法程序 将其运 用到s m e s 优化设计问题中 改进电磁场逆问题计算时间冗长问题 三 将上述方法用于s m e s 系统的优化计算 1 理解s m e s 系统在交流电网中的作用和工作原理 要达到的优化效果 和正常工作时的条件限制 2 总结其数学模型 优化的目标函数 约束条件 变量的可行域 6 浙江大学硕士学位论文 3 建立计算s m e s 磁场以及储能的有限元计算模型 使用m a t l a b 编写程 序计算目标函数中的实际储能和对装置1 0 米处的电磁环境影响指标 并用于 s m e s 的优化设计 浙江大学硕士学位论文 第2 章遗传算法及其改进 2 1 遗传算法 2 1 1 遗传算法的原理 遗传算法 g e n e t i ca l g o r i t h m g a 是一种通过模拟达尔文遗传选择和自然 淘汰的生物进化过程而提出的随机类搜索算法 是在计算机上模拟生物进化机制 而发展起来的一种计算方法 该算法进化过程虽然较长 但从进化结果而论 可 以说是一种高效率的优化过程 算法的提出者j o h nh o l l a n d 和他的学生的研究工 作主要集中在两个方面 1 抽象并严格解释自然系统的自适应机制 2 设计具有类似机制的人工系统 他们所设计的这套人工系统就是遗传算法 遗传算法是由n 个随机产生的 种群开始 通过繁殖 交叉和变异等遗传操作 种群一代一代向好的方面进化 直到满足一定的终止条件为止 其基本迭代过程为 1 初始化 随机产生初始种群p t 并计算初始种群的适应值和目标函数 2 由初始种群p t 通过繁殖 交叉和变异操作 产生新的种群p t 1 3 终止条件判定 如果满足条件 则算法终止 否则令p t p t 1 转步骤 2 继续搜索 经过几十年的发展 遗传算法理论不断地成熟 所以 无论是在建模还是实 际工程上 遗传算法的应用范围都在不断扩大 简单遗传算法的程序流程图如图2 1 所示 采用遗传算法优化问题时 首先 通过编码操作将问题空间映射到编码空间 而问题的每一个可能的解则被编码成 r 浙江大学硕士学位论文 一个染色体 即个体 若干个个体构成种群 遗传算法开始时 生成一组随机个 体构成初始种群 通过对各个染色体解码用预定目标函数完成对每个个体的评 价 即函数适应值 基于此适应值 选择个体来复制下一代 接下来 在编码空 间内通过选择 交叉 变异等遗传操作 通过解码还原至原问题空间 确定子代 种群 按照如上方式循环迭代直到满足程序终止条件 选择操作模拟自然界生物 个体与个体之间 个体与环境之间的生存竞争关系 优秀的个体得到更大的选择 概率 体现进化论 适者生存 的原理 而在竞争中处于劣势的个体因被选择的 概率小而被慢慢淘汰 在这种选择模式作用下 个体之间通过交叉变异操作实现 染色体基因重组 期待得到更优良的后代个体在竞争中保留下来 新的个体由于 继承父代的优良性状 故此在性能上优于父代 这样迭代过程中种群逐步朝着适 应度更高的方向进化 图2 1 遗传算法程序流程图 从上面的论述不难看出 遗传算法这种模拟生物进化机制的算法是不同于传 9 浙江大学硕士学位论文 统随机类搜索算法 其关键在于遗传操作 交叉算子 c r o s s o v e ro p e r a t o r 与变 异算子 m u t a t i o no p e r a t o r 的作用保证状态空间 选择算子 s e l e c t i o no p e r a t o r 的作用下保证迭代过程朝着适应度高的方向进行 与传统方法相比 它的优势 1 使用参数的编码集 而不是参数本身进行运作 2 遗传算法在种群中寻优 并非局限于单个个体 3 遗传算法使用问题本身的目标函数进行运作 无需任何先决条件 4 遗传算法使用随机转移机制而不是确定性规则 2 1 2 遗传算法的实现 从遗传算法的原理可以看到 标准遗传算法主要包含六个要素 编码方法的 选择 初始种群的设定 适应度函数的设计 遗传操作的设计和遗传参数的设定 指种群大小和遗传算子的概率 算法终止规则 这几个因素是决定遗传算法 的关键 1 编码设计 编码就是将问题的解用一种码来表示 从而将问题的状态空间与遗传算法的 编码空间相对应 这很大程度上依赖于问题的性质 并将影响遗传操作的设计 编码的选择是影响算法性能和效率的重要因素 遗传算法采用的编码方法很多 有二进制编码 浮点型编码 格雷码等种类 使用二进制向量作为染色体来表示决策变量的真实值 在目前运用较为广 泛 然而在求解复杂问题时 二进制编码方式不够简洁 考虑本文优化变量搜索 可行域为连续的三维实数空间 因此采用浮点型编码 浮点型编码使用线性插值 的方式生成可行解 并以实数向量 其长度与解向量相同 的方式返回结果 解 码时同样采用与之匹配的浮点型方式 1 0 浙江大学硕士学位论文 随着计算机技术的发展 树型编码 矩阵编码 量子比特编码等新的编码方 式正在不断兴起 1 5 17 1 关于各种编码方法的叙述和比较 文酬1 8 1 有较为详细的 介绍 二进制编码几乎能表达所有问题应用也最为广泛 实数编码适用于求解多 维连续函数优化问题 矩阵编码适合求解多目标优化问题和大规模复杂问题 树 型编码适合能用数和图表示的优化设计问题 各种编码各有利弊 其方案的选择 依赖于求解问题的性质和遗传算子的设计 2 适应度函数 遗传算法在搜索进化过程中一般不需要其他外部信息 仅适应度函数值来评 价个体的优劣 并作为后续遗传操作的依据 适应函数 f i t n e s sf u n c t i o n 也称 目标函数 o b j e c t i v ef u n c t i o n 用来对种群的染色体设定一定概率 保证该染色 体被选择的可能与函数适应值成正比 适应值大的染色体被选中的机会更大 一 般可直接应用优化问题的目标函数作为适应度函数 但有时需要另行构造 适应 度函数厶一 基本有以下三种 1 直接将待求的目标函数转化为适应度函数 若目标函数 功为最大值 问题 则 厶一 z 力 2 1 若目标函数f x 为最小值问题 则 厶觚 功 f x 2 2 或者 厶脚 x 瓦而1 2 3 式2 3 中 a 为常数 2 界限构造法 若目标函数厂 力为最大值问题 则 厶一 加 竺卜c 慨 2 4 式2 4 中 l 为 x 的最小值估计 若目标函数f x 为最小值问题 则 浙江大学硕士学位论文 知 加 o 2 卜 2 5 式2 5 中 c 雠为厂 x 的最大值估计 3 去倒数法 若目标函数厂 力为最大值问题 n k 工 丽1 c c 厂 x 2 6 若目标函数f x 为最小值f 3 题 则 k x 而1 c c 似 2 7 上两式中 c 为目标函数界限的保守估计值 作为一般应用原则 适应度函数的设计应尽量满足 1 单值 连续 非负 2 合理一致 适应度能反映对应解的优劣性 3 计算量小 适应度函数设计应尽可能简单易于计算实现 4 通用性强 对某类具体问题 应尽可能通用 本文选择的直接法 常数a 的数量级与f x 保持一致时 适应度函数的设 计效果较为满意 3 初始种群 如图2 1 所示在遗传算法处理流程中 以初始种群的产生为起点 一代代进 化直到按某种进化准则终止过程 由此得到最终的种群 在初始化种群时 需考 虑种群的规模和种群个体产生的规则 种群规模越大 群体的多样性就越丰富 算法陷入局部极值点的可能性就越小 然而 种群规模越大 重复计算的可能性 就越大 浪费计算资源降低算法效率的可能性就越大 因此在设计种群大小时必 须综合考虑种群多样性和算法效率两个方面 一般来说在确定种群大小n 的前 提下 应用伪随机数的生成方法随机产生n 个在可行域内的个体 作为初始种 群 这样可使初始种群尽量均匀分布在可行搜索域 在一定程序上避免算法陷入 1 2 浙江大学硕士学位论文 局部极值点 关于种群规模对遗传算法性能的影响 文献 1 9 有详细的论述 当种群规模 的增大时 进化代数降低 当种群规模的增大时 全局搜索能力增强 当种群规 模的增大时 收敛时间在初始阶段会下降 而当种群达到某个规模后 收敛时间 又会增加 同时上述变化都不是单调增加或者减少的 而是随着种群规模的增大 改变是波动或震荡的 对于不同的函数 各个性能的变化率都不相同 有不同的 上升或下降速率 也就是说种群规模对算法性能影响的大小跟函数的选取也有 关 4 遗传操作 一般遗传算法都有三个最基本的操作 即选择 交叉 变异 遗传操作是遗 传算法最核心的部分 决定算法朝着最优解迭代的关键 1 选择 s e l e c t i o n 选择运算又称繁殖或复制运算 用于模拟生物界汰劣存优的自然选择现象 他从种群中选择出适应性强的染色体 为染色体交换和变异运算产生新种群准 备 判断个体优劣的标准就是目标函数的适应度值 每次选择操作选择的个数应 与染色体个数相当 显然这一操作借鉴了达尔文适者生存的进化原理 即个体适 应度越高 其被选择的概率就越大 由于在选择用于繁殖下一代个体时 是根据 个体的函数适应度值来决定其繁殖量 因此这种选择也被称为非均匀再生 d i f f e r e n t i a lr e p r o d u c t i o n 目前 应用较广的选择策略主要有轮盘赌法和锦标赛法两种 2 0 1 轮盘赌法 选择策略是根据个体的适应度值算出每个个体在种群中出现的概率 并按此概率 随机选择个体构成子代种群 当前种群个体被选择的概率等价于个体适应度值在 种群总适应度值中所占的比例 如图2 2 所示 轮盘赌法选择策略的立足点是适 应度越好的个体被选择的可能越大 从轮盘赌法选择策略不难看出 在求解最大值问题时可以直接用适应度值进 行选择 在求解最小值问题时需要转换适应度函数 把问题转变为最大值问题 锦标赛法选择策略每次从种群中选取若干个体 选择其中最优的个体进入子 代种群 重复该操作 直到子代种群个体数量与父代种群一致 锦标赛法对最大 值最小值问题同样适用 无需转换 8 1 e 3 1 图2 2 轮盘赌法个体被选择概率图 文献2 0 通过n 组目标函数测试比较 发现对锦标赛法在求解精度和求解速 度上都要优于轮盘赌法 特别是在最小值问题中 并且参与锦标赛的组规模大小 为种群规模的6 0 8 0 之间时 效果教好 以之为参考 本文选用锦标赛法选 择策略 2 交叉 c r o s s o v e r 选择操作只能够从旧种群中找出优秀者 而不 作之外引入交叉操作 它模拟生物进化过程中的繁 叉组合产生新的优良品种 对于选中用于繁殖下一 体的相同位置 按照交叉概率在选中位置完成交叉 1 4 浙江大学硕士学位论文 合 该过程采用随机信息交叉 交叉时可使用单点交叉或多点交叉 交叉操作是 种群新个体的主要来源 因此在遗传操作中极为重要 因为本文编码方式采用的是浮点型编码 染色体是个实数向量 每个基因都 是一个实数 所以本文采用的交叉方式如下 两条染色体随机产生 交叉基因 即 第几个变量 随机产生 当然是否进行交叉由交叉概率控制 3 变异 m u t a t i o n 变异操作用来模拟生物在自然界中由于各种偶然因素引起的基因突变 即以 很小的概率随机的改变遗传基因 对应到遗传算法中就是以概率随机改变某个个 体的某一个变量值 若只有选择操作和交叉操作 而没有变异操作 则无法在初 始基因组之外的空间进行搜索 变异操作能确保算法中基因类型的多样性 增加 算法的全局优化属性 本文变异操作的实现方式如下 生成一个小于1 的伪随机数 与变异概率相 比 决定是否进行变异 变异染色体随机产生 染色体变异基因随机产生 确定 变异染色体和变异基因后 随机生成一个该基因搜索空间内与原值不同的数值替 换原来的数值 5 参数设定 交叉概率只用于控制交叉操作的频率 概率过大时 种群中个体基因的互换 太频繁 进而会是高适应度值的个体很快被破坏了 概率过小时 交叉操作太少 导致迭代过程停滞不前 变异概率己用来控制迭代过程中新个体的产生 从而保持种群多样性 概 率过小则不会产生新的基因结构 降低算法全局寻优能力 概率过大 则会使算 法趋向纯粹的随机类搜索 从而降低算法收敛速度 这些参数控制着算法的计算效率和优化性能 不同的参数组合对优化的结果 浙江大学硕士学位论文 有可能截然不同 因此 无论在理论研究还是在实际问题中 参数的设计都是极 为重要的一个因素 6 终止规则 遗传算法的理论研究已经表明算法具有可收敛性 因此对于算法我们关注的 是它的收敛速度 这与算法操作设计和参数选取有密切联系 然而 实际应用遗 传算法时不可能让它无限制的运行下去 而且通常最优解事先是未知的 所以 需要设定一定的规则来终止算法的进程 通常的终止规则是事先设定一个最大迭代次数 或者判断最优解是否连续若 干次没有明显变化 2 2 遗传算法的改进 正如前文的介绍 遗传算法具有应用广泛 鲁棒性好 适应于并行计算等优 点 但是 遗传算法擅长全局搜索 局部寻优能力不足 许多研究者的测试结果 说明 遗传算法可以很快搜索到近似全局最优解 但如果继续寻优直到真正的全 局最优解 则需要消耗巨大的计算资源 因此提高标准遗传算法的局部寻优能力 进而提高算法的搜索效率成为遗传算法研究的重要方向 分析标准遗传算法早熟与局部寻优能力不足的原因 交叉算子在算法中对新 个体的产生起主要作用 当经过多次迭代后 群体中个体多样性变差 而当前群 体又不包含全局最优个体时 出现收敛于局部最优解的现象 即算法早熟 由交 叉和变异操作产生子代的机制具有很大随机性 并不能保证算法局部空间搜索时 的有效性 极端情况会出现子代适应度比父代更差的情况 这将导致算法的收敛 速度减慢 目前 根据上面分析的原因 国内外众多研究者从算法本身结构和结合其他 1 6 浙江大学硕士学位论文 算法两个方向来研究改进 部分工作取得令人满意的结果 在前人方法的启发下 本文提出适应于当前种群最优个体的自适应对偶种群遗传算法 算法引入自适应 对偶种群及新的子代产生规则来保证种群多样性提高算法局部寻优能力 引入自 适应终止规则保证算法计算效率 l 自适应对偶种群 自适应对偶种群和子代产生规则 父代种群为瓴i f 1 2 其中 是 最佳个体 经过遗传操作 产生新种群以ii 1 2 以父代最佳个体五为 中心对称点 得到以i 江1 2 关于 的对偶种群娩if 1 2 n 如果 缘i 江1 2 中存在个体在可行搜索区域外则随机生成一个搜索区域内的新 个体 2 子代产生规则 选择当前两对偶种群的适应度前5 0 个体做为子代种群 这种规则的优势在 于 其一 利用父代的最佳个体为中心对称点 而不是直接用遗传操作后的子代 取代父代 保证搜索的有效性 避免计算资源的浪费 其二 用一个对偶种群来 保证种群多样性 避免算法因种群多样性缺失导致的算法早熟 3 自适应算法终止规则 自适应算法终止规则如下 i 允一k i 占 f 2 8 这里 i 为当前迭代次数 屯和无删分别是当前种群中的最优个体和最差个体 的函数适应值 占 f 口 丽b a 为第i 次迭代时的控制算法终止迭代的精度 函数 这是个跟迭代次数有关的单调递减函数 其中a b c d 均为设定常量 其值的选择需保证算法刚开始时 占 f 值较大 算法处于随机搜索阶段 随着i 浙江大学硕士学位论文 的增大 占 d 逐渐变小 算法进入局部细化搜索阶段 考虑遗传算法全局搜索能力强局部搜索能力不足的特点 在没有陷入局部极 值点的情况下能够较快搜索到全局最优解附近 构造的精度函数保证随机搜索阶 段简短 而局部搜索阶段漫长 所以这个函数的数值变化特性是随着迭代次数的 增加前期递减快 后期变化平坦 精度函数常数设置与目标函数的适应度有关 按照测试经验和其他研究者的 工作总结 4 7 一般在随机搜索阶段占 f 取值 0 0 1 0 1 在局部优化阶段f o 取值 o 0 0 0 0 0 1 0 0 0 1 以本文优化问题t e a mw o r k s h o pp r o b l e m 2 2 为例 由于目标 函数的适应度值较小 选取a l e 6 b 2 e 4 c l o d 9 精度函数值在算法开始时 设为2 e 4 算法终止时设为l e 6 是一个与迭代次数相关的递减函数 占 f 随i 变化的曲线如图2 3 所示 精 度 函 数 值 迭代次数 图2 3 终止规则函数变化曲线 根据标准遗传算法的步骤和改进策略 总结出自适应对偶种群遗传算法的基 本步骤如下 1 初始化参数 确定种群大小n 交叉概率 变异概率己 精度函数占 f 1 r 浙江大学硕士学位论文 的相关常数a b c d 2 初始化种群 x i t i i 1 2 n 对种群个体编码 浮点型编码 解码得到 相应个体数值 计算其目标函数适应值 找出种群最优个体以 f 3 对种群 f i 江1 2 n 个体编码 在编码空间内进行选择 交叉 变异 操作 解码还原至原问题状态空间 产生新种群 y i t i i 1 2 n 4 确定新种群关于毛 f 中心对称的对偶种群镰 f ii 1 2 n 如果 编 f ii 1 2 n 中有个体不在搜索区域内 则随机生成一个可行区域内的新个 体替代该个体 计算两对偶种群的目标函数适应度值 选择其中最优一半个体做 为子代种群 f 1 i i 1 2 n 并中找出子代最优个体x k t 1 5 更新参数 迭代次数i 精度函数e i 图2 4 改进的遗传算法程序流程图 1 9 浙江大学硕士学位论文 6 终止条件判断 如果满足 则算法终止 否则令新产生的子代做为下一次 迭代的父代返回步骤3 结合改进后的自适应对偶种群遗传算法的详细步骤 画出简明的程序流程图 如图2 4 所示 2 3 改进遗传算法的验证 为测试改进算法的性能 选取国际上评价优化算法典型数学函数问题进行仿 真实验 这是一个具有三个自变量的优化问题 目标为全局最小值 优化问题如 1 五 3 9 i 1 2 3 2 9 x 玉 x 2 x 3 与厂 x 分别是自变量与目标函数 这是一个比较复杂的目标函 数 在自变量的变化范围内总共有5 1 2 个极小值点 其最小值点x 2 0 2 0 2 0 最小值f x 3 为了验证方法的稳定性和寻优效果 设置种群大小为2 0 交叉概率0 7 变 异概率o 2 算法控制精度函数常数a b c d 分别为l e 6 l e 2 1 0 9 采用本文所提出的算法连续进行2 0 次仿真实验 结果均收敛于全局最优点 附近 其详细的仿真结果见表2 1 表2 1 典型数学函数一2 0 次仿真实验结果 1 j 蕾 丝5 l s 9 02一 墨 一加 l 汹 o3 x f 分析上表 全部2 0 次寻优结果都在全局极值点附近 除了第1 0 1 3 次精度 稍差 其他1 8 次的结果令人满意 算法平均收敛于全局最小点所需要的迭代次 数约为2 6 8 次 则其目标函数平均调用次数约为1 0 9 2 次 上述数据足够说明改 进后的自适应对偶种群遗传算法在保留标准遗传算法全局搜索优势的同时提高 了局部寻优能 浙江大学硕士学位论文 选择迭代次数接近平均水平2 6 8 次的结果做为分析对象 其迭代过程中的 种群适应度变化如图2 5 所示 搜索到的最佳自变量x 1 9 9 9 9 2 0 0 0 0 1 9 9 9 6 目标函数最小值f x 3 0 0 0 1 针对同样的问题 采用文献 2 1 1 中所记录的标准遗传算法 改进后的可控交 叉遗传算法和自适应模拟退火算法进行优化计算 这三种方法与本文方法的结果 比较见表2 2 0 表2 2 优化算法结果比较 由于该问题的最优解是 2 0 2 0 2 0 刚好位于搜索空间的中心处 为消除算 法对最优解位置依赖的嫌疑 选择另一个具有广泛代表性的检验函数 高斯基 本函到2 3 1 来测试改进后的算法 功 芝层2 鲁2 孑 一手 生二鱼兰 2 1 0 目前 高斯基本函数只有二维问题结果己知 所以随机生成参数屈 勺 q 创造一个m 为5 的二维最大值问题 f 玉兰2 兰兰2 刍 三 圣二三2 三鱼曼2 三 兰 1 2 三 m a x f x o 7 e o 1 8 0 7 5 e o 3 2 p 2 1 苎二i 兰 苎 窭 兰 望 1 2 e 0 3 2 e 0 7 2 2 1 1 该问题在搜索空间内有5 个局部极值解 分别是 1 1 1 3 3 1 3 4 5 2 鲁棒解是 3 1 全局最优解为 3 4 对应优化问题最优值为1 2 1 1 运用改进后的自适应对偶种群遗传算法优化式2 1 1 的问题 设置种群大小 为2 0 交叉概率o 7 变异概率0 2 算法控制精度函数常数a b c d 分别为 1 e 1 0 l e 3 1 0 9 分别用改进后的遗传算法和标准遗传算法连续测试2 0 次 其结果如表2 3 所示 其中 标准遗传算法的终止条件设置与改进后算法完全一 致 表2 3 典型数学函数二2 0 次仿真实验结果 最优解x最优值迭代次数 仿真实验编号 i 五 琵i i 再g ag ap g a 1 3 0 0 1 1 0 0 3 2 9 7 9 4 0 0 1 0 9 9 9 0 1 2 0 9 43 11 2 2 2 9 9 7 1 0 1 4 3 0 0 8 3 9 8 5 0 9 9 9 1 1 2 1 0 6 2 91 5 3 4 9 3 3 1 9 5 7 3 0 1 4 0 9 8 7 0 9 18 3 1 0 0 0 83 36 4 2 9 9 3 0 9 9 9 3 0 4 6 0 9 6 7 0 9 9 9 1 0 9 9 9 52 77 5 3 0 0 9 3 9 9 6 2 9 8 5 0 9 7 4 0 8 2 5 8 1 0 0 0 4 2 47 6 2 9 9 1 1 0 0 1 3 0 0 5 4 0 0 1 0 9 9 9 1 1 2 1 1 02 81 2 7 3 0 0 8 1 0 0 4 2 9 9 8