（计算机应用技术专业论文）动态优化问题的进化求解策略.pdf

摘要 摘要 现实社会中存在大量的动态优化问题 研究并解决这些问题具有重要的现实 意义 进化算法是一种智能计算方法 目前已被广泛的应用于求解动态优化问题 中 研究基于进化算法的动态优化问题求解策略意义重大 本文在已有研究成果的基础上 从三个方面对动态环境中的进化求解策略展 开了研究 具体工作如下 1 研究并设计了一种新的联想记忆更新策略 本文通过分析联想记忆机 制中环境信息与个体的对应关系 提出了一种基于环境信息的联想记忆更新策 略 并在不同的环境下使用三种动态测试用例检验了该策略的性能 实验结果表 明 该策略在循环环境中能显著的提高基于联想记忆机制的进化算法的性能 2 在联想记忆机制下提出了两种新的记忆抽取策略 分别是基于生存性 的联想记忆抽取策略和基于多样性的联想记忆抽取策略 这两种策略在选择环境 信息使用时分别用环境信息在新环境中的生存性以及环境信息的多样性作为依 据 在实验中 这两种策略与经典的抽取策略做了比较 结果表明 这两种策略 都是有效的动态问题求解策略 3 通过混合记忆机制 精英机制与随机移民机制提出了一种自适应的混 合迁移策略 在该策略中存在三种不同的迁移个体 而且每种迁移个体的数目在 进化过程中会依据其迁移个体对搜索的贡献而不断的自我调节 实验表明 这种 自适应混合迁移策略能有效的提升算法的环境适应能力 本论文通过对动态优化问题的研究 提出了基于环境信息的联想记忆更新策 略 基于生存性的联想记忆抽取策略 基于多样性的联想记忆抽取策略以及自适 应混合迁移策略 这些工作不仅对动态优化问题中进化求解策略的研究有着重要 的意义 而且对实际动态问题中进化求解策略的应用也有重要的指导作用 关键词 计算智能动态优化问题进化算法联想记忆 a b s t r a c t a b s t r a c t t h e r ea r em a n yd y n a m i c o p t i m i z a t i o np r o b l e m s d o p s i n r e a l w o r d a p p l i c a t i o n s i th a sr e a l i s t i cs i g n i f i c a n c et os t u d ya n ds o l v et h e s ed o p s r e c e n t l y e v o l u t i o n a r ya l g o r i t h m s e a s h a v eb e e nw i d e l yu s e dt os o l v ed o p s t h e r e f o r e s t u d y i n ga n dd e v i s i n ge f f i c i e n te v o l u t i o n a r ys t r a t e g i e sf o rd o p s a l ev e r yi m p o r t a n t b a s e do nt h ee x i s t e n te f f i c i e n te v o l u t i o n a r ys t r a t e g i e s t h em a i nw o r k si nt h i s t h e s i si n c l u d et h r e ea s p e c t sa sf o l l o w s 1 d e v i s i n gan o v e lu p d a t i n gs t r a t e g yf o rt h ea s s o c i a t i v em e m o r ys c h e m e a c c o r d i n gt ot h er e l a t i o n s h i po ft h ee n v i r o n m e n t a li n f o r m a t i o na n dt h ei n d i v i d u a l t h i st h e s i sp r o p o s e st h ee n v i r o n m e n t a li n f o r m a t i o nb a s e du p d a t i n gs t r a t e g y t h i s s t r a t e g yi st e s t e d i nd i f f e r e n te n v i r o n m e n t so nt h r e ed y n a m i ct e s tf u n c t i o n s t h e e x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h a tt h ep r o p o s e du p d a t i n gs t r a t e g yc a ni m p r o v et h e p e r f o r m a n c eo ft h ea s s o c i a t i v em e m o r y b a s e da l g o r i t h ms i g n i f i c a n t l y 2 p r o p o s i n gt w om e m o r yr e t r i e v i n gs t r a t e g i e s i e t h es u r v i v a b i l i t y b a s e d r e t r i e v i n gs t r a t e g ya n dt h ed i v e r s i t y b a s e dr e t r i e v i n gs t r a t e g y f o rt h ea s s o c i a t i v e m e m o r ys c h e m e i nt h e s et w os t r a t e g i e s t h ee n v i r o n m e n t a li n f o r m a t i o ni s r e t r i v e d a c c o r d i n gt ot h es u r v i v a b i l i t ya n dt h ed i v e r s i t y r e s p e c t i v e l y i ne x p e r i m e n t s t h e s e t w o s t r a t e g i e s a r e c o m p a r e d w i t has t a t e o f t h e a r t r e t r i e v i n gs t r a t e g y t h e e x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h a tt h e s et w os t r a t e g i e sa r eb o t he f f i c i e n tf o rd o p s 3 a na d a p t i v e h y b r i di m m i g r a n t ss c h e m ei sp r o p o s e db yc o m b i n i n gt h e m e m o r ys c h e m e t h ee l i t i s ms c h e m ea n dt h er a n d o mi m m i g r a n t ss c h e m et o g e t h e r a d a p t i v e l y i nt h i ss c h e m e t h r e ek i n d so fi m m i g r a n t sa r ec r e a t e d f u r t h e r m o r e t h e n u m b e ro ft h e s et h r e ek i n d si m m i g r a n t si sa d j u s t e da d a p t i v e l ya c c o r d i n gt ot h e i r c o n t r i b u t i o nt ot h es e a r c ha b i l i t y t h ee x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h a t t h i s s c h e m ec a ni m p r o v et h ee n v i r o n m e n t a la d a p t a b i l i t yf o re a s w i t ht h es t u d i e si nt h ed y n a m i co p t i m i z a t i o n t h ee n v i r o n m e n t a li n f o r m a t i o n b a s e d u p d a t i n gs t r a t e g y t h es u r v i v a b i l i t y b a s e dr e t r i e v i n gs t r a t e g y t h e d i v e r s i t y b a s e dr e t r i e v i n gs t r a t e g ya n dt h ea d a p t i v eh y b r i di m m i g r a n t ss c h e m ea r e p r o p o s e di n t h i sp a p e r t h e s ew o r k sa r ev e r yi m p o r t a n tf o rt h er e s e a r c ha n dt h e a p p l i c a t i o no f t h ee v o l u t i o n a r ys t r a t e g i e st os o l v ed o p s i i i a b s t r a c t k e yw o r d s c o m p u t a t i o n a li n t e l l i g e n c e d y n a m i co p t i m i z a t i o np r o b l e m e v o l u t i o n a r ya l g o r i t h m a s s o c i a t i v em e m o u 插图目录 插图目录 图1 1m p b i l 算法框架 1 6 1 6 图2 1 基于环境信息的更新策略 1 3 图3 1 适应值高的个体对应的环境信息不一定适合当前环境 2 3 图3 2 基于生存性的联想记忆抽取策略 2 4 图3 3 基于多样性的联想记忆抽取策略 2 6 图4 1 基于自适应混合迁移策略的遗传算法 3 8 图4 2 当f5 0 p 0 1 时 算法在环境最后2 0 次变化过程中的动态性能 4 4 图4 3当f5 0 萨1 0 时 算法在环境前1 0 次变化过程中的动态性能 4 4 i x 表格目录 表格目录 表2 1e i u m p b i l 与m p b i l 在循环环境中的t 检验结果 1 6 表2 2e i u m p b i l 与m p b i l 在循环环境中的离线性能 1 6 表2 3e i u m p b i l 与m p b i l 在带噪音的循环环境中的t 检验结果 1 7 表2 4e i u m p b i l 与m p b i l 在带噪音的循环环境中的离线性能 1 7 表2 5e i u m p b i l 与m p b i l 在随机环境中的t 检验结果 1 8 表2 6e i u m p b i l 与m p b i l 在随机环境中的离线性能 1 8 表2 7m p b i l 与e i u m p b i l 在检测到环境变化后样本集概率向量的多样性 2 0 表3 1 循环环境中算法的t 检验结果 2 9 表3 2 循环环境中算法的离线性能 2 9 表3 3 带噪音的循环环境中算法的t 检验结果 3 0 表3 4 带噪音的循环环境中算法的离线性能 3 0 表3 5 随机环境中算法的t 检验结果 3 1 表3 6 随机环境中算法的离线性能 3 1 表3 7 循环环境中次好样本对应的概率向量的平均使用次数 3 2 表4 1 循环环境中算法的离线性能 4 1 表4 2 带噪音的循环环境中算法的离线性能 4 2 表4 3 随机环境中算法的离线性能 4 3 表4 4k 分别为1 2 3 时a h i g a 的离线性能 4 5 表4 5h i g a a h i g a 及a h i g a i i 的离线性能 4 6 表4 6a h i g a m e r i g a 和m e a 砌g a 在循环环境中的离线性能 4 7 表4 7a h i g a m e r i g a 和m e a r i g a 在带噪音的循环环境中的离线性能 4 8 表4 8a h i g a m e r i g a 和m e 水i g a 在随机环境中的离线性能 4 9 表4 9a h l g a 小依i g a a m e i g a 和a e r i g a 在循环环境中的离线性能 5 0 表4 1 0a h i g a a m r i g a a m e i g a 和a e r i g a 在带噪音的循环环境中的离线性能 l 表4 1 1a h i g a a m r i g a a m e i g a 和a e r i g a 在随机环境中的离线性能 5 2 x i 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文 是本人在导师指导下进行研究工作所取得的成 果 除已特别加以标注和致谢的地方外 论文中不包含任何他人已经发表或撰写 过的研究成果 与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明 作者签名 筮园 签字日期 丝丝 当2 2 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一 学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权 即 学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版 允许论文被查阅和借阅 可以将学位论文编入有关数据 库进行检索 可以采用影印 缩印或扫描等复制手段保存 汇编学位论文 本人 提交的电子文档的内容和纸质论文的内容相一致 保密的学位论文在解密后也遵守此规定 血丞开口保密 年 作者签名 弛 签字日期 塑 竺 兰 至 导师签名 里塞 望 签字日期 第1 章绪论 第1 章绪论 在现实社会中 很多问题都可以抽象成最优化问题 近年来 各种优化求 解方法受到了广泛的关注与研究 这些方法可以很好的解决一部分在求解过程 中最优解不变的问题 即静态优化问题 然而在现实中 很多问题的最优解是 随时间的变化而不断变化的 此类问题被称作动态优化问题 d y n a m i c o p t i m i z a t i o np r o b l e m s d o p s 进化算法 e v o l u t i o n a r ya l g o r i t h m s e a s 起源于达尔文的进化学说 具 有很强的鲁棒性与自适应性 对求解动态优化问题具有先天优势 现如今 进 化算法已被越来越多的用于求解动态优化问题 并取得了很大的进展 本章首先对动态优化问题的研究背景及意义进行了简单的介绍 然后 概 述了应用进化算法求解动态优化问题的研究现状 接着介绍了几种常用的动态 测试函数及算法性能评价方法 最后 介绍了本文的主要研究内容及组织结构 1 1动态优化问题的研究背景与意义 随着科学的发展 在很多研究领域中都出现了动态优化问题 例如 工作 时间调度 1 2 机器人行走路径规划 3 及移动a dh o c 网络最短路径 4 5 等 在这些问题中 目标函数的最优解有可能会随着时间的变化而不断地发生变化 动态优化问题可以分为多种不同的类型 1 根据环境变化方式的不同 动态优化问题所处的环境可以分为循环 变化的环境 带噪音的循环变化的环境以及随机变化的环境等 在循环变化的环境中 环境会在一组既定的环境中循环地发生变化 问题 最优解的变化遵循一定的规律 在带噪音的循环变化的环境中 环境仍然会在一组既定的环境中循环地发 生变化 与循环变化的环境所不同的是 环境在每次变化时都会受到噪音的扰 动 使得变化后的环境与给定的环境有所偏差 在随机变化的环境中 环境可以变化成任意一种新的环境 问题最优解的 变化没有规律可循 在该环境中 如果环境变化强度不大 新环境中问题的最 优解很有可能会非常接近旧环境中的最优解 然而 如果环境变化强度很大 该优化问题就可能会变成一个全新的问题 2 根据目标函数在时间与搜索空间上变化方式的不同 动态优化问题 又可以分为时间连续的 时间离散的 搜索空间连续的以及搜索空间离散的四 第1 章绪论 类 6 时间连续的变化是指目标函数所处的环境每时每刻都可能会发生变化 而 时间离散的变化是指环境在两次变化之间会有一定的时间间隔 在连续的搜索 空间上 最优解在空间中位置的变化是连续的 例如在实值空间中的变化 相 反 动态优化问题的最优解在离散空间中的位置变化是离散的 对于上述动态问题的优化 不能只是仅仅满足于找到最优解 而是应该设 计一些方法来追踪最优解的变化 以满足实时的需求 否则就有可能会造成损 失 贻误战机 进化算法是一类模拟生物进化机制的人工智能方法 具备先天的自适应性 是解决动态优化问题很好的选择 1 9 6 6 年 f o g e l 等人 7 最早将进化算法应用 在了动态环境中 然而 传统的进化算法在运行过程中 种群会逐步收敛 其 收敛性使得它难以应对变化的环境 失去了对新环境的适应能力 为了改善这种情况 越来越多的人开始研究并设计新的策略来提升进化算 法的动态适应能力 现如今 基于进化算法的动态优化问题求解策略已经成为 了动态优化问题研究领域中的最大热门之 6 8 1 3 研究并设计有效的求解策 略来帮助提升进化算法在动态环境中的适应能力具有重大的现实意义 1 2 基于进化算法求解动态优化问题的研究现状 近年来 越来越多的进化算法被应用到动态优化问题的求解中 为了使进 化算法能够更好的解决动态变化的问题 学者们研究并设计了多种进化求解策 略来提升传统进化算法的动态适应能力 本节对进化算法及其进化求解策略进 行了简单的概述 其中重点介绍了记忆机制与混合求解策略在求解动态优化问 题中的研究现状 最后介绍了一种典型的基于联想记忆机制的进化算法 1 2 1 进化算法及其在动态优化问题中的应用概述 进化算法是由生物进化理论演化出的一种搜索优化算法 进化算法的工作 步骤可以分为以下几步 1 4 s t e p1 初始化 进化代数f 0 随机产生一个种群p t 评价e t 中每个 个体的适应值 s t e p2 重复以下步骤 直到满足算法结束条件 s t e p2 1 进化操作 将进化算子 交叉 变异等 作用于种群p t 中的 个体 产生新的种群p f s t e p2 2 评估适应值 评价p f 中每个个体的适应值 2 第1 章绪论 s t e p2 3 选择 利用选择算子从p f 或p t 与尸 f 中选择合适的 个体组成下一代种群p t 1 s t e p2 4 进化代数t t 1 s t e p3 算法结束 进化算法具有很好的自适应性与鲁棒性 目前已被广泛的应用于解决动态 优化问题中 遗传算法 g e n e t i ca l g o r i t h m g a 1 4 与p b i l 算法 p o p u l a t i o n b a s e di n c r e m e n t a ll e a r n i n ga l g o r i t h m 1 5 是用于解决动态优化问 题的进化算法中比较有代表性的两个算法 遗传算法是由美国m i c h i g a n 大学的 b h nh o l l a n d 教授创建的 是一种模拟 生物优胜劣汰规则的智能进化算法 1 4 遗传算法主要包括基因编码 选择 交叉 变异及适应值评估等几个步骤 当使用遗传算法优化一个问题时 首先 将该问题的参数进行基因编码 由一组基因个体组成一个初始种群 然后 按 照优胜劣汰的原理 根据个体的适应值从种群中挑选合适的个体进行交叉 变 异操作 产生下一代种群 这样逐代演化直到找到问题的满意解 遗传算法具 有自适应性及很强的鲁棒性 非常适于求解动态优化问题 p b i l 算法是由美国卡内基梅隆大学的b a l u j a 提出的 1 5 在p b i l 算法中 种群是由一个不断进化学习的 概率向量 产生的 称为样本集 概率向量尸的 每一位p 代表该位生成编码 1 的概率 其中f 1 z z 是编码长度 在进 化的每一代f 概率向量p f 都会经历学习与变异两个过程 分别如公式 1 1 和公式 1 2 所示 1 6 只0 1 1 一口 枣只 f 口木s f f p 幸 1 一瓦 p i i f p l p 牛 1 一氏 瓦 p 以 0 5 胁 f 0 5 1 2 p f 厂 b c t h e n 尸 r p u f 进化过程 5 e l s e 根据公式 1 1 学习概率向量p t 对概率向量p f 进行变异操作 用变异后的p f 生成新的样本集s o 并评估 该样本集中的所有样本 p t 1 p 0 s t 1 s 0 t t 1 6 u n t i l 终止条件得到满足 图1 1 m p b i l 算法框架 1 6 本节将详细介绍一种典型的基于联想记忆机制的进化算法 m p b i l 算 法 该算法是由y a n g 与y a o 1 6 提出的 具有很好的求解动态优化问题的性能 6 第1 章绪论 m p b i l 的算法框架如图1 1 所示 在m p b i l 中 记忆集被用来存储好的样本及其对应的环境信息 其中 环 境信息由种群的概率向量表示 为便于描述 本文将m p b i l 算法记忆集中所存 储的一个样本及其对应的环境信息称为一个 记忆点 因此 一个记忆点包括 一个样本及其对应的环境信息 在m p b i l 中 记忆集每隔一段随机的代数就要进行更新 当记忆集更新时 如果记忆集还未满 则把当前样本集中的最好样本及当前的概率向量作为一个 记忆点直接存储到记忆集中 如果记忆集已经满了 首先在记忆集中找出与当 前最好样本海明距离最近的记忆样本所对应的记忆点 然后对该记忆点做替换 操作 如果当前样本集中的最好样本比该记忆点的样本的适应值高 则用当前 的最好样本及其当前的概率向量分别替换该记忆点的样本与概率向量 否则 保持该记忆点不变 不更新记忆集 该更新策略使用的正是b r a n k e 3 5 总结的 四种更新策略中的第三种 为了描述方便 本文将这种记忆集更新策略称为 基 于个体的更新策略 在m p b i l 算法运行的每一代 记忆集中的样本都会被重新评估 以此来检 测环境的变化 当环境被检测到发生变化时 记忆集中所存储的最好的环境信 息就被抽取出来重新使用以增强算法在新环境中的搜索能力 其中 记忆集的 抽取过程为 选择记忆集中最好的样本与当前样本集中最好的样本作比较 如 果记忆集中的最好样本比当前最好样本的适应值高 就用该记忆样本所对应的 概率向量替换当前样本集的概率向量在新的环境中进行进化搜索 否则不变 1 3 常用的动态测试函数及算法性能评价方法 为了模拟现实中的动态优化问题 检验动态优化算法的性能 近年来学者 们设计了很多动态测试函数 5 8 其中 最常用的主要有两个 b r a n k e 3 5 设计 的m p b 问题 m o v i n gp e a k sb e n c h m a r kp r o b l e m 以及y a n g 与y a o 1 8 5 4 设计 的动态问题生成器 d o pg e n e r a t o r m p b 测试函数 3 5 是一组连续多维空间中随时间动态变化的多峰函数 当 环境发生变化时 峰的高度 宽度及其位置都可以发生变化 在m p b 函数中 环境变化的速度与强度 峰的数目与形状 空间的维度等参数都是可以调节的 因此 问题的难度是可以调整的 由于m p b 测试函数的解空间是连续的 因此 它常被用来测试解空间连续变化的动态优化问题的算法的性能 与m p b 测试函数相反 动态问题生成器 1 8 5 4 1 主要用于生成解空间离散 的动态测试函数 它可以将任何二进制编码的静态问题转化为动态问题 动态 7 第1 章绪论 问题生成器使用模板来将静态函数转化为动态函数 在计算个体在当前环境中 的适应值时 先将个体与模板的对应位做异或操作 然后对异或的结果进行评 估 使用该动态问题生成器 可以很容易的模拟各种变化形式不同的环境 如 随机变化的环境 循环变化的环境以及带噪音的循环变化的环境等 为了在同 n 试函数下比较动态优化算法的性能 还需要一套可行的性能 评价方法 在动态变化的环境中 问题的最优解是不断变化的 因此一般不能 以算法是否找到最优解为评价依据 目前常用的评价方法主要有在线 1 1 4 土4 白日匕r 及离 线性能等 1 1 在线性能 1 1 是指截止到当前代数为止 种群在每一代中所有个体适应值的 平均 它可以实时的反应动态优化算法的性能 该定义如公式 1 3 所示 1g f c t e f 1 3 i 7 t l 其中 c r 是当前代数 e f 代表第t 代时种群所有个体适应值的平均值 相比较在线性能而言 离线性能评价指标的使用更加普遍 在算法运行结 束后 它将每一代种群中的最好个体的适应值求平均 以此代表算法的性能 其定义如公式 1 4 所示 1 1 一 1r f 言 以 f 1 4 上t l 在该公式中 丁是算法运行的总代数 五o 代表第f 代种群中最好个体的适应 值 1 4 本论文主要研究内容及安排 本文围绕着动态优化问题的进化求解方法 在以下三个具体方面做了深入 的分析研究 1 联想记忆机制下的记忆集更新策略研究 本文在已有的记忆集更新 策略基础上 根据联想记忆机制的特点 提出了一种新的联想记忆更新策略 在该策略下 环境信息与当前环境最相似的记忆点被选择出来进行替换操作 记忆点的记忆个体与环境信息是分开进行替换操作的 记忆个体根据其适应值 的大小进行替换 而环境信息则是依据对替换后的记忆个体的匹配度进行替换 实验证明 该策略有利于提高进化算法对动态优化问题的求解性能 特别是在 循环变化的环境中 2 联想记忆机制下的记忆抽取策略研究 针对联想记忆机制 本文提 出了两种新的联想记忆抽取策略 在以往常用的抽取策略中 选择环境信息时 8 第1 章绪论 通常只依据其对应个体的适应值大小 而在本文提出的这两种策略中 分别使 用环境信息在新环境中的生存性与环境信息的多样性来选择合适的环境信息使 用 实验表明 这两种求解策略在动态环境中都是有效的 能显著提升基于联 想记忆机制的进化算法的性能 3 混合策略在动态优化问题中的应用研究 本文通过混合记忆机制 精英机制与随机移民机制提出了一种自适应的混合迁移策略 该策略能自适应 的生成三种迁移个体以应对不同的环境 实验表明 自适应混合迁移策略有利 于提升进化算法的环境适应能力 本文其余章节的安排如下 第二章提出了一种新的联想记忆更新策略 在 不同的动态测试函数下以及不同的环境中进行了实验 并与经典的更新策略做 了对比分析 第三章提出了两种新的联想记忆抽取策略 并通过实验验证了这 两种策略求解动态问题的有效性 第四章提出了一种自适应混合迁移策略 并 通过大量的实验检验和讨论了该策略的性能 第五章对本文工作进行了总结与 展望 9 第2 章一种新的联想记忆更新策略 第2 章一种新的联想记忆更新策略 在显式记忆机制中 记忆集的空间大小通常是有限的 一个好的记忆集更新 策略可以充分利用有限的记忆空间来存储更多有用的信息 然而 现有的记忆更 新策略通常只是针对直接记忆机制的 本章通过分析联想记忆机制的特点 在 m p b i l 算法框架下提出了一种新的联想记忆更新策略 基于环境信息的更新 策略 e n v i r o n m e n t a li n f o r m a t i o nb a s e du p d a t i n gs t r a t e g y 并与经典的记忆更新 策略通过实验做了对比分析 实验结果表明 相对于经典更新策略 该策略在循 环变化的环境中更有助于提升进化算法求解动态优化问题的性能 本章首先分析了已有的记忆集更新策略在联想记忆机制中的应用 紧接着提 出并描述了基于环境信息的更新策略 并通过实验对该策略的性能做了对比分 析 最后对该策略进行了讨论并给出了本章小结 2 1 问题的提出 在显式记忆机制中 记忆集的空间大小通常是有限的 为了充分的利用有限 的记忆空间 一种常见的做法是选取与当前种群的最好个体最相似的记忆个体进 行替换 在二进制编码问题中 个体间的相似性常用个体间的海明距离来度量 在直接记忆机制下 记忆集中只存储个体 因此 上述做法比较适于直接记忆机 制的记忆集更新 然而在联想记忆机制中 记忆集不只是存储个体 个体所对应的环境信息也 一并被存储下来了 因此 当更新记忆集的时候 如果只是单单用个体的适应值 大小来决定是否对一个记忆点进行替换可能会导致某些有用的环境信息无法保 存下来 个体对应的环境信息也应该被考虑进来 正如1 2 2 节所总结的 目前主流的记忆集更新策略大都只是针对直接记忆 机制的 联想记忆机制还没有自己独特的更新策略 采用的依然是直接记忆机制 的更新策略 m p b i l 算法 1 6 的基于个体的更新策略就是沿用以往的直接记忆机 制的更新策略 在m p b i l 算法的基于个体的更新策略中 概率向量的存储和替 换与否完全决定于它所对应的样本的适应值的大小 这不利于记忆集存储更有用 的环境信息 第2 章一种新的联想记忆更新策略 2 2 基于环境信息的联想记忆更新策略 2 2 1 策略设计 在m p b i l 算法 1 6 1 在进化的任意一代f 新的样本集都是由概率向量 p t p t t r 生成的 其中 是编码的长度 样本集中任何一个样本 s j s 的生成过程可由公式 2 1 描述 f 1 驴i o i f r a n d o o 1 0 t h e n b m b c i fm a t c h d e g r e e b c 乓 m a t c h d e g r e e b c t h e n 尼 e l s e i fm a t c h d e g r e e b m 足 m a t c h d e g r e e b m t h e n 足 图2 1 基于环境信息的更新策略 7 从该步开始是记忆点的替换过程 首先比较所选取的记忆样本b w 与 当前样本集中最好样本e 适应值的大小 若置 的适应值高 则执行步骤 8 否则执行步骤 1 1 8 将当前样本集中的最好样本耳存储到记忆集中 替换b 9 计算反与足的匹配度以及反与匕的匹配度 若眈与足的匹配度 高 则执行步骤 1 0 否则算法结束 1 0 将当前工作中的概率向量只存储到记忆集中 替换匕 1 1 记忆样本b 的适应值高于当前样本集中最好样本毋的适应值 1 2 计算 与足的匹配度以及 与圪的匹配度 若 与尼的匹配度 高 则执行步骤 1 3 否则算法结束 1 3 将当前工作中的概率向量耳存储到记忆集中 替换匕 2 2 2 策略特点 对比传统的基于个体的更新策略 基于环境信息的更新策略在记忆点的选取 与替换两个方面拥有明显的特点 首先是记忆点的选取 在基于个体的更新策略 1 6 中 记忆点选取的依据是 1 3 l z 王 t 孓 z 吼 m n 坦 b 第2 章一种新的联想记忆更新策略 记忆样本与当前样本集中最好样本的海明距离 海明距离最近的记忆样本所对应 的记忆点将被选取出来 在基于环境信息的更新策略中 记忆点的选取是依据样 本与概率向量的匹配度大小进行的 如图2 1 的步骤 6 所示 当选取记忆点 时 首先计算记忆集中所有的概率向量与当前样本集最好个体的匹配度 匹配度 最大的概率向量所对应的记忆点将被选取出来进行替换操作 其次是记忆点的替换 在基于个体的更新策略 1 6 中 如果所选取的记忆样 本的适应值低于当前样本集中的最好样本的适应值 那么整个记忆点就都会被替 换掉 记忆点替换的依据是记忆样本的适应值大小 在基于环境信息的更新策略 中 记忆点中的样本与概率向量是分开进行替换操作的 而且各自替换的依据也 不同 首先进行样本的替换 比较该记忆样本与当前样本集中最好样本的适应值 大小 如果该样本的适应值低 那么就用当前样本集中的最好样本替换该样本 取代它在记忆集中的位置 样本的替换是依据样本适应值的大小 接下来进行概 率向量的替换 对于样本已经更新完毕的记忆点 分别计算记忆点的概率向量与 记忆样本的匹配度以及当前工作中的概率向量与记忆样本的匹配度 若当前工作 中的概率向量与记忆样本的匹配度高 则用当前的概率向量替换被选出的记忆点 的概率向量 概率向量替换的依据是概率向量与样本的匹配度大小 2 3实验 本节将基于环境信息的更新策略引入到了m p b i l 算法 1 6 中 替换其康先 的基于个体的更新策略 为描述方便 记这种新的m p b i l 算法为e i u m p b i l 通 过实验分析了基于环境信息的更新策略在e i u m p b i l 算法中的性能 并与基于个 体的更新策略在m p b i l 中的性能做了对比 2 3 1 动态测试函数 在本实验中 动态测试用例是借助y a n g 与y a o 1 8 5 4 1 设计的动态问题生成 器以三个二进制编码长度为1 0 0 的静态函数为原型生成的 分别记为d d u f l d d u f 2 及d d u f 3 1 6 作为原型的三个静态函数分别是o n e m a x 函数 p l a t e a u 函数以及d e c e p t i v e 函数 这三个函数都是由2 5 组长为4 的模式块构成的 每个 模式块对适应值的贡献最大为4 o n e m a x 函数的作用实际上是统计比特串中编码为 1 的位的个数 o n e m a x 函数没有局部最优解 是一种简单的测试函数 p l a t e a u 函数是一个稍微复杂点的函数 如果其模式块中编码为 l 的位的 个数少于2 该模式块对适应值的贡献为o 否则的话 模式块中编码为 1 的 1 4 第2 章一种新的联想记忆更新策略 位的个数每增加一个 该模式块对适应值的贡献就增加1 进化算法在p l a t e a u 函数中的搜索难度要远远大于在o n e m a x 函数中的搜索难度 d e c e p t i v e 函数则更加复杂 当模式块中编码为 1 的位的个数少于3 时 编码为 l 的位的个数每增加一个 模式块对适应值的贡献就减少1 当模式 块中编码为 1 的位的个数为4 时 模式块对适应值的贡献为4 当模式块中 编码为 1 的位的个数为o 时 模式块对适应值的贡献为3 每个模式块都存 在一个局部最优解 即当编码为 i 的位的个数为0 时的解 而且该局部最优 解与全局最优解的位置相距很远 在这三个函数中 进化算法在d e c e p t i v e 函数 中的求解难度是最大的 对每一个d d u f y a n g 和y a o 提出的动态问题生成器 1 8 5 4 都构造了三种 环境 循环变化的环境 带噪音的循环变化的环境以及随机变化的环境 环境每 隔f 代就会变化一次 为了检验环境变化速度对算法性能的影响 参照目前通常 采用的实验设置 1 6 本实验设置了两种环境变化速度 分别是1 0 与2 5 环境 变化的强度参数用p 来表示 对每一个d d u f 都有四种不同的变化强度 0 1 0 2 0 5 及1 0 在循环变化的环境及带噪音的循环变化的环境中 针对上述设 置的参数p 环境的状态数目分别为2 4 1 0 及2 0 在带噪音的循环变化的环 境中 对环境加入噪音的概率设置为o 0 5 总的来说 每一个静态函数 对应不同的参数设置有8 种不同的环境 并由 此一共生成了2 4 组动态问题 本实验将用这些动态测试函数来检验基于环境信 息的更新策略在e i u m p b i l 算法中的性能 2 3 2 实验参数设置 为了公平起见 e i u m p b i l 与m p b i l 1 6 具有以下共同的参数设置 种群大 小丹 1 0 0 其中包含m 1 0 的记忆集空间 概率向量的学习速率口 o 2 5 变异 迁移量皖 o 0 5 变异概率p 0 0 2 在每一次实验中 每一个算法都要使用相同的一组随机种子单独运行5 0 次 每次进化5 0 0 0 代 针对不同的环境变化速度f 1 0 与r 2 5 每次运行时 环境 的变化次数分别是5 0 0 与2 0 0 为了比较算法的优劣 本实验采用离线性能来评 估算法的性能 离线性能在本实验中的具体计算方法如公式 2 4 所示 1 6 一 1r1 尺 f e o r 2 4 t la r l 其中 丁表示一次运行时总的进化代数 在本实验中为5 0 0 0 r 代表总的运行次 数 本实验中为5 0 名 是第 次运行中的第f 代中种群中最好个体的适应值 1 5 第2 章一种新的联想记忆更新策略 2 3 3 实验结果与分析 表2 1e i u m p b i l 与m p b i l 在循环环境中的t 检验结果 f t e s tr e s u l td d u f ld d u f 2 d d u f 3 f 1 0 p j 0 1o 20 51 00 10 2o 51 00 10 20 51 o e i m m p b i l a 西p b r ls s 七 s s s 5 s f 2 5 p j 0 1o 20 51 oo 1o 20 51 00 10 2 0 5 1 o e i 址 l p b i l 一 涯p b i ls s 七s 七七s 七s j rs s j rs s 一一 表2 2e i u m p b i l 与m p b i l 在循环环境中的离线性能 d d u f s f p 中b i le i u b i l d d u f l1 0o 1 9 0 9 2 5 o 2 5 51 9 1 1 8 3 0 3 1 9 8 0 2 9 0 6 8 0 1 2 8 9 3 9 1 9 0 2 1 2 6 8 0 o 5 9 8 2 6 4 o 0 9 6 0 9 8 3 1 3 o 0 9 0 0 1 o 9 8 9 8 6 0 0 3 5 1 9 9 0 5 5 0 0 1 7 3 2 5o 1 9 1 2 0 4 0 1 5 7 2 9 1 7 2 0 o 2 2 4 6 o 2 9 1 1 7 3 0 5 2 8 0 9 1 5 3 9 o 4 2 6 9 o 5 9 6 3 3 0 1 6 9 2 8 9 7 7 8 4 5 4 7 9 4 1 o 9 9 5 6 8 o 0 0 6 5 9 9 5 7 8 o 0 0 4 3 d d u f 21 0o 1 7 8 6 5 7 2 2 0 7 0 7 8 9 5 7 1 7 9 5 6 o 2 7 7 7 0 4 7 5 0 1 6 7 9 7 2 6 6 1 9 7 4 o 5 8 6 8 8 4 11 3 7 0 9 0 1 9 2 5 6 5 3 5 1 o 8 3 5 9 1 8 8 6 2 3 9 0 5 8 5 4 2 7 6 2 2 50 1 7 9 5 6 6 1 2 4 4 7 8 0 9 0 6 1 4 7 4 7 0 2 7 9 4 5 3 1 5 3 9 3 8 0 2 1 2 1 2 7 2 5 0 5 8 8 5 4 3 3 7 19 4 9 1 8 3 3 1 3 0 3 6 1 09 3 2 38 2 0 2 0 7 9 5 9 8 1 7 4 7 2 7 d d u f 31 00 1 7 8 7 7 7 1 0 8 1 7 7 9 7 2 9 1 4 3 4 4 0 28 4 3 81 1 6 7 3 6 8 4 6 4 6 o 6 5 7 8 0 5 8 6 5 4 6 o 0 8 0 3 8 6 5 6 6 o 0 6 4 0 1 o 8 7 313 o 0 0 4 5 8 7 3 1 4 o 0 0 4 2 2 50 1 7 9 0 9 6 0 8 4 0 8 8 0 0 6 8 0 9 5 x 9 0 2 8 4 1 1 9 2 9 4 8 6 8 4 8 8 1 o 3 9 8 2 o 5 8 6 7 2 5 o 0 9 3 1 8 6 7 21 o 0 8 9 0 1 o 8 7 3 2 5 o 0 0 3 5 8 7 3 2 4 0 0 0 3 9 m p b i l 算法与e i u m p b i l 算法的实验结果在表2 1 到表2 6 中给出 其中 表2 1 表2 2 给出的是循环变化环境下算法的实验结果 表2 3 表2 4 给出的 是带噪音的循环变化的环境下的实验结果 随机变化环境下的实验结果在表2 5 及表2 6 中给出 1 6 第2 章一种新的联想记忆更新策略 表2 3e i u m p b i l 与m p b i l 在带噪音的循环环境中的t 检验结果 州砖s tr e s u i td d u f ld d u f 2 d d u f 3 r 1 0 p j 0 10 20 5 1 00 10 2 0 51 0o 10 20 51 0 e i h m p b i l a 伫b l ls s s 一j 一一 一 s 一 5 一j f 2 5 d j o 10 20 51 0 0 1 0 20 51 00 1o 20 51 0 e i u m p b i l m p b i l s 一 一 s 一 一 s s 表2 4e i u m p b i l 与m p b i l 在带噪音的循环环境中的离线性能 d d u f s r p m p b i le i u 口b i l d d u f l 1 00 1 6 6 9 3 4 o 0 9 0 3 6 6 7 2 9 o 0 7 9 7 0 2 6 5 5 8 5 o 0 9 5 5 6 5 4 5 6 o 11 5 1 0 5 6 6 9 0 0 0 1 2 1 5 6 6 7 6 4 0 1 0 9 1 1 o 7 1 9 0 4 o 3 7 5 2 71 6 9 8 0 4 6 0 6 2 50 1 7 8 9 8 7 0 1 9 7 1 7 8 9 9 2 0 1 9 8 5 0 2 7 1 3 7 7