（信号与信息处理专业论文）粒子群算法改进研究及其在图像检索中的应用.pdf

哈尔滨工程大学硕士学位论文 摘要 粒子群优化算法( p a r t i c l es w a r mo p t i m i z a t i o n ，以下简称p s o 算法) 模拟 了生物界中鸟群觅食的过程实现了问题寻优，其算法操作简单、涉及参数少， 因此在当今的优化领域中受到越来越多人的关注。p s o 算法的主要缺点是易 于陷入局部最优解、收敛精度低。为此一些改进的p s o 算法应运而生，但是 这些改进算法仍存在计算复杂度高、收敛速度慢等缺点，因此对粒子群算法 进行有效的改进仍然是目前学者研究的一个热点。 本文针对粒子群算法在陷入局部最优时难于跳出的缺陷，提出了一种“基 于种群分类与动态学习因子的粒子群改进算法”。该算法首先利用粒子适应 值的统计规律将粒子分成好、适中、差3 类，用“社会模型”进化表现差的 粒子从而加快其收敛速度；用“认知模型”进化表现好的粒子从而提高其收 敛精度；而对于利用“完全模型 进化的粒子，采用动态调整学习因子的方 法，从而大大提高了算法的优化效率和优化精度。本文通过反复实验分析， 得出学习因子随着进化推进的最优变化规律，并给出了学习因子的最佳函数 表达式。仿真结果表明，利用本文提出改进的p s o 算法优化4 种具有代表性 的基准函数，无论是在优化精度方面还是在优化效率方面，均较p s o - o 算 法在性能上有本质的提高。 鉴于p s o 算法“并行搜索”和“具有记忆”的特性，本文还提出一种“基 于粒子群算法的交互式图像检索方法”，该方法首先采用“变均分单元 法对 图像进行预处理，用预处理后得到的图像矩阵形成特征向量，用特征向量对 粒子进行编码，把目标图像看成问题的解，检索图像的过程就可以看成是利 用粒子群算法在特征空间搜寻最优解的过程。在检索过程中，该方法采用人 机交互的方式对粒子( 即图像) 进行适应度评价，采用这种方式一来解决了 算法适应度函数难于构造的问题；二来保证了适应性评价的客观性。该方法 将p s o 算法“并行搜索”和“具有记忆”的特性与人机交互的检索方式结合， 哈尔滨工程大学硕士学位论文 从而保证了检索到的图像和人们的检索意图一致。最后通过对基于遗传算法 的交互式检索方法与本文提出方法进行仿真对比，证实了本文提出的检索方 法在基于内容的图像检索中的有效性。目前国内外还没有利用p s o 算法的思 想进行图像检索的论文发表，本文将p s o 算法引入到基于内容的图像检索 中，拓展了算法的应用领域，是一次成功的尝试。 关键词：粒子群算法；种群分类；动态学习因子；基于内容的图像检索 哈尔滨工程大学硕士学位论文 a b s t r a c t p a r t i c l es w a r mo p t i m i z a t i o n ( p s o ) a l g o r i t h mi sp u tf o r w a r da c c o r d i n gt o t h es i m u l a t i o no ft h eb i r df l o c ki nt h e i rf o o d s e a r c h i n g b e c a u s eo fn o tm u c h p a r a m e t e ra d j u s t i n g , s i m p l eo p e r a t i o na n de a s ya p p l i c a t i o n ，n o w a d a y sp s o a l g o r i t h mi sp a i dm o r ea n dm o r ea t t e n t i o ni nt h eo p t i m i z i n ga p p l i c a t i o n b u tp s o a l g o r i t h mh a sb a c k w a r d so fe a s yf a l l i n g i n t ol o c a l o p t i m i z a t i o na n d l o w c o n v e r g e n c ep r e c i s i o n f o rt h e s er e a s o n s ，s o m ei m p r o v e m e n t so ft h ea l g o r i t h m w e r ep r o p o s e d t h o u g hg a i n e ds o m ea c h i e v e m e n t sa n dp r o g r e s s ，t h e s ei m p r o v e d a l g o r i t h m ss t i l lh a v ed i s a d v a n t a g e so fh i g hc o m p l e x i t yc o m p u t a t i o na n dl o w c o n v e r g e n c es p e e de t c s op r o p o s i n ge f f i c i e n ti m p r o v e m e n to fp s oi ss t i l la h o t t o p i ca m o n gt h er e s e a r c h e r sn o w p a r t i c l es w a r mo p t i m i z a t i o no , s o ) a l g o r i t h mh a st h ed i s a d v a n t a g et h a to n c e i tg e t si n t ot h el o c a lo p t i m i z a t i o ni ti sv e r yh a r dt oj u m po u tf r o mt h el o c a l o p t i m i z a t i o n f o rt h a tr e a s o n , an o v e li m p r o v e dp a r t i c l ef f w a r i no p t i m i z a t i o n a l g o r i t h mi sp r o p o s e di nt h i sp a p e r t h ea l g o r i t h mc a l lu s es t a t i s t i c a ll a w so f p a r t i c l ef i t n e s st oc l a s s i f yt h ep a r t i c l e s ，a n dt a k ed i f f e r e n te v o l u t i o nm o d e lf o r d i f f e r e n tk i n d so fp a r t i c l e s a n df o rt h ep a r t i c l ee v o l v e di nf u l lm o d e l ，l e a r n i n g f a c t o ri s 砌u s t e dd y n a m i c ，w h i c hc a ne n h a n c et h ee v o l u t i o n e f f i c i e n c ya n d p r e c i s i o ng r e a t l y b yt h ee x p e r i m e n t sa n da n a l y s i s ，t h eo p t i m i z a t i o nv a r i a t i o nr o l e w h i c he v o l v e dw i t ht h el e a r n i n gf a c t o ri sa c h i e v e d ，a n dt h ef u n c t i o ne x p r e s s i o n s o fl e a r n i n gf a c t o ra r eg i v e ni nt h i sp a p e r t h es i m u l a t i o nr e s u l t ss h o w e dt h a t ， c o m p a r e dw i t ho t h e rp s oa l g o r i t h m sp r o p o s e db e f o r e ，i ti si m p r o v e dv i r t u a l l yo n b o t ho p t i m i z a t i o np r e c i s i o na n do p t i m i z a t i o ne f f i c i e n c yb yu s i n gt h ei m p r o v e d p s oa l g o r i t h mt oo p t i m i z e4t y p i c a lb e n c h m a r k s w h e r e a st h ep a r a l l e la n dm e m o r yq u a l i t yo fp s oa l g o r i t h mt h ec b i rb a s e d o ni n t e r a c t i v ep s oa l g o r i t h mi sp r o p o s e di nt h i sp a p e r i nt h i sm e t h o d ，f i r s t l y ， e a c hi m a g ei nt h ec o l l e c t i o ni ss e g m e n t e di n t oac o n s t a n tn u m b e ro f s u b i m a g e s ， a n dt h ec o n t e n ti ne a c hs u b - i m a g ei sc o m p u t e dt om a k eu pt h ef e a t u r ev e c t o ro f 哈尔滨工程大学硕士学位论文 t h ei m a g e l i k et h i s ，“t h ei m a g ed a t a b a s e w a st r a n s f o r m e di n t o t h ef e a t u r e s p a c e ”，w h e r ee v e r yp a r t i c l er e p r e s e n t saf e a t u r ev e c t o ri nt h ef e a t u r es p a c e w e c a nr e g a r do b j e c ti m a g ea st h es o l u t i o nt oq u e s t i o n ，a n dt h ep r o c e s so fr e l r i e v a l i m a g em a y b er e g a r d e da st h ep r o c e s so fs e a r c h i n go p t i m a ls o l u t i o nu s i n gp s o i i lm ef e a t u r es p a c e i nt h er e t r i e v i n g ，t h i sm e t h o de v a l u a t ef i t n e s so fp a r t i c l e ( i m a g e ) u s i n gt h em a n - m a c h i n ei n t e r a c t i o n t h i sm e t h o dc a nn o to n l ys o l v et h e d i f f i c u l t yc o n s t r u c to ff i t n e s sf u n c t i o n ，b u ta l s oe n s b l et h eo b j e c t i v i t yo ff i t n e s s e v a l u a t i o n b e c a u s eo ft h ec o m b i n a t i o np a r a l l e la n dm e m o r yw i t hi n t e r a c t i v e ，t h i s m e t h o dc a na u t o m a t i c a l l ys e a r c ho p t i m a ls o l u t i o n ，a tt h es a m et i m e ，i t se v e r ys t e p w i l lb ea d j u s t e db ym a n u a lp a r t i c i p a t i o n a sar e s u l t ，i ta s s 町e st h a tt h ei m a g e o b t a i n e dc a nc o n s i s t e n tw i t ho u ra t t e n t i o n f i n a l l y , t h r o u g ht h ee x p e r i m e n t s i m u l a t i o n , t h ea v a i l a b i l i t yo ft h ei m p r o v em e t h o dw a s f u r t h e rc o n f i r m e d k e yw o r d s ：p s oa l g o r i t h m ；p o p u l a t i o nc l a s s i f i c a t i o n ；d y n a m i cl e a r n i n gf a c t o r ； c o n t e n t - b a s e di m a g er e t r i e v a l 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体己 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ：自l 虱荽 日期：三矽弼年多月7 日 哈尔滨工程大学硕士学位论文 第1 章绪论 1 1 论文研究的目的及意义 粒子群优化算法( p a r t i c l es w a r mo p t i m i z a t i o n ，以下简称p s o 算法) ，是 由k e n n e d y 和e b e r h a r t 于1 9 9 5 年首次提出的一种基于迭代的寻优算、法f l 】，它 模拟了生物界中鸟群觅食的过程。p s o 算法是一种基于群体( p o p u l a t i o n ) l 拘优 化算法，每个粒子通过和其他粒子进行信息交互，调整自己的进化方向，以 及避免陷入局部最优。由于p s o 算法操作简单、易于实现、涉及参数少，因 此在当前的优化应用中越来越受到人们关注。目前p s o 算法已广泛应用于函 数优化、神经网络训练、模糊系统控制、求解大规模组合优化问题以及遗传 算法所应用的各个领域。 p s o 算法的主要缺点是易于陷入局部最优解、收敛精度低。为此一些改 进的p s o 算法应运而生，如模糊p s o 算、法【2 】、混合p s o 算法1 3 1 、智能p s o 算 法 4 1 、协同p s o 算法 5 1 等。它们从不同的角度对p s o 算法进行了有效改进， 取得了一定的成果和进展，但是这些改进算法仍存在计算复杂度高、收敛速 度慢等缺点，因此对p s o 算法进行有效改进仍然是目前学者研究的一个热 点。 p s o 算法的发展历史只有l o 年左右，还不像其它的启发式算法那样已形 成系统的分析方法和具有坚实的数学基础。目前参数的选择更多的是依靠实 验和经验，没有定理来确定，国内外的有关研究仍停留在实验探索阶段，但 从当前的应用效果来看，这种模仿自然生物的新型系统寻优思想无疑具有十 分光明的前景，更多深入细致的工作还有待于进一步展开。 本文将对p s o 算法近年来的研究进展以及算法的成功应用领域进行归 纳总结，分析对比各种改进算法存在的不足，并针对不足之处在深入理论分 析的基础上进行算法改进，旨在提高p s o 算法的寻优性能；同时由于p s o 算法的“并行搜索”和“具有记忆”的特点对于图像检索非常适用，本课题 哈尔滨工程大学硕士学位论文 将提出一种有效而适用的p s o 图像检索算法。目前国内外还没有p s o 算法 在图像检索中应用的论文发表，所以本课题将在深入研究p s o 算法的基础上 探索其在图像检索领域的应用。 1 2 国内外研究现状 1 2 1 粒子群算法国内外研究现状 自p s o 算法提出以来，由于它操作简单、易于实现，引起了国际上相关 领域众多学者的关注和研究，其研究大致可以分为：算法本身、参数选取、 以及与其他进化算法的融合及应用。下面就这些方面的研究情况做综述性的 介绍。 为了提高p s o 算法的收敛性能，s 1 1 i 等人于1 9 9 8 年在原始p s o 算法的 速度项引入惯性权重( i n e r t i aw e i g h t ) t l ，引入惯性权重是为了平衡粒子的全局 搜索能力和局部搜索能力。如果惯性权重大，则全局搜索能力强，局部搜索 能力弱：反之，则局部搜索能力增强，全局搜索能力减弱，惯性权重的引入 对p s o 算法的性能改善很大，因此称带有惯性权重的p s o 算法为标准p s o 算法。同年，另一个称之为收缩因子( c o n s t r i c t i o n f a c t o r ) 的系数被引入川，但 从数学上分析，这两个参数是等价的。 1 9 9 8 年a n g e l i n e 提出采用遗传算法中的选择操作改进p s o 模型【8 】，称为 混合p s o 算法( h p s o ) 。混和p s o 算法主要应用p s o 算法的基本机制以及遗 传算法所采用的自然选择机制。在a n g e l i n e 的h p s o 模型中，根据适应度函 数选择每次迭代产生的新粒子，用适应度较高的一半粒子的位置和速度矢量 取代适应度较低的一半粒子的矢量，但保持后者个体极值不变。这样p s o 算 法在提高收敛速度的同时保证了一定的全局搜索能力，在大多数的 b e n c h m a r k 函数的优化上取得较原始p s o 算法更好的优化结果。 2 0 0 0 年l o v b j e r g 与r a s m u s s e n 提出将遗传算法中的交叉操作引入p s o 算、法【。基本原理为：粒子群中的粒子被赋予一个交叉概率，这个交叉概率 是用户确定的，与粒子的适应值无关，选择父代时没有基于适应值，这样做 哈尔滨工程大学硕士学位论文 是为了防止在进行多局部极值函数优化时陷入局部最优。 也有人将变异算子引入到p s o 算法中，变异算子的引入主要是为了增强 p s o 算法跳出局部最优解的能力。其变异过程为：首先，确定变异的时机。 很多参数都可以表现粒子群的收敛程度，它们的大小和变化情况可以作为确 定变异时机的依据，例如群体最优个体的历史最优位置的变化 9 1 、粒子群位 置质心到各个粒子当前位置的距离之和 9 1 、群体最优适应值的变化率【l 、群半 径f l l 】( 所有粒子当前位置到全局极值的距离) 、群体适应值的方差1 1 2 1 等。这些参 数可以单独使用，也可以“结合 起来判断变异的时机。 2 0 0 1 年p a r s o p o u l o s 将目标函数进行两步转化的思想应用到了p s o 算法 中0 3 1 。该方法能跳出局部最优，有效定位全局最优点，更稳定地收敛，成功 率有明显提高，但不能枚举全部最优。 2 0 0 2 年a 1 - k a z e m i 提出m u l t i p h a s ep s o 算法0 4 1 ，在群中随机选取部分个 体向全局极值飞，其他个体向反方向飞，以扩大搜索空间。 我国学者孙俊于2 0 0 4 年给出具有量子行为的p s o 算法旧，该方法是一 种不确定的搜索算法。此算法是标准p s o 算法在量子空间的扩展，其性能优 于标准p s o 算法，但用在优化网络权重时，优势并不明显。同年，王俊伟 1 6 1 等通过引入梯度信息来影响粒子速度的更新，构造了一种带有梯度加速的 p s o 算法。梯度信息的加入使粒子的移动更具针对性，进一步提高了p s o 算 法的收敛速度，但也会增加算法对问题的依赖性，特别是有些梯度信息极易 将粒子引向局部最优解。 2 0 0 5 年王华秋提出将模拟退火( s a ) 算法引入到p s o 算法中【- 7 】。这种模拟 退火p s o 算法，结合了p s o 算法的快速寻优能力和s a 的概率突跳特性。粒 子群的追踪过程在各个相对独立的并行进程内完成，从而保证各个种群的多 样性。同年，赵明8 j 等将粒子群优化算法引入抗体的生成，提出了一种基于 粒子群优化机理的多样性抗体生成算法，利用这一算法生成的抗体的多样性 以及算法的收敛速度都令人满意。同年刘靖明提出一种基于粒子群的k 均值 聚类算法【1 9 】。该算法有很好的全局收敛性，有效地克服了传统k 均值算法易 哈尔滨工程大学硕士学位论文 陷入局部最优和对初始值敏感的问题，而且具有较快的收敛速度。同年，俞 欢军1 2 0 1 等提出将h o o k e j e e v e s 模式搜索方法嵌入粒子群优化算法中，此外， 在搜索过程中还加入变异操作。其中，局部搜索增加了算法的开发能力，而 变异操作提高了算法的探测能力。此算法局部搜索能力有显著提高，且搜索 到全局最优的概率更高。 2 0 0 6 年吴延科提出了基于统计规律的p s o 算法【2 l l ，该算法按照粒子的适 应值统计规律对粒子进行分类，对不同类别的粒子采用不同的进化模型，较 大的改善了p s o 算法的性能。p s o 算法是在解决连续优化问题中发展起来的， e b e r h a r t 等又提出了p s o 算法的离散二进制版，用来解决工程实际中的组合 优化问题阎。 以上改进算法各有优缺点，它们引入一些新的参数，在改进算法的同时 增加了算法的复杂性，提高某种性能的同时也为此付出了相应的代价。因此 对p s o 算法的改进研究还存在很大的发展空间。 p s o 算法已经引起越来越多人的关注，尽管它还缺乏完善的理论分析， 其有效性也没有给出严格的数学论证，但回顾模糊控制的发展历史，理论的 不完善并不妨碍应用，有时甚至应用是超前于理论的，并推动理论的研究， 到目前为止，p s o 算法已经广泛应用于函数优化、神经网络训练、模糊系统 控制以及其他遗传算法的应用领域。 1 2 2 基于内容的图像检索国内外研究现状 2 0 世纪7 0 年代末，基于文本的图像检索技术已经产生【2 3 l ，但是随着图 像数据库的增大，其手工注解工作量大、主观性强的弊端就暴露出来，于是 基于内容的图像检索( c o n t e n t b a s e di m a g er e t r i e v a l ，c b i r ) 应运而生。 c b i r 检索技术【z 4 】兴起于9 0 年代，目前该技术的研究主要集中在特征层 次上，根据图像的低层可视特征如，颜色、纹理、形状、空间关系等建立图 像的索引，之后计算数据库中图像和目标图像的相似距离，按相似度匹配进 行检索。该检索技术从提出到现在，国内外已经取得了一些成就，其中，具 哈尔滨工程大学硕士学位论文 有代表性的有如下成果： 1 q b i c 系统 q b i c 系统是由m m 公司开发，同时支持关键词检索与内容检索，支持 示例图像、用户构造的略图、选择的颜色、纹理的查询等。q b i c 系统由图 像入库、特征计算、查询阶段三部分组成。索引技术方面使用6 4 位直方图与 改进的t a m u r a 纹理模型，采用k - l 变换降低维数，利用r 树建立索引嘲。 2 v i s u a ls e e k 系统 v i s u a ls e e k 系统由哥伦比亚大学开发，该系统由四部分组成：图形用户 界面、服务器应用、图像检索服务器和图像归档。在索引技术方面，提出了 基于色彩和纹理的索引方法，使用二进制数进行索引，支持基于视觉特征和 特征之间空间关系的查询 2 6 1 。 3 m a r s 系统 m a r s 系统是由美国i l l i n o i s 大学开发的。它与其它系统在研究范围 和技术上都有不同，它从计算机视觉、d b m s 、信息查询三个领域进行研究， 提出了相关反馈的体系结构 2 7 1 。 4 v t r a g e 系统 v i r a g e 系统是由v i r a g e 公司开发的。与q b i c 系统相似，v i r a g e 支持基 于颜色、纹理和结构的可视化查询，但比q b i c 系统更进一步，它也支持上 述四个子查询的任意组合，用户可以根据自己的侧重调整这四个子查询的权 重。v i r a g e 系统可分为四层进行表示：图像表达层、图像对象层、领域对象 层、领域事件层。系统中图像索引的提取需要经过图像预处理后再提取。这 些特征被称为“原语 。原语可分为色彩、色彩的布局、纹理及空间结构等。 v i r a g e 系统可以通过对不同特征空间中的距离赋予不同的权重，来构成总特 征空间中的复合距离，通过调节权重和检索的特征值，表达不同的特征请求。 国内在c b i r 检索技术的研究中也取得了很大进展1 2 8 1 。例如，浙江大学 计算机系研发的基于图像颜色的检索系统和基于图像形状的检索系统、清华 大学研发的i n t e m e t 上静态图像的c b i r 系统、中国科学院计算机技术研究所 哈尔滨工程大学硕士学位论文 的多媒体信息检索系统( m u l t i m e d i ai n f o r m a t i o nr e t r i e v a ls y s t e m ，m i n e s ) 等。 其中，m i r e s 系统可以完成示例图像、关键词或两种模式交互混合三种方式 的检索，允许用户设置各种特征的权重因子，支持相关反馈。 c b i r 检索技术是一种相似性搜索1 2 9 1 ，不是类似于文本检索的准确匹配， 所以图像相似性度量是c b i r 检索研究中的另一个核心问题。一般来说，不 同的特征对应着不同的相似性度量方法，为此人们对不同的图像特征描述， 定义了不同的相似性判别式，如颜色、纹理、形状和空间关系等。 决定c b i r 性能的两个最主要的问题是： 1 如何利用图像的低级可视特征( 如颜色、纹理、形状等) 有效地表示图 像的内容； 2 如何度量图像的相似性。 目前，绝大多数有关c b i r 的研究工作都是围绕这两个问题展开的p 】， 研究人员力求找到一种能利用图像低级可视特征有效地表示图像内容，并能 有效地计算图像相似性的方法，但是效果并不是很理想。 1 3 本论文主要研究内容及论文安? - i 本课题属于基础理论研究，旨在对粒子群算法近年来的研究发展进行总 结，归纳算法的成功应用领域和存在的不足，并针对算法存在的不足，在深 入理论分析的基础上对算法进行改进，目的在于提高粒子群算法的总体性能； 同时，鉴于粒子群算法的特殊寻优机理即“并行搜索”和“具有记忆对于 基于内容的图像检索很适用，本文提出一种基于粒子群算法的交互式图像检 索方法，并利用计算机进行仿真实现。为此本论文的具体内容安排如下： 第1 章为绪论。首先介绍粒子群算法的研究目的、意义及国内外发展现 状，最后简要介绍本文的主要研究工作和内容安排。 第2 章将介绍粒子群算法的基本原理，首先分析算法涉及的参数对算法 性能的影响，并对现有的经典粒子群改进算法进行综述，分析不同改进算法 的优缺点。其次介绍粒子群算法在函数优化、神经网络训练、组合优化、工 6 哈尔滨工程大学硕士学位论文 程等方面的应用。最后给出用于测试p s o 算法性能的基准函数，以及通过 m a t l a b 仿真出的基准函数图。 第3 章将提出一种基于种群分类与动态学习因子的p s o 改进算法。该算 法首先利用粒子适应值的统计规律对粒子进行分类，用“社会模型”进化表 现差的粒子从而加快其收敛速度；用“认知模型”进化表现好的粒子从而提 高其收敛精度；对于利用“完全模型进化的粒子，采用动态调整学习因子 的方法。本章将通过对标准p s o 算法进行仿真和分析，确定动态因子随着进 化推进的最优变化趋势，并通过大量的实验测试给出其最佳函数表达式；最 后本章将对改进算法与p s o - 盯算法进行仿真对比，证明其有效性。 第4 章将首先介绍基于内容的图像检索( c o n t e n t - b a s e di m a g er e t r i e v a l ， c b i r ) 技术的由来，及其相对传统的基于文本图像检索的优势，并给出c b i r 方法的检索流程，着重介绍c b i r 方法涉及的关键技术如特征提取、特征匹 配、评估方法和交互反馈等，并阐述交互反馈的必要性。这些背景知识将为 下一章将p s o 算法引入到基于内容的图像检索中奠定理论基础。 第5 章将介绍基于内容的图像检索存在的不足，即图像特征不能很好的 表达图像所代表的内容，虽然两幅图像的特征相近，但表达的内容可能千差 万别，导致检索结果背离检索意图。针对这个不足，提出一种“基于粒子群 算法的交互式图像检索方法 ，该方法首先采用“变均分单元”法对图像进行 分割，并对图像的特征信息加以汇总，形成图像的特征向量，如此一来“图 像库 就转变为“特征空间”。每一个粒子代表特征空间中的一个特征向量， 把目标图像看成问题的解，检索图像的过程就可以看成是利用粒子群算法在 特征空间搜寻最优解的过程。在检索过程中，该方法采用人机交互的方式对 粒子( 即图像) 进行适应度评价，采用这种方式一来解决了算法适应度函数 难于构造的问题，二来保证了适应度评价的客观性。该方法将p s o 算法的“并 行搜索”和“具有记忆”的特性与人机交互的检索方式结合，从而保证检索 到的图像和人们的检索意图一致。本章将首先介绍该方法的检索流程，之后 介绍采用“变均分单元”法对图像进行特征提取、利用特征对粒子编码以及 哈尔滨工程大学硕士学位论文 确定新一代样本图像的方法；本章将通过实验仿真，证实该方法在基于内容 的图像检索中的有效性。 最后本文将总结归纳作者一年来在粒子群算法及其在图像检索中的应用 中所作的工作，并对其不足和今后的发展进行展望。 哈尔滨工程大学硕士学位论文 第2 章粒子群优化算法 粒子群优化算法( p a r t i c l es w a r mo p t i m i z a t i o n ，以下简称p s o 算法) ，是 由k e n n e d y 和e b e r h a r t 于1 9 9 5 年首次提出的一种基于迭代的寻优算法。该算 法是对鸟群社会行为的模拟，p s o 算法和遗传算法类似，是一种基于群体 ( p o p u l a t i o n ) 的优化算法，每个粒子通过和其他粒子进行信息交互，调整自己 。的进化方向，以及避免陷入局部最优；同时，p s o 算法采用不同于遗传算法 的随机搜索策略，操作起来要比遗传算法简便得多，因此在解决某些优化问 题时显示出更优越的性能和优势。 2 1 粒子群算法基本原理 p s o 算法把优化问题的解抽象成粒子，如果把粒子想象成一只鸟，从一 组解出发寻求最优解的过程就类似于鸟群寻找食物的过程。p s o 算法的流程 如图2 1 所示。 图2 1p s o 算法的流程图 9 哈尔滨工程大学硕士学位论文 我们用数学语言来描述这个过程。假设在一个维的搜索空间中，每一 个粒子i 都有一个维的位置向量和速度向量k 。用于计算粒子的适应 值，适应值的大小反映粒子与最优解的近似程度，对于最小化问题，适应值 越小，对应的解越好；而圪则用来修正粒子的位置。粒子通过记忆2 个量来 改变位置，一个是粒子在寻找最优解的过程中所经过的最好位置( 记为p b e s t ) ， 另一个是粒子群中最好的那个粒子的位置( 记为g b e s t ) 。 k e n n e d y 和e b e r h a r t 最早提出的原始p s o 算法采用如下公式来更新粒子 状态： i 巧( f + 1 ) = 巧( d + g 坨矾d 一o ) ) + g 聊一蚴 ( 2 1 ) 【0 + 1 ) = 五( d + 巧o + 1 ) 式中：t 表示的是第t 次迭代；以f ) 表示第t 次迭代后第f 个粒子所记忆的p b e s t ， g ( d 表示第t 次迭代后整个群体记忆的g b e s t g2 个r a n d o 是独立的 o ，l 】之间的 随机数；c l 和c 2 是学习因子，均取固定值2 。在实际操作中，为避免算法收 敛过快，还需引进一个阈值，用来保证k 不超过区间【一，珞舡】。 原始p s o 算法涉及的参数主要有如下几种： 1 粒子种群大小m - 粒子种群大小的选择视具体问题而定，但是一般设置 粒子数为2 0 到5 0 个。实际上对于大部分的问题，1 0 个粒子已经足够可 以取得很好的结果，但是对于比较复杂的问题或者特定类型的问题，粒 子数也可以取到1 0 0 或2 0 0 。 2 粒子的长度m 粒子的长度等于问题解的维数。 3 粒子的最大速度：粒子的解在每一维上都有一个最大速度限制值 ，用来对粒子的速度进行限制，使速度控制在【- ，】范围内。 该值一般由用户自己设定。“是一个非常重要的参数。如果“瞰值过 大，则粒子可能会飞过最优区域；另一方面如果。值太小，则可能导 致粒子无法跳出局部最优，无法对局部最优以外的区域进行充分的探测。 假设搜索空间的某一维定义为区间 。，“】，则通常戤= k x 疋懈， i o 哈尔滨工程大学硕士学位论文 0 1 七o 2 ，每一维都用相同的设置方法 3 0 l 。 4 学习因子：为了确定学习因子c l 和c 2 对算法性能的影响，k e n n e d y 做了 大量计算，- 】。p s o 算法的速度更新公式分为三部分：蹦力是“惯性 部分， 表示粒子对上一次迭代速度的继承；c ! r a n d o 似f ) 嘲力) 是“认知 部分， 表示粒子从自身学习的成分；c 2 r a n d o ( g ( t ) 双f ) ) 是“社会”部分，表示 粒子从群体学习的成分。对于p s o 算法的速度更新公式，当c j = 0 时对 应“认知模型”；当c 1 = 0 时对应“社会模型 ；当c l = c 2 时对应“完全 模型”。k e n n e d y 通过大量计算得出如下结论： “认知模型”只考虑粒 子本身的信息，缺少社会信息的交流和共享，所以收敛速度慢；“社会 模型”只考虑群体因素，倾向于向群体学习，收敛速度比较快，但容易 早熟。为了平衡群体因素和个体因素的影响，普遍认为c l = c 2 - 2 效果较 好。 5 迭代终止条件：迭代终止条件一般设为最大迭代次数、计算精度或最优 解的最大凝滞步数。 2 2 粒子群算法的改进现状 p s o 算法提出至今不过1 0 余年，由于p s o 算法在寻优领域表现出的优 越性能，使得越来越多的人对其产生关注。但p s o 算法存在早熟收敛、收敛 精度差等缺点，鉴于此，学者们对其作了多种改进，主要围绕算法本身、参 数选择、以及与其他算法结合等。在原始p s o 算法的基础上，已经出现了很 多有意义的改进p s o 算法。 2 2 1 带惯性权重的p s o 算法 1 9 9 8 年，s h i 等人对速度项啊f ) 引入惯性权重w 6 1 ，引入惯性权重后粒子 的更新公式表示为： lk o + 1 ) = w 巧o ) + c i 陀聊d ) 一( f ”+ c 2 r a n d o ( c , ( t ) 一( 功( 2 - 2 ) 【o + d = o ) + 形0 + 1 ) 1 1 哈尔滨工程大学硕士学位论文 惯性权重w 对算法性能的影响很大，对其研究也很多，比较典型的有以 下几种方法： l 线性调整w 的策略 很明显，当w 较大时，公式( 2 2 ) 的第一部分值比较大，使得速度较大， 有利于跳出局部最优解，而当w 较小时有利于算法的收敛。s h i 和e b e r h a r t 提出了一种随着算法迭代次数的增加惯性权重线性下降的方法d 2 1 ，惯性权重 的计算公式如下： ww w = 一上墼黜砌p( 2 3 ) g e n ，分别是w 的最大值和最小值，g e n 为最大迭代次数，e x e t i m e 为当前迭代次数。文献 3 2 】试验了将w 设置成随着进化的推进，w 的值从0 9 到0 4 的线性下降，使得粒子在开始时探索较大的区域，较快地定位最优解 的大致位置，随着w 逐渐减小，粒子速度减慢，开始精细的局部搜索。该方 法使p s o 算法更好地控制探测和开发的能力，加快了收敛速度，提高了算法 的性能，我们称之为惯性权重线性下降的粒子群算法，简记为l d w ( l i n e a r l y d e c r e a s i n gi n e r t i aw e i g h t ) 。 2 模糊调整w 的策略 p s o 算法的搜索过程是一个非线性的复杂过程，让w 线性下降的方法并 不能正确的反映真实的搜索过程。因而，s l l i 等提出用模糊推理机来动态地 调整惯性权重的技术 2 1 。模糊w 法的优缺点如下：模糊推理机能预测合适的w 值，动态地平衡全局搜索能力和局部搜索能力，从而大大提高了粒子的平均 适应值；但是该方法涉及参数比较多，增加了算法的复杂度，实现起来较为 困难。 由于惯性权重的引入，粒子群算法的性能有了很大的提高。因此称带有 惯性权重的p s o 算法为标准p s o 算法。 2 2 2 带收缩因子的p s o 算法 粒子群优化算法起源于模拟鸟群觅食，算法本身缺乏峰实的数学基础。 1 2 哈尔滨工程大学硕士学位论文 1 9 9 9 年c l e r k 对算法的数学研究证明，采用收缩因子能够确保算法的收幼7 】。 收缩因子模型如下所示： k o + 1 ) = 忌【巧( f ) + g 咒刁堋曰( 吩一( t ) ) + c z r a n d o ( g ( t ) - x ，o ) ) 】( 2 - 4 ) 七2 e i 厕痧= q + g ， 4 2 - 5 通常将矽设为4 1 ( c 1 = c 2 = 2 0 5 ) ，则k 由式( 2 5 ) 计算得o 7 2 9 ，将k 代入式 ( 2 4 ) 与( 2 2 ) 对比一下，则相当于w - - - 0 7 2 9 ，c l = c j = 0 7 2 9 x2 0 5 = 1 4 9 4 4 5 。在算 法早期的试验和应用中，认为当采用收缩因子模型时x 参数无足轻重，后 来的研究表明将其限定为石瞰可以取得更好的优化结果【，3 】。收缩因子法控制 系统行为最终收敛，该方法简记为c f m ( c o n s t r i c t i o nf a c t o rm o d e l ) 。 参数w 和k 的引入，产生两种版本的标准p s o 算法：惯性权重线性下降 算法( l d w ) 和收缩因子模型( c f m ) 。前者是为了提高算法的收敛性能，平衡 收敛的全局性和收敛速度，在多峰函数上效果显著；后者是为了保证算法收 敛性的同时使速度的限制放松，在单峰函数上效果优于l d w 。但两种标准算 法在高维复杂问题寻优时仍然存在早熟收敛、收敛精度比较低的缺点。 2 2 3 粒子群混合算法 p s o 算法和其他优化算法结合是另一个研究热点。经典p s o 算法及其各 种改进算法都着眼于更有效地用一个粒子群在“解空间”中搜索最优解。粒 子在搜索时，总是追逐当前全局最优解，和自己迄今搜索到的历史最优解， 因此粒子们的速度很快降到接近于0 ，导致粒子们陷入局部极小而无法摆脱。 要想扩大搜索范围，就要增加粒子群的粒子数，或者减弱粒子对当前搜索到 的全局最优解的追逐。增加粒子数将导致算法计算复杂度增高，而减弱粒子 对全局最优解的追逐又会造成算法不易收敛。针对这一难题，研究人员提出 了以下几种解决方法。 2 2 3 1 选择法 a n g e l i n e 于1 9 9 8 年提出采用遗传算法中的选择操作改进p s o 模型1 8 1 ，称 哈尔滨工程大学硕士学位论文 为混合p s o ( h p s o ) 。该算法主要应用p s o 算法的基本机制以及遗传算法采 用的自然选择机制。由于p s o 算法搜索过程依赖p b e s t 和g b e s t ，所以搜索区 域有可能被他们限制住，引入自然选择机制将会逐渐减弱其影响。 在a n g e l i n e 的i - i p s o 模型中，根据适应函数选择每次迭代产生的新粒子， 用适应度较高的一半粒子的位置和速度矢量取代适应度较低的一半粒子的矢 量，而保持后者个体极值不变。这样p s o 算法在提高收敛速度的同时保证了 一定的全局搜索能力，在大多数的b e n c h m a r k 函数的优化上取得较原始p s o 算法更好的优化结果，但却在g r i e w a n k 函数上得到了较差的结果。因此该方 法提高了p s o 算法的局部搜索能力，但削弱了全局搜索能力。 必须指出，i - i p s o 算法收敛速度的提高是以牺牲全局搜索能力为前提的。 在解决超高维、非线性、多局部极值的复杂性优化问题时有其局限性，而且 实际的工程优化问题的环境往往是动态变化的，采用上述的半数选择机制并 不能保证对动态环境的跟踪优化。因此，考虑将模糊系统引入选择机制，根 据不同问题制定相应的模糊控制规则，确定合理的输入变量，根据特定的优 化问题进行粒子的动态选择将是这种p s o 模型下一步的研究重点。 2