（计算机应用技术专业论文）仿生算法及其在专家分配问题中的应用.pdf

中文摘要 遗传算法和蚁群优化算法是两种最流行的仿生算法，前者以自然选择和遗传 变异理论为基础，后者则是对蚂蚁觅食行为进行模拟而提出的一种仿生算法。本 文对这两种算法进行了深入的研究，针对它们收敛速度慢、多样性差、容易早熟 等不足，提出了几种改进的方法。此外，本文还将这两种算法成功应用到一个新 的领域专家分配问题。取得的成果和创新点如下： 提出了两种改进多峰值搜索能力的遗传算法。一种是改进局部搜索能力的小 生境遗传算法。该算法在进化后期进行小生境境内的交叉与变异操作来取代其在 整个解空间内的交叉变异，进行有针对性的局部搜索。它具有更高的求解精度， 更快的收敛速度，是一种寻优能力、效率和可靠性更高的优化算法。另一种方法 将小生境遗传算法和h o p f i e l d 神经网络有机的结合在一起，首先进行小生境遗传 算法寻优，然后对所得具有全局多样性的解进行聚类分析，得到的聚类中心作为 h o p f i e l d 网络的初始搜索点，最后利用h o p f i e l d 网络逐个寻优。该方法综合了 h o p f i e l d 神经网络准确、快速和小生境遗传算法多样性的优点。 提出了一种蚁群优化算法和遗传算法的混合算法。该算法将遗传操作引入到 了蚁群优化算法的每一次迭代后，利用遗传算法全局快速收敛的优点，来加快蚁 群系统的收敛速度。并且通过遗传算法的变异机制，增强了蚁群系统跳出局部最 优的能力。 提出了一种具有先验知识的蚁群优化算法。新算法将问题特征作为先验知识 事先提取出来，并赋予蚁群优化算法中的精英蚂蚁以识别该固有特征的能力，以 提高精英蚂蚁的搜索质量，进而使得新算法整体的求解能力得以提高。 在随着项目数量的迅速增长与研究范围的不断扩大，传统的分配方法和手工 操作已经不能满足基金管理工作需要的前提下，本课题研究了专家分配问题，并 结合专家分配问题的特点，设计了信息素指导下的遗传算子，使用遗传算法对其 进行了求解。并进一步提出了蚁群优化算法求解专家分配问题的方法，实验取得 了较好的效果。 关键词：仿生算法遗传算法蚁群优化算法专家分配问题函数优化旅行商 问题 a b s t r a c t g e n e t i ca l g o r i t h m ( g a ) a n da n tc o l o n yo p t i m i z a t i o n ( a c 0 ) a r et w ob e s tp o p u l a r b i o n i c a la l g o r i t h m s g ai sb a s e do nn a t u r a ls e l e c t i o na n de v o l u t i o nt h e o r y , a n da c o s i m u l a t e sa n t s b e h a v i o u ro fl o o k i n gf o rf o o d t h i sp a p e rd i dm u c hr e s e a r c ho nt h e s e t w oa l g o r i t h m sa n dp r o p o s e ds e v e r a ln e wa l g o r i t h m st oi m p r o v et h e i rp e r f o r m a n c e m o r e o v e rt h i sp a p e ri n t r o d u c e dt h e mt oan e wd i s c r e t eo p t i m i z a t i o na r e a ：e x p e r t a s s i g n m e n tp r o b l e m t h em a i nw o r k sa n d i n n o v a t i v ep o i n t sa r ea sf o l l o w s ： t w oi m p r o v e dg a sf o rm u l t i m o d a lo p t i m i z a t i o nw e r ep r o p o s e d o n ei san o v e l n i c h eg e n e t i ca l g o r i t h m ( n g a ) w i t hl o c a ls e a r c ha b i l i t y t h en e wa l g o r i t h ma d o p t e d t h em e c h a n i s mo fc r o s s o v e ra n dm u t a t i o ni nn i c h ep o p u l a t i o ni n s t e a do ft h ew h o l e p o p u l a t i o nd u r i n gl a t e i t e r a t i o n s t h er e s u l t su s e di ns h u b e r tf u n c t i o ns h o w e di t s s u p e r i o r i t y t h eo t h e ri s ah y b r i da l g o r i t h mo fh g aa n dh o p f i e l dn e u r a ln e t w o r k ( h n n ) ag r o u po fs o l u t i o n sw i t hv a r i e t yw e r eo b t a i n e du s i n gh g af i r s t l y , a n dt h e n t h es o l u t i o n sw e r ep a r t i t i o n e di n t os o m ec l u s t e r sw h o s ec e n t r o i d sw e r ea st h ei n i t i a l v a l u eo fe a c hh n n ，a n dh n n sw e r er u nt oo b t a i na l lm i n i m a i tm a d eu s eo ft h e a d v a n t a g e so fb o t hh g a a n dh n n ，a n da p p e a r e de x c e l l e n tc h a r a c t e r i s t i ci no p t i m a l p r o b l e m so fm u l t i m o d a lf u n c t i o n a h y b r i da l g o r i t h mo fg aa n da c o w e r ep r o p o s e d i ta d d e dg at oa c 0 e v e 拶 g e n e r a t i o n m a k i n gu s eo fg a sa d v a n t a g eo fw h o l eq u i c kc o n v e r g e n c e a c 0 c o n v e r g e n c es p e e dw a sq u i c k e n e d a n dg a sm u t a t i o nm e c h a n i s mi m p r o v e dt h e a b i l i t yo fa c o t oa v o i db e i n gp r e m a t u r e an e wi n t e l l i g e n ta c of o rt r a v e l i n gs a l e s m a np r o b l e m ( t s p ) w a sp r o p o s e d t h e n e wa l g o r i t h me x t r a c t e dt h ei n t r i n s i cc h a r a c t e r i s t i cr u l eo ft s pa n dt h e ni n je c t e di t i n t ot h ee l i t eo fa n t s ，w h i c hi m p r o v e dt h ee l i t ea n t sc a p a b i l i b 7t ob u i l dab e t t e r s o l u t i o na n dt h e nm a d ea ni m p r o v e m e n to f a c o c o m b i n i n gw i t ht h ep r o p e r t yo ft h ee x p e r ta s s i g n m e n tp r o b l e m ，t h i sp a p e r d e s i g n e dt h ei m p r o v e dg e n e t i co p e r a t o r sa n da c oo p e r a t i o n s ，a n dp r o p o s e dm e t h o d s o fs o l v i n ge x p e r ta s s i g n m e n tp r o b l e mu s i n gg a ，a c oa n dh y b r i da l g o r i t h m so fg a a n d a c o k e yw o r d s ：b i o n i c a la l g o r i t h m ，g e n e t i ca l g o r i t h m ，a n tc o l o n yo p t i m i z a t i o n ， e x p e r ta s s i g n m e n tp r o b l e m ，f u n c t i o no p t i m i z a t i o n 。t r a v e l i n gs a l e s m a np r o b l e m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤鲞盘鲎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名： 奄出曰y 叶签字日期：zc ，驴多年7 月夕曰 学位论文版权使用授权书 本学位论文作者完全了解苤鲞盘堂 有关保留、使用学位论文的规定。 特授权基盗盘茔可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 签字日期：3 驴口g 年 导师签名： 霄 心讼 签字日期：2 c ，留年了月步日 天津大学博士学位论文 1 1 仿生算法 第一章绪论 一直以来，为了让人类社会更进步，人们都在不断发明和创造。在向周围环 境学习的过程中，自然界的许多自适应优化现象不断地给人类以启示：生物体和 自然生态系统可以通过自身的演化就使许多在人类看起来高度复杂的优化问题 得到完美的解决，这种能力让最好的计算机程序也相形见拙。2 0 世纪8 0 年代以 来，尤其是在最近几年，一些与经典的数学规划原理截然不同的、试图通过模仿 自然生态系统机制求解复杂优化问题的新型计算方法，如遗传算法、蚁群优化算 法、免疫算法等相继出现，大大地丰富了最优化技术，也为那些传统最优化技术 难以处理的组合优化问题提供了切实可行的解决方案。自然界的生物现象给计算 机科学工作者很多启发，创造了许多来自生命现象的计算方法，一个以模仿自然 与生物机理为特征的仿生算法( b i o n i c a la l g o r i t h m s ，b a ) 时代悄然兴起，并在 一些经典的优化问题( 如旅行商问题) 的求解和实际应用中显示了强大的生命力 和进一步的发展潜力 1 翻。其中，应用最为广泛和成功的算法有遗传算法、蚁群 优化算法等。 仿生算法是模拟自然界生物系统，完全依赖生物体自身的本能，遁过无意识 的寻优行为来优化其生存状态，以适应环境的一类新型的最优化方法【3 j 。仿生算 法具有许多与传统优化算法不同的特点【l ，4 - 5 】： 1 ) 它是一类基于多个智能体的智能算法。仿生算法中的各智能体之间通过 相互的协作来更好地适应环境，表现出与环境交互的能力。 2 ) 它是一类不确定性的方法。不确定性体现了自然界生物的生理机制，并 且在求解某些特定问题方面优于确定性方法。仿生优化算法的不确定性是伴随其 随机性而来的，其主要步骤含有随机因素，从而在算法的迭代过程中，事件发生 与否带有很大的不确定性。不确定性算法的优点在于算法能有更多的机会求得全 局最优解。 3 ) 它具有潜在的并行性。搜索过程不是从一点出发，而是同时从多个点同 时进行。这种分布式的多个智能体的协作过程是异步并发进行的，分布并行模式 将会大大提高整个算法的运行效率和快速反应能力。 4 ) 它具有突现性。仿生算法总目标的完成是在多个智能体个体行为的运动 第一章绪论 过程中突现出来的。 6 ) 它具有稳健性。仿生算法的稳健性是指在不同条件和环境下算法的适用 性和有效性。由于仿生算法不依赖于优化问题本身的严格数学性质和所求解问题 本身的结构特征，因此用仿生算法求解不同问题时，只需要设计相应的评价函数 等，而基本上无需修改算法的其他部分。 7 ) 它具有进化性。在复杂的、不确定的、时变的环境中，仿生算法可以通 过自学习不断提高算法中个体的适应性。仿生算法根据环境的改变和过去的行为 结果，对自身的知识库或自身的组织结构( 视系统的表达方式而定) 进行再组织， 从而实现算法求解能力的进化。这种进化是环境变化和算法自学习能力发生的交 互作用的产物。由于这种作用机理的复杂性和环境变化的不确定性，更加强了仿 生算法的不可预测性。 用于解决复杂组合优化问题的算法，从最初的构造性方法发展到局部搜索技 术，再发展到现在的基于种群的算法。这一发展历程是和信息交换技术的发展相 平行的。仿生算法处理的对象是基于多个个体的种群，个体之间通过独特的信息 交换机制不断进化，同时每个个体也可以独立地向前进化。个体间相互合作的阶 段与个体自身自适应的阶段交互进行，从而达到个体行为( 如蚁群优化算法中的 蚂蚁个体) 或个体性能( 如遗传算法中的染色体和免疫算法中的抗体) 的优化。 仿生算法能以惊人的效率有效地完成优化和控制的复杂任务，为人类科学技术的 发展提供了研究的理论方法。 1 1 1 遗传算法 遗传算法( g e n e t i cm g o r i t h m ，g a ) 是j o h nh o l l a n d 于1 9 7 5 年受生物进化 论的启发而提出的【6 】。它的思想来源于达尔文的进化论和孟德尔的遗传学说。它 为求解传统数学方法难以处理的问题提供了一个有效的途径和通用框架。早在 2 0 世纪6 0 年代起美国大学开始研究自然和人工系统的自适应行为，并于1 9 7 5 年首先模拟达尔文的遗传选择和自然淘汰的生物进化论，并在此基础上发展起来 了遗传算法的计算模型。( ( a d a p t a t i o ni nn a t u r a la n da r t i f i c i a ls y s t e m ) ) ( h o l l a n d ， 1 9 7 5 ) 一书被公认为遗传算法的诞生【6 l 。1 9 8 9 年，d a v i de g o l d b e r g 博士专著的 ( ( g e n e t i ca l g o r i t h m si ns e a r c h ，o p t i m i z a t i o na n dm a c h i n el e a r n i n g ) ) 是g a 发展史 上的又一个里程碑】，标志着遗传算法在工程实际中得到了应用。从1 9 8 5 年在 美国卡耐基梅隆大学召开的第一届国际遗传会议到1 9 9 7 年5 月的i e e e 的 t r a n s a c t i o n so ne v o l u t i o n a r yc o m p u t a t i o n 创刊，遗传算法作为具有系统优化、适 应和学习的高性能计算和建模方法的研究日趋成熟。在h o l l a n d 、d ej o n g 和d a v i d g o l d b e r g 为遗传算法奠定了理论基础之后，遗传算法的研究经历了一个相对平稳 天津大学博士学位论文 的发展时期，其主要特征是理论研究结合应用的算法的性能改进等等。 1 1 1 1 基础理论研究 遗传算法的理论研究涉及广泛，从待解决问题可行解的编码格式、遗传操作 中的参数设置，遗传算子的搜索机制与选择方式的选取，到遗传算法的收敛性与 收敛速度分析，复杂性分析，算法性能优劣的评价以及算法生成的方式方法等等， 都是理论工作者与应用工作者十分关注的基本问题。模式理论和收敛理论是其中 两个热点和关键问题。对于收敛性理论，作为遗传算法的一个核心理论问题它包 含收敛性与收敛速度的研究。收敛性问题曾困扰了人们很长时间，直到最近才有 一些令人欣慰的研究成果出现。如文献 8 利用链的遍历性给出收敛结果；文献 9 利用一理论给出遗传算法的渐进强收敛性结果，文献 1 0 1 和文献f 1 1 1 利用不动点 理论给出简单遗传算法的收敛性结果，等等。尽管遗传算法收敛性的研究已取得 了较大进展，但是其理论的系统性和通用性还远远不够，仍有很多问题需要进一 步研究，如对基于个体水平与基因水平上的算法模型的收敛性分析，非选择型算 法的收敛性分析及非二进制编码算法的收敛性研究等等。与遗传算法收敛性的研 究相比，遗传算法收敛速度的研究相对滞后，研究成果是非常有限的，文献 1 2 综述了遗传算法收敛性及收敛速度估计的近期研究结果，并指出遗传算法理论研 究存在的亟待解决的问题；文献 1 3 1 研究了具有e l i s i t 选择的遗传算法的收敛速 度估计问题，文献 1 4 将遗传算法分为时齐和非时齐遗传算法，并利用 m i n o r i z a t i o n 条件讨论了这两类算法的收敛速度；文献 15 研究了经典遗传算法的 收敛速度。总之，遗传算法收敛速度的研究还需要人们花费更多的时间精力去深 入研究。 1 1 1 2 算法性能改进 自从1 9 7 5 年h o l l a n d 系统的提出遗传算法的完整结构和理论以来，众多学 者一直致力于推动遗传算法的发展，对编码方式、控制参数的确定、选择方式和 交叉机理等进行了深入的探索，引入了动态策略和自适应策略以改善遗传算法的 性能，提出了各种变形的遗传算法。如分层遗传算法、c h c 【1 7 】、m e s s yg a 7 】、 自适应遗传算法【1 8 】、混合遗传算法( 如与梯度法、模拟退火算法的结合等) 1 9 - 2 2 、 并行遗传算法 2 3 - 2 5 】等。 改进策略大致可以概括为以下几个方面： 1 ) 改进遗传算法的组成成分或使用技术，如选用优化控制参数、适合问题 特性的编码技术等； 2 ) 采用混合遗传算法： 第一章绪论 3 ) 采用动态自适应技术，在进化过程中调整控制参数； 4 ) 采用非标准的遗传操作算子； 5 ) 采用并行遗传算法。 另外，为了提高遗传算法种群中个体的多样性，引入了小生境技术。小生境 遗传算法( n i c h eg e n e t i ca l g o r i t h m ，n g a ) 目前代表性的有c a v i c c h i o 提出的基于预 选择机制的小生境技术 2 6 】；d ej o n g 提出的基于排挤机制的小生境技术 2 7 】，它使 用种群的代间覆盖方式，依据相似性替换种群中的个体；g o l d b e r g 和r i c h a r d s o n 提出的基于共享机制的小生境技术【2 8 1 。 1 1 1 3 应用研究 遗传算法由h o l l a n d 首次提出后，逐渐发展成一种白适应启发式概率型搜索 算法，用以求解不同的非线性问题。用遗传算法作为工具解决实际问题，这一直 是遗传算法的主要研究领域。 从2 0 世纪8 0 年代以来遗传算法的应用研究一直处于不断上升的趋势，其应 用领域主要包括以下几个方面： 1 ) 函数优化 2 8 - 3 0 】：函数优化是遗传算法的经典应用领域，也是对遗传算法 进行评价的常用领域。 2 ) 求解工程技术领域中存在的大量优化问题 3 1 - 3 3 ：遗传算法在求解大规模、 复杂的优化问题方面取得了重要的应用成果，但是在如何根据具体问题设计有效 的遗传算法以提高计算效率及解决约束优化问题方面还有许多工作要做。 3 ) 分类系统 3 4 - 3 6 ：分类系统属于基于进化算法的机器学习中的一类，它包 括一个简单的基于串规则的并行生成子系统，规则评价子系统和进化算法子系 统。 另外遗传算法还有在生产调度问题3 7 1 、机器人智能控锖o t 3 8 3 9 j 、图像处理和模 式识另l j 4 0 - 4 2 、优化控制 4 3 - 4 5 等方面的成功应用。 遗传算法自二十世纪七十年代产生以来越来越受到人们的关注，这是由于遗 传算法在解决一系列复杂难问题时具有独特功效 4 6 - 4 8 】。作为一种随机搜索算法， 它较其他算法有其自身显著特色，其中算法演化的并行性、对全局优化问题的有 效性与实用性，以及对问题求解的稳健性是其他算法无法比拟的。当然，遗传算 法产生的意义不仅仅表现在它能有效的解决实际问题，更重要的是，如文献 4 9 1 中所展望的，它将可能指导人类自身的诸多智力活动的演化。 1 1 2 蚁群优化算法 蚁群优化算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) 是一种受自然界生物行为 天津大学博士学位论文 启发而产生的仿生算法，基本思想是模仿蚂蚁依赖信息素进行通信而显示出的社 会行为，它是一种随机的通用试探型方法，可用于求解各种不同的组合优化问题， 具有通用性和鲁棒性，是基于总体优化的方法。作为通用型随机优化方法，蚁群 优化算法自问世以来就表现出了强大的生命力，较之以往的启发式算法不论在搜 索效率上，还是在算法的时间复杂度方面都取得了令人满意的效果。 2 0 世纪9 0 年代d o r i g om 最早提出了蚁群优化算法蚂蚁系统( a n t s y s t e m ，a s ) 并将其应用于解决计算机算法学中经典的旅行商问题( t s p ) p 川。 自1 9 9 1 年意大利学者d o r i g om 等提出蚁群优化算法后的近5 年时间里，并没有 在国际学术界引起广泛关注，这段时期在蚁群优化算法理论及其应用上也没有取 得突破性进展 5 1 - 5 4 】。到了1 9 9 6 年，d o r i g om 等发表了”a n ts y s t e m ：o p t i m i z a t i o n b yac o l o n yo f c o o p e r a t i n ga g e n t s ”一文，这是蚁群优化算法发展史上的又一篇奠基 性文章【5 5 1 。自1 9 9 6 年之后的5 年时间里，蚁群优化算法逐渐引起了世界许多国 家研究者的关注，其应用领域迅速拓宽，这期间也有大量有价值的研究成果陆续 发表。1 9 9 8 年，在比利时布鲁塞尔召开了第一届蚁群优化算法国际研讨会。2 0 0 0 年，d o r i g om 在国际顶级学术刊物( ( n a t u r e ) ) 上发表了蚁群优化算法的研究综述 陋6 1 ，从而把这一领域的研究推向了国际学术的最前沿。进入2 l 世纪后的最后几 年，国际著名的顶级学术刊物曾多次对蚁群优化算法的研究成果进行报道。如今， 在国内外许多学术期刊和会议上，蚁群优化算法已经成为一个备受关注的研究热 点和前沿性课题。 我国在蚁群优化算法领域的研究起步较晚，从公开发表的论文看，国内最先 研究蚁群优化算法的是东北大学控制仿真研究中心的张纪会博士与徐心和教授。 随着蚁群优化算法的研究发展，国内越来越多的学者也开始关注这一算法，并提 出了一些改进算法，对蚁群优化算法的研究与发展也做出了一定的贡献。其中， 也有一些将蚁群优化算法与其他智能优化方法相结合的改进算法，如遗传算法与 蚁群优化算法相结合的改进算法：吴庆洪等人提出的具有变异特征的蚁群优化算 法( m u t a t i o na n ts y s t e m ，m a $ ) 5 7 j ；陈烨提出的带杂交算子的蚁群优化算法 ( c r o s s e d a n tc o l o n ys y s t e m ，c c a s ) 【5 8 】；丁建立等人提出的遗传算法与蚁群优 化算法的融合( g e n e t i ca l g o r i t h m a n ta l g o r i t h m ，g a a a ) 1 5 9 。免疫算法与蚁群 优化算法相结合的改进算法：胡纯德等人提出的基于人工免疫算法和蚁群优化算 法求解旅行商问题 ；蒋加伏等人提出的基于免疫蚁群优化算法的多约束 q o s 路由选择【6 。还有通过自适应性地改变算法的相关参数的改进算法：如自适 应调整信息素的蚁群优化算法【6 引；具有分工的自适应蚁群优化算法【6 3 j ；基于协 同学习机制的蚁群优化算法畔 等。以上这些改进算法都从不同方面对蚁群优化算 法进行了有效的改进，对算法的发展做出了一定的贡献，为蚁群优化算法在更多 第一章绪论 领域中的应用奠定了坚实的基础。 回顾蚁群优化算法自创立以来十多年的发展历程，蚁群优化算法无论在算法 理论还是在算法应用方面都取得了很多突破性研究进展。作为一个前沿性的热点 研究领域，蚁群优化算法引起越来越多国内外研究者的关注，近五年内其研究人 员和研究成果均呈几何级数增长。现己陆续应用到组合优化、人工智能、通讯等 多个领域。从数值模拟结果来看，它比目前广泛研究的遗传算法、模拟退火算法 等有更好的适应性。表1 1 列举了部分有代表性的蚁群优化算法应用情况。 表1 1 当前a c o 算法的应用列表 天津大学博士学位论文 蚁群优化算法理论的应用方法研究证明，虽然相对于各种比较成熟的计算智 能方法来说蚁群优化算法的研究还处于初级阶段，并存在种种有待深入研究和解 决的问题，但是可以预言，它的研究代表了以后计算机研究发展的一个重要方向。 1 2 优化问题 优化方法涉及的工程领域很广，问题种类与性质繁多。归纳而言，最优化问 题可分为函数优化问题和组合优化问题两大类，其中函数优化的对象是一定区间 内的连续变量，而组合优化的对象则是解空间中的离散状态。 1 2 1 连续优化问题 连续优化问题又称函数优化，通常可描述为：令s 为r 胛上的有界子集( 即 变量的定义域) ，厂：s r 为”维实值函数，所谓函数厂在s 域上全局最小化就是 寻求点x 。；。s 使得s ( x 。m ) 在s 域上全局最小，即v x s ：厂g 幽) s ( x ) 。算法 的性能比较通常是基于一些称为b e n c h m a r k 的典型问题展开的。连续优化问题可 以分为无约束优化问题和约束优化问题两大类。 无约束优化问题是指【lj ： m i n f ( x 1 x r ” ( 1 一1 ) 约束优化问题由目标函数和约束条件两部分组成【】 ： m i nf ( x 、x r ” s 1 c ，( x ) = 0 ，= 1 2 ，聊 ( 1 - 2 ) c ，( x ) 0，= m + 1 ，”+ 2 。，7 其中，s ( x ) 及c ，b ) 都是定义在r ”上的实值连续函数。n 是一正整数，m 是 介于0 和n 之间的整数。r ( x ) 为目标函数，被称为约束函数。s t 是英文s u b j e c tt o ( 满足于) 的缩写。如果m - - n ，则问题被称为等式约束优化问题。如果c ，( x ) 都 是线性，称该问题是一个线性约束优化问题。一个线性约束优化问题，如果目标 函数厂( x ) 是二次函数，则被称为二次规划问题。 满足所有约束条件的解空间称为可行域，可行域中的解称为可行解。在可1 亍 域中使目标函数最小的解为最优解。对于最大化问题，可将目标函数乘以1 ，转 化为最小化问题求解。 1 2 2 组合优化问题 组合优化或称为离散优化是一门古老而又年轻的学科。说它古老，是因为一 些组合优化问题有着悠久的历史渊源。说它年轻，是因为其作为运筹学的一个独 第一章绪论 立分支而发展起来还是近几十年的事。二十世纪后半叶，随着计算机科学技术突 飞猛进的发展和其在各行业的广泛应用，组合优化已壮大成为- - f q 新兴的学科分 支。一些数百年前数学家们偶然想到的问题和方法，现在已在网络通信、物流管 理、交通规划、生物信息等方面发挥了重要作用。这寓示了此学科的巨大前景。 组合优化问题通常可描述为【l 】：令q = b ，s ：，s ， 为所有状态构成的解空间， c ( s ，) 为状态s ，对应的目标函数值，要求寻找最优解s + ，使得v j ，q ， ( 1 f ) = m i n c ( 5 ，) 。组合优化往往涉及排序、分类、筛选等问题，它是运筹学的一 个重要分支。 典型的组合优化问题有旅行商问题、加工调度问题、o 1 背包问题、装箱问 题、图着色问题、聚类问题等。这些问题描述都比较简单，并且有很强的工程代 表性，但最优化求解很困难，其主要原因是所谓的“组合爆炸”。譬如，聚类问 题的可能划分方式有k ”七! 个，j o h s h o p 的可能排列方式有( 门! ) ”个，基于置换排 列描述的胛城市旅行商问题有胛! 种可能排列，即便对无方向性和循环性的平面问 题仍有( q 一1 ) 2 种不同排列，显然状态数量随i 口- j 题规模成指数增长。若计算机每 秒能处理1 亿种排列，则穷举2 0 城市问题的2 01 种排列约需几百年，如此巨大的 计算量是无法承受的，更不用谈更大规模问题的求解。因此，解决这些问题的关 键在于寻求有效的优化算法，也正是问题的代表性和复杂性激起了人们对组合优 化理论与算法的研究。 1 3 专家分配问题 1 3 1 专家分配问题的研究背景和意义 科学基金制 9 4 。9 6 】是社会支持与促进科学事业发展的一种制度或管理方式，指 国家各级政府或各种社会团体、企事业单位与私人以某种方式( 拨款或捐赠) 拿 出一部分钱，作为科学基金交给科学家团体( 科学基金会或相应的管理部门) 予 以管理并用于支持科学事业的做法。 我国的科学基金制是伴随着改革开发和科技体制改革逐步形成的。1 9 8 2 年 中国科学院首先设立了面向全国的自然科学基金，即中国科学院科学基金，这是 我国科学基金制的开始。1 9 8 5 年中共中央关于科技体制改革的决定指出， 改革科技拨款模式，对基础研究和部分应用研究逐步试行科学基金制。19 8 6 年 国家自然科学基金委员会成立，标志着科学基金制在我国正式建立。2 0 多年的 实践证明，科学基金制这一科技管理制度适合我国国情。随着我国科技体制改革 的不断深入，具有中国特色的科学基金制已经形成。 天津大学博士学位论文 我国的科学基金制改进了计划经济体制下的科技拨款制度，根据竞争择优的 原则决定科技资源的配置，在实际操作中往往采用同行评议的方式。同行评议 一卜1 0 1 从原则上讲是一种遴选资助项目的科学方法，因为它依靠同行专家判断项 目的科学价值，以此决定是否给予资助。目前，世界各国都已建立了不同同行评 议模式的基金机构 1 0 2 。1 0 5 ，如美国国家科学基金会( n s f ) 、美国国立卫生研究院 ( n i h ) 、加拿大自然科学与工程研究理事会( n s e r c ) 、德意志研究联合会 ( d f g ) 、澳大利亚研究理事会( a r c ) ，它们都将同行评议作为遴选科学基金项 目的主要手段。虽然各国都已建立了完善的同行评议方法，但是都没有对“同行 评议”给出一个标准的定义。比较公认的定义是：一群与要评估的项目研究者具 有同等知识和专业技能的科学家同行对该研究项目进行的技术、科学价值的独立 评估过程【1 0 6 】。同行评议在评价科学研究活动方面发挥着不可替代的作用，已被 世界上众多国家普遍应用，越来越成为提高科研管理绩效、科学进行科技投资决 策、推进管理的科学化和民主化的一种重要辅助手段 1 0 7 】。 同行评议的首要工作是分配专家，在同行专家进行项目评审之前，首先要为 项目确定评审专家。评审专家的素质及其对所评审项目的熟悉程度，将直接影响 同行评议结果的质量。专家在同行评议中的关键性作用在于，他们的评审意见对 项目最终评价和立项结果起着决定性的作用。因此，专家分配的质量关系到基金 管理制度实施的公平性、公正性的体现，关系到基金投入是否能够回收预期的成 本，关系到能否真正推动科技进步从而促进区域经济的发展。 初期，专家分配是为项目逐一分配相同数目的评审专家，按照项目的学科从 专家库中一一选定。在科学基金制建立初期，基金申报项目较少，涉及的研究范 围有限，因此该方法完全满足基金管理的需要。 随着科学基金制的逐渐推广和应用，基金申请项目数量逐年增长，上述分配 方法也出现了相应的问题：导致参加评审的专家数巨大，无法有效的统一管理评 审专家；大量的评审专家致使评审成本无法控制，给基金管理工作带来困扰；部 分专家分配了过多的项目，致使专家在短时间内无法按时提交评审结果，难以保 证评审质量，或者部分专家分配的项目过少，造成专家资源的浪费。鉴于此，对 内容相近的申请项目尽可能的选择同一组专家评审成为解决问题的一个途径，这 样可以一定程度上减少评审专家的数目，便于管理评审专家和控制评审成本。 目前，多数基金管理机构采用专家按学科分组、随机抽取专家的方法为项目 分配评审专家，例如现行国家自然科学基金项目专家分配的基本程序剁1 0 8 ：先 按研究领域将项目分组，每个项目组按学科随机选择6 7 位同行专家，同一单位 回避，确保每个项目有五位专家评议。 随着基金申请项目的继续增长与研究范围的不断扩大，项目分组的标准不断 第一章绪论 细化，分组的规模也不断增大。使用传统的方法，在保证项目能找到合适专家评 审的前提下，需要给项目按照细化的标准分组，分组后为每个项目组选择专家， 而规模巨大的分组造成工作复杂度的增大，甚至是手工无法完成的，这又给管理 人员的工作带来了困难。因此，各基金管理部门也在逐步探索新的专家分配方法， 完善项目评审过程。 在计算机技术快速发展的今天，智能优化技术也不断成熟。我们希望能探索 到一种更有效、更科学、更便捷的分配方法，基于智能优化技术并使用计算机技 术实现，解决现在专家分配没有明确标准，手工操作落后的状况。 随着信息技术的发展，数字化时代的到来，基金管理的各项工作也正在向信 息化、数字化发展。网上申报、网上评审等工作使基金管理工作更为高效，项目 评价、专家评价等工作又使得基金管理工作更为科学。基金管理中各项工作的信 息化、数字化形成了各项基础数据的电子化，也成为我们使用计算机技术解决专 家分配问题的数据基础。 因此，专家分配问题研究的实际需要和数据条件的具备促成了本课题的研 究。 1 3 2 专家分配问题的主要内容和研究步骤 专家分配问题不同于特定项目的专家选择问题。选择专家，着重于对专家各 种素质的综合评价，然后为特定的项目选择最适宜、综合评价最高的专家；而分 配专家则着重为一组项目和相应的一组专家之间建立最优化的分配方案，主要研 究专家在诸多项目间的共享从而达到资源的最优配置。 专家选择只需要从数据齐备的专家库中找出最合适的专家，而专家分配需要 在各个项目间调配专家以达到整体分配方案最优，因此在分析实际应用过程中专 家分配工作的各种关联后，确定了专家分配问题的主要内容：专家分配是给一组 项目基于一定的分配原则，在一定的约束下，为达到相应的分配目标在专家集合 中分配专家的过程。专家分配的分配目标是各指标的整体最优，一组项目中各个 项目的分配结果相互关联甚至相互制约，最终形成整体分配方案。下面详述问题 的分配原则、约束条件和分配目标。 分配原则 专家分配和同行评议贯彻的原则是一致的：公开性、公正性、可靠性、效用 性和经济性。 约束条件 要避免将项目的负责人和成员作为评审专家；避免为项目分配到和项目的负 责人、成员在同一单位的专家；避免为项目分配到项目提出需要回避的专家；每 天津大学博士学位论文 个项目必须分配相同数目的评审专家。 分配目标 1 ) 每个项目都属于特定的一个学科或多个学科( 交叉学科项目) 。同样每个 专家也都有自己所熟悉的学科。为项目分配的专家要熟悉项目的研究内容及相关 研究领域的国内外发展情况，并且学风严谨，办事公正，有较高的道德修养。因 此最终的分配方案，每个项目和其评审专家的学科匹配程度越高越好；评审专家 对项目所属学科的熟悉程度越高越好：评审专家个人的综合评价等级越高越好： 2 ) 参加评审的专家总数越少越好。科学基金组织要对专家评审过程进行监 督，对于未及时评审项目的专家进行督促或者撤换，对项目分配有偏差即评审专 家对项目不甚熟悉的情况要进行及时调整。最后，进行专家评审意见收集整理和 专家评审意见量化打分等一系列工作，因此较少数量的评审专家便于管理和监 督，使得项目评审工作更高效更准确；另外，使用较少的专家可以降低评审成本， 节约资源； 3 ) 参加评审的专家所评审的项目数不易过多，避免专家延误提交评审意见 的日期或者出现评审任务繁重而无法仔细阅读评审材料、斟酌评审意见的情况； 4 ) 参加评审的专家所评审的项目数不易过少，专家作为项目的评审者存在 于科学基金组织建立的专家库中，是科学基金组织的重要资源之一，因此要保证 对资源的充分利用。 根据专家分配问题的主要内容，可以得出专家分配问题的主要特点： 1 ) 多约束条件的存在。专家分配有两个约束条件必须满足，这样最终的分 配方案才是有效的。 2 ) 分配目标的多样性。专家分配是个多目标优化问题。 3 ) 数据量大。随着基金申请项目的迅速增长与专家数据库的不断扩充，使 得专家分配问题面对的数据量逐渐增大。假设现有1 1 个项目，m 个专家每个项 目必须分配a 个专家，那么每个项目就有c ：种专家组合可以分配，而对于n 个 项目就有( c ：) ”种分配方案，可见随着项目数的增大，专家分配问题所面对的数 据规模将成指数速度增加。 对于专家分配问题的四个分配目标，第一个分配目标注重的是项目和专家的 匹配精度；第二个分配目标注重的是整体使用的专家个数；第三个和第四个分配 目标注重的是每个专家的评审项目数，都在最优范围内或者刚近最好。而第一个 分配目标和其余两个是相互制约的，完全要求匹配精度，必然导致莱些专家评审 项目数的过多或过少，也会导致最终专家数目的增加。而如何协调分配目标，达 到整体最优是专家分配问题的难点。 另外，专家分配面对的数据量逐年增大，因此对于这个庞大的数据整体我们 第一章绪论 需要分组完成。况且，对项目按照学科分组，对组内项目尽量使用同一组专家评 审，也是现在专家分配采用的主要方法，但是传统的分配方法需要给项目进行精 细的分组，这样同一组的项目才可以尽量使用同一组专家评审，而本文所讨论的 专家分配问题是研究一组项目和一组专家的动态分配，因此不需要精细分组，只 要在一定程度上降低每组项目的数据规模即可。 1 3 3 专家分配问题的研究现状 目前国内多数基金管理机构采用专家按学科分组、随机抽取专家的方法为项 目分配评审专家，此方法存在很多弊端。然而，国外，由于每年申请项目基金的 人数相对较少，它们通常建立专门的学术小组，基金管理制度比较完善。比如美 国n i h 学术评审由科学评议中心专门负责( c s r ) ，并建立相关领域的科学评审 小组( s r c s ) 。澳大利亚研究理事会( 灿汇) 分为4 个学科组，学科组主任指定 评审成员，决定评议人。德意志研究联合会( d f g ) 采用学会推荐+ 直接选举相 结合方法产生同行评议委员会，并采用“2 + 1 ”同行评审方式，对于一般项目， 首先选择2 位具有独立判断力的同行专家进行评议。如果两位专家的意见一致， 那么就按照同行专家的意见决定是否给予资助；如果2 位专家评议意见不一致， 则选择第三位同行评议专家，依据第三位同行评审专家的意见决定是否推荐资 助。对于重点项目和特殊研究领域项目的评审，采用答辩和实地考察相结合的方 式。 此外，目前国内外对同行评议的研究集中在评议过程中评议方式和评议后期 评议结果的处理上。主要有以下几个方面： 1 ) 各学科、各专业领域里同行评议专家库的建设和更新 1 0 8 1 0 9 。 2 ) 专家和项目评价指标的确定和评估问题 1 i o , 1 1 1 。 3 ) 跟踪评审专家的评审质量，根据同行评议结果对专家进行反评估 t t 2 - 1 1 4 3 ， 将评审结果“奇异”而又不能给出有说服力解释的专家给以淘汰出专家库或者降 低其专家水平等处理。 4 ) 采用多级同行评议5 | 。一个项目的评审，经过同行专家通讯评议、学科 综合意见、学科评审组会审三个环节，由同行专家、评审会专家和学科管理人员 三者形成相互依赖、相互制约的决策群体：对于学科交叉、全新研究领域以及争 议较大的研究项目，在可能的情况下可以采用“面对面”公开答辩的方式听取意 见，确保创新项目得到公正准确的认识和评价。 对评议初期，研究重点集中在专家库的建立和动态管理，以及对专家各种素 质进行综合评价，然后为项目选择在学术水平、评议水平和道德水平等多项指标 综合下最适宜的专家 9 9 1 0 7 1 。而随着知识的剧增，申报项目的研究范围越来越广， 天津大学博士学位论文 学术领域的划分越来越细，要每个项目都由学科方向完全一致的专家来评审，在 现有专家相对项目紧缺的状况下，也是无法实现的。那么如何在现有资源下合理 分配专家也就是如何协调多个项目间专家的分配，使得专家资源得到充分利用而