粒子群优化算法在玻璃排版问题中的应用.pdf

四川大学硕士学位论文粒子群优化算法在玻璃排版问题中的应用控制理论与控制工程专业研究生徐辉指导教师舒朝君粒子群优化算法( P a r t i c l eS w a r mO p t i m i z a t i o n - P S O ) 是一种基于群体的进化算法，算法通过微粒间的相互作用来发现复杂搜索空间中的最优区域由于粒子群算法在函数优化等领域有广阔的应用前景，所以自算法提出以来，引起了相关领域众多学者的关注和研究，成为演化计算研究的热点本文将粒子群优化算法用于解决一个多目标组合优化问韪——玻璃排版优化问题基于粒子群算法对玻璃排版进行优化的研究目前在国内还没有见到有相关的资料介绍，本文对问题的求解提出了一些新的实现方法，并通过实验实现了该问题的优化在解决玻璃排版优化问题时，我们将该问题分解成多个单一目标问题，即布局问题和旅行商问题，逐步对其进行求解，以降低整体求解难度在用粒子群算法求解每个问题时，针对其问题的特殊性，对粒子群优化算法的描述进行了必要的修改，以实现问题的求解在求解布局问题时，我们采用了B * - t r e e结构来描述一个布局中各玻璃模块之间的关系，并利用模块之间的组合值来逐步建立一个最优的布局排版；在求解旅行商问题时，我们利用了交换子和交换序的概念，并对算法迭代公式中的加法运算做了新的定义，通过交换操作实现了最短切割路径的求解。

前一步布局问题的求解对下一步旅行商问题的求解有着很大的影响，即合理的布局排版方案不一定就是唯一的，雨不同豹布局方案就会有不同的切割路径，其长短也是不相同的，所以说布局方案越优，就越有利于求解旅行商问题找到更短的切割路径本文的主要内容和结构安排如下：第一章介绍了本文要作的工作、工作背四J I I 大学硕士学位论文景和问题的提出；第二章对粒子群算法做了系统的介绍主要内容有；算法的背景、原理、数学表达及其具体实现步骤等；第三章详细讲解了玻璃排版优化问题中平面布局问题的粒子群优化算法的设计、具体实现和试验结果：第四章详细介绍了玻璃排版优化问题中旅行商问题的粒子群优化算法的设计、具体实现和试验结果，并对布局问题和旅行商问题的求解关系进行了讨论；第五章是对本文的总结关键词：粒子群优化算法组合优化问题B 丰一t r e e 结构平面布局问题旅行商问题Ⅱ四川大学硕士学位论文A b s t r a c tT h ea l g o r i t h mo fp a r t i c l es w a r mo p t i m i z a t i o ni sa ne v o l u t i o n a r ya l g o r i t h m ．T h ea l g o r i t h mo fp a r t i c l es w a r mo p t i m i z a t i o nf i n do p t i m a lr e g i o n so fc o m p l e xs e a r c hs p a c et h r o u g ht h ei n t e r a c t i o no fi n d i v i d u a l si nap o p u l a t i o no fp a r t i c l e s ．T h er a p i ds p e e do fc a l c u l a t i o na n ds i m p l er e a li z a t i o na r ei t se x c e l l e n tp e r f o r m a n c e ．Am u l t i —o b j e c tc o m b i n a t o r i a lo p t i m a lp r o b l e m ———一g l a s s —b l o c kt y p e —s e t t i n go p t i m a lp r o b l e ms o l v e db yp a r t i c l es w a r mo p t i m i z a t i o ni ss t u d i e di nt h i sp a p e r ．T h ed a t ar e l a t e dw i t ht h i ss t u d yo nt h eo p t i m i z a t i o no fg l a s s —b l o c kt y p e s e t t i n gb a s e do nP S Oh a sn o tb e e nf o u n da th o m e ．T h eg l a s s —b l o c kt y p e s e t t i n go p t i m i z a t i o na l g o r i t h ma r ed e s i g n e da n dr e a l i z e di nt h i sp a p e r ．I no r d e rt ol e s s e nt h ed i f f i c u l t y ，t h em u l t i —o b j e c tp r o b l e mi sd i s a s s e m b l e di n t os e v e r a ls i n g l eo b j e c tp r o b l e m s ，a n dt h e s ep r o b l e m sa r es o l v e do n eb yo n eb ya p p l y i n gP S O ．I nt e r m so ft h ep a r t i c u l a r i t yo fe a c hp r o b i e r a , t h em o d i f i c a t i o ni sn e c e s s a r yo nP S O ．I nt h el a y o u tp r o b l e mo fg l a s s —b l o c kt y p e s e t t i n g ，w eu s et h es t r u c t u r eo fB * - - t r e et od e s c r i b et h er e l a t i o na m o n gt h eg l a s s —b l o c k sa n dt h ea s s e m b l i n gv a l u eb e t w e e nt w og l a s s —b l o c k st oc o n s t r u c tal a y o u tg r a d u a l l y ．I nt h eT S Po fg l a s s —b l o c kt y p e s e t t i n g ，w er e d e f i n et h ef o r m u l ao fP S Oi no r d e rt of i n dt h es h o r t e s tr o u t e ．T h er e s u l to ft h el a y o u tp r o b l e mh a sg r e a ti n f l u e n c et ot h a to ft h eT S P ．T h er a t i o n a ll a y o u ti sn o te x c l u s i v e ，a n dd i f f e r e n tl a y o u tw i l ll e a dd i f f e r e n tr e s u l to fT S P ．T h e r e f o r e ，t h eb e t t e rl a y o u ti sg a i n e d ，t h eb e t t e rr e s u l to fT S Pw ec a ng e t ．I nc h a p t e r1w ei n t r o d u c et h ew o r ko ft h ep a p e r ，i t sb a c k g r o u n da n dt h ep r o b l e mw ew i l ls o l v e ．I nc h a p t e r2w ei n t r o d u c e dP S Os y s t e m a t i c a l l y ，w h i c hi n c l u d et h ea l g o r i t h mb a c k g r o u n d ，t h et h e o r yo fP S Oa n db a s i cI I I四川大学硕士学位论文i m p l e m e n tt e c h n i q u e so fP S Oa n ds oo n ．I nc h a p t e r3w ed is c u s si nd e t a ilt h ed e s i g na n di m p l e m e n to fP S Ou s e dt os o l v et h el a y o u tp r o b l e mo fg l a s s —b l o c kt y p e s e t t i n g ．I nc h a p t e r4w ed i s c u s si nd e t a i lt h ed e s i g na n di m p l e m e n to fP S Ou s e dt os o l v et h eT S P ．A n dt h er e l a t i o n s h i pb e t w e e nl a y o u tp r o b l e ma n dT S Pi sa l S Od i s c u s s e d ．I nc h a p t e r5w es u m m a r i z et h i sp a p e r ．K e y w o r d s ：P a r t i c l eS w a r m0 p t i m i z a t i o nC o m b i n a t o r i a lo p t i m i z a t i o nB * - t r e es t r u c t u r eL a y o u tp r o b l e mT S PI V四J i l 大学硕士学位论文第一章绪论本章对玻璃排版问题的工作背景、目的、意义进行了简要的介绍，该问题涉及到的组合优化问题和粒子群算法也在本章中作了简要的介绍。

