（计算机软件与理论专业论文）“遗传—蚁群”混合算法及其在水量调度中的应用.pdf

摘要 遗传算法是模拟自然界生物进化过程的随机化搜索算法，其主要 特点是采取群体搜索策略和在群体中个体之问进行信息交换，具有很 多优良性质和使用价值，然而存在对信息利用不足，求解易于过早收 敛的缺点。蚁群算法是一种随机搜索算法，与其它模拟进化优化算法 一样，通过由候选解组成的群体的进化过程来寻求最优解，它比遗传 算法具有更好的适应性，但算法的初期信息不足，求解速度较慢。 本文分别论述了两种算法的原理、模型和应用之后，提出了一种 新的直观的可用于连续性空间( 一般函数) 优化的“遗传一蚁群”混合 算法模型，该模型强调处理优化问题时把遗传算法与蚁群算法结合， 对实际问题先用遗传算法进行初步求解，然后在此基础上运用蚁群算 法求最优解。该新算法汲取了两种算法的优点，克服了各自的缺陷， 实现了优势互补。该“遗传一蚁群”混合算法被成功应用于水量预测 和水量调度问题的求解中，实践表明这种算法确实综合了遗传算法和 蚁群算法的优点，特别强化了求优化解的微调过程，有一定的实用价 值。文章最后对“遗传一蚁群”混合算法的收敛性进行了初步分析。 关键词遗传算法，蚁群算法，收敛性 a b s t r a c t g e n e t i ca l g o r i t h mi sar a n d o ms e a r c h i n gm e t h o du s i n gp r o b a b i l i t y a n di t sb a s i ct h e o r e mi st os i m u l a t et h eb i o l o g ye v o l u t i o n i tu s e st h e p o p u l a t i o n s e a r c hm e t h o da n de x c h a n g e st h ei n f o r m a t i o nb e t w e e nt h e i n d i v i d u a l s g e n e t i ca l g o r i t h mh a sal o to fg o o dp r o p e r t i e sa n dm e r i t s ， b u ti ts o m e t i m e sh a sp r e m a t u r ec o n v e r g e n c ea n dc a n tm a k em u c ho ft h e s y s t e mi n t e r e s t s a n tc o l o n ya l g o r i t h mi sa l s o ar a n d o ms e a r c h i n g m e t h o db a s e do nt h eb i o l o g yp o p u l a t i o ne v o l u t i o nl i k eo t h e re v o l v i n g o p t i m i z a t i o na l g o r i t h m i t sa d j u s t a b i l i t yi sb e t t e rt h a ng e n e t i ca l g o r i t h m b u ti th a s n te n o u g hi n f o r m a t i o na tf i r s ta n dt h er a t eo fc o m p u t i n gi s l o w e rt h a ng e n e t i ca l g o r i t h m an e wm e t h o do fa m a l g a m a t i v ea n tc o l o n ya l g o r i t h mw h i c hc a nb e u s e df o r s o l v i n go p t i m i z a t i o np r o b l e m s i nc o n t i n u o u s s p a c e ( g e n e r a l f u n c t i o n 、i sp r o p o s e d t h i sm e t h o di sb a s e do nt h ec o m b i n a t i o no f g e n e t i c a l g o r i t h m a n da n t c o l o n ya l g o r i t h m ，i td e v e l o p se n o u g h a d v a n t a g eo ft h et w oa l g o r i t h m s t h ea m a l g a m a t i v ea l g o r i t h mi su s e di n t h ef o r e c a s ta n dt h ea l l o c a t i o no fw a t e rc a p a c i t ys u c c e s s f u l l y o u ri d e ai s v a l i d a t e di nt h i s p r a c t i c e t h ec o n v e r g e n c ec h a r a c t e r i s t i co ft h en e w a l g o r i t h mi st ob ea n a l y z e da tl a s t h o w e v e r , t h ep r e c i s i o no ft h en e w a l g o r i t h mi ss t i l ln e e dt ob es t u d i e d k e yw o r d sg e n e t i ca l g o r i t h m ，a n tc o l o n ya l g o r i t h m ，c o n v e r g e n c e 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共 同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名： f ：亟耋日期：型年二细兰日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位 论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论 文：学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名：盟丛年! 月竺日 硕士学位论文 笫一章绪论 第一章绪论 1 1 水量调度问题的提出 水是人类生存的生命线，人类因水而生存因水而发展。然而，本世纪人类却 面l 临着更加严重的水资源问题。水资源短缺几乎成为世界性的问题。我国是水资 源贫乏的国家，人均水资源仅为世界平均水平的1 4 。1 9 9 8 年，黄河流域用水量 为多年平均水资源量的6 8 ，已经大大超过国际上认可的合理利用率( 4 0 ) 。 因此对水资源实行统一规划、统一配置、统一调度势在必行。在水资源管理领域 中，发达国家的研究开始的很早，他们在水调方案编制上更加注重生态、经济、 环境和社会可持续发展等因素。在我国水量分配中更注重的是水权思想，尤其是 在些易于干旱的流域，随着技术的进步和社会可持续发展的要求，我国的水资 源管理面临新的机遇和挑战。 水量调度就是如何合理分配水资源，简称水调。目的就是要如何合理的分配 有限的水资源，使之最大限度地发挥经济效益和社会效益。合理分配黄河水资源 就是要在制定可持续发展的水资源开发战略计划时，根据全流域的自然条件、资 源分布、社会经济格局以及水资源分布状况，制定出区域性的人均年拥有水量的 目标值，以此作为水资源开发的战略目标。 1 2 水量调度问题的研究方法 合理分配水资源需要在相应的数学模型指导下进行，在水量调度中建立的数 学模型的描述主要有线性规划法和非线性规划法。对于线性规划可采用最小二乘 准则对数据进行一元或多元线性回归分析；然而，有许多实际问题实质上是非线 性的，模型中常有非线性等式和不等式约束混合离散变量，过去由于没有有效的 非线性模型拟合方法，只得采用近似的线性模型 1 】，因而对实际问题描述效果很 不理想。在对非线性模型或最佳一致逼近等准则进行回归分析时口j ，往往涉及到 最优化理论及相应的计算方法，其理论和计算过程都较为复杂，使其实际应用受 到了限制。因此采用传统的优化方法求解既繁琐又难以保证得到全局满意解。因 此近年来人们纷纷尝试运用智能算法来求解该类问题，试图在求解的效率和精度 硕士学位论文第一章绪论 上得到大幅提高。 近年来智能算法迅速发展起来，具有常用的有：人工神经网络技术、遗传算 法、进化规划、模拟退火算法和蚂蚁算法等。这些算法具有高效、简单、通用、 鲁棒性强等优点，已经广泛地应用于计算机科学、优化调度、资源分配、运输问 题等领域r 3 。目前研究较多的是遗传算法和蚁群算法。 遗传算法( g e n e t i c a l g o r i t h m ，g a ) 是根据d a r w i n 进化沦和m e n d e l 的遗传学 说生物进化思想而得出的一种全局优化算法，由美国j h o l l a n d 教授1 9 7 5 年在他的 著作自然系统和人工系统的适配中提出，其主要特点是采取群体搜索策略和 在群体中个体之间进行信息交换，利用简单的编码技术和繁殖机制来表现复杂的 现象，不受搜索空间的限制性假设的约束，不要求诸如连续性、导数存在和单峰 等假设。由于当时计算机的发展水平底下，容量小，计算速度慢，而遗传算法计 算量大，需要存储的信息多，难于实际应用，因而没有得到重视。到2 0 世纪8 0 年代中期以来，由于计算机容量和计算速度的不断提高，以及遗传算法本身的逐 步成熟而引起国际学术界的普遍重视，得到了迅速发展。目前遗传算法已经在自 动控制、数据挖掘、计算机科学、工程设计和丰啐i 经网络等领域得到了越来越广泛 的应用。 遗传算法它不同与传统的搜索和优化方法。它的特点是【4 l ： ( 1 ) 自组织、自适应和自学习性( 智能性) 。 ( 2 ) 本质并行性。首先遗传算法是内在并行的，非常适合大规模并行运算。其次 遗传算法内含并行性，可以同时搜索解空问的多个区域，并相互交流信息。 ( 3 ) 遗传算法直接以适应值作为搜索信息，无需导数等其他辅助信息。只需要影 响搜索方向的目标函数和相应的适应度函数。 ( 4 ) 遗传算法使用概率搜索技术，而非确定性规则。 遗传算法虽然有很多优点，但它对于系统中的反馈信息利用不够”1 ，当求解 到一定范围时往往做大量无为的冗余迭代，求精确解效率低。 蚁群算法是近年来出现的一种新型的模拟进化算法。它是2 0 世纪9 0 年代由 意大利学者m d o r i g o 等人首先提出来的l “，这种算法模仿了蚂蚁在搬运食物的 过程中，每个蚂蚁智能体都根据路径上的状况作相应的选择，自发寻找最短路径， 最终整个蚁群的能力能够得到优化。蚂蚁的这种选择路径的过程被称为“自催化 行为”( a u t o c a t a l y t i cb e h a v i o r ) ，蚁群算法可用来求解分配问题、指派问题等n p 完全问题，由此显示出蚁群算法在求解复杂优化问题方面的优越性。目前这种算 法己被加以改进应用到不同的领域1 7 - 1 4 。 众多研究已经证明蚁群算法具有很强的发现较好解的能力，这是因为该簿法 利用了正反馈原理，在一定程度上加快进化进程，可以理解成是一种增强型学习 2 硕士学位论文 第一章绪论 系统( r e i n f o r c e m e n tl e a r n i n gs y s t e m ) ；而且是种本质并行算法，并且它具有通用 性和鲁棒性，是基于总体优化的方法。 目前对蚁群算法的研究，不仅有算法意义上的研究，还有应用模型的研究， 并且不断有学者提出对蚁群算法的改进方案：有的将蚁群算法与遗传算法相结 合，有的给蚁群系统加人变异特征，还有的提出所谓最大最小蚁群算法( m m a s1 等。在应用领域上经典的就是求解t s p 问题，目前也有用于求解连续空间的优 化问题。 但是，现阶段对蚁群算法的研究大多还只是停留在仿真阶段，尚未能提出一 个完善的理论分析，对它的有效性也没有给出严格的数学解释。不过，从以前模 糊控制所碰到的情况看，理论上的不完善并不妨碍应用，有时应用还会超前于理 论，并推动理论研究，蚁群算法也是如此。 蚁群算法作为一种新型的模拟进化算法，有如下特点【”i ： ( 1 ) 正反馈：正反馈机制能够扩大解的质量对个体选择路径的影响，使得算法能 够快速地发现较好的解或最优解。 ( 2 ) 分布式计算：分布式计算要求个体独立地搜索最优解，而个体之间互不干扰， 这对于避免过早收敛有一定的效果。 ( 3 ) 启发性：人工蚂蚁能够利用反映可行解质量的启发信息，借以指导自己的搜 索方向，这使得算法在搜索过程的早期就能发现质量较好的解，而完全随机 的选择路径，会造成早期搜索到的解的质量不高。 ( 4 ) 通用性：它可以解决同一问题的不同版本，比如在旅行商问题中，既可以解 决对称旅行商问题( t s p ) ，也可以解决不对称的旅行商问题( a t s p ) 。 ( 5 ) 鲁棒性：它通过稍加修改，就可以应用到其他类型的问题当中【l “。 ( 6 ) 并行性：由于每个蚂蚁个体是独立地搜索可行解，容易实现该算法的并行化， 从而提高算法效率。 ( 7 ) 局部收敛：和其他进化算法一样，蚁群算法存在着早熟现象，即容易陷入局 部最优解，这是算法设计过程中应力求避免的。 本文从一个新的角度将遗传算法与蚁群算法相结合，得到一种新型的“遗传 一蚁群”混合算法，它吸取了遗传算法与蚁群算法的优点，实现了二者的优势互 补，克服了各自的缺陷，然后利用该算法来求解黄河局部流域水量调度数学模型， 并将它与传统数学方法求的结果进行比较，以此探讨“遗传一蚁群”混合算法在 函数优化问题中的应用前景。 硕士学位论文 第一章绪论 1 3 论文组织结构 第一章绪论，讲述了本文研究的背景、意义；回顾了求解水量调度模型的方法 和策略，指出了现有方法的困难，提出了采用新型算法求解问题的想法。 第二章遗传算法和蚁群算法的原理与分析，给出了遗传算法和蚁群算法的特征 和流程，综述了它们的理论和应用现状。 第三章针对遗传算法和蚁群算法的各自特点，提出了“遗传一蚁群”混合算法， 比较了新算法与他人研究的不同之处，并成功应用在函数优化问题的求解中。该 算法可以提高求解的效率。 第四章讲述了水量调度的目标和模型，并针对具体的水量调度问题，运用“遗 传一蚁群”混合算法进行求解，实践证明该算法是可行的，有较高的实用价值。 第五章讨沦了“遗传一蚁群”混合算法的收敛性，分析了遗传算法的近似优化 解的取得的方法及其对后续的蚁群算法的影响。 最后是全文的总结，并展望了今后进步研究的方向。 硕士学位论文 第二章 遗传算法和蚁群算法的原理与分析 第二章遗传算法和蚁群算法的原理与分析 2 1 遗传算法的原理 2 1 1 遗传算法的基本思想 遗传算法模拟进化、适者生存的过程，按照一定的规则生成经过基因编码的 初始群体，然后从这些代表问题的可能潜在解的初始群体出发，挑选适应度强的 个体进行交叉( 或称交配、交换) 和变异，以期望发现适应度更好的个体，如此 代代地演化，最后得到一个或几个( 具体数目依问题而定) 最优个体，将其进 行解码，所得即为对应问题的最优或近似最优解。 遗传算法的基本思想可归为两点： ( 1 ) 将生物进化的理论用于求问题的解，物种的进化又可以分为遗传和变异两个 方面。 ( 2 ) 只有最适合环境的物种才能保留下来，因而经过多代的进化后可以得到最优 或近似最优的解。 2 12 遗传算法的过程 遗传算法流程图，如图2 1 21 3 基本遗传算法描述 基本遗传算法( s i m p l eg a ，简称s g a ) ，s g a 是相当简单的抽象模型。个体 用固定长度的串表示，群体大小也是固定的。按概率选择群体中的个体来生成下 一代个体，选择的概率与个体适应度大小成正比，通过交叉和变异产生新个体。 硕士学位论文 第二章遗传算法和蚁群算法的原理与分析 l 图2 1 遗传算法流程图 算法如下：( m 为群体中的个体总数，r 为优化准则) p r o c e d u r es g a b e g i n i n i t i a l i z ep ：创建适应度函数p f i t = f a l s e ：f i t 为逻辑变量，如有个体满足优化准则，f i t 为t r u e f o r 滓1t o md o i f r ( i ) t h e nf i t = t r u e 检验个体是否满足优化准则 e n d f o r ； w h i l e ( n o tf i t ) d o没有个体满足优化准则，则进行进化计算 f o r i - lt o md o e v a l u a t ep ( i ) 计算个体适应度 e n d f o r ； f o r i = lt o md o s e l e c t p ( i ) 选择适应度高的个体 e n d f o r ； 硕士学位论文 第二章遗传算法和蚁群算法的原理与分析 f o r l = it o m 2d o c r o s s o v e r ( m ，n )个体m 与n 按概率交叉 e n d f o r ： f o r i = lt o md o m u t a t i o n ( t ) t 为随机选到的个体，对t 进行变异 e n d f o r ， f o r i _ lt o md o i f r ( i ) t h e nf i t = t r u e 在产生的新群体中重新检验是否满足 优化准则 e n d f o r 2 1 4 遗传算法的分析 在流程的以上各步骤中最重要的交叉和变异的过程，遗传算法的搜索能力主 要是由选择和交叉赋予的。 交叉可以把两个个体中的优良的模式传递到子代中，使子代具有优于其父辈 的性能，如果交叉后得到的子代的适应度不佳，则可以在此后的选择过程中将其 去掉。寻优的搜索过程主要通过交叉来实现的，因此，交叉在遗传算法的迭代中 发生的概率比较大，但交叉并不是在每对个体上都发生，它的发生频率由交叉概 率决定。 变异是以一定概率改变遗传基因的操作。如果完全没有变异，则无法在最初 遗传基因组合以外的空间进行搜索，因而求得的解的质量将受到限制。当遗传算 法陷入局部极值点后，群体中的个体有很强的相似性，此时进行交叉运算已经无 效。因此需要对个体进行突然变异，从而保持群体的多样性，增加了自然选择的 余地，并使得遗传算法跳出局部极值点。有利的突变将由于选择的作用得以遗传 和保留：有害的突变则将在逐代遗传中被淘汰。变异保证了算法能搜索到问题解 空间的每一点，从而使得算法能全局寻优增强了算法的能力。 交叉和变异保证了算法的全局收敛性和搜索的完备性。使问题的解逐代优 化，逼近最优解。 通常，变异按设定的固定概率使各遗传基因发生变化，但也有动态地改变变 异率的，如适应变异。在适应变异中，由交叉结果生成的两个个体近似度用加权 硕士学位论文第二章遗传算法和蚁群算法的原理与分析 平均距离测定，距离越近则用越高的变异率。这样，便可确保群体中遗传基因类 型的多样性，以便向尽可能大的空间进行搜索。 但交叉和变异要有一定的适度，过多的变异会使迭代过程发生振荡，经常发 生变异，群体的平均拟合程度改进慢，收敛速度低。太多的变异会破坏交叉产生 优良个体，从而增加需要迭代的次数，不管交义概翠多大，只要变异概翠p 大于 o5 就会导致随机搜索1 4 】；变异概率过小又达不到应有的效果，模型产生的变异 能力不够，会出现整个种群最后都演变为一个单一的模式，该模式可能并不是全 局的最优解，选取合适的变异概率，可以使最优模式拟合能较迅速地改进，而不 会陷于一个局部极值。具体的交叉和变异的概率将依具体问题而定”】。 g o l d b e r g 推荐的参数为： 交叉概率p ，：07 5 - - 09 5 变异概率p 。：o0 0 5 - - 00 1 2 2 遗传算法的应用 2 2 1 遗传算法的应用领域 遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖问题的具 体领域，对问题的种类有很强的鲁棒性，所以能广泛应用在很多学科中。下面是 遗传算法的一些主要应用领域： f 1 ) 1 函1 数优化。函数优化是遗传算法的经典应用领域，也是对遗传算法进行性 能评价的常用算例1 8 - 1 9 1 。 ( 2 ) 组合优化。随着问题规模的扩大，组合优化问题的搜索空间也急剧扩大， 有时在目前条件下用枚举法很难或者甚至不可能求出精确最优解，只能寻找满意 解。实践证明，遗传算法对组合优化问题中的n p 完全问题非常有效。例如，遗 传算法已在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到了 成功的运用 2 0 - 2 1 】。 ( 3 ) 生产调度问题。生产调度f q 题在许多情况下建立起来的数学模型难以精确 求解，即使经过一些简化之后可以进行求解，也会因为简化太多而使得求解的结 果与实际相差甚远。遗传算法已经成为解决复杂调度问题的有效工具口。”j 。 此外，g a 也在自动控制、机器人智能控制、图像处理和模式识别、人工生 命、遗传程序设计和机器学习等方面获得了广泛的运用。 硕士学位论文 第二章 遗传算法和蚁群算法的原理与分析 2 2 2 求解函数优化问题的遗传算法应用实例 下面通过简单的实际例子分析遗传算法的应用 例：求x 0 , 2 9 范围内的y = 一1 0 ) 2 的最小值。 过程如下： ( 1 ) 编码： 变量r 为实数，实数作为此次遗传算法的表现型形式，通过编码算法将x 转 化为二进制的串，成为基因型的形式。串的长度取决于求解的精度，这里设定求 解精确到1 位小数，由于区间长度为2 9 0 = 2 9 ，所以必须将闭区间 o ，2 9 分为 2 9 1 0 1 等份。因为： 2 5 6 = 28 2 9 0 2 9 = 5 1 2 所以编码的二进制串至少需要9 位。 ( 2 ) 产生初始群： 每个个体是串长为9 位的随机产生的二进制串，串的每一位是染色体的一 个基因码，这里设定群体大小为1 0 ，即个体数目为l o 。 ( 3 ) 计算适应度： 先将个体串进行解码，转化为表现型的r 值，步骤翘 首先，将一个二进制串( 口。口，1 5 1 2 口o 。) 代表的二进制数转化为十进制数： ( a 8 口7 a 2 1 5 1 l a o ) 22 ) l o = x 然后，x + 对应的区间 0 ，2 9 内的实数： m _ 筹 例如一个二进制串( 1 0 11 0 1 0 11 ) 表示实数值为 x = ( 1 0 1l o l 0 11 ) 2 = 3 6 3 r ：0 0 + 3 6 3 婴兰：2 0 6 2 一1 考虑到本例中目标函数在定义域内均大于0 ，而且是求函数最小值，所以参考目 硕士学位论文第二章遗传算法和蚁群算法的原理与分析 标函数得出：，( x ) = 5 0 0 一( x 一1 0 ) 2 作为其适应度函数。 ( 4 ) 遗传操作： 首先，计算每个个体的选择概率，选择概率要能够反映个体的优秀程度这 里用蒙特卡岁法来确定选择概率，即假如某个个体f ，其适应度为，则其被选 取的概率为： 寥：毒l ( 公式2 一1 ) ： 例如1 0 个体选择概率计算如表2 一l 所示： 表2 1 个体适应情况 j只 累积 个体 r 染色体 概率 l1 1 0 0 0 0 1 0 0 1 14 2 0 7 90 1 0 40 1 0 4 22 30 0 0 l o t 0 0 04 4 0 7 l0 1 0 90 2 1 3 35 8o o ll o o l l o4 8 2 3 60 1 1 90 3 3 2 47 9 0 1 0 0 0 1 0 1 14 9 5 5 9o 1 2 30 4 5 5 51 2 40 1 1 0 1 1 0 1 04 9 4 2 4o 1 2 20 5 7 7 61 5 71 0 0 0 1 0 i 0 04 6 7 5 l0 1 1 60 6 9 3 71 8 11 0 0 1 l l l l 04 3 4 3 90 1 0 70 8 0 0 82 0 8 l o u 0l 0 3 8 3 3 60 0 9 50 8 9 5 92 5 6 1 1 1 0 0 0 0 1 l2 5 6 6 40 0 6 30 9 5 8 1 0 2 8 21 1 1 1 1 0 0 0 11 6 8 7 60 0 4 21 0 0 0 然后，按照适应度进行父代个体的选择，在选出的个体中进行交叉。选择算 法常用的有：轮盘赌选择、随机遍历抽样、局部选择、截断选择、锦标赛选择等。 这里选择轮盘赔选择方法来挑选个体进行交叉。 先按照每个个体的选择概率创建一个赌轮，然后选取1 0 次，每次先产生一 个0 到l 之间的随机小数，然后判断该随机数落在那个段内就选取相对应的个体， 在这个过程中，适应度高的个体被选中概率商，简且可能被选中多次；适应度低 的个体被选申的概率低，也可能一次也选不到，就很可能被淘汰。 1 0 硕士学位论文 第二章遗传算法和蚁群算法的原理与分沂 此题中的轮盘赌可以设计如图2 2 0 0 1 0 40 2 1 30 3 3 20 4 5 5 0 5 7 70 6 9 30 8 0 0 0 8 9 5 0 9 5 8l l 一一一l 一一i 一一i 一一一i 一一l i 一一l 一l 一一l 一一f 个体：l 234 f5 + 67 l 89l o 0 5 4o 8 7 图2 - 2 轮盘 如果选取了一个随机数为o8 7 ，则落在个体8 的块内，个体8 ( 1 0 11 0 l l1 0 ) 就被选择，选中的个体被放到新的集合中；再次取随机数o5 4 ，则落在个体5 的块内，个体5 ( o l1 0 1l o l o ) 就被选中放到新集合中；不断重复直到选完1 0 次组 成新集合，集合中的个体等待进行交叉配对( 此时，集合内的个体数量很可能小 于1 0 ) 。 在二进制串之间进行交叉常用的方法有：单点交叉、多点交叉、均匀交叉、 洗牌交叉等。 这里采用随机单点交叉： 例如按交叉概率o7 5 取到的一个个体4 ( 0 1 0 0 0 1 0 11 1 ，则它与后面的个体 5 ( 0 1 1 0 1 1 0 1 0 ) 进行交叉。 再随机产生一个交叉点的位置，比如3 ，则将个体4 、5 的第3 个位置之后的 所有基因进行互换，交叉后生成两个子个体为： 子个体4 ( 0 1 0 0 1 1 0 1 0 ) 子个体5 ( 0 1 1 0 0 1 0 11 ) 这两个子个体就替代了他们的父个体在新集合中的位置。 在新集合中的交叉操作结束后，接着进行变异操作，变异作用在单个个体上， 变异的方式有多种，通常有：简单变异( 将某一位的二进制值取反运算) 、交换 变异、打乱变异、插入、删除等。当然并不是每个个体都要进行变异，假如按变 异概率选到了个体( 0 1 1 0 0 1 0 1 1 1 ，随机选取一个位置，比如选到6 号位置，在这 里采取简单变异，将6 号位的1 取反运算得位0 ，则得到新的个体( 0 11 0 0 0 0 11 ) 。 经过选择、交叉、变异三步过程便完成了一代遗传进化，得到新的一代个体。 不断进行上述三步处理，经过若干代遗传，就可获得问题的全局最优解或近似最 优解。 ( 5 ) 模拟结果： 设定种群大小位1 0 ，交叉概率为p 。= o7 5 ，变异概率p 。= oo l ，设定遗传 进化的代数为5 0 代，按照上面的基本遗传算法( s g a ) ，在运行到第3 2 代时 硕士学位论文 第二章 遗传算法和蚁群算法的原理与分析 获得最佳个体： r a i n = ( 1 0 11 0 0 0 0 ) 此时 x = 1 00 厶。= 0 0 该个体的解与数学计算的结果吻台，由于只精确到小数点后一位，且纯数学 解为整数所以即使计算中存在微小误差，四舍五入仍能得到吻合的解。 如果数学解为多位小数，例如8 位，则得到的结果不会与数学解正好吻合， 会有极微小的误差存在，而这也是正常的。 2 3 蚁群算法的原理 2 31 蚁群算法的基本思想 在自然界中，蚂蚁是通过感知信息素( p h e r o m o n e ) 的浓度来选择路径的。在 从巢穴通往食物源的各条路径上，最开始是没有任何信息素留下的，第- - t t 蚂蚁 首次选择路径时并不知道哪条路径最短，它们的选择是盲目的。随后出发的蚂蚁 则可以把第一批蚂蚁留下的信息素作为参考信息，根据信息素浓度选择路径。而 将食物搬回巢穴的蚂蚁，再次前往食物源时，不会再顺原路走了，而是重新选择 路径，当然这次它会根据蚂蚁群以前留下的信息素的浓度来选择路径，它们会选 择信息素浓度高的路径来前进。在行进过程中，蚂蚁由于只会根据信息素来选择 路径，有时会走回头路，它不会因为曾经走过就不走了。这些现象都说明，蚂蚁 没有记忆能力，并不记得自己以前走过的路径。 自然界是存在于一个连续的时空当中的，信息素会因为时间的流逝而逐渐挥 发，蚂蚁的行进和留下信息素也都是一个连续的过程。蚂蚁之间通过信息素进行 交流，路径上信息素浓度越高，表明走过的蚂蚁也越多，当然路径也越短，从而 吸引更多的蚂蚁选择这条路。这样该路径上信息素的浓度也随之增加，如此反复， 最短路径上的信息素浓度将高于其它路径上的信息素浓度，整个蚁群最终会聚集 到最短的路径上。 真实蚁群除了信息索外不会去学习任何关于路径长短的先验知识，蚂蚁也没 有记忆力，这使得蚁群的行为体现出一定的盲目性，缺乏效率，如搜索时间较长， 而且容易出现停滞现象等。这是蚁群算法需要进行改进的方面。 人工蚁群算法模仿蚁群寻找食物的生物过程，用信息素的浓度来反映路径的 长短，并通过正反馈机制强化这些信息，找到最短路径，体现了蚁群的群体智能 特性。下面引用m d o r i g o 举的例子【”i 在图2 书蚁群系统模型图中来说明蚁群算 硕士学位论文 第二章遗传算法和蚁群算法的原理与分折 法的原理。 如图2 - 3 ( a ) 所示：设a 为蚁穴，e 为食物，路径d h 、b h 和b c d 的路程长 度d 为l ；c 是路径b c d 的中点；假设在每个单位时间内，有3 0 只蚂蚁从a 来 到b ，3 0 只蚂蚁从e 来到d ；每只蚂蚁单位时间内行进路程为l ；蚂蚁在行进过 程中在单位时问内留下1 个浓度单位的信息素，1 个浓度单位的信息素在一个时 间段( t ，t + 1 ) 结束后瞬间完全挥发。 如图2 - 3 ( b ) 所示：t = 0 时，在b 和d 点各有3 0 只蚂蚁，由于此前路径上没 有信息素，它们随机地选择路径，从统计的角度可以认为它们以相同的概率选择 b h 、b c 、d h 、d c 。在d h 、d c 、b h 和b c 上各有1 5 只蚂蚁。 如图2 - 3 ( c ) 所示：t = l 时，在h 点有3 0 只蚂蚁，其中有1 5 只来自d h ，1 5 只来自b h ，所以在d h 这条路上只有1 5 只蚂蚁走过，信息素浓度为1 5 ，b h 这条路也如此。在d 点有1 5 只蚂蚁来自b c d ，在b 点有1 5 只蚂蚁来自 d c b ，所以d c b 这条路上共有3 0 只蚂蚁经过，信息素浓度为3 0 。这时又 有3 0 只蚂蚁由a 到达b ，它们发现在b h 上的信息素浓度为1 5 ，b c 上信息素 浓度为3 0 ，因此选择b c 路径的蚂蚁数的期望值是选择b h 蚂蚁数的2 倍。所以 2 0 只蚂蚁选择b c ，1 0 只蚂蚁选择b h 。同样的情况发生在d 点。 h e a 图2 3 ( a )图2 3 ( b )图2 3 ( c ) 图2 - 3 蚁群系统模型图 随着时间的推移，蚂蚁将会以越来越大的概率选择路径b c d ，最终完全选 择路径b c d 。从而找到由蚁穴到食物源的最短路径。由此可见，蚂蚁个体之间 的信息交换是一个正反馈过程。 在自然界中，蚁群的这种寻找路径的过程表现为正反馈的过程，与人工蚁群 的寻优算法极为一致。如果我们把在优化求解中那些只具备简单功能的单元看作 硕士学位沦文 第二章遗传算法和蚁群算法的原理与分析 “蚂蚁”，那么上述寻找路径的过程可以用于解释人工蚂蚁的寻优过程。 由以上分析可知，人工蚁群和自然界蚁群的相似之处在于，两者优先选择的 都是含“信息素”浓度较大的路径。人工蚁群和自然界蚁群的区别在于【“l ：人 工蚂蚁具有记忆或智能功能，它能够记忆己经访问过的节点：人工蚂蚁有一定的 视觉，人上蚁群在选择p 一条路径的时候，并不是完全盲目的，而是按一定的启 发信息有意识地寻找最短路径；人工蚂蚁“生活”在一个离散时间的环境中，而 真实蚂蚁生活在连续时间的环境中。这一点对于解决分步骤的优化问题是十分重 要的。 2 3 2 蚁群算法数学描述 蚁群算法的提出最早是用于解决平面n 个城市的t s p 问题，该问题的蚁群 算法模型的数学描述是蚁群算法思想的经典表述。 旅行商问题( t s p ) 说的是：给定，j 个城市和它们两两之间的直达距离，寻 找一条闭合的旅行路线，使得每个城市刚好经过一次且总的旅程最短。用图论语 言描述就是：己知一个，阶无向完全图g ，e ) 其中y 为点的集合，e 为边的集 合；每条边e e 有非负权值w ( e ) ，寻找g 的h a m i l t o n 圈c ，使得c 的总权值 ( c ) = w ( e ) 最小。 e e f ( c ) 将7 1 1 只蚂蚁尽量均匀地放入，? 个的城市中；吐，( ，= 1 , 2 j 3 一，1 1 ) 表示城市i 和 城市，之间的距离；f 。( t ) 表示f 时刻在城市i 和城市j 连线上残留的信息量。在运 动过程中，蚂蚁根据各条路径上的信息量来选择下一个它还没有访问的城市，选 择下一个城市的依据主要是：7 ( f ) 的值；的值( 蚂蚁由城市i 转移到城市j 的 期望信息，这一启发式信息可由所要解决的问题给出，并由一定的算法来实现， t s p 问题中一般取2 百1 在这里可以称为先验知识口 初始时刻，各条路径上信息量相等，设f ，( o ) = c ( c 为常数) 。规定蚂蚁k ( k = 1 , 2 , 3 ，聊) 经过一个时问单位的间隔( 从f 到f + 1 ) ，可以从城市i 到达城市 。那么蚂蚁完成一次周游所用的时间是”。在完成周游后，需要对各条路径上 硕士学位论文 第二章遗传算法和蚁群算法的原理与分析 的信息素按下面的公式进行更新 7 口( ，+ ，) = p f u ( t ) + 7 口 其中p ( o p 1 ) 是衰减系数，1 一p 表示了路径上的信息素在时间f 和，+ h 中 的挥发程度。 、。 a r f = 呓 = l 其中a r ：是第k 只蚂蚁在时间，和t + n z l l 司留在路径( ，) 上的信息素增量。 它由下面的公式确定： ，：号如果蚂蚁k 在( + ，) 时间内经过( ，) 1 0 没有经过( ，j ) q 为一个常量，可定义为蚂蚁循环一周或一个过程在经过的路径上所释放的 信息素的总量。表示第k 只蚂蚁在本次循环中走过的路径的长度。 对于a r ：的计算，m d o r i g o 除给出这种a n t c y c l es y s t e m 方法外，还给出了另 外两种：a n t - d e n s i t ys y s t e m ，a n t - q u a n t i t ys y s t e m 。 在a n t d e n s i t y 模型中： 瞄= 铲糊蚍徽篓绁u 在a n t q u a n t i t ys y s t e m 模型： 瞄：塄如果蚂虫义k 在( f h 删司内经过( 力 1 0 没有经过( ，j ) 在a n t d e n s i t y 模型中，蚂蚁在路径上留下的信息素量是一个与路径长度无关 的常量，对路径长短的信息强化的比较少，因此在搜索初期不易找到好的路径； 在a n t q u a n t i t y 模型中，蚂蚁留下的信息素量与局部路径长度成反比，强化了路 径长短的信息，但这只提供了局部路径优劣的信息，无法反映全程范围的路线长 短；在a n t c y c l e 模型中，蚂蚁留下的信息素量同蚂蚁选择的路线的全程长度成 反比，这种全局信息对蚂蚁搜索最短的路线提供了参考，能够使蚂蚁向全局最优 的方向靠拢，加快算法的搜索速度。 硕士学位论文第二章遗传算法和蚁群算法的原理与分析 为了满足周游所有城市且每座城市只访问一次的要求，要为每只蚂蚁设立一 一t 禁忌表i n h i b l i s t ，表中记录了t 和t + n 这段时间内蚂蚁己经访问过的城市，如 果蚂蚁所在城市的相邻城市中有某座城市已经出现在禁忌表中，则蚂蚁被禁止前 往该城市，实现了人工蚂蚁的记忆功能。 定义p o ( ，) 表示在f 时刻蚂蚁膏由城市车移到目标城市j 的概率，表达式为： 蔫，e a ，。，r e d c t ，。公式：一：， 0o t h e n v i s e 其中，a l l o w e d ( k ) = ( v i n h i b l i s t ( k ) ) ，即蚂蚁可以到达不在禁忌表中的城市 集合；其中口表示残留信息量的相对重要程度、口表示期望值的相对重要程度。 算法中的参数设定目前尚无理论上的依据，经验结果为：( 1 ) l 口5 ( 2 ) 1 卢5 ；( 3 ) o5 p s0 9 9 ，其中p 取o7 左右为佳；( 4 ) 1 s q 1 0 0 0 0 ，q 对算法的影响不大【1 “。 2 33 蚁群算法的过程 算法开始时，将”，只蚂蚁尽量均匀地放置在门个城市，从，= 0 时刻开始第一 轮搜索，当t = n 时所有蚂蚁走完，座城市，完成了第一轮搜索。此时更新路径上 的信息素，并将禁忌表清空。然后开始下一轮搜索。在达到用户设定的最大搜索 轮数n c 。时，或所有的蚂蚁都选择同一条回路，不再寻找新的路线( 称之为收 敛) 时，算法终止，此时找到的最佳路线作为问题的最优解【2 5 。2 ”。 算法的流程图，如图2 - 4 2 34 蚁群算法描述 下面给出求解t s p 问题的蚁群算法的算法伪代码为 硕士学位论文 第二章遗传算法和蚁群算法的原理与分析 图2 - 4 蚁群算法流程图 b e g i n n c 2 0 ，f f 2 0 ；a r v = o ， r f = z d ； c o n v e r g e n c e = f a l s e ；c o n v e r g e n c e 是逻辑变量，初始值为f a l s e ，如果算法的 解收敛，即最佳路径不再变化，则c o n v e r g e n c e 为t u r e i n h i b l i s t ( k ) = ： i n h i b l i s t 0 为禁忌表，初始值为空 w h i l e ( n c n c 。o r n o tc o n v e r g e n c e ) f o r ( k = o ；k m ；k + + ) 将m 个蚂蚁放入n 个城市中 硕士学位论文第二章遗传算法和蚁群算法的原理与分沂 e n d e n d f o r ： f o r ( q = o ；q n ；q + + ) q 为当前循环中走过的城市个数 f o r ( k = o ；k 至 f 是 最优解 结束 图3 1 “遗传一蚁群”混合算法流程图 3 2 函数优化问题的“遗传一蚁群”混合算法 3 2 1 一般函数优化问题中“遗传一蚁群”混合算法的修正 更 新 信 息 素 在本文a g a a s a 算法中先用遗传算法求得二进制近似优化解，判断判定问 题的解是否收敛速度接近停滞时，要根据实际问题的要求来定，例如给一个函数： f ( x ) = zs i n ( 1 0 z y ) + 2 0 ，x 一l ，2 ，求最大值，要求解精确到6 位小数，那么 不妨设定在每满l o 代内，任取两代中的最佳个体一，x ，求k x j ，判断是否 小于5x 1 0 。4 这参考值。如果大于，则认为算法求解状况良好，继续运行；如 果小于，则认为求解接近停滞，终止遗传算法运行。 在最近l o 代中任选5 个最佳个体，把这些解作为初始条件，运行蚁群算法 时采取以解- i l j - - 进制位为顶点交叉定向搜索的方法来求得最佳路径。在这里蚂蚁 硕士学位论文第三章遗传算法与蚁群算法的结合 进行的是定向搜索，实际上是在有向图中寻找最佳路径，并且每只蚂蚁限定不能 遍历所有节点。由于求解的是函数优化问题，所以的值( 蚂蚁由城市f 转移到 城市的期望信息) 是实时的，根据每只蚂蚁走过的路径而动态变化的，而非事 先固定的，这一点与t s p 问题中的设置是有本质区别的。 例如：在求函数f ( x ) = 5 一o 1 1 ) 2 ，x 7 ，1 5 的极大值中，假如遗传算法求 得的近似最优解为r 。= 1 0 = ( 1 0 l o ) 2 ，t ：= 1 3 = ( 1 1 0 1 ) ：，x 3 = 7 = ( 0 1 1 1 ) ：，把这 三个解排成三列，如图3 2 o lx 2 ll0 0l1 0ll 图3 - 2 二进制解的排列 把二进制的每一位都看作一个顶点，则这三个解共产生1 2 个顶点，蚂蚁在 搜索时规定只能从第一层第一个起点开始，从上往下逐层搜索，不能横向搜索， 也不能由下往上搜索，例如一只蚂蚁从第一位的1 出发( 约定蚂蚁总以第一个 解的第一位为起点，从其他起点出发的话，只是起点不同，而中间走过的路径能 做到完全相同，因此等蚂蚁走完后，再将第一个起点的值取反，然后再