（车辆工程专业论文）二维布局优化神经计算方法研究.pdf

摘要布局问题广泛存在于许多行业并且属于复杂的组合最优化问题，尽管有许多学者在这方面进行了大量的理论研究，并取得了一些进展，但仍然存在大量问题有待进一步的研究。本文对二维布局神经网络的原理和设计方法进行了系统分析和探讨。i 主要研究内容如下：0首先通过广泛查问国内外有关文献，对现有布局求解理论和方法进行了综述与分析，明确了本文的研究方向即利用人工神经网络进行二维布局优化求解。随后对人工神经卜习络求解组合最优化问题的机理和方法进行了系统的研究，成功的将矩形物体的布局问题映射到h o p f i e l d 网络模型。并且通过编制软件模拟计算，对影响人工神经网络布局求解的因素进行了深入讨论和研究接着对b o l t z m a n n 机和c a u c h y 机在布局问题求解上的应用进行了研究，利用c a u c h y 机进行的模拟计算表明，与h o p f i e l d 网络求解算法相比，该算法求解质量较好且稳定，但算法求解时间较长。新兴的混沌神经网络由于其混沌动力学特性，使得网络状态容易摆脱局部极小，因而利用其进行了布局求解神经计算，模拟计算表明，混沌神经网络具有求解速度较快，质量好并且稳定的特点。总之与传统布局求解算法相比，前i 局问题神经计算方法具有解的相对稳定性，且由于乓高度并行性求解运算速度较快。、最后，对全文的：作进行了总结并对以后的研究方向作了展望。l 一关键词：布局，启段式方法，人工神经网络，模拟退火法，混沌a b s t r a c tp a c k i n gp r o b l e m sa r ec a t e g o r i z e da sc o m p l e xc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s t h e r ea r em a n yt h e o r e t i c a ls t u d i e so np a c k i n gp r o b l e m sa n dp r o g r e s sh a sb e e nm a d e b e c a u s eo fi t sh i g hc o m p l e x i t y ,t h e r ea r es t i l lm a n yp r o b l e m st os o l v e i nt h i sd i s s e r t a t i o n ，t h ep r i n c i p l eo fa r t i f i c i a ln e u r a ln e t w o r k ( a n n ) t os o l v ec o m b i n a t o r i a io p t i m i z a t i o np r o b l e m si st h o r o u g h l ys t u d i e d ad e t a i l e dr e v i e wo fc u r r e n tr e s e a r c hs t a t u sb o t hi n l a n da n da b r o a di sm a d eb yt h o r o u g ha n a l y s i so fe x i s t i n ga l g o r i t h m sf o rp a c k i n gp r o b l e m a n dt h er e s e a r c hw i l lb ef o c u so ni m p l e m e n t a t i o np o s s i b i l i t yo fa n nt ot w od i m e n s i o n a lr e c t a n g u l a rp a c k i n gp r o b l e m s t h r o u g has e to fh e u r i s t i cr u l e s ，at w od i m e n s i o nr e c t a n g u l a rp a c k i n gp r o b l e mi sm a p p e dt oh o p f i e l dn e u r a ln e t w o r k t h e nt h r o u g hs i m u l a t i o n ，t h ef a c t o r st h a te r i e c ts o l u t i o no fp a c k i n gp r o b l e m si nt h i sm e t h o da r et h o r o u g h l ys t u d i e d r e s e a r c h0 1 1a p p l i c a t i o no fb o l t z m a nm a c h i n ea n dc a u c h ym a c h i n et os o l v ep a c k i n gp r o b l e m si sc a r r i e do u t t h r o u 血s i m u l a t i o no fc a u c h ym a c h i n e i ti n d i c a t e st h a tt h er e s u l t sa r eb e t t e ra n dm o r es t a b l et h a nh o p f i e l dn e u r a ln e t w o r kb u tn e e d sl o n g e rt i m eb e c a u s eo fi t sc h a r a c t e ro fc h a o sk i n e t i c s c h a o sn e u r a ln e t w o r kc a ng e ta w a yf r o nl o c a lo p t i m a ls o l u t i o n s t h r o u g hs i m u l a t i o n c h a o sn e t w o r kc a no b t a i ns t a b i er e s u l t sa sc a u c h ym a c h i n eb u tn e e d ss h o r t e rt i m e c o m p a r e dw i t ht r a d i t i o n a lp a c k i n ga l g o r i t h m s ，t h er e s u l t so b t a i n e db yp a c k i n gn e u r a ln e t w o r ka r em o r es t a b l e w h a ti sm o r e t h ei n f i n i t ep a r a l l e l i s mo fn e u r a ln e t w o r ki n d i c a t e st h a tp a c k i n gn e u r a ln e t w o r kc a nb eaf e a s i b l ea p p r o a c hf o rs o l v i n gp a c k i n gp r o b l e m sw i t hc e r t a i nc o n d i t i o n s f i n a l l y , c o n c l u s i o n so ft h ew h o l ed i s s e r t a t i o na r ed r a w na n dt h ep e r s p e c t i v eo fr e s e a r c hd i r e c t i o n si sg i v e n k e y w o r d s ：p a c k i n g ，h e u r i s t i cm e t h o d ，a r t i f i c i a ln e u r a ln e t w o r k ，s i m u l a t e da n n e a l i n g ，c h a o si i北方交通大学硕士学位论文第一章绪论第一章绪论布局问题大量地出现在机械制造、出版印刷、服装、皮革、造船、玻璃、交通运输、航空航天，机器人手臂运动规划、大规模集成电路的设计、城市规划和建筑设计等诸多行业。布局结果的好坏对这些行业生产的合理性、经济性和安全性等指标具有重大的影响。布局问题的主要表现有：将许多相同大小的二维矩形块摆放在某一个长方形容器内，使其某性能最优。港1 5 1 、车站装卸生产中叉车托盘上的货物的摆放、托盘尺寸系列的设计及出版业中纸张的切割方案的制定等均属这一类问题。一刀切问题：将某个二维矩形块按照“一刀切原则”切割出一组大小不同的矩形块来，使面积浪费最少。这是玻璃切割中出现的主要问题。( 所谓一刀切原则即每一刀必将一矩形分割成两个矩形)矩形几何布置问题：将许多不同大小的二维矩形布置在一个大的矩形中，使面积覆盖率最大。这是大规模集成电路( v l s i ) 中掩膜设计所碰到的主要问题。二维不规则形体布置问题：将许多任意形状、大小的二维形体布置在一任意形状的二维平面内以使某一性能最优，如服装样本的下料、皮革下料、造船工业中钢板下料等等。三维矩形体布局：将许多不同尺寸的长方体放入一长方体容器当中苎垄! 塑! ! 壁堡主兰垡堡兰蔓二里堕堡以使某一性能最优，如集装箱内具有长方体包装的货物的配载。不规则三维实体的最优布局：将许多任意形状、大小和性能的三维实体摆放在一个任意形状、大小的三维容器中以满足某些约束或使某一目标最优。例如火箭仪器舱内的仪器布局问题。布局问题是复杂的离散组合鼹优化问题。最优化问题可根据求解所需的时间分为几类。如果存在一个算法，它求解问题的时间与问题的大小n 只成多项式( 或更低) 关系，则说它是多项式的，属于p类。p 类其实是另一类既n p 类( n p 是非确定性多项式n o n d e t e r m i n i s t i cp o l y n o m i a l 的缩写) 的子类，对于n p 问题我们可以以多项式时间试验对解的一个“猜测”是不是正确。n p 问题中另一个重要的子类是所谓n p 完全( n p c o m p l e t e ) 问题，这是最困难的n p 问题。般来说，如果我们能够找到一个确定性算法以多项式时间求解一个n p 完全问题，那么所有其它n p 问题都能以多项式时间解决，在这种情况下，p ，n p 和n p 一完全都是相同的类，不过，极可能的是p 不等于n p 。经验说明，求解一个n p 完全问题所需的时间随n 指数增长。前人已经证明即使是最简单的一维布局也为n p 完全问题，因此长期以来关于布局问题的理论研究进展较慢。现实生活中，布局问题往往用人工方式根据自身经验进行试凑摆放；经过多次反复最后找出一个可行布局方案。由于受到问题复杂性和求解时间的限制，许多更好的方案在布局设计时经常无法被发现。当布局规模较大，布局物体形状复杂，约束条件增多时，人工往往需要花费几十天的时间进行布局求解。尤其在国内航天、服装、皮革和其它一些轻工企业中，处理手段的落后对生产效率和效益影响很大。2 ，北方交通人学硕士学位论上第一章绪论国外发达国家工业界对这个问题非常重视，尤其是航天和汽车业，已经有了较成熟的应用，如仪器仓和车体内部的物体摆放充分考虑到人机工程和优化布局，在这方面远领先于国内。g a r y 和j o h n s o n 在其关于n p 完全性理论的专著中已明确指出：在有限合理的时间内不可能求得n p 完全问题的精确解。从s w e e n e y 和p a t e m o s t e r 对1 9 4 0 年到1 9 9 0年五十年间发表的4 0 0 多篇有关c u t t i n gm a dp a c k i n g 的文章的统计发现，这些文章涉及1 4 0 多个领域，并且绝大多数布局算法都是启发式的。因为同样的布局问题在不同的行业和应用背景下有不同的约束条件和不同的目标，所以试图找到一种求解布局问题的通用算法是不可行的。应针对不同的工业背景，研究相应的专用算法。这种趋势反映在关于布局问题的文章发表在不同的科技刊物上，如计算几何学、计算机图形学、计算机辅助设计和运筹学杂志等。尽管不同行业的布局问题在形式上差别很大，但寻找布局物体在布局空间中的合理布局这一首要目标是共同的。对同一个布局问题，在不同的应用背景下，某一布局物体的可行位置和方向可能不同，但用于求解问题的理论和方法大多可以互用，因此对布局问题的通用求解理论和方法进行研究是必要的。1 2 国内外研究综述布局问题广泛出现在诸多领域，并且在不同的应用领域有不同的表现形式，因此从总体上对布局问题的研究进行概括不是一件容易的事，然而任何复杂系统的实施和控制都包含有定性和定量两种分析和决策过程。就布局问题的求解而言，布局问题知识模型的建立是在定3 韭查茎望苎塑兰堡兰苎墨二垦塑堡性分析基础上的定性决策过程；而对布局知识模型的计算机自动化处理则属于定量分析和决策过程，所以可从布局问题知识模型的建立和对此模型的自动化处理两个方面对国内外的研究现状进行综述。1 2 1 布局问题知识模型的建立工程布局问题的复杂度体现在如下两个方面：首先，工程布局问题无法用纯数学模型精确表达。其次，可用数学模型表达的部分具有n p 完全计算复杂度。然而现有的大部分布局求解方法在建立布局问题知识模型时，一般是通过对原问题进行简化，在次基础上建立单纯的数学模型，研究的重点集中在关于所建立数学模型求解算法的设计上。当原问题较复杂时，所建立的数学模型往往与原问题不相符合，得到的解可能与实际情况有较大的差异。可见，布局问题知识模型的建立是布局领域研究的一个弱点。王金敏将布局问题看作约束满足问题，在深入分析布局问题所涉及各种约束特点的基础上引入导向约束，为基于约束求解方法的柔适性提供了可靠保证。并利用面向对象的方法较为完善地表达了各种布局约束，进而建立了基于约束的布局问题知识模型。同传统的布局问题数学模型相比，基于约束的布局知识模型较好地表达了布局问题所涉及到的无法用数学方法精确描述的各种约束条件，较为精确地表达了原始布局问题。工程问题不仅涉及可用数学模型描述的知识( 如问题的优化目标等) 而且往往涉及只能用符号模型描述的知识( 如布局物体的材料性能以及装卸工艺等) ，所以任何单一模型的知识模型都不足以精确表d 一北方交通大学硕士学位论文第一章绪论达这样的工程布局问题。智能工程理论指导下的布局问题知识模型是复合型的，既包括那些可用数学模型描述的知识，也包括那些只能用符号才能表达的知识。1 2 2 布局问题求解方法综述尽管布局问题的表现形式多种多样，但总的来说布局问题可分为规则物体( 一般指长方形物体或长方体) 的布局问题和不规则物体的布局问题两种。在上节所述的六类布局问题中，由于两类问题附加有特殊条件，问题本身可以抽象为纯数学模型的表达形式，因此理论上这类问题已获得解决，主要成果有动态规划、分支定界树搜索等方法。两类问题虽然吸引了国内外大量的理论研究，但是由于问题本身已变成n p 完全问题，随着问题规模的增加，解空间呈指数倍地增长，出现空间爆炸现象，动态规划、分支定界、隐枚举等基于穷举思想的算法都行不通，因此这两类问题的所有算法都是基于特定应用领域的启发式算法。两类问题，由于布局对象形状的随意性，使得问题变得异常复杂，目前研究报导较少，进展很小。布局问题是复杂的组合最优化问题，所以组合最优化领域存在的理论研究同实际应用间存在着较大差距的现象在布局领域中也有所体现。理论研究人员偏重与将布局问题抽象成一定的数学模型，然后借用各种优化方法进行问题的求解，并认为这些基于严谨的数学推导的优化方法是进行问题求解的正统方法：而实际工作人员则偏重于各种布局启发式方法的研究，认为纯理论的布局求解方法不能解决实际问题。问题的求解只能依赖于各种启发式方法。同时人们发现实际应用s 一北方交通大学硕士学位论文第一童绪论中的许多问题都是n p 完全问题，这在组合最优化领域尤其突出。g a r e y和j o h n s o n 的出色工作使得组合最优化领域的理论研究人员开始注重对各种启发式方法的研究，在其纯理论的搜索策略中巧妙地加入了各种启发式经验，使得基于优化理论的各种布局问题求解更加适合实际问题的求解；同时实际工作人员也开始重视各种优化方法的应用，使得各种启发式的布局求解方法更加系统化。因此，尽管规则物体布局问题的求解方法较多，但归纳起来可分为如下几类：1 数学规划法数学规划法包括分支定界法( b r a n c h a n d b o u n da l g o r i t h m ) 、动态规划法( d y n a m i cp r o g r a m m i n g ) 、整数规划法( i n t e g e rp r o g r a m m i n g )非线性规划法( n o n 1 i n e a rp r o g r a m m i n g ) 和线性规划法( l i n e a rp r o g r a m m i n g ) 等。在大量有关矩形物体布局问题尤其是板材加工业的一刀切问题上，分枝定界法被广泛应用。树的分枝对应于各种可能的切割情形，而各种结点则表示切割下的矩形。随着研究的深入，分枝定界法已经能够用于非一刀切问题。a r e n a l e s 等设计了一种分枝定界布局求解算法，其中用于表示问题求解过程的b b 树是一棵与或树，并规定了分技的两种具体情形。一种是每个结点只产生两个分枝，对应于一刀切分割；另一种是每个结点产生五个分枝，对应于非一刀切的一种简单情形。通过上述两种分枝方法，减少了需要搜索的解空间的规模。该算法还采用了一些规则和启发式经验，减少了与或树的搜索时间，加快了问题求解速度。v a l e r i od ec a r v a l h o 等将两阶段下料问题抽象为约束优化问题，并6 北方交通大学硕士学位论文第一章绪论用一简化的线性规划模型来表达该约束优化问题，最后用列生成技术对得到的线性舰划模型进行求解。为克服线性规划模型中变量过多的情况，使用了一个预处理过程并利用特定的规则删除了一些不良模式，从而使问题得到解决。b e a s l e y 则将布局问题抽象为o l 整数规划模型。基本思路是用一个二值变量表示某类型特定物体的可行位置，代表布局容器的长方形则可表示为可行位置左上角点的坐标分割成的网络。只要每个网络位置仅被不多于一个的布局物体所占据，得到的一组布局物体的位置便是可行的。这个要求可很容易地表达为关于每个网络点的线性约束，同时，每种类型布局物体的数目要求也可作为约束条件合并到上述线性约束中。b e a s l e y 将问题的求解分为如下三步进行。首先，在o 1整数规划模型的基础上建立了拉格郎目松弛模型，该模型给优化目标的值提供了一个上限：其次，用次梯度优化方法最小化该上限；最后用树搜索过程解决问题。结果表明，该方法适合于中等规模矩形物体布局问题的求解。以分枝定界法为代表的数学规划法，由于纯数学推导中启发式经验的加入，极大的提高了问题的求解能力，成为布局求解方法中一种主要方法。但是因为数学规划法在进行问题的求解时需要将问题抽象为一定的数学模型，所以当实际的问题涉及一些不容易用数学模型表达的约束条件时，采用各种近似方法得到的数学模型往往会与原问题产生较大的偏差，进而影响问题的求解效果。2 启发式布局求解算法由于布局问题在各个不同的应用领域具有不同的特点，所以针对 北方交通大学硕士学位论文第一章绪论各个领域有不同的具体的求解算法。启发式布局求解算法的设计可充分发挥设计者的创造性，并且可糅合进成功的经验，因而成为倍受算法设计者喜爱的一种问题求解方法。布局问题是n p 完全问题，问题的求解只能依赖各种启发式方法，所以现有的绝大多数布局求解算法都是启发式的。布局启发式算法大体上可分为如下两类：( 1 ) 构造式启发算法：通过逐步增加解中的构造元素而得到问题的可行解。因为构造式启发布局算法的循环系数与解中构造元素的数目成正比而与解空间的大小无关，所以其问题求解的速度是相当快的。布局问题中构造法基本上由两类规则组成。第一类为定序规则( o r d e r i n gr u l e s ) ，用来决定待布局物体放入布局空间的先后顺序；第二类为定位规则( p l a c e m e n tr u l e s ) ，用来确定布局物体在布局空间中的具体摆放位置。研究使用不同的定位规则和定序规则就产生了不同的构造布局方法。目前使用较多且效果较好的定序规则有：按照布局物体最短边或最长边长递减的顺序；按物体体积递减的顺序；按布局物体最小面面积递减的顺序；按布局物体可行域递增的顺序进行定序。定序规则的研究成果主要有：占角策略，即将布局物体摆放在布局容器的某一角；顺放策略，即从布局容器的某一角开始将布局物体沿着容器的摆放：在底盘装载中，将布局立方体先沿着边放置，最后摆放到底盘中心；在三维规则布局中，从布局容器的某一面墙开始，一层一层布局，在某一面墙上再确定一条边，最后归结为一个角；在三维规则布局中，根据布局物体布局剩余空间的凸体积进行布局。不规则物体布局具有与规则物体布局不同的特点，所阻其定位策略与规则物体布局不同。a m a r a le ta l 按布局物体面积递减将布局物体8 北方交通大学硕士学位论文第一章绪论定序，对大的和小的布局物体分别采用两种不同的定位策略。试图以小的布局物体填补大的布局物体拼合时留下的空隙以提高覆盖率。a l b a n oa n ds a p u p p o 将分枝定界搜索策略用于布局物体位置的确定。在布局过程中，允许物体任意角度旋转，所以布局问题解的状态空间很大。( 2 ) 启发式布局求解的一种改进算法：从个可行解开始，通过其邻域内的搜索操作如交换、合并、增加、删除结构元素等来改进解的质量。基于这种思想，a l b a n o 开发了一个人机交互布局系统。系统首先产生个初始布局方案，如果用户对该方案较为满意，则布局结束并输出布局方案；否则，用户根据经验对布局方案中不合理的部分给系统一个更改或删除信息，对布局方案进行不断修改，直到得到满意的布局方案为止。黄文奇等提出了方格布局问题的改进策略。首先采用局部调整策略( 力迫策略) 进行改进，即某一时刻，若位置总势能u 0 ，则令各布局物体沿受力方向移动得到下一时刻的位置。如果此时位置总势能u = 0 则策略应用成功，停止计算；若u 不为零但有所减少则沿受力方向继续移动物体；若u 没有减少则策略失败；当局部调整进行到总势能已无法再减少但仍然大于零时，采用大范围调整策略，即将具有最大挤压势能的布局物体放到当前状态下布局空间中空隙度最大的位置。由于该算法中一些计算( 如位置总势能) 在计算机上实现具有一定难度，而人脑在这些方面恰恰具有优越性，因此将计算机和人脑优势互补，开发具有人机交互功能的改进布局求解算法是一种可行的途径。与数学规划法相比，启发式布局求解算法具有设计简便、灵活和q 北方交通大学硕士学位论丈篱一章绪论计算速度快等优点，是目前最重要的一种实用问题求解方法。但是启发式算法的通用性较差，对某种问题有效的启发式算法不一定适合其它问题的求解，同时该算法的性能分析也没能得到圆满解决，缺乏完整的数学理论作为工具对启发式算法进行分折。该方法由于其实用性受到越来越多重视。同禁忌搜索、基因算法或模拟退火等搜索算法相结合，可开发出形式多样的算法。3 圈论求解方法d o w s l a n d 和l e u n g 等首先利用图论作为工具，建立了布局问题的图论模型。他们将矩形或立方体布局物体视为图的结点，若顶点之间存在弧连接则表明相应的两布局物体相邻。于是问题转化为求解连接图的极大独立集或最大权平面子图。尽管图论在其它的一些领域得到广泛应用并且取得良好进展，但在对于布局优化问题，图论方法只能解决小规模规则物体的布局问题。原因在于，将一个相邻拓扑关系图转化为无尺寸布局时产生了组合爆炸，而求解极大独立集或最大权平面子图的方法往往为分枝定界法、整数规划法及动态规划法。因此采用图论的方法解决布局优化问题目前没有取得很好的进展。4 数值优化方法数值优化方法由于具有较为成熟的理论和相应的算法，园而在工程设计领域广泛应用并取得了很多令人满意的成果。因此很多专家研究利用数值优化方法解决布局优化问题。u d y 利用序列二次规划和广义简约梯度法来解决小型三维布局问题，但其解的质量过分依赖与初始位置的选择，这也是算法本身决定的。k i m h e 和g o s s a r d 通过惩罚因子将布局约束转化为目标函数惩罚项，然后用无约束优化方法来求1 0 北方交通丈学硕士学位论文第一章绪论解。黄文奇等借鉴有限元求解弹性力学问题的思想，提出了“挤压弹性势能”的概念来度量布局物体的相互嵌入程度，但是其中两物体距离的计算很困难。腾弘飞等对人造卫星再入仓的布局进行研究提出了旋转锥体中圆柱体和长方体的布局优化算法，取得一定进展。优化算法求解性能的优劣依赖于数学模型的建立且只能找到局部最优解，此外初始位置的选择对布局结果也有显著影响。对于有些问题由于很难建立准确的数学模型，只能用简化的数学模型来描述，造成局部最优解的数目急剧增加，难以得到满意的解。5 基因算法和模拟退火算法基因算法是一种基于生物进化原理的全新搜索策略，即根据优胜劣汰、适者生存等自然进化规则，逐代优选适应性能评价函数的参数，然后重新组合形成新的参数组合。与传统搜索算法不同之处在于：基因算法使用编码字符串来表示各个变量，而不涉及变量本身；该算法在搜索最佳参数组合时不仅搜索一个点而是同时搜索多个可行解：它用适合函数来评价可行解，意义是隐含的；该算法求解过程是随机的而不是确定的。模拟退火算法由于有可能求得布局问题的全局最优解而受到人们越来越多的重视，发展成为求解大规模组合最优化问题特别是n p 完全问题的有效近似算法。其基本思想是：用目标评价函数得出一状态下的目标函数值，然后随机产生下状态得出其目标函数值，如果目标函数值得到改善，则接受新的状态作为当前状态；否则以一定概率接受该状态作为当前状态。如此循环直到找到满意最优解或达到终止状态。可以看出该算法在达到局部最优点时有可能跳出局部最优点，些立奎堕查兰! 堂堡! 垒苎蔓二童笪堡从而向全局最优点靠近，可能得到全局最优解。6 约束求解算法王金敏认为布局问题可以看成是满足一定功能要求和满足布局的显式及隐式说明的问题，此处的要求和说明都可认为是约束，因而布局问题为一个约束满足问题7 神经网络法和并行算法自从h o p f i e i d 利用h o p f i e l d 神经网络成功的求解了旅行商( t s p )问题以来，神经网络在组合优化领域得到越来越多的重视，有了很大进展。郝局优化问题作为组合优化的一个分技也不例外。戴佐和王爱虎利用h o p f i e l d 神经网络对布局问题进行了初步研究，表明效果良好。王爱虎运用并行理论求解伟局问题也取得了良好进展。1 3 本文研究内容和意义综上所述，神经网络种经计算和启发式算法的结合是今后布局研究的个重要方向，神经网络由于其并行运算的特点，具有很强的计算能力，因此本文在这方面进行了深入的研究，由于布局问题在许多行业生产中普遍存在并由于其求解的高度复杂性，本文的探索和研究既有理论意义也有实用价值。本文主要对几种不同的人工神经网络在布局上的应用作出探讨和研究。并对规则物体布局算法向不规则物体布局算法移植改进进行了研究。对不规则物体布局的可行且简便实用的方法绝大多数都是用最小包络矩形法，即将参加布局的不规则物体以最小包络矩形进行包络，而后用这些最小包络矩形进行布局，此外对复杂不规则物体布局还可用组合套排和嵌入等方法组合在一起后求1 2 北方交通大学硕上学位论文第一章绪论最小包络矩形，以提高覆盖率。因此对矩形物体的布局便是最基本的布局问题。全文安排如下：第一章对布局问题的重要性及研究现状进行了深入细致的介绍和论述。从而确定了本文研究的目标。第二章对h o p f i e l d 网络用于布局问题的求解方法进行了讨论，指出了目前h o p f i e l d 网络求解该类问题的不足，并给出了改进算法。从网络参数、初始状态和能量函数等影响h o p f i e l d 网络求解结果的因素进行了讨论，给出了初步结论。第三章在h o p f i e l d 网络解决布局问题方法的基础上，提出了b o l t z m a n n 机和c a u c h y 机用于布局问题求解思路，并对算法原理进行了详细讨论，指出了这两种神经网络求解方法与h o p f i e l d 网络相比较的优缺点。第四章对目前较新发展的混沌神经网络模型在布局问题上的应用进行了研究。由于混沌神经网络模型接近人脑实际神经元模型，因而具有很好的发展前途。第五章给出了全文总结并指出了今后应进行的研究方向。! ! 查茎望查兰堡主堂竺丝塞第二章h o p f i e l d 晡4 络布局优化神经计算第二章h o p f i e l d 网络布局优化神经计算2 1 人工神经嘲络概述人工神经网络是一门多学科、综合性的研究领域。8 0 年代以来，研究以非线往大规模并行分布式处理为主流的神经网络取得了杰出的进展，其应用已渗透到各个领域，并在智能控制、模式识别、人工智能、知识工程、机器人学等方面取得了引人注目的成就。目前在我国，神经网络及其应用的研究正处在热潮之中。人工神经网络可概括性地定义为由大量简单单元( 神经元，可用电子元件，光学元件等模拟之) 广泛相互连接而成的复杂网络系统，它是在现代神经网络科学研究成果的基础上提出的，反映了人脑功能的若干基本特征，但并非神经系统的真实写照，而只是其简化、抽象和模拟。也就是说人工神经网络是一种抽象的数学模型，从不同的角度和目标出发，它可用作为计算模型，或大脑结构模型，或大脑结构模型，或认知模型。人工神经网络的研究为优化问题求解开辟了一个全新领域。神经元是神经网络的基本处理单元，它一般是一个多输入单输出的非线性器件，其结构模型如图2 ，1 所示。其中“，为神经元的内部状态，鼠为阀值，工，为输入信号，矿表示从“，到“，连接权值，s ，表示外部输入信号( 在某些情况下，它可以控制神经元“，使得它保持在某一状态) 。这种结构模型可形式地描述为：1 4 竖蔓奎i ! ! 壁堕主兰壁堡塞兰三兰旦! ! ! 坚旦塑塑旦垡垡塑竺j 篁盯，= z w , j x ，+ j 。一0 ，= i ( o ，)y ，= g ( u ，) = h ( o - ，) ， = g 厂图2 1 神经元结构模型w i l当神经元没有内部状态时，可以令f = i ( 恒等式) 。常用神经元非线性特性可描述如下：阀值型。在这种模型内部没有内部状态，而且函数f 是一个阶跃函数( 图2 2 a 所示) ，即：h ( x ：) = s ( x ，) = “( 而)，ll ，x ， 0卜1 0 尚o分段线性函数。如图2 2 b 所示；s 状。它一般是没有内部状态并且连续取值，其i o 特性常用对数或双曲正切等一类s 曲线来表示。这类曲线反映了神经元的饱和特性。如图2 2 c 所示。1 5 -北方交通大学硕士学位论史第二章h o p f i e l d 网络布局优化f 申经计算尽管目前神经网络的类型很多，但就总体而言，均是采用巨量并( a ) 一呕禹酿型( b ) ，于段线任型f c 蝠i g i n o a d 掣图2 2 神经元的i 0 特性行，力图表现人脑的基本特征。神经网络具有以下的基本特征：l 以大规模模拟并行处理为主。神经网络的大规模并行处理不同于多处理器的并行机。单纯的并行机制不能很好地体现因果关系和信息的相互影响，功能必然过于简单，好的网络应是大规模并行处理和串行处理的有机结合。神经网络擅长的不是精密的数学计算或绝对准确的决策，只是要求基本正确。正如人不可能绝对正确一样，神经网络主要涉及有限次“运算”，而且它本身具有容错性和纠错性，误差不会积累，高精度实际上并无必要。2 具有很强的鲁棒性和容错性，善于联想、概括、类比和推广。由于信息存储本质上是分布式的，任何局部的损伤不会影响整体的结果。3 具有很强的自学能力。系统可以在学习过程中不断完善自己，具有创新特点，这不同于人工智能中的专家系统，后者只是专家经验的知识库，并不能创新和发展。4 它只是一个具有高度非线性的超大规模连续时间动力系统，具有集体运算的能力和一般非线性动力系统的共性，即不可预测性、吸1 6 ，些方交通大学硕士学位论文第二章h o p f i e l d 网络布局优化神经计算引性、耗散性、非平衡性、不可逆性、广泛联结性和自适应性等，这与在本质上是线性系统的传统数字计算机不同。能量函数是神经网络的一个基本量。按对能量函数的利用可分为三种工作方式：能量函数的所有极小点都起作用。这一类主要用于各种联想存储器、信息压缩及编码。-利用能量函数的全局极小点。这一类主要用于求解组合最优化问题。本文布局优化神经计算原理就是属于此类。_ 在工作中不考虑能量函数，主要作用是函数映射，它主要用于模式分类和特征提取。存储能力和计算能力是现代计算机科学的两大基本问题，在人工神经网络中，它们构成了神经网络理论的两个最基本问题。在应用神经网络存储信息时，信息是分布存储的而且是按照以后加工处理的要求而存储的，信息可以联想记忆。电子计算机主要用于离散的符号处理，它基于算法和编程，而应用神经网络的计算则基于连续的动力系统中的状态空间变换的轨迹，神经网络的计算就是其中状态的转换过程，对给定的输入，其结果就是系统的稳定状态。2 2 布局优化神经计算原理利用神经网络求解优化问题在许多技术和经济领域中有广泛的应用价值。在这些问题中，能量就是代价函数或目标函数。最优化计算神经网络中一般研究的也是实际情况理想化后的模型。神经网络方法用于组合最优化的思路是：将优化函数和约束函数的线性表达式作为1 7 些妻奎里茎兰堡主兰垡笙墨第二章h o p f i e l d 网络布局优化神经计算能量函数e ，从e 出发设计相应的神经网络：d e d v ，= - db l x j d tv ，：= g ( “。)h o p f i e l d 教授提出的h o p f i e l d 神经网络开辟了神经网络模型在计算机科学应用中的新天地，开辟了组合优化问题求解的一个全新途径。用神经网络来进行组合优化问题求解是当前神经网络应用研究的一大热点。由于历史的原因，这方面的工作大多局限于一些具有代表性和共性的问题，如旅行商问题( t s p ) 和图论中图的划分问题( g p p ) 、顶点覆盖问题( v c p ) 和最大独立集问题( m i s p ) 等，而对于能解决各个特殊领域的实际组合最优化问题( 如布局问题) 的神经网络的研究不多见。王爱虎和王金敏运用神经网络对布局物体进行了初步的研究，但仅限于h o p f i e l d t a n k 模型。2 2 1 神经网络计算的收敛条件一般认为，神经网络系统是一个高度复杂的非线性动力学系统。虽然每个神经元的结构和功能十分简单，但有大量神经元构成的神经网络系统的行为丰富多采十分复杂。c o h e n 和g r o s s b e r g 对具有形如式( 2 2 ) 所示的微分方程所表示关系的动力学系统进行了深入的研究( 系统的数学模型概括了相当多的神经网络模型) ，发现了以式( 2 2 ) 所示的微分方程为特征的神经网络收敛的条件。鲁硇g ，枇妫一j 兰= l c v g j g 明眩z ，研究结果表明，具有式( 2 2 ) 所示微分方程所表示关系的动力北方交通大学硕士学位论文第二章h o p f i e l d 网络布局优化神经计算学系统存在一个能量方程( l y a p u n o v 方程) ，如果矩阵c 。和函数a 。b 。，g ，满足如下的三个条件：( 1 )矩阵c 口是对称矩阵，即c ”2 c ( 2 )函数口，和b ，连续并且口，非负；( 3 )函数g ，非减。一个动力学系统的能量方程对组成系统的微分方程的收敛行为施加了约束，使得系统总是朝使能量方程非增的方程进化。如果具有式( 2 2 ) 所示微分关系的动力学系统存在一个能量方程，则无论系统的初始状态如何，系统最终必将达到一个稳定状态，且该稳定状态对应于能量方程的一个局部最小值。因此，如果能找到某一组合最优化问题的形如式( 2 2 ) 且满足以上三个稳定性条件的能量方程，则可用任何以式( 2 2 ) 为特征的神经网络模型进行组合最优化问题的求解，这就是神经网络求解组合最优化的基本原理。h o p f i e l d 和t a n k 独立地发现了一个满足上述条件的神经网络模型，并将其用于t s p 问题的求解，即所谓的h o p f i e l d 网络模型。h o p f i e l d网络模型是一种非适应反馈网络模型，是用于组合最优化问题求解的通用模型。以后又陆续开发了b o l t z m a n n 机、c a u c h y 机模型及混沌神经网络等神经网络模型可对一些组合优化问题进行有效求解。本文将对这几种神经网络模型在布局问题求解中的应用进行研究。1 9 ! ! 查奎堡查堂堡主兰堡堡塞第二章h o p f i e l d 网络布局优化神经计算2 3h o p f i e l d 神经网络布局优化计算原理如前所述，h o p f i e l d 教授提出的h o p f i e l d 神经网络开辟了神经网络模型在计算机科学应用中的新天地，开辟了组合优化问题求解的一个全新途径。下面就其求解方法和原理进行讨论，对原来算法的缺点进行了讨论并给出其改进算法。影响神经计算求解质量的因素主要有网络参数、网络初始状态和能量函数的设计等，本文对这三个方面对求解质量的影响进行了研究和讨论。2 3 1h o f i e l d 神经网络模型以下通过对h o p f i e l d 网络的神经元的输k 输出关系、运动方程和网络的能量函数这三个方面的数学描述，揭示h o p f i e l d 网络是极小值求解机这一计算特征。然后运用该网络进行布局优化计算。( 1 ) 离散异步h o p f i e l d 模型离散模型中每个神经元的输入“，和输出v ，满足阶梯函数：v ，= j 印( 矾)( 2 3 )不妨假设v ，只取0 和1 两个值，则其输入输出关系见图2 3 。每个神经元i 与其他神经元j 都有联系，用连接强度r 。表示第j个神经元对第i 个神经元的输入连接强度。神经元i 的输入有两类：一是外部输入j ，另一来自其他神经元。因此神经元i 的总输入是：乃v j + f ，j ，2 0 北方交通大兰壁学位论文第二章h o p f i e l d 网络布局优化神经计算矿tllr _ 一o j r _ 一一11 ，t “v ，+ i f “f矿广0 ，z t u v i + j r 。 z 拉li = lj = l = ij i式中，。和w i 分别为布局物体i 的宽度和高度。约束条件一般可表示为：h尸c 2 = v 。，一n = 0j = 1x = l2 4 1 布局神经网络的能量方程为使上述具有n * p 个神经元的h o p f i e l d 神经网络成功地解决矩形物体的布局问题，必须找到最低能量状态对应于布局最优解的能量方程。一3 0 一0=矿知m，| |c= 坚互至望苎堂堡圭! 型塑塞一苎三兰旦! ! ! ! 里塑塑塑旦垡些翌垒! 兰根据前述能量函数的构造方法，将有约束的布局优化问题转化为非约束问题。王爱虎给出布局神经网络的能量方程为：e = i a 刍n 至p 盖p 一。矿，十i b ( 善n 至py 。一j v ) 2等耋砉【扣扩n2+了d兰p苫nn【w，飞)2i1上j = 1y x f l=2 = l j ：li i。有关研究表明，这种能量函数对于网络参数太敏感，解的质量太低，原因在于其第一项和第二项分别所对应全局最优点不是整个能量函数的全局最优点。h o p f i e l d 原模型的致命弱点是经常陷入无效解。本文根据有关研究将能量函数化为：e ：昙圭( 圭一1 ) z +导圭雏帆一渺n 。 2 + 等耋耋飞肌吲z ，上xy x f _ lf i i2j = l _ l l其中a 、c 、d 为正数，z ，、w 。分别为布局物体i 的长度和宽度。第一项为约束项，该项为0 当且仅当每一列中只有一个神经元的输出为1 ；第二项为优化项，该项为0 当且仅当每组长度相等；第三项为0 当且仅当每组中布局物体的高度相等。这是一个多目标组合优化问题。仿真研究表明，改进后的方法具有收敛速度快，在参数选择适当的情况下易获得优化解等特点。由神经元运动方程d 础= 一a e 归矿。，推导出神经元( x ，i ) 的3 1 北方交通大学硕士学位论文第二章h o p f i e l d 网络布局优化千甲经计算动态方程警= 一爿( 鼽一t ) 埘j 氓= t 计算出d “，。d t 的值后，按照下式计算下一个输入状态。( 2 8 )o + 血) = 0 。) + 华i 。血( 29)atu对于输出特性曲线，研究证明对于如式( 2 7 ) 所示描述的系统不论系统的初值如何，沿系统运动轨道总有：d e t i t 0 ，而且当且仅当d u 。，d t = 0 时，扭西= 0 。进一步研究证明，对于输出特性曲线，如果它是单调非减，在每一点上的导数满足上述条件，且一阶导数单调非减，那么输出特性曲线不一定要选择成一个有明确表达式的函数。这就为简化计算和控制系统的运动提供了手段。为了使网络输出有意义，输出特性益线必须具有饱和特性，这样做能保证系统的收敛性。本文中输出特性曲线采用s 型函数，即：圳吩扣t 础 c 对于所。，下面具体分析介绍在软件模拟实现优化计算的过程中重点考虑的几个问题。v矿，卅一w，_lpd一埘矿r _ 1，一，hc2+! ! 互奎望查堂堡上学位论文第二章h o p f i e l d 网络布局优化神经计算2 4 2 网络参数的选择式( 27 ) 中的网络参数a ，c ，d ，等对网络的变化相当敏感，原则上不能随意改变，选择时主要考虑以下两个问题进行折衷：l 、当与a 的值相比c 和d 的值选择较小时容易得到合法解，但解的波动范围较大，经常得到质量较差的解；其值较大时可增加最优分组的权重，从而使合法解趋于最优，但经常得不到合法解。本文中在a = 0 ，5 的情况下改变c 和d 的值，编制软件进行模拟计算得出c 和d 较理想地变化范围即可行域。2 、“o 是放大器的增益，太小时阀值函数接近于符号函数，不能获得较好的解，太大时，s 型函数过于平坦，神经元状态不易于收敛到o 和l ，从而使获得合法解的概率下降。本文根据经验取“。= o 0 2 ，然后在此基础上改变其大小，通过模拟计算得出其变化对解质量的影响。这样的选择使能量函数式( 2 7 ) 的数值减小数量级，从而使舡的数值也减小，由于程序是以e 为收敛的判据，因而上述选择加快了程序的收敛速度。2 4 3 网络初始状态的选择神经元输