1 ．1 玻璃排版问题的工作背景玻璃是建筑施工中消耗的主要建材之一玻璃切割通常是在常规出厂玻璃底料幅面内对玻璃原片进行二次加工，即将矩形玻璃原片切割加工成各种规格的矩形玻璃产品玻璃切割机的软件控制系统由切割控制软件和玻璃排版软件两部分组成首先由玻璃排版软件在玻璃原片上根据玻璃产品的规格尺寸和数目进行排版，并对切割路径进行优化，形成切割加工的版图，再由该版图形成切割加工工艺流程切割机控制系统根据该工艺控制流程对切割机进行控制，将玻璃原片加工成所需的玻璃产品玻璃排版软件对玻璃原片进行排版，在玻璃切割机的电气控制系统与切割控制软件确定后，玻璃的排版就尤为重要了，因为玻璃的排版决定了加工过程的生产成本和工作效率由于玻璃底料的耗用量大，即使对玻璃底料的利用率仅有少量提高，都会对降低生产成本、提高经济效益产生极大的影响，所以随之出现了很多种优化算法，如线性规划、非线性规划、分支定界法、搜索法、启发式算法、及遗传算法等优化算法，以提高玻璃底料的利用率而本文所说的粒子群优化算法是一种较新的优化算法，由于其容易理解、易于实现，在许多优化问题中得到成功应用，所以，将粒子群算法应用于玻璃切割优化是很有意义的。

1 ．2 玻璃排版优化问题的提出本文所说的玻璃排版优化主要是指玻璃切割机对玻璃原片进行加工过程中玻璃排版环节的优化，即将矩形玻璃原片切割成各种规格的矩形玻璃产品，并四。