1、大连海事大学硕士学位论文人工鱼群算法的分析及改进姓名：王闯申请学位级别：硕士专业：应用数学指导教师：刘巍20080301中文摘要摘要优化命题的解决存在于许多领域，对于国民经济的发展也有着巨大的应用前景随着优化对象在复杂化和规模化等方面的提高，基于严格机理模型的传统优化方法在实施方面变得越来越困难人工鱼群算法(A r t i f i c i a lF i s h-S w a r mA l g o r i t h m，A F S A)是由李晓磊等在2 0 0 2 年提出的，源于对鱼群运动行为的研究，是一种新型的智能仿生优化算法它具有较强的鲁棒性、优良的分布式计算机制、易于和其他方法结合等优点目前对
2、该算法的研究、应用已经渗透到多个应用领域，并由解决一维静态优化问题发展到解决多维动态组合优化问题人工鱼群算法已经成为交叉学科中一个非常活跃的前沿性研究课题本文的主要研究成果与贡献如下：1)简要的回顾了智能仿生优化算法理论产生的背景总结了仿生算法的基本理论和特点，以及仿生优化算法的共性与个性2)对于人工鱼群算法进行了详细的分析人工鱼群算法是一种新兴的仿生学算法，在介绍了A F S A 的基本原理、算法描述、算法参数和流程的基础上，又介绍了其应用前景3)通过对六年来人工鱼群改进算法的研究，提出了四种改进思路，并介绍了几个典型的改进模型4)提出了引入免疫系统的免疫信息处理机制的两种改进的人工鱼群算法
3、：I M-A F S A 和I V A F S A I M A F S A 是一种基于免疫记忆和调节机制的免疫人工鱼群算法；I V A F S A 是一种基于疫苗接种的免疫人工鱼群算法与基本人工鱼群算法相比，I M A F S A 在提高避免陷入局部最优和收敛速度方面有比较好的效果，而I V A F S A 在保持上述优点的基础上，进一步提高了算法的寻优精度关键词：人工鱼群算法；免疫系统；l M-A F S A；I V-A F S A英文摘要T h eA n a l y s i sa n dI m p r o v e m e n to fA r t i f i c i a lF i s h-S
4、 w a r mA l g o r i t h mA b s t r a c tO p t i m i z a t i o np r o b l e m sn e e dt ob es o l v e di nm a n yf i e l d sa n dt h ef i n es o l u t i o n st ot h ep r o b l e m sm a yl e a dt og r e a te c o n o m i cb e n e f i t W i t ht h ei n c r e a s i n gc o m p l e x i t ya n ds c a l eo f
5、t h eo p t i m i z a t i o np r o b l e m s，c l a s s i c a lo p t i m i z a t i o nm e t h o d sw h i c ha l eb a s e do nt h es t r i c tm o d e l i n gb e c o m ed i f f i c u l tt oU S e T h eA r t i f i c i a lF i s h-S w a r mA l g o r i t h m(A F S A)i sa ne v o l u t i o n a r yc o m p u t a
6、 t i o nt e c h n i q u eb a s e do ni n t e l l i g e n c eb i o n i co p t i m i z a t i o na l g o r i t h m T h i sW a sd e v e l o p e db yL iX i a o l e ii n2 0 0 2a n di n s p i r e db yt h es o c i a lb e h a v i o ro fag r o u po ff i s h T h eA F S Ah a sas t r o n g e rr o b u s t n e s s
7、；t h ef i n ed i s t r i b u t e dc o m p u t i n ga n de a s yt ou n i o nw i t ho t h e rm e t h o d s A tp r e s e n t，t h i sa l g o r i t h mr e s e a r c hh a sa l r e a d yi m p r o v e dm a n yo t h e ra p p l i c a t i o n sa n dh a sd e v e l o p e df r o mao n e-d i m e n s i o n a ls t a
8、 t i cs t a t eo p t i m i z a t i o ns o l u t i o nt oam u l t i-d i m e n s i o n a ld y n a m i cc o m b i n a t i o no p t i m i z a t i o ns o l u t i o n T h eA F S Ah a sa l r e a d yb e c o m ee x t r e m e l ya c t i v ef r o mr e s e a r c hq u e s t i o ni nt h ei n t e r d i s c i p l i
9、 n a r ys t u d i e s T h em a i nc o n t r i b u t i O I l So ft h i sp a p e ra r ea sf o l l o w s：1)T ol o o ka tt h eb a c k g r o u n do fi n t e l l i g e n c eb i o n i ct h e o r y S u m m a r i z et h et h e o r ya n dc h a r a c t e r i s t i c so fi n t e l l i g e n c eb i o n i ca l g
10、o r i t h m s A n dt h ec o m m o n n e s sa n di n d i v i d u a l i t yo fi n t e l l i g e n c eb i o n i ca l g o r i t h m s 2)D e s c r i p t i o no ft h eA F S Aw h i c hi san e wb i o n i c sa l g o r i t h m I ti n c l u d e sa l li n t r o d u c t i o no ft h eb a s i ct h e o r y，t h e a
11、l g o r i t h m i cd e s c r i p t i o n,t h ep a r a m e t e r sa n df l o w c h a r to fA F S A 3 1I tp r o p o s e sf o u ri m p r o v e m e n tm e t h o d so nt h eb a s i so ft h er e s e a r c ho nA F S Ad u r i n gt h ep a s t6y e a r s I ta l s oi n t r o d u c e ss e v e r a lt y p i c a li
12、 m p r o v e m e n tm o d e l s 4)I tp r o p o s e st w oi m p r o v e dA F S A，t h eI M A F S Aa n dt h eI V-A F S Aw h e ne m b e d d e di nt h ei n f o r m a t i o np r o c e s s i n gm e c h a n i s mo ft h ei m m u n es y s t e m T h eI M A F S Ai Sb a s e do ni m m u n em e m o r ya n dm e d i
13、 a t o r ym e c h a n i s m；t h eI V-A F S Ai S英文摘要b a s e dO Rv a c c i n a t i o n C o m p a r e dw i t ho r i g i n a lA F S A，I M A F S Ah a sab e t t e re f f e c ti nt h ea s p e c to fa v o i d i n gt h ep r e m a t u r ec o n v e r g e n c ea n dt h ec o n v e r g e n ts p e e d I V A F S An
14、 o to n l yh a st h es a m ee f f e c t，b u ta l s oh a sab e t t e rv a l u e K e yW o r d s：A F S A；I m m u n es y s t e m；I M-A F S A；I V-A F S A大连海事大学学位论文原创性声明和使用授权说明原创性声明本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果，撰写成博士硕士学位论文：厶王鱼登簋选笪佥堑区馥鲎：。除论文中已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本论文中不包含任何未加明确注明的其他
15、个人或集体已经公开发表或未公开发表的成果。本声明的法律责任由本人承担。论文作者签名：臼副刎缉3 月叩日学位论文版权使用授权书本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、版权使用管理办法，同意大连海事大学保留并向国家有关部门或机构送交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论文。保密口，在年解密后适用本授权书。本学位论文属于：保密口不保密口(请在以上方框内打“”)敝作者签名：习同期：导师签名：驯荔I功晦3 月7 同人工鱼群算法的分析及改进第1
16、章绪论优化的目的是寻找所求问题的最优答案现代意义上的优化实质上是计算机技术同数学规划的综合，对于一个问题而言，它包含有许多限制性的因素(如强度、成本、工艺性、技术等)，优化过程就是使用最优化理论与方法，通过计算机的迭代计算，寻找在限制因素下最优的设计参数值，使该问题在某一方面或某些方面达到最优【嵋】当今社会竞争是很激烈的，各个国家之间的竞争已不仅仅体现在军事方面，而更常用的是渗透到人们日常生活中的经济竞争，抛开其它人为因素，这实质上是产品质量及产品价格之间的竞争，通过降低产品的成本，节约资源，使产品的综合性能达到最优，则产品更富有竞争力，上述要求可以通过采用最优化设计方法达到所以可以说当今对最
17、优化设计的要求比以前任何时候都显得更加重要和迫切【3】1 1 智能仿生优化算法简介地球上的生物物种在漫长的演化过程中形成了丰富的行为特性，并且一直在不断地完善和发展，以更好的适应其所生存的环境随着计算机的诞生，人们期望借助计算机程序的形式创造出一些新型的智能体，于是对人类的大脑活动、生物物种的社会行为以及生物界的进化过程进行了模拟研究随着科学技术的不断发展和进步，人们面临着越来越多的工程优化类问题，其中很大一部分是大规模的、使用传统的优化方法和技术难以解决的最优化问题同时，人类在与自然界的相互作用过程中，认识事物的能力也在不断提高，自然界中的许多自适应优化现象不断给人以启示：生物体和自然生态系
18、统可以通过自身的演化就能使许多在人类看起来高度复杂的优化问题得到完美的解决实践表明：基于自然生念系统模拟而形成的演化计算方法是解决这类问题的有效手段近年来，各种演化方法被相继提出，并得到了国内外学者的深入研究和应用实践演化计算方法在当今世界中J 下同益显示出其巨大的威力试图通过模拟自然生态系统机制以求解复杂优化问题的仿生优化算法，是人工智能研究领域的一个重要的分支自从2 0 世纪4 0 年代以来，人们一直在利用来第1 章绪论自生物系统的灵感来解决许多实际问题，并构造和设计出许多智能仿生优化算法，其中包括模拟生物界中自然选择和遗传机制的遗传算法(G A)、模拟蚂蚁群体觅食行为的蚁群算法(A C
19、O)、模拟人类大脑及其活动的人工神经网络(A N N)、模拟哺乳动物免疫系统的人工免疫算法(A I A)、模拟鱼群觅食行为的人工鱼群算法(A F S A)，以及模拟鸟类群体捕食行为的粒子群算法(P s o)等 4 1 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 年提出的一种仿生优化算、法【5，6 1 受到人工生命(a r t i f i c i a ll i f e)的研究结果启发，P S O 算法的基本概
20、念源于对鸟群捕食行为的研究设想这样一个场景：一群鸟在随机搜索食物在这个区域里只有一块食物所有的鸟都不知道食物在哪里但是它们知道当前的位置离食物还有多远那么找到食物的最优策略是什么呢最简单有效的就是搜寻目前离食物最近的鸟的周围区域P S O 算法从这种模型中得到启示并用于解决优化问题P S O 算法中，每个最优化问题的潜在解都是搜索空间中的一只鸟，称之为“微粒”所有的微粒都有一个由被优化的函数决定的适应值(f i t n e s sv a l u e)，每个微粒还有一个速度决定它们飞翔的方向和距离然后微粒们就追随当前的最优微粒在解空间中搜索P S O 算法初始化为一群随机微粒(随机解)然后通过迭
21、代找到最优解在每次迭代中，微粒通过跟踪两个“极值 来更新自己第一个就是微粒本身所找到的最优解这个解称为个体极值另一个极值是整个种群目前找到的最优解这个极值是全局极值另外也可以不用整个种群而只是用其中一部分作为微粒的邻居，那么在所有邻居中的极值就是全局极值目前，P S O 算法的应用比较广泛，它有着比较好的发展前景，值得做进一步的研究1 1 2 人工免疫算法免疫系统是哺乳动物抵御外来有害物质侵害的防御系统，动物一生始终处于复杂多变、充满伤害的自然环境中，但它们能够平安无事地进行正常的生命活动，其原因是免疫系统在其中起着重要作用人工免疫算法(A r t i f i c i a lI m m u n
22、 eA l g o r i t h m，A I A)正是基于生物免疫抗体产生记忆系统的学习机理的产物这方面的人工鱼群算法的分析及改进研究最初从2 0 世纪8 0 年代中期的免疫学研究发展而来2 0 世纪9 0 年代初，B e r s i n i和V a r e l a 首次使用A I A 来解决实际问题【7】A 认依据的主要免疫学原理包括免疫网络理论、克隆选择原理、免疫学习机制等免疫系统由淋巴细胞把自身细胞与抗原识别出来，并产生抗体对付入侵的抗原，以达到消灭抗原的目的免疫系统对自身也具有免疫能力，它能抑制过多抗体的产生免疫系统有能力产生很多种抗体，但实际上系统只需根据抗原的种类和数目产生适量的
23、相关抗体根据免疫网络理论，每个细胞系的B 型淋巴细胞识别出感受器的遗传类型后，相互之间便构成了链接的网络，从而只产生所需数量的抗体，免疫系统的控制机制可完成这一调节功能如果抗原的刺激激活了某细胞系中的细胞并开始繁殖，则其他能识别这种基因类型的细胞系也被激活并开始繁殖如果这一过程连续地进行，就构成了对自身的免疫，并通过所有淋巴细胞的作用实现了内部调节机制0 1 在使用A n 解决问题时，一般各个步骤有其对应形式：抗原对应所求问题的数据输入；抗体对应于所求问题的最优解；亲和力对应于对解的评估和对结合强度的评估；记忆细胞分化对应于保留优化解；抗体促进和抑制对应于优化解的促进及非优化解的删除；抗体产生
24、对应于优化解的出现；等等A 认产生新个体的方法要灵活的多，并且具有较强的全局搜索能力，是继遗传算法以来又一种具有广阔应用前景的仿生优化算法1 1 3 人工神经网络人工神经网络】(A r t i f i c i a lN e u r a lN e t w o r k，A N N)，或称为神经网络(N e u r a lN e t w o r k s，简称y N)，是大脑及其活动的一个理论化的数学模型，由大量的处理单元(神经元)互连而成的，是神经元联结形式的数学抽象，是一个大规模的非线性自适应模型人工神经网络具有高速的运算能力、很强的自学习能力、自适应能力和非线性映射能力以及良好的容错性，特别适用
25、于处理需要同时考虑许多因素和条件的，不精确和模糊的信息处理问题因而它在模式识别、图像处理、信号及信息处理、系统优化和智能控制等许多领域得到了广泛的应用1 9 4 3 年，心理学家M c C u l l o c h 和数理逻辑学家P i t t s 在研究生物神经的基础上，第1 章绪论首先利用数理逻辑提出了第一个简单的A N N 模型，简称为M P 模型，从此开创了A N N 研究的先河，并为以后的研究提供了依据神经网络是以对信息的分布式存贮和并行处理为基础，它具有自组织、自学习的功能，在许多方面更接近人对信息的处理方法，它具有模拟人的形象思维的能力，反映了人脑功能的若干基本特性，但它并不是人脑
26、的逼真描述，而只是它的某种抽象、简化和模拟1 1 4 遗传算法遗传算法(G e n e t i cA l g o r i t h m s，G A)是基于D a r w i n 进化论和M e n d e l 的遗传学说的随机化自适应搜索算法，最先由美国M i c h i g a n 大学的H o l l a n d 教授于1 9 7 5 年提出的【1 2】由于采用了类似物种进化过程中基因的选择、交叉和变异等操作手段，使得遗传算法在本质上成为一类非确定性算法，具有全局搜索能力，特别适用于多峰值函数的优化问题遗传算法思想是从代表问题可能潜在解集的一个种群开始的，一个种群由经过基因编码的一定数目的个
27、体组成初始种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解在每一代，根据问题域中个体的适应度大小挑选个体，并借助自然遗传学的遗传算子进行交叉和变异，产生出代表新的解集的种群这个过程将导致种群像自然进化一样，后代种群比前代更加适应环境，末代种群中的最优个体经过解码，可以作为问题近似最优解遗传算法是一种不依赖具体问题的直接搜索方法，在模式识别、神经网络、图像处理、机器学习、工业优化控制、自适应控制、生物科学、社会科学等方面都得到了应用在人工智能研究中，人们认为遗传算法、自适应系统、细胞自动机、混沌理论与人工智能一样，都是对今后的计算技术有重大影响的关键技术1 1 5 蚁群
28、算法蚁群算法(A n tC o l o n y)是模拟真实的蚁群觅食过程寻求最短路径的原理，由意大利学者D o r i g o 等在2 0 世纪9 0 年代初首先提出的【l 引最初的蚂蚁算法称为蚂蚁系统(A n tS y s t e m)，对于旅行商问题(T S P)及二次分配问题(Q A P)等取得了较好效果，经过改进后称为蚂蚁算法或蚁群算法4人工鱼群算法的分析及改进蚁群算法吸收了蚂蚁群体行为的典型特征：一是能察觉小范围区域内状况，并判断出是否有食物或其他同类的信息素轨迹；二是释放自己的信息素；三是所遗留的信息素数量会随时间而逐步减少蚁群算法通过候选解组织群体的过程来寻求最优解，这一过程包括
29、适应阶段和协作阶段在适应阶段，各候选解根据积累的信息不断调整自身的结构；在协作阶段各候选解间通过信息交流，以便产生性能更好的解在蚁群算法中，一个有限规模的人工蚁群体，通过相互协作搜索用于解决优化问题的较优解每只蚂蚁根据问题依赖的准则，从被选的初始状态出发建立一个可行解或是解的一个组成部分在建立蚂蚁自己的解决方案中，每只蚂蚁都搜集关于问题特征和其自身行为的信息，并且使用这些信息来修改问题的表现形式，正如其它蚂蚁所看到的那样蚂蚁既能共同的行动又能独立的工作，显示出了一种相互协作的行为，它们之间不使用直接通讯，而是用信息激素指导着蚂蚁间的信息交换蚂蚁使用一种结构上的贪婪启发式搜索可行解根据问题的约束
30、条件列出了一个解，作为经过问题状态的最小代价(最短路径)每只蚂蚁都能够找到一个解，但可能是较差解蚁群中的个体同时建立了很多不同的解决方案，找出高质量的解是群体中的所有个体之间全局性的相互协作的结果1 1 6 人工鱼群算法人工鱼群算法(A r t i f i c i a lF i s h-S w a r mA l g o r i t h m，A F S A)是一种基于模拟鱼群行为的优化算法，是由李晓磊等【1 4】在2 0 0 2 年提出的一种新型的寻优算法在基本A F S A 中，主要是利用了鱼群的觅食、聚群和追尾行为，从构造单条鱼的底层行为做起，通过鱼群中各个体的局部寻优，达到全局最优值在群体
31、中突现出来的目的该算法具有良好的克服局部极值、取得全局极值的能力并且算法中只使用目标函数的函数值，无需目标函数的梯度值等特殊信息，对搜索空间具有一定的自适应能力算法对初值无要求，对各参数的选择也不很敏感A F S A 采用自上而下的设计思路，从A F 的个体行为出发，达到最终的结果的突现，为最优化问题的解决提供了一条新的思路，该算法主要有以下特点：并行性：多个A F 并行的进行搜索；简单性：算法中仅使用了目标问题的函数值；第1 章绪论全局性：算法具有良好的跳出局部极值的能力；快速性：算法中虽然有一定的随机因素，但总体是在步步向最优化搜索；跟踪性：随着工作状况或其它因素的变更造成的极值点的漂移，
32、具有快速跟踪变化的能力A F S A 是一种新型的思路，从具体的实施算法到总体的设计理念，都不同于传统的设计和解决方法，但同时它又能与传统方法相融合因此，从具体的数学问题到更高层次的管理调度等问题，都具有良好的应用前景1 2 智能仿生优化算法的共性与个性1 2 1 智能仿生优化算法的共性目前流行的仿生优化算法主要有遗传算法、蚁群算法、人工神经网络、微粒群算法、人工免疫算法、人工鱼群算法等，它们都属于一类模拟自然界生物系统、完全依赖生物体自身本能、通过无意识巡游行为来优化其生态状态以适应环境需要的最优化智能算法【1 5 9 1 因此，这些仿生优化算法有许多相同的特点(1)都是一类不确定的算法不确
33、定性体现了自然界生物的生理机制，并且在求解某些特定问题方面优于确定性算法仿生优化算法的不确定性是伴随其随机性而来的，其主要步骤含有随机因素，从而在算法的迭代过程中，事件发生与否带有很大的不确定性(2)都是一类概率性的全局优化算法非确定算法的优点在于算法能有更多的机会求得全局最优解(3)都不依赖于优化问题本身的严格数学性质在优化过程中都不依赖于优化问题本身的严格数学性质(如连续性、可导性)以及目标函数和约束条件的精确数学描述(4)都是一种基于多个智能体的仿生优化算法仿生优化算法中各个智能体之间通过相互协作来更好的适应环境，表现出与环境交互的能力(5)都具有本质并行性人工鱼群算法的分析及改进仿生优化算法的本质并行性表现在两个方面：一是仿生优化算法的内在并行性(i n h e r e n tp a r a l l e l i s m)，即仿生优化算法本身非常适合大规模并行；二是仿生优化计算的内含
