（机械设计及理论专业论文）基于遗传算法的矩形件优化排样系统研究.pdf

的距离即可。 图3 5 排样图在显示器屏幕上的显示位置 3 3 与智能c a d 系统及智能切割系统的连接方式的确定 器屏幕 本文的任务是开发一套能用于工程实际应用的矩形件智能优化排样软件。 即：在用户给定矩形件数目及尺寸之后，能在指定的矩形件板材上产生经优化计 算后的排样图，并根据排样图自动生成各矩形件在其上的排列位置信息。 如前所述，优化排样系统只是整个系统里的一项中间子课题，需要从前面课 题丌发的系统中接收矩形件的参数，同时还要将本程序产生的各矩形件的排列信 息传送到下一个课题研究的系统中作为输入参数，所以本程序必须保证前后相 连。但由于各个项目开发是单独进行的，所以可能存在着各个项目之间采用的开 发工具及开发方式不尽相同，从而不利于接口的预留。为了最大限度的保证各系 统的独立开发，本文采用数据库连接的方式，即前面课题开发的系统生成数据之 后将这些数据保留在一个数据库中，本系统则直接从该数据库中调取数据，然后 本系统生成的各矩形件的位置信息也同样保存在一个数据库中，后面的课题开发 的系统也只需从数据库中直接调取数据即可。这样的连接方式无须考虑由于开发 工具不同而带来的麻烦，从而可以在保证各项予课题独立研究的基础上实现了前 后相连。 由于本文在各个子系统中采用数据库的连接的方式，所以在本系统开发过程 中，数据库的开发与连接是一个非常重要的内容。 3 3 1 数据库系统概述 数据库系统为我们提供了一种把与我们工作和生活紧密相关的信息集合在一 起的方法，它还提供了在某个集中的地方存储和维护这些信息的方法。数据库系 统主要由三大部分组成：数据库管理系统，其功能是专门负责组织和管理数据信 息的程序：数据库应用程序，其功能是使用户能够获取、显示和更新由数据库管 理系统存储的数据；数据库，是按定结构组织在起的相关数据的集合【2 ”。 数据库管理系统( d b m s ) 是用于描述、管理和维护数据库的程序系统，是 数据库系统的核心组成部分。它建立在操作系统的基础上，对数据库进行统一的 管理和控制。其主要功能有： 1 描述数据库：描述数据库的逻辑结构、存储结构、语义信息和保密要求。 2 管理数据库：控制整个数据库系统的运行，控制用户的并发性访问，检验 数据的安全、保密与完整性，执行数据检索、插入、删除、修改等操作。 3 维护数掘库：控制数据库初始数据的装入记录工作r 志，监视数据库性 能，修改更新数据库，重新组织数据库，恢复出现故障的数据库。 4 数据通信：组织数据的传输。 数据库管理系统和数据库可以和应用程序同时驻留在同一台计算机上并在同 一台计算机上运行，有些情况下两者甚至结合在同一个程序中，这种数据库管理 系统被称之为本地数据库如d 1 3 a s e 、f o x p r o 、p a r a d o x 、a c c e s s 等，以前使用的大 多数数据库系统都是用这种方法设计的。由于与数据库应用程序位于同一个系统 中，所以其运行操作速度快。但是随着数据库管理系统技术的发展，目前的大型 数据库系统都在向远程数据库服务器( s q l 服务器) 发展，如：o r a c l e 、 s y b a s e 、i n f o r m i x 、i n t e r b a s e 等。远程数据库服务器将数据库管理系统和数据库 应用程序分丌，客户端可以用结构化查询语言( s q l ) 来访问操作。远程数据库 服务器是为多个用户同时访问数据库而设计的，它比本地数据库能处理更多的数 据，从而大大提高了数据库系统的处理能力。 数据库管理系统主要有四种类型：文件管理系统、层次数据库系统、网状数 据库系统和关系数据库系统。其中关系数据库系统应用最为广泛，其特点是用二 维表来表示数据的结构。一个二维表就象一张表格，每个表中的每一列称为一个 字段，每个字段都有相应的描述信息，如数据类型、数据宽度等，一般一个表有 多列来表示数据的信息；每个表中的每一行称为一个记录，一个记录表示一条数 据，一般一个表有多个记录。 微软公司出品的a c c e s s 是一种使用广泛的关系型本地数据库【2 “，简单易 用，在本文的开发过程中所选用的正是这种数据库。 3 3 2c + + b u i l d e r 开发数据库 用c + + b u i l d e r 开发数据库时常用b d e 来进行数据库的连接。b d e 是b l a n d 公司提供的一个位于数据库应用程序和数据库之间的数掘库引擎，它通过不同的 驱动程序可以直接访问常见的本地数据库如：a c c e s s 、f o x p r o 、d b a s e 、p a r a d o x 和文本数掘库：通过b l a n d 公司提供的s q ll i n k s 驱动程序或微软公司提供的 o d b c 驱动程序，b d e 可以访问s q l 数据库服务器如：i n f o r m i x 、d b 2 、 o r a c l e 、s y u a s e 、s q ls e r v e 等。b d e 给要访问的本地或远程数据库起个名称，称 为数据库别名( d a t a b a s ea l i a s e s ) ，数据库应用程序仅通过此数据库的别名就可 以进行数据库的操作。图3 6 是使用b d e 的单层结构数据库应用程序模型。 数据库界 数据源 勰鞴 j 面构件 构件 件 b i ) e 表单 数据模块 图3 6 用b d e 的单层结构数据库应用程序模型 3 1 3 3 字段的定义及动态数据表的建立 对于本系统，输入的数据是矩形件的长、宽、数目。所以，我们建立的字段 如表1 ： 表1 ：矩形件字段定义 字段名 数据类型 中文含义索引字段 n o 臼动编号k 整型编号是 l e n g t h整型长度不是 w i d t h 整型宽度不是 、 n u m 整型数目 不是 对于本系统，输出的数据是矩形件的x 、y 坐标，建立的字段如表2 ： 表2 ：输出数据字段定义 字段名数据类型中文含义索 l 宇段 n o 自动编号长整型编号是 x 单精度型x 坐标不是 y 单精度型 y 坐标 不是 对于a c c e s s 数据库来说，一个数据库中可以有很多数据表，每个数据表保存 一次输入的矩形件参数或一次数据点输出的坐标。由于输入和输出的数据次数无 法事先确定，从而数据库中的表的数目也无法确定，如果事先建立太多的表浪费 了资源，而太少了又无法满足要求，所以解决这个问题的最好办法是采用动态建 立数据表的方法。 所谓动态建立数据表是指在程序运行的过程中根据具体的需要用户自己建立 数据表，在建立数据表时用户只需要输入数据表名即可。 在c + + b u i l d e r 中动态创建数据表只需要一条语句： t t a b l e + n e w t a b l e = n e wt t a b l e ( f o r m l ) , 这条语句在程序运行过程中创建了个隶属于窗体f o r m l 的表n e w t a b l e ，然 后通过操作n e w t a b l e ，就可以动态地添加数据表名、字段名、字段类型等等，调 用或输出数据等过程和操作固定数据表一样。 3 3 4 数据表的管理 当一个数据库中有了许多数据表之后，这些表的管理将是一个很重要的问 题。在数据表调用时我们可以直接输入数据表名，很显然，当数据表比较多的时 候，这些表名是难以一一记住的，所以我们必须打开数据库。然后在库中去搜寻 我们要使用的数据表，这样做的结果自然是降低了工作效率。 为了解决这个问题，本文采用了一种用文件记录数据表名的方法。首先，由 程序判断在磁盘的某个目录下是否存在一个有特别文件名的文本文件( 戗t ) ， 若没有，则在此目录下产生一个具有特别文件名的文本文件( 之所以要用一个特 别的文件名是为了防止在该目录下出现重名的现象) 。 建立这个文本文件之后，在每次保存数据的时候都自动将数据表表名保存在 这个文本文件中，当要调用数据表时先将该文本文件的内容调入到一个 c o m b o b o x 控件中，这样就可以在这个控件的下拉选项中直接选用所需要的数据 表a 如图3 7 所示，我们建立了一个文件名为i t e m l 的文本文件，在程序中调用 数据表时可以看n - 者的内容和排列顺序都是致的。 3 4 切缝宽度的计算 请选择要调用的表 图3 7 用文本文件管理数据表 板材的切割有多种工艺方法，如火焰切害u 、等离子切割、激光切割、线切割 等等。不同的切割方法会形成不同宽度的切缝，所以必须根据不同的切割设备来 确定切缝的宽度忙”。 在图3 8 中，设切缝的宽度为w i d t h ，实线表示的是各矩形件的轮廓线，虚线 表示的是切割时应走的路线。很显然，我们可以看到，只要w i d t h 不等于零，切 割的路线就会和矩形件的外轮廓线相隔一段距离f 2 8 1 ，这段距离的大小正好是 w i d t h 2 。由于最终的排样图是为切割服务的，所以在排样系统产生的排样图中的 矩形件并不是实线所示的原尺寸矩形件，而是图中虚线所示的由切割路径构成的 矩形件，也就是说，各矩形件必须在原有尺寸( 长和宽) 基础上增加w i d t h ，只 有这样排样才考虑了切缝的影响。 图3 8 切缝对排样的影响 所要注意的是位于角点、两侧和底部的矩形件如图3 8 所示的1 、3 、2 。由 于它们的位置特殊，所以在进行放大的时候要进行特别处理，如图3 _ 8 中的1 ， 在长和宽方向都只放大了w i d t h 2 ，而2 、3 在宽的方向放大了w i d t h ，而在长的 方向只放大了w z d t h 2 ，所以我们可以得出一个结论： 位置位于角点处的矩形件的长和宽只需放大切缝的一半；位于板材四周的矩 形件则根据其排列的方向的不同，或长放大切缝的宽度，宽放大切缝宽度的一 半，或宽放大切缝的宽度，长放大切缝宽度的一半：位于板材中间的矩形件的长 和宽都是在原基础上放大切缝的宽度。 随着排样的变化，位于四周的矩形件也是各不相同，有可能这次排样是这几 个矩形件，而下次就是另外几个了，所以我们无法确定究竟是哪些矩形件排列在 这些特殊的位置，也就是说我们无法事先判断哪些矩形件该放大切缝宽的一半， 哪些矩形件该全部放大。 为了解决这个问题，我们采用的方法是对所有的矩形件都采用同样的放大原 则，即在原有的长和宽基础上都放大切缝的宽度。这样就会出现图3 9 这样的现 象( 实线表示原始矩形件，虚线表示放大后的矩形件) 。 o x 图3 9 矩形件放大之后的排样 由图可以看出，如果还用原有尺寸的板材来排布矩形件，由于板材四周不需 要切割，所以会出现切割之后的某些矩形件尺寸比原有尺寸大( 如图3 9 中的 1 , 2 ，4 ) 。为了解决这个问题，可以将整个板材也放大切缝的宽度，在排列矩形件 时以放大后的板材作为排样的板材。但要注意的是原有的坐标系不能变动，这样 可以得到如图3 1 0 所示的排样图。 图3 1 0 整个板材放大后的排样图 在图3 1 0 中，对于矩形件p ( 1 ) ，p ( 2 ) ，p ( 4 ) 来说，表示它们位置的 有些点( 如p ( 1 ) 中的1 ，2 ，4 ，5 ) 的位置也随之发生了变化，这样一来。这 些特殊位置的矩形件的位置信息就没有得到正确的表示。解决这个问题的办法是 采用比较记录数据法，即： 对于每个矩形件p ( f ) ， 如果p ( f ) d o t 们，x o 那么p ( f ) d o l 们j f o ； 女口果p ( f ) d o t 【， y o 丑b 么p ( f ) d o t ， 二y 2 0 ： ( o ，4 ) 这样就将超出边界的点的值进行了修f 。 3 5 可排矩形件数目的初步估计 对于一块板材而言，它能够排布的矩形件的数目与矩形件本身的大小有关， 与自身的大小有关，与优化的程度有关。对于一块已经给定尺寸的板材及一批给 定参数的矩形件，不管如何优化它能够排布的矩形件的数目总是有一个最大限度 的 z 9 1 。在排样之前。这个数目到底为多大是无法确定的。如果有批矩形件数目 较多，要用几块板材才能排完( 这种判断可以由经验作出) ，那每块板材究竟 分配多少块矩形件呢? 如果分配得太多，则会有较多数目的矩形件超出板材，虽 然可以在人机交互系统中对这些超边界的矩形件进行处理，但参与运算的矩形件 数目增加会影响系统运行速度，降低工作效率；如果分配得太少，扳材没有得到 充分利用，从而造成不必要的浪费。虽然没有办法可以确切地确定可排矩形件的 具体数目，但可以采用适度函数经验值估计的办法来确定个大概的数目。 由式( 2 4 ) 可知，利用贝p ) 可以估计可排矩形件的大致数目，具体步骤如下： 1 先根据以往的计算结果确定一个适度值厂( 这个值并不要求很准确) ； 2 计算出板材的面积彳，那么所能排入的所有矩形件的面积之和a r e a 。为 a r e a 庐f , a ； 3 从所有的矩形件中依次选取要排入的矩形件，直到这些矩形件的面积之 和大于等于a r e a 。然后停止选取。 该流程图如图3 1 1 所示。 型，然后使用赋值语句将对象赋给变量。如前所述，a p p l i c a t i o n 对象位于 a u t o c a d 层次对象结构的顶层，它代表a u t o c a d 本身，用户的应用程序必须从 a p p l i c a t i o n 对象的建立开始。a u t o c a d 每个对象都有很多方法和属性，图4 5 显 示了a p p l i c a t i o n 对象的部分属性、方法和事件。通过a u t o c a d 应用程序对象 ( a p p l i c a t i o n ) 的属性和方法逐级向下访问就可以访问到所有下级对象。 图4 5a p p l i c a t i o n 对象的属性、方法和事件( 部分) 4 4d e l p h i 基于a c t i v e xa u t o m a t i o n 开发a u t o c a d 基于a c t i v e xa u t o m a t i o n 开发a u t o c a d 在理论上可以用任何一种支持 a c t i v e x 的开发工具，但实际上现在无一例外的都用v b 作为开发工具，这一点可 以体现在a u t o c a d 所开发的帮助文档及众多的关于v b 开发a u t o c a d 的书籍和 文章上 4 q 。v b 简单易学，但相比其它如jb u i l d e r ( j a v a ) 、d e l p h i ( o b j e c t p a s c a l ) 、c + + b u i l d e r ( c + + ) 等真正的面向对象的开发工具而言，v b 使用的 b a s i c 语言过于简单。功能相对较弱，程序稳定性也相对较差，所以有很多程序开 发人员并没有选择v b 。既然可以用任何一种支持a c t i v e x 的开发工具对 a u t o c a d 进行二次开发，所以我们也不必拘泥于v b 这一种开发工具，在此，本 文尝试用d e l p h i 来进行开发。 d e l p h i 是一个非常优秀的快速开发工具，它具有开发速度快，语言结构非常 严谨( o b j e c tp a s c a l ) ，程序模块化好，开发完全面向对象等特点f 4 2 】，是当今最 为流行的开发工具之一。 一一一一一一一一 l萋l幽董|燃妻l一 叫一一一一一吾|一一蚍一 在利用a c t i v e xa u t o m a t i o n 来开发a u t o c a d 时首先必须让开发工具与 a u t o c a d 建立连接。d e l p h i 与a u t o c a d 建立联系的方式是在d e l p h i 建立的应用 程序中添加a u t o c a d 的类型库【4 3 1 。在d e l p h i 编程环境中选择【p r o j e c t 】 i m p o r tt y p el i b r a r y 就会出现图4 6 所示的对话框。 i m p e l t y p e l t b t 删1 图4 6 引入类型库对话框 添加之后在应用程序中将自动添加a p p l i c a t i o n 对象，通过这个对象就可以实 现对a u t o c a d 的控制了。 4 5 重构排样图的方法 如何将排样图引入到a u t o c a d 中去是人机交互寻优后处理系统中非常重要 的一步。如前所述，在记录数据时实际记录的并不是排样图，而是一些表示各矩 形件分布的数据点，所以弓l 入排样图的过程实际是通过这些数据点重构排样图。 每个矩形件用5 个数据点来表示其在板材上的位置，所以将排样图引入到 a u t o c a d 中去实际上是用这5 个数据点在a u t o c a d 中重构一个矩形，重构出来 的排样图如图4 7 所示。 图4 7 用矩形重构的排样图 4 9 很显然，从图中很难分辨出哪些是排列的矩形件，哪些是矩形件与矩形件在 排列时形成的空洞( 因为很多空洞的形状也是矩形) ：另外，如图4 _ 8 所示，由 于编号为4 的矩形件被编号为1 、2 、3 、5 的四个矩形件所包围，所以在选取它的 时候会出现选不上或误选其它矩形件的情况。 图4 8 被包围矩形件的选取 鉴于此两种情况，本系统在重构矩形件时采用的是多段线构造法，用多段线 构造出矩形并将其中一个对角线连起来，以便矩形件和空洞区别开来，同时也方 便矩形件的选取。之所以用多段线来构造主要是考虑到构造出来的图形是一个整 体，这样可以确保任意选择矩形件的一部分都可以将整个矩形件选取到。采用这 种构造方法产生的图形如图4 9 所示。 图4 9 用多段线重构排样图 在此要说明的一点是a u t o c a d 中的坐标系的y 轴方向和c + + b u i l d e r 中的坐 标系的y 轴方向刚好相反，如图4 1 0 所示。在c + + b u i l d e r 中排样的起点是左上 角，而在a u t o c a d 中排样的起点是左下角，所以二者形成的排样图以x 轴对 称。排样坐标虽然有了变化，不过对结果并没有任何影响。 5 0 c + + b u il d e r 的坐标系a u t o c h d 的坐标系 图4 1 0 两种环境中的坐标系的比较 4 6 排样图的交互处理 x 排样图的交互处理主要包括三种情况：矩形件超出边界的处理、矩形件太少 的处理、局部调整优化处理。 4 6 1 矩形件超出边界的处理 超边界是因为在进行自动排样时未进行矩形件选择估计或在估计时所使用的 适应度函数估计值太高等因素造成的。矩形件超出边界的处理在a u t o c a d 中很 容易实现，采用的方法是直接通过观察排样图来判断哪些矩形件超出了边界，然 后用“删除”命令将超出边界的矩形件从排样图上删除。 4 6 2 矩形件太少的处理 这个问题分三种情况，一是排样的矩形件的总数目较少，而所选用的板材较 大。二是在自动排样时所选用的适应度函数估计值太低。三是排样图经过超边界 处理之后使得排样的矩形数目太少。 对于第一种情况对排样图只要进行一些局部优化即可。而对于后两种情况都 要在排样图上增加新的矩形件。 由于考虑到用户对图形的观测及矩形件的选取所以没有用矩形来重构排样 图，采用的方式是用多段线来模拟构造矩形，而在a u t o c a d 中并没有直接用多 段线来构造矩形的命令，因此本系统用d e l p h i 建立了这样一个专用命令窗口如图 4 1 l 所示。 l _， o【_l】|p 图4 。1 1 自建的添加矩形件的命令窗口 这是一个漂浮在a u t o c a d 界面之上的命令窗口，用户可以随意将其拖动到 任意位置，也可以将它置于a u t o c a d 界面之后，等需要使用时再将它调出来。 用户只需要输入实际矩形件的长和宽，它就会根据先前输入的切缝宽度自动放大 所画的矩形件。如果用户没有设雹矩形件的起点坐标，矩形件将自动生成在板材 的右侧。 在添加矩形件时用户将面临着这样一个问题：在排样图上已经排列了多少个 矩形件，这些矩形件的尺寸分别为多少，还有多少个矩形件未排布，它们的尺寸 分别是多大，经过处理之后还剩下多少个未排矩形件。这是在实际交互处理中肯 定存在的问题，为此，本系统特别提供了一个数据窗口以便用户了解矩形件排样 信息。点击添加矩形件命令窗口中的“查看信息表”按钮，将会弹出一个如图 4 1 2 所示的对话框让用户选择保存了排样矩形件尺寸信息的数据表。 图4 1 2 矩形件尺寸信息数据表选择对话框 在下拉控件中会显示所有的矩形件参数数据表，选择正确的表之后点击 “o k ”将出现排样信息表，如图4 1 3 所示e 图4 1 3 排样信息表 在排样信息表中显示了所有矩形件的尺寸、数目，每点击一次“刷新数据” 按钮，程序将记录所有在a u t o c a d 上显示的排样图中的矩形件的信息然后和排 样信息表中的数据进行比较，最后将信息记录在“剩余数目”栏。对于如图4 1 4 所示的排样图经过删除矩形件之后变为如图4 ，1 5 所示。 图4 1 4 未删除矩形件之前的排样图图4 1 5 删除矩形件之前的排样图 经过刷新数据之后所得到的排样信息表如图4 1 6 所示，可以看到，在“剩余 数目”栏显示了各不同尺寸矩形件所剩下的数目。 图4 1 6 刷新之后的排样信息表 4 6 _ 3 局部调整优化 局部调整是优化排样图的一个重要手段f 4 ”，对于排样图的局部调整主要包括 以下三个方面： l - 矩形件之间相互调换位雹，如图4 1 7 所示，a 、b 矩形件调换位置之后所 得的排样图( b ) 比( a ) 更优。 ( a ) 调换之前的排样图 ( b ) 调换之后的排样图 图4 1 7 矩形件相互调换位置来实现排样图的优化 2 将矩形件在原位置进行旋转后重新排列，如图4 2 所示。 3 将矩形件旋转后插入到在排样时形成的空洞中，如图4 1 8 所示。 ( 。) 矩形件插入空洞之前的排样图 ( b ) 矩形件插入空洞之后的排样图 图4 1 8 矩形件旋转后插入到空洞中 4 7 切缝对排样图的影晌 在前面已经经过分析得出了结论：在排样图不同位嚣的矩形件尺寸放大的量 不定都相同，在中间部分的按正常情况放大，在角点位置的长、宽只放大切缝 的一半，在四周的或是长或是宽只放大切缝的一半。由于在添加矩形件时总是由 用户根据具体的排样图来确定矩形件排放的位置所以系统无法确定当前要添加 的矩形究竟按哪一个原则来放大一当然也可以让用户来确定其位置是在中间还 是在两侧但这样做一方面会影响效率，更重要的是一旦确定其位置就无法改 变，所以这种方法是不可取的，这个问题同样在进行矩形件位蚤互换时存在。 本系统采用的方法是对于新添加的所有的矩形不管它会被安排在何处，都按 同一个原则来进行放大：将长和宽都放大切缝的宽度，同时也将板材的长和宽放 大切缝的宽度。这样，在增加矩形件时实质上是以放大后的板材的轮廓线来进行 限制的，在a u t o c a d 中重构的排样图如图4 1 9 所示。 救太后媳扳料轮嚓钱 实胃豪板料鸵窬线 圈4 1 9 在a u i o c a d 中实际重构的排样图 4 8 数据保存 进行交互调接之后要重新记录数据 每个矩形件在排样图上的位置坐标记录； 4 8 1 矩形件位置坐标的记录 在本系统中有两类数据需要保存：一是 二是剩余的矩形件信息的记录。 在记录数据时，系统首先要从a u t o c a d 中“读取”数据，采用的方式是先 遍历模型空间( m o d e ls p a c e ) 所有的图形对象，将符合条件的图形对象的坐标记 录下来。具体步骤如下： 1 先用a u t o c a d 中的子对象m o d e l s p a c e 的属性c o u n t 来计算出在模型空间 中所有的图形对象的数目。 2 循环判断所检测到的对象是不是所需要的对象。在前面已经介绍了排样图 在重构时所采用的是用多段线模拟a u t o c a d 中的矩形命令来重生矩形件 的，所以只需要判断所检测的是不是多段线对象。方法是将所检测到的 对象赋给一个v a r i a n t 变量，然后通过该变量的t y p e 属性来判断是否是 a c s i m p l e 3 d p o l y ( 多段线对象) 。 3 若是多段线对象，