（系统工程专业论文）基于离散二进制PSO算法的专家选择系统.pdf

基于离散二进制p s o 算法的专家选择系统 摘要 自上世纪8 0 年代以来，智能优化算法( 如人工神经网络、混沌算法、遗传算法等) 通过模拟或揭示某些自然现象和过程而发展起来，为优化理论提供了新的思路和手段， 并在科学、经济以及工程领域得到了广泛应用。粒子群优化算法是一种基于种群搜索策 略的自适应随机算法。作为智能优化算法中的一种，它可用于求解大部分的优化问题， 并在工程实践中表现出巨大潜力，现已广泛应用于神经网络、模糊系统控制、模式识别 等多个领域。 本文在对该算法及其应用进行全面综述的基础上，重点进行了离散二进制p s o 算 法的研究，并将微粒群算法应用于专家选择系统中。本文的研究目的：一方面是探索和完 善离散二进制p s o 算法模型，使之能更有效的解决传统方法难以解决的问题；另一方面 拓展离散二进制p s o 算法的应用领域，使之能够解决更多的工程实践问题。 基于这种方法，针对大型实际项目“辽宁省科学技术基金管理系统”所面临的实际 问题，创造性的提出一整套针对此系统在其外挂专家池中进行专家选择的算法，并完成 了相应系统的设计与实现。 本文采用概念性研究、实际数据测试、数理证明等主要论证手段。本文算法以及系 统设计是针对这一类问题的一种新的思考方式和尝试性的解决方案。对于今后此类算法 的构建以及类似系统的实现，具有一定的借鉴作用。 关键词：离散二进制p $ o 模型：专家选择；微粒群算法 基于离散二迸制p s o 算法的专家选择系统 a b s t r a c t f r o mt h e1 9 8 0 s ，i n t e l l i g e n to p t i m i z a t i o na l g o r i t h ms u c ha sn e u r a ln e t w o r k , o a , c h a o s h a sb e e nd e v e l o p e dt h r o u g ht h es i m u l a t i o no f n a t u r ea n ds o c i a lp r o c e s sa n di tp r e s e n t san e w a p p m a c hf o ro p t i m i z a t i o nm e t h o d s p a r t i c l es w a r mo p t i m i z a t i o ni s ap o p u l a t i o n - b a s e d , s e l f - a d a p t i v es e a r c ho p f i m i z a t i o nt e c h n i q u e a sak i n do f i n t e l l i g e n ta l g o r i t h m , i tc a nb eu s e d t os o l v ev a r i o u so p t i m i z a t i o np r o b l e m sa n ds h o w sg r e a tp o t e n t i a li np r a c t i c e n o w ，i th a sb e e n w i d e l ya p p l i e di nm a n yo t h e ra r e & 8 ，s u c ha sa r t i f i c i a ln e u r a ln e t w o r ka n df u z z ys y s t e m c o n t r 0 1 o nt h eb a s i so fs y s t e m a t i c a ls u m m a r yo fp s oa l g o r i t h ma n di t sa p p l i c a t i o n , t h ea r t i c l e m a i n l yp r o c e e d i n g0 - 1p s om o d e lr e s e a r c ho na n da p p l y i n gi tt o t h es y s t e mo fc h o o s i n g e x p e r t so p t i m i z a t i o n t h eg o a lo ft h i s d i s s e r t a t i o ni st oe x p l o r ea n df u r t h e r 0 - 1s w a m l i n t e l l i g e n c em o d e l s ，w h i c hm a k e si te a s yt os o l v el a r g e s c a l ec o m p l i c a t e dp r o b l e m s o nt h e o t h e rh a n d ，t h i st h e s i se x t e n d st h ea p p l i c a t i o nd o m a i n so f0 - 1s w a r mi n t e l l i g e n c em o d e la n d c o p e sw i t hm o r ep r a c t i c a le n g i n e e r i n gp r o b l e m s o nt h eg r o u n do ft h ei d e aa n da i m e da tt h er e a l 州c c t - m em a n a g e m e n ts y s t e m so f s c i e n c ea n dt e c h n o l o g yf u n do fl i a o n i n gp r o v i n c e , t h i sw o r kc r e a t i v e l yp r o p o s e saw h o l e s e to fg e n e t i ca l g o r i t h m s ，a n db u i l d su pt h ec o r r e s p o n d i n gs y s t e m 一c b o o s 吨e x p e r t s s y s t e m t h i sw o r ke m p l o y sc o n c e p t i o n a lr e s e a r c h , r e a ld a t at e s t , a n dm a t h e m a t i c a lp r o v i n ga s c o r em e t h o d s a l s o t h ea l g o r i t h m si nt h et e x ta r e 舶s hc o n s i d e r a t i o na b o u ts u c hi s s u e s ，a n d m a ye n l i g h t e nf o l l o w i n g r e s e a r c h e s k e yw o r d s ：0 - 1p s oh o d e i ：o h o o s i n ge x p e r t s ；p a r t i c l es w a r mo p t i m i z a t i o n 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均己在论文中做了明确的说明并表示了谢意。 作者签名：矬日期： 竺2 ：! ：堡 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理1 ：大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名：三嘲整作者签名：翌7 训噩秒 导师签名： 耄延毛 2 旦年月里日 基于离散二进制p s o 算法的专家选择系统 1 引言 1 1 群体智能 群体智能的概念源于对蜜蜂、蚂蚁、大雁等这类群居生物群体行为的观察和研究而 得到的，通常将这样一种从群居性生物中产生出来的集体智能行为称为群体智能。严格 来讲，群体智能是一种在自然界生物群体所表现出的智能现象启发下提出的人工智能模 式，是对简单生物群体的涌现现象的具体模式研究，即“简单智能的主体通过合作表现 出复杂智能行为的特性川”1 。该种智能模式需要以相当数目的智能个体来实现对某类问 题的求解功能。作为智能个体本身，在没有得到智能群体的总体信息反馈时，它在解空 间中的行进方式完全是没有规律的。只有受到整个智能群体在解空间中行进效果的影响 之后，智能个体在解空间中才能体现出具有合理寻优特征的行进模式。 最早关于群体智能的研究是c r a i gr e y n o l d s 0 1 在1 9 8 6 年提出一个用于模拟鸟类聚集 飞行行为的仿真模型b o i d ，通过对现实世界中这些群体运动的观察在计算机中复制重建 这些运动轨迹，并对这些运动进行抽象建模以发现新的运动模式。1 9 9 9 年由牛津大学出 版社出版的e b o n a b e a u 和m d o r i g o 等人编写的专著群体智能：从自然到人工系统 ( s w a r mi n t e l l i g e n c e ：f r o mn a t u r a lt oa r t i f i c i a ls y s t e m ) 和2 0 0 1 年出版的j a m e s k e n n e d y 与r u s s e l le b e r h a r t 合著的群体智能( s w a r mi n t e l l i g e n c e ) 将“群体智能” 概念的影响不断扩大。 m i l l o n a s 在1 9 9 4 年提出了群体智能应该遵循的五条基本原则嘲： ( 1 ) 邻近原则( p r o x i m i t yp r i n c i p l e ) ：群体能够进行简单的空间和时间计算； ( 2 ) 品质原则( q u a l i t yp r i n c i p l e ) ：群体能够响应环境中的品质因子； ( 3 ) 多样性反应原则( p r i n c i p l eo fd i v e r s er e s p o n s e ) ：群体的行动范围不应该太 窄； ( 4 ) 定性原则( s t a b i l i t yp r i n c i p l e ) ：群体不应在每次环境变化时都改变自身的行 为； ( 5 ) 适应性原则( a d a p t a b i l i t yp r i n c i p l e ) ：在能够接受的计算代价内，群体必须能 够在适当的时候改变自身的行为。 以上原则说明，实现群体智能的智能个体必须能够在环境中表现出自主性、反应性、 学习性和自适应性等智能特性。但是，这并不代表群体中的每个个体都相当复杂，事实 恰恰与此相反。群体智能的核心就是，由众多简单个体组成的群体能够通过相互之间的 简单合作来实现某一功能，完成某一任务。其中，“简单个体”是指单个个体只具有简 基于离散二进制p s o 算法的专家选择系统 单的能力或智能，而“简单合作”是指个体和与其邻近的个体进行某种简单的直接通讯 或通过改变环境间接与其它个体通讯，从而可以相互影响、协同动作。 群体智能具有以下特点m ，： ( 1 ) 群体中相互合作的个体是分布式的，不存在中心控制。因而它更能够适应当前 网络环境下的工作状态，并且具有较强的鲁棒性，即不会由于某一个或几个个体出现故 障而影响群体对整个问题的求解； ( 2 ) 每个个体只能感知局部信息，不能直接拥有全局信息；并且群体中每个个体的 能力或遵循的行为规则非常简单，因而群体智能的实现比较方便，具有简单性的特点； ( 3 ) 个体之间通过非直接通信的方式进行合作。由于群体智能可以通过非直接通讯 的方式进行信息的传输与合作，因而随着个体数目的增加，通讯开销的增幅较小，也就 是说，它具有较好的可扩充性； ( 4 ) 自组织，即群体表现出来的复杂行为是通过简单个体的交互而突现出来的智能 ( e m e r g e n ti n t e l l i g e n c e ) 。 目前，对群体智能的研究尚处于初级阶段，但是由于其具有分布式、自组织、协作 性、鲁棒性和实现简单方便等特点，使之在没有全局信息的情况下，为寻找复杂问题的 解决方案提供了快速可靠的基础，为系统复杂性以及n p 问题等方面，为人工智能、认知 科学等领域的基础理论问题的研究开辟了新的研究途径，同时也为诸如优化问题求解、 工业动态生产控制问题、工程设计优化、数据挖掘、神经网络训练、机器人协作控制与 路径规划、通信网络管理和路由控制、电力系统优化、生物医学分析、交通路径规划以 及系统辨识与参数估计等实际工程问题提供了新的解决方法”1 ”。因此，群体智能的研 究具有重要意义和广阔的应用前景，它也越来越受到国际智能计算研究领域学者的关 注，逐渐成为一个新的重要的研究方向“。 日前，群体智能有两种典型的算法实现模式：蚁群优化算法“”( a n tc o l o n y o p t i m i z a t i o n ，a c o ) 和微粒群优化算法“”1 ( p a r t i c l es w a r m0 p t i m i z a t i o n ，p s o ) 。本 文的研究对象是微粒群优化算法( 以下简称为“微粒群算法”或“p s o 算法”) 。 1 2 微粒群算法 1 。2 1 微粒群算法的起源 微粒群算法最初是为了图形化地模拟鸟群优美而不可预测的运动。自然界中，鸟群 运动的主体是离散的，其排列看起来是随机的，但整体的运动却使它们保持着惊人的同 步性，整体运动非常流畅而极富美感。这些呈分布状态的群体表现出的似乎是有意识的 集中控制，一直是许多研究者感兴趣的问题。研究者对鸟群的运动进行了计算机仿真， 基于离散二进制p s o 算法的专家选择系统 他们通过对个体设定简单的运动规则，来模拟鸟群整体的复杂行为。例如，1 9 8 6 年c r a i g r e y n o l d s 提出了b o i d 模型用以模拟鸟类聚集飞行的行为，通过对现实世界中这些群体运 动的观察在计算机中复制重建这些运动轨迹，并对这些运动进行抽象建模以发现新的运 动模式。之后，生物学家f r a n kh e p p n e r 在此基础上增加了栖息地对鸟进行吸引的条件， 提出了新的鸟群模型。 上述模型关键在于对个体间距离的操作，即群体行为的同步性在于个体努力维持自 身与邻居之间的距离为最优，为此每个个体必须知道自身位置和邻居的信息。生物社会 学家w i l s o ne 0 认为伽“至少从理论上，在搜索食物的过程中群体中的个体成员可以 得益于所有其他成员的发现和先前的经历。当食物源不可预测地零星分布时，这种协作 带来的优势是决定性的，远大于对食物的竞争带来的劣势。”以上两例说明，群体中个 体之间信息的社会共享有助于进化。 受上述鸟群运动模型的影响，社会心理学博士j a m e sk e n n e d y 和电子工程学博士 r u s s e l le b e r h a r t 于1 9 9 5 年提出了微粒群算法。微粒群算法是一种演化计算技术，算法 中，将鸟群运动模型中的栖息地类比于所求问题解空间中可能解的位置，通过个体间的 信息传递，导引整个群体向可能解的方向移动，增加发现较好解的可能性。群体中的鸟 被抽象为没有质量和体积的“微粒”，通过这些“微粒”的相互协作和信息共享，其运 动速度受到自身和群体的历史运动状态信息影响，以自身和群体的历史最优位置来对微 粒当前的运动方向和运动速度加以影响，较好地协调微粒本身和群体运动之间的关系， 在复杂的解空间寻找最优解。 1 2 2 微粒群算法的发展 微粒群算法自提出以来，已经历了许多变形和改进。包括数学家、工程师、物理学 家、生物化学家以及心理学家在内的研究者对它进行分析和实验。大量的研究成果与经 验为微粒群算法的发展提供假设和基础，并为实际的工业应用指引了新的方向。 到目前为止，国内外的研究者对微粒群算法的研究与发展，可以归纳为以下几个方 面： ( 1 ) 参数选择与设计：在微粒群算法中存在几个显参数和隐参数，它们的值可被调 整，以产生算法搜索问题空间的方式的变化。研究者发现，这些参数的调整将控制诸如 收敛和爆炸之类的重要行为，因此可以通过调整不同显参数和隐参数的重要性来最优化 算法的性能。在之后的研究中，得到了经验的最佳参数配置，并对某些特定的现象进行 了解释。这些微粒群算法的研究基础，为微粒群算法的发展提供了可靠的依据。 基于离散二进制p s o 算法的专家选择系统 此外，研究者对基本参数进行了一定的扩展，提出了如带惯性权重和收敛因子的微 粒群算法；考虑到其中某些参数的调整模式，提出了自适应调整v 、的算法和用模糊规 则动态调整w 的算法等，实现了对参数的自适应动态调整，大大优化了算法的寻优性能。 ( 2 ) 种群拓扑结构：从1 9 世纪4 0 年代起的研究已经表明，组内的交流及最终组的性能 要受社会网络结构的影响。于是，微粒群研究者提出了几种简单的社会结构，并对几种 种群结构模型进行了分析与比较。全局最优模型( g b e s t ) 和局部最优模型( l b e s t ) 是最常 见的两种类型。 ( 3 ) 群体组织与进化：社会心理学研究表明，人们的态度、信仰和行为倾向于朝同伴 的方向变化，他们会根据自己所处群体的规范选择自己的意见和行为，即人们通常模拟 所在群体的典型行为和信仰，而不一定是某个特定个体的行为。受此启发，提出用簇来 表示群体中的子种群，用簇中心代替最优值的算法模式。此外，为了保证群体的多样性， 研究者将变异，繁殖和差异进化等思想引入微粒群，此外，还可以通过采用竞赛选择方 法、微粒替换操作、空间邻域法以及引入子种群的方法来实现并提出了很多改进算法 模式。 ( 4 ) 混合微粒群算法：将进化计算中的选择、交叉和变异等特性、混沌、免疫系统的 免疫信息处理机制以及热力学中熵的概念等与微粒群算法中的寻优机制相结合，提出了 相应的混合算法，如进化微粒群算法、高斯变异微粒群算法、免疫微粒群算法和耗散微 粒群算法等，有效地增强了算法的收敛特性。 ( 5 ) 离散微粒群算法：微粒群算法最初是用来对连续函数进行优化的。而实际中许多 问题是组合优化问题，因此，k e n n e d y 和e b e r h a r t 博士在基本算法的基础上提出了一种 离散二进制决策模型。在二进制空间中，微粒的移动是通过翻转位值实现的，而微粒的 速度描述了每次迭代改变的位数，或某微粒在t 和t + l 时刻的取值之间的海明距离。此外， 根据要解决的实际问题，有研究者提出了相应的离散微粒群算法模式。 1 2 3 微粒群算法的应用 微粒群算法自从提出之后，由于其概念简明、实现方便，在短期内迅速得到了国际 演化计算研究领域的认可，并且由于其在解决复杂的组合优化类问题方面所具有的优越 性能，微粒群算法在工程设计与优化、电力系统领域、机器人控制和工业生产优化领域 等取得了较为成功的应用。随着研究的不断深入，微粒群算法将会应用到越来越多的领 域中。 在工程设计优化方面，微粒群算法被用于进化神经网络、模糊神经元网络规则的提 取、电路设计、数字滤波器设计、半导体器件综合以及布局优化等方面。在电力系统领 一4 一 基于离散二进制p s o 算法的专家选择系统 域，微粒群算法用于实现电能优化、电压控制、提高电站可靠性以及电容器优化配置问 题等。在机器人控制中，微粒群算法用于机器人振动抑制轨迹规划以及移动机器人路径 规划等。在工业生产领域，微粒群算法用于原料混合优化和计算机控制研磨优化等。此 外，微粒群算法还用于交通导航与路径规划的动态规划问题、通信中的路由规划和基站 布置与优化问题、任务分配问题、模式识别、图像处理、数据挖掘、控制器参数优化以 及系统辨识与状态估计等。 2 微粒群优化算法介绍 微粒群算法的思想来自于社会认知理论( s o c i o c o n g n i t i v e ) 。根据社会认知理论： 我们可以将微粒群算法的问题求解概括为以下三个过程：评价、比较和模仿( k e n n e d y ) 【2 1 - 2 2 l ： 评价过程是对各种激励进行评估。根据正反馈或负反馈、吸引或排斥等激励特性对 其进行排序。在自然界中这是普遍存在的一种行为特征。有机生命只有通过对外界激励 的评价，才能够完成对环境的学习。微粒群对环境的自适应学习过程也包含了这样一种 评价过程。 比较过程是指微粒群中的个体对其他个体标准进行测量，并与自身条件相比较，从 而确立自身学习和修正的动机。 模仿过程是微粒群中的个体依据自身判断模拟其他个体行为的过程，这是自然界中 普遍存在的一种非常有效的学习模式。通常只模拟那些由于自身的个体。 上述三个过程的有机结合即可构成一种能够适应复杂环境变化，解决困难问题的简 单社会个体，并以计算机程序的形式实现。 2 1 原始微粒群算法 2 1 1 微粒群算法原理 微粒群算法( p s o ) 是由k m n e d v 和e b e r h a r t 等于1 9 9 5 年开发的一种演化计算技术 1 7 j ，其基本思想来源于对鸟群简化社会模型的研究及行为模拟。微粒群算法与其他演化 算法相似，也是根据对环境的适应度将群体中的个体移动到好的区域，不同之处在于它 不像其他演化算法那样对个体使用演化算子，而是将每个个体看作寻优空间中的一个没 有质量没有体积的微粒。在搜索空间中以一定的速度飞行，通过对环境的学习与适应， 根据个体与群体的飞行经验的综合分析来动态调整飞行速度。 在整个寻优过程中，每个微粒的适应值( f i t n e s sv a l u e ) 取决于所选择的优化的 函数的值，并且每个微粒具有以下几类信息：微粒当前所处位置；到目前为止由自己发 基于离散二进制p s o 算法的专家选择系统 现的最好位置( p 。) ，将信息视为微粒的自身飞行经验和目前为止整个群体中所有微 粒发现的最好位置( g 。) ( g 。是在p 。中的最好值) ，视为微粒群的同伴共享飞行 经验。于是，微粒根据其运动速度受到自身和群体的历史运动状态信息影响，以自身和 群体的历史最优位置来对微粒当前的运动方向和运动速度加以影响，很好地协调了微粒 自身运动和群体运动之间的关系。 2 1 2 微粒群算法描述 微粒群算法是一种基于迭代的优化算法，最初用于连续空间的优化，在连续空间坐 标系中，微粒群算法数学描述如下： 设微粒群体规模为，其中每个微粒在d 维空间中的坐标位置可表示为 x t = ( 勤，勘，a ，妇，a 工。) ，微粒f ( i = 1 n ) 的速度定义为每次迭代微粒移动的距离， 用k = l ，吩2 ，a ，a ) 表示。于是，在微粒f ( f = 1 ) 在d ( d = 1 d ) 维子空间中的 飞行速度根据下式进行调整： v i d = w v d + c l r a n d i o ( p 甜一j ) + c 2 r a n d 2 0 ( p 硝一工d ) ( 2 1 a ) 矿 v 一 矿v “ 4 ，通常取伊为4 1 ，则 1 2 一妒一、，伊2 4 妒l z = o 7 2 9 。实验结果表明，与使用惯性权重的微粒群算法相比，使用收敛因子的微粒 群算法有更快的收敛速度。其实质要恰当的选取w 、q 和c ，的值，两种算法是一样的， 因此带收敛因子的微粒群算法可被看作带惯性权重的算法的一个特例。同时这也说明， 恰当地选择算法的参数值可以改善算法的性能。 柯晶等嘶1 提出一种改进微粒群算法，该算法同时采用局部模式压缩因子方法和全局 模式惯性权重方法已获得相对较高的性能，同时针对p s o 算法可能出现的停滞现象， 引入了基于全局信息反馈的重新初始化机制。 2 1 5 3 对v 一的动态调整 在算法初期，往往需要加大的步幅，随着搜索的进行，需要将步幅逐渐减小。惯性 权重w 可以实现这一目标。如果直接对速度进行动态限制，也可以实现对步幅的调节。 h u i y u a n f a n ”1 提出了一种用限速来调整步幅的改进算法。在这种微粒群算法的改进模式 中，其飞行速度是按下式决定的： v 讲= w v d + e l r a n d l o ( p d - - x d ) + c 2 r a n d 2 0 ( p 耐一x d ) ( 2 7 a ) 广v d = ( 1 一( t t ) 。) v 。i f ( 1 一( t t ) ) v j i v d = 一( 1 一( t t ) 。) v 。矿v “ 一( 1 一( t t ) ) v 一 ( 2 7 b ) 这种算法模式相当于在基本算法模式中对v 。的动态调整，本质上也是对惯性权重 w 进行非线性自适应调整，实验证明算法具有较好的寻优效果。 2 1 5 4 具有空间特性的微粒群 如果将微粒赋予一定的半径，则微粒便具有了一定的空间特性。将该空间特性作为 算法的参数扩展，因此，此类算法可归结为参数的选择与控制研究。 t h i e m o 等。”提出一种空间扩展微粒群算法( s e p s o ) ，算法中假设微粒是具有一定 体积的球体，并且在聚集时会发生碰撞现象，每个微粒赋一半径值，并用于检测两个微 基于离散二进制p s o 算法的专家选择系统 粒是否会碰撞，如果会，则采用弹离策略使它们分离。算法给出三种弹离策略：随机弹 离、实际物力弹离和速度直线弹离，在实验中采用了直线弹离策略，即碰撞发生后，微 粒沿原速度方向做直线运动，并将速度值乘以弹跳因子。弹跳因子可为正也可为负，表 明弹离速度可与原速度同向也可反向；弹跳因子可小于1 也可大工或等于1 ，表明微 粒在弹离后可以加速也可减速。对于高维多峰函数，速度直线弹离显著改善了算法的性 能，它维持了群体的多样性，使得微粒群可以持续进化。另外，在算法运行初期不经常 使用弹离，这样可以避免微粒的碰撞聚集而引起的停滞现象。 2 2 离散二进制微粒群模型 微粒群算法最初是一种基于实值连续空间的优化技巧，然而许多实际的工程应用问 题是组合优化问题，因而需要将微粒群算法在二进制空间进行扩展，构造一种离散形式 的二进制微粒群决策模型。 在这个模型中，个体进行二进制决策的概率是一个与个体和群体相关的函数 ( k e n n e d y 和e b e r h a r t ，1 9 9 7 ) ，定义如下： e ( x d ( o = 1 ) = f ( x d o 一1 ) ，v d u 一1 ) ，p d ，p 一) ( 2 3 ) 其中： p ( x ，。( f ) = 1 ) 是个体f 为位串上第d 位选择1 的概率( 当然选择零的概率为1 一p ) 。 石。( ，) 是个体，的位串位置d 的当前状态。 t 是当前的时间步，而t 一1 是前一步。 ( ，) 代表个体作一个或另一个选择的倾向，它将决定一定概率阈值，并运用s 形 函数将其限制于需要的范围，并且有时它适于用作概率阈值的性质。 p 。是迄今为止发现的最好状态，例如，如果白为l 时个体取得最大的成功，那么p 0 为1 ；若为0 时个体取得最大的成功，那么p 。为0 。 p 。是邻域的最好状态，如果邻域的任意成员在处于1 状态时取得最大的成功，则 p 。为l ；否则为0 。 于是，在二进制空问中，微粒的移动是通过翻转位值实现的，而微粒的速度描述了 每次迭代改变的位数，或某微粒在f 和卜1 时刻的取值之间的海明距离。为了与连续空 间微粒群算法在表述上保持一致性，忽略其中的时刻表示，并且其中参数的含义保持不 变。微粒群算法的离散二进制模型的速度和位置更新等式为： ，d = 1 0 + c l r a n d l ( x p 盯一x , , t ) + c 2 r a n d ：【天p 一劫j 基于离散二进制p s o 算法的专家选择系统 i f ( r a n d ( ) s h ) ) t h e n = 1 ( 2 4 ) e l s e = 0 其中，s ( v “) = _ 三共t j s i g m o i d 函数，r a n d ( ) 为 o ，1 之间的随机数。速 1 十c 叩一”d j 度5 - i v a 决定了位置分量取1 或0 的概率，越大，则取1 的概率越大。在 离散二进制模型中，仍保留了p o ，它起限制取1 或0 的最终概率的作用。 在此基础上，杨淑媛等1 提出了一种基于量子编码的离散微粒群算法。算法采用量 子个体的表示形式，不再引入非线性的s i g m o i d 函数，而是将p s o 算法“利用最优解 引导整个种群逐渐向好解的区域靠拢”策略应用于一种基于量子比特状态表示的微粒向 量。 2 3 微粒群算法与其他优化算法的比较 2 3 1 微粒群算法与遗传算法的比较 微粒群算法( p s o ) 与遗传算法( g a ) 都是进化计算方法。从算法的步骤来看，两 者基本类似，都遵循以下过程： ( 1 ) 群体随机初始化； ( 2 ) 计算群体的每一个体适应值，通常适应值与最优解关联； ( 3 ) 群体按个体适应值概率进行复制； ( 4 ) 判断终止条件。如果满足终止条件，算法停止；否则转至步骤( 2 ) 。 同时，算法的基本点都是基于适合度的概率计算。 两种算法的主要区别为： 首先，在进化算子上，g a 采用遗传操作算子如交叉( c r o s s o v e r ) 和变异( m u t a t i o n ) ； p s o 是通过对速度的修改来完成进化和搜索的。从某种意义上讲，p s o 的搜索比g a 更具随 机性，因此，更不容易落入局部最优。 其次，与遗传算法比较，p s o 的信息共享机制不同，在遗传算法中，整个种群的移 动是比较均匀的向最优区域移动。在p s o 中，信息的流动是单向的，整个搜索过程是跟 随当前最优解的过程。与遗传算法比较，在大多数情况下，所有的粒子可能更快的收敛 于最优解。此外，微粒群算法基本不受问题峰数增加的影响，受问题维数的影响也很小。 一 茎王壹墼三鲎型! ! 旦簦鲨箜童窒丝堡墨竺 2 ，3 2 微粒群算法与演化规划的比较 如果将( 2 1 ) 看作一个变异算子，则微粒群算法与演化规划( e p ) 很相似，然而， 在每一代，p s 0 算法中的每个微粒只朝一些根据群体的经验认为是最好的方向飞行，而 不象在演化规划中可通过一个随机函数变异到任何方向。也就是说，p s o 算法执行一种 “有意识( c o n s c i e n c e ) ”的变异。从理论上讲，演化规划具有更多的机会在优化点附 近开发，而p s o 贝, t j 有更多的机会更快地飞到更好解的区域，如果“意识”能够提供有用 的信息。 2 3 3p s o 算法与其它优化方法的比较 与传统的基于梯度的优化方法相比，p s o 这类群体智能优化算法具有以下优点： ( 1 ) 在优化目标函数的性态上没有特殊要求，对问题定义的连续性无特殊要求， 甚至可以将传统优化方法无法表达的问题描述为目标函数，使算法应用更具广泛性。 ( 2 ) 没有中心控制约束，个别个体的故障不影响整个问题的求解，算法更具鲁棒 性。 ( 3 ) 非直接的信息共享方式实现合作，算法具有扩充性。 ( 4 ) 由于p s o 算法的随机搜索本质，使得它更不容易陷入局部最优。同时，居于适 合度概率进化的特征又保证了算法的快速性，因此，p s o 算法对于复杂的，特别是多峰 高维德优化问题具有很强的优越性。 3 算法的分析与设计 3 1 对于本问题算法的描述 3 1 1 问题的描述 在众多外挂专家池的大、中型系统中，辽宁省自然科学基金评审系统绝大多数系统 类似于实际项目辽宁省自然科学基金评审系统。在这个系统的开发过程中，对于每一年 申报的项目进行审查并发放基金的工作。在审查项目的过程中，采用多位专家针对同一 个项目进行打分的形式。但是对于评审专家的选择一直采用在项目所在学科领域中，随 机选择出五位专家的方法。在很多情况下，这种方法是不能够很好完成这一功能的，这 也是造成专家拒评项目的主要原因之一。经过仔细的核对和研究后，我们发现，造成这 种专家拒绝评审项目的主要原因是专家的学科领域与专家的单位情况与评审项目之间 的关系造成的。正是在选择专家的过程中，没有对于这两个属性进行考虑，才导致后来 专家的拒绝评审，或者评审质量不高的情况。目前，在专家拒绝评审项目后，解决的方 基于离散二迸制p s o 算法的专家选择系统 法只有通过手动再次为待评审项目分配项目评审人，这样不仅耽误评审进度，同时造成 不必要的人员浪费。对于这两个属性的建模寻优同时也是众多相似系统在解决此类问题 中的共同解决途径。 在综合考虑了问题的情况后，我们首先确定了两个评价域学科领域和单位。由 于在这两个领域内，被评审项目与评审专家的属性存在着模糊耦合性，例如，评审专家 所在领域与被评审项目之间存在着某种以隶属度值为特征的模糊耦合性。因此，我们采 用模糊评价矩阵与寻优算法相结合的方式来进行进一步的研究。 本文研究的问题将是基于一系列模糊关系上的匹配问题。主要是从众多相似因素 ( 同行专家) 当中选择出与目标问题( 待评审项目) 相匹配的因素。通过该算法，我们将可 以从众多( n 个) 相似的已知因素当中选择出符合实际问题需要的m 个因素的最优组合方 案，其中这i 3 个因素都具有相同的模糊属性，同时实际问题也是模糊的。 3 1 2 问题涉及的定义 在进一步进行算法设计之前，先将本文算法涉及到的定义做一明确界定。本文算法 主要涉及到以下定义： ( 其中为了理解方便，将定义的名词加了下划线“一”) 定义3 1 待选因素：一个问题所对应的所有可能被选择的因素称为“待选因素”， 其构成的集合成为“待选因素集”。例：在算例中，缱造固蠢就是专家，而缱丝国塞塞 就是整个专家池( e x p e r tp 0 0 1 ) 定义3 2 匹配因素：匹配因塞是离散微粒群中编码为“l ”所对应的待选因素。例， 在二进制微粒群决策模型的运算过程中，产生新的微粒群1 1 0 0 1 0 1 l ，则第1 、2 、5 、7 、 8 位对应的专家被选中称为匹配因素。 定义3 3 子代的匹配因素( 选定因素) ：在二进n p s o 算法的计算过程中，每一代 称为一个“子代”。在某一子代中被算法选定的因素称为“子代的匹配因素( 选定因素) ”。 但它并不一定是最终的匹配因素，其特征是在子代中的微粒的编码位为“1 ”。 定义3 4 最终的匹配因素：在二进$ l j p s o 算法结束或不再产生新组合情况下形成的 微粒群中的微粒编码位为“1 ”的相应因素叫做“最终的匹配因素”，同时构成问题的 最优解或满意解。 定义3 5 适配度：通过对微粒群每一选定因素自身评价指标的衡量而选出与实际问 题所需要的因素组合最佳模式最为接近的若干个因素的综合评价指标叫做建定固塞与 实际问题的“适配度”。这里应该注意，有的问题是可以找到与实际问题所需要的因素 最佳模式相同( 问题的最优解) 的因素的，但是，大量的问题往往是找不到的。所以，只 能找最为接近的因素( 问题的满意解) ，这里也是为什么要采取模糊评价方法的原因所 基于离散二迸制p s o 算法的专家选择系统 在。将每一个选定因素的单独的适醒鏖以整个二进制微粒群为单位叠加后计算出整个二 迸制微粒群的“合适配度( 微粒群的适配度) ”。 定义3 6 排斥度：二进制微粒群中众多选定因素间由于某种实际关系而产生的不能 同时被选中的倾向，衡量这种倾向的综合评价指标叫做选定因素间的“排斥度( 微粒群 的排斥度) ”。这是一种惩罚变量，用来模拟实际情况，因而，拥有较大排斥度的两个 因素不能同时选中。一般问题不会涉及到这个问题，但是为了保证算法的完整性同时也 是使本算法更具一般性，所以，在算法中将有所体现。 定义3 7 适应度：综合考虑每一子代选定因素组合中的各个要素的适配度和排斥度 从而形成整个组合对问题的“适应度”，其形式即问题的目标函数。 理解定义3 6 、3 6 和3 7 ，我们可以用物理里的作用力的概念来做个比喻，其中适 壁廑就像合力作用中的正向力动力，而挂屋麈则像合力作用中的负向力一一阻力， 这“两种力”同时作用在待选因素上，形成的合力则是适应度。 3 2 算法的设计 3 2 1 框架算法的选择 本文之所以选择二进制p s o 算法作为框架算法，而非其它优化算法，主要是由于二 进制p s 0 算法的并行性，这样可以在众多专家中，选择出一组匹配专家，同时保证这一 组专家的组成也是优化的。如果，我们运用一般的串行优化算法，则不能够达到所选择 的n 位专家的构成是优化的。 其次，没有选择其他具有并行性的算法，例如：神经网络聚类的方法，其一，是由 于没有足够多的有效数据量；其二，是由于神经网络的算法复杂性要普遍高于遗传算法 的复杂性，这样，对于我们的目标一快速寻找满意解，是不利的。因此，放弃了传统的 串行优化算法，以及同样具有并行优化特性的神经网络算法，而选用二进制p s o 算法作 为本算法的框架算法。 3 2 2 模糊关系矩阵的构建 且标函数确立的基础就是模糊评价体系的建立，在待选因素的各种主要属性值不 同，且关系不能简单通过确定数值表示的情况下，需要人为的通过经验建立起一整套模 糊评价体系对各个因素的各种属性进行确定性评价，这就是“模糊评价体系( f a s ：f u z z y a p p r a i s a ls y s t e m ) ”。例如算例实际问题当中的“专家研究的学科领域之间相关性 问题”，我们通过经验( 经验的获得来源于主要是众多专家、项目负责人、基金评审管 理小组、项目开发人等通过讨论达成共识) 建立起如图3 4 所示模糊评价体系图。在遴 基于离散二进制p s o 算法的专家选择系统 选五位专家时，被遴选专家所研究专业领域与被评项目所在专业领域应适当重合。这样 做主要是因为，如果所有专家的学科领域与被评审项目完全相同，会造成对项目评价的 片面性，而且对项目的实际价值的评价将会带有学科局限性：反之，相差太多，专家也 会感觉无从下手。同时，五位专家的研究领域如果过分重合，也会给项目的评价带来片 面性。因此，基于前一种考虑，我们在算法的定义体系及目标函数中引入一个阻碍算子 h a t e 。 标相关性 图3 4 模糊评价体系图 关于学科相关性矩阵的建立，最初打算由专家评审委员会( 其中包括各个评审领域 的代表，省基金中心的领导以及项目开发组的代表组成) 共同商议决定，但是由于工作 量巨大，时间有限；同时，众多意见难于统一。一共找到两种弥补方法一种是教科 文组织发布的学科相关性矩阵，另外一种是从s c i e n t o m e t r i c s ( 科学计量学杂 志) 中得到的学科间关系矩阵。 学科的相关性分析在国内研究还处于初级阶段，但在国外，已经有比较成熟的研究 成果了，特别是在国际教科文组织( u n e s c o ：u n i t e d n a t i o n se d u c a t i o n a l ，s c i e n t i f i c ， a n dc u l t u r a lo r g a n i z a t i o n ) 于1 9 9 2 年发布了学科相关矩阵( 示意图见3 5 ) 之后叫“， 绝大多数成熟的学科之间的相关性已经得到公认。这不仅给研究科学学的专家带来方 便，而且在新的学科的产生、建设和发展中都起到了积极的作用。这个矩阵的得出，是 以学科s 对学科s ，的支持程度而得出的，其中一个矩阵元s 。的大小反映了学科墨对学 科s 的支持程度。呻1 基于离散二进制p s o 算法的专家选择系统 图3 5 教科文组织学科相关性矩阵示意图 f i g u r e3 5s k e t c hm a po ft h es u b j e c t s r e l a t i o n s h i pm a t r i xf r o mu n e s c o 国内研究学科相关性的方法，一种是以上海复旦大学预测与发展研究所陈德棉教授 以及刘云研究员为中心，运用逻辑符号表证的学科相关性分析图；另外一种是新兴的基 于正规学术期刊引言的“引言分析法”。其中，第一种方法也是基于国际教科文组 织发布的学科相关性矩阵，改进而来；而第二种方法，以文献计量学为基础的科学计量 学中针对学科之间运用引文分析的方法所获得的学科支持矩阵来做计算的基础则更为 具有实证研究的价值。综合考虑以上两种方法，我们认为第二种方法更具有时变性，同 时也好转换为数据库表的形式。在参考以引文引用量为基础的支持性矩阵，以及专家评 审组的意见，得到运用矩阵形式来反映不同学科之间的相关性。 3 2 3 问题的评价空间 问题的目标函数是在我们的评价空间中使得算法收敛到最优解( 或满意解) 的一种 规则。这里所说的评价空间是由不同的评价指标构成的一种虚拟空间，待评审项目与评 审专家由于具有相同的属性( 即评价空间的评价指标) ，所以，可以看作是散落在评价空 间中的一些零散的点。 我们在辽宁省基金管理系统中主要涉及到两个影响因素学科领域与单位。但是 在其他的问题中可能这种影响属性就不只两个，而是多个。我们在这里遵守一种原则： 只要是对评审结果有影响的属性( 例如：学科领域或单位) ，那么，专家与待评审项目之 间关于这个属性就一定存在着某种模糊关系。因此，我们就能够根据经验对这种模糊关 系进行从定性到定量的评价，从而形成模糊评价矩阵。 基于离散二进制p s o 算法的专家选择系统 那么，根据之前对于评价空间的描述，当扩展到多个( t 个) 属性时，评价空间就不 再是二维的了，而变为t 维的评价空间。例如，我们对于一个新的问题，需要考虑x 、y 、 z - - - 个不同的属性的影响，我们则需要在一个由x 、y 、z 三个不同的属性的隶属度构成的 评价空间中进行寻优工作。如图3 6