（农业水土工程专业论文）蚁群算法的改进及其水资源应用.pdf

摘要 摘要 在水资源系统工程中，存在诸多非线性、多维组合优化问题。解决这些问题的传统方法 多采用解析法和穷举法，但这些方法都存在不同程度的缺点。本论文的目的旨在寻求出能够 解决这些问题的更有效更方便的方法。蚁群算法( m tc o l o n ya l g o r i t h ma b b r e v i a t e d ：a c a ) 是 一种全局优化方法，本论文在前入研究基础上，对蚁群算法进行了改进，建立了蚁群算法在 水资源优化和预测等方面的新模型，通过m a t l a b 计算机语言编程，进行数据处理，应用于 实践中，较好地解决了水资源系统中的多元复杂性问题。取得了良好的效果。 本文取得了以下三方面的成果： 1 本文介绍了一种具有随机性的局部搜索策略的蚁群算法模型，它可以提高一般函数优化 问题的求解精度和搜索效率。本次研究将该模型成功的应用在明渠断面临界水深优化计算、 溢流坝下游断面水深优化计算中，效果十分明显，计算精度也较高。 2 本论文找到了蚁群算法与m a r t 小波神经网络的结合点，用优化连续空间的多维蚁群算 法代替梯度下降法，调节b p 网络的权值与小波函数的伸缩系数、平移系数：用小波函数m m - r 代替b p 网络中的s 型激活函数；并用小波网络的总体标准差作为蚁群算法的目标函数。该耦 合模型用于水稻需水量预测中，取得了满意效果。 3 蚁群算法具有很好的全局优化能力。本文在实码加速遗传算法的基础上，对该模型进行 了很大的改进。提出了连续多维型蚁群一遗传算法，并首次应用在查哈阳灌区水稻灌溉制度 优化利用中，计算结果与实际配水基本一致，证明该模型具有很好的实用价值。 基于以上几种的模型的建立，本论文实现了理论与实践的有机结合。该论文的研究成果 既为水文水资源领域的复杂、非线性问题提供了新的方法和思路，同时也拓宽了蚁群算法的 应用范围，并且在理论上做了相应的改进。 关键词水资源系统；蚁群算法；人工神经网络；遗传算法；优化；预测 东北农业火学工学硕- 【：学位论文 i m p r o v e m e n t o fa n tc o l o n ya l g o r i t h m a n di t sa p p l i c a t i o ni nw a t e r r e s s y s l r e s o u r c e s ：s y s t e m a bs t r a c t w a t e rr e s o u r c e s s y s t e me n g i n e e r i n ge x i s t e d ag r e a td e a lo fn o n l i n e a r , m u l t i d i m e n s i o n a l c o m b i n a t i o no p t i m i z a t i o n t r a d i t i o n a ls o l u t i o n sw e r ea n a l y t i c a la n de x h a u s t i v em e t h o d , b u tt h e s e m e t h o d sh a dd i f f e r e n td i s a d v a n t a g e s t h i ss u b j e c tc o u l ds e e km o r ee f f e c t i v ea n dc o n v e n i e n t s o l u t i o n s a n tc o l o n ya l g o r i t h mw a sag l o b a lo p t i m i z a t i o nm e t h o d ，a n dw a si m p r o v e do np r e v i o u s r e s e a r c hf o u n d a t i o n i th a db e e ne s t a b l i s h e dt h a tn e wm o d e l so fa n tc o l o n ya l g o r i t h mi nw a t e r r e s o u r c e so p t i m i z a t i o na n dp r e d i c t i o n ，a n dh a db e e ni m p l e m e n t e db ym a t l a bl a n g u a g e t h e m o d e lc o u l db e t t e rs o l v em u l t i - e l e m e n tc o m p l i c a t e dp r o b l e m so f w a t e rr e s o u r c e ss y s t e mi np r a c t i c e a n de f f e c tw a sg o o d t h i sp a p e ro b t a i n e dt h r e ea s p e c t so fa c h i e v e m e n t sb e l o w ： ( 1 ) t h i sp a p e ri n t r o d u c e dam o d e lo fa n tc o l o n ya l g o r i t h mo fl o c a lr a n d o m n e s ss e a r c h s t r a t e g y , w h i c ht h em o d e lc o u l di m p r o v es o l v i n gp r e c i s i o na n ds e a r c h i n ge f f i c i e n c yt oc o m m o n f u n c t i o no p t i m i z a t i o n t h em o d e lh a db e e na p p l i e ds u c c e s s f u l l yi n c r i t i c a ld e p t hc a l c u l a t i o nf o r s e c t i o ni nd i t c ha n dc o m p u t i n gw a t e rd e p t ho fs e c t i o nd o w n s t r e a mo v e r f l o wd a m ，a n de f f e c tw a s b e r e lp r e c i s i o nw a sh i g h e r ( 2 ) c o m b i n a t i o np o i n th a db e e nf o u n dt h a ta n tc o l o n ya l g o r i t h ma n dm a r tw a v e l e tn e u r a l n e t w o r k m u l t i d i m e n s i o n a la n tc o l o n ya l g o r i t h mi nc o n t i n u o u ss p a c e si n s t e a d e dg r a d i e n td e s c e n t m e t h o d ，a n da d j u s t e dw e i g h tv a l u e so fb pn e t w o r ka n de x p a n s i o na n dt r a n s l a t i o n a lc o e f f i c i e n t so f w a v e l e tf u n c t i o n ，w h i c hm a r ro fi ti n s t e a d e ds t y p ea c t i v a t i o nf u n c t i o ni nb pn e t w o r k ，a n d p o p u l a t i o ns t a n d a r dd e v i a t i o ni nw a v e l e tn e t w o r kw a su s e da so b j e c t i v ef u n c t i o no fa n tc o l o n y a l g o r i t h m t h er e s u l t so ft h em o d e lw a ss a t i s f i e di nf o r e c a s t i n gr i c ew a t e rr e q u i r e m e n t ( 3 )a n tc o l o n ya l g o r i t h mh a dv e r y g o o da b i l i t yo fg l o b a lo p t i m i z a t i o n c o n t i n u o u s m u l t i - d i m e n s i o n a la n tc o l o n ya l g o r i t h m - - g e n e t i ca l g o r i t h mh a db e e np r o p o s e do nr e a lc o d i n gb a s e d a c c e l e r a t i n gg e n e t i ca l g o r i t h m t h en e wm o d e lh a db e e na p p l i e di ni r r i g a t i o nr e g i m eo fr i c ea t c h a h a y a n gi r r i g a t i o na f e a c a l c u l a t i n ga n dp r a c t i c a lw a t e rw e r es a m eb a s i c a l l y , w h i c hp r o v e dt h a t t h em o d e lh a dv e r yg o o dp r a c t i c a lv a l u e b a s e do nt h ea b o v ee s t a b l i s h e dm o d e l ，t h et h e o r ya n dt h ep r a c t i c eh a db e e na s s o c i a t e d o r g a n i c a l l y t h er e s e a r c hr e s u l to f f e r e dn e wm e t h o df o rt h ec o m p l e xn o n l i n e a rp r o b l e mi nt h e i i a b s t r a c t d o m a i no fh y d r o l o g ya n d w a t e rr e s o u r c e a tt h es a m et i m e ，t h ea p p l i e dr a n g eo fa n tc o l o n y a l g o r i t h mm o d e lw a sa m p l i f i e d m o r e o v e r , t h et h e o r yw a si m p r o v e da c c o r d i n g l y k e yw o r d s ：w a t e rr e s o u r c e ss y s t e m ；a n tc o l o n ya l g o r i t h m ；a r t i f i c i a ln e u r a ln e t w o r k ；g e n e t i c a l g o r i t h m ；o p t i m i z a t i o n ；p r e d i c t i o n c a n d i d a t e ：y a n gn a s p e c i a l i t y ：s o i la n dw a t e ro f a g r i c u l t u r a le n g i n e e r i n g s u p e r v i s o r ：f uq i a n g i l l 硕上研究生学位论文独创声明和使用授权 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含未获得 ( 洼! 翅遗直基丝益墓挂别童盟笪：奎拦互窒2 或其他教育机构的学位或证 书使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示谢意。 学位论文作者签名粥柳 吼押留年，月日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权学校可以将学位论文的全部或部分内容编入有关数据库进行检索，可以 采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解 密后适用本授权书) 学位论文作者签名：罚汤翎f 日期：扣g 年月日 导师签名：钭双 嗍榔年夥日 绪论 1 绪论 1 1 水资源系统优化概述 水资源系统优化是各种优化方法在水资源系统中的应用过程，其中称目标函数、优化变 量和约束条件为水资源系统优化的三要素。水资源系统的规划、设计、运行，管理中有许多 问题的目标函数和约束条件是复杂的非线性函数，如区域水资源的最优配置、水利工程规模 的最优选择、水库和水电站参数的最优选择、水电站的最优运行管理等问题。水资源系统优 化，要求在有限的水资源条件下，通过系统内部各变量之间、各变量与各子系统之间、各子 系统之间、系统与环境之间的组合和协调，最大限度地满足生产、生活、生态等各用水部门 的可持续利用要求，使水资源系统具有最好的社会经济效益和生态环境效益。显然，研究各 种水资源系统优化问题在系统工程理论和实践中都具有十分重要的意义。 不同的水资源系统优化问题，水资源系统优化方法的求解过程一般也会不同。从方法论 的角度看，水资源系统优化方法的一般步骤大致可以分为如下6 步( 汪应洛，2 0 0 1 ；孙德 敏。1 9 9 7 ) ：确定被优化系统的目标体系，并用经济、时间、精度、实物等性能指标表示。目 标体系不同，相应的优化结果就不同。性能指标选得是否合理直接影响到所得优化结果的实 用性。选择影响系统目标的独立的优化变量集。确定各优化变量的取值范围即约束条件。 约束条件可以用等式、不等式和集合形式等表示，可以是显式约束，也可以是隐式约束。 确定系统优化模型的结构形式，即用目标函数和约束条件来描述各优化变量之间、各优化变 量与各性能指标之间的关系式。针对所确定的系统优化模型的结构形式，运用相应的解析 优化方法或数值优化方法等进行最终求解。对所得优化结果的合理性、计算精度和敏感性 等进行分析和验证。可对优化结果进行协调、修正、评定，确定最终的系统优化结果，作为 决策依据，也可根据优化结果的实际应用效果对以上步骤进行不断修改和完善，因此，复杂 水资源系统的优化常常是一个多次迭代的过程。 能否顺利求解水资源系统优化问题的关键表现在如下几个方面( 汪树玉，1 9 9 3 ) ：目标函数 的数目、关系、层次结构、性态、连续性、可微性、凸性、非线性、可计算性等。优化变 量的数目、类型及其关系、取值范围等。约束条件的数目、关系、连续性、可微性、凸性、 非线性等。初始可行点是否易于获取、可行域的复杂程度、可行域外的目标函数和约束函 数是否可计算。系统优化模型中各参数的估计值的可靠性和精度如何。能否对最优解的 大致范围、是否存在多个局部最优解等问题有初步的了解和估计。能否理解所用的算法、 能否获得或编制该算法的可靠程序。 受天文因子、气候因子、水文气象因子、植被土壤因子、地貌因子、地质因子和人类活 动因子等众多因子的综合影响，实际水资源系统优化问题都是十分复杂，水资源系统优化方 法至今仍是目前水资源系统工程界的热点和难点之一，就国内外研究现状而言，这方面的研 究仍处于积极探索和不断发展阶段。 东北农业大学t 学硕十学位论文 1 2 最优化问题 优化方法涉及的工程应用领域很广，问题的种类及性质繁多。归纳而言，最优化问题可 分为函数优化问题和组合优化问题两大类，其中函数优化的对象是一定区间内的连续变量， 而组合优化问题的对象是解空间中的离散状态( 王凌，2 0 0 1 ) 。本文研究的主要问题是将蚁群优化 策略应用于连续空间中的函数优化问题，所以下文仅介绍函数优化中的若干问题。另外，最 优化包括最大化和最小化，鉴于两者可以相互转换，因此若不加特殊说明，文中讨论的最优 化仅指最小化。 最优化问题通常可以表示为 m i 矿( z ) s t x s( 卜1 ) 其中x = 仁。，工2 ，工。夕r 是p 维向量，5 是可行域。由于很多实际的优化问题比较复杂， 在解空间中存在多个极值点。下面给出局部最优与全局最优的定义： 定义1 2 1 ：4 殴f ( x ) 为目标函数，s 为可行域，若存在x 的s 邻域 丑： xl x - x 肛彬 o ( 1 - 2 ) 使得对每个x s n b ，斤x j f ( x 夕成立，则称x 为斤x 夕在s 上的局部最优解。 定义1 2 2 - 设厂( x ) 为目标函数，s 为可行域，x s ，若存在可行解x ，使得对每一个 x s ，x 夕f ( x 夕成立，则称x 为x 夕在s 上的全局最优解。 由于算法的结构以及搜索机制的不同，有些算法具有很强的局部搜索能力，能够高效地 找到问题的更优解；而另一些算法的全局搜索能力较强，有能力求取问题的全局最优解。 1 2 1 邻域函数与局部搜索 邻域函数是优化中的一个重要概念，其作用就是指导如何由一个( 组) 解来产生一个( 组) 新 的解。在函数优化中，利用距离的概念通过附加扰动来构造邻域函数是最常用的方式，如 x7 = x + 刁占，其中x7 为新解，x 为旧解，刁为尺度参数，占为满足某种概率分布的随机数或 白噪声或混沌序列或梯度信息。采用不同的概率分布( 如高斯分布、柯西分布、均匀分布等) 或下降策略，将实现不同性质的状态转移。 局部搜索算法是基于贪婪思想利用邻域函数进行搜索的，它通常描述为：从一个初始解 出发，利用邻域函数持续在当前解的邻域中搜索比它好的解，若能够找到这样的解，就把它 作为新的当前解，然后重复上述过程，否则结束搜索过程，并以当前解作为最终的解。可见， 2 绪论 局部搜索算法尽管具有通用易实现的特点，但搜索性能完全依赖于邻域函数和初始解。邻域 函数设计不当或初始解选取不合适，则算法最终的性能会很差。同时，贪婪思想无疑使算法 丧失全局寻优的能力，也即算法在搜索过程中无法避免陷入局部极小点。 1 2 2 全局搜索 鉴于局部搜索算法的上述存在的问题，智能优化算法，如模拟退火法、遗传算法、免疫 算法、禁忌搜索、混沌搜索、神经网络以及蚁群优化算法等，从不同角度利用不同的搜索机 制和策略来提高算法的全局优化性能。 算法的全局寻优性能是在算法研究过程中始终关注的一个关键问题，对于较复杂问题的 求解，人们只能寻求找到更优良的解，而无法找到其最优解，或者无法证明其找到的解就是 最优解，如大规模的t s p 问题。从而为开发性能更好的全局优化算法提出了巨大的挑战，也 提供了一个很好的机遇。本文重点研究的连续蚁群优化算法就是一类性能良好的全局寻优算 法。 1 3 经典优化算法 经典的优化方法根据问题的性质不同，通常将问题划分为线性规划、非线性规划以及随 机规划、非光滑规划、多目标规划、几何规划、整数规划等，相应的有一些较成熟的常规算 法，如应用于线性规划问题的单纯形法，应用于非线性规划的n e w t o n 法、共扼梯度法、序列 二次规划法等，应用于整数规划问题的分支定界法、割平面法和动态规划法等( 马振华等 1 9 9 7 ) 。这些方法一般有较严格的数学理论，但当模型复杂的时候，如变量的维数多、约束方 程数多、非线性强等，或模型结构复杂，不能用显式的方程来表达时，这些方法往往不能进 行有效求解，或者求解的时间过长，如组合优化问题中的组合爆炸：或者求解的效果差，如 陷入局部极值、初始值直接影响寻优的结果等( 李晓磊，2 0 0 3 ) 。 1 4 现代启发式算法 人们总是期望能够尽快地找到问题的最优解，早期主要着重于研究能够找到问题最优解 的算法，即问题的最优算法，通过该算法可以求得该问题每个实例的最优解，它是问题求解 的一种理想方法。然而，在某些情况下，特别是在实际问题中，最优算法的计算时间使人无 法忍受或因问题的难度使其计算时间随问题规模的增加以指数速度增加( 刑文训等1 9 9 9 ) 。因 此，相对于最优算法，提出了启发式算法( h e u r i s t i ca l g o r i t h m ) 。启发式算法有下面这两种定义： 一种定义为：启发式算法是一个基于直观或经验构造的算法，在可接受的计算耗费( 指计 算时间、占用空间等) 下给出待求解问题的一个可行解，该可行解与最优解的偏离程度不一定 事先可以预计。 3 东北农业大学t 学硕十学位论文 另一种定义为：启发式算法是这样一种技术。这种技术使得在可接受的计算耗费内去寻 找最好的解，但不一定能保证所得到的解的可行性和最优性，甚至在多数情况下，无法阐述 所得到的解同最优解的近似程度。 上述启发式算法的两个定义中，一个共同的特点是不考虑算法所得到解与最优解的偏离 程度。如果采用分析最坏情况的误差界限的概念来评价启发式算法，则可以将近似算法定义 如下( 刑文训等1 9 9 9 ) ： 定义：设a 是一个问题，记问题a 的任何一个实例i 的最优解和启发式算法h 解的目标 值分别为z o p t f ，) 和z 封f ，j ) 。于是对于某个占0 ，称h 是a 的占近似算法( s - a p p r o x i m a t i o n a l g o r i t h m ) ，当且仅当 i z h f ，u z o p t f ，川i z o p t f ，j 川， v i a( 1 3 ) 上面的定义给出启发式算法和近似算法两个概念的联系和区别。启发式算法概念定义的 算法集合包含了近似算法概念定义的算法集合。近似算法强调给出的算法最坏情况下的误差 界限，而启发式算法不考虑偏差程度。由于许多复杂优化问题的最坏情况误差界估计需要很 强的数学基础和较强的技巧，甚至一些问题很难或无法给出最坏情况误差界，而实际问题又 迫切需要求解的方法，因此，只能通过启发式算法解决问题。 早在2 0 世纪4 0 年代末期，由于实际问题的需要，人们已提出了一些解决实际问题的快 捷有效的启发式算法，有代表性的工作是1 9 4 8 年p o l y a 的著作( 1 9 4 8 ) 。随着2 0 世纪6 0 7 0 年 代对数学模型及最优解算法的重视，这些算法被称为“快速与丑陋( q u i c ka n dd i r t y ) ”方法。 随着2 0 世纪7 0 年代算法复杂性理论的完善，我们不再强调一定要到达最优解，因此促使8 0 年代初兴起的现代启发式优化算法在今天得到了巨大的发展。 2 0 世纪8 0 年代以来，人们通过模拟自然现象或过程，基于仿生的思想，提出了一系列新 颖的启发式优化算法一m e t a h e u r i s t i c ，有人称之为自然启发式算法，直译应该为元启发式算 法，文献中更多的将这类方法统称为现代启发式算法，本文中我们沿用现代启发式算法来表 述m e t a h e u r i s t i c 的含义。这类算法中包括有进化算法、模拟退火、禁忌搜索、免疫算法等。 算法思想和内容涉及数学、物理学、生物进化、统计力学、人工智能等。以前通常将模拟退 火、遗传算法、禁忌搜索以及人工神经网络统称为四大现代启发式算法( 王凌等2 0 0 0 ) 。随着 新型算法的相继提出，现代启发式算法的范围也在不断扩大。现代启发式算法是一类随机型 的搜索算法，因其只需要适应度信息而无需问题其他特殊信息，以及算法表现出的高效的全 局优化性能等优点，为解决复杂问题的全局最优解提供了新的思路和手段，在诸多领域得到 广泛的关注和应用( 丛明煜等2 0 0 3 ) 。 1 4 1 遗传算法 遗传算法是最广为人知的进化算法。1 9 7 5 年，h o l l a n d 总结自己的研究成果，发表了遗传 算法领域的奠基之作一自然及人工系统的适应性( 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 l s y s t e m s ) ，书中h o l l a n d 为所有的适应系统建立了一种通用理论框架，并展示了如何将自然界 4 绪论 的进化过程应用到人工系统中去。经过多年的发展，遗传算法已经发展成为了一大类算法， 在理论上和实际应用中都取得了很大的进展。 构成基本遗传算法的要素主要有：染色体编码方法、个体适应度值评价、遗传算子以及 算法参数设置等等。 1 解的编码方法常见的编码方法为二进制编码，将问题的可行解使用一个二进制符号串 来编码，表示种群中的一个个体，即染色体，符号串中的每一个位置称为染色体的一个基因， 对应位置的符号( o 或者1 ) 是该基因的值。求解结束后，将最优个体的二进制串反编码为问题 的解的形式。另一种常用的编码方式是实数编码，针对连续空间中优化问题，直接用问题可 行解的解向量作为染色体，此时，向量中的每一个分量分别表示染色体的一个基因。 2 适应度函数在遗传算法中，遗传操作主要通过适应度函数( f i t n e s sf u n c t i o n ) 的导向来实 现的。它是用来评估一个染色体相对于整个群体的优劣的相对值的大小。 3 遗传算子基本遗传算法通常使用下述三种遗传算子： 选择算子：按照某种策略从父代中挑选个体进入中间代。 交叉算子：随机地从中间群体中取得两个个体，并按照某种交叉策略使两个个体互相交 换部分染色体码串，从而形成两个新的个体。 变异算子：通常按照一定的概率，改变染色体中的某些基因的值。 4 遗传算法的运行参数有以下四个运行参数需要提前设定：群体大小( 加，即群体中所 含个体数量；最大进化代数( d ；交叉概率( 只) ：变异概率( 厶) 。这四个参数对遗传算法的求解 结果和求解效率都有很大的影响。因此，要合理设定这些参数，才能获得较好的效果。 1 4 2 人工神经网络 人工神经网络( a n n ) 是通过数学方法对人脑若干基本特性进行的抽象和模拟，是一种 模仿人脑结构及其功能的非线性信息处理系统。现代神经生理学和神经解剖学的研究结果表 明，人脑是极其复杂的，大约由1 0 一1 0 1 2 个神经元交织在一起，构成一个网状结构。被认为 是最复杂、最完美、最有效的一种信息处理系统，而人工神经网络就对人脑的功能作了很好 的模拟。 自1 9 4 3 年心理学家w m c c u l l o c h 和数学家w p i t t s 合作提出了神经元和神经网络最早的 数学模型( m c c u l l o c h p i t t s ，m p 模型) 以来，a n n 的发展几经波折，直到2 0 世纪8 0 年代 初，h o p f i e l d 提出h o p f i e l d 网络，国际上再次掀起了a n n 的研究热潮。1 9 8 7 年国际神经网络 学会诞生，1 9 8 8 年学会的正式杂志n e u r a l n e t w o r k s 创刊，1 9 9 0 年电气和电子工程师学会i e e e ( i n s t i t u t ef o re l e c t r i c a la n de l e c t r o n i ce n g i n e e r s ) 的神经网络会刊问世，从此a n n 在各个领域 蓬勃发展，并取得了丰富的研究成果。 1 9 9 0 年，由e c k h o m 等对猫的视觉皮层神经元脉冲串同步振荡现象的研究，得到了哺乳 动物神经元模型，并由此发展形成了脉冲耦合神经网络( p u l s ec o u p l e dn e u r a ln e t w o r k s ， p c n n ) 模型，国际上称p c n n 是第三代人工神经网络。脉冲耦合神经网络的出现为人工神经 网络领域注入了新鲜血液，同时必将拓宽a n n 的应用领域，不断深化a n n 的理论基础。 5 东北农业人学工学硕：匕学位论文 1 4 3 蚁群优化算法 2 0 世纪9 0 年代初，人们在研究社会性生物群体的行为的时候发现，群体中单个个体的行 为很简单，随机性大，但整个群体在整体上呈现出高度的有组织性，比如蚁群能有效地找到 从巢穴到食物源之间的最短路径；鸟群在未知空间中捕食等。这引起了人们对生物群体的智 能特征的关注，相继提出了多种群智能( s w a r mi n t e l l i g e n c e ) 优化算法。 所谓群智能，是指一种通过大量数目的智能体群来实现的智能方式。单个的智能个体本 身，在没有得到智能体群的总体信息反馈的时候，在解空间中的运动是完全没有规律的( 吴启 迪等2 0 0 4 ) 。研究社会性生物群体的科学家发现群体中个体之问存在高度白组织的协作行为， 它们的协调行为通过个体之间的交互行为直接实现，或者通过个体与环境的交互行为间接实 现。虽然这些交互行为非常简单，但是他们聚在一起却能快速有效地解决一些难题。这种潜 在方式的集群智能已经逐渐为人们所认识，并得到应用( 李士勇，2 0 0 4 ) 。 作为群智能的典型实现，模拟生物蚁群智能寻优能力的蚁群优化算法( a n tc o l o n y o p t i m i z a t i o n ，简称a c o ) ( d o f i g o m ，2 0 0 4 ) 和模拟鸟群运动模式的粒子群优化算法( p a r t i c l e s w a r mo p t i m i z a t i o n ，简称p s o ) ( 曾建潮等2 0 0 4 ) 正在受到学术界的广泛关注。由于蚁群优化 算法所提出的时间相对较早，得到了众多学者较为广泛的研究。这也是本文研究的重点和出 发点。 1 4 3 1 蚁群算法的起源 蚂蚁是地球上最常见、数量最多的昆虫种类之一。这些昆虫的群体生物智能特征引起了 一些学者的注意。意大利学者m d o f i g o ，v m a n i e z z o 等人在研究蚂蚁觅食行为时发现，蚂蚁总 能找到巢穴与食物源之间的最短路径。经研究发现，蚂蚁的这种群体协作功能是通过一种遗 留在其来往路径上的叫做信息素( p h e r o m o n e ) 的挥发性化学物质来进行通信和协调的。化学通 信是蚂蚁采取的基本信息交流方式之一。在蚂蚁的生活习性中起着重要的作用。通过对蚂蚁 觅食行为的研究，他们发现，整个蚁群就是通过这种信息素进行相互协作，形成正反馈，使 多个路径上的蚂蚁逐渐聚集到最短的那条路径上来的。 这样，m d o r i g o 等人于1 9 9 1 年首先提出了蚁群算法。其主要特点就是：通过正反馈、分 布式协作来寻找最优路径。这是一种基于种群寻优的启发式搜索算法，充分利用了生物蚁群 能够搜索到从巢穴至食物间最短路径的群体寻优特性。利用蚁群算法的寻优过程与旅行商问 题之间的相似性，得到了具有n p 难度的旅行商问题的最优解答。 充分利用了生物蚁群在觅食过程中能通过环境共享和间接地传递信息，从而搜索到从巢 穴至食物间最短路径的群体寻优特性。利用蚂蚁觅食过程与旅行商问题之间的相似性，蚁群 算法得到了具有n p 难度的旅行商问题的最优解答。 6 绪论 1 4 3 2 蚁群算法的发展 自1 9 9 1 年意大利学者m d o r i g o 首次提出了蚂蚁系统( a n ts y s t e m ，简称a s ) 开创了蚁群优 化算法研究的先河( m d o r i g o ，vm a n i e z o o ，a c o l o m i ，1 9 9 1 ) 。此后，经d o r i g o ，c o l o m i ，s f i i t z l e ， h o o s b i l c h c v , g a m b a r d e l l a 等多位学者的发展，从蚂蚁系统( a n ts y s t e m ，a s ) 开始，先后有 a n t q 、蚁群系统( a n tc o l o n ys y s t e m a c s ) 、最大最小蚂蚁系统( m a x m i n a s ，m m a s ) 等，1 9 9 9 年d o r i g o 在这些改进的基础上提出了蚁群优化( a n tc o l o n yo p t i m i z a t i o n ) 的通用框架，使之有 更坚实的基础和良好的性能，其应用范围也由t s p 拓展到q a p 、车间调度、交通路由、资源 分配、图着色、大规模集成电路设计、通讯网络中的路由问题以及负载平衡等问题。正因为 如此，为进一步促进世界范围内相关领域的研究工作，i e e e 进化计算会刊于2 0 0 2 年8 月出版 了蚁群优化算法特刊，在其中以蚁群算法的成功应用领域离散优化问题求解为重点，发 表了许多优秀的研究论文，集中体现了蚁群算法研究和应用领域的成功进展。 自1 9 9 8 年起，每隔两年就要在比利时的布鲁塞尔举行一次蚁群算法方面专门的国际研讨 会，2 0 0 6 年9 月4 号到7 号第五届蚁群优化与群智能国际研讨会又将在比利时的布鲁塞尔拉 开帷幕。会议的目的是将有着不同兴趣爱好的研究入员和实践者聚在一起，研究蚁群优化的 本质及实现模式。涉及的学科领域从生物学到物理学、工程学、和计算机科学。它标志着蚁 群算法的研究已经得到了国际上的广泛支持。研讨会体现了蚁群算法研究和应用的最新成果 与研究方向，对推动蚁群优化算法的统一发展作出了重要贡献。 关于蚁群优化思想在连续空间的优化问题中的应用也逐渐受到学者门的关注，提出了一 些新颖的思想和方法。这是本文研究的核心问题，在后文中会有详细的论述。 1 5 本文结构 本文共七章。本章是全文的第一章，简要地介绍了本文的研究基础以及研究背景。 第二章主要介绍基本蚁群优化算法，系统地综述了基本蚁群优化算法的生物学基础，算 法模型及结构，算法的局限性，算法在水资源领域的应用以及在理论上取得的进展。并与其 他基于种群的优化算法进行了比较。 第三章中，首先分析了基本蚁群优化算法本质上的离散性，并提出了对其进行连续性改 造的方法。在此基础上详细介绍了一维与多维连续蚁群优化算法的模型。并对算法的性能进 行了客观地分析与讨论。 第四章从全局蚂蚁和局部蚂蚁的寻优特征入手，详细分析了第三章中提出的连续蚁群优 化算法的寻优机理，并应用于不规则断面明渠临界水深计算、泄水建筑物下游收缩断面水深 具体计算中。同时指出，蚁群优化算法( a c o ) 是一类比遗传算法( g a ) 演化机制更简洁的进化算 法，并应用于全空间探索寻优过程中，同时对算法参数的选取进行了研究。 第五章受生物蚂蚁在连续空间中觅食行为的启发，将优化函数的连续型蚁群算法与小波 神经网络耦合，用蚁群算法优化神经网络的权值和小波参数，找到了蚁群算法中信息素更新 的最佳衡量标准，且建立了基于蚁群优化的小波神经网络模型( c a c a w n n ) ，同时对三江 7 东北农业大学工学硕上学位论文 平原富锦市1 9 8 5 至2 0 0 1 年的井灌水稻区全生育期需水量进行了预测，为制定合理的灌溉制 度、提高水利用率提供科学依据。 第六章将简洁、快速模式搜索的蚁群算法作为遗传算法局部进化策略，且连续空间的蚁 群算法与实码加速遗传算法进行耦合，发挥了两种算法的各自优势，提出了一种新的优化模 型一一连续蚁群遗传算法( a n tc o l o n ya l g o r i t h mi nt h ec o n t i n u o u ss p a c eo p t i m i z a t i o n p r o b l e m s - - r e a lc o d i n gb a s e da c c e l e r a t i n gg e n e t i ca l g o r i t h m ，缩写a c a c r a g a ) ，并很 好的应用在查哈阳灌区灌溉制度优化中，不仅验证了算法的可行性，且为灌区的灌溉管理提 供了有效的科学依据。 第七章对全文工作进行了总结，并介绍了当前连续蚁群优化算法研究中存在的问题，以 及今后研究的一些展望。 8 基本蚁群算法 2 基本蚁群算法 1 9 9 8 年1 0 月1 4 - - 1 6 日，首届蚁群优化国际研讨会在比利时布鲁塞尔召开。此次会议的 目的是将有着不同兴趣爱好的研究人员和实践者聚在一起，研究蚁群优化的本质及实现模式， 涉及的学科领域从生物学到物理学、工程学、和计算机科学。会议考虑的主要问题是结构化 复杂行为的分析与拟合，包括简单通信智能体的大量合成，其中把蚁群系统作为模型基础， 它标志着蚁群算法的研究已经得到了国际上的广泛支持( 吴启迪等2 0 0 4 ) 。此后，每两年都会 召开一次这样的国际研讨会，2 0 0 6 年第5 届蚁群优化及群智能国际研讨会将于9 月4 日到7 日在比利时的布鲁塞尔召开。蚁群优化算法在理论和应用上都取得了很大的进展，并成为相 关领域的新的研究热点。 本章中主要对蚁群算法的研究成果作了系统综述：首先回顾了蚁群算法的基本原理，并 与其它基于种群进化计算方法进行比较，接着总结了蚁群算法的一些理论研究成果，然后概 述了基本蚁群优化算法的应用进展，最后介绍了蚁群优化算法在水资源系统优化中的应用情 况与算法局限性分析。 2 1 蚁群优化算法 蚂蚁是种最古老的社会性昆虫，起源于约1 亿年前，大约与恐龙生活在同个时代。 这种看似简单的小东西很早就引起了人们的注意。单个蚂蚁的结构和行为很简单，但是由这 些简单的个体组成的群体一蚁群，却表现出高度结构化的社会组织和极强的自组织行为，体 现出复杂系统的一般特性。研究表明，蚁群有着奇妙的信息系统，其中包括视觉信号、声音 通讯和更为独特的无声语言，即包括化学物质、触角信号和身体动作在内的多个募集系统， 来策动其它个体( 李士勇，2 0 0 4 ) 。 2 1 1 蚁群算法的基本原理 像蚂蚁这类群居昆虫，虽然没有视觉，却能找到由蚁穴到食物源的最短路径，原因是什 么呢? 虽然单个蚂蚁的行为极其简单，但由这样的单个简单的个体所组成的蚁群群体却表现 出极其复杂的行为，能够完成复杂的任务，不仅如此，蚂蚁还能够适应环境的变化，如：在 蚂蚁运动路线上突然出现障碍物时，蚂蚁能够很快重新找到最优路径。蚂蚁是如何完成这些 复杂任务的呢? 人们经过大量的研究发现，蚂蚁个体间是通过一种称之为信息素( p h e r o m o n e l 的物质进行信息传递，从而能相互协作，完成复杂的任务。蚂蚁之所以表现出复杂有序的行 为，个体之间的信息交流和相互协作起着重要的作用。 蚂蚁在运动过程中，能够在它所经过的路径上留下该物质，并以此指导自己的运动方向， 蚂蚁倾向于朝着该物质强度高的方向移动。因此，由大量蚂蚁组成的蚁群的集体行为表现出 一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后者选择该路径的概率越大。蚂蚁个 9 东北农业大学工学硕士学位论文 体之间就是通过这种信息的交流达到搜索食物的目的。这里，用一个形象化的图示来说明蚂 蚁群体的路径搜索原理和机制： 假定障碍物的周围有两条道路可从蚂蚁的巢穴到达食物源( 如图2 1 ) ：n e s t a b d f o o d 和 n e s t a c d f o o d ，分别具有长度4 和6 。蚂蚁在单位时间内可移动一个单位长度的距离。开始 时所有道路上都未留有任何信息素。 图2 1 蚁群系统示意图 f i g 2 1a n tc o l o n ys y s t e m c h a r t 在f = 0 时刻，2 0 只蚂蚁从巢穴出发移动到a ，它们以相同概率选择左侧或右侧道路，因 此平均有l o 只蚂蚁走左侧，1 0 只走右侧； 在，= 4 时刻，第一组到达食物源的蚂蚁将折回： 在t = 5 时刻，两组蚂蚁将d 点相遇。此时b d 上的信息素数量和c d 上的相同，因为各 有1 0 只蚂蚁选择了相应的道路，从而有5 只返回的蚂蚁将选择b d 而另5 只将选择c d ； 在f = 8 时刻，前5 只蚂蚁将返回巢穴，而a c 、c d 、b d 上各有5 只蚂蚁； 在t = 9 时刻，前5 只蚂蚁又回到a 并且再次面对往左还是往右的选择； 这时，a b 上的轨迹数是2 0 而a c 上是1 5 ，因此将有较为多数的蚂蚁选择往左，从而增 强了该路线的信息素。随着该过程的继续，两条道路上的信息素数量的差距将越来越大，直 至绝大多数蚂蚁都选择了最短的路线。正是由于一条道路要比另一条道路短，因此，在相同 的时间区间内，短的路线会有更多的机会被选择。 蚁群算法是一种随机搜索算法，与其他模型进化算法一样，通过侯选解组成的群体的进 化过程来寻求最优解，该过程包含两个阶段：适应阶段和协作阶段。在适应阶段，各侯选解 根据积累的信息不断调整自身结构；在协作阶段，侯选解之间通过信息交流，以期望产生性 能更好的解。 作为与遗传算法同属一类的通用型随机优化方法，蚁群算法不需要任何先验知识，最初 只是随机地选择搜索路径，随着对解空间的“了解”，搜索变得有规律，并逐渐逼近直至最终 达到全局最优解。蚁群算法对搜索空间的“了解”机制主要包括三个方面： ( 1 ) 蚂蚁的记忆。一只蚂蚁搜索过的路径在下次搜索时就不会再被选择，由此在蚁群算法 中建立禁忌列表来进行模拟： l o 基本蚁群算法 ( 2 ) 蚂蚁利用信息素( p h e r o m o n e ) 进行相互通信。蚂蚁在所选择的路径上会释放一种叫做信 息素的物质，当同伴进行路径选择时，会根据路径上的信息素进行选择，这样信息素就成为 蚂蚁之间进行通讯的媒介。 ( 3 ) 蚂蚁的集群活动。通过一只蚂蚁的运动很难到达食物源，但整个蚁群进行搜索就完全 不同。当某些路径