（计算机科学与技术专业论文）基于小波变异的二进制粒子群算法及应用研究.pdf

a p p l i c a t i o na n dr e s e a r c hf o rw a v e l e tm u t a t i o n b a s e db i n a r y p a r t i cl es w a r ms t r a t e g y b y y u a nj i a n l i a n g b e ( h u n a nn o r m a lu n i v e r s i t y ) 2 0 0 8 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro f e n g i n e e r i n g l n c o m p u t e rs c i e n c ea n dt e c h n o l o g y i nt h e g r a d u a t es c h o o l o f h u n a nu n i v e r s i t y s u p e r v i s o r p r o f e s s o rp e n gm a n m a n m a y ，2 0 1 1 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法 律后果由本人承担。 作者签名： 喜史匆 日期：刃l 年r 月3 0 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编 本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“ ) 作者签名：芬遑勿 导师签名：协蒸复 日期：w f 年丁月如日 e l 期：加，f 年f 月弓口日 基于小波变异的二二进制粒了群算法及_ f 、；f 用研究 摘要 粒子群算法通过一组初始化的粒子群体在搜索空间进行并行搜索，迭代搜索 出最优解。其优点是对问题的依赖性小、概念简单、收敛速度快、容易实现等， 已被广泛应用于函数优化、多目标优化、自动目标检测、生物信号识别、图像分 割、动态环境优化、决策调度、模糊控制系统、神经网络训练等众多领域。然而 粒子群算法主要应用于连续空间的优化问题，而现实世界中还有很多问题是离散 的，变量是有限的，因此需要对粒子群算法进行离散化，使其适用于解决离散空 间优化问题。另外粒子群算法存在早熟的现象，优化结果精度不高，因此需要对 粒子群算法进行改进以提高解的精度。论文的主要工作如下： 首先研究了粒子群算法的基本原理和进化机理，分析了粒子群算法的两种主 要的离散化方法，重点研究了二进制粒子群算法。在遵循二进制粒子群算法基本 原理的基础上，改变了算法的具体进化规则，利用个体最优解和全局最优解以及 上一次迭代结果直接运用贝叶斯公式得出本次迭代粒子位置取值的概率，并将该 概率与随机函数值进行比较确定粒子位置值，提出了改进的二进制粒子群算法。 通过计算d e j o n g 测试函数发现，计算结果符合预期要求，证明了该算法的有效 性和收敛性。 其次针对改进的二进制粒子群算法容易早熟、解精度不高的缺点，引入小波 变异操作，对粒子进行微调，提高粒子群体的多样性，提出了基于小波变异的二 进制粒子群算法。从实验得知，该算法计算结果优于二进制粒子群算法，有更好 的搜索精度，解的质量更高。 最后将基于小波变异二进制粒子群算法应用于软硬件划分问题。将目标系统 的结构规定为二向划分模式，也就是单c p u + 单a s i c 结构，对该结构的目标系统 采用d a g 图进行建模，将软硬件划分问题转化为带约束条件的0 1 背包问题。并 提出一种改进的广度优先遍历法对系统进行任务调度，通过对实例的计算证明该 调度策略是有效的。用小波变异二进制粒子群算法和二进制粒子群算法对不同规 模的划分问题进行软硬件划分，实验结果表明小波变异二进制粒子群算法解的质 量高于二进制粒子群算法，在满足约束的基础上，系统的执行时间更短，划分结 果更好。 关键词：二进制粒子群算法；贝叶斯；小波变异；软硬件划分；广度优先遍历 _ _ _ _ _ _ _ _ _ _ _ 。_ _ _ _ _ _ _ _ 。一 硕十学位论文 a b s t r a c t p a r t i c l es w a r ma l g o r i t h m sg e tt h e i ro p t i m a ls o l u t i o n si t e r a t i v e l y ，t h r o u g h t h e p a r a l l e ls e a r c ha p p r o a c h e sb yag r o u po fi n i t i a lp a r t i c l es w a r m s w e a kd e p e n d e n c i e s t op r o b l e m s ，s i m p l ec o n c e p t s ，q u i c kc o n v e r g e n c e ，a n de a s y t ob ei m p l e m e n t e da r e t y p i c a la d v a n t a g e so fi t a c c o r d i n g l y ，i ti sg e n e r a l l ya d o p t e d i nf u n c t i o no p t i m i z a t i o n ， m u l t i p l eo b i e c t i v eo p t i m i z a t i o n s ，a u t o m a t i c o b j e c t i v ed e t e c t i o n ，b i o l o g i c a ls i g n a l r e c o g n i t i o n ，i m a g ep a r t i t i o n i n g ，d y n a m i c a l e n v i r o n m e n to p t i m i z a t i o n ，s c h e d u l i n g d e c i s i o n ，f u z z yc o n t r o ls y s t e m ，n e u r a ln e t w o r kt r a i n i n g ，e t c n e v e r t h e l e s s ，p a r t i c l e s w a r m a l g o r i t h m s a r e u s u a l l ya c c e p t a b l e t ot h e o p t i m i z a t i o np r o b l e m sf o rc o n t i n u o u ss p a c e ，w h i l eh a r d l ya d a p t a b l et ot h en u m e r o u s e x i s t i n gp r o b l e m sw h i c ha r ed i s c r e t e ，j u s tw i t hl i m i t e dv a r i a b l e s c o n s e q u e n t l y ，t o m a k et h e ma c c o m m o d a t e dt ot h eo p t i m i z a t i o np r o b l e m si nd i s c r e t es p a c e ，t h ep a r t i c l e s w a r ma l g o r i t h m ss h o u l db ed i s c r e t i z e d a d d i t i o n a l l y ，t h ep r e m a t u r e c o u l db e c o m m e n c e di np a r t i c l e s w a r ma l g o r i t h m s ，w h i c hw i l lc o n t r i b u t e t od e c r e a s eo f p r e c i s i o n f o rs o l u t i o n s t h e r e f o r e ，t h ep r e c i s i o n o fs o l u t i o n ss h o u l db ef u r t h e r i m p r o v e d t h i sp a p e rf o c u s e s o nt h ef o l l o w i n gi s s u e s ： a tp i r s t ，t h eb a s i cp r i n c i p l e a n de v o l u t i o nm e c h a n i s mo fp a r t i c l e s w a r m a i g o r i t h m sa r er e s e a r c h e d ，t h ep r i m a r yt w ok i n d so fd i s c r e t ea p p r o a c h e s a r ea n a l y z e d ， a n df u r t h e rd e d i c a t et ot h eb i n a r yp a r t i c l es w a r ma l g o r i t h m s o n t h ef o u n d a t i o no f b a s i cp r i n c i p l eo fb i n a r yp a r t i c l es w a r m ，t h ec o n c r e t ee v o l u t i o nr u l e sa r e t r a n s f o r m e d t h ep r o b a b i l i t yf o rc u r r e n tp o s i t i o no fp a r t i c l es w a r m i sc a l c u l a t e db yi n t r o d u c t i o no f b a v e sf o r m u l a s ，b a s e do nt h er e s u l to ft h ec o m b i n a t i o no f t h ei n d i v i d u a lo p t i m a l s o l u t i o n ，g l o b a lo p t i m a ls o l u t i o na n dt h er e s u l to fl a s ti t e r a t i o n t h e n ，t h ep r o b a b i l i t y i sc o m p a r e dt oar a n d o mv a l u e ，i no r d e rt od e t e r m i n et h ep o s i t i o nf o rp a r t i c l es w a r m m e a n w h i l e ，b a s e do nt h e s ep r i n c i p l e s ，a no p t i m i z e db i n a r yp a r t i c l e s w a r ma l g o r i t h m w a sp r o p o s e d e x p e r i m e n tr e s u l t s d e m o n s t r a t et h a tt h es o l u t i o n s a r ee f f e c t i v e ， c o n v e r g e n ta n dp a r a l l e lt ot h ee x p e c t e dr e q u i r e m e n t s ，v i at h ec o m p u t a t i o n o fd e j o n g t e s t a ts e c o n d ，o nt h ep u r p o s eo fd e a lw i t ht h ed e f i c i e n c yo fi m p r o v e db i n a r yp a r t i c l e s w a r ma l g o r i t h m s ，s u c ha se a s yp r e m a t u r e ，l o wp r e c i s i o no fs o l u t i o n s ，aw a v e l e t m u t a t i o no p e r a t i o nw a si n t r o d u c e dt oa d j u s tt h ep a r t i c l es w a r m ss l i g h t l ya n di m p r o v e t h ed i v e r s i t yo ft h e m ，t h e naw a v e l e tm u t a t i o n b a s e db i n a r yp a r t i c l es w a r ma l g o r i t h m i l l w a sp r e s e n t e d t h er e s u l t sg a i n e df r o mt h i sa l g o r i t h ma r em o r ep r e c l s et h a nb l n 8 r y p a r t i c l es w a r ma l g o r i t h m a tl a s t t h ew a v e l e t m u t a t i o n b a s e db i n a r yp a r t i c l e s w a r m a l g o r i t h m i s i n t r o d u c e df o rt h es o f t w a r e h a r d w a r ep a r t i t i o n i n gp r o b l e m s t h eo b j e c t i v es y s t e ma r e c o n s t r a i n e da sb i d i m e n s i o n a lp a r t i t i o n i n gp a t t e r n ，s a ys i n g l ec p ua n ds i n g l ea s i c a r c h i t e c t u r e t h e n ，d i r e c t e da c y c l i cg r a p h ( d a g ) w a su s e dt o m o d e lt h eo b j e c t i v e s v s t e m ，a n dt r a n s f o r m t h es o f t w a r e h a r d w a r ep a r t i t i o n i n gp r o b l e m s i n t os n a c k p r o b l e m ，w i t hc o n s t r a i n t s ai m p r o v e db r e a d t h f i r s ts e a r c ha p p r o a c hw a sp r o p o s e dt o s c h e d u l et h et a s k s ，w h o s ee f f i c i e n c i e sa r ev e r i f i e db yt h ec o m p u t a t i o no fi n s t a n c e s w a v e l e tm u t a t i o nb i n a r yp a r t i c l es w a r mm e t h o da n db i n a r yp a r t i c l es w a r ma p p r o a c h a r ea d o p t e dt op a r t i t i o nt h es o f t w a r ea n dh a r d w a r e t a s k si nd i f f e r e n ts c a l e t h e e x p e r i m e n tr e s u l t si n d i c a t et h es o l u t i o no ff o r m e ri sb e t t e rt h a nl a t e r ，s i n c ei t so v e r a l l e x e c u t i n gt i m ei ss h o r t e ra n dt h ep a r t i t i o n i n gr e s u l t i sb e t t e r ，u n d e rt h ec o n d i t i o no f m e e t i n ga l lt h ec o n s t r a i n t s k e yw o r d s ：b i n a r yp a r t i c l es w a r ma l g o r i t h m ；b a y e s ；w a v e l e tm u t a t i o n ；s o f t w a r e h a r d w a r ep a r t i t i o n i n g ；b r e a d t hf i r s ts e a r c h i v 坝f 学f 讧论文 目录 学位论文原创性声明i 摘要i l a b s t r a c t i i i 目录v 插图索引v i i 附表索引v i i 第1 章绪论1 1 1 课题背景及研究意义1 1 2 主要研究内容3 1 3 论文的组织结构4 第2 章粒子群算法基础6 2 1 粒子群算法产生的背景6 2 2 粒子群算法研究现状7 2 2 1 粒子群算法的理论研究。8 2 2 2 粒子群算法的性能改进研究9 2 2 3 邻域拓扑结构1 2 2 2 4 离散粒子群算法研究1 4 2 2 5 粒子群算法的应用1 4 2 3 粒子群算法离散化方法1 5 2 3 1 基于连续空间的离散粒子群算法1 5 2 3 2 基于离散空间的离散粒子群算法1 6 2 4 几种典型的离散粒子群算法1 7 2 4 1 二进制编码的粒子群算法1 7 2 4 2 混合编码的粒子群算法1 8 2 4 3 整数空间的粒子群算法1 9 2 4 4 顺序编码的粒子群算法2 0 2 5 离散粒子群算法的应用2 1 2 5 1n 皇后问题2 1 2 5 2 电网机组控制问题2 2 2 5 3t s p 问题2 2 2 5 4v r p 问题2 2 v 早十小波蹙异的- 二进制粒r 群算法及胁用珂f 究 2 6 j 、结：2 3 第3 章基于小波变异的二进制粒子群算法2 4 3 1 二进制粒子群算法2 4 3 2 改进的二进制粒子群算法2 6 3 2 1 贝叶斯公式2 6 3 2 2i b p s o 算法2 7 3 2 3 实验及数据分析31 3 3 基于小波变异的二进制粒子群算法3 5 3 3 1 小波变异3 6 3 3 2 算法流程3 7 3 3 3 实验及数据分析3 7 3 4 小结3 8 第4 章w i b p s o 算法在软硬件划分问题上的应用3 9 4 1 前言3 9 4 1 1 软硬件协同设计3 9 4 1 2 软硬件划分4 0 4 2 目标软硬件系统描述4 2 4 2 1 目标系统结构4 2 4 2 2 目标系统建模4 2 4 3 算法流程4 6 4 4 实验与数据分析4 6 4 5 j 、结4 9 结论5 0 参考文献5 2 致谢5 8 附录a攻读学位期间所发表的学术论文目录5 9 附录b攻读学位期间参加的科研项目6 0 v i r 。_ _ _ _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ _ - 。1 1 。 基于小波变异的_ 二进制粒了群算法及应用研究 插图索引 图1 1 传统优化方法流程1 图2 1 环形拓扑结构1 2 图2 2 轮形拓扑结构1 3 图2 3 编码交换流程2 1 图3 1 二进制粒子群算法流程图2 5 图3 2 函数1 迭代效果图3 2 图3 3 函数2 迭代效果图f 3 3 图3 4 函数3 迭代效果图3 4 图3 5i b p s o 算法迭代过程值的变化情况3 5 图4 1 软硬件协同设计流程图4 0 图4 2 目标系统结构4 2 图4 3d a g 模型表示的任务图g 4 3 图4 4 化简后的任务图g 4 4 图4 5 图4 4 的邻接矩阵4 5 图4 6 目标系统d a g 图4 7 图4 7w i b p s o 与b p s o 平均调度时间4 8 v i i 基于小波变异的二进制粒了群算法及戍用研究 附表索引 表2 1 粒子群算法设计应用1 5 表3 1 测试函数1 的实验数据3 2 表3 2 测试函数2 的实验数据3 3 表3 3 测试函数3 的实验数据3 4 表3 4i b p s o 与b p s o 算法对三个测试函数的计算结果3 5 表3 5w i b p s o 与i b p s o 算法对三个测试函数的计算结果3 7 表4 1 各节点的属性值4 7 表4 2w i b p s o 与b p s o 结果比较4 8 i l 硕i j 学位论文 1 1 课题背景及研究意义 第1 章绪论 研究在工程、技术、经济、管理和科学研究等众多领域和交叉领域中经常遇 到的最优化问题，具有广泛的理论价值和应用价值。现在，最优化方法得到越来 越广泛的应用，在经济和社会发展中发挥着越来越重要的作用。所谓最优化问题， 就是指在满足一定的约束条件下，寻找一组参数值，使某些最优性度量得到满足， 即系统的某些性能指标达到最优( 最大或最小) 。传统优化方法主要有线性规划的 单纯形法和非线性规划的基于梯度的各类迭代算法两大类。这些算法的基本步骤 包括以下三个步骤，如图1 1 所示。 图1 1 传统优化方法流程 传统优化方法的这种计算框架具有难以克服的局限性。主要有以下几个方面： ( 1 ) 单点运算方式大大限制了计算效率的提高 传统优化方法是从初始解开始，迭代过程针对一个点，难以发挥现代计算机 高速计算的性能。特别是在多核c p u 和现代并行计算模式中很难应用，这限制了 算法求解大规模问题的能力。 ( 2 ) 向改进方向移动限制了跳出局部最优的能力 传统优化方法每一次迭代都是按照改进方向移动，这样一旦进入某个局部的 低谷，就没有“爬山”能力，局限于这个低谷区域，不能搜索该区域以外的其他区 域。 皋于小波变异的_ 二进制粒了群算法t o r = ，l 及戍用 ( 3 ) 停止条件只是局部最优性的条件 传统优化方法的结束条件只是最优解的必要条件，并不是充分必要条件。只 有当解的可行域是凸集，并且目标函数是凸函数时，才能保证获得的解是全局最 优解。 ( 4 ) 对目标函数和约束函数的要求限制了算法的应用范围 传统优化方法通常要求目标函数和约束函数是连续可微的解析函数，甚至有 的算法要求这些函数是高阶可微的，这样的条件在实际中往往很难满足。 针对传统优化方法的不足，对优化问题提出了一些新的需求，从而诞生了智 能优化方法，并且发展非常的迅猛。这些需求主要包括以下几个方面： ( 1 ) 对目标函数和约束函数的要求必须更加宽松 实际问题中，目标函数和约束函数可能都不是解析的，那么希望它们可以不 必是解析的，更不必是连续和可微的。那么，目标函数和约束函数只要蕴含的规 则、条件和逻辑关系，更加宽松的条件就是只要这种关系能够被描叙成由一段计 算机程序的返回值就可以，便可作为目标函数或者约束函数使用。 ( 2 ) 计算效率比理论最优性更加重要 不同于传统优化方法，智能优化方法改进方向不是定向的，那么就不必太注 重理论的最优性，而且实际问题并不是重点关注解的理论最优，而更加注重计算 效率和收敛速度。由于实际问题规模比较大，要求很强的实时性和实效性，这就 要求优化方法能高效快速地得出令人满意的解，这个解只需达到一定要求，很多 情况下，是否为最优解并不十分重要。 ( 3 ) 对优化模型中数据质量要求更加宽松 传统优化方法是精确的数学方法，对数据的质量和准确性要求相对严格，而 实际生活，很多信息量是不确定的，有很强的模糊性。 ( 4 ) 算法任意时刻终止都能得到较好的解 由于许多实际问题要求很高的实时性，这类问题可能并不需要得到最好的结 果，只需要随时能得到较好的解，而传统优化方法不能保证随时终止随时得到较 好解，甚至都得不到可行解。 以上这些要求以及实际生活对最优化方法的需求促进了最优化方法的发展， 新的优化方法不断出现。 1 9 7 5 年，h o l l a n d 提出遗传算法；1 9 9 7 年，g l o v e r 提出禁忌搜索算法；1 9 8 3 年， k i r k p a t r i c k 提出模拟退火算法；2 0 世纪9 0 年代，d o r i g o 等提出蚁群算法；1 9 9 5 年， k e n n e d y 和e b e r h a r t 提出粒子群算法；1 9 9 9 年，l i n h a r e s 提出捕食算法。这些算法 相对于传统优化方法，被称为智能优化算法，它们有一些共同的特点： ( 1 ) 优化目的不是为了找到理论最优值，更加看重算法的收敛速度和计算效 率。 2 硕1 ：学位论文 ( 2 ) 对目标函数和约束函数的要求比较宽松。 ( 3 ) 算法的灵感来自自然界，基本是对某自然规律的模拟，具有人工智能的 特点。 ( 4 ) 多数算法有种群这一概念，优化寻优的过程就是种群进化的过程。 ( 5 ) 算法的理论研究相对其应用比较薄弱。 粒子群算法作为解决最优化问题的一种智能优化算法，自从提出以来，引起 国际上相关领域众多学者的关注并投入人力物力进行研究。 粒子群优化算法【1j 是通过对社会型生物群体行为模型提出的一类新型的生物 启发式算法，它源于对鸟类捕食行为的模拟仿真。后来，s h i 等人为了控制算法收 敛性和探索能力1 2 j ，引入了w 这一惯性权重，形成基本粒子群算法。粒子群算法通 过一组初始化的粒子群体在搜索空间进行并行搜索，它无须梯度信息、对问题的 依赖性小、概念简单、收敛速度快、容易实现等优点，已被广泛应用于函数优化、 多目标优化、自动目标检测、语音识别、生物信号识别、图像分割、动态环境优 化、决策调度、模糊控制系统、神经网络训练等众多领域。粒子群算法的主要研 究方向有算法理论分析、算法性能改进、拓扑结构、算法的应用及算法离散化这 几个方面。 粒子群算法虽然应用的非常广泛，但是算法的理论研究部分比较薄弱，不够 深入和完善。另外，由于粒子群算法在搜索后期，每个粒子的最好位置、整个粒 j 子群的全局最好位置和粒子的当前位置都会趋于同一点，而每个微粒的运动速度 则趋于零，导致局部寻优能力较差【3 1 。标准粒子群算法主要应用解决连续空间的 优化问题，而当目标问题属于离散空问时，标准粒子群算法的应用显得力不从心， 需要对粒子的优化过程进行改进。而目前离散粒子群算法的研究较少，所以将标 准粒子群算法离散化是非常有意义的研究。 无论标准粒子群算法还是离散粒子群算法由于算法本身进化机理，容易早熟， 陷入局部最优，使得解的精度不高，解的质量偏低。二进制粒子群算法作为离散 粒子群算法的一种，可以有效地解决组合优化问题，但是也具有粒子群算法的弱 点，即解的精度不高，所以提高二进制粒子群算法解的精度和解的质量也是非常 具有研究价值。 1 2 主要研究内容 本文研究了粒子群算法的基本原理和进化机理，阐述了粒子群算法的主要研 究方向和内容。针对主要研究内容之一离散粒子群算法，在前人研究的基础上， 基于粒子群算法的进化机理，提出了一种改进的二进制粒子群算法，该算法适用 于解决组合优化这一离散优化问题，对d e j o n g 测试函数进行计算，证明了该算 法对测试函数的计算具有收敛性和有效性。针对粒子群算法容易发生早熟现象、 3 綦十小波变异的_ 二逃制粒了群算法研究及应用 陷入局部最优、搜索精度不高的缺陷，将小波变异引入改进的二进制粒子群算法， 提出基于小波变异的二进制粒子群算法，用该算法和二进制粒子群算法对d e j o n g 测试函数计算，实验数据显示该算法搜索精度更高，优化结果更好。最后将基于 小波变异的粒子群算法应用于软硬件划分问题，定义了软硬件系统的系统结构和 系统模型，经过该算法优化后的划分结果系统执行时间短，功耗和面积使用都比 较低。论文主要内容有： ( 1 1 对二进制粒子群算法的分析和设计。论文分析了粒子群算法的离散化方 法，阐述了几种典型的离散粒子群算法，并列举了它们的主要应用。在此基础上， 分析了二进制粒子群算法的基本原理，并遵循该原理，改变了算法的具体进化规 则，利用个体最优解和全局最优解以及上一次迭代结果直接运用贝叶斯公式得出 本次迭代粒子取值的概率，形成改进的二进制粒子群算法。为了进一步提高优化 结果的精度，解决粒子群算法早熟的问题，将小波变异引入改进的二进制粒子群 算法中，提高了解的精度。 ( 2 ) 将算法用以计算d e j o n g 测试函数。列举了3 个测试函数，并分析了各个 测试函数的特点，用改进的二进制粒子群算法计算了这3 个测试函数，得到了较 好的结果，实验数据证明该算法的正确性和收敛性，但其解的效果参差不齐，解 的精度不高。为此，利用本文提出的基于小波变异的二进制粒子群算法对三个函 数进行测试了计算，实验表明，该算法解的精度高于二进制粒子群算法的优化结 果。 ( 3 ) 将小波变异粒子群算法应用于软硬件划分问题。软硬件划分问题是一个 n p 难问题，一直是一个比较难以解决的优化问题，并且属于离散优化问题，是 一个组合优化问题。首先确定目标系统属于二向划分问题，定义系统结构，对目 标系统进行建模，提出改进的广度优先遍历策略，解决系统的调度问题。阐述了 基于小波变异的二进制粒子群算法解决软硬件划分问题的算法流程，与二进制粒 子群算法的优化结果进行比较，该算法优化后的软硬件划分结果系统执行时间更 少。 1 3 论文的组织结构 论文主要对离散粒子群算法进行研究，提出了一种改进的二进制粒子群算 法，保持了粒子群算法概念简单，收敛速度快，易于实现的特点，并通过实验证 明了该算法的有效性。为了提高该算法的优化精度，引入小波变异操作，提出了 基于小波变异的二进制粒子群算法，增加了粒子种群的多样性，有效地提高了解 的精度。 论文的章节安排如下： 第1 章是绪论部分，说明课题的背景以及研究意义，并介绍了论文的主要研 4 硕f j 学位论文 究内容和章节安排。 第2 章是介绍粒子群算法产生背景以及研究现状，重点描述了离散粒子群算 法。先介绍了粒子群算法的基本模式，再从粒子群算法的理论研究、性能的改进、 邻域拓扑结构、典型的离散粒子群算法和粒子群算法的应用这五个方面介绍了国 内外对粒子群算法的研究现状。然后介绍了粒子群算法离散化的两种基本方法以 及二进制编码、混合编码、整数编码、顺序编码这四种版本的离散粒子群算法。 最后就离散粒子群算法主要应用解决两种问题：一种是变量为0 ，1 的类似0 1 背 包问题，另一种是变量为整数的具有排序特点的问题，阐述了几种具体的应用。 第3 章是基于小波变异的二进制粒子群算法。首先详细介绍了二进制粒子群 算法和贝叶斯公式，脱离传统粒子群算法的速度位移更新算子的表达方式，在满 足粒子群算法进化机理的基础上，直接利用个体最优解和全局最优解以及上一次 迭代结果运用贝叶斯公式得出本次迭代粒子取值的概率，提出了一种改进的二进 制粒子群算法。然后计算d e j o n g 测试函数证明了算法的有效性。最后将小波变 异引入改进的二进制粒子群算法，提出了一种基于小波变异的二进制粒子群算法， 实验结果表明该算法增加了粒子种群的多样性，有效地提高了解的精度。 第4 章介绍了软硬件划分的基本内容，规定了目标系统是二向划分系统，定 义了系统结构，并对系统进行了建模，提出改进的广度优先遍历法对系统任务图 进行任务调度计算任务执行时间。在该模型上，应用基于小波的二进制粒子群算 法进行软硬件划分，并与二进制粒子群算法的划分结果进行比较，实验数据显示 随着问题规模的增大，无论是划分结果的最优的系统运行时间还是平均系统运行 时问均优于二进制粒子群算法。 5 甚于小波变异的_ 二边制粒了群算泫研究及戍用 第2 章粒子群算法基础 2 1 粒子群算法产生的背景 在自然界中，随机排列、个体离散的动物群体运动保持着惊人的同步性，这 一直是研究者们感兴趣的问题。例如，上世纪八十年代c r a i gr e y n o l s 提出了b o i d 模型模拟鸟类聚集飞行的行为1 4 j ，对现实世界中的这些群体运动进行观察，将这 些“鸟”看成一个个粒子，在计算机中复制和重现这些运动轨迹，并基于这些运动 进行抽象建模，以发现新的运动模式。该模型设定的规则有：个体之间碰撞的避 免；个体与附近个体的速度保持一致；个体必须飞向邻域的中心。之后，生物学 家f r a n kh e p p n e r 在这个基础上增加了栖息地或者食物源对鸟会产生吸引以及随 机因素的影响的仿真条件，提出了新的鸟群模型【5 1 。这两种鸟类模型最基本的规 则是个体之间会相互吸引和排斥，并且能够信息共享。 在上个世纪9 0 年代初期，复杂适应系统c a s ( c o m p l e xa d a p t i v es y s t e m ) t 里论 有了长足的发展【6 】。c a s 中的成员称为主体，主体有适应性，所谓适应，就是个 体与环境之间的主动的、反复的交互作用。主体能够与环境及其他主体进行交流， 并且根据交流的过程中“学习”或“积累经验”改变自身结构和行为。复杂适应系统 理论的主要特点是： ( 1 ) 主体是主动的、活的实体； ( 2 ) 体与环境相互影响、相互作用，是系统演变和进化的主要动力； ( 3 ) 把宏观和微观有机地联系起来； ( 4 ) 引进了随机因素的作用，使它具有更强的描述和表达能力。 粒子群算法起初是应用到连续空间的，这种基于连续空问的问题在现实中有 广泛的应用，但是现实世界中还有很多问题的离散的，变量是有限的。比如一些 经典的问题，有整数规划问题、，l 争后问题、旅行商问题、调度与路由问题等等。 所幸的是，粒子群算法能够容易适应离散空间，这些离散值通过将加、减、乘、 除等算术操作离散化得以计算，很容易用于离散问题。通常这样的改变是通过改 变粒子速度，粒子轨迹和速度限制与冲量的意义来实现的。 粒子群算法如果按照粒子对粒子群体的其它粒子的感知程度，可以把粒子群 算法分为全局版本粒子群算法和局部版本粒子群算法，局部版本中的粒子只知道 某种近邻结构中的最好值，而全局版本中的每个粒子能知道粒子群中所有粒子的 历史最好解。全局版本又叫基本粒子群算法。 基本粒子群算法的数学描述为设在一个，l 维的搜索空间中，由m 个微粒组成 6 硕f j 学位论文 的群体x = “，x 2 ，j 。) 。在群体中第i 个微粒位置为x i 一“。，x i ：，气广，其速度为 v i 一“，u ：厂。粒子群的个体极值记为只一 晶，只：，最，粒子群的全局极值为 乞= f g 。，乞：，乇) r ，微粒f 的速度和位置更新公式分别为 v , j ( t + 1 ) = v i j ( t ) + c l x r a n d o x ( p o x o ( t ) ) + c 2x r a n d o x ( 乞一嘞( f ” ( 2 1 ) 驴 ” ( 2 2 ) u ，2 l z z j 【叫懈， v o 。时，一v m 。；当 一；时，v o 一- - v m 。 粒子群速度位置公式主要由三部分构成，第一部分表示粒子依据惯性原则对 自身先前速度的继承；第二部分是粒子的自我认知部分，即粒子所经历的最优位 置对粒子位置更新的影响；第三部分就是社会认知部分，它表示的是粒子之间的 相互合作与信息共享，即全局最优位置对粒子位置更新的影响。 2 2 粒子群算法