（电路与系统专业论文）动态优化方法及其在软硬件动态划分中的应用研究.pdf

摘要 摘要 在实际生产和科学研究中存在着大量复杂的优化问题，其中一些优化问题的 目标函数或者约束条件会在问题求解过程中随时间而变化，这类优化问题被称为 动念优化问题。近年来，演化计算在解决动态优化问题方面取得了显著的进展。 本文研究基于演化计算的动态优化算法，对记忆策略进行实验分析，并将动态优 化进化算法应用于软硬件协同设计领域的动态划分问题进行求解，取得了一些有 意义的结果。 论文的主要工作和创新之处如下： ( 1 ) 提出了一种双吸引子多群体粒子群算法( b m p s o ) 。b m p s o 算法采用两 个群体吸引子对解空间进行搜索，能够有效的平衡算法的收敛速度和群体的多样 性。此外，将记忆策略引入多群体粒子群算法( m p s o ) ，改善了m p s o 算法对周期 性变化的动态优化问题的适应性，有效的提高了算法在具有历史相关性的动态环 境中的搜索效率。 ( 2 ) 通过大量对比实验，对记忆策略的特点及其适用范围进行了较为深入 的分析，从中总结出：1 、有效的信息保存是记忆策略取得较好效果的保证。2 、 记忆策略的效果与历史环境的动态相关性有很大关系。 ( 3 ) 对软硬件协同设计中的动态划分问题进行了初步研究，提出了一个基 于m p b i l 算法的动态划分方法。该方法能够有效改善算法在任务结构变化初期搜 索效率低的问题，提高了划分的效率和结果的稳定性。 关键词t 动态优化粒子群优化算法记忆策略动态软硬件划分 a b s t r a c t a b s t r a c t i nt h er e a l w o r l da p p l i c a t i o n sa n dt h er e s e a r c hf i e l d s ，t h e r ee x i s tm a n yc o m p l e x o p t i m i z a t i o np r o b l e m s s o m ep r o b l e m so p t i m u mo rc o n s t r a i nf u n c t i o nm a yc h a n g e o v e rt i m ed u r i n gt h e p r o b l e ms o l v i n gp r o c e s s a n d t h e y a r en a m e dd 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 nr e c e n ty e a r s ，e v o l u t i o n a r yc o m p u t a t i o no b t a i n s s i g n i f i c a n tp r o g r e s s i nt h ef i e l d so fd y n a m i co p t i m i z a t i o n ，a n dm a n ye x c e l l e n t a l g o r i t h m sh a v eb e e np r o p o s e d t h er e s e a r c ho fd y n a m i ca l g o r i t h m si n t h i sp a p e ri s b a s e do nt h ee v o l u a t i o n a r ya l g o r i t h m s ；f o c u sm a i n l yo nt h ee x p e r i m e n t a la n a l y s i so f m e m o r ys c h e m e ；s u c c e s s f u l l y u s e st h ed y n a m i co p t i m i z a t i o na l g o r i t h mo nt h e h w - sw p a r t i t i o n i n gp r o b l e ma n dg e t ss o m em e a n i n g f u lr e s u l t s t h em a i nw o r ka n dc o n t r i b u t i o n so ft h i sp a p e rc a nb es u m m a r i z e da sb e l o w ： 1 an e wa l g o r i t h mn a m e d “b i a t t r a c t o rm u l t i - p o p u l a t i o np a r t i c l es w a r ma l g o r i t h m ( b m p s o ) ”h a sb e e np r o p o s e d b m p s ou s e st w os w a l t na t t r a c t o r s t op e r f o r m s e a r c h i n g ；t h i sm e t h o dc a nb a l a n c et h ep o p u l a t i o nd i v e r s i t ya n dt h ec o n v e r g e n c e s p e e de f f e c t i v e l y i no t h e r w i s e ，t h i sp a p e ri m p o r t st h em e m o r ys c h e m et o t h e m u l t i p o p u l a t i o np s oa l g o r i t h m ( m p s o ) s u c c e s s f u l l y t h i sm e t h o dp e r f o r m sm o r e a d a p t i v e l yi nt h ep e r i o d i cd y n a m i ce n v i r o n m e n ta n dc a ne n h a n c e t h es e a r c h i n ga b i l i t y g r e a t l yi nt h ep r o b l e mo fw h i c hh a sm u c hh i s t o r i c a lc o n c u r r e n c y 2 t h i sp a p e rc o n d u c t sm a n ye x p e r i m e n t a la n a l y s e so nt h em e m o r ys c h e m ea n d s u m m a r i z e st h et w op r o p e r t yo fm e m o r ys c h e m e ：1 t h ee f f e c t i v e n e s so ft h e i n f o r m a t i o nc o n v e r s a t i o ni st h eb a s eo ft h em e m o r ys c h e m e 2 t h ep e r f o r m a n c eo f t h em e m o r ys c h e m eh a sm u c hr e l a t i o no nt h ec o r r e l a t i o no ft h eh i s t o r i c a l e n v i r o n m e n t 3 t h i sp a p e rr e s e a r c h e sb a s i c a l l yo nt h es w - h wc o - p a r t i t i o n i n gp r o b l e ma n du s e s t h em p b i la l g o r i t h mo nt h ed y n a m i cs w - h w c o p a r t i t i o n i n gp r o b l e m t h i sm e t h o d c a ns o l v et h el o we f f i c i e n c yp r o b l e mo ft r a d i t i o n a ld y n a m i ca l g o r i t h m sa tt h e b e g i n n i n go ft h ed y n a m i ce n v i r o n m e n ta n de n h a n c et h ep e r f o r m a n c ea n ds t a b l y k e y w o r d s ：d y n a m i co p t i m i z a t i o n ，p a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m ，m e m o r y s c h e m e ，s w - h wc o p a r t i t i o n i n g i l 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。 作者签名： 涵暑 签字同期：圣! ! ! 笙塑! 三旦 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人 提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 ， 曰公开口保密(年) 作者签名：皿 导师签名：本娥 签字日期：塑! 翌生塑! 三望签字日期：塞馊2 ，：! 童 第一章绪论 第一章绪论 在现代科学技术的各个应用领域都存在着大量的优化问题。其中存在着这样 一类问题，它们抽象出来的目标函数或者约束条件会在问题求解过程中随时间发 生变化，导致问题的最优解也随之变化。这一类优化问题被称为动态优化问题。 例如：变化背景的动态目标识别问题、动态更新型数据库的数据挖掘问题、动态 规划问题、动态智能交通问题等等 1 。针对动态优化问题最简单的解决方法就 是直接采用静态优化算法，即在每一次问题变化之后重新初始化一个静态优化算 法对问题进行重新求解。但是，如果问题变化过快，一次求解所需的时间大于动 态问题两次变化的间隔时间，那么优化算法就没有足够的时间收敛到最优解，从 而使得这种方法的效果很差，甚至远远的偏离全局最优解。 动态优化问题的动态特性大大的增加了问题求解的难度。为了解决这类问 题，需要设计一类能够自动检测动态问题结构( 也称为动态环境) 变化并动态调 整搜索方向的自适应算法。这类算法需要具备能够有效判断环境的变化，并在发 现环境变化后迅速调整搜索区域并快速收敛的能力。这一类算法也被称作动态优 化算法。由于解决动态优化问题在生产实践中具有非常重要的意义，且问题本身 也具有很大的难度，因此对于动态优化方法的研究就变得越来越重要。 近年来，演化计算在解决动态优化问题方面取得了令人振奋的进展。演化计 算方法与自然界的进化选择有很多相似的特点，它对于环境的变化有很强的自适 应性，能针对不同的环境以群体进化的方式去解决优化问题。因此利用演化计算 方法解决动态问题具有很多优势。自从1 9 6 6 年研究人员首次将进化计算方法用 于解决动态优化问题以来 2 】，此领域研究工作已经得到了更为广阔和深入的发 展，对此领域的深入研究具有更为重要的意义。 1 1 动态优化问题的定义及其特点 不同于传统的静态优化问题，动态优化问题的目标函数或者约束函数会随着 优化过程的进行而变化，如式( 1 1 ) ( 1 2 ) 所示： f = z ( 墨，五，t ) ( 1 1 ) c ，( ，五，f ) = t ( t ) ( 1 2 ) 其中石，x 2 , ，砂是目标函数，c ，x 2 ，0 是约束函数，他们都是时间t 的函数， 蜀，恐凰是优化问题决策变量，它构成了一个维空间，被称为解空间。动态 第一章绪论 问题的变化在模型上对应于解空间的结构发生变化，通常也被称为动态环境发生 变化。根据函数解析式的变化方式，动态优化问题又可以分为线性、周期、随机 等三个动态模型 1 ： ( 1 ) 线形模型中的全局最优解的位置呈线性变化，其在每一维上的偏移量按下 式计算 毹= 文一+ s ，k = 1 ，2 ，3 l ，群= 0 ( 1 3 ) ( 2 ) 周期模型中全局最优解的位置按固定的或非固定周期丁作循环移动，其在 每一维上的偏移量按下式计算 毹= 文一+ s 。，- c c o s 名，k = 2 l ，武= o ( 1 4 ) l 反= 掣+ s 2 札i n 2 个r r _ _ _ i i ，k = 1 ，3 l ( 1 5 ) ( 3 ) 随机模型的全局最优解的位置是变化的且不可预测，其在每一维上的偏移 量按下式计算 瞑= 文+ s x r a n d o m ( 0 ，1 ) ，k = 1 ，2 ，3 l ，罐= 0 ( 1 6 ) 上述三种模型具有不同的优化难度。通常采用“时间相关性”来衡量一个动态优 化问题的求解难度，它是一个用来度量适应度函数两次变化之间相关度的量。对 于时间相关性强的问题，变化前后的解空间结构具有很大相似性，这样变化前优 化算法保存的环境信息可以被利用来指导变化后的优化函数的求解。而变化相关 性弱的问题，它的解空间结构是类似于随机变化的，变化前后的优化函数相似性 低，它只能依靠具有更高收敛速度优化方法去进行求解，其优化难度最大。 针对具有上述特性的优化问题，动态优化的目的就是：在检测到环境变化后 及时有效的追踪最优解的变化，并根据变化改变算法的搜索方向，在下一个环境 变化到来之前尽可能快速的实现收敛，找到全局最优解。 1 2 动态优化算法的分类 根据算法求解的动态问题的适应度函数类型不同，可将动态优化算法分为： 连续空间优化算法和离散空间优化算法两大类，它们具有不同的特点。连续空间 动态优化算法解决的是决策变量在实数空间连续取值的优化问题。而离散动态优 化算法主要解决的是决策变量在离散空间取值的优化问题，如动态组合优化问 题。著名的连续动态优化算法有：动态差分演化算法( d y n d e ) 3 、多群体动态 粒子群算法( m p s o ) 4 、多群体量子动态粒子群算法( m q s o ) 5 等。离散动态 优化算法有：热力学遗传算法( t d g a ) 6 、随机移民动态遗传算法 ( r i m m g a ) 7 、基于记忆策略的遗传算法( m g a ) 8 9 等。 第一章绪论 根据所基于的进化算法模型的不同，可将动态优化算法分为：动态粒子群类 优化方法，动态e d a 类优化方法，动态遗传算法类优化方法等。 根据动态优化算法使用的动态策略思想不同，又可以将动态优化方法分成以 下四类： 1 在环境变化后提高算法群体多样性 这种策略的思想是当算法检测到环境变化时，算法就会使用专门的方法增加 群体的多样性。通过这种方式使得算法的搜索方向更为容易地向新的最优解转 移。其中较为典型的方法就是h y p e r m u t a t i o n 方法 1 0 ，这种方法利用在环境变 化后增加个体的变异概率来实现增加群体多样性的目的。但是这种策略存在一个 问题，增加多样性过程会破坏环境变化前精英个体保存下来的信息，而使算法表 现类似于随机搜索 1 1 。 2 在整个算法运行过程中维持群体多样性 这种策略的思想是在整个算法运行过程中避免部分个体的收敛，这样就会形 成一个较为“松散”的群体，从而有利于适应环境的变化。一个典型的例子是随 机移民方法 1 2 ，此方法通过在群体的新一代个体中加入一些随机个体来维持群 体的多样性。基于共享和c r o w d i n g 机制小生境技术也是著名的保证多样性的方 法 1 3 。 3 使用环境记忆策略 这种策略的思想是在演化算法中引入记忆机制，用来存储上一次变化前环境 的有用信息，并用这些信息来帮助引导算法在新环境中的搜索。这种记忆策略对 于环境变化具有周期性特点的问题非常有效。记忆策略可以进步分为显式记忆 策略和隐式记忆策略两类。在显式记忆策略中，通常采用一个额外的存储空间来 保存历史搜索信息。一个典型的例子是r a m s e y 和g r e f e n s t e t t e 提出的“条件”初 始化g a 算法 1 4 。他们使用c a s e b a s e dr e a s o n i n g 来区分不同的环境变化。在一 次环境变化后，将记忆存储空间中一些在类似环境表现优异的个体重新放入群体 中。隐式策略通常使用的是冗余表达( r e d u n d a n tr e p r e s e n t a t i o n ) 的方法：通过引入 冗余的染色体序列( 双倍或多倍) 来保存遗传信息。并使用一个称为显性控制序 歹l j ( d o m i n a n c ec o n t r 0 1 ) l 拘机制根据环境的变化来控制染色体的表达，从而实现对 变化环境的动态适应。其中最为著名的例子就是多倍染色体( p o l y p l o i d y ) 方法和 m u l t i d i p o l y 方法 1 5 1 6 。 4 多群体策略 多群体策略是通过将一个群体分割成多个子群体，并允许各个子群体独立搜 索跟踪解空间内的多个局部最优解的方法。每一个子群体对空间中一个潜在最优 解区域进行搜索并跟踪其位置变化，这也可以看作是一种维持种群多样性的有效 第一章绪论 方法。为了获得一个较高的搜索效率，同时需要对各个子群体之间加入某些排斥 机制，以防止各个子群体之间的搜索区域因重叠而造成的搜索资源的浪费。典型 的例子有：m u l t i s w a r mp s o ，m u l t i s p e c i e sp s o ，自组织监视 1 7 ，m u l t i n a t i o n a l g a 1 8 、s h i f t i n gb a l a n c eg a 1 9 和d y n d e 3 等。 不同的动态优化方法对于不同的问题各有优缺点，他们的使用领域和侧重解 决的问题的特点也是不同的。例如：p s o 动态优化算法主要用于连续空间的优化 问题，而e d a 类算法对于离散空间的优化问题较为适用。应当根据动态问题的特 点加以应用。 1 3 常用的动态测试函数及算法评价方法介绍 在对动态优化算法进行分析和评价时，以前的研究工作者通过对动态问题的 抽象，设计了一些专门用来测试动态问题的测试函数，其中较为著名的有：t h e m o v i n gp e a k sb e n c h m a r kp r o b l e m ( m p b ) 测试问题 2 0 、动态0 1 背包问题 9 以及由x y a o 等提出的动态测试环境生成器( d o pg e n e r a t o r ) 2 1 2 2 2 3 。 m p b 测试函数由j b r a n k e 等人设计，该测试函数描述了一个含有时间变化 参数的连续空间的动态多峰目标函数。m p b 测试函数包含一系列变化的峰，其中 峰的位置、高度、宽度、形状等都是可以变化的。其表达式如下所示： 凡蹦户m a k - 朋【而斋丽j 7 ， 其中形( ，) 和只( f ) 分别代表第j 个峰的宽度和高度，( ，) 是在时间r 时刻解空 间中第个点的位置与第i 个峰的中心位置的距离。每一个峰都能够独立的改变 自己的高度和宽度，并在搜索空间内移动。其形状如下图所示： 4 图1 1m p b 问题的静态空间结构 第一章绪论 这个测试问题可以通过条件多个参数来改变问题的难度，如峰的数目、问题的维 数、环境变化的频率、环境变化的强度等等。 动态b i t m a t c h i n g 问题是一类应用非常广泛的离散动态测试函数。由于其数 学结构简单且用非常少的控制参数就能够生成具有不同特点的测试问题，因此得 到了广泛的应用。b i t m a t c h i n g 问题是通过用一个静态的离散函数与一个称为“动 念屏蔽项( m a s k ) ”的算子进行异或操作而得到的。静态离散函数如下公式描述： 水) ，( 卸) 7 ) ( 1 8 ) 其中x 是一个长度为，的离散比特串。其与“动态屏蔽项”进行异或操作就得到 了动态离散函数： ，- + 、，。 _ 、 f l l = 厂ix m ( k ) i ，k = t r 7 ( 1 9 ) 一， 其中m ( k ) 是与时间有关的动态屏蔽项，r 是动态环境变化的周期，k 是当前环 境在变化序列中的编号k = l ，2 ，3 这里，为了能够控制动态坏境变化的强度， m ( k ) 被定义成如下式所示： m ( k ) = m ( k - 1 ) r ( k ) ( 1 1 0 ) 7 1 f 后) 被称为动态生成模板，每次函数变化都是由它产生。它在每一次环境变化 时在长度为的比特串上随机的产生p z 个“1 ”，其余比特为“0 ”，这样就随机 地生成了一组二进制比特序列。这里p ( 0 0 ，1 o ) 就是变化控制参数，决定了环 境变化的剧烈程度。从上述定义可以看出，在初始情况下，第一个周期令k = l ， 将m ( 1 ) = 0 设为全。比特，然后在每一次环境变化时，新环境的模板m ( k 1 通过 将旧环境模板m ( k - 1 ) 与一个随机模板r ( 七) 进行异或操作产生。随机模板r ( k ) 每次由控制参数p 随机生成。最后再将屏蔽项肘( 七) 与静态函数f ( x ) 进行异或操 作就得到了动态b i t m a t c h i n g 测试函数。 根据静态函数f ( x ) 描述方式的不同，b i t - m a t c h i n g 问题又可以细分为 o n e m a x 问题、n k 系列问题和“骗”问题( d e c e p t i v e ) 。下图为4 比特长度模式 块( b u i l d i n gb l o c k ) 的静态适应度函数描述图。 “1 ”的个数 图1 2b i t m a t c h i n g 问题的静态适应度函数结构 第一章绪论 动态k n a p s a c k 问题是一类实际应用非常广泛的动态测试问题，也被称为时 变k n a p s a c k 问题( t i m e v a r y i n gk n a p s a c kp r o b l e mt v k p ) 。它通过下面一组式子描 述： 山m 训a x 川z = c 小) x 以) ( 1 1 1 ) 薯( f ) e o l 鲁”7 ”7 一 其约束条件为：a ，( f ) 誓( f ) 6 ( f ) ，f = 1 ，2 其中是背包的数量，a ，和c ，分别是背包的权重和价值，b 是随时间变化的约束 值，一( ，) 的值取。或1 。在实验中口，和c ，在一定的范围内随机取一个值，并在 整个实验中保持不变，实验中通过不断减小b ( t 1 ，使问题产生变化，并且问题难 度越来越大。常用的变化6 ( r ) 有三种方式，其中b 。= a i ： 1 每一步减少b s u m 的1 0 ，将b ( t 1 从9 0 减小到5 0 。 2 每一步减少b s u m 的1 0 ，将b ( t 1 从5 0 减4 , n1 0 。 3 每一步减少b s u m 的2 0 ，将6 ( ，) 从9 0 减小到5 0 。 为了评价不同的动态优化算法的性能，人们提出了一些评价方法，它们从不 同方面度量算法的优化。i i 。工- t - 白厅匕p 。常用的评价方法有在线。龇( o n l i n ep e r f o r m a n c e ) 、 离线。陛能( o f f i l n ep e r f o r m a n c e ) 7 f 1 离线误差( o f f i i n ee r r o r ) 2 4 ，其中离线误差的使 用最为普遍。在线性能可以定义为： x ( 丁) = 专0 ( 1 1 2 ) 其中e ，代表第，次评估的适应度值，丁代表总的评估次数。由于每一次的评估都 对于最终的结果产生影响，因此它反映了在整个优化过程中算法对于动态环境变 化的实时反应能力。而离线性能定义为： x 。( 丁，) - 嘉其中z = m a x ( e r e r e r e l ，) ( 1 1 3 ) 与在线误差不同，这里的e ，e r + 1 ，e r + 2 e t 是在一个静态间隔内的评估序列。举 个例子，考虑一个动态环境在每隔一定的时间就变化一次，每一次环境变化的时 闻 日j 隔可以不固定，但是在整个算法的优化过程中，一共经历了丁次环境变化。 算法在每个固定的时间就对当前解进行一次评估，在一个静态环境间隔中( 两次 环境变化的间隔) ，算法一共评估了卜f 次并得到一系列评估值 e ，e + l ，e ，+ 2 e t ，那么离线性能就可以表示为在每一个静态环境间隔上算法找 到的最优解乞的适应度的平均值。离线性能值越高说明算法的优化能力越强。 用算法一次找到的最优解作为算法性能评价是不够的，这是因为算法的优化 第一章绪论 是在一个动态的过程中进行的，而且目标问题的最优解也会动态的变化。因而通 常采用离线误差来对动态优化算法性能进行度量。为了引入离线误差的定义，首 先介绍当前误差，它是指在一个环境间隔中的算法找到的最优解o p t 俐与当前 静态环境间隔全局最优解的差值： 毛= o p t ( t ) 一白 ( 1 1 4 ) 其中b 为当前误差，q 为当前静态环境间隔的全局最优解。离线误差是指：在 每一个静态间隔中算法找到的当前误差的平均，如下式描述： 17 s + ( 丁) = 专乞 ( 1 1 5 ) if = l 其中动态环境一共变化了r 个间隔，为当前误差。与离线性能相反，离线误 差越小说明算法的优化性能越好，其理论最优值为0 。 1 4 基于演化算法的动态优化方法的研究现状及其存在的主要问题 将演化类算法应用于动态优化问题最早可以追溯到1 9 6 6 年 2 ，后来直到上 世纪8 0 年代，对基于演化算法的动态优化方法的研究才渐渐得以展开，并逐渐 成为研究热点。目前较为流行的基于演化算法的动态优化算法研究主要可以分为 基于遗传算法的动态优化算法、基于粒子群优化算法的动态优化算法和基于e d a 算法的动态优化算法3 大类。下面将分别介绍这三类算法的发展与研究现状。 1 4 1 基于遗传算法的动态优化方法研究 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 是最早被用来解决动态优化问题的一类演 化算法，它是模拟生物进化过程中优胜劣汰规则与群体内部染色体信息交换机制 的一类处理复杂优化问题的方法，是种基于群体的启发式搜索算法。由于遗传 算法不受问题本身的性质、优化准则形式、被优化参数数目和有无约束等的限制， 仅用目标函数在概率准则引导下进行并行全局自适应搜索，能够处理传统优化方 法难以解决的许多复杂问题，具有极高的鲁棒性和广泛的适用性，因而遗传算法 在动态优化领域得到了广泛应用。 经过近4 0 年的发展，遗传算法的性能被不断改善，所能处理的问题也从以 前的函数优化问题扩展到包括组合优化、动态调度等问题的一个很宽的范围。遗 传算法的主要流程包括基因的编码、选择、交叉、变异操作和适应度的评估等几 个主要步骤。在将遗传算法应用到动态优化问题上时，需要针对动态优化的特点 做一些专门的设计。j e s m i t h 提出在优化问题发生变化后，如果父代个体与子 代个体发生竞争，那么需要对所有父代个体进行重新评估，因为环境的改变会直 第一章绪论 接改变父代个体在解空间中的适应度值 2 5 。h g c o b b 提出了一种称作 h y p e r m u t a t i o n 的方法，此方法通过在环境变化后增加个体的变异概率，来增加群 体的多样性，扩大个体在新环境解空间的分布范围，从而增加算法对于新环境的 探索能力，有利于快速适应动态环境的变化 2 6 。但是这种方法存在一个问题， 在通过随机变异增大群体多样性的同时，历史群体的搜索信息会随之而减少，从 而使算法的收敛性受到了影响。在算法的多样性和收敛性之间维持一个良好的平 衡关系在动态优化问题中显得尤为重要。j j g r e f e n s t e t t e 提出了一种称为随机移 民的策略( r a n d o mi m m i g r a n t ss c h e m e ) 。此方法在每一代产生新个体后，人为的用 一些随机产生的个体来取代群体中的一些个体，并通过这种方法来维持整个群体 的多样性。有了这些随机移民，使得算法的搜索范围能够有效的展开，从而提高 了算法对于动态问题的适应能力 1 2 。n m o r i 和h k i t a 提出了著名的反馈热退 火遗传算法( f e e d b a c kt h e r m o d y n a m i c a lg e n e t i ca l g o r i t h mf t d g a ) ，此算法通过 使用热力学中的最小自由能原理来控制遗传算法的选择操作，并用一个叫做“熵” 的物理量来度量群体的多样性，并将这个“熵”量反馈给控制选择操作的参数7 1 从而实现对变化环境的自适应调节 6 。 1 4 2 基于粒子群优化算法的动态优化算法研究 粒子群算法( p s o ) 是一种通过模拟鸟群、鱼群行为的新型演化算法。它由 e b e r h a a 于1 9 9 5 年提出 2 7 。p s o 算法同遗传算法类似，是一种基于群体迭代的 演化算法。首先，系统初始化为一群粒子( 问题的候选解) ，通过迭代搜索最优 值。p s o 并没有遗传算法的选择和交叉操作，而是通过一群粒子在解空间追随最 优粒子的移动来进行搜索。同遗传算法相比，p s o 的优点在于简单、高效，并且 不需要调整很多参数。目前，p s o 已经被成功应用到如电力、化工、机器人、机 械设计、通讯、经济学、图像处理、生物信息、医学、运筹学等许多领域。 将p s o 算法应用于动态优化问题始于2 0 0 1 年，为了解决群体多样性问题， x h u 和r c e b e r h a r t 提出采用重新初始化粒子的方法来维持系统的多样性 2 8 ， 当检测到坏境发生变化时，算法从群体中选择一部分粒子对其位置进行随机重新 初始化，使其能够扩大搜索范围，维持群体多样性。这种方式能够有效地提高群 体多样性，但是算法的收敛速度受到了影响，并且也很难根据环境的变化来决定 重新初始化粒子的比例。后来，人们逐渐将研究的重点转移到了利用算法中粒子 的各种邻域关系和拓扑结构上。t m b l a c k w e l l 采用互斥粒子( 带电粒子) 来保 证粒子不会快速收敛，这种方法与前一种方法相比，优势在于其相互作用仅仅在 粒子充分收敛的情况下才比较强烈，这样就能够很好的维持收敛性与多样性的平 衡，使得算法搜索效率更高 2 9 。与此同时，x l i 和k h d a m 采用了一种具有 “网格”结构的粒子群策略，这种结构能够有效地减少粒子当前最优位置对搜索 第一章绪论 方向的压力，从而维持了群体的多样性 3 0 。后来s j a n s o n 和m m i d d e n d o r f 采 用了类似的思想，并提出了一种树形结构的p s 0 算法( h p s o ) ，这种方法将每一 个粒子映射到一棵树上，树的层和每层的节点数由自己定义，树的越上层节点的 适应度越大，每一个粒子的速度和位置更新只和其上层节点( 父节点) 有关，通 过这利，特殊的结构，可以有效的维持群体粒子的多样性 3 1 。t m b l a c k w e l l 等 人一些将上述方法与多群体策略结合，提出了多群体粒子群算法( m p s o ) 矛d 多群 体量子粒子群算法( m q s o ) 。此方法将一个粒子群分成多个子群体，并由每一个 子群体对解空间中的潜在最优解位置进行搜索，由于搜索具有针对性，所以这种 方法能够在环境变化后很快的找到新最优解所在的区域，从而大大提高了搜索效 率 3 2 。w l d u 等提出多策略集成粒子群算法( m e p s o ) ，将群体按比例分为 两部分，一部分粒子负责局部搜索，另一部分粒子负责外围巡逻，分别采用不同 的算法策略，两部分粒子之间通过共享群体最优解和一个差分算子建立联系，以 实现良好的收敛性与多样性的平衡 3 5 。 1 4 3 其他演化类动态优化方法介绍 m g u n t s c h 和m m i d d e n d o r f 采用蚁群算法 3 3 用来求解动态t s p 问题。动 态t s p 问题是在传统的静态t s p 问题中允许城市的动态加入和删除。其主要思 想是：保存旧的信息素矩阵中大部分元素，并且重新初始化那些严重受环境变化 影响的部分矩阵元素，这样信息素矩阵就能够根据环境的变化而更新，从而实现 搜索。 r m e n d e s 将差分演化算法( d i f f e r e n t i a le v o l u t i o n ) 弓l 入了动态优化问题，提出 了d y n d e 算法，它是在原有的d e 算法基础上加入了多群体策略及排斥策略， 这种排斥策略能够自适应的修改d e 算法中个体位置的更新向量。这样，通过自 适应调节更新向量参数就能够使每个子群体中的个体对优化空间中的潜在最优 解位置进行跟踪。 s x y a n g 将p b i l 算法与记忆策略思想结合，提出了m p b i l 动态优化算法 3 4 ，其主要思想是通过设置一个显示的记忆存储结构，将历史上训练好的概率 向量以及部分历史信息保存起来。当一个新的环境到来时，首先通过一种机制将 当日仃环境与历史环境比较，找到最为相似的一个，并直接利用与相似环境对应的 概率向量来继续进行优化。这样有效的避免了在环境变化后重新对概率向量进行 初始化而造成的搜索效率降低的问题，从而大大的提高了算法的搜索效率。 1 4 4 动态优化方法主要存在的几个问题 目f ； ，基于演化计算的动态优化方法主要存在以下三个方面的问题有待深入 研究：一个问题是收敛性与多样性平衡的问题。收敛性是指算法在运行过程中， 9 第一章绪论 群体汇聚到某个最优解或者某个较优区域的速度。收敛速度快的算法，其找到较 优解的速度快，但是容易陷入局部最优而不能找到真正的最优解。收敛速度慢的 算法，需要运行相对较长的时间，耗费相对较多的计算代价才能找到局部最优解。 多样性指的是在一个算法的搜索过程中群体在搜索空间分布的特性。收敛性和多 样性是一对矛盾，如果算法侧重收敛速度而忽群体多样性，那么算法在动态变化 的优化问题上就很难改变自己的搜索目标( 搜索方向) ，这就导致对环境变化的 反映不够敏感。如果算法侧重保持群体多样性而忽略收敛速度，那么将会使算法 不收敛，很难找到最优解，在环境变化频率高的情况下，由于没有足够的时间去 找到较优解，就使得算法的优化能力会变低。因此根据环境变化的特点，在收敛 性和群体多样性上面找到一个平衡是每一个动态优化算法需要面对的问题。 另一个问题是如何及时发现环境的变化。在很多情况下，动态环境的变化是 不可预知的，因此算法就需要有能够及时检测到环境变化的能力，这也是关系到 算法反应速度的一个重要指标。但是，对于环境的检测需要有两个条件：一个是 这种检测本身需要耗费一部分计算资源，从而对算法的搜索效率造成一定的影 响。另一个就是环境的检测依赖于群体的多样性。因为检测环境变化需要了解的 是整个解空间的变化信息，如果群体都集中在一个很小的搜索区域内，群体中个 体所反映的空间信息必然也是有限的，但是群体收敛是搜索的必然要求，因此， 寻找一种合适的方法，能够以较小的计算代价去有效的检测环境变化也是一个十 分重要的问题。 还有一个重要问题就是如何充分利用历史环境信息。动态环境的变化会留下 很多历史信息，这些信息具有一定的相关性，对于先验信息的学习有助于算法对 新环境的预测。对新环境预测的准确性直接影响了算法的搜索效率，因此该问题 的解决对算法性能的提高具有重要作用。 1 5 本文主要研究内容及主要创新之处 围绕着动态优化方法及在动态软硬件划分的应用这个论题，本文主要从以下 四个具体方面入手对动态优化方法及其应用进行深入分析研究。 一、p s o 算法在动态连续空间优化问题中的研究 针对动态p s o 算法普遍存在的两个难点问题，即搜索信息的自适应更新问题 和收敛性与多样性的平衡问题，本文提出了一种新的双吸引子多群体粒子群优化 算法( b m p s o ) 。与传统的p s o 算法比较，b m p s o 算法的创新之处可以归纳为以 下三点：1 ) 应用了“广域搜索粒子”( g p ) 和“局域搜索粒子 ( l p ) 两种搜索粒 子，对搜索空间分别进行搜索，并且它们具有各自的特点。2 ) 采用了两个群体 吸引子( s w a r ma t t r a c t o r ) 一“广域吸引子”和“局域吸引子”来指导g p 和l p 的 第一章绪论 更新。两部分搜索粒子的搜索信息通过这两个吸引子来进行共享。3 ) 在b m p s o 中，多个子群体之间使用了一种新的“迁移”机制来避免个各子群体的碰撞。通 过这种机制，能够有效地避免因粗略的重新初始化所有粒子而造成的搜索效率低 的问题。通过上面的方法，b m p s o 较为有效地解决了收敛性与多样性的平衡问 题，具有很好的表现性能。并且在峰的数目变化的m p b 测试问题上有着比传统 动态p s o 算法更为稳定的表现性能。 二、引入记忆策略的动态粒子群优化算法研究 本文将记忆策略引入p s o 算法，提出了一种新的基于记忆策略的粒子群优化 算法( m m p s o ) 。与传统的动态p s o 算法相比，在m m p s o 中，采用了一个额外 的存储空间来保存历史上变化环境的信息。通过将充分收敛后的粒子位置作为环 境有用信息保存到记忆存储结构结构中，实现历史环境信息的记忆( 此部分论证 参考第三章内容) 。当检测到环境变化后，算法会根据当前的环境的特点对记忆 存储结构中保存的环境信息进行评估，从中选择出与新环境最为相似的环境信 息，用来指导新环境下粒子的生成( “c o m p a r e s t o r e g e n e r a t e ”机制) 。通过这种 方式，可以有效地避免在环境变化初期，因为需要重新随机初始化粒子而造成有 用信息丢失以及搜索效率低的问题。 其次本文对传统的m p b 测试问题进行了改进，引入了控制动态环境周期特 性的参数丁。通过参数r 可以控制m p b 问题更为有效的对周期性动态问题进行模 拟。实验结果表明，m m p s o 算法对于周期性m p b 问题具有很好的优化效果。 三、记忆策略在不同算法上的对比实验分析 为了更为全面的对记忆策略进行分析研究，本文实现了m p b i l 算法和 m d p b i l 算法，并将其与传统的p b i l 算法及d p b i l 算法在不同的动态测试问题 上进行实验比较和分析，从对比中得出记忆策略的优点与不足以及其与群体多样 性的依赖关系。 四、m p b i l 算法在动态软硬件划分中的应用研究 对动态软硬件划分问题进行了研究，将m p b i l 算法应用于动态软硬件划分 问题的求解，并与传统的动态划分算法进行了比较。实验结果表明，基于记忆策 略的m p b i l 算法对于动态软硬件划分问题具有更好的性能。 1 6 本文组织结构 本文的章节组织如下：第二章首先介绍标准粒子群算法原理和多群体p s o 策略，然后介绍双吸引子多群体粒子群算法( b m p s o ) 原理及流程，最后通过4 组实验分析比较b m p s o 算法与其他典型的动态粒子群算法的特性。第三章介绍 第章绪论 记忆策略在p s o 算法上的应用，并通过实验对算法性能进行分析；第四章通过 实验比较基于记忆策略的p b i l 算法的性能，分析记忆策略在动态优化问题中的 特点和不足。第五章对软硬件协同设计中的动态划分问题构建数学模型，研究 m p b i l 算法在动态软硬件划分问题中的应用；第六章对本文工作进行总结及展 望。 第- 二章一种基于多群体策略的动态p s 0 算法- - b m p s 0 第二章一种双吸引子多群体动态p s o 算法一b m p s o 在将p s o 算法应用于动态优化问题时，首先需要解决的就是维持粒子多样性 与粒子收敛性之间的平衡问题 1 】。从第一章的介绍中可以了解到历史上解决这 个问题主要是依靠重新初始化粒子位置的方法来增加粒子多样性。但是这种方法 存在很多问题，例如：1 、对粒子的随机初始化会直接导致粒子历史搜索信息的 丢失，从而影响整个群体的搜索效率。2 、多样性和收敛性的平衡难以控制。3 、 随机初始化粒子是一种盲目的增加多样性的行为，其数量很难根据环境变化的强 度来控制。 本文提出了一种基于多群体策略的双吸引子粒子群算法。其主要思想可以归 纳为：使用了两个“群体吸引子”和两种搜索粒子。两种搜索粒子在两个群体吸 引子的控制下独立地进行搜索，它们具有不同范围的搜索特性，一种粒子利于进 行全局搜索，而另一种利于进行局部搜索。通过引入一种新的“传递”机制，两 部分粒子可以更有效地共享搜索信息。通过这种方法可以更为有效的维持群体多 样性，同时保证合理的收敛速度。 本章的结构如下：2 1 节首先介绍标准p s o 算法原理及流程。2 2 节介绍在动 态