（计算机应用技术专业论文）最优路径选择在配电网信息管理系统中的应用研究.pdf

华北i u 力大学坝l 学缸沦义摘篮 摘要 配电网最佳抢修路径问题既是曰时地理信息系统网络分析中的一个研究热点， 也是配电网管理系统的重要组成部分。坩誓叶1 j | 对配电网最佳抢修路径的特点对基本 蚁群算法进行了改进，并将改进的蚁群算。五应用于实际系统当中。以行午时间最短为h 标，考虑影响行车效率的并种因索建立了配电网最件抢修略径的数学模型。结合河南 濮刖电力局基于g i s 的配电网信息管理系统实际项目对最佳抢修路径搜索功能模块 进行实现。实际结果表明，在解决配电劂最佳抢修路径问题上，改进的蚁群算法有 良好的效果。 关键词：最佳抢修路径，蚁群算法，地理信息系统，配电网管理系统 a b s t r a c t t h eb e s tr e p a i rp a t ho fp o w e rd i s t r i b u t i o nn e t w o r kf o c u so nt h er e s e a r c hi nc t l r r e n n e t w o r ka n a l y s i so fg e o g r a p h i ci n f o r m a t i o ns y s t e m a tt h es a m et i m e ，i ti sa ni m p o r t a n tp a r t o fp o w e rd i s t r i b u t i o nn e t w o r km a n a g e m e n ts y s t e m int h i sp a p er ，b a s i ca n tc o l o n ya l g o r i t h m i si m p r o v e da c c o r d i n gt os p e c i a l i t yo ft h eb e s tr e p a i rp a t ho fp o w e rd i s t r i b u t i o nn e t w o r ka n d i m p r o v e da n tc o l o n ya l g o r i t h mi sa p p l i e dt oa c t u a ls y s t e mt h em a t h e m a t i cm o d e lo ft h eb e s t r e p a i rp a t ho fp o w e rd i s t r i b u t i o nn e t w o r ki se s t a b l i s h e dw h i c ht a k e st i m es h o r t e s tt r a v e lt i m ea s o b j e c ta n dt h ef a c t o r so fi n f l u e n c i n gt r a v e le l ；i ti e n c ya r ec o n s i d e r e di nt h i sm o d e lf u n c t i o n a l m o d u l eo ft h eb e s t r e p a i rp a t h i sr e a l i z e da s s o c i a t ew i t hp o w e rd i s t r i b u t i o nn e t w o r k m a n a g e m e n ti n f o r m a t i o ns y s t e mb a s ed ng i sf o rp u y a n ge l e c t r i cp o w e rb u r e a u i m p l e m e n t a t i o nr e s u l te x p r e s st h a ti m p r o v e da n tc o l o n ya l g o t i t h mi sb e n e f i c e n ti nq u e s t i o no f t h eb e s tr e p a i rp a t ho f p o w e rd i s t r i b u t i o nn e t w o r k y ex i a n y i ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db ypr o f c h e n gx i a o r o n g k e yw o r d s ：t h eb e s tr e p a i rp a t h ，a n tc o l o n ya l g o r i t h m ，g i s ，d m s 声明 本人郑重声明：此处所提交的硕_ 一位沦文最优路径选择在配电网信息管j m 系统中的应用研究，是本人在华北电力大学攻凄硕士学位期问，在导9 目日静导f 进 行的研究工作和取得的研究成粜。掘本人所知，际了文中特别加以标注和致i | 于之处 外，论文中不包含其他人已经发表或撰写过的研究成果，电不包含为获得华北电力 大学或其他教育机构的学位或ie i 。捧而使用过的材料。与我同工作的| 舌i 志对本研究 所做的任何贡献均已在论文中作了明确的晚明并表示丁谢意。 学位论文作者签名：吐星盟 日期：动r6 f 4 关于学位论文使用授权的说明 本人完全了解华北电力人学有关保管7 奠用学位论文的规定，即：学校有权保管、 并向有关部门送交学位论文的原l b 与复印件：学校可以采川影印、缩印或其它复制手 段复制并保存学位论文；学校可允许学位论文被查i 列或借i ；学校可以学术交流为 目的，复制赠送和交换学位论文；同意学校可以用不同方式在不同媒体上发表、传播 学位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定) 作者签名：盟1 导师签名：彳篁翌至多 f t 期：竺! ! ! 终 日期：丝：! ：丛7 f 吕：i 匕l 也力火：学顺：i ：学位论义 第一章 引言 1 1 选题背景及现实意义 电力系统在国民经济中占有重要的地位。其中宜接供电给用户的配电网络拥有 山整个供电系统6 0 投资及2 0 运行成本的极大数暴的电力设备，其可靠性与质黾 直接关系到国民经济和人们的日常牛活。 随着电力系统的发展，而对越来越密织的电网，复杂的电力设备，时刻变化的 负荷信息，不断变迁的道路和建筑，以及用广i 对供电i j 靠性、电能质量，以及优质 服务的需求都刁i 断提高，如何向用户提供快捷、准确、优质的服务是当前电力企业 必须考虑的一个问题。传统配电网管理方式已经很难满足电网的建设和安全经济运 行要求，电力运行、营业部门必须对极其庞大繁杂的信息进行采集、存储、分析和 快速处理。配电网不仅包括电力公司的变、配电设备和网络，而且还有为数众多、 性质各异且经常变化增长的用户设备，其功能涉及到运行、管理等多个方面1 “。配 电管理系统( d i s t r i b u t i o nm a n a g e m e n ts y s t e m ，d m s ) 近些年来引起了学术界和 电力行_ k 的注意，是目前国内外- - f 在研究和发展的热点。在配电自动化系统中引入 地理信息系统( g e o g r a p h i ci n f o r m a t i o ns y s t e m ，( ；ls ) 是当前技术发展的方向， 也是d m s 的一个重要特征。g i s 是以地理空问数据库为基础，在计算机硬、软件环境 的支持下，对空间相关数据进行采集、管理、操作、分析、模拟和显示，适时提供 卒间和动态的地理信息，为决策服务的一类信息系统。g i s 作为【) m s 的一个重要组成 部分，正日益受到人们的重视。 城市配电网随城乡电网的建设和改造的不断进行日趋复杂，配电网设备发牛故 障的数量也呈上升趋势。在故障发生后，根据抢修队目前所处的位置及发生故障的 地点，及时派出抢修人员到达现场，不没停电时问最短，同时能够树立电力企业 良好形象、改善电力企业与用户之问的关系具有重要的社会及经济意义。 最佳抢修路径问题实际上属于城市交通网络中的最短路问题，是目前g i s 网络分析 中的一个研究热点，也是d m s 的重要组成部分。g i s 网络分析中的其它问题，如最可靠 路径问题、最大容量路径问题、位址选择模型等都+ 口j 归并到最短路径问题类型中。 1 2 课题的研究现状 1 2 1 配电网地理信息系统研究和发展现状 早在2 0 世纪7 0 年代，西方发达国家的电力企业就开始应用g i s 技术建立“数 字电网”作为突破u 来进行生产经营“业务流程重绸”和提高电网运行管理水平， 一i 一 华：u j 学l i j i ： - ：学阪沦义 从而增强企业的自身竞争能力。随蓿地理皤息系统的快速发腱以及其优良特性，配 电g i s 电得到长足发展，目前已广泛应j 1 j 于电网图形f = l j 视化j 矗示、电力没备的定位、 配电删优化设计、潮流计算、可靠性分析、敞障的快速隔离、负荷转移等方面 地理信息系统在我同电力企业的应用起步较晚，而且主要围绕供电企业应用， 但近几年应用发展很快。目前，北京、两安、武汉、? 斜、一i 。：海、重庆、j 州、绍 兴等地供电局相应开展了电力地理信息系统项目建设，有的项目已经进入实用化阶 段，有的在进行了2 0 世纪9 0 年代ti 后期的试点工作后，又陆续向仝方位发展。所 建系统已从过去的主要应用集中在配电系统管理功能方面，向输电系统、客户服务 系统、客户管理系统、用电营业系统、配电管理系统以及地理信息系统和e m s s c a d a 、 配电自动化系统相互结合的综合应用发展。 由于配电网包括有众多地理位置各异的设备、网络、川户等，因此配电网g i s 系统的研究成为电力g i s 系统研究中的重点。在配电网运行方面，有的文献提出通 过建立电力设备地理分布图，为配电网g i s 系统离线和在线监测系统提供设备位置 的空间信息和配电网的实时工作情况，其综合信息系统可以管理变压器的负荷以及 在事故中的负荷转移；随着监视控制和数据采集( s u p e r v is o r yc o n t r o la n dd a t a a c q u i s i t i o r l ，s c a d a ) 技术在d m s 中的j 泛应用，如何合理结合g i s 系统与s c a d a 为 配电网管理服务也成为许多学者研究的重点 1 。在配电网规划方面，针对配电网规 划的复杂性，有的文献将g i s 及人二l 智能( a r t if ic i a l in t e l “g e n c e ，a i ) 方法引 入配电网规划问题研究，结合了g i s 系统空间及网络分析( i ；j 拓扑特性和a i 方法的鲁 棒性及高效性两者的优点：在计算机辅助规划设计中，有人提出采用g i s 系统技术 来帮助分析决策，或者综合运用g i s 系统和遗传算法来实现配电网优化规划：有的 研究者提出基于g i s 系统的城市电网规划计算机辅助决策系统来优化城市电网的规 划结果，解决城市电网规模大、不确定和不精确因素多及涉及领域广等问题。 1 2 2 配电网最佳抢修路径问题研究现状 配电网最佳抢修路径问题实际上属于城市交通网络中的最短路径问题，按照问 题特征中的起始点特性，最短路径问题口j 分为两种：单源最短路径问题及所有节点间最 短路径问题。其中单源最短路径史具有普遍意义，并1 7 可为所有：市点问最路径问题提供 良好的借鉴。 根据解决问题的不i 刊思想，可将单源最短路径算法分为基于g i s 系统空问企询 语言的最短路径分析和基于专门设计的功能模块的最短路径分析两类。基于g i s 系 统空问查询语言的最短路径口前还停留在理论研究阶段，距离商业实际应川还有 定的距离。基于功能模块思想的最短路径算法研究是最短路径问题研究的热点。按 照问题特征、实现技术的差异，单源最短路径问题的算法可分为很多种，如d ij k s t f i t - 2 - f 导：i 匕l u 力火学颂：l 。：学旺i l - 义 算法、动态规划方法、神经网络法、流体神经网络模拟交通网并结合遗1 i 算法的优 化参数法、遗传算法优化路径参数的d ij k s t r a 法、撼于路径模糊信息的最大满- i i - 意度 路径法、基_ 丁人上智能的启发式搜索算等。针列1 i 同的背景应用需求及具体的软 硬件环境，各种算法在空间复杂度、时问复杂度、易实现性等方确i 各具特邑。 现阶段，配电网最佳抢修路径中所采用的算：法多数为基于不j 刊存储结构的 d ij k s t r a 算法，近几年又有一种新的基于空问方向关系的实用最短路径算法被提出 并应川到本问题i i i 。 1 3 课题研究的主要内容 本课题研究的主要内容是将蚁群算法应用于配电网最佳抢修路径问题的研究并 结合实际项目进行编程验证。 配电网最佳抢修路径是配电网信息管理系统的一个组成部分，在实际系统中作 为一个独立的功能模块出现。本课题在河南濮阳市配电网信息管理系统实际工程项 目基础上，对配电网最佳抢修路径问题进行研究，实现的主要功能包括： ( 1 ) 根据用户的故障投诉电话或者配电网自动化系统中的故障监测信息在地图上定 位故障地点以及维修队所处的位置。 ( 2 ) 根据统计出的不同时段城r h 道路上车流量计算维修人员到达故障地点的最佳路 径。 ( 3 ) 将求得的最佳路径在地图上动态显尹：i 刊时给出该路径的文字描述。 本课题研究的主要工作为： ：j j ( 1 ) 蚁群算法的研究和改进。 ( 2 ) 建立城市道路及交通信息等数据库。 ( 3 ) 结合影响行车效率的因素构建最佳抢修路径的数学模型。 ( ，4 ) 选择合适的g i s 开发平台及编程工具，对系统结构进行设计。 ( 5 ) 编程验证该算法的n j 。行性。 一3 一 华：f e i u 力大学硕： = 学位沦义 第二章地理信息系统技术 配电网信息管理离不开相关的地理信息，地理信息系统已经成为配电系统开展 各利，自动化( 如电量计费、投诉电话热线、丌具操作票等) 的基础i r 台，同时也是 未来电力信息化发展的重要方向之一。配电网最佳抢修路径作为配电网信息管理系 统的一个重要的功能模块，其故障设备的定位、道路信息数据的获取、最佳路径的 显示等同样依赖于地理信息系统卜“。 2 1 地理信息系统基本概念 地理信息系统( g e o g r a p h i ci n f o r m a t i o ns y s t e m ，简称g i s ) 是一种为了获取、存 储、检索、分析和显示空问定位数据而建立的计算机化的数据库管理系统。地璎信息系 统的处理对象是空f 刨实体，其处理过程是依据空间实体的空问位置与空间关系进行的。 g i s 针对特定的应用任务，存储事物的空间数据和属性数据，记录事物之间的关系和演 变过程。它可根据事物的地理坐标对其进行管理、检索、评价、分析、结果输出等处 理，提供决策支持、动态模拟、统计分析、预测预报等服务。其应用覆盖工业、农业、 交通运输、环保、国防、公安等诸多领域，特别是g i s 与m i s 相结合，其应用几乎涉及人 类生活的各个方面”。 简而言之，地理信息系统是以计算机为工具，具有地理图形和空问定位功能的空问 型数据管理系统，它是一种特殊而又十分重要的信息系统，综合了计算机、系统二 程、 经济管理等多学科的知识，属跨学科的技术系统。其组成蜘i 图2 1 所示： 图2 1地理信息系统的组成 2 2 地理信息系统主要功能 地理信息系统的基本功能主要包括以下五个方面： ( 1 ) 数据采集 - 4 一 华：i 匕1 i = l 力火：学影i 。l - - i f ：f 讧i = 仑义 g i s 要对多种形式、多种来源的数据，实现多种力啪勺数据输入，建立：空间数据库。 一般是将地图“欠量化”，即把原来的地i 到刑扛j 描仪或数字化仪处理后，利用( j i s 软 件进行编辑，形成所谓的电子地图。目前o s 的输入j 皤f 越来越多地借助非地图形式， l i ；女i i 遥感和g p s 技术应用都非常广泛，具有很好的发腱附景。臼动化数据输入已成为 地理信息系统研究的重要内容。 ( 2 ) 数据存储和管理 空问数据库的数据量大，空间数据与属性数据不可分离。区l i f l i ，须对数据库进行有 效地管理，使数据冗余量小，选择合适的数据结构和数据模型。如图2 2 ，空间数据一 般有栅格结构、矢量结构和栅格矢量混和结构三种组织方式；而属性数据则有层次模型、 网络模型和关系数据模型等进行描述和表达，其中关系数据库系统应用最为广泛：，j o i 刘2 2g i s 数抛组彩j j 舀理 ( 3 ) 地理数据的操作和分析 g i s 中对数据的操作提供了对地理数据有效管理的手段。g i si 图形数据与属性数 据紧密结合在一起，形成对地物的描述，对其中一类数据的操作势必影响到与之相关的 另一类数据，因而操作带来的数据一致性? 7 i 操作效率问题是g i s 数据操作的主要问题。 地理数据的分析，即窄间分析，是g i s 得以广泛应用的重要原因之一。通过g i s 提供的空问分析功能，用户可以从已知的地理数据中得出隐含的重要结论。g i s 的空问 分析可以分为两大类：矢量数据空问分析和栅格数据空问分析。 ( 4 ) 数据显示、结果输出 数据显示是中间处理过程和最终结果的屏幕显示，包括图形数折；n 勺数字化与编辑以 及操作分析过程的显示：结果输出有专题地图、图表、表格和报告等各种类型的硬拷少! 一5 一 - f 岳：i l l 【l 力人学渺：学位沦义 图形，输出形式通常有两种：在计算机j 并幕- i - k i 示或通过绘图仪输出。 ( 5 ) 数据更新 数据更新即通过删除、修改、再捅入h ? 系夕0 操作以新的数据或记录替换数据文f ， 或数据序列中杆i 对应的数据或记录。但现实中g f s 的数据更新往往有时滞性。 2 3 地理信息系统开发方式 2 3 1 应用型gis 开发的三种实现方式1 ( 1 ) 独立开发 独立开发指不依赖于任何g i s 工具软件，从空i 刈数据的采集、编辑到数据的 处理分析及结果输出，所有的算法都由开发者独立设计，然后选用某种程序设计语 言，如v i s u a l c + + 、d e l p h i 等，在定的操作系统平台上编程实现。这种方式的 好处在于无须依赖任何商业g i s 工具软件，减少了开发成本，但一方面对于大多 数开发者来说，能力、时间、财力方面的限制使其开发出来的产品很难在功能上与 商业化g i s 工具软件相比。 ( 2 ) 单纯二次开发 单纯二次开发指完全借助于g i s 工具软件提供的开发语言进行应用系统开 发。g i s 工具软件大多提供了可供用户进行次开发的宏语言，如e s r i 的 a r c v i e w 提供了a v e n u e 语言，m a p 【n n 公司研制的m a p n f op r o f e s s i o n a l 提供 了m a p b a s ic 语言等等。用户可以利川这些宏语言，以原g i s 二 具软件为开发平 台，开发出自己的针对不同应用对象 i , o 应用程序。这种力+ 式省时省心，但进行二次 开发的宏语言，作为编程语言来讲其功能比较弱，用它们来开发应用程序仍然不尽 如人意。 ( 3 ) 集成二次开发 集成二次开发是指利用专业的g i s 7 1 1 具软件，如a r c v i e w 、m a p i n f o 等，实 现g i s 的基本功能，以通用软件开发工具尤其是可视化开发工具，如d e l p h i 、 v is u a l c + + 、v is u a lb a s ic 、p o w e rb u i1 d e r 等为开发平台，进行二者的集成开发。 集成二次开发目前主要有o l e d d e 和g i s 控什两种方式： 2 3 2 三种实现方式的分析和比较 由于独立开发难度太大，单纯二次开发受g i sj 厂具提供的编程语言的限制也 强人意，因此结合g i s 工具软件与当今可视化于r 发语言的集成_ 次开发方式就成 为g i s 应用开发的主流。 一6 一 三北巳力大学硕：l ：学他沦文 集成二次开发的优点是既可以充分利用( ：+ l ：儿软件对空问数抛库的管胖、 分析功能，_ 义可以利用其它可视f t ”发语言具有的高效、方便等编程优点，集独立 丌发与单纯二次开发之所长，4 i 仪能大大提高应用系统的丌发效率，而f t 使用可视 化软件开发工具开发t 来的应刷程序具有更好的外观效果，更强大的数据库功能 可靠性好、易于移植、便于维护。jc = 其是使用o c x 技术利用g i s 功能组件进行集 成开发，更能表现出这些优势。 口前许多软件公司都开发了很多a c tiv e x 控件，合理选择和运川现成的控件， 减少了开发者的编程工作量，使开发者避开某些应用的具体编程，直接调用控件， 实现相应的具体应用，不仅可以缩短程考：开发周期，使编程过程更简洁，用户界面 更友好，而且可以使程序更加灵活、简便。与利用0 l ea u t o m a t i o n 技术作为服务 器的开发方式相比，利用控件开发速度快，占用资源少，而且易实现许多底层的编 程和开发功能。 2 4 本章小结 本章对地理信息系统的组成、功能等做了简要的描述，i 司时分析比较了应用型g i s 的i 种开发方式，本章内容是开发前面提到的配电信息管理系统的理论基础。通过对i 种开发方式在系统运行时间、初始费川、人力费川、灵活性、技术要求和现有资源的利 用等方面的比较，本文中的配电网信息管理系统的开发选择y - - 次集成开发方式。 - 7 - ! ：l 匕 也力大学顺：i ：学位沦义 第三章蚁群算法及改进 蚁群算法( a n tc o l o n yo p tim iz ajo n ，a c o ) 最早是由m a r c od o t ig o 等人在l9 9 1 年首次提出的，被称为蚂蚁系统( a n ts y st e r n ，a s ) ，主要通过一种i ll i 做信息素的 物质对信息进行交流，根据信息素的多少进行选择和更新，通过数次迭代产生伞局 最优解。蚁群算法来源于对自然界蚂蚁寻找从蚁巢到食物的最短路径并找到回巢路 径方法的研究。它是一种并行算法，所有“蚂蚁”( 个体) 独立行动，没有监督机 构：它是种合作算法，每一只“蚂蚁”选择路径时，有残留信息的路径被选中的 可能性要比没有残留信息的路径人得多；它足一种鲁棒算法，因此只要对算法作小 小的修改，就可以运用于别的组合优化问题。 3 1 蚁群算法背景介绍 群居的社会性昆虫往往能够表现m 一种令人惊讶的复杂形态，从中也触发了研 究的热情。最近，计算学家纷纷开始把关于社会性昆虫的特殊行为的研究，运用到 一些“多智能体”的算法设计中。特别令人感到新奇的足关于“蚂蚁社会行为”的 研究：这是一个全新的领域，现在已经形成了些算法，例如“蚁群算法( a n t a l g o r it h m ) 。在“蚁群算法”中，一些由大量的简单智能体一一蚂蚁( a l l t s ) 组成 的团体，能够有效的完成一些复杂的任务，例如食物来源的优化和控制。每个蚂蚁 智能体都根据路径上的状况作随机的选择，最终整个蚁群却能够得到优化”一。蚂蚁 的这种选择路径的过程被称为“自催化行为”( a u t o c a t a l y t i cb e h a v i o r ) 。 在 m a r c od o r i g o 最早提出的摧本蚁群系统( b a s i ca n ts y s t e m ，b a s ) 中，给 出了二三种不同的模型；它们之间的区别在于：其中两种模型利用的是局部信息，而 另一种为整体信息。众多研究已经证明蚁群算法具有很强的发现较好解的能力，这 是因为该算法利用了正反馈原理，在一定程度上加快进化进程，可以理解成是一种 增强型学习系统( 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 ) ；而且是一种本质并行算法，并且 它具有通用性和鲁棒性，是基于总体优化的方法33 。但该算法本身也存在一些缺陷， 如搜索时间较长，而且容易出现停滞现象等。 目前对蚁群算法的研究，刁i 仅有算法意义一l 的研究，还有应用模型的研究，并 且不断有学者提出对蚁群算法的改进乃：有的将蚁群算法r 卜遗传算法棚结合，有 的给蚁群系统加入变异特征，还有的提出所谓最大最小蚁群算法( m m a s ) 。但是， 现阶段对蚁群算法的研究大多还只是停留在仿真阶段，尚未能提出一个完善的理论 分析，对它的有效性也没有给h 1 严格的数学解释。但是，从以前模糊控制所碰到的 情况看，理论上的不完善并不妨碍应用，有时应用还会超前于理论，并推动理论研 究，蚁群算法也是如此1 。为此本章尝试根据配电网最佳抢修路径的特点对蚁群算 一r 一 华：i 匕 u 力大0 1 阿i 二l ：筝f t 沦文 法进行改进并将其运用到最佳路径- 4 之f 0 4 ：当中。 3 2 基本蚁群算法 蚁群系统是最早随着蚁群这个概念提出来的算法，它尚先被成功地运用于t s i 问题。 虽然与己经发展完备的一些算法( 如g a ) 等比较起来，基本蚁群算法计算量比较人，而 且效果也并不一定更好，佩是它的成功运用还是激起了人们对蚁群算法的极大兴趣，并 吸引了一批研究人员从事蚁群算法的研究。a s 的优点在于：能迅速找到质量较好的解； 分布式计算可以避免不健康的收敛：强启发能在早期的寻优中迅速找到合适的解决方 案。a s 算法被成功地运用丁许多能被表达为在图表上寻找最佳路径的问题。 3 2 1 基本蚁群算法原理 自然界中像蚂蚁这样几乎没有视力的昆虫有很多，它们早如f - - i 找到由其巢穴到 食物源之间的最短路径的? 生物学家经过长期大量细致的观察研究后发现，蚁群之 所以能相互协作，完成复杂的任务，个体之问的信息交流与相互协作起着重要的作 用。蚂蚁在运动过程中会在其经过的路径上留下一种叫做外激素( p h e r o m o n e ) 的 信息物质。蚂蚁个体之间的信启、传递就是依靠这种物质进行的。一方面，每只蚂蚁 在其走过的线路上留下一定量的信息物质，且留在路径上的信息物质随时间逐渐衰 减。另一方面，后来的蚂蚁能够感知这信启、物质并以路径上残留信息量的多少指 导其行为，信息最越大的路径，被选中的概率也越大。显然，蚁群搜索食物源的过 程是信息量的一个正反馈过程。据此，蚁群可以快速地找到由巢穴到食物源的最佳 路径m 】。 a e ch c hc 图3 1蚁群搜索食物路线示意幽 蚂蚁选路过程中较短路径卜遗留的信息量会在很短时问内大于较长路径的原 理可用图3 1 来说明。图中a 点是蚁群的巢穴，e 点是食物源，从a 点到e 点川有 两条路径a b h d e 和a b c d e ，其中b h 和h d 间距离为1 个单位， b c 和c d 间距离为0 5 个甲位。假译在个时间t ：f j 元内有3 0 只蚂蚁由a 点到 - 9 - r # ：l 匕l 乜力大学颂：i ：学战沦义 达b 点，j j 样有3 0 只蚂蚁f | - i s 到达d 点。 最初( 即t = 0 时刻) ，当蚂蚁走到分支路口b 或者d 点时，婴决定往哪5 个方向 走。因为初始时没有什么线索时供它们选择，所以它们就以相同的概率选择j l ! 径， 结果是有1 5 只蚂蚁走左边的路径d 一 l 、b i i ：另外l5 只蚂蚁走右边的路径【) 一c 、 b c 这些蚂蚁在行进过程中分别留下信息物质，若假发蚂蚁都具有相| 刊的速度( 1 单位距离单位时间) 和信息物质释放能力。则经过1 个单位时问后从d 点出发的 3 0 只蚂蚁有1 5 只到达了h 点，有15 只经过c 点到达了b 点，同样的从b 点出发的 3 0 只蚂蚁有1 5 只到达了i i 点，有l5 只经过c 点到达了d 点。很显然，在相等的时 间阳j 隔内路径d h b 上共有i5 只蚂蚁经过1 ：遗留了信息量，d c b 上却有：3 0 只蚂蚁经过并遗留了信息量，其信息量强度足d h b 路径上的2 倍。因此，当3 0 只蚂蚁分别回到a 、e 点重新选择路径时就会以2 倍于d h b 的概率选择路径d c b 从而d h b 上的蚂蚁数目变成了1 0 只，是d c b 上蚂蚁数目的一h 距离较短的路径上信息量很快得到了强化，其优势也很快被蚁群所发现。 人工蚂蚁寻找最优路径的方法就是根据上面的真实蚂蚁寻找最优路径的方法 提出的，即让人工蚂蚁根据路径上的柑当于p h e r o m o n e ( r j 数字信息量的强度选择路 径，并在所经过的路径上留下相当于p h e r o m o n e 的数字信息量，然后随着时1 1 1 l j 的推 移，最优路径上的数字信息量将积累的越来越大，从而被选择的概；红也越来越大， 最终所有人工蚂蚁将趋向丁选择该路径1 1 ”1 。 3 2 2 蚁群算法描述 3 2 2 1 算法的特征 蚁群算法利用简单个体一蚂蚁，不断迭代地的构造组合优化问题的候选解。蚂蚁解 的构造是由信息素和启发式信息来指导的。原则上通过定义解的分量蚁群算法能够用于 各种组合问题。一只蚂蚁开始时使用一个审解，然后重复增加解的分量直至产生一个完 整的候选解，这样米构造候选解。在每一：- 选择点上，蚂蚁必须决定那个解的分量要加 到它的当前部分解。解的构造完成后，蚂蚁将他们构造的解给予f 反馈，通过将信息素 投放到使用的解的分量上。 给定n 个城市的t s p 问题，人j 二蚂蚁数量为m ，这些人上蚂蚁具有记忆功能每个人 工蚂蚁具有以下特征n 引： ( 1 ) 根据信息素浓度和启发式信息，用相应的转移概率选择下一个城市； ( 2 ) 将已经走过的城市放入记忆表，而记忆表中的城市不再被选择为下一个城市； ( 3 ) 完成一次环游后，根据整个路径的长度来释放相应的信息素，并更新走过的路 径上的信息素。 一l o - p ：i i ：f 【l 力火7 产f f t i ：卜学位沦义 ( 4 ) 两个重要公式 城市i 的第k 只蚂蚁在f 时刻选择下一个城i 的转移概葺： 只( i ，j ) = j n j 仨n 。 其中，z - 。表示边( i ，j ) 上的信息素浓度； ，7 ，= l i d 为从城市i 到城市j 的期望程度： d 。为城市i 与城市j 的距离； 。代表第k 只蚂蚁在i 节点的可通行性表，即该蚂蚁还未访问过的节点： 口，分别为信息素浓度r ，和l 划望程度7 7 ，的作用系数；口一般取值范围应 该在( 0 ，5 ) 之间；一般取口5 ；当口= 0 时，算法就是传统的贪心算法： 当= 0 时，就成了纯粹的正反馈的启发式算法 信息素更新规则： t , j ( f 十1 ) = ( 1 一p ) z 口( f ) + a r ： = i 公式( 3 2 ) 其中，p 为信息素的保留比例，是一个在0 和l 之间取值的常数，l p 表 示在连续两次寻优过程问信息紊的挥发，该参数口j 以避免无限度的增强信息索 的浓度。当一条道路没有被任何蚂蚁选择到时，这条道路上的信息素浓度会呈 指数级的减少，所以该参数还可以帮助算法“遗忘”过去时刻的“错误选择” 或者“不良选择”。 r ：是第k 个蚂蚁在t 时刻到( t + 1 ) 时刻之间，在边( i ，j ) 上增加的信 息素变量。它的值由下式确定： ， 呓= 孑7 篓薏? a ，j ) 被蚂蚁尼使刷 公式( 3 3 ) 是蚂蚁k 本次环游一周的长度： q 是一个常数； 3 2 2 2 算法的实现过程 1 算法步骤描述 ( 1 ) 初始化： 定义一组人工蚂蚁，4 9 - 蚂蚁分布于各个城市( 开始城市) ； 初始化r ，和r 各路径上信息量强度，通常可设为j ：w i n 。： ( 2 ) 构造环游： 对每只蚂蚁用转移概率在l u 通行表c m q 城市驰选择翻多动的下个城市，将所 选城i h 从u j 通行表巾去掉： 每只蚂蚁环游一圈后，汁算环游k 度，更新各条边信息索浓度( 局部史新) 。 ( 3 ) 全局更新信息索： 所有蚂蚁环游一圈后，按信息索更新规则更新备条路径上的信息素浓度： 比较所有的环游长度，找出长度最短的环游路径： 将记忆表清空，回到步骤( 2 ) ： r 4 1 不断迭代直至满足停止条件。 停止条件一般是设定迭代次数或满足相邻两次迭代的环游【丈度之差小于设定值。 2 算法流程图： 罔3 2蕺本蚁群非法流程罔 由上述可知，蚁群算法优化过程的本质在于：( j ) 选择机制。信息量越大的路径 一1 2 - i t l 也力大学顺1 j 学他沦义 被选择的概率越大；( 2 ) 更新机制。路径1 f f i i f l j 能0 、量会随蚂蚁的经过而增k ，小也 随着时间的推移逐渐减小；( 3 ) 协调机制蚂蚁之间实际上是通过信息量来互棚通信、 仂、同上作的。这样的机制使得蚁群算法具有很强的发现较好解的能力。 3 3 蚁群算法的改进 蚁群算法的主要特征是正反馈、分布式汁算以及运用贪婪启发式搜索。正反馈有助 于快速发现问题较好的解：分布式汁算可避免在迭代过程中出现早熟现象；而运用贪婪 启发式搜索贝0 可使搜索过程中较早地发现可接受解。到目前为1 i ：，蚁群算法在许多领域 已经取得了令人瞩目的成功。 一系列的研究表明，基本蚁群算法求薯最短路径过程中经常出现两个问题：第， 搜索陷入最优解，即搜索进行到一定程度后，所有的个体发现的解基本完全一致，出现 停滞现象，不能再对解空间进一步搜索，导致口j + 能无法找到全局最优解：第二，收敛到 全局最优解的时间长，求解结果反复在局部最优解和全局最优解之间震荡”“。 针对匕述基本蚁群算法的缺点，主要改进的进行是围绕选择概率模型和信息素更新 规则的设计。其中既包括了对于纯粹的蚁群算法的改进，也包括了引入其它优化算法对 蚁群算法的性能进行提高。争取在扩大解空间搜索的同时加快算法收敛的时间，以满足 配电网抢修的实时性要求。 3 3 1 变换状态转移准则 在路径( i ，j ) 处，传统蚁群算法的寻径概率仅仅是根据r 口和决定的，现在加 入两个参数g 和g 。，g 表示一个随机变量，可以在某个区问，如 0 ，1 之间取值，q 。是 一个适当选定的阈值。蚂蚁在选择下一个路径之前先进行次随机试验得到g ，根据g 和 吼的比较结果选择相应的概率计算公式瞄”。 如果，g g 。贝u ： 棚，= 矗挈“叫“ ，巧r ) 刖= f 帮嚣 公式( 3 4 ) 公式( 3 5 ) 通过上面的改进虽然可以获得定的效果，但是若q 。较大，则多数蚂蚁仍然倾向于 选择信息量最大的边，在搜索过程中可能容易m 现多数蚂蚁搜索到相同的路径，使得搜 索到的解空间较小，不利于发现全局最优解，算法收敛到局部最优解的可能性大。若口。 一1 3 其中门。，门分别为迭代次数；门。、为最大迭代次数： 0 8 c l 1 ，0 c o 0 4 ： 式( 3 6 ) 表明，算法开始时为加速算法的收敛，以较大概率选择信息量最大的边， 使得较好的路径上的信，色、量明显高于其他路径上的信息量。直到迭代到笫胛。次。此后， 为了防止搜索陷入局部最优解，便于发现全局最优解，以较大的概率在局部最优解的邻 域中搜索其它解，直到迭代到第九。次。为了使算法收敛到全局最优解，门。次后再以较大 的概率选择信息量最人的边，直到运行结束。 变换状态转移准则的优化原理就是若仅仅依靠路径卜的信息素浓度的变化来确定 下一个选择的道路，则由于某些已经找到的当前“最优”或“较优”的道路上的信息量 远远高于其他路径上的信息量，而此路径。：一定是全局最优的，会导致随后的搜索出现 停滞现象：因此采用随机的方式用些新的寻找下一路径的规则，适当的体现局部的优 化权重，同时改善搜索的灵活性n 二“。但是如果完全或很大程度卜抛弃信息素的影响， 在某些情况下( 5 0 节点以下) 就不会有良好的效果。 3 3 2 局部搜索算法选择 选择合适的局部搜索算法，能扩大搜索空间，有利于发现全局最优解。有一些有效 的基本搜索算法可以快速形成最短路径问题大最的可行解。这些解有着j l f 常大的差异， 质量良莠不齐，但是却都是相对而言“没有重大缺陷”的解；也就是说，虽然这些算法 本身所得到的解并不是最优，但是它却能够做到最基本的没有交叉的优化程度。所以在 运用蚁群算法进行最短路径优化的同时，基本的去交叉算法也应该被运用；特另0 是在算 法的初期，如果能运用些有效的去交叉算法，就能够创造出大量的有着很大差异的， 优化过的可行解，有效改善蚁群算法发现更优解的能力，避免潜在的己经发现的新解被 错误的丢失比制。 最短问题的最终解是一个不存在交叉路线的解，女果仅仅依靠蚁群算法来去除这些 存在着交叉现象的解，效果并不明显。较好的去交叉法有k o p t 法，譬如3 - - o p t 法，就 是对于当前找到的一个路径，从中随机选取三个节点进行交换，对于得到的6 个新的路 径，取总长较小的一个作为下一寸, - a 匕ku 阱j ：- - 。化的原始路径。3 - - o p t 一共需要0 ( 1 1 3 ) 次如 上的交换才能获得一次循环的“最优解”( 算法收敛) ，这一做法可以扩充到k 点。女| f 果k 1 4 一 华： 匕电力大学顺? i j 学他论义 越大，则去交叉的效果越好，但是计算量也变得越来越大，交换所需的次数也增加到o ( n 。) 次。为了伏_ 侧7 - u ；- i h - q 匕5 r 。u 、f f 算时间的矛盾，也经过实验，发现2 - - o p t 不l j3 一o p c 对于改 善系统的启发性的效果比较明显而h 速度较快。而如果使j | l4 一o p t 以上的去交叉法，针 对一个5 0 个节点的最短路径问题，它对每个可行的路径就需要o ( 5 0 4 ) = 6 2 5 0 0 0 0 次 交换，显然很难收到好的成效；相反，2 - - o p t 年l l3 - - o p t 计算量的数量级就小得多。图3 3 图3 3 2 一o p t 去交叉原理图 因此，如果在蚁群算法中同时加入2 - - o p t 和3 - - o p t 去交叉对于改善算法收敛速度 有很好的作用。如果计算机速度较慢，可以使用2 一o p t ，也可以混合使用2 一o p t 和3 - - o p t 。同时在实际使用中，根据问题的规模，最好先试验确定k - - o p t 迭代优化的次数， 如5 0 个节点，2 一o p t 收敛的次数应该是7 0 0 次左打。 遗传算法是一种发展比较成熟且被广泛应用的一种迭代自适应概率搜索算法。受遗 传算法的启发，将变异思想引入到局部搜索算法，给出一个具有变异特征的局部搜索算 法。设蚂蚁k 搜索到从s 到丁的路径p 为：订o ( s ) ，( ，l ，a 2 ，人，a ，人，“，+ i ( t ) 。 a ( 0 a ，7 + 1 ) 为图it 的节点。给定变异率只，在门次循环lh 广生，7 个( o ，1 ) 内均匀分 布的随机数。若第7 ( 1 门) 个随机数， 只，则第“，个节点要发生变异。设存在节点 臼一，臼，和口，- l 相连外，有w 个节点a 小a 小人，日，- l 和“，- i 相连。进行w 次循环，产生w i i r 个( 0 ，1 ) 内均匀分布的随机数，若第t , 0 h w ) 个随机数r h 只( 尸、为给定的选择概率) ， 则用a 2 。代替以，得到1 个解p ：a o ( s ) ，口一! ，人，口2 ，人，“，+ 。( 丁) 。若路径p ：的值l e ：l k i ， 则用p ：作为蚂蚁k 搜索到的局部最优解。 实际应用中可以先用2 一o p t 算法去交义，然后使用上述变异算法对去交义后的路 径进行变异优化，两种搜索算法相结合更能加人对解审间的探测力度。 3 3 3 信息量更新原则调整 基本蚁群算法在每次循环之后，每只蚂蚁的信息素都叠加到道路上，那些找到了较 差路径的蚂蚁也会对系统的信息素分布发生影响，使得最优路径的优势无法体现。因此 每次循环应选取找到最佳路径的蚂蚁进行信息反馈，以避免无效信息的干扰。也就是将 式( 3 2 ) 改为： r i j ( f + 1 ) = ( 1 一p ) f ( f ) + r 7 公式( 3 7 ) 一1 5 一 r 8 ，i b l u j 大学顶二l 二学位沦义 i 司样的思路也可以有其 f 也f 1 9 优化力法：在本次搜索没何找到全局更优解的前提下， 所有的蚂蚁都不对路径上的信息素做任何更动，同时蒸发因子l i l 不发挥作用，只有找到 更优解的蚂蚁才能对系统的信，目，素产生影响n “_ 。 综合卜述思想，现对信息素强度更新原则作m 如卜渊整： 为避免后来的蚂蚁只在当前所走过的优化路径附近寻路，每当一只人： 蚂蚁完成一 次搜索时，进行信息索强度的局部更新k 9 1 。 如果路径( ? ，) 是蚂蚁k 所选择的前进路径，则按t a 调整其相应的信息素强度：否 则，不作调整。 r ：= ( 1 一p ) z - ： 公式( 3 - - 8 ) 为了使算法较快地收敛到全局最优解，采用下式对信息量进行全局更新： r ，7 f i ：d - p ) r + f ；o c y k = l c 7 e ，7 一 公x 一- u k , ：3 9 ) fj=：z0 l j 了， 【( 1 一p ) r i i + r 岁 ，7 l c y c l e ，7 。、 r ：= 孑肛 翼毳边a j 被蚂蚁尼使用 r = d 。差譬j ；票言掌萎竺篓蓑：条边 其中，d 。是蚂蚁k 求得的局部最优解； 公式( 3 1 0 ) 公