（模式识别与智能系统专业论文）中压配电网络自动规划的研究.pdf

中文摘要 配电网规划的任务主要是优化网络结构，寻找配电网络的最优扩展方案，通 过对网架路径的确定，使得整个网络在保证网络安全的基础上投资费用和运行费 用最小。对于配电网规划这样一个高度复杂的非线性问题，如何实现配电线路在 城市小区街道中的沿街铺设，获得可行的优化方案是本文研究的重点。 在分析和研究国内外配电网络规划方法的基础上，本文以蚁群算法、产生式 规则为理论基础，结合配电网地理信息系统( 配电网g i s ) ，研究提出基于改进 蚁群算法的配电网自动规划系统设计方案，本文主要工作总结如下： 1 研究了g i s 在配电网规划中的应用，完成了配电网g i s 中矢量地图的识 别及相关信息的提取，并形成了相应的地理信息知识库。 2 将配电线路的沿街优化铺设问题分为两个阶段，即寻找变电站负荷点的 点到点沿街最短路径问题和优化布线问题。( 1 ) 应用基本蚁群算法寻找变电站一 负荷点的沿街最短路径，形成一个待规划的初步辐射型配电网络规划图：( 2 ) 在 优化布线阶段充分利用第一阶段的布线结果，将其应用在蚁群信息素的初始化方 案和信息素动态更新原则中，并在转移概率模型中加入适合于负荷信息处理的产 生式规则。 基于以上几个方面的改进，形成适合于配电网络规划实际问题的改进蚁群算 法，通过对实际规划区域的仿真计算，证明了方法的有效性和实际应用价值。 关键词：配电网络规划蚁群算法地理信息系统产生式规则自动布线 a b s t r a c t t h em a i nt a s ko fd i s t r i b u t i o nn e t w o r kp l a n n i n gi st oo p t i m i z en e t w o r ks t r u c t u r e ， f i n di t so p t i m u me x t e n d e dp l a n t h eo p t i m i z a t i o na i mi st om i n i m i z et h ei n v e s t m e n t a n do p e r a t i n gc o s tw h i l em e e tt h ee n t i r en e t w o r k ss a f e t y f o rs u c hah i g h l y c o m p l i c a t e dp r o b l e m ，i ti st h ek e yp o i n tt og e tt h ef e a s i b l eo p t i m i z a t i o ns c h e m ew h i l e r e a l i z i n gt h ed i s t r i b u t i o nl i n e s a u t o m a t i cr o u t i n ga l o n gt h es t r e e t so ft h eu r b a n a f t e ra n a l y z i n gt h ee x i s t i n gm e t h o d so fd i s t r i b u t i o nn e t w o r kp l a n n i n g ，c o m b i n i n g t h eg e o g r a p h i ci n f o r m a t i o ns y s t e mo fd i s t r i b u t i o nn e t w o r kp l a n n i n g ，t h ea n tc o l o n y a l g o r i t h ma n dp r o d u c t i o nr u l e s a leu s e dt or e s e a r c ht h ed e s i g n i n gs c h e m eo f a u t o m a t i cd i s t r i b u t i o nn e t w o r kp l a n n i n gs y s t e m , t h em a i nw o r ko ft h i sp a p e ri sa s f o l l o w s ： 1 t h ea p p l i c a t i o no fg i si nn e t w o r kd i s t r i b u t i o np l a n n i n gi ss t u d i e d ，a n dt h e r e l a t i v ei n f o r m a t i o ni sr e c o g n i z e da n de x t r a c t e df r o mt h ev e c t o rg r a p hi nt h eg i s t h u s ，t h ec o r r e s p o n d i n gg e o g r a p h i ci n f o r m a t i o nk n o w l e d g ed a t a b a s ei sc o n s t r u c t e d 2 t h eo p t i m i z a t i o np r o c e s si sd i v i d e di n t ot w os t a g e s ：s e a r c h i n gf o rt h es h o r t e s t p o i n t - t o - p o i n tr o u t ef r o mt h es u b s t a t i o nt oe a c hl o a dp o i n t ，a n da u t o m a t i cr o u t i n g o p t i m i z a t i o n ( 1 ) t h eb a s i ca n tc o l o n ya l g o r i t h mi su s e dt os e a r c hf o rt h es h o r t e s t r o u t ea l o n gt h es t r e e t sf r o ms u b s t a t i o nt ol o a dp o i n t ，t h i sa l g o r i t h mc a ng e tt h e e l e m e n t a r yr a d i a ln e t w o r kp l a n n i n gg r a p ho fa l lu r b a na r e a ；( 2 ) a tt h ea u t o m a t i c r o u t i n go p t i m i z a t i o ns t a g e ，t h ei n i t i a ls t a g e sr e s u l t sa r ef u l l yu s e di n t ot h ei n i t i a l s c h e m eo ft h ea n tc o l o n y sp h e r o m o n ei n i t i a l i z a t i o na n dd y n a m i cu p d a t e s ，t h e p r o d u c t i o n r u l e sf o rp r o c e s s i n gl o a di n f o r m a t i o na r ea d d e di n t os t a t et r a n s f e r p r i n c i p l e s b a s e do nt h ea b o v ei m p r o v e m e n t s ，t h ep a p e rp r e s e n t sa ni m p r o v e da n tc o l o n y a l g o r i t h mf o rp r a c t i c a ld i s t r i b u t i o nn e t w o r kp l a n n i n gp r o b l e m s t h e s i m u l a t i o n r e s u l t so fp r a c t i c a lp l a n n i n gr e g i o n ss h o wt h ee f f e c t i v e n e s sa n dt h ea p p l i c a t i o nv a l u e o ft h ep r e s e n t e dm e t h o d k e yw o r d s ：d i s t r i b u t i o nn e t w o r kp l a n n i n g ，a n tc o l o n ya l g o r i t h m , 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 ( 6 i s ) ，p r o d u c t i o nr u l e s ，a u t o m a t i cr o u t i n g 独创性声明 木人j i - , 明听早交的。浮p 论迂垃本人存导帅指导卜进7 “i 勺, f i j l j lf 1 ：和u f ! “门 研究成果，除了文中特另t j ；h r l ：奠柄：和致谢之处外，论文中不包含i i 他人已纤技衣 或撰写过的研究成果，也不包翕为获得苤鲞盘堂或其他教育干j l ：；巾：。j ：- 7 ：f - 二，k 醑 书而使用过的材料。与我- i 一1 j 1 作的l 司志对奉研究所做的任何贞献均已往沦义tl ， 作了明确的说明并表示了谢意。 学位论文作者签名： 姻l 丽 签字丌期： 砌7 年l f 门乡 学位论文版权使用授权书 本学位论文作者完全丁解丕盗盘堂有关保留、使用学位沦义的胱定。 特授权盘鲞盘堂可以将学位论文的全部或部分内容编入自灭数捌库进 j 检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。i 司意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文礼舢带斤i 适用本授权说明) 学位论文f 1 睹签名： 拥舀确 导师签稆：潞丢袈 签字同期：如7 年；月弓同 签字同期：1 年莎 月；f | 第一章绪论 第一章绪论 城市配电网是城市现代化建设的重要基础设施之一，同时也是为用户提供优 质电能的关键环节。其建设的好坏直接影响到城市经济的发展，人民生活质量的 提高，投资环境的优化等。配电网络的规划是供电企业的一项重要工作，为了获 取最大的经济效益，配电网规划既要保证电网安全可靠，又要保证电网的经济 运行，所以配电网络规划的主要任务是，在可行技术的条件下，为满足负荷发展 的需求，制定可行的配电网发展方案。 1 1 城市中压配电网络存在的问题 我国的配电系统发展起步较晚，发展水平低，建设相对落后，配电网络缺乏 合理的规划和建设。城市配电网自动化水平和发展状况相对落后。 以前，我国电网规划设计部门很多使用的是传统的以方案比较为基础的电网 规划方法。由于参加比较的方案往往是规划设计人员凭经验提出的，不可避免的 包含很大的人为因素和局限性，因此最终选出的不一定是最优方案。 目前，我国城市中压配电网的发展还存在的主要问题【1 2 】表现在：中压配电 网的网架结构薄弱；城市配电网技术落后，网络自动化水平低；线路损耗较高、 电压合格率较低；绝缘水平低；供电可靠性低等。从以上分析可知：目前我国 部分城市配电网的突出问题是：可靠性低、电能质量差、停电时间长。 所以如何提高我国电网规划水平已经受到了日益广泛的重视。 1 2 中压配电网规划的特点 中压配电网规划问题有如下特点e 3 , 4 j ： ( 1 ) 动态性：网架规划不仅要满足规划年限内的经济、技术等性能指标要 求，而且要考虑到今后网络的发展以及网络性能指标的实现问题。 ( 2 ) 非线性：线路电气参数与线路功率及网损等费用的关系是非线性的。 ( 3 ) 多目标性：规划方案不仅要满足经济、技术上的要求，还必须考虑社 会、政治及环境等因素，这些因素常常是相互冲突和矛盾的【5 1 。 ( 4 ) 不确定性：负荷预测、设备有效度及其他条件等均存在显著的不确定 第章绪论 性。 ( 5 ) 线路呈辐射状：由于配电网线路一般呈辐射状运行，每个用户只从一 个电源受电，各变电所所带用户之间是独立的，所以配电网潮流、规划要按辐射 网来计算，线路不能随意组合。 因此，从数学上讲，网架规划是一个动态、多目标、不确定性、非线性、整 数规划问题。要想解决这个复杂的问题，不进行一些技术上的假设和简化是不可 能的。根据简化手段的不同，形成了众多有特点的规划方法。 1 3 配电网络规划的目的和意义 随着现代工业、商业、服务业和农业的不断发展及人民生活水平的日益提高， 电力的供应和消耗己渗透到社会生产、人民生活的各个角落，社会对电力的需求 量越来越大。同时，产业结构的调整，城市土地使用制度的改变也对电力供应提 出了新的要求。这些变化和要求使电力系统面临着更复杂繁重的规划任务。电力 工业的发展水平不仅对国民经济的其它部门会产生重大的影响，而且一次能源消 耗和投资的数量也相当巨大。所以，合理地进行电力系统规划不仅可以获得巨大 的社会效益，也可以获得巨大的经济效益。 通过配电网络的规划，优化配电网络结构，不但可以保障电网的安全运行、 降低电能损耗、提高供电可靠性，适应市场经济快速发展的需求，更好地满足社 会经济的发展和人民生活水平的提高对用电的需求，同时也为国家和电力企业带 来客观的经济效益【6 】。 因此，对电力系统规划问题进行研究，以期最大限量地提高规划质量，具有 重大的现实意义。 1 4 国内外研究现状和发展方向 我国的城市电网在经历了建国初期的恢复建设，6 0 7 0 年代的初步发展期后， 从8 0 年代起进入了一个崭新的发展阶段，9 0 年代以来，随着城市经济的高速发 展，对城市电网的供电能力和质量安全都提出了更高要求。1 9 9 3 年由原水电部 和建设部颁发的2 2 8 号文城市电力网规划设计导则，对加强城市电网规划工 作起到了重要的推动作用。2 0 0 1 年建设部又修编出台了城市电力规划规范， 对城市配电网发展规划具有重要的指导意义，各省市或重要城市也均出台了相应 的城市电网( 或配网) 改造技术导则。近年来，随着农村配电网及城市电网改造 的不断深入，新产品、新设备、新技术的不断应用，国家及各地方又相继出台了 第章绪论 相应的规划改造技术原则，有效地指导了城市配电网的改造，而且在一些科研院 所及大学的技术支持推动下，出现了一些很好的配电网的规划设计方法及相关软 件【7 】o 目前，国内外已经有很多关于配电网络规划的问题的研究成果： 线性规划算法( 如单阶段模型和多阶段模型1 8 - 1 3 ) 将运筹学中的优化算法应 用于配电网规划问题，简化忽略了很多重要的约束条件，难以求解大规模的组合 优化问题，9 0 年代以后，线性规划在配电网规划中应用的研究已经很少了，人 们在积极探索更加有效的算法。 传统优化算法( 如支路交换法 1 4 - 1 5 】) 与初始解的选取有密切的关系，对于负 荷数据不确定、参数估计不准确的配电网规划，难以确定一个离最优解较近的初 始解。而且传统优化算法在求解配电网规划问题时，往往对问题作如下简化：将 变电站和馈线系统分开规划；将非线性问题线性化：将多阶段问题分解成单阶段 问题；不考虑配电网的辐射状运行约束：不考虑可靠性。这使得所求出的解只是 在某一特定条件下的局部优解【1 6 】。所以用传统最优算法来规划配电网误差较大， 有可能脱离实际。 现代智能随机搜索方法的应用为网架优化提供了新的思路。遗传算法【1 7 】是求 解全局优化问题的随机搜索算法，通过杂交、变异等一系列算子的操作产生优良 的迭代结果，其效果在配电网络规划中得到一定的认同，但是编码问题的存在导 致大量不可行解的出现，从而直接影响了算法的搜索效率。进化策略【l8 】与遗传算 法一样属于模拟进化算法，但更重视变异的作用。禁忌搜索算法【l9 】是一种单线随 机搜索算法，同其它算法结合，具有强大的全局搜索性能，但局部搜索性能易受 分散性的影响。模拟退火算法【z u j 利用概率突跳性在解空间中随机寻找目标函数的 全局最优解，也与其它方法相结合【4 7 j 应用到了配网规划中。 1 5 本文的主要工作 城市配电网规划中，将进行负荷预测、变电站选址与定容、配电网络规划和 无功优化等各项工作，其中在负荷预测和变电站选址与定容的基础上进行的配电 网络规划，是一项复杂而重要的工作。 本文对城市中压配电网络规划中的网架优化进行了研究，基于g i s 平台，应 用改进的蚁群算法，提出了一套中压配电网络自动规划的方案。具体工作包括以 下几点： ( 1 ) 依据现在电网规划设计中较多的应用地理信息系统( 简称g i s ) 技术 的特点，分析了g i s 在中压配电网络规划中的应用，完成了城区规划地理信息图 第一章绪论 中的街道信息和负荷信息的自动识别与提取，建立了地理信息知识库，将空间数 据转换成适合网架优化开发工作的数据结构。 ( 2 ) 研究了基本蚁群算法的原理、模型和发展应用，根据其在形成辐射状 网络及路径搜索方面的突出优势，将其应用在寻找变电站负荷点的沿街最短路 径的研究中。 ( 3 ) 分析网架优化的目标函数，从而指出优化布线的约束条件，依据约束 条件的要求设计出适合于中压配电网络规划实际问题的蚁群优化策略，主要包括 在信息素初始化及信息素动态更新模型中采用基于变电站点一负荷点最短路径的 信息素处理方法；在转移概率模型中加入处理负荷信息的规则库。有效提高了算 法的执行效率及解的质量。 ( 4 ) 总结提出了基于复杂算法，应用于网架优化的配网自动规划系统，实 现自动布线功能。 4 第二章g i s 在中压配电网络规划中的应用 2 1 引言 第二章g i s 在中压配电网络规划中的应用 以前，我国电网规划设计部门很多使用的是传统的以方案比较为基础的电网 规划方法。由于参加比较的方案往往是规划设计人员凭经验提出的，不可避免的 包含很大的人为因素和局限性，因此最终选出的不一定是最优方案。在配电系统 中应用地理信息系统( g i s ) 【2 ，为配电网规划提供了新的思路。g i s 在电力系 统中的应用虽然刚起步，但是在电力生产和管理上已经发挥了重要作用。 本章主要研究配电网g i s 中地理数据的处理工作，即提取配电网络原始地图 中的有用信息，从而形成适用于配电网络规划的地理信息知识库。 2 2 空间数据结构 配电系统可以拓扑成g i s 系统中的各个要素。g i s 将空间事物抽象成点、线、 面三种基本类型，而g i s 除了记录空间目标几何图形数据外，还要考虑与他相关 的属性信息以及空间目标的相互关系【2 2 1 。以满足空间查询和空间分析的需要，如 图2 - 1 。 i 一。 属性数据 空间数据 图2 1 属性数据与空间数据的关联 配网具有上述三种类型数据，如变电站、负荷点可以用一个点的坐标数来表 示其空间位置，属于“点”数据类型。而它的属性可以有多种描述，例如，对于 一个负荷点来说，可以有几十个属性，包括负荷预测值、所在小区编号、所在中 区编号等：配电线路、街道的空间数据可以是一线状的坐标串，也可以是一封闭 坐标串，属于“线”数据类型；而供电区域则属于“面”数据类型。这样，变电 站、配电线路、供电区域之间的关系被抽象成g i s 中的点、线、面之间的关系。 而矢量地图中属性数据与空间数据相关联，这样与常规配电网络规划考虑的问题 也是一敦的。 第二章g i s 在中压配电网络规划中的应用 在一条街区中，街道的边缘即是不同用地类型所形成的各小区的边界，这样， 小区内的负荷和供电网之间通过街道这级空间单元的过波面建立起联系。 2 3 矢量地图数据的处理 在城市配电网中，配电网络、变电站及设备、用户及负荷等资源均是按照地 理位置分布的，在进行配电网络规划之前，负荷的位置和预测值、变电站的位置 和容量以及供电区域划分均已在负荷预测和变电站选址与定容工作中完成，因 此，配电网络规划原始矢量地图已经存在，为了以后规划工作的方便，需要对原 始图进行处理。 图2 - 2 规划原始矢量地图 图2 - 2 为一张规划原始矢量地图( a u t o c a d 图) ，为了实现配网规划中配电 线路的沿街优化铺设，需要提取的信息主要有：街道信息，以及负荷点、变电站 与街道的相互关系。 2 3 1 提取方法 应用a u t oc a d 的二次开发工具o b j e c t a r x 处理矢量图形数据，无疑是一 个好的方法。它具有功能强大，编程效率高的特点，而应用n e t 阵营的开发语 言c 群，又结合了c # 语言较之v c + + 易学易用的特点，可以快速地开发出功能强 大的程序实现相应需求。 6 第二章g i s 在中压配电网络规划中的应用 ( 1 ) o b j e c t a r x 开发环境【2 3 】 o b j e c t a r x 是一种崭新的开发a u t o c a d 应用程序的工具，它以c 系语言为 编程语言，采用先进的面向对象的编程原理，提供可与a u t o c a d 直接交互的开 发环境，能使用户方便快捷地开发出高效简洁的a u t o c a d 应用程序。 使用o b j e c t a r x ，首先要确定目标平台，获得适当的开发环境。一般来说， o b j e c t a r x 开发包的版本和a u t o c a d 的版本是对应的。本文所使用的开发平台 如下： a u t o c a d2 0 0 8 v i s u a ls t u d i o2 0 0 8 o b j e c t a r x2 0 0 8 开发包 由于提取的大量原始数据需得到合理的存储备份，因此软件的开发过程中还 应用到数据库，这里选择s q ls e r v e r2 0 0 0 数据库。 ( 2 ) 小区及负荷信息提取 配电网络规划中的小区对应于a u t o c a d 空间数据中的闭合轻量多段线类 ( p o l y l i n e ) ，负荷点对应于块参照类( b l o c k r e f e r e n c e ) ，要想获得所有的小区及负 荷数据，需要应用选择集和过滤器来遍历和筛选符合特定条件的实体。 选择集【2 4 1 用来选择符合要求的对象，既被用户或程序所选择的一组实体， 允许用户同时选择多个图形对象，同时提供了丰富的手段来选择符合特定条件的 实体。选择集涉及到的类比较多，主要是选择集用户交互类 p r o m p t s e l e c t i o n o p t i o n s 和用户提示类p r o m p t s e l e c t i o n r e s u l t ，还有表达选择集本 身的s e l e c t i o n s e t 类，以及用来表示过滤的s e l e c t i o n f i l t e r 类等等。选择集通过调 用g e t s e l e c t i o n 及s e l e c t x 函数来实现，本文主要用到s e l e c t a l l 函数来选择 用过滤器过滤后的所有实体。 过滤器用来限定选择的对象，本文主要用到如下过滤器类型来标识过滤条 件： ( d x f c o d e s t a r t ) ：对象类型，这里用到“p o l y l i n e ，而块参照比较特殊， 它所使用的类型名称为“i n s e r t ”。 ( d x f c o d e t e x t ) ：图元的主文字值，这在提取块参照的属性时将用到。 ( d x f c o d e b l o c k n a m e ) - 对象名，本文用来限定块参照的名字。 ( d x f c o d e l a y e r n a m e ) ：图层名，这里限定所提取的小区和负荷信息所 在的图层。 本文程序中主要使用与配电网络规划用户交互的方式来限定选择条件，如下 图对话框所示： 第二章g i s 在中压配电网络规划中的应用 国2 - 3 信息提取及 库过程中的参数设置 提取小区信息的选择集限定：提取带有负荷点的所有层，小区图形限定为多 段线( 避免线路不连续，重复划线) 。不要使用单线段，因为单线段极易出现断 点和重复划线现象，影响识别的准确率。块属性限定，只提取块属性名为“i n b l k ” ( 即表示负荷点信息的块属性) 的块的相关信息。 值得说明的是：这里使用选择集的目的是为了读取选择集中的实体，这就必 须使用事物处理来遍历选择集中的实体，得到它的对象o b j e c f l d 。然后以读的方 式打开它，最后提交事务处理完成读取。不然，将产生错误。使用和提交事务处 理的代码如下； d o c u m e n t d o c = a u t o d e 出a u t o c a d a p p l i c a f i o n s e r v i c e s a p p l i c a t i o n d o c u m e n t m a n a g e r m d i a c t i v e d o c u m e n t ； d a t a b a s e d b = d o c d a t a b a s e ； t r a n s a c t i o n = d b t r a n s a c t i o n m a n a g e r s t a r t t r 粕s a c t i o n ( ) ； u s i n g ( 仃，使用事务处理 第二章g i s 在中压配电网络规划中的应用 t r c o m m i t ( ) ； 提交事务处理 2 3 2 信息提取流程图 在分析了矢量地图信息提取主要方法的基础上，给出信息提取的流程 图： 图2 4 矢量地图信息提取流程图 其中，判断点是否在闭合多段线内部的函数用到射线法：即从这个点向右水 平发出一条射线，如果交点个数是偶数，则点在多段线外，奇数则点在多段线内， 如图2 5 所示。 9 第二章g i s 在中压配电网络规划中的应用 图2 - 5 点与多边形关系示意图 由于规划原始地图中多边形都是凸多边形，而且点与多边形的关系只是简单 的在多边形内与在多边形外，因此不需要考虑诸如点在多边形一条边上等特殊情 况。 具体流程图如下： 图2 - 6 点与多段线关系流程图 l o 第二章g i s 在中压配电网络规划中的应用 2 3 3 提取结果 通过上述提取过程，形成负荷信息表和小区顶点信息表，现截取两张表的部 分内容如下表2 1 ，2 2 所示。 表2 1负荷表 如功l i j 3 如x均 b 艇 b 2 1 2 7 7 2 7 1 1 2 7 1 5 8 4 1 2 7 4 0 1 8 1 2 6 9 5 l 1 2 7 2 0 3 3 1 2 7 5 4 1 4 1 2 t 1 1 3 9 2 9 5 0 7 99 2 9 5 3 2 7 6 2 9 5 2 2 3 8 2 9 4 8 1 6 了 2 9 4 7 0 8 2 9 4 5 8 1 7 2 9 4 3 2 9 5 2 2 6 30 6 5 1 0 6 6 4 9 9 2 9 3 3 1 1 5 1 5 2 9 4 5 8 4 4 0 96 1 9 3 6 0 9 9 9 2 2 了6 4 2 2 9 6 4 0 注：l o a d i d 是负荷的唯一标识； l o a j ：) _ x 表示负荷位置的x 坐标； l o a d _ y 表示负荷位置的y 坐标； l o a d v a l u e 表示负荷量； l o a d n e a d 王i 与l o a d n e a r 2 表示与该负荷相邻的小区的负荷编号。 表2 2 小区顶点表 p o i n ti d f o i 耵xp o i n ty 圆 1 2 7 8 1 5 6 4 2 6 5 3 3 3 32 9 4 8 4 8 ，2 4 4 6 9 2 1 5 1 1 0 21 2 7 9 3 6 6 9 11 6 2 2 9 52 9 5 1 8 2 8 2 1 8 3 11 6 4 1 0 3 1 2 7 6 7 3 0 2 6 1 6 5 9 62 9 5 3 1 4 6 5 8 9 5 8 8 1 5 1 0 41 2 7 5 3 1 1 8 5 3 3 4 0 8 92 9 4 9 7 0 4 4 3 4 1 0 2 5 9 2 0 11 2 7 1 4 9 2 5 3 4 11 1 8 22 9 5 11 9 2 8 0 9 2 6 6 2 0 2 1 2 7 0 1 9 6 7 8 1 2 2 6 7 12 9 5 1 6 6 4 3 4 3 0 1 5 3 8 2 0 31 2 7 1 6 4 0 9 8 4 9 5 3 3 92 9 5 5 2 4 7 9 9 6 7 5 5 8 1 2 0 41 2 7 2 8 2 7 3 1 4 9 9 9 42 9 5 4 7 9 5 9 t 7 8 7 8 1 注：p o i n ti d 与l o a di d 对应； p o i n t _ x 表示小区顶点的x 坐标； p o i n t y 表示小区顶点的y 坐标。 2 4 地理信息知识库的形成 2 4 1 原始数据整理 在得到地理信息的原始数据表后，我们需要对原始数据进行相应的整理、提 炼，形成既准确表达各要素拓扑关系，又便于调用、查询与更新的地理信息知识 库。 第二章g i s 在中压配电网络规划中的应用 例如，原始数据表记录了各小区的顶点信息及与之相邻小区的小区编号，这 些信息并不能直接为我们的沿街铺设线路所使用，其关键是要从中提炼出所有街 道以及街道交叉点的信息。 对照地理信息原始图可知：每个小区都用一个多边形图形表示：每两个 相邻多边形的相邻边组成一段街道，而没有相邻边的那几条边则自成一段街道这 一特点，如图2 7 所示，运用图形学【4 】知识即可提取出能够直接为程序所使用的 街道信息。具体实现如下： 图2 7 小区关系示意图 相邻边组 成一段街 * 嬗 相邻情况的 成一段街道 ( 1 ) 街道交叉点的提取。 原始数据中存储着各小区的顶点信息，以i d 号来区分究竟是哪个小区的哪 个顶点。以表2 2 的“p o i n ti d ”列说明i d 号的编码规则： 百位以上( 含百位) 数字为小区编号，若相同表示几个顶点同属一个 小区，如表2 2 的第一至第四行均为“l ”，说明他们均是编号为“1 的小区的顶点；若不同，则表示各顶点分属不同的小区。 i d 号的个位和十位数字表示小区顶点的顺次标号，相同小区标号唯 一，不同小区间则可重复。 根据这一编号规则，计算不同小区的顶点的距离，距离很近的顶点( 如图 2 7 中圆圈所示) 合并成一个点，作为街道的交叉点；未找到小于所设阈值距离 的点，表明其为区域外边界的转角( 图2 7 小三角形内所示点) ，同样作为街道 交叉点，这样遍历所有的点，将不同小区间的顶点计算距离并比较，提取出街道 交叉点来。 、 1 2 第二章g i s 在中压配电网络规划中的应用 ( 2 ) 街道信息的提取。 小区边界( 多边形的各边) 或自成段街道，或与相邻小区某边界共同组成 一段街道，应当视情况分别提取。 如图2 - 8 所示，标号为的小区共有四条边界，与标号为的小区属相邻小 区。红色加粗的边为相邻边，这两条边共同组成一段街道；其它三边无相邻边， 它们各自自成一段街道。 提取由相邻边组成的街道时，首先要识别相邻边，其依据“相邻边的斜率相 同或相差不大且距离符合街区宽度”。如图2 8 中，红色边斜率相差不大，而红 色边与蓝色边斜率差别较大；同为红色边，两条粗边距离较小，粗边与细边距离 较大。识别相邻边的具体操作如下： 表2 2 记录了相邻小区的编号，已知的还有小区的各个顶点顺次的坐 标( 顺次说明某一顶点只与其编号相邻的顶点组成边界作为小区边 界) ，遍历小区顶点； 根据公式( 2 一1 ) 求各边的斜率，比较斜率，差值小于某一阈值的可 视为平行边： 求平行边距离，距离在某一设定范围内的，即为相邻边。 七：兰二兰 y i y 2 其中：( z 。，y ，) ，( x 2 ，y 2 ) 为两点坐标； k 表示斜率值。 图2 - 8 小区边界位置关系示意图 ( 2 1 ) 提取出街道后，需将街道的始末结点与街道交叉点对应。这只需计算街道的 结点与所有街道交叉点的距离取最小即可。 第二章g i s 在中压配电网络规划中的应用 2 4 2 知识库建立 经过上述数据处理过程，即可得到反映街道信息以及负荷点、街道交叉点与 街道拓扑关系的地理信息知识库表。 在s q ls e r v e r 2 0 0 0 数据库中建立知识库表如表2 3 ，2 - 4 ，2 - 5 所示。 表2 4 街道 注：r o u t ei d 表示街道的编号： 一 s t a r tn o d e 表示该街道的起始结点； e n dn o d e 表示该街道的终止结点： ， l o a d1 与l o a d2 分别表示街道两侧的负荷编号； 表2 3 街道交叉点 |404023 4 0 2 7 7 3 8 24 0 4 0 8 54 0 2 6 8 7 0 34 0 4 0 4 64 0 2 6 0 4 9 44 0 4 0 9 94 0 2 5 4 1 9 5 4 0 3 5 2 34 0 2 5 4 0 4 64 0 3 5 3 94 0 2 6 1 4 8 7 4 0 3 5 0 24 0 2 6 4 3 5 84 0 3 5 3 34 0 2 6 8 1 9 注：n o a d i d 表示结点( 街道交叉点) 的编号； c o o d m a t ex 与c o o d i n a t e - y 分别表示结点( 街道交叉点) 的x 坐标与y 坐标； i j 9 _ d 表2 5 负荷 lc o o d i n k t eylw i g f t 4 0 3 8 0 6 7 4 0 3 1 5 7 5 8 4 0 2 0 4 2 5 9 4 0 3 3 5 28 5 4 0 2 2 9 9 2 3 3 4 0 2 0 3 1 8 6 4 0 2 5 1 74 6 4 0 2 9 7 4 3 6 注：l o a di d 表示负荷的编号； 4 0 3 0 1 0 3 4 0 2 5 7 8 3 1 4 0 2 6 2 6 3 7 4 0 2 6 3 3 4 4 0 2 6 3 2 5 2 4 0 2 6 5 6 0 3 4 0 2 6 2 9 8 8 4 0 2 7 6 0 4 3 7 5 5 2 4 2 5 9 9 1 9 2 9 1 9 9 5 0 1 1 1 0 5 8 t 1 8 1 3 0 1 7 2 8 9 5 5 8 7 3 1 9 2 9 0 9 2 1 9 0 3 4 5 s 0 5 0 5 0 5 0 5 0 s 0 s 0 s 0 第二章g i s 在中压配电网络规划中的应用 c o o d i n a t e x 与c o o d i n a t ey 分别表示负荷点的x 坐标与y 坐标； w i g h t 表示负荷量值； b e g 表示负责给该负荷点供电的变电站编号。 2 5 面向对象的程序设计 当提取并整理得到地理信息知识库以后，需要通过合理的设计使得开发程序 的数据结构与数据库中知识相对应。 面向对象的程序设计运用对象、类、封装、继承、多态和消息等概念来构造、 测试、重构软件口5 1 。它以认识论为基础，用对象来理解和分析问题空间，并设计 和开发出由对象构成的软件系统。在处理数据方面，面向对象思想把问题的数据 用归类的思想分析清楚，然后针对功能做责任分配。这种模式有诸多的优点：符 合人们通常的思维方式；从分析到设计再到编码采用一致的模型表示，具有高度 连续性；软件重用性好。 根据这种思想，程序设计中定义三类对象与数据库中三个表内容相对应，分 别如下： c l a s sc p i o n t i m pi d ；结点的唯一标识 d o u b l e p x ；结点的横坐标 d o u b l e 吖； 结点的纵坐标 ； c l a s sc l o a d i n tl j d ； 负荷的唯一标识 i i l tl _ b e l ； 负荷所属变电站的标号 d o u b l el _ w i g h t ； 负荷预测值 ) ； c l a s sc r o u t e i n t r i d ；街道的唯一标识 c p i o n trs t a r ； 街道的起始结点 c p i o n tr e n d ； 街道的终止结点 c l o a dr e l a l o a d l ； 街道一侧的负荷编号 第二章g i s 在中压配电网络规划中的应用 c l o a dr e l a l o a d 2 ； d o u b l er l e n g t h ； 街道另一侧的负荷编号 街道长度 1 6 第三章基本蚁群算法与沿街最短路径 第三章基本蚁群算法与沿街最短路径 为了得到初步的辐射型网络，需要找到从变电站站点出发，到所有负荷点的 点到点沿街最短路径，如图3 1 所示。 图3 1 变电站点到负荷点最短路径示意图 蚁群算法作为一种能够充分满足沿实际街道铺设网线的特殊性的启发式智 能算法，成为本文寻找沿街最短路径问题的研究方法。 3 1 基本蚁群算法的原理 蚁群算法是一种由于受自然界生物的行为启发而产生的“自然”算法。它是 从对蚁群行为的研究中产生的。正如m d o r i g o 等人在关于蚁群算法的第1 篇文 章中指出的：蚁群中的蚂蚁以“外激素”为媒介的间接的异步的联系方式是蚁群 算法的最大的特点陬2 7 1 。蚂蚁在行动( 寻找食物或者寻找回巢的路径) 中，会 在它们经过的地方留下一些化学物质，我们称之为“外激素”。这些物质能被同 第三章基率蚁群算法与沿街最短路径 一蚁群中后来的蚂蚁感受到并作为一种信号影响后到者的行动( 具体表现在后 到的蚂蚁选择有这些物质的路径的可能性比选择没有这些物质的路径的可能性 大得多) 而后4 者留下的外激素会对原有的外激素进行加强，并如此循环下去。 这样，经过蚂蚁越多的路径，在后到蚂蚁的选择中被选中的可能性就越大( 冈为 残留的外激素浓度较大的缘故) 。由于在定的时间内，越短的路径会被越多的 蚂蚁访问，因而积累的外激素也就越多在下一个时间内被其他的蚂蚁选中的可 能性也就越大。这个过程会一直持续到所有的蚂蚁都走最短的那一条路径为止。 如图3 - 2 所示”o 2 s 3 0 j 。 b 1 圈3 - 2 蚂蚁的路径选择示意罔 圈3 - 2 中有一条蚂蚁经过的路径，我们假设a 点是食物，而e 点是蚂蚁的巢 穴，如图3 - 2a ) 所示。在菜个时刻忽然有一个障碍物出现在蚂蚁经过的路径中， 原有的路径被切断，从a 点到e 点的蚂蚁就必须在b 点决定应该往c 点方向迹是 往h 点方向走。而从e 点到a 点的蚂蚁也必须在d 点决定选择哪条路径。这种决 定会受到各条路径上以往蚂蚁留下的外激素浓度( 即残留信息浓度) 的影响。如 果向h 点方向的路径上的外激素浓度比较大那么向h 点方向的路径被蚂蚁选中 的可能性也就比较大一些。但是对障碍出现后第一个到达b 点或d 点的蚂蚁而言， 因为没有外激素的影响，所以它们选择向c 点或者向h 点方向的可能性是一样的。 若以从a 点到e 点的蚂蚁为例进行说明，对于从e 点到a 点的蚂蚁而言过程基本 是一样的。由于路径b h d 比路径b c d 要短，因此选择b h d 路径的第只蚂蚁要比 选择b c d 的第一只蚂蚁早到达d 点。此时从d 点向b 点看，指向路径d h b 的外 激素浓度要比指向路径d c b 的外激素浓度大。因此从下一时刻开始。从e 点经d 。m孙暑!m啦”卅淞。o 第三章基本蚁群算法与沿街最短路径 点达到a 点的蚂蚁选择d h b 路径比选择d c b 路径的可能性要大得多。从而使路径 b h d 或( d h b ) 上外激素浓度与路径b e d 或( d c b ) 上外激素浓度的差变大。而外 激素浓度差变大的结果是选择路径b h d ( 或d h b ) 路径的蚂蚁进一步增加，这又 导致外激素浓度差进一步加大。 在自然界中，蚁群的这种寻找路径的过程表现为一种正反馈的过程，与人工 蚁群的寻优算法极为一致。如我们把只具备了简单功能的工作单元视为“蚂蚁”， 那么上述寻找路径的过程可以用于解释人工蚁群的寻优过程。 由以上分析可知，人工蚁群和自然界蚁群的相似之处在于，两者优先选择的 都是含“外激素”浓度较大的路径；在这两种情况下，较短的路径上都能聚集比 较多的外激素；两者的工作单元( 蚂蚁) 都是通过在其所经过的路径上留下一定 信息的方法进行间接的信息传递。 而人工蚁群和自然界蚁群的区别在于，人工蚁群具有一定的记忆能力。它能 够记忆己经访问过的结点；另外，人工蚁群在选择下一条路径的时候并不是完全 盲目的，而是按一定的算法规律有意识地寻找最短路径。 3 2 蚁群算法的实现 蚁群算法最早成功地应用于解决著名的旅行商问题( t s p ) ，因此，借助经 典的对称t s p 问题进行说明【3 1 】。t s p 问题可描述为：给定刀个城市，找一条穿 过各个城市一次且仅一次，最后回到起点的最短路径。设蚁群中蚂蚁的数量为m ； d u ( f ，j = 1 , 2 ，疗) 表示城市i ，之间的距离：b i ( f ) 表示时刻f 位于城市i 上的蚂蚁 数，则有聊= 6 ，( f ) ；q 雕) 表示f 时刻城市i ，j 连线上的信息素浓度。初始时刻， 百 。 各条路径上的信息量相等，设f ，( 0 ) = c ( c 为常数) 。蚂蚁k ( k = 1 , 2 ，所) 在运动过 程中，根据各条路径上的信息量决定转移方向。在t 时刻，蚂蚁七由城市i 转移到 城市，的概率p ! ( f ) 为： p ；( f ) = ( ，仨t a b u 女) o t h e r w i s