




已阅读5页,还剩46页未读, 继续免费阅读
(管理科学与工程专业论文)蚁群算法在开拓系统结构优化中的应用研究.pdf.pdf 免费下载
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
西安建筑科技大学硕士学位论文 蚊群算法在开拓系统结构优化中的应用研究 专业:管理科学与工程 硕士生:周华 指导教师:卢才武教授 摘要 在当前经济形势下,矿山企业对经济效益的要求越来越高,开拓系统结构由于矿山企 业的行业特殊性而成为企业的主题部分和发展之基础,其优化更加显得重要。蚁群算法作 为一种新的搜索寻优技术具有通用性( 便于与其他算法结合) 、鲁棒性( 便于应用于其他问 题) 、并行搜索的优点,可以用于求解多种n p 问题( 没有多项式时间算法解的问题) ,如 t s p ( 旅行商问题) 、j s p ( 调度问题) 等,为开拓系统结构优化提供了一种更有效的新途径。 本论文的具体工作主要有以下几方面: 1 首次将蚁群算法应用于开拓系统结构优化中,提出了基于蚁群算法的矿山开拓系统 结构优化模型,从而为开拓系统的结构优化问题提供了一种可行的解决方案。 2 实现了简单蚁群算法和改进蚁群算法的计算机模拟,并进行了对比分析。经过对比, 改进蚁群算法在性能方面要优于简单蚁群算法。 3 ,对开拓系统识别进行了研究。本论文结合已有的研究成果将图论中的一些思想应用 于开拓系统结构识别中,并结合开拓系统特点,将其演化为一种有效的系统判别法,为今 后的进一步研究提供了可能。 4 以m i c r o s o f t v i s u a l b a s i c 6 0 语言为基础,结合所建立的问题模型,给出了整个算法 的实现流程,对以后在实际中类似问题的研究提供了方便。 5 结合一个开拓系统的例子,成功地进行了优化计算,对于蚁群算法在以后的普及及 推广有重要意义。 本论文研究工作有助于蚁群算法在实际中的推广和应用,尤其是为处理开拓系统结构 优化这一类复杂的系统工程问题提供了新的技术途径,对企业的经济与社会效益将产生深 远的影响。 关键词:蚁群算法开拓系统结构优化 论文类型:应用基础 西安建筑科技大学硕士学位论文 s t u d y o nt h ea p p h c a f i o no f a n t c o l o n ya l g o r i t h mi nt h es t r u c t u r a l o p t i m i z a t i o no fd e v e l o p i n gs y s t e m s p e c i a l i t y :m a n a g e m e n ts c i e n c ea n de n g i n e e r i n g n a m e :z h o nh h a i n s t r u c t o r :p r o f l uc a i a b s t r a c t i nc u r r e n te c o n o m i cs i t u a t i o n , t h ee f f e c to fe c o n o m i cp r o f i tb e c o m e sm o r ea n dm o r e i m p o r t a n tt om i n i n gi n d u s t r yi no u rc o u n t r y b e c a u s eo ft h es p e c i a l i t yo fm i n i n g ,d e v e l o p i n g s y s t e mm a k e su pt h em a j o rp a r to ft h em i n ea n db e c o m e st h eb a s eo fd e v e l o p m e n t ,s ot h a ti t s o p t i m i z a t i o n i s n e c e s s a r y a s an e wt e c h n o l o g yo f o 砸m i z a t i o n ,t h em a i n d e s i r a b l e c h a r a c t e r i s t i c so f a n tc o l o n ya l g o r i t h m , a r ev e r s a t i l e ,r o b u s ta n dp a r a l l e ls e a r c h i n g ,a n dc a nb e u s e dt os o l v em a n yk i n d so fo p t i m i z a t i o np r o b l e m sf o re x a m p l et s p ,j s ri tp r o v i d e san e w e f f i c i e n tm e a l l st os t r u c t u r a lo p t i m i z a t i o no f d e v e l o p i n gs y s t e m t h ec o n c r e t ew o r ko f t h i sp a p e rc h i e f l yp o s s e s st h eb e l o wr e s p e c t s : 1 a n tc o l o n ya l g o r i t h mi sf i r s t l ya p p l i e di nt h es t r u c t u r a lo p t i m i z a t i o no f d e v e l o p i n gs y s t e m t h i sp a p e rp r o p o s e st h es t r u c t u r a lo p t i m i z a t i o no f d e v e l o p i n gs y s t e mm o d e lb a s e do na n tc o l o n y a l g o f i t h r a ,s op r o v i d e sa n e w f e a s i b l em e a n st os t r u c t u r a lo p t i m i z a t i o no f d e v e l o p i n gs y s t e m 2 t h i sp a p e rc a r r i e so u tc o m p u t e rs i m u l a t i o no f b a s a la n tc o l o n ya l g o r i t h ma n dr e f o r m a t i v e a n tc o l o n ya l g o r i t h ma n da l s op u t su pac o n 扛a s t t h r o u g ha n a l y s i s ,r e f o r m a t i v ea n tc o l o n y a l g o r i t h mi sl i v i n gt h a tt h ep e r f o r m a n c er e s p e c tw i l lb es u p e r i o rt ob a s a la n tc o l o n ya l g o r i t h m 3 t h i sp a p e rp u t su pt h ei d e n t i f i c a t i o no ft h es n l l c t i 蒯o fd e v e l o p i n gs y s t e m i tu n i t e st h e e x i s t i n gr e s e a r c hf r u i ta n du s e ss o m ei d e a so fg r a p hi nt h ei d e n t i f i c a t i o no ft h es t r u c t u r a l o f d e v e l o p i n gs y s t e m m o r e o v e rt h ep a p e rc o m b i n e sf e a t u r e so fd e v e l o p i n gs y s t e ma n dp r o v i d e sa e 彘c t i 、噌s y s t e md i s e r i m i n a n c e ,s oa f f o r dp r o b a b i l i t yt om o r ew o r k s 4 t h i sp a p e rt a k e sm i c r o s o f tv i s u a lb a s i c s6 0l a n g u a g e sa st h eb a s e ,u n i t e st h ep r o b l e m t h ee s t a b l i s hp a t t e r na n dg i v eo u tt h ee n t i r ea l g o r i t h mr e a l i z a t i o nf l o w ,s os u p p l yt h ec o n v e n i e n c e f o ra n a l o g o u sp r o b l e mr e s e a r c hi nt h ep r a c t i c e i i 西安建筑科技大学硕士学位论文 5 。t h i sp a p e ru n i t e sai n s t a n c eo f d e v e l o p i n gs y s t e ma n ds u c c e s s f u l l y c a r r i e s0 1 1 o p t i m i z a t i o nc a l c u l a t i o n ,w h i c hh a v et h es i g n i f i c a n ts e n s et op o p u l a r i z a t i o na n ds p r e a do fa n t c o l o n ya l g o r i t h m t h i sp a p e rw i l lh e l pa n tc o l o n ya l g o r i t h mt o s p r e a da n da p p l yi np r a c t i c e i te s p e c i a l l y p r o v i d e san e wm e a n st or e s o l v et h ec o m p l i c a t e ds y s t e m se n g i n e e r i n gs u c ha ss t r u c t u r a l o p t i m i z a t i o no f d e v e l o p i n gs y s t e m ,w h i c ha f f e c t h ee c o n o m i c a lb e n e f i t sa n ds o c i e t y k e yw o r d s :a n tc o l o n ya l g o r i t h m d e v e l o p i n gs y s t e m s t r u c t u r a l o p t i m i z a t i o n t h e s i st y p e :a p p l i c a t i o nf o u n d a t i o n i l i 声明 本人郑重声明我所呈交的论文是我个人在导师指导下进行的研究工作及取 得的研究成果。尽我所知,除了文中特别加以标注和致谢的地方外,论文中不 包含其他人已经发表或撰写过的研究成果,也不包含本人或其他人在其它单位 已申请学位或为其它用途使用过的成果。与我一同工作的同志对本研究所做的 所有贡献均已在论文中作了明确的说明并表示了致谢。 申请学位论文与资料若有不实之处,本人承担一切相关责任。 论文作者签名: 削净 日期:加畋6 。7 - 关于论文使用授权的说明 本人完全了解西安建筑科技大学有关保留、使用学位论文的规定,即:学 校有权保留送交论文的复印件,允许论文被查阅和借阅:学校可以公布论文的 全部或部分内容,可以采用影印、缩印或者其它复制手段保存论文。 ( 保密的论文在论文解密后应遵守此规定) 论文作者签名:7 司斧 导师签名: 论文作者签名:7 到华 导师签名: 注:请将此页附在论文首页。 日期:加竹l f 脚1 百 彳 西安建筑科技大学硕士学位论文 1 1 论文研究背景及意义 1 绪论 随着我国社会主义市场经济的发展,企业的经济效益将决定着企业的发展与存亡。而 一个矿山企业的经济效益的好坏,除了与生产期的经营管理水平有很大关系外,还与企业 建设期的系统设计密切相关。可以这样比喻:企业建设期的系统决策与设计决定了其先天 存在条件,而生产期的经营管理则相当于后天的努力。对于人而言,先天的不足可以通过 后天的努力加以弥补,但对于一个企业而言,其先天性决策失误造成的数以千万计的巨额 投资浪费却无法在以后的生产经营中挽回,而且往往系统结构上的不合理将导致生产期经 营成本的上升,甚至会使企业因此而在市场经济竞争大潮中被淘汰。对于作为现代工业基 础的矿业更是如此。在矿山建设投资中,除了部分为生产设备外,其它投资为一次性、不 可更改且无回收价值的开拓工程。对于井下开采企业,这种开拓工程投资占总投资的比例 更大( 本文研究的开拓系统是针对并下开采企业而言) 以新建某一采选联合企业为例, 在包含地质探矿、生产设备、厂房及员工福利等一切费用时,开拓投资占总投资的比例达 3 2 9 2 ,如果仅考虑开采部分,这个比例将超过6 0 ,而且其开拓系统结构还直接关系 到以后的生产经营成本及企业的后期发展。所以对于矿业尤其是地下开采企业其开拓系统 结构优化设计至关重要。尤其当前我国正进行政府机构体制改革,国家将不再对矿产品实 行计划价收购,矿产品市场将放开,矿山企业的竞争更加剧烈,因此降低成本,提高经济 效益更加显得重要,自然的开拓系统结构优化设计也将受到更大的重视。 改革开放以来,在引进外资的同时,西方先进的管理技术与经济理论也纷纷被引入我 国,矿业界开始重视并掀起矿产经济研究的热潮,从而极大地促进了我国矿业经济的研究, 各种优化理论与优化方法不断涌现,更可喜的是大批研究成果己应用于企业,并取得明显 的经济效益。与此同时,由于种种制约,在开拓系统结构优化设计研究方面仍停留在传统 的方法与理论上,难以采用新的开拓系统结构优化理论与方法的主要表现在以下方面:第 一,开拓系统结构属于一个复杂的三维空间问题,如何用种方便、合适的数学模型来描 述它:第二,如何对任意个开拓系统进行系统结构识别。任意给出一个开拓系统结构模 型,如何判别它所对应的系统方案是否可行,即符合基本的生产及安全原则;第三,如何 实现由一种开拓方案模型向另一种开拓模型的转变,即如何由有限到无限的转变。 上世纪5 0 年代中期创立了仿生学,人们从生物进化的机理中受到启发,提出了许多用以 解决复杂优化问题的新方法,如遗传算法、进化规划、进化策略等i i j 。蚁群算法( a n tc o l o n y a l g o r i t h m ,a c a ) 是最近几年才提出的一种新型的模拟进化算法,由意大利学者m d 研鼬 等人首先提出来,他们称之为蚁群系统( a n t c o l o n ys y s t e m ) ,并用该方法来解决系统工程 两安建筑科技大学硕上学位论文 学中经典的“货郎担问题”:如果有n 个城市。需要对所有n 个城市进行访问且只访问一 次的最短距离:后来又用于求解指派问题、调度问题,取得了一系列较好的实验结果。受 其影响,蚁群系统模型逐渐引起了其他研究者的注意并周该算法解决一些实际问题。虽 然对此方法的研究刚刚起步,但是初步研究已显示出蚁群算法在求解复杂优化问题方面的 一些优越性,证明它是种很有发展前景的方法。蚁群算法作为- 1 3 新技术,由于其提出 的较晚,在国内的应用比较少,仅少最论文在杂志上发表,关于其论著则更少。因此,对 蚁群算法在开拓系统结构中应月j 研究,不但对矿业界寻求新的开拓设计方法有着重要的意 义,亦对推广蚁群算法在我国的普及十分有意义。 1 2 国内外研究现状 在国外,计算机应用于矿业中开始于五十年代,大多数早期的模拟都是由用户以 f o r t r a n 语言在主机上实现的,主要用于分析铁路、胶带、汽车等运输系统,用来寻找 合理的设备配套、数量配合;评价运输设备的调配原则;研究各种开拓运输系统的功能、 运行规律、限制和使用条件;分析系统的薄弱环节、选取改进方案等等p q 。 近年来,随着计算机的推广,计算机优化技术已渗透到矿山的各个方面。概括地讲, 矿山优化技术可分为2 类:参数优化及结构优化。参数优化指具体尺寸的优化,如巷道断 面、矿块尺寸等,这方面已取得许多成助的经验。结构优化指几何形态及拓扑关系的优化, 如巷道布置等,目前仍无十分有效的方法。地下矿开拓系统的确定就属于拓扑关系的结构 优化范畴。尽管开拓系统具有重大意义,然而至今仍无满意的解决方法。 传统的开拓系统结构优化是由设计人员根据经验列举出有限几个可行的开拓系统结 构方案,然后从技术经济指标方面进行比较,选出这些方案中的最优方案。很明显,这种 传统的优化方法有如下不足:( 1 ) 所得出的最优开拓系统结构方案往往与设计人员的经验 及水平相关:若还有更好的开拓系统结构方案未列入比较,所得出的所谓最优方案只不过 是各选方案中的较优方案( 即局部最优解) 。通常,在入选比较的有限几个方案中并不包 括有一个方案能从各方面都十全十美( 即全局最优解) :( 2 ) 入选比较的系统结构方案数 目往往受工作量制约,同此不可能入选太多的方案进行比较,即搜索寻优范围很小:对开 拓系统结构进行技术经济分析的计算量很大,而且其它辅助任务( 如绘制系统图等) 也较 多,由于各方案结构的不一致性,难以采用通用的程序及算法,所以采用传统的方案比较 法一般不超过3 个入选方案;( 3 ) 进行技术经济比较得出的最优系统结构只能是参与比较 方案中某种,而不能综合各参与比较系统结构的优点。即当两系统结构各有长短时,只 能取其一而不能由这两种系统结构综合得出另一种更好的系统结构。 近些年随着仿生学的普及和发展,为克服传统方法的不足,一些学者尝试利用此类技 近些年随着仿生学的普及和发展,为克服传统方法的不足,一些学者尝试利用此类技 西安建筑科技大学硕士学位论文 术对开拓系统结构进行优化,例如文献【1 7 和文献【1 8 】就利用了遗传算法来进行开拓系统的 结构优化,取得了很好的效果。但是这些尝试由于种种原因还没有普及开来,目前无论在 国内还是国外大部分的矿山开拓系统结构优化还是采用传统的方法。 1 3 本次课题研究的主要任务 本课题侧重于研究蚁群算法及其在开拓系统结构优化中的应用,并用实例得以验证。通 过建立基于蚁群算法的开拓系统结构优化模型,找到解决问题的方法。 本论文主要从以下几个方面开展研究工作: 首先完成蚁群算法的计算机实现,这是本论文研究的前提和基础。 在蚁群算法的基础上实现开拓系统结构辨别,实现以包括基建、运输( 由于计算量的 原因,本文不涉及通风系统) 在内的技术经济指标作为计算标准,这是本论文研究工作的核 心任务。 结合某开拓实例进行开拓系统结构优化运算,并对运算结果进行分析,为蚁群算法实 际应用于开拓系统结构优化提供理论指导。 对论文所做的工作进行全面的总结,对今后的研究重点进行展望。 本文的研究框架以及每章的研究重点如图1 1 所示。 西安建筑科技大学硕士学位论文 技术路线主要内容 基本蚁群算法原理概述 i 基本蚁群算法和改进蚁群算法 实现和对比 0 地下矿山开拓系统结构识别 - 基于改进蚁群算法的地下矿山 开拓系统结构优化 申 i全文总结及研究展望研究背景及意义 国内外研究现状0 本蚁群算法的提出及其参数选择 0 本蚁群算法和改进蚁群算法模 拟实现及结果对比分析上 自下矿山开拓系统结构识别方法 讨论上 毒于改进蚁群算法的地下矿山开 拓系统结构优化模型及实现上 l 实例验证ll l上 全文总结研究展望 图1 1 论文研究技术路线以及每章的研究重点路线图 1 4 本次课题研究的工作步骤 蚁群算法从理论上讲对于处理开拓系统结构优化问题是有效、可行的,但作为一种新的 优化技术,特别是本次研究为首次应用尝试,其中许多细节问题还有待于迸一步研究。本论 文的工作规划就是结合本次研究的主要任务,对蚁群算法在开拓系统结构优化中的应用作一 定的研究,以期对蚁群算法在开拓系统结构优化的应用中作一些抛砖引玉的工作。 具体的实旌步骤可归纳如下: 1 实现蚁群算法的计算机模拟; 2 实现开拓系统结构辨别; 3 实现技术经济指标评价; 4 进行实例优化运算; 5 对蚁群算法运算结果进行分析,确定蚁群算法在实际应用中的有效性与合理性,得出 结论。 4 西安建筑科技大学硕士学位论文 2 蚁群算法基本原理 人工蚁群算法是受到人们对自然界中真实蚂蚁集体行为的研究成果而启发提出的一 种基于种群的模拟进化算法,属于随机搜索算法【5 1 。m d o r i g o 等人首先提出该方法时,充 分利用了蚁群搜索食物的过程与著名的旅行商问题( t s p ) 之间的相似性,通过人工模拟蚂蚁 觅食的过程来求解t s p ,为了区别真实蚂蚁群体系统,我们称这种算法为”人工蚁群算法”, 这里首先介绍一下现实蚂蚁的觅食方式。 2 1 蚂蚁觅食的生态现象 真实蚂蚁作为生态系统中重要的组成部分之一,它的取食行为与生态系统有着密切的 关系,根据文献【1 0 】蚂蚁的觅食方法主要可以分成三种:简单合作觅食、小组觅食和集体 觅食。 2 1 1 简单合作觅食 简单合作觅食是单个蚂蚁独自完成觅食过程的觅食方式,s c h n l i d h e m p e l 在研究箭 蚁c b i c o l o r 的觅食行为时发现此种觅食方式。c b i c o l o r 生活在干旱区,每一觅食蚂蚁都有 自己固定的觅食路线。晴天。它们靠太阳和其他可见线索来定位运动方向,一般以此方式 猎取小块猎物。但在发现一些大块猎物时,它们几乎没法和同巢蚂蚁取得联系。美国沙漠 中盘腹蚂蚁a p h a e n o g a s t e r 也是单独觅食,但能通过释放一种化学激素而与一米以内的同 伴保持联系。 2 1 2 小组觅食 小组觅食是当某一觅食者发现食物后,作好标志,然后返回巢并带领一小组蚂蚁搬回 所发现的食物。弓背蚁c a m p o n o t u ss o c i u s 主要用这种觅食方式觅食。当一蚂蚁发现食物时, 它在食物的周围释放一种分泌物作标记,然后回巢并路释放该分泌物作为示踪标记。在 巢内,它做“摇摆表演”来召集同伴,随后同巢部分工蚁在它的带领下沿着分泌物的气味 找到食源一般情况下,一只工蚁熊召集5 3 0 个同伴。但是,当首先发现食物的工蚁中 途消失后,其同伴只能沿着示踪气体继续前进1 0 m 左右,因而很难找到所标记的食物。 西安建筑科技大学硕士学位论文 2 1 3 集体觅食 集体觅食是当某一只蚂蚁发现食物后回巢告知同伴,大批的蚂蚁将一起涌向食物, w i l s o n 发现火蚁s o l e n o p s i si n v i c t a 和小家蚁m o n o m o r i c u mp h a r a o n i s 就采用这种觅食方式。 当一蚂蚁发现食物后,释放出一种挥发性激素作为示踪标记,然后回巢告知同伴,它在巢 内来回迅速跑动并用前腿和触角轻拍同伴,当同伴得到信息后,成百上千的蚂蚁涌向食物 直至食物被取完为止。 2 1 4 其他觅食方式 有些种类的蚂蚁自己不去觅食,而靠抢劫其他蚂蚁的食物,或者偷食其他蚂蚁的卵或 幼虫,或者寄生在其他种类的巢内,有的甚至役使其他种类的蚂蚁替它觅食。 2 2 人工蚁群与真实蚁群 意大利学者m d o r i g o 等人提出的蚁群算法就是模拟上述觅食方式中的第三种,即集体 觅食方式。为了与真实蚁群相区别,我们称蚂蚁算法中的蚁群为人工蚁群。 蚁群算法是受真实蚂蚁的群体合作行为而提出的,它的很多观点都来源于真实蚁群, 它们都包括下列几项: ( 1 ) 存在一个群体中个体相互交流通信的机制,这里通常表现为信息素 真实蚂蚁和人工蚂蚁都存在一种机制改变它当前所处的环境:真实蚂蚁在经过的路径 上留下化学刺激物一信息索( p h e r o m o n e ) ,人工蚂蚁在它们经过的路径上改变了路径上存储 的数字信息,这个信息记录了蚂蚁当前的和历史的解的性能状态,而且能够被经过的其他 人工蚂蚁读写,类似的,我们称这种数字信息为人工信息素。在蚁群优化算法中蚂蚁进行 交流协作的方式就是当前路径上的信息素,这种交流方式在收集可利用的知识上占据着重 要的位置,其重要的作用在于它改变了当前蚂蚁所经过的路径周围的环境,同时也像一个 函数似的改变了整个蚊群所存储的历史信息。通常,在蚂蚁优化算法中有一个挥发机制, 它像真实的信息素挥发一样随着时间的推移改变路径上的人工信息素。挥发现象使得蚁群 可以逐渐的忘却历史遗留信息,这样就可以使选路不局限于过去蚂蚁的路径选择经验。 ( 2 ) 群体中每个个体所记录的当前遍历序列 人工蚂蚁和真实蚂蚁都要完成一个相同的任务:寻找个从源节点( 巢穴) 到目的节点 ( 食物源) 的最短路径,它们都不具有跳跃性,都只能在相邻节点之间步一步移动直至选 择完所有节点得到一个遍历序列,为了能在多次寻路过程中找到最短路径则应该记录当前 移动序列。 西安建筑科技大学硕士学位论文 ( 3 、利用当前信息进行路径选择的随机选择策略 人工蚁群算法中人工蚂蚁从一个节点移动到下一个节点的求解方法是利用概率选择 策略实现的,概率选择策略只利用当前的信息去预测未来的情况,而不能利用未来的信息, 因此,该选择策略利用的都是当前信息。在从真实蚂蚁的行为中获得启发构造蚁群算法的 过程中人工蚂蚁还具备了真实蚂蚁不具有的一些特性: a 人工蚂蚁存在于一个离散的空问中,它们的移动是一个状态到另一个状态的转移。 b 人工蚂蚁具有一个记忆它本身过去行为的内在状态。 c 人工蚂蚁更新信息素的时机是随不同问题而变化的,不反映真实蚁群的行为,如: 有的问题中人工蚂蚁在产生一个解后改变信息素,有的问题中则蚂蚁每做出一步选择就更 改信息素,但无论哪种方法,信息素的更新并不是随时可以进彳了的。 2 3 基本蚁群算法 因为人工蚁群和真实蚁群存在联系与区别,所以实现人工蚁群模拟真实蚁群进行问题 的求解就成为了可能。实践证明这种仿生方法是行之有效的。 2 3 1 基本蚁群算法原理 图2 1 蚁群总能够找到从巢穴到食物源泉的最短路径 现实生活中单个蚂蚁的能力和智力非常简单,但它们通过相互协调、分工、合作完成 不论工蚁还是蚁后都不可能单独完成的筑巢、觅食、迁徙、清扫蚁穴等复杂行为,比如在 蚂蚁觅食过程中能够通过相互协作找到食物源和巢穴间的最短路径( 现实中我们总可以观 察到大量蚂蚁在巢穴和食物源之间形成近乎直线的路径,而不是曲线或者圆等其他形状, 图2 1 ) 。像蚂蚁这样的群居昆虫,虽然没有视觉,却能找到由蚁巢到食物源的最短路径, 原因是什么呢? 西安建筑科技大学硕士学位论文 图2 2 蚂蚁以等同概率选择各条路径 蚁群群体能够完成复杂的任务,不仅如此,蚂蚁还能够适应环境的变化,如:在蚁群 运动路线上突然出现障碍物时,一开始各个蚂蚁分布是均匀的,不管路径是否区分长短, 蚂蚁总是先按同等概率选择各条路径( 图2 2 ) 。 但经过一段时间后蚂蚁能够很快的重新找到最优路径,蚁群是如何完成这些复杂任务 的呢? 所有这些问题,很早就激起了生物学家和仿生学家的强烈兴趣,仿生学家经过大量细 致观察研究发现,蚂蚁个体之间是通过一种称为外激素( p h e r o m o n e ) 的物质进行信息传递, 从而能相互协作,完成复杂的任务。蚁群之所以表现出复杂有序的行为,个体之间的信息 交流与相互协作起着重要的作用。蚂蚁在运动过程中,能够在它所经过的路径上留下该种 物质,而且蚂蚁在运动过程中能够感知这种物质的存在及强度,并以此指导自己的运动方 向,蚂蚁倾向于朝着该物质强度高的方向移动。如路径上出现障碍物时相等时间内较短的 路径上信息量就遗留得比较多,选择较短路径的蚂蚁也随着增多( 图2 3 ) 。 图2 3 较短路径上信息量较大,选择该路径的蚂蚁增多 蚂蚁选路过程中较短路径上遗留的信息量会在很短时间内大于较长路径的原理我们 不妨用下图( 图2 4 ) 说明:假设a 、e 两点是蚁群的巢穴和食物源,从其间有两条路径a b h d e 和a b c d e ,其中b h 和h d 间距离为1 1 n ,b c 和 c d 间距离为0 5 m 。 最初( 即t = 0 时刻) ,如图2 4 所示,当3 0 只蚂蚁走到分支路口b 或者d 点时,要决定 西安建筑科技大学硕士学位论文 往哪个方向走,因为初始时没有什么线索可供它们选择,所以它们就以相同的概率选择路 径,结果是有1 5 只蚂蚁走左边的路径d h 、b h ;另外1 5 只蚂蚁走右边的路径d c 、b c ,这些蚂蚁在行进过程中分别留下信息量。若假设蚂蚁都具有相同的速度0 r r a s ) 和信息量释放能力,则经过l s 后从d 点出发的3 0 只蚂蚁有1 5 只到达了h 点,有1 5 只经 过c 到达了b 点,同样的从b 点出发的3 0 只蚂蚁有1 5 只到达了h 点,有1 5 只经过c 到 达了d 点。很显然,在相等的时间间隔内路径d h b 上共有1 5 只蚂蚁经过并遗留了 信息量,d c b 上却有3 0 只蚂蚁经过并遗留了信息量,其信息量强度是d h b 路径上的2 倍。因此,当3 0 只蚂蚁分别回到a 、e 点重新选择路径时就会以2 倍于d h b 的概率选择路径d c b ,从而d h b 上的蚂蚊数目变成了l o 只,是d c b 上蚂蚁数目的一半,距离较短的路径上信息量很快得到了强化,其优势也很快被蚁 群所发现。 回卜 卜 图2 4 蚂蚁选路过程示例 不难看出,由大量蚂蚁组成的蚁群的集体行为表现出了一种信息正反馈现象:某一路 径上走过的蚂蚁越多,则后来者选择该路径的概率就越大,蚂蚁个体之间就是通过这种信 息的交流搜索食物,并最终沿着最短路径行进( 图2 5 ) 。 人工蚂蚁寻找最优路径的方法就是根据上面的真实蚂蚁寻找最优路径的方法提出的, 即让人工蚂蚁根据路径上的相当于p h e r o m o n e 的数字信息量的强度选择路径,并在所经过 的路径上留下相当于p h e r o m o n e 的数字信息量,然后随着时间的推移,最优路径上的数字 信息量将积累的越来越大,从而被选择的概率也越来越大,最终所有人工蚂蚁将趋向于选 择该路径。这种模拟蚁群搜索食物的过程与著名的旅行商问题非常相似,因而最初人工蚁 群算法被提出用于求解旅行商问题。 9 西安建筑科技大学硕士学位论文 可见,人工蚁群算法是一种随机搜索算法,与其他模拟进化算法一样,通过侯选解组 成的群体的进化过程来寻求最优解,该过程包含两个基本阶段:适应阶段和协作阶段。在 适应阶段,各侯选解根据积累的信息不断调整自身结构;在协作阶段,候选解之间通过信息 交流,以期望产生性能更好的解。 2 3 2 基本蚁群算法模型 图2 5 蚂蚁最终饶过障碍物找到最短路径 现在大量的工作是围绕组合优化问题进行的,因为蚁群模型的定义要受到问题结构的 影响,故而选择一种标准的问题是衡量算法好坏,并与其它算法进行比较的前提,通常选 择的问题是旅行商问题( t s p ) ,下面简要地介绍一下用于t s p 的蚁群算法。 为了便于理解,我们以求解平面上n 个城市的t s p 问题( 0 ,1 ,n - 1 表示城市序号1 为例说明蚁群系统模型。n 个城市的t s p 问题就是寻找通过n 个城市各一次且最后回到出 发点的最短路径【6 】。其数学模型可以表述成一个完全加权的有向图g = ( v ,a ,d ) ,其中v = f o , 1 ,n - l 是节点( 城市) ,集合a - ( r ,s ) i ( r ,s ) v x v 是支路集合,d 是a 的权函数, 它将每条支路( r ,s ) 与一个正整数权d ( r ,s ) 相关联( d ( r ,s ) 可看成节点r 和s 之间的距离) 。 目标是找到恰好访问每个节点一次的最小长度的闭合回路。t s p 在数学上被称为是n p 难 的优化问题。 我们这里设m 是蚁群中的蚂蚁总数,碣,( i ,j = 1 ,2 ,1 1 ) 表示城市i 和j 间的距离。 f 。o ) 表示t 时刻城市i 和3 之问的信息量,初始时刻各条路径上信息量相等,设0 ( o ) = c ( c 为常数) ,我们以此来模拟实际蚂蚁的分泌物。蚂蚁k ( k = 1 ,2 ,m ) 在运动过程中根据 各条路径上的信息量决定转移方向,p k ,( t ) 表示在t 时刻蚂蚁k 由城市j 转移到城市j 的概 率,则: 。 碍) 瑶瑶( f 蝣 j a l l o w e d , 学u ) 2 “洲d k ( 2 1 ) 1 0其它 l o 西安建筑科技大学硕士学位论文 式中: d 一一残留信息的相对重要程度; 口一一期望值的相对重要程度; a l l o w e d k = ( 1 ,2 ,n ) 一t a b u ( k ) 为所有可能的目标城市集合,即还没有访问的 城市集合;为了避免对同一个城市的多次访问,每一只蚂蚁都保存一个列表t a b u ( k ) ,用 于记录目前为止已经访问的城市; 一一由城市i 转移到城市j 的期望程度,例如,可以取巩= 1 z ,; 随着时间的推移,以前留下的信息逐渐消逝,用参数卜p 表示信息消逝程度,经过n 个时刻,蚂蚁完成一次循环,各路径上信息量要根据下式调整: r o ( t + 玎) = p r 扩( ) + 乃 乃= a r : k = l 其中: p 残留信息的保留部分; 剪第k 只蚂蚁留在路径i j 上的信息量; a r o 本次循环中留在路径i j 上的信息量; 呓由下式确定: 砖: q 厶 ”【0 ( 2 2 ) ( 2 3 ) 毒銎:只蚂蚁在本次循环中经过 ( 2 4 ) 否则 其中q 为常数,厶表示第k 只蚂蚁在本次循环中所走路径的总长度。在经过若干次循 环以后,可以根据适当的停止条件来结束计算e 根据具体算法的不同,分8 ) ,a 勺( f ) , p u 2 ( ) 的表达形式可以不同,要根据具体问题而定am d o d g e 曾给出三种不同的模型, 分别是a n t - c y c l es 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 ys y s t e m ,它们的差别在于公式2 4 的不同。在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 ys y s t e m 中: 弓= 悟 若第k 只蚂蚁在本次循环中经过i j ( 2 5 ) 否则 n j g k r n 警在本次循环中经过i j ( 2 6 ) 否则 它们的区别在于后两种模型中利用的是局部信息,而前者利用的是整体信息,在求解 西安建筑科技大学硕士学位论文 t s p 问题时性能较好。因而我们采用前者为基本模型。停止条件可以用固定进化代数或者 当进化趋势不明显时停止计算。算法框图如图2 6 : 主要步骤为: 图2 6 蚁群算法流程图 步骤1n c = 0 ( n c 为迭代步数或搜索次数) 各气和a 分的初始化;将m 个蚂蚁置于初始位置上; 步骤2 将各个蚂蚁的初始出发点置于当前解集中; 对每个蚂蚁k ,按概率姥( f ) 移至下一个点j ;将点j 置于当前解集; 步骤3 计算各蚂蚁的目标函数值l k ( k = 1 ,m ) ;记录当前的最好解; 步骤4 按更新方程( 2 2 ) 修改轨迹强度; 1 西安建筑科技大学硕士学位论文 步骤5 对各边( i ,j ) ,置f 。2 = 0 ,n c n c + 1 步骤6 若n c 预定的迭代次数,则转步骤2 步骤7 输出当前的最优解。 蚁群优化算法对于解决货郎担问题并不是目前最好的方法,但它提出了一种解决货郎 担问题的新思路1 l o 】;其次由于这种算法特有的解决方法,它己经被成功用于解决其他组合 优化问题,例如图的着色( g r a p hc o l o r i n g ) 及最短超( s h o r t e s tc o m m o ns u p e r s e q u e n c e ) 等 问题【1 2 i f l 4 】 捌。国内也有研究者用蚂蚁算法求解全国1 4 4 个城市的最短回路问题,求得的解 同其它方法求到得解一样精确,这说明蚂蚁算法不但是求解组合优化问题的可行方法,而 且是一种很有竞争力的算法。 2 3 3 基本蚁群算法参数特性 很多学者对基本蚁群算法a s 的参数进行了讨论,其中的参数q ,c ,口,卢,p 可 以用实验方法确定其最优组合,目前尚无理论依据,己经公布的结果都是针对特殊的问题 而言的。对经典的t s p ,其经验结果为0 - 口s 5 ,1 s 卢5 ,p 取0 7 左右,q 的影响不 大,c 根据所求解问题的适应度取相应的数量级。 为了探讨蚁群算法中参数的最佳设定原则,本论文用m i c r o s o f tv i s u a lb a s i c6 0 语言模 拟实现了基本蚁群算法,通过一系列的对比仿真实验研究加上已有文献的成果,给出如下 的设定原则。以利于蚁群算法在实际中的应用和推广。 2 3 3 1 信息量挥发度的选择 在蚁群算法中,人工蚂蚁是具有人类记忆功能的,随着时间的推移,以前留下的信息 将要逐渐消逝。在算法模型中用参数1 一p 表示信息消逝程度( 或称信息量挥发度) ,而p 就 是信息量残留系数。蚁群算法与遗传算法等各种模拟进化算法一样,也存在着收敛速度慢、 易于陷入局部最优等缺陷。而信息量挥发度1 p 的大小直接关系到蚁群算法的全局搜索能 力及其收敛速度:由于信息量挥发度1 p 的存在,当要处理的问题规模比较大时,会使那 些从来未被搜索到的路径( 可行解) 上的信息量减小到接近于0 ,因而降低了算法的全局搜索 能力,而且当1 p 过大时以前搜索过的路径被再次选择的可能性过大,也会影响到算法的 随机性能和全局搜索能力;反之,通过减小信息量挥发度1 一p 虽然可以提高算法的随机性 能和全局搜索能力,但又会使算法的收敛速度降低。 西安建筑科技大学硕士学位论文 09 89 92 78 9j 7 59 62 66 4 4 9 9 805 49 87 3 1 87 78 96 3 6 4 9 95 406 1 3 66 94 65 31 38 l 2 79 86 1o8 67 51 58 7 2 1 8 7 8 9 7 33 68 604 61 9 8 76 54 6 1 7 51 86 97 5 4 602 65 32 12 3 9 67 74 61 5 1 92 604 63 6 5 4 2 68 95 38 78 75 34 607 56 5 6 46 31 32 l6 52 l 3 6 7 5q5 4 4 96 48 l8 74 6 2 35 46 5 5 40 关于蚁群算法中信息量挥发度1 p 对算法性能的影响及其在实际应用中的选择,可以 通过计算机仿真实验来分析和确定。对此,取如下的t s p 阀题及算法参数进行仿真比较, 距离矩阵d 如上。 群体中蚂蚁数m = 5 ,蚂蚁循环一周所释放的总信息量q = i ,信息启发式因子口= 0 9 , 期望启发式因子= 1 0 ,运算的停止条件为相邻两次循环搜索中最优解的差别小于o 0 0 1 , 并使信息量残留系数的变化为p 0 3 ,0 5 ,0 , 7 ,0 9 ,0 9 5 ,0 。9 9 。信息量残留系数对 算法性能影响的有关仿真结果如表2 1 : 表2 1 信息量残留系数对算法性能的影响 残留系数p最优路径长度搜索循环次数 0 33 7 9 7 3 8 71 7 o 53 7 9 7 3 0 32 6 o 7 3 7 9 7 3 2 1 4 4 0 93 7 9 7 5 4 71 1 5 o 9 5 3 7 9 8 6 3 9 1 6 5 0 9 93 7 9 _ 2 0 1 35 6 9 由仿真实验结果不难看出,在其它参数相同的情况下,信息量挥发度p 的大小对蚁群 算法的收敛性能影响极大,特别是当1 p 很小时,由于路径上的残留信息占主导地位,搜 索的随机性增强,因而蚊群算法收敛速度很馒;而在l p 比较大时,搜索的随机性减弱, 虽然算法收敛速度加快但易于陷入局部最优状态。因而,关于蚁群算法中信息量挥发度1 p 的选择,必须综合考虑算法的全局搜索能力和收敛速度两项性能指标,针对具体问题的应 西安建筑科技大学硕士学位论文 用条件和实际要求,在全局搜索能力和收敛速度两方面作出合理或折中的选择。由上述试 验可见,在p = o 5 0 7 范围内,算法的性能比较稳定和一致,搜索的全局性和收敛速度都 比较好。所以在蚁群算法中信息量挥发度的选择宜取为1 一p = 0 3 ( 即p = 0 ,7 ) 。 2 3 3 2 蚂蚁数量的选择 蚁群算法是一种随机搜索算法,与其它模拟进化算法一样,通过多个候选解( 可行解的 一个子集) 组成的群体的进化过程来寻求最优解,在该过程中既需要每个个体的白适应能 力,更需要群体的相互协作。蚁群在搜索过程中之所以表现出复杂而有序的行为,个体之 问的信息交流与相互协作起着至关重要的作用。对于t s p 问题,单个蚂蚁在一次循环中所 经过的路径,表现为问题可行解集中的一个解,1 t 1 个蚂蚁在一次循环中所经过的路径,则 表现为问题解集中的一个子集。显然,子集越大( 即蚁群数量多) 可以提高蚁群算法的全局 搜索能力以及算法的稳定性;但蚂蚁数目增大后,会使大量的曾被搜索过的解( 路径) 上的 信息量的变化比较平均,信息正反馈的作用
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年及未来5年中国饮料工业行业竞争格局分析及发展趋势预测报告
- 高压试验工岗位操作熟练度考核试卷及答案
- 2025年合肥师范学院高层次人才招聘63人考前自测高频考点模拟试题及答案详解(名师系列)
- 2025辽宁本溪高新区国有企业招聘6人模拟试卷及完整答案详解1套
- 船舶修理工职业健康、安全、环保技术规程
- 铸管退火工设备安全技术规程
- 热力网值班员事故应急处理模拟考核试卷及答案
- 2025年福建省莆田市仙游县森林防灭火指挥部招聘10人模拟试卷及1套参考答案详解
- 白银熔池熔炼工岗位设备安全技术规程
- 电池配料工工艺作业技术规程
- 二年级趣味数学校本教材
- JJF新1422024电动汽车充电检测用程控电阻负载校准规范
- 当代主要疾病和预防课件2025-2026学年北师大版生物八年级上册
- 葡萄种植培训课件
- 车辆入股协议书范本合同
- 好利来工作协议合同模板
- 人防检测培训课件
- 2025年睡眠监护仪项目申请报告范文
- 征地拆迁业务知识培训课件
- 3.1 世界是普遍联系的 课件 高中政治统编版必修4 哲学与文化
- 01综合管沟汇报
评论
0/150
提交评论