博士学位论文-粒子群算法及其在图像分割中的应用与研究.pdf

江南大学 博士学位论文 粒子群算法及其在图像分割中的应用与研究 姓名：高浩 申请学位级别：博士 专业：轻工信息技术与工程 指导教师：须文波 20091201 摘要 摘要 粒子群优化算法源于鸟群和鱼群群体运动行为的研究，是一种新的群体智能优化算 法，是演化计算领域中的一个新的分支。它的主要特点是原理简单、参数少、收敛速度 快，所需领域知识少。该算法的出现引起了学者们极大的关注，已在函数优化、神经网 络训练、组合优化、机器人路径规划等领域获得了广泛应用，并取得了较好的效果。尽 管粒子群优化算法发展近十年，但无论是理论分析还是实践应用都尚未成熟，有大量的 问题值得研究。 本文从算法机理、算法改进和算法应用等方面对其进行了系统性的研究。此外，图 像分割是图像分析和模式识别的首要问题，也是图像处理的经典难题之一。本文将微粒 群算法和图像分割法相结合，提出了基于改进p s o 算法的分割算法，在取得良好的分 割效果的同时，运用算法的并行搜索机制显著的提高了分割速度。论文具体内容如下t ( 1 )对粒子群算法及其理论基础( 优化方法和进化计算) 进行了详细的综述。 首先本文概述了优化方法的产生和发展，着重介绍了优化方法的基本思想、研究领域、 应用发展情况；阐述了进化计算的产生、定义以及研究内容，并介绍了几种典型的进化 计算方法，包括遗传算法、进化策略、微分进化等；最后介绍了粒子群优化算法，阐述 了粒子群优化算法的起源，介绍了粒子群优化算法的初始版本和标准版本，从理论研究 和应用研究的角度综述了粒子群优化研究的现状，总结了标准粒子群优化算法存在的问 题。同时本文使用了蒙特卡罗方法对粒子的行为进行了研究，结果显示p s o 算法在迭 代后期具有搜索能力较弱的缺点，同时也给出了如何提高p s o 算法收敛性的方法。此 外，九个标准测试函数用来测试p s o 算法和其他几种流行的进化计算方法的性能，结 果验证了p s o 有着其他进化算法无法比拟的快速收敛等特性。 ( 2 )尽管p s o 算法比其他算法对复杂函数有着较强的寻优能力以及收敛速度快 等特点，但是它依然无法保证在搜索空间中找到全局最优点。因此在本文中引入了具有 着更强全局搜索能力的q p s o 算法来进行研究改进。但是由于q p s o 同p s o 算法一样 的是，它也把粒子作为一个整体来进行更新，因此q p s o 算法同样具有维数限制的缺点。 通过把一个具有复杂高维的粒子分解为多个一维的子个体进行优化，使用协作方法的 q p s o 算法能够很好的克服这一缺点。八个测试函数以及应用于图像分割领域的最大类 间方差法( o t s u 方法) 在本文中用来测试改进以后的q p s o 算法的成绩。仿真结果表 明，与其他算法比较来看，协作方法帮助q p s o 算法获得更精确的解。它同样也克服了 o t s u 方法受维数束缚的缺陷。 ( 3 ) 在分析了粒子群全局收敛能力的基础之上，针对粒子群算法局部收敛和搜 索精度低的问题，提出了一种全局的基于g a u s s i a n 变异的粒子群算法( g g p s o ) 该算法 结合了局部和全局变异因子使算法在全局和局部搜索能力中找到了一个很好的平衡，并 证明了它能以概率1 收敛到全局最优解。典型函数优化的仿真结果表明，该算法不仅可 有效的避免标准p s o 算法的早熟收敛，而且具有寻优能力强、搜索精度高、稳定性好等 优点。同时针对图像信息处理中的图象分割这一难点问题，以k a p u r 算法为优化目标， 摘要 验证了该算法克服了图象分割中寻优速度慢的缺点，与其他群体算法比较获得了更大的 适应度函数值。因此，该算法更适合于图像分割以及相关的函数优化问题。 ( 4 )在分析了粒子群收敛性的基础之上，针对粒子群( p s o ) 算法后期搜索能力下 降的问题，提出了一种基于适度随机搜索策略的粒子群算法( i r p s o ) 该方法在提高粒 子群算法收敛速度的前提下，有效的提高了粒子的全局搜索能力。另外，由于该方法只 有一个控制参数和迭代公式，因此更为简单易实现。典型函数优化的仿真结果表明，该 算法相对于比较算法来说获得了更好的性能。同时针对图像分割这一难点问题，以互信 息熵差为优化目标，验证了该算法在比较算法中获得了更好的分割效果。 论文最后对所做工作进行了总结，并提出了进一步研究的方向。 关键词：进化算法，粒子群算法，图像分割，收敛速度，全局搜索能力，维数约束， 蒙特卡罗方法 h a b s t r a c t 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 ) i sa l le v o l u t i o n a r yc o m p u t a t i o nt e c h n i q u ed e v e l o p e d b yd r e b e r h a r ta n dd r k e 皿e d yi n19 9 5 ，i n s p i r e db ys o c i a lb e h a v i o ro fb i r df l o c k i n go rf i s h s c h o o l i n g r e c e n t l y , p s oa l g o r i t h mh a sb e e ng r a d u a l l ya t t r a c t e dm o r ea t t e n t i o no v e ra n o t h e r i n t e l l i g e n ta l g o r i t h m p s o i s s i m p l e i n c o n c e p t ，f e w i n p a r a m e t e r s ，a n de a s y i n i m p l e m e n t a t i o n i tw a sp r o v e dt ob ea ne f f i c i e n tm e t h o dt os o l v eo p t i m i z a t i o np r o b l e m s ，a n d h a ss u c c e s s f u l l yb e e na p p l i e di nt h ea r e ao ff u n c t i o no p t i m i z a t i o n ，n e u r a ln e t w o r k t r a i n i n ga n d f u z z yc o n t r o ls y s t e m s ，e t c h o w e v e r , b o t ht h e o r ya n da p p l i c a t i o no fp s oa r es t i l lf 打f r o m m a t u r e ，n l ep a p e rg i v e sa c o m p r e h e n s i v es t u d yo np s o f r o mt h ea s p e c to f a l g o r i t h mm e c h a n i s m a l g o r i t h mm o d i f i c a t i o na n di t sa p p l i c a t i o n f u r t h e r m o r e ，i m a g es e g m e n t a t i o ni st h ef i r s ta n d f o r e m o s tp r o b l e mi ni m a g ea n a l y z i n ga n dm o d er e c o g n i t i o n ，a n di sa l s oat y p i c a ls t u m b l i n g b l o c ki ni m a g ep r o c e s s i n g i no r d e rt or a i s ei t ss p e e d ，w ec o m b i n e dt h em e t h o do fp s oa n d i m a g es e g m e n t a t i o na l g o r i t h mo nv a l v e sa n dt h e r e f o r ep r o p o s e ds e v e r a ls e g m e n t a t i o n a l g o r i t h m sb a s e do ni m p r o v e dp s o a sw ea c h i e v ea ne f f e c t i v es e g m e n t a t i o n ，w ea l s or a i s e d t h es p e e do ft h ep a r a l l e ls e a r c h i n gs y s t e m t h em a i nc o n t e n ti sa sf o l l o w s ： ( 1 ) t h ep a p e rs u r v e y sp s oa l g o r i t h ma n di t sb a s i ct h e o r i e s ( o p t i m i z a t i o nm e t h o da n d e v o l u t i o n a r yc o m p u t a t i o n ，e c ) f i r s tw es u m m a r i z et h eg e n e r a t i o na n dd e v e l o p m e n to f o p t i m i z a t i o nm e t h o di nd e t a i l ，a n de m p h a s i z et h eb a s i ci d e a ，r e s e a r c hf i e l da n da p p l i c a t i o n s a n dt h e nw ee x p a t i a t et h ee m e r g e n c e ，d e f i n i t i o na n dr e s e a r c hf i e l d ，a n ds o m et y p i c a le c m e t h o d s ，e g g e n e t i ca l g o r i t h m ，e v o l u t i o n a r ys t r a t e g y , d i f f e r e n t i a la l g o r i t h ma r ei n t r o d u c e d a tl a s tw ei n t r o d u c ep s oa l g o r i t h m ，i n c l u d i n gi t s o r i g i n a le d i t i o na n ds t a n d a r de d i t i o n , s u m m a r i z ei t st h e o r e t i c a la n d a p p l i e dr e s e a r c h m o n t ec a r l om e t h o di sp r e s e n t e dt o i n v e s t i g a t et h ea b i l i t yo fp a r t i c l e s t h er e s u l t sr e v e a lw h yt h ep s oh a sr e l a t i v ep o o rg l o b a l s e a r c h i n ga b i l i t yi nt h el a s ts t a g eo fi t e r a t i o n ，i ta l s og i v e st h ew a yh o wt oi m p r o v et h e c o n v e r g e n c er a t eo fp s o f u r t h e r m o r e ，n i n eb e n c h m a r kf u n c t i o n sa r eu s e dt o t e s tt h e p e r f o r m a n c eo fp s 0a n do t h e rp o p u l a re ca l g o r i t h m s t h er e s u l t ss h o wt h a tt h em e r i t so f p s oi nt e r m so ft h ef a s tc o n v e r g e n c er a t e ( 2 ) i ns p i t eo fp s oh a sc o m p a r a b l eo re v e ns u p e r i o rs e a r c hp e r f o r m a n c ef o rm a n yh a r d o p t i m i z a t i o np r o b l e m sw i t hf a s t e ra n dm o r es t a b l ec o n v e r g e n c er a t e s ，b u ti tc a n tg u a r a n t e et o f i n dt h eg l o b a lo p t i m ai nt h es e a r c hs p a c e s ot h eq u a n t u m - b e h a v e dp s o ( q p s o ) a l g o r i t h m w h i c hh a sp o w e rg l o b a ls e a r c h i n ga b i l i t yt h a np s oi si n t r o d u c e df o ri m p r o v i n gi nt h i sp a p e r b u tf o rq p s ou p d a t i n gt h ep o s i t i o no f p a r t i c l ea sw h o l e i t e mw h i c hl i k e sp s o ，i ta l s oh a st h e p r o b l e mo ft h ec u r s eo fd i m e n s i o n a l i t y h e n c et w on e wh y b r i dq p s 0a l g o r i t h m sw i t h c o o p e r a t i v em e t h o d ( c q p s oa n di c q p o ) i sp r o p o s e di nt h i sp a p e rf o rs o l v i n gt h i sp r o b l e m t h ec o o p e r a t i v em e t h o di ss p e c i f i c a l l ye m p l o y e dt oc o n q u e rt h e “c u r s eo f d i m e n s i o n a l i t y ”，b y s p l i t t i n gap a r t i c l ew i t hc o m p o s i t eh i g h - d i m e n s i o n a li n t os e v e r a lo n e - d i m e n s i o n a ls u b p a r t s n i n eb e n c h m a r kf u n c t i o n sa n dm a x i m i z a t i o no ft h em e a s u r eo fs e p a r a b i l i t yo nt h eb a s i so f b e t w e e n - c l a s sv a r i a n c em e t h o d ( o f t e nc a l l e do t s um e t h o d ) ，a p o p u l a rt h r e s h o l d i n g t e c h n i q u e i se m p l o y e dt oe v a l u a t et h ep e r f o r m a n c eo ft h ep r o p o s e dm e t h o d t h ee x p e r i m e n t i i i a b s t r a c t 一_ 一 r e s u l t ss h o w t h a t , c o m p a r e dw i t ht h ee x i t i n ge cm e t h o d s ，t h ec o o p e r a t i v em e t h o dh e l p st h e n e wp s oa l g o r i t h mt og e tm o r ee f f e c t i v ea n de f f i c i e n tr e s u l t s i ta l s oc o n q u e r st h ec u r s eo f d i m e n s i o no ft r a d i t i o n a lo t s um e t h o d ( 3 ) b a s e do na n a l y s i so ft h eg l o b a ls e a r c h i n ga b i l i t yo fp s o ，an e w g l o b a lg a m s i a np s o ( g g p s o ) i sp r o p o s e dt oo v e r c o m et h ep r o b l e mo ft h ep r e m a t u r ea n dl o wp r e c i s i o no ft h e s t a n d a r dp s o i nt h i sa l g o r i t h m ，c o m b i n i n gw i t hg l o b a la n dl o c a lm u t a t i n gm e t h o df i n d sa n e x c e l l e n tb a l a n c eb e t w e e ng l o b a ls e a r c h i n ga n dl o c a ls e a r c h i n g ，w h i c hi sa l s og u a r a n t e e dt o c o n v e r g et ot h eg l o b a lo p t i m i z a t i o ns o l u t i o nw i t hp r o b a b i l i t yo n e e x p e r i m e n ts i m u l a t i o n s s h o wt h a tt h ep r o p o s e da l g o r i t h mc a nn o to n l ya v o i dp r e m a t u r ee f f e c t i v e l yb u ta l s oh a s p o w e r f u lo p t i m i z i n ga b i l i t y , g o o ds t a b i l i t ya n dh i g h e ro p t i m i z i n gp r e c i s i o n f o rs o l v i n gi m a g e s e g m e n t a t i o nw h i c hi st h eg r e a ti m p o r t a n c ei nt h ef i e l do fi m a g ep r o c e s s i n g ，w eu s ek a p u r t u n c t i o na st h eo p t i m i z a t i o no b j e c t ，a n dt h ee x p e r i m e n t ss h o wt h a tt h eg g p s o a l g o r i t h m o u t p e r t b r m st h ec o m p a r e da l g o r i t h m se s p e c i a l l yi nm a x i m u mt h ef i t n e s sv a l u e s oi tc a n a p p l i e di ni m a g es e g m e n t a t i o na n do p t i m i z a t i o np r o b l e m sw e l l ( 4 、b a s e do na n a l y s i so ft h ec o n v e r g e n c eo fp a r t i c l es w a l t f lo p t i m i z a t i o n ( p s o ) an e w p s ob a s e do n i m p r o v e dm o d e r a t er a n d o ms e a r c h i n ga b i l i t y ( i r p s o ) i sp r o p o s e dt o o v e r c o m et h ep r o b l e mo fb a ds e a r c h i n ga b i l i t yi nt h el a s ts t a g eo ft h es t a n d a r dp s o i th e l p s t h ep a r t i c l e sh a v em o r ee x p l o r a t i o na b i l i t ya n df a s t c o n v e r g e n c er a t e f u r t h e r m o r e f o rt h e i m p r o v e da l g o r i t h mo n l yh a v i n go n ep a r a m e t e ra n di t e r a t i o nf o r m u l a , i ti ss i m p l e rt h a np s o e x p e r i m e n t ss h o wt h a tt h ep r o p o s e da l g o r i t h mp e r f o r m sm u c hb e t t e rt h a n t h eo t h e r a l g o r i t h m si nt e r m so ft h eq u a l i t yo fs o l u t i o n f o rs o l v i n gt h ep r o b l e mi ni m a g es e g m e n t a t i o n , w eu s et h ed i f f e r e n c eo fm u t u a li n f o r m a t i o n ( d m i ) a st h eo p t i m i z a t i o nf u n c t i o n a i l d t h e e x p e r t m e n t s s h o wt h a tt h ei r p s oa l g o r i t h m g e t s t h eb e t t e r p e r f o r m a n c e o fi m a g e s e g m e n t a t i o na m o n gt h ec o m p a r e da l g o r i t h m s f i n a l l y , t h ew o r ko ft h i sd i s s e r t a t i o n r e s e a r c hi sd i s c u s s e d i ss u m m a r i z e da n dt h ep r o s p e c t i v eo ff u t u r e k e y w o r d s ：e v o l u t i o n a r yc o m p u t a t i o n ，p a r t i c l es w a r l t la l g o r i t h m ，i m a g es e g m e n t a t i o n ， c o n v e r g e n c er a t e ，t h eg l o b a ls e a r c h i n ga b i l i t y , t h ec u r s eo fd i m e n s i o n ，m o n t ec a r l om e t h o d 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 签名：0 淫 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签。 名： q 三兰 导师签名： 日期： l 在乏tl 是 第一章绪论 第一章绪论 1 1 课题背景 1 1 1 最优化 最优化已经成为了一个使用非常广泛的术语，最优化的概念反映了人类实践活动中 十分普遍的现象。最优化是一个重要的数学分支，是一门应用性强、内容丰富的学科。 例如，工程设计中怎样选择设计参数，使得设计方案既满足设计要求又能降低成本；资 源分配中，怎样分配有限的资源，使得分配方案既能满足各方面的基本要求，又能获得 好的经济效益；生产计划安排中，选择怎样的计划方案才能提高产值和利润。在人类活 动的各个领域中，诸如此类，不胜枚举。这些问题在某种程度上都可以称为最优化问题。 最优化的目的是对于给出的实际问题，从可行的解决方案中找出最好或较好的解决方案 来，即要在尽可能节省人力、物力和时间的前提下，争取获得在可能范围内的最佳效果。 最优化问题可以追溯到十分古老的极值问题，早在1 7 世纪，英国科学家n e w t o n 发明微积分的时代，就已提出极值问题，后来又出现了l a g r a n g e 乘数法。1 8 4 7 年法国 数学家c a u c h y 研究了函数值沿什么方向下降最快的问题，提出了最速下降法。1 9 3 9 年 前苏联数家玎b kahtopobhq 提出了解决下料问题和运输问题这两种线性 规划问题的求解方法。人们关于最优化问题的研究工作，随着历史的发展不断深入。但 是，任何科学的进步都会受到历史条件的限制。直至2 0 世纪3 0 年代，最优化这个古 老的课题并未形成独立的系统学科。 2 0 世纪4 0 年代以来，随着生产活动和科学研究地不断发展，特别是计算机技术 的高速发展和广泛使用，使最优化问题的研究不仅成为一种迫切需要，而且有了求解的 有力工具。因此各种优化理论研究发展迅速，新方法不断出现，实际应用日益广泛。而 且在计算机技术的推动下，一些超大规模的优化问题也得以实现，最终使得优化理论与 方法在经济规划、工程设计、生产管理、交通运输等方面得到了广泛应用，成为- - f q 十 分活跃的学科l l j 。 一般来说，最优化问题可以表示为： m i n ，( z ) ，乩t 玩( z ) 0 i = 1 ，m ( z ) = 0 ，j = 1 ，z ( 1 1 1 1 ) z x 其中，z 冗”是决策变量，( z ) 为目标函数，x 为可行域，玩( z ) 、勺( z ) 为约束函 数，玩( z ) 称为不等式约束，乞( z ) 称为等式约束。 1 1 2 最优化方法 为了达到最优化的目标所提出的各种求解最优化问题的方法称为最优化方法。最优 化方法是一个以数学为基础的重要的科学分支，它一直受到人们的广泛重视，并在许多 江南大学博士学位论文 工程领域得到迅速推广和应用，如系统控制、人工智能、模式识别、生产调度、计算机 工程等。它对促进运筹学、管理科学、控制论和系统工程等新兴学科的发展起到了重要 的作用。 最优化方法在实践中的应用可以分为最优设计、最优计划、最优管理和最优控制等 四个方面【l 】。最优设计：在飞机、造船、机械、建筑等工程技术界都已广泛应用最优化 方法于设计中，从各种设计参数的优选到最佳结构形状的选取等，结合有限元方法已使 许多设计优化问题得到解决。电子线路的最优设计是另一个应用最优化方法的重要领 域。配方配比的优选方面在化工、橡胶、塑料等工业部门都得到成功的应用，并向计算机 辅助搜索最佳配方、配比方向发展。一个新的发展动向是最优设计和计算机辅助设计相 结合。最优计划：在编制国民经济和部门经济的计划和农业、交通、能源、环境、生态 规划中，在编制企业发展规划和年度生产计划中应用最优化方法的过程称之为最优计 划。一个重要的发展趋势是帮助决策部门进行各种优化决策。最优管理：在企业日常生 产计划的制订、生产经营的管理和运行中，通过计算机管理系统和决策支持系统等辅助 工具的建立和使用，运用最优化方法进行经营管理的过程称为最优管理。在经济管理学 上就是在一定人力、物力和财力资源条件下，使经济效果( 如产值、利润等) 达到最大， 并使投入的人力和物力达到最小的科学方法。最优控制：主要用于对各种控制系统的优 化。例如，导弹系统、卫星系统、航天飞机系统、电力系统等高度复杂系统中运用最优 化方法。计算机接口装置不断完善和优化方法的进一步发展，还为计算机在线生产控制 创造了有利条件。最优控制的对象也将从对机械、电气、化工等系统的控制转向对生态、 环境以至社会经济系统的控制。 求解最优化问题的最优化方法有多种形式。不同类型的最优化问题可以有不同的最 优化方法，同一类型的最优化问题也可有多种最优化方法。某些最优化方法可适用于不 同类型的最优化问题，针对相同的最优化问题，不同的最优化方法具有不| 一的优化特性。 有些最优化方法可以快速求解到局部最优解，有些优化方法具有很好的全局寻优特性。 一般来说，求解最优化问题的理想情况是快速有效的得到全局最优解。当然，由于对最 优化问题的性质和最优化方法认识的不足，这种情况只能在有限的条件下实现。对于复 杂函数最优化问题，一般很难找到收敛性好且全局最优的最优化方法。 一般来说，求解最优化问题可以分为以下几个步骤： ( 1 ) 提出需要进行优化的问题； ( 2 ) 建立求解优化问题的有关数学模型，确定变量，列出目标函数和有关约束条件； ( 3 ) 分析模型，选择合适的最优化方法； ( 4 ) 求解方程； ( 5 ) 最优解的验证和实施。 显然，在最优化问题的数学模型建立后，主要问题是如何通过不i 一的求解方法解决 寻优问题。最优化问题的数学求解方法一般可以分成解析法、直接法、数值计算法等几 类【2 ，3 】： 2 第一章绪论 解析法：对于目标函数及约束条件有简单而明确的解析表达式的非线性优化问题， 通常可采用解析法来求解。解析法的求解方法是先按照函数极值的必要条件，用数学分 析的方法( 求导或变分法) 求出其解析解，然后按照充分条件或问题的实际物理意义间 接地确定最优解，因此也称间接法。这类方法主要用来解决动态优化问题。其中经典变 分法用来求解无约束动态优化问题；极大( 极小) 值原理和动态规划主要用于求解有约 束的动态优化问题。另外，经典微分法可用于求解静态优化问题。 直接法：当目标函数较为复杂或者不能用变量显函数描述或无法用解析法求必要条 件时通常可采用直接法来解决。直接法的基本思想是用直接搜索的方法经过一系列的迭 代以产生点的序列，使之逐步接近到最优点。这种方法常常是根据经验或通过试验得到 所需要的结果，直接法可以分为函数逼近法、区间消去法和爬山法。对于一维搜索( 单 变量极值问题) ，主要用消去法或多项式插值法，对于多维搜索问题( 多变量极值问题) 主要用爬山法。 数值计算法：这种方法也是一种直接法，是以梯度法为基础的。它是一种解析与数 值计算相结合的方法。这类方法主要用于多变量的寻优问题。其中最速下降法、共轭梯 度法、牛顿法与拟牛顿法、变尺度法和牛顿高斯最小二乘法等适用于多变量无约束的 优化问题。解决多变量约束的优化问题通常也采用以解析法为基础的数值解法，这类方 法很多，大致可分为以下三种类型：一是将有约束的优化问题转化为系列无约束的优 化问题，然后采用无约束优化方法来求解，这种方法称为变换算法或序列无约束极小化 方法，如拉格朗日乘子法和惩罚函数法；二是采用一系列线性或二次规划问题的解来逼 近原非线性约束问题的解，这种方法称为线性近似化技术，如序列线性规划化、割平面 法和序列二次规划化；三是直接处理约束条件，研究在约束边界处如何搜索以获得使目 标函数值逐步改善的可行点列，最后趋近约束问题的极小值点，这种方法称为可行方向 法、梯度投影法和简约梯度法。 用数学方法求解优化问题的历史相对悠久，当前仍然在不断的发展过程中。这些传 统的方法大多是针对某些特定问题的，并且对搜索空间要求相对严格，有些方法还需要 使用被优化函数的各阶导数信息。但是，随着科学技术的发展，优化问题也变得更加复 杂。如工程优化所建立的数学函数，往往是带有多种约束条件的复杂函数，而且大部分是 不连续、不可微的隐函数。对于这些复杂函数来说，用常规的数学方法很难或根本无法处 理。有些问题甚至无法用函数关系来表达，对于这类问题，采用上述方法，不可能得到 圆满的结果。因此，需要进一步研究和探索新的优化思想和优化方法。 1 1 3 基于进化计算求解最优化问题的方法 承上所述，随着科学技术的发展，实际的优化问题也变得越来越复杂。优化问题表 现出了复杂性、约束性、非线性、多极小、建模困难等特点，因此常规的求解方法已很 难适用，寻求一些新的优化技术成为一个重要研究目标和引人注目的研究方向。 2 0 世纪8 0 年代以来，进化计算作为一类通过模拟生物进化过程与机制来求解问 题的优化技术，为解决复杂优化问题提供了新的思路和方法，近年来受到了人们极大关 注。进化计算采用简单的编码技术来表示各种复杂的结构，并通过对一组编码进行简单 江南大学博士学位论文 的进化操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。由于采用种群的方式 组织搜索，这使得进化计算可以同时搜索解空间的多个区域，而且用种群组织搜索的方 式也使得进化计算特别适合大规模并行操作。在赋予进化计算自组织、自适应、自学习 等特征的同时，优胜劣汰的自然选择和简单的进化操作使进化计算具有不受其搜索空间 限制条件( 如可微、连续、单峰) 的约束及不需要其它辅助信g ( 如导数) 的特点。 基于进化计算求解优化问题的一般步骤为： ( 1 ) 随机给定一组初始解； ( 2 ) 评价当前这组解的性能； ( 3 ) 按照一定的方法选出性能优良的解作为进化操作对象； ( 4 ) 对选出的解进行进化操作( 如交叉、变异等) 得到新一代解； ( 5 ) 评价当前新一代解的性能，如果满足要求或进化过程达到定代数，过程 结束，否则转到( 3 ) 。 对于复杂优化问题的求解，进化计算有实用性、通用性、灵活性强、效率高等特点， 能在更多的情况下求得有用的( 即近似的、次优的和在精度许可范围内的) 解。与传统数 学方法相比，基于进化计算方法有如下特点【4 j ： ( 1 ) 进化计算的处理对象可以是参数本身，也可以是经过某种映射形成的特定编码， 编码形式可以是矩阵、树、图、集合、串、序列、链和表等。这个特点使进化计算有广 泛的应用领域，尤其是对多目标、大规模、高维数、非线性以及带有不可转化约束条件 的复杂优化问题，具有更强的适应性。 ( 2 ) 进化计算通过策略、参数、操作以及算子的调整，能够很快提高寻优求解的性 能，更重要的是进化计算能够通过自身的改良以及同其它方法的交叉融合，在较短的时 间内快速进化，这一点体现了进化计算的灵活性。 ( 3 ) 进化计算采用群体搜索策略，而传统方法多采用单点搜索策略，这种特点使进 化计算具有极好的全局性，减少陷入局部最优的风险；i 司时，也使进化计算本身易于大 规模并行实现，可充分发挥高性能计算机系统的作用。 ( 4 ) 进化计算具有高效的特点，不是说在拥有同等计算资源时，求解优化问题肯定 都比传统方法快( 从整体上讲，在近年来多数工程应用中的效率确实高出传统算法，否 则，进化计算的发展速度也不会突飞猛进) ，更多的是指能够更充分挖掘计算机的潜力， 比如容易实现并行寻优求解( 通过占用更多的冗余计算资源来实现速度的提高) 。 ( 5 ) 进化计算基本不依赖搜索空间的知识及其他辅助信息，它采用适应度函数来评 价个体，并在此基础上驱动进化过程，而对适应度函数本身无特别严格要求。而传统方 法则要求函数有诸如连续、可微或空间凸性等条件。这使进化计算有更广泛的应用范围。 ( 6 ) 进化计算用概率的变迁规则来控制搜索的方向，表面上看好像是在盲目搜索， 实际上它遵守某种随机概率，在概率意义上朝最优解方向靠近，因此，它不像通常采用 确定性规则的传统方法，需要构造合适的下降方向。 二十世纪七十年代以来，一些与经典优化方法不同的的进化计算方法相继被提出， 其中包括遗传算法【5 ，6 1 、蚁群算法【7 】、粒子群算法【3 9 1 以及微分进化算澍i o , l q 。其中粒子群 4 第一章绪论 算法是近年来提出的一种简单而高效的进化算法。由于它容易理解、易于实现，所以发 展十分迅速，在很多领域得到了成功应用。由于图像分割是图像分析和模式识别的首要 问题，也是图像处理的经典难题之一，它是图像分析和模式识别系统的重要组成部分， 并决定图像的最终分析质量和模式识别的判别结果。因此本文针对基于p s o 的图像分 割算法进行了研究，提出了多个新的解决这类优化问题的算法。 1 2 课题的目标和意义 粒子群优化算法有些与遗传算法相似，如它们都是基于群体的优化技术，有较强的 并行性无需梯度信息，只需利用目标的取值信息，具有很强的通用性。但是，粒子群算 法比遗传算法更简单、操作更方便。因而，粒子群算法从诞生起，就引起了国内外学者 的广泛关注，掀起了该方法的研究热潮，己经广泛应用于函数优化、神经网络训练、模 糊系统控制【1 2 】等领域。近年来进化算法已成为分布式人工智能研究的一个重要领域，在 美国成立有专门的组织研究群体的仿真；由欧洲联盟资助的进化算法相关研究项目也于 2 0 0 1 年在欧洲多个研究机构启动；在国内，国家自然科学基金“十五”期间学科交叉 类优先资助领域中，认知科学及其信息处理的研究内容就明确列出了群体智能的进化、 自适应与现场认知、相关项目以及复杂系统与复杂性。它的主要研究方向及内容是复杂 系统与复杂性的理论与方法研究；物质层次复杂系统的研究；生命层次复杂系统的研究： 社会层次复杂系统的研究。2 0 0 1 年3 月8 日在北京召开的第六届全国人工智能联合会 议暨“8 6 3 计划智能计算机主题学术会议，戴汝为院士特邀报告的主要内容就是进化 算法的研究进展。到现在，国家自然科学基金委员会每年都有资助数项粒子群优化算法 相关理论和应用的研究。 国际上，每年召开的顶级国际会议中以进化算法为主题的会议主要有美国计算机协 会( a s s o c i a t i o no f c o m p u t i n gm a c h i n e r y ) 每年举行的基因与进化计算国际会议( g e n e t i c a n de v o l u t i o n a r yc o m p u t a t i o nc o n f e r e n c e s ) ，i e e e 计算智能协会( i e e ec o m p u t a t i o n a l i n t e l l i g e n c es o c i e t y ) 每年举行一次的进化计算国际会议( i e e ec o n f e r e n c eo ne v o l u t i o n a r y c o m p u t a t i o n ) 以及自2 0 0 3 年起每年举行一次群体智能会议( i e e es w a r mi n t e l l i g e n c e s y m p o s i u m ) 。其中粒子群优化算法是这些会议的重要主题。 p s o 自1 9 9 5 年提出以来，由于其简单和明确的实际背景，以及前述的诸多优点， 使得很多研究者加入到对这种算法的研究中，目前粒子群优化算法的理论研究与应用研 究都取得了很大的进展，对于算法的原理已经有了初步的了解，算法的应用也已经在不 同学科中得以实现。这些研究主要集中在如下几个方面： ( 1 ) 粒子群优化算法的理论分析 具体来说，这个问题的研究分为三个方面：一是单个粒子的运动轨迹，现有的研究 发现，单个粒子不断的在各种正弦波上“跳跃”，即其轨迹是各种正弦波的随机的叠加 组合，这里所用的主要工具是微分方程和差分方程【1 2 】；二是收敛性问题，关于粒子群算 法的收敛性研究比较多的集中在一些简化条件下的结果，采用的主要工具是动态系统理 论。其它还有采用集合论的方法来研究此问题，得出的结论是【i3 】：在没有任何改进的情 江南大学博士学位论文 况下，原始的粒子群优化算法既不能收敛到全局极值点，也不能收敛到局部极值点，但 是这种证明是非构造性证明，对于理解算法的工作原理没有太大帮助。三是整个粒子系 统随时间的演化和分布，这方面的研究目前还少有人涉及。 ( 2 ) 粒子群优化算法的改进 这方面的内容非常庞杂，从改进的