（模式识别与智能系统专业论文）电网图智能布线系统研究与实践.pdf

中文摘要 为实现借助电网图管理和维护电网数据库，并由电网数据库自动生成 电网图，建立有面向对象的电网知识库系统。本文为面向对象的电网知识 库的一部分。 在深入研究人工智能搜索方法和迷宫布线算法的基础上，本文把人工 智能搜索方法应用在迷宫布线算法中，解决了电网图自动生成中的布线效 率问题。另外对电网知识库系统的维护做了研究与实践。 1 讨论了在电网图布线中应用迷宫算法的可能性，提出应用人工智能 搜索方法来减少迷宫布线搜索空间。 2 应用产生式系统描述布线问题，采用二维数组作为系统全局数据库， 表示电网图的状态，构造了一个点的扩展( 搜索) 规则库。并从手工绘制 电网图时总结出的大量经验和走线规律，在布线过程中综合考虑深度优先 搜索策略、启发式搜索策略、局部最优策略、回溯策略的组合优化，解决 了布线效率问题。 3 研制了一种编辑电网图基本要素、承载和链接电网知识( 知识对象) 的图元编辑器，结合通用电气元件知识类的创立和组织，使系统用户亲自 维护电网知识库成为可能。 随着布线效率的提高，电网图知识库系统的由数据库自动生成电网图 功能的工程价值才得以真正体现。 图元编辑器作为用户需求和系统自我完善的重要桥梁，使电网知识库 系统对实际电网图特别是电气元件的变化和调整具有很强的适应性，由此， 进一步提升了该系统的工程使用价值。 关键词：电网图迷宫布线智能搜索方法产生式系统图元编辑器 a b s t r a c t t of u l f i l lt h et a s ko ft h em a n a g e m e n ta n dm a i n t e n a n c eo fp o w e rn e t w o r k d a t a b a s ew i t ht h ea i do f p o w e r n e t w o r k g r a p h ，t h er e v e r s ep o w e rn e t w o r kg r a p h a u t o g e n e r a t i o n f r o m p o w e r n e t w o r kd a t a b a s e ，a o b j e c t o r i e n t e dp o w e r n e t w o r kk n o w l e d g eb a s es y s t e mi sc o n s t r u c t e d t h i sp a p e ri so n ep a r to ft h i s s y s t e m t h i sp a p e ra p p l i e st h ea is e a r c hm e t h o di nt h em a z e r o u t i n gt oi m p r o v e t h e e f f i c i e n c yo f t h ea u t o m a t i cr o u t i n go fp o w e rn e t w o r kg r a p h s o m er e s e a r c h a n d p r a c t i c e h a v e b e e nd o n e f i r s t ，t h i sp a p e rd i s c u s s e st h ef e a s i b i l i t yo fa p p l y i n gm a z er o u t i n gt ot h e a u t o m a t i cr o u t i n go fp o w e rn e t w o r kg r a p h m e a n w h i l e ，t h ep r o j e c to f u s i n ga i s e a r c hm e t h o dt or e d u c et h es e a r c h i n gs p a c ei sp u tf o r w a r d s e c o n d ，e m p l o y i n gp r o d u c t i o ns y s t e mt o d e s c r i b e r o u t i n gp r o b l e ma n d a d o p t i n g2 一d i m e n s i o na r r a ya st h eg l o b ed a t a b a s et oe x p r e s st h es t a t eo ft h e p o w e rn e t w o r k g r a p h ，w ec o n s t r u c tar u l e b a s et oe x p a n dap o i n t a c c o r d i n gt o t h e e x p e r i e n c e s a n dr u l e sd r a w nf r o mt h em a n u a l d r a w i n g ，a n dt a k i n gt h e c o m b i n a t i o na n d o p t i m i z a t i o n o ft h em e t h o d si n t o a c c o u n t s ，w h i c h a r e d e p t h - f i r s t s e a r c h s t r a t e g i e s ，h e u r i s t i c a l l y s e a r c h s t r a t e g i e s ，i r r e v o c a b l e s t r a t e g i e sa n db a c k p a c k i n gs t r a t e g i e s ，w em a k e t h er o u t i n gm o r e e f f i c i e n t l y f i n a l l y ，ag r a p h e l e m e n t e d i t o r ( g e e ) ，w h i c he n c a p s u l a t e sp o w e rn e t w o r k k n o w l e d g eo b j e c t ，i sd e v e l o p e dt oe d i tb a s i ce l e m e n to fp o w e r n e t w o r kg r a p h w i t ht h ec o n s t r u c t i o na n d o r g a n i z a t i o no fg e n e r a le l e c t r i cc o m p o n e n tk n o w l e d g e c l a s s ，g e ee n a b l e ss y s t e m u s e rm a i n t a i np o w e rn e t w o r kk n o w l e d g eb a s e h i m s e l f w i t ht h ei m p r o v e m e n to fr o u t i n ge f f i c i e n c y , t h e p r o j e c tv a l u e s o ft h i s s y s t e mc a nb ea c h i e v e da c t u a l l y b e s i d e s ，t h ei m p l e m e n t a t i o no fg e e ，w h i c h s e r v e sa sam a i n c o n n e c t i o nb e t w e e nu s e r r e q u i r e m e n t a n d s y s t e m s e l f - a d a p t a t i o n ，s t r e n g t h e n st h es y s t e ma d a p t a t i o nt o t h er e a lp o w e rn e t w o r k ， e s p e c i a l l y t h ea l t e r n a t i o na n dm o d i f i c a t i o no fe l e c t r i cc o m p o n e n t k e y w o r d ：p o w e rn e t w o r k g r a p h m a z e r o u t i n gp r o d u c t i o ns y s t e m g r a p h e l e m e n te d i t o r 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取 得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得丞洼盍堂或其他教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡 献均己在论文中作了明确的说明并表示了谢意。 学位论文作者签名司委剁务 签字日期： 埘年月夕日 学位论文版权使用授权书 本学位论文作者完全了解云洼太坐有关保留、使用学位论文的规 定。特授权丞洼盘堂可以将学位论文的全部或部分内容编入有关数据库进 行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。 同意学校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 翩签名：卫商寸机孑 签字日期：夕阳簪 1 月夕日 签字日期：乃。；年月，o 日 第一章绪论 1 1 课题背景与任务 1 1 1 课题背景 第一章绪论 随着我国经济建设的快速发展，人民生活水平的不断提高，对电力供应 的要求持续增加，我国的电力系统建设也不断发展，电网规模不断扩大，电 网上的各种电气设备越来越多。各级电力部门为了管理电网上的各种电气设 备纷纷建立了电网设备数据库。并以此为基础开发了大量的仿真和计算程序。 显然电网设备数据库为电网设备的管理、维护及基于其上的仿真和计算程序 提供了准确的数据，在电力系统基础信息建设中发挥着重要的作用。目前， 上述数据库仅配有传统的记录方式操作界面，这种操作界面不能将电力系统 的连接关系直观的表示出来，为数据查询与维护带来不便。为此华中电力公 司调度局与天津大学合作研制了“电力系统保护与调度计算数据库图形管理 系统”，该系统具有下述两种功能。 ( 1 ) 该系统在不影响原有数据库系统的前提下，通过电网连接图( 电网 厂站内部接线图，下同) 的形式来查询和维护电气设备的各种参数( 从图到 库) 。 ( 2 ) 按照选定范围，根据数据库信息自动生成电网连接图，即将分散在 数据库各表中的结构类数据提取并集结起来，以规范的图形格式将电网图再 现出来( 从库到图) 。 分析上述两项需求，把关系型数据库中记录的内容视为事实型知识，构 建一系列规则反映数据与图形的各种关系，再将由库到图的自动过程交给推 理机，发现这是一个典型的知识库系统构架。近年来面向对象的思想和技术 以其明显的优势影响着计算机科学与应用的每个领域，人们开始关注面向对 象的知识库系统的研究与应用。一般来讲，面向对象的知识库系统将表征静 态属性的知识和反映动态智能行为的知识处理方法封装成知识对象，形成知 识实体：具有相同结构、属性和功能的知识对象形成知识类，借助类的继承 和组合构成整个知识库系统的层次网络模型。因此，研究并开发了一个面向 对象电网知识库系统，该系统具有从图到库和从库到图的双向功能。 面向对象电网知识库系统的框架如图卜1 所示。 第一章绪论 图i - i 电网知识库系统框架 1 、电气元件知识类库的构建 首先，根据电网图的构成特点定义广义电气元件，其广义性在于电气元 件不单指电网中各种具体设备，还包括所有的母线和连线，因此电网知识类 库亦即电气元件知识类库，其中包括用于反映各种电气设备的设备知识类和 用于反映电网图结构的连线知识类，鉴于每条母线和连线都具有电路节点属 性，连线知识类又称为节点类；设备类又根据设备的外部接线数量分为单端 设备、双端设备和多端设备，通过对设备类的继承得到单节点设备类、两节 点设备类和多节点设备类；每一个具体的设备类分别从三个上层类中派生而 出。电气元件知识类库的层次关系如图卜2 所示。 利用面向对象程序设计方法和m i c r o s o f t 的m f c ( m i c r o s o f tf u n d a m e n t a l c l a s s ) 基本类库技术可以方便高效地完成面向对象知识库中知识类的构建， 鉴于m f c 类库中的基础类c o b j e c t 包含了类的消息处理机制等所有类都应具 有的属性及方法，本系统将其作为公共父类，通过继承产生出图卜2 中的各 知识子类。另外，图中虚线框表示虚类，虚类不产生对象；图形类是显示电 网图时为每一个电气元件生成的与之相对应的设备图形对象。 第一章绪论 图1 - 2 电气元件知识类库的层次关系 下面以刀闸为例简单说明上述类之间的继承与派生关系。由图卜2 可知， 刀闸类从两节点设备类继承而来，两节点设备类又从设备类继承得到，实现 方法如下。 设备类： c l a s se l e m e n t ：p u b l i cc o b j e c t 设备类 属牲 e l e m e n t g r a p h * p g r a p h ：设备图形对象指针 c s t r i n gm a i n k e y ：设备主键 c p o i n tp o s i t i o n ：设备在图中的位置 志法 ) 两节点设备类： c l a s se l e m e n t t w o j o i n t 属性 j o i n t * u p j o i n t ： p u b l i ce l e m e n t 两节点设备类 上节点对象指针 第一章绪论 j o i n t * d o w n _ j o i n t ：下节点对象指针 f 壳法 】 刀闸类： c l a s ss w i t c h ：p u b l i ce 1 e m e n t t w o j o i n t 刀闸类 ( 属性 c h a rt y p e ；刀闸类型 | 赢法 2 电气元件知识对象的封装 面向对象知识库系统的基本工作单元是知识对象，它所包含的事实型知 识及一系列处理方法，通过两种途径获得。 ( 1 ) 事实型知识的链接及载入 电力系统通用关系数据库中记载着几乎全部的关于电网的事实型知识， 如电网规模( 母线、连线、设备) 、每个电气设备的技术参数和运行参数等， 所缺少的是服务于数据库图形界面的图形事实知识。为此，首先设计并绘制 电网设备图形符号并形成图元文件，然后补充图元样式表以存储所有的图形 事实知识，如图元尺寸、名称、出线点等。我们把这样的数据库作为放置在 知识库系统中事实型知识的载体，是知识库系统的事实知识子库。 在生成知识对象时，为了减少知识库中知识的冗余，不再把事实知识库 中全部内容分类封装给对象，而仅载入数据库相关纪录的主键值，借此找到 对象的事实知识。 ( 2 ) 处理方法的导入 电气元件知识类库中含有知识库系统需要的全部处理知识的规则以及对 象内部的推理过程，这些将作为知识处理方法借助系统的对象生成和封装模 块的工作分类导入知识对象。 至此，一个面向对象的电网知识库由电气元件知识类库、事实库以及系 统运行时生成的全部电气元件知识对象共同组建成功。 4 第一章绪论 3 电网知识库系统双向功能的实现 ( 1 ) 知识的维护与管理 如前言所述，建立面向对象的电网知识库的直接目的是建立一种由电网 图直接管理和维护电网数据库的途径，即所谓从图到库的功能。而电网数据 库已被当作电网知识库中的事实知识子库，对它的维护和管理本应属知识库 系统的工作。为此我们专门配置了一个电网图编辑平台，平台上任何电网母 线或设备的拽入都将伴随相关知识对象的产生，若这一知识对象与关系数据 库某条纪录链接成功，则利用a d o 接口导入原有记录供用户编辑修改：若链 接不成功，则系统提供一个待填入各项字段数据的窗口由用户完成新记录的 添加；记录的删除则通过删除已生成的知识对象的显示图元来完成：而对数 据库数据的查询及定位就是对所有知识对象显示图元的查询与定位。简言之， 电网图图形界面上对知识对象显示图元的任何操作( 移动、缩放除外) 都可 引发对数据库的操作。 ( 2 ) 知识的推理及应用 解决电网图自动生成问题是建立面向对象电网知识库的另一重要任务， 也即所谓从库自动生成图的功能。为此，我们在系统中加入基于规则的知识 自动推理机制，以实现从数据到图形的飞跃。由库到图的自动生成过程需要 两个步骤，第一步是自动布局，主要工作为划分作图平面和设备定位。划分 作图平面就是把整个计算机作图平面按照规定单位长度划分为若干个栅格， 其意义在于保证作图规范的前提下尽量缩小问题描述空间：设备定位即确定 厂站中的所有电气设备在作图平面上的位置。第二步是在图中各设备分布位 置己知的前提下，从出发点出发，沿水平或垂直方向，绕过其它元件，找到 到达目的点的一条线路，即自动布线。布线算法为点光源法，具体做法如下。 假想整个平面是一片黑暗地区，出发点s 是一个光源，从该光源发出的 光水平或垂直交替发射，遇到障碍后停止传播。如图卜3 所示，从光源点s 亮度值为1：亮度值为2：亮度值为3 图l - 3 点光源布线算法 第一章绪论 出发，将向上方向的光线经过点的亮度置为1 ( 图中最粗线) ，再将亮度值为 1 的个点视为次级光源，按照同样的方法向外发出水平光线，并将光线经过点 的亮度值置为2 ；以此类推，直到找到目的点e 为止。亮度标定之后，只需按 照亮度值的指示，从目的点回溯到出发点便完成了自动布线。 1 1 2 任务的提出 经过系统实际运行，发现电网知识库系统中有两点急需解决的问题。 ( 1 ) 在能够合理布局的情况下，图卜3 所示的布线算法效率较低，所用 时间较长，无法满足大规模电网图自动生成的实时性和快速性要求，无法充 分体现本系统的主要工程价值，即由数据库自动生成电网图，所以需要设计 问题对策、研究新的算法，以提高布线效率。经查阅国内外文献发现，关于 电网厂站图自动布线的研究尚未出现，而大规模集成电路布线从6 0 年代提出 到现在日益发展成熟，电网厂站图是各种电气元件相互连接构成的线网，所 以可以借助大规模集成电路中的面向线网布线的基本思想，以实现高效自动 布线算法。本文将在下一节介绍面向线网布线的发展研究现状。 ( 2 ) 知识库系统维护中缺乏对知识类库维护部分，即用户无法对知识类 库进行修改、增加和删除等操作，当知识类库需要改变时，由系统开发人员 来完成，这将降低系统的通用性，增大开发成本。 1 2 面向线网布线综述 总体来看，面向线网布线主要有迷宫布线算法和线探索法两种方法，下 面分别介绍其提出、发展和研究现状。 1 2 1 迷宫布线算法 l e e 口j 于1 9 6 1 年提出了一个两端线网的布线算法。称为李氏算法，该算法 后来被广泛应用。李氏算法实际上是图论中最短路径算法在布线设计中的一 种应用。其算法思想也可描述为对波传播过程的模拟。自李氏算法提出以后， 由许多对该算法的改进，包括提高其速度和减小计算空间。李氏算法及其改 进算法形成了一组布线算法，统称为迷宫算法( i t l a z e r o u t i n ga l g o r i t h m s ) 。 迷宫算法用来寻找连接两个待连接线网端点的一条路经，一个端点称为 源( 出发点) ，另一个称为目标。对于标准单元设计模式，总是把平面表示成 一个网格组成的模型。布线区域表示成由实心和空心顶点构成的定点图，其 中的实心顶点表示布线障碍，空心顶点表示可布区域。迷宫算法的目标就是 6 第一章绪论 在源点和目标点之间寻找一条由空心顶点连成的连通路径。 在寻找开始，从源点出发，一般由许多( 顶点) 路可以选择，不断从这 些顶点扩展直到有一条路径到达目标点为止。 1 基本的迷宫算法 李氏算法的主要思想比较直观简单。在一个网格状的平面上，先从源点 开始，同时向上下左右各扩展一格。如果源点标为“0 ”，那么扩展的点即为 “1 ”，当然这个点必须是空心的，即不被障碍物( 模块) 所占有。标“1 ”的 点在同样向四周扩展一格，标为“2 ”。如此进行下去直到所标点的格为要连 接的目标点为止或无法再进行扩展为止。在存在路径的情况下，李氏算法能 够找到。图1 - 4 所示为一条路经的寻找过程及结果。下面介绍李氏算法的布线 过程。 图l - 4 李氏算法所实现的两点线网布线 ( 1 ) 数据准备 首先，在存储器中建立一个二维数组g ( “j ) ，使作图平面网格映射为 该数组的一个元素。数组的维数分别表示了作图平面的长度和宽度，其下标 值为网格的坐标( 以线间距为单位) 。算法中定义了两个波前w f ( w a v e f r o n t ) ： 一个为当前波前w f l ，纪录当前波传播所达到的位置：另一个为上一个波前 w f 0 ，记录波本次扩展前波的波前位置。初始时，w f 0 和w f l 都为空集。数 组g ( i ，i ) 中未占用的元素值为0 。 ( 2 ) 扩展过程 扩展开始后，任意选取待连接的两个端点( 如a 和b ) 中的一个点为波 源点，并将其送入w f 0 ，同时在数组g ( i i ) 相应位置做起始点标志。另一 个点定义为目标点，并在g ( i ，i ) 相应位置做目标点标志。 当w f 0 非空时，顺次将其中的元素取出，并向邻接网格进行扩展，扩展 后的网格值为w f 0 元素网格值加l ( 令源点网格值为0 ) ，它也就表示了将扩 7 第一章绪论 展到的网格距波源点的最小曼哈顿距离。纪录该格值为v ，当其邻格不是障 碍或源格值大与v 是，将v 添入邻格，并将此邻格送入w f l 。当w f 0 中元 素处理完毕后，将w f l 元素全部送入w f 0 并将w f l 清零。 扩展时，若其中的一个邻格为目标点，则扩展过程结束，说明已找到一 条最短的连通路径。若尚未达到目标点而此时w f l 为空，则说明该线网布线 失败，不存在a 和b 的可行路径。 ( 3 ) 回找过程 如果扩展过程中达到了目标点，则开始回找处理，即确定布线路径。回 找时，可能存在多条连接a 和b 的路径，这些路径在理论上为等价的，但考 虑到布线质量及对今后布线的影响，实际处理时可遵循一定的原则：如使一 条路经的拐弯数量少，即在回找是尽量不改变当前的回找方向。 2 李氏算法的改进 李氏算法存在着两个弱点，一是需要较大的存储空间，二是采用广度优 先扩展策略，使得算法效率较低。纵观迷宫算法的发展，所有对李氏算法的 改进都是从这两方面着手进行的。 ( 1 ) 减小存储空间 a k e r s 4 】提出了一种减少存储空间的方法，任何网格值为k 的邻格的网格 值不是( k 1 ) 便是( k + 1 ) ，分别表示了该网格的“先行”和“后继”。从这 一点得到启发，如果网格的安排能够将它和它的邻格之间的“先行”、“后继” 关系描述清楚就可以了。因此，可以设计一个简单的添数序列，如1 、l 、2 、 2 、1 、1 ，按此顺序进行添数，就可方便的确定每一个网格与其邻接的“先行” 和“后继”的关系。使用这种添数策略，每个网格的信息只需两位就够了， 存储量大大降低。 ( 2 ) 减小搜索空问 s o u k u p 5 1 和r u b i n 6 1 把深度优先搜索策略引入到李氏算法中，其基本思想 是优先扩展朝向目标点的波前元素。 h a d l o c k 7 】于1 9 7 7 年提出了最小迂回法，其基本思想为使得扩展过程中背 离目标点方向上的节点个数最少。 对李氏算法的改进还有很多种 8 】【9 】【1 0 】【l l l 【1 2 】【1 3 】 1 4 】 1 5 】【1 6 1 1 17 1 ，不再一一赘述。 1 2 2 线探索法 迷宫算法的最大缺点是它要搜索较大的布图空间，所以要花费较长的时 间和较大的存储空间。人们开始考虑能否在搜索中避免大量网格空间的搜索 第一章绪论 而取代之以较简单的搜索方法。当然，人们想到的简单图形搜索方法就是直 线探索的方法。h i g h t o w e r 在1 9 6 9 年1 引，m i k a m i 和t a b u c h i 在1 9 6 8 年f 1 9 1 分 别提出了线探索( 1 i n e p r o b ea l g o r i g h m ) 的思想和算法。这种算法的基本思想 就是用线探索的方法减少存储空间和计算时间，因为探索用到的空间要比探 索用的网格所存储的空间少得多。 线探索法的基本算法描述如下：从源点即目标点产生两个直线表s l i s t 和 t l i s t ，产生的线不能穿越障碍物。如果s l i s t 中的直线与t t i _ s t 中的相交，那么探 索结束：否则，继续产生新的直线。这些直线要起源于s l i s t 和t l i s t 线上的“逸 出点”( e s c a p ep o i n t s ) 。新的s l i s t ( t l i s t ) 线要与原s l i s t ( t l i s t ) 相交。若探索 结束，从目标点回溯找到源点，从而形成一条通路。线的产生是在水平和垂 直方向交替进行的。 m i k a m i 和h i g h t o w e r 两个算法的主要区别在于逸出点的选择。m i k a m i 算 法中，线上的每一个点都是逸出点，可以产生与之垂直的新线，这相当于广 度优先搜索，它保证能找到一条存在的通路，但通路不一定是最短的。图1 5 就是一个用m i k a m i 算法布线的实例。 厍拜 ：i ： 盐 n ：i ： 篚 匝 e | 三 图l 一5m i k a m i - t a b u e h i 算法布线 在h i g h t o w e r 算法中，每根线只有一个逸出点，最简单的情况是搜索的线 与障碍物平行，那么逸出点就在障碍物尽头那边线的尾端，如图1 6 所示。 图i - 5h i g h t o w e r 算法布线 第一章绪论 线探索法中的直线要比迷宫探索中的网格数少得多，所以线探索法所需 存储空间要少得多。h i g h t o w e r 和m i k a m i 算法本质的不同在于，h i g h t o w e r 试图去探索尽量小的搜索空间，虽然搜索速度加快，但往往会因为没有探索 足够大的空间而找不到本该存在的路径。m i k a m i 算法则一定保证找到存在的 路径，虽然不能保证路径最短。 近年来，出现了一种图论框架的线探索、法【2 0 】1 2 l 】【2 2 l ，计算几何也给线探索 法的发展提供了良好的工具。 1 3 本文的工作 前述布线算法都出于集成电路布线设计的应用，而电网图和集成电路图 有很大区别，主要表现在如下两个方面。 ( 1 ) 图面划分 在不影响作图规范性的前提下，可以尽可能加大图面划分基本单位，以 使描述问题所需的存储空间大规模减少。 ( 2 ) 布线顺序 在集成电路布线中布线顺序非常重要，因为一条线路的布通可能导致下 一条线路的不能布通；而在电网图布线中，设备间连接线允许穿越，而相互 穿越的连接线并不预示着相关设备的电气连通。这就使两者在布线策略及布 线顺序上呈现很大的区别。 电网图作图平面栅格划分，类似于李氏算法的数据格式。本文采用氏算 法的基本思想，构造一个产生式系统解决电网图的快速自动布线问题； 另外，利用面向对象技术，通过通用电气元件知识类的创建和图元编辑 器的研制，解决面向对象电网知识库的维护问题。 1 0 第二章智能布线理论基础 第二章智能布线理论基础 1 1 人工智能问题求解方法简介 1 1 1 状态空间法 问题求解及搜索是人工智能的核心概念和技术耻3 】【2 4 1 。分析在人工智能研 究中运用的方法，会发现许多求解方法归类于试探搜索法，这些方法大都通 过在某个可能的解答空问中寻找解。 在状态空间问题求解中，问题的状态和规则是两个重要概念。问题状态 表示为问题求解中的每一步问题状况的数据结构，而规则表示把问题从一种 状态变换为另一种状态的手段。例如对于李氏算法布线来说，一个问题状态 就是布线圈面状态( 二维数组状态) 。由初始状态出发所能达到的状态空问是 由全部可能路径组成，这些路径可由点在图面上扩展而得到。规则能够把一 种状态变为另一状态，对于李氏布线算法来讲有4 个规则：向上扩展、向左 扩展、向右扩展和向下扩展。 李氏布线涉及这样一个搜索过程，首先将规则用于初始状态以产生新的 状态：然后再将规则用于这些新的状态，由此连续搜索下去，直到出现目标 状态。而问题的搜索方法有很多种，将在下一节介绍。 1 1 2 问题的归约 某些比较复杂的问题求解方法含有子问题的概念，应用问题归约方法去 分析原问题以产生一个子问题集合，这样，对浚子问题的某个具体子集的解 答就意味着是对原问题的一个解答。每个子问题可用任何一种可行的方法给 以解答。子问题可能用状态空间法求解，子问题本身有可能被分析并产生出 子问题的子问题。任何首先产生子问题然后又解决子问题的解答方法，叫做 问题归约法。 对于迷宫布线问题，对于一个线网的布线归约为端点到端点的布线，当 线网所有端点都连接后，则整个线网的布线随之完成。 1 2 搜索方法简介 状态空间求解过程伴随从初始状态到目标状态的搜索。当问题有解时， 采用不同的搜索方法，找到解的搜索空间范围是有区别的。搜索策略的主要 任务是确定如何选取规则的方式，通常有两种基本方式：一是不考虑给定问 第二章智能布线理论基础 题所具有的特定知识，系统根据事先确定好的某种固定排序，依次调用规则 或随机调用规则，这实际上是盲目搜索的方法，一般统称为无信息引导的搜 索策略，主要包括深度优先搜索和宽度优先搜索。再就是考虑问题领域可应 用的知识，动态的确定规则的排序，优先调用较合适的规则等，这就是通常 所说的启发式搜索策略或有信息引导的搜索策略。 迷宫布线的基本思想是布线转化为点的扩展，而点的扩展过程即为点的 搜索过程，可以应用搜索方法来优选点的扩展方向，从而减小搜索空间。 1 2 1 盲目搜索 盲目搜索又叫无信息搜索，主要包括两种方法。 ( 1 ) 广度优先搜索 该方法以接近起始状态的程度依次扩展，使搜索逐层进行，并在对下一 层的任一状态进行搜索之前，必须搜索完本层的所有状态。李氏布线算法所 用搜索策略即为广度优先搜索。 ( 2 ) 深度优先搜索 该方法首先扩展新产生的状态，并使搜索沿着状态空间某条单一的路径 从起始状态向下扩展；只有当搜索到达一个没有后裔的状态时，才考虑另一 条路径，r u b i n 算法中加入了深度优先搜索策略，减小了李氏算法的搜索空问， 提高了算法效率。 1 2 2 启发式搜索 要在盲目搜索中找到一个解，所需要扩展的状态数目可能很大。因为这 些状态的扩展次序完全随意，而且没有利用己解决问题的任何特征。因此， 除了那些最简单的问题之外，一般都要占用很多时间或空间( 或者两者均有) 。 这种结果是组合爆炸的一种表现形式。 有关具体问题领域的信息常常可以用来简化搜索。设问题的初始状态、 算符和目标状态的定义都是完全确定的，为更有效、快速地搜索问题的给定 空间。一般需要某些有关具体问题领域的特定信息，并称此种信息为启发信 息。利用启发信息的搜索方法叫做启发式搜索方法。启发信息按其用途可分 为下列3 种。 ( 1 ) 用于决定要扩展的下一个状态，以免象在广度优先或深度优先搜索 中盲目扩展状态； ( 2 ) 扩展一个状态的过程中，用于决定要生成哪一个或哪几个后继状态， 1 2 第二章智能布线理论基础 以免盲目的同时生成所有可能状态； ( 3 ) 用于决定应该从搜索树中抛弃或修剪哪些状态。 其中，第一种启发信息的状态空间搜索法，总是选择“最有希望”的状 态作为下一个被扩展的状态，这种搜索叫做有序搜索。 1 3 产生式系统 产生式系统( p r o d u c t i o ns y s t e m ) 是1 9 4 3 年p o s t 提出的一种计算形式 体系里所使用的术语，主要是使用类似于文法的规则，对符号串做替换运算。 到了6 0 年代产生式系统成为认知心理学研究人类心理活动中信息加工过程的 基础，并用它来建立人类认知的模型。到现在产生式系统已发展成为人工智 能系统中最典型最普遍的一种结构。采用产生式系统构造问题模型描述问题 的原因如下”： ( 1 ) 用产生式系统结构求解问题的过程和人类求解问题时的思维过程很 相象，因而可以用它来模拟人类求解问题时的思维过程且便于理解。 ( 2 ) 可以把产生式系统作为人工智能系统的基本模块看待，就好像是积 木世界中的积木块一样，便于整个人工智能系统的模块划分。 本章简单介绍产生式系统的组成，以此为基础介绍产生式系统的图搜索 策略，然后介绍产生式系统的控制策略。 1 产生式系统结构 产生式系统的基本要素是一个综合数据库( g l o b l ed a t a b a s e ) 、一组产 生式规则( s e to fr u l e s ) 和一个控制策略( c o n t r o ls y s t e m ) 。三要素之间 的关系如图2 - 1 所示。 图2 - l 产生式系统的主要组成 ( 1 ) 综合数据库 综合数据库是人工智能产生式系统所使用的主要数据结构，用来表述 问题状态或有关事实，包含着所求解问题的信息，其中有些部分可以是不 变的，有些部分则可能只与当前问题的解有关。人们可以根据实际的问题， 用适当的方法来构造综合数据库且填充必要的数据。值得注意的是，它不 第二章智能布线理论基础 同于软件工程中数据库的概念，计算机程序设计中常用的数据结构类型如 向量、集合、数组、符号串、树、表格乃至文件都可以选作为综合数据库 的数据载体。 应用产生式系统描述迷宫布线问题时，由于二维点阵数组表示整个作 图平面的状态，所以可以用二维数组来作为综合数据库。 ( 2 ) 产生式规则 产生式规则是一个以“如果满足这个条件，就应当采取某些操作”形式 表示的语句。般表述为： 条件 行动 或前提一 结论 可写成 i f t h e n 的形式。 产生式的i f ( 如果) 被称为条件、前项或产生式的左边。它反映应用这 条规则必须满足的条件；t h e n ( 那么) 部分被称为操作、结果、后项或产生 式的右边。在产生式系统的执行过程中。如果某条规则的条件满足了，那么， 这条规则就可以被应用，也就是说，系统的控制部分可以执行规则的操作部 分。产生式的两边可用谓词逻辑、符号和语言的形式，或者用较复杂的过程 语句来表示，这取决于所采用数据结构的类型。一条产生式规则满足了应用 的先决条件之后，就可对综合数据库进行操作，使其发生变化。如果综合数 据库代表当前状态，则应用规则后就使状态发生转换，生成出新状态。 迷宫布线问题点的扩展可以应用如下统一规则形式表示。 i f 点能够在某个方向( 上、下、左、右) 上扩展 t h e n 点扩展到该方向上的相邻点 ( 3 ) 控制策略 控制策略是规则的解释程序。它规定了如何选择一条可应用的规则对数 据库进行操作，即决定了问题求解过程的推理路线。当数据库满足条件时， 系统就应停止运行；同时系统应记住求解过程中应用过的规则序列，以便最 终能给出解的路径。 如何选择一条可应用的规则作用于当前的综合数据库、生成新的状态以 及记住选用的规则序列是构成控制策略的主要内容。对大多数的人工智能应 用问题来讲，控制策略中拥有的知识或信息并不足以仅靠几步算法，就能选 出最合适的规则来，因而人工智能产生式系统的运行通常表现出一种搜索过 程，在每一个循环中选一条规则使用，直至找到某一个规则序列能产生一个 1 4 第二章智能布线理论基础 满足结束条件的数据库为止。由此可见高效率的控制策略需要有关被求解问 题的足够知识，这样才能在搜索过程中减少盲目性，比较快地找到有效的求 解路径。 控制策略可划分为两大类：不可撤回策略和试探性方式。而试探性方式 又可分为回溯方式和图搜索方式。 不可撤回方式 这种方式是利用问题给出的局部知识决定如何选取规则，并应用所选规 则作用于当前综合数据库得到新状态。接着根据新状态继续选择规则，搜索 过程如此进行下去，不再考虑撤回用过的规则。搜索过程中如能有效利用局 部知识，即使使用了不甚理想的规则，也可以通过下一步规则更合适的选取 补偿前面的操作。可见，不可撤回方式般并不影响求到解结果，只是解序 列中可能多出一些不必要的规则。 回溯方式 在问题的求解过程中，有时会发现应用了一条不合适的规则，阻挠或拖 延达到目标的过程。在这种情况下，需要有这样的控制策略：先试一试某一 条规则，如果以后发现这条规则不合适，则允许退回去，另选一条规则来试。 回溯过程是一种可试探的方法，这时可按任意方式选取规则。从形式上 看不存在选择规则有用的知识，不过如果有好的选择规则的知识可用，就用 来引导规则选取，以减少盲目性、降低回溯次数( 甚至不回溯) ，以提高求解 效率。此外回溯机理的引入，可以避免陷入局部极大值的情况，使搜索工作 沿着存在目标的路径行进。 图搜索方式 ， 如果把问题求解过程用图或树的结构来描述，即图中的每一个节点代表 问题的状态，节点间的弧代表应用的规则，那么问题的求解空间就可由图来 描述。图搜索方式就是用某种策略选择应用规则，并把状态变化过程用图结 构记录下来，一直到得出解为止，也就是从图中搜索出含有解路径的子图来。 2 产生式系统的特征 最基本的产生式系统是条件驱动型( 或数据驱动型) 系统，即所谓向前 推理型系统，或称之为纯产生式系统。纯产生式系统出规则库、综合数据库 以及推理机构三要素构成。规则库及数据库都是平面式的构造，推理机构的 动作则是如前所述的单纯认识行动过程的循环。认识过程由与综合数据库有 关的规则的条件部分的模式匹配来进行，行动过程是由认识处理过程中选出 的规则的行动部分对于综合数据库的更新处理。也就是根据各认识一行动周期 的执行，系统将不断对综合数据库进行更新同时向目标状态移动，这就是推 第二章智能布线理论基础 理机构的动作过程。 纯产生式系统从其原理来看，具有以下特征： ( 1 ) 综合数据库是唯一的各系统部件相互作用的通道。在产生式系统中， 所有规则都可以对综合数据库进行存取操作，使规则借助综合数据库相互作 用。这种性质不仅使得推理机构具有单纯明确的结构，而且对于打算使用产 生式系统开发专家系统的用户也很容易理解。 ( 2 ) 规则表现形式的一致性。全部的规则都以i f t h e n ( 条件部分行 动部分) 的一致形式表示，而且用i f 与综合数据库进行模式匹配，用t h e n 对综合数据库进行更新，各自具有自己的功能，此性质也使得推理机构单纯 化并有利于用户理解。 ( 3 ) 具有高度模块化性质。所谓具有高度模块化性质，是指当把系统分 割成几个构成部分( 模块) 时，彼此之间的相互联系较少。因此，该类系统 更便于各构成部分的变更和扩张。在产生式系统中，规则仅对综合数据库起 作用，而规则之间是相互独立的，因此可以将规则看作模块。这就是说，由 于各规则之间不直接执行操作，使得产生式系统具有高度模块化性能。对规 则的定义、修正、追加等动作可以各自独立进行的性质，使得在开发产生式 系统初期，可以先构筑一个小型的系统库，然后再逐渐扩张( 一般都是采用 这种做法来开发专家系统的) ，使整个研究开发工作更有条理。 以上是产生式系统的特征。下面我们来总结一下它的优点： ( 1 ) 个别的规则容易理解和定义； ( 2 ) 便于进行规则的追加和变更： ( 3 ) 便于确认规则库修正的效果。 在产生式系统中，各条规则都是以极简单的形式表现出来，因而即使对 没有计算机知识的专家来讲也不易形成理解的障碍。这些从知识获取角度来 看是其最大的优点。另外，在系统试制的初期可以从小规模入手，然后一边 检验数据进行试验，一边不断的追加规则和修正规则库，使系统的规模逐步 扩张，在扩张的过程中同时完成规则库的修正。总之，产生式系统的模块化 性能好，修正效果的确定较为容易。 1 6 第三章自动布线问题的产生式系统描述 第三章自动布线问题的产生式系统描述 本章在上一章产生式系统理论的基础上，主要讨论应用产生式系统描述 电网图自动布线问题，介绍全局数据库和产生式规则的建立方法。 3 1 电网图图面的若干约定 图3 一l 是具有代表性的实际电网图图例，分析该图可知，电网图使用图 形符号来表示电网厂站中的实际电气元件、负载标识等，根据图形符号外部 连接特点，通常分为母线图形符号和非母线图形符号两种类型。母线图形符 号跨度较大且可在任意位置上引出与其它电气元件相连接的连线；非母线图 形符号如电气元件、负载标识等，此类图形符号近似呈矩形且只能在固定位 置引出连线。 图3 - i 典型电网图例 下面首先结合图3 一l 给出一些名词术语定义或说明。 ( 1 ) 图形元素 称电网图中规范的图形符号为图形元素。为了方便计算机作图，对于上 述非母线图形符号绘制在矩形框内，如图3 2 所示。 1 7 第三章自动布线问题的产生式系统描述 非母线图形元素在电网图中占据的空间范围 图3 - 2 非母线图形元素 ( 2 ) 出线点 图形元素可以向外引出连线的点称之为出线点。母线图形元素可以在任 意位置引出连线，而非母线图形元素只能在固定位置引出连线，如图3 3 所 示。 出线点 图3 - 3 非母线图形元素山线点 ( 3 ) 线路 图形元素间连接线称为线路。 3 1 1 平面栅格及栅格点 为了方便电网图自动生成，同时使生成的电网图在符合工程规范的同时减 小系统的存储空问，将电网图面划分成若干栅格以生成新的坐标体系。 首先将某个固定的像素数( 本系统中默认为5 个像素) 定义为一个单位 长度。”，以单位长度作为基本单位将作图图面进行划分，称划分后得到的栅 格为单元格，划分线的交叉点为栅格点也即新的坐标点，如图3 4 所示，图 中黑色矩形表示图形元素所占区域。 在取得栅格划分的作图平面上，电气元件、出线点、线路等图形要素在 第三章自动布线问题的产生式系统描述 尺寸和定位上受到如下约束： ( 1 ) 图形元素的图形长度、宽度尺寸必须是单位长度的整数倍： ( 2 )