（控制理论与控制工程专业论文）粒子群优化算法在玻璃排版问题中的应用.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 t 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 ni sa ne v o l u t i o n a r y a 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 l r 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 s i 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 e r 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 d i 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 f g 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 e g 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 d i 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 s d 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 e s 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 h p 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 f g 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 e t 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 o g 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 k t 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 t r 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 f t 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 l l 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 d t 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 c i 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 il t 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 t p r o b l e mo f g 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 n a 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 n l 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 s p 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 n b * - t r e es t r u c t u r e l a y o u tp r o b l e m t s p i v 四j i l 大学硕士学位论文 第一章绪论 本章对玻璃排版问题的工作背景、目的、意义进行了简要的介绍，该问题 涉及到的组合优化问题和粒子群算法也在本章中作了简要的介绍。 1 1 玻璃排版问题的工作背景 玻璃是建筑施工中消耗的主要建材之一。玻璃切割通常是在常规出厂玻璃底 料幅面内对玻璃原片进行二次加工，即将矩形玻璃原片切割加工成各种规格的 矩形玻璃产品。玻璃切割机的软件控制系统由切割控制软件和玻璃排版软件两 部分组成。首先由玻璃排版软件在玻璃原片上根据玻璃产品的规格尺寸和数目 进行排版，并对切割路径进行优化，形成切割加工的版图，再由该版图形成切 割加工工艺流程。切割机控制系统根据该工艺控制流程对切割机进行控制，将 玻璃原片加工成所需的玻璃产品。 玻璃排版软件对玻璃原片进行排版，在玻璃切割机的电气控制系统与切割控 制软件确定后，玻璃的排版就尤为重要了，因为玻璃的排版决定了加工过程的 生产成本和工作效率。由于玻璃底料的耗用量大，即使对玻璃底料的利用率仅 有少量提高，都会对降低生产成本、提高经济效益产生极大的影响，所以随之 出现了很多种优化算法，如线性规划、非线性规划、分支定界法、搜索法、启 发式算法、及遗传算法等优化算法，以提高玻璃底料的利用率。而本文所说的 粒子群优化算法是一种较新的优化算法，由于其容易理解、易于实现，在许多 优化问题中得到成功应用，所以，将粒子群算法应用于玻璃切割优化是很有意 义的。 1 2 玻璃排版优化问题的提出 本文所说的玻璃排版优化主要是指玻璃切割机对玻璃原片进行加工过程中 玻璃排版环节的优化，即将矩形玻璃原片切割成各种规格的矩形玻璃产品，并 四川i 大学硕士学位论文 使原片的利用率最高及切割刀所走路径最短。鉴于此，本文将玻璃排版优化问 题分为两个优化目标：一、按玻璃原片的尺寸、各种所需玻璃规格的尺寸与需 求量，确定各种组合的排版方案，使玻璃原片的利用率最高。二、根据前者的 优化方案，找到一条最短的切割路径，按该路径进行切割，做到不重复切割， 且所走的路径最短，以加快切割速度。 从本质上来说，玻璃排版优化问题是一个多目标组合优化问题。所谓组合优 化是指在离散的、有限的数学结构上，寻找一个满足给定的约束条件并使其目 标函数达到最大或最小值的解【4 l 。一般来说，组合优化问题通常带有大量的局部 极值点，往往是不可微的、不连续的、多维的、有约束条件的、高度非线性的 n p c ( n o n d e t e r m i n i s t i cp o l y n o m i a lc o m p l e t e ) 问题，因此，精确地求解组合优 化问题的全局最优解是不可能的。由前面的分析，我们可以将玻璃排版问题分 为两个子问题，分别归属到两类典型的组合优化问题中：平面布局设计问题和 旅行商问题。玻璃布局排版的优化归属于平面布局设计问题，切割路径的优化 归属于旅行商问题。 1 3 粒子群优化算法技术 粒子群优化算法的基本思想来源于群智能的思想，并以鸟群捕食的过程作 为优化过程的模型。本文就是采用粒子群优化算法来解决玻璃排版问题中的两 个组合优化问题。 与各种各样的自适应随机搜索算法相比，演化计算技术创造了被称为“种 群”的潜在解，并通过种群问个体的协作与竞争来实现对问题最优解的搜寻【1 】， 这类方法往往能够比传统优化方法更快地发现复杂优化问题的最优解。群智能 ( s w a r mi n t e l l i g e n c e ) 作为一种薪兴的演化计算技术已成为越来越多研究者的 关注焦点，它与人工生命，特别是与进化策略以及遗传算法有着极为特殊的联 系 2 1 。群智能中的群体指的是“一组相互之间可以进行直接通信或者间接通信( 通 过改变局部环境) 的主体( a g e n t ) ，这组主体能够合作进行分布式的问题求解”， 而群智能则是指“无智能的主体通过合作表现出智能行为的特性”。群智能在 没有集中控制且不提供全局模型的前提下，为寻找复杂的分布式问题求解方案 2 四川大学硕士学位论文 提供了基础【3 】。 目前，在群体智能理论研究领域中，有两种基于群智能的算法，蚁群算法 ( a n tc o l o n yo p t i m i z a t i o n ) 和粒子群算法。d o r i g o 等从生物进化的机理中受到 启发，通过模拟蚂蚁群落食物采集过程，提出了蚁群优化方法，已经成功运用 在很多离散优化问题上。e b e r h a r t 和k e n n e d y 于1 9 9 5 年提出的粒子群优化算法 是基于对鸟群飞行的模拟，通过鸟之间的集体协作使群体达到目的1 5 】。其最初的 设想是模拟乌群觅食的过程，但后来发现p s o 也是一种很好的优化工具，于是得 到了快速的发展。通常单个自然生物并不是智能的，但是整个生物群体却表现 出处理复杂问题的能力，群体智能就是这些群体行为在人工智能问题中的应用。 p s o 算法作为一种新的随机化搜索、优化方法，近几年来在组合优化领域已 有较广泛的研究和应用，并显示出了良好的性能和效果。 1 4 本文所做的工作 1 对粒子群优化算法进行了介绍。包括基本粒子群优化算法的描述；与遗 传算法和b p 算法对神经网络的训练进行比较；改进的粒子群优化算法的描述； 粒子群算法的发展。 2 对玻璃排版问题进行了分析，将该问题分解为两个基本的组合优化问 题：平面布局问题和旅行商问题。 3 运用粒子群优化算法实现了玻璃排版问题中的平面布局问题。采用 b * - t r e e 结构来描述平面布局结构，并在此基础上提出了一种建立b * - t r e e 结构 布局的算法，将其应用于粒子群优化算法中以解决布局问题；提出了用于解决 平面布局问题的粒子群优化算法的新的描述：对该算法进行了试验，并得到了 较好的优化结果。 4 运用粒子群优化算法实现了玻璃排版问题中的旅行商问题。为了更好的 运用粒子群算法，采用了交换子和交换序的概念，并将其运用到优化算法中； 提出了用于解决旅行商问题的粒子群优化算法的新的描述。 5 对玻璃排版优化问题中的两个基本问题之间的关系和转换进行了分析和 实现。 四川大学硕士学位论文 第二章基本粒子群优化算法 本章介绍了粒子群算法的基本理论。主要有：基本粒子群算法、改进的基 本粒子群算法、与其他进化算法的比较和粒子群算法的发展。 2 1 粒子群优化算法的背景 粒子群优化算法( p s o ) 是由e b e r h a r t 和k e n n e d y 等【5 用于1 9 9 5 年提出的 一种进化计算算法，p s o 同遗传算法( g a ) 类似，是一种基于迭代的优化算法。 它是对鸟群觅食过程中迁徙和聚集的模拟，更确切的说是由简单个体组成的群 落与环境以及个体之间的互动行为。该模拟系统利用局部信息，从而可能产生 不可预测的群体行为。p s o 算法最直接的应用是函数优化问题，包括多元函数优 化、带约束优化问题f 7 】。a n g e l i n e 经过大量的实验研究发现【8 月1 ，粒子群优化算 法在解决一些典型函数优化问题时，能够取得比遗传算法更好的优化效果。这 就说明粒子群优化算法在解决很多实际问题时具有很好的应用前景，因为许多 实际问题都可以归结为函数优化问题。此外p s o 算法还在各种复杂的优化问题、 动态优化问题和多目标优化问题【1o l 中得到成功应用。例如，噪声和动态环境下 的优化问题【1 1 】、整数规划1 1 2 】、非线性规划【1 3 , 1 4 | 、神经网络训练【1 5 1 、模糊系统控 制以及其它遗传算法的应用领域。粒子群算法名称中的“群”来源于粒子群， 因为既要将群体中的成员描述为没有质量和没有体积，同时还需要描述它们的 速度和加速状态，因此选择了“粒子”这个单词来表示算法中的个体。 2 2 粒子群优化算法介绍 如上所述，p s o 算法来源于鸟群捕食的场景，因此，该算法的假设是无争 议的：在寻求一致的认知过程中，个体往往记住它们的自己的经验，同时考虑 同伴们的经验。当个体察觉同伴的经验较好的时候，它将进行适应性地调整。 如同鸟群的捕食行为；一群鸟在随机搜索食物，在这个区域里只有一块食物， 4 四川大学硕士学位论文 所有的鸟都不知道食物在哪里，但是通过某种感官它们知道当前的位置离食物 还有多远，那么找到食物的最简单有效的方法就是搜寻目前离食物最近的鸟的 周围区域。 p s o 算法从这种模型中得到启示并用于解决优化问题。在p s o 算法中，每个 优化问题的解都是搜索空间中的一只鸟，我们称之为“粒子”。所有的粒子都有 一个由被优化的函数决定的适应值( f i t n e s sv a l u e ) ，每个粒子还有一个速度决 定他们飞翔的方向和距离，然后粒子们就追随当前的最优粒子在解空间中搜索。 p s o 算法初始化为一群随机粒子( 随机解) ，然后通过迭代逐步找到最优解。在每 一次迭代中，粒子通过跟踪两个“极值”来更新自己。第一个就是粒子本身所 找到的最优解，这个解叫做个体极值p 6 e s t ；另一个极值是整个种群目前找到的 最优解，这个极值是全局极值g b e s t 。实际操作中，通过由优化问题所决定的适 应度值来评价粒子的“好坏”程度，每个粒子都通过上述两个极值不断更新自 己，从而产生新一代群体，即每个粒子根据如下3 条原则来更新自身状态： ( 1 ) 保持自身惯性； ( 2 ) 按自身的最优位置来改变状态； ( 3 ) 按群体的最优位置来改变状态。 2 ，2 1 基本粒子群优化算法的数学描述 在p s o 算法中，每个粒子可以看作是解空间中的一个点。假设粒子的群体 规模为，则第i ( i = 1 , 2 ，) 个粒子的位置可表示为置，它是优化问题的一个 潜在解，将它带入优化目标函数可以计算出相应的适应值，根据适应值可衡量 石，的优劣。每个粒子经历过的“最好”位置称为个体历史最好位置，记为 p b e s t i 】，它的飞行速度用k 表示。整个群体中“最好”粒子的位置称为全局历 史最好位置，用g b e s t 表示。在每一次迭代中，所有的粒子在d 维空间中移动以 搜索全局最优解。粒子f 将根据下面的公式来更新自己的速度和位置1 1 e , 1 7 ： 一”1 = 一+ c 1 r a n d l o ( p b e s t i 一x 。) - i - c 2x r a n d 2 0 x ( g b e s t 一置) ； ( 2 1 ) 四川大学硕十学位论文 置= 置+ k “1 ；( 2 2 ) 其中f = 1 , 2 ，为粒子群中粒子的个数，t 表示迭代次数。 和k “1 分别表示第f 个粒子的当前速度向量和修正后的速度向量；x 。和 彳。“1 分别为第f 个粒子的当前位置向量和修正后的位置向量； k = 。，k ：， x i = x x ，x l d 、 2 2 2 参数分析 公式( 2 1 ) 中6 ，c 2 为加速系数，又称为学习因子；r a n d l o 和r a n d 2 0 是两个 在 0 ，1 范围内变化的随机数。 1 加速系数 q ，c ：对粒子群算法的收敛速度影响颇大，合适的加速系数有利于算法较快 收敛和脱离局部极值。它们代表将每个粒子推向其个体历史最好位置和全局历 史最好位置的统计加速项的权值。低的加速系数值允许粒子在被拉回之前可以 在目标区域外徘徊，而高的加速系数值则可能导致粒子突然地冲向或越过目标 区域。 在公式( 2 1 ) 中，若c l = c 2 = 0 ，粒子将一直以当前的速度惯性飞行，直到到 达边界；由于它只能搜索有限的区域，所以很难找到最好解。若c l = 0 ，则粒子 没有认知能力，只有社会部分，所以c 2 又称为社会参数；此时收敛速度比基本 粒子群算法快，但对复杂问题，则比基本粒子群算法容易陷入局部极值，若 q = 0 ，则粒子之间没有社会信息共享，只有认知部分，所以q 又称为认知参数； 此时个体间没有交互，一个规模为 ，的群体等价于个单个粒子的运行，得到 最好解的机率非常小。 通常，c l = c 2 = 2 。也有实验结果显示，当c l = c 2 = 0 2 时能取得更好的效 果。最近一些研究【3 】还表明认知参数q 选择的大些而社会参数q 选择的小些， 但c l + c 2 4 时能得到更好的结果。 2 随机数r a n d , 0 和r a n d ，0 这两个随机数可以保证粒子群体的多样性和搜索的随机性。由于它的随机 6 四川大学硕士学位论文 性，需要设置速度的限值。最大最小速度可以决定当前位置与最好位置之间区 域的分辨率( 或精度) 。如果最大速度太高或最小速度太低，粒子可能会飞过好 解；如果最大速度太小或最小速度太大，则粒子不能在局部最好区间之外进行 足够的探索，导致陷入局部极值。该限制的耳的主要是防止计算溢出，改善搜 索效率和提高搜索精度。 整个p s 0 算法公式由三部分组成，第一部分是粒子先前的速度，说明了粒 子目前的状态，起到了平衡全局和局部搜索的能力；第二部分是认知部分，表 示粒子本生的思考，即一个得到加强的随机行为在将来更有可能出现，使粒子 有了足够强的全局搜索能力，避免局部极小；第三部分为社会部分，体现了粒 子间的信息共享与相互合作，当观察者观察到一个模型在加强某一行为时，将 增加它实行该行为的几率，即粒子本生的认知将被其他粒子所模仿。在这三个 部分共同作用下粒子才能有效的到达最好位置。 2 2 3 改进的基本粒子群优化算法 在前面所述的基本粒子群优化算法的迭代公式( 2 1 ) 中，第一项k 。表示粒 子前一速度对下一速度的影响，故巧的大小对粒子的搜索范围及能力都有一定 的影响。文献 1 8 中的作者对( 2 1 ) 式作了如下修改： k “1 = 彩k + c 1 r a n d l o x ( p b e s t i 一置) + c ，r a n d ，o ( g b e s t 一x 1 ) ； ( 2 3 ) 即在公式( 2 1 ) 中加入了惯性权重国，它为非负数，控制着前一速度对当前 速度的影响。如果较大，则前一速度影响较大，能够搜索以前未能达到的区 域，使得整个算法的全局搜索能力加强；若国较小，则前一速度的影响较小， 主要是在当前解附近搜索，使得局部搜索能力加强，有利于算法收敛和提高搜 索精度。最初版本的粒子群优化算法中，为常数。后来，有人提出了彩的自 适应调整策略，刚开始时较大，随着迭代的进行，0 3 线性减小【1 9 l 。又有人认 为刚开始国= 1 4 ，然后逐步减d , n 国= o 3 5 比较合适刚。通常计算开始时k 项 系数取值较大，随着符合度的增大而减小，从而逐步加强局部搜索能力。文献 7 四”f 大学硕士学位论文 2 1 描述了一种带收敛因子的粒子群优化算法，其位置和速度更新等式如下所 示： v t “= z 哦+ q x r a n a i o x ( p b e s t i 一x 、 4 - c 2xr a n d 2 0 ( g b e s t x i ” ( 2 4 ) 1 其中，z = 二亍，为收敛因子，伊= c l + c 2 4 。通常取伊为4 1 ， i2 一伊一、妒一4 妒 则z = 0 7 2 9 。 类似惯性权值，收敛因子可以改善算法的收敛性，使用收敛因子的粒子群 优化算法有更快的收敛速度。实验结果表明【2 刃，在没有最大速度限时，带收敛 因子的p s o 算法比不带收敛因子的p s o 算法具有更好的性能。其实只要恰当地选 取国、q 和q 的值，两种算法是一样的，因此带收敛因子的粒子群优化算法可 被看作带惯性权重的算法的一个特例。同时这也说明，恰当地选择算法的参数 值可以改善算法的性能。 如上所述，惯性权重在优化算法向全局最优值的收敛过程中扮演了很重要 角色，用它来控制前一速度对下一速度的影响以及局部和全局的搜索能力【2 孓2 5 1 。 一般来说，基于群的优化算法在优化的初始阶段，都希望激励个体去搜索整个 搜索空间，而不是聚集在局部最优值附近；另一方面，在优化的后期阶段，提 高向全局最优值的收敛性，有效找到最优解是十分重要的【2 q 。大的惯性权重能 够使粒子在全局范围内搜索，而小的惯性权重能使粒子在局部范围内搜索。 2 2 4 基本粒子群优化算法的基本操作流程 基本p s o 的流程可以描述为： 1 初始化设置粒子群的规模、惯性权值、加速系数、最大允许迭代次数或 适应值误差限，各微粒的初始位置和初始速度等。 2 按目标函数评价各粒子的初始适应值。 3 根据公式( 2 3 ) 计算各粒子新的速度，并对各粒子新的速度进行限幅处 8 四川大学硕士学位论文 理。 4 根据公式( 2 2 ) 计算各粒子新的位置，并对各粒子新的位置进行限幅处 理。 5 按目标函数重新评价各粒子的适应值。 6 对每个粒子，比较其当前适应值和其个体历史最好适应值，若当前适应 值更优，则令当前适应值为其个体历史最好适应值，并保存当前位置为其个体 历史最好位置。 7 比较群体所有粒子的当前适应值和全局历史最好适应值，若某粒子的当 前适应值更优，则令该粒子的当前适应值为全局历史最好适应值，并保存该粒 子的当前位置为全局历史最好位置。 8 若满足停止条件( 适应值误差达到设定的适应值误差限或迭代次数超过 最大允许迭代次数) ，搜索停止，输出搜索结果。否则，返回3 继续搜索。 其程序流程如图2 1 。 2 2 5 基本粒子群优化算法的程序伪代码 粒子群算法实现的伪代码如下： f o re a c hp a r t i c l e i n i t i a l i z ep a r t i c l e e n d d o j o r e a c hp a r t i c l e c a l c u l a t ef it n e s sv a l u e i f t h ef i t n e s sv a l u ei sb e t t e rt h a nt h eb e s tf i t n e s sv a l u e ( p b e s t ) i nh i s t o r y e n d c h o o s et h ep a r t i c l ew i t ht h eb e s tf i t n e s sv a l u eo fa l l t h e p a r t i c l e sa st h eg b e s t 9 四”i 大学硕十学位论文 群体初始化 上 - t 计算适应度函数 否 否 更新g b e s t 0 更新糙子i 的位置和速度f - 输出最优解 图2 1 粒子群优化算法程序流 1 0 四川大学颂士学位论文 f o re a c hp a r t i c l e c a l c u l a t ep a r t i c l ev e l o c i t ya c c o r d i n ge q u a t i o n ( 2 3 ) 1 i p d a t ep a r t i c l ep o s i t i o na c c o r d i n ge q u a t i o n ( 2 2 ) e n d w h il em a x i m u mit e r a ti o n so rm i n i m u me r r o rc r i t e r i ai sn o ta t t a i n e d 2 3 粒子群算法与其它优化算法的比较 2 3 1p s o 和遗传算法的比较 遗传算法( g e n e t i ca l g o r i t h m - - g a ) 自上世纪7 0 年代正式提出已成为比 较成熟的进化算法。g a 是建立在生物自然选择和群体遗传学原理基础上的随机、 迭代、进化的搜索方法，算法的主要步骤为：( 1 ) 编码；( 2 ) 初始化群体；( 3 ) 适 应性评价；( 4 ) 选择操作；( 5 ) 交叉操作；( 6 ) 变异。g a 有相应的数学理论，其操 作主要通过种群整体共享并控制3 个典型的算子来实现。最终形成在时间上父 代到子代到孙代等的搜索。种群收敛慢，较均匀地向最优区域移动。g a 应用极 其广泛，目前已经渗透到通信、电子学、交通、工程结构优化、计算数学、航 空航天、制造系统、计算机科学等等很多学科。 p s o 算法与遗传算法( g e n e t i ca l g o r i t h m ，g a ) 有许多相似之处：都是从 多个初始点开始的并行随机搜索，搜索时对目标函数、传递函数都没有求导要 求，应用范围都很广，应用方式都很灵活。但两者也有明显的区别：搜索时p s o 是依据自己的搜索经验和同伴的搜索经验，采用全局搜索和局部搜索相结合的 搜索模式得到粒子下一个位置；而g a 算法是采用优势个体的选择、交叉、变异 的方式产生下一代。在计算时，g a 算法有编码、解码、选择、交叉和变异等操 作；而p s o 算法没有遗传操作，它是通过对速度与位置的修改来完成的，粒子 的位置也不像g a 算法那样由于受到编码的限制而不够灵活。迭代时，g a 算法 受适应值的绝对大小影响很大，而p s o 算法只需比较适应值的大小，与适应值 的绝对大小无关。粒子还有一个重要的特点，就是有记忆。与遗传算法比较，p s o 算法的信息共享机制是很不同的。在g a 算法中，染色体( c h r o m o s o m e s ) 互相 阳川大学硕士学位论丈 共享信息，所以整个种群的移动足比较均匀的向最优区域移动。在p s o 算法中， 只有局部最优或全局最优将信息给其他的粒子，这是单向的信息流动，整个搜 索更新过程是跟随当前最优解的过程，与g a 算法比较，在大多数的情况下，粒 子可能更快的收敛于最优解。 2 3 2p s o 与b p 算法对神经网络训练的比较 p s o 算法在对神经网络( n n ) 训练方面的应用也是非常有潜力的，它操作简 单，可以方便地调节神经网络的连接权值和阈值，目前已被成功地用来解决许 多实际问题。如：基于p s o 的神经网络应用于医疗诊断【鲫，分析人的颤抖。利用 p s o 讨i i 练积单元神经网络，来预测噪声环境的混沌时间序列【3 1 】，都得到了很好的 效果。 b p ( b a c kp r o p a g a t i o n ) 算法是一种反向传播算法，在神经网络训练方面已 获得广泛应用，它在训练神经网络时，是利用单一初始值，以梯度下降模式进 行；而p s o 在训练神经网络时是以一群粒子，即很多个初始值采用依据自己的经 验结合群体的经验，有导向的随机搜索模式进行，因此，p s o 陷入局部极值的概 率大大降低。此外，b p 算法在训练神经网络时，需要较复杂的求导计算，导致它 对目标函数、传递函数都有要求( 要求可求导) ，隐含层层数也不宜过多。而 p s o 算法在训练神经网络时，无需求导计算，因而对神经网络的层数、目标函数 和神经元的传递函数等部没有限制，应用更为灵活方便。 2 4 粒子群优化算法的现状和发展 由于认识到粒子群优化算法在函数优化等领域有广阔的应用前景，p s o 算法 自提出以来，引起了国际上相关领域众多学者的关注和研究，成为国际演化计 算界研究的热点。目前，其研究现状大致分为两个方向：算法的改进，算法的 应用。 四川大学硕士学位论文 2 4 1 粒子群优化算法的改进 由于粒子群算法提出的时间不长，算法缺乏深刻的、具有普遍意义的理论 分析，其数学基础相对薄弱，且存在许多不完善和末涉及到的问题，因此，迄 今已经出现了很多对粒子群优化算法的改进方法。下面介绍几种较新的算法改 进方法： i 混合p s o ( h p s o ) 算法 h n g e l i n e 于1 9 9 8 年提出采用进化计算中的选择操作的改进型p s o 算法，成为 混合p s o ( h p s o ) 1 2 8 , 3 2 1 。在a n g e l i n e 的h p s o 模型中，将每次迭代产生的新的微粒群 根据适应函数进行选择，用适应度高的一半微粒的位置和速度取代适应度低的 一半微粒的位置和速度，并保持后者个体极值不变。h p s o 提高了收敛速度并保 持了一定的全局收敛能力，在大多数的函数优化结果上比p s o 算法更好。不过， 它在解决超高维、非线性、多局部极值的复杂性优化问题时有些力不从心。 2 杂交p s o 算法 借鉴遗传算法的思想，文献 3 3 最早提出了杂交p s o 算法的概念。文献 3 4 进一步提出了具有繁殖和子群的算法。粒子群中的粒子被赋予一个杂交概率， 这个杂交概率是用户自己确定的，与粒子的适应值无关。在每次迭代中，依据 杂交概率选取指定数量的粒子放入一个池中。池中的粒子随机地两两杂交，产 生同样数目的子代粒子，并用子代粒子代替父代粒子。从而保持种群的粒子数 目不变，子代粒子的位置由父代粒子的位置决定。对于局部版的p s o 算法而言， 相当于在一个种群中划分了若干个子群。因此，杂交操作既可以在同一子群内 部进行，也可以选择在不同的子群之间进行。实验结果显示，p s o 杂交算法的收 敛速度比较快，搜索精度也相对比较高，对一些非线性优化问题可以很好的解 决。但因为引用的待调整参数较多，导致仿真的次数增多，工作量加大，所以 对使用者的经验有一定要求。 3 协同p s o 算法 协同p s o 算法的基本思想是：用个相互独立的粒子群分别在d 维的目标搜 索空间中的不同维度方向上进行搜索3 6 l 。其具体做法是：选定划分因子和 粒子群的粒子数m ，将输入的d 维向量( 粒子的速度和位置向量) 划分到个粒 子群。前d m o d n 个粒子群，其粒子的位置和速度都是d 维的；后k 一( d m o _ l v ) 四川大学硕士学位论文 个粒子群，其粒子的位置和速度向量也是d | 维的。在每一步迭代中，这个 粒子群相互独立地进行状态更新，粒子群之间不共享信息。计算适应值时，将 每个粒子群中最优粒子的位置向量拼接起来，组成d 维向量并代入适应函数计 算适应值。此算法在迭代初期，适应值下降缓慢( 收敛速度缓慢) 。且其收敛速 度与种群所含粒子数目成反比。但由于协同p s o 算法采用的是局部学习策略，因 此比基本p s o 算法更容易跳出局部极值，从而达到较高的收敛精度。 4 基于模拟退火的p s o 算法 该算法把模拟退火算法思想引入到粒子群算法中，结合了粒子群优化算法 具有的全局寻优能力，以及计算速度快，实现简单的优点。也结合了模拟退火 算法所具有的较强的跳出局部最优解的能力。从而避免了粒子群算法容易陷入 局部极值点的缺点，提高了粒子群算法进化后期的收敛速度f 3 丌。 5 自适应变异的p s o 算法 自适应变异的p s o 算法【3 8 1 是在基本p s o 的进化过程中增加了随机变异算子， 在进化过程中，根据群体适应度方差以及当前最优解的大小来确定当前最优粒 子的变异概率。变异操作增强了粒子群优化算法跳出局部最优解的能力。从而 提高了全局搜索能力，并且能够有效避免早熟收敛的问题。 除此之外，还有很多有关粒子群算法的改进方法，例如，离散p s 俨”、自 适应p s o l 2 9 、耗散的p s o 、g a p s d 3 9 1 等多种粒子群优化算法。如何利用有效的数 学工具对算法的收敛性，收敛速度的估计，计算的复杂性，以及预防陷入局部 最优和参数设置影响等进行分析将是今后的研究热点之一。 2 4 2 粒子群优化算法的应用 由于p s o 算法概念简单，易于实现，因而在短期内得到很大发展，迅速得到 了国际演化计算研究领域的认可，并在很多领域得到应用，主要有以下几个方 面： 1 神经元网络训练 文献 4 0 利用p s o 算法来训练神经元网络；文献 3 9 将遗传算法与p s o 算法 结合来设计递归模糊神经元网络；应用结果均显示利用p s o 算法设计神经元网 络是一种快速、高效并具有潜力的方法。 1 4 四j i l 大学硕士学位论文 2 化工系统领域 文献 4 1 利用p s o 算法求解苯乙烯聚合反应的最优稳态操作条件，p s o 算法 有效地解决了该m 0 问题，同时获得了最大的转化率和最小的聚合体分散性；文 献 4 2 使用p s o 算法来估计在化工动态模型中产生不同动态现象( 例如周期振 荡，双周期振荡，混沌等) 的参数区域，仿真结果显示p s o 提高了传统动态分叉 分析的速度。 3 电力系统领域 文献 4 3 】将智f l e p s o 算法应用于电磁场的优化分析；文献 4 4 将p s o 算法用 于多机电力系统稳定器的优化设计；文献 4 5 将交叉p s o 算法用于电力分布系统 电压、电流及负载的状态分布预测和状态值估计；文献 4 6 使用p s o 对一个电气 设备的反馈功率和电压进行控制；文献 4 7 将p s o 算法用于电力系统负荷模型的 参数辨识，这些应用都取得好的效果。 4 电机和机械设计 文献 4 8 将p s o 算法用于机械结构设计中尺寸和形状的优化设计，得到比遗 传算法和梯度下降算法更好的效果。文献 4 9 采用p s o 算法对粗轧宽展控制模型 进行优化结果表明优化后的模型效果明显优于原来的模型，体现了p s o 算法在优 化领域的优越性。文献 5 0 将p s o 算法应用于发电机参数辨识，提出了一种同步 发电机参数辨识的计算框架，结果表明这种参数辨识算法简单实用，具有可行 性。 标准粒子群算法主要适用于连续空间函数的优化问题，如何将算法应用于 离散空间的优化问题，特别是非数值优化问题，将是粒子群算法的主要研究方 向。此外，充分利用其他进化算法以改善微粒群算法存在的不足，也是值得研 究的问题。 四川大学硕士学位论文 第三章粒子群优化算法解决玻璃排版中平面布局问题 玻璃排版中的布局问题是指将待切的玻璃模块合理的分布在玻璃原片上， 使得玻璃原片的利用率达到最大。本章针对玻璃排版问题中的平面布局问题， 使用粒子群算法作为布局优化算法，并在算法中提出了一种基于b 一t r e e 结构 的算法，依此算法来逐步建立一个合理的布局方案，解决玻璃排版平面布局问 题。 3 1 平面布局问题描述 布局问题就是要把一些物体按一定的要求合理地放置在一个空间内，称物 体为布局物体( 或布局块) ，空间为布局容器。从布局问题的上述定义可以看出： 它是由布局容器、布局物体及其相互之间的关系和要求组成的。这些关系、要 求都可认为是布局的约束。当所有的布局约束都被满足时，布局问题才算得到 解决。布局问题求解过程是对问题不断细化求精的层次迭代。布局问题广泛应 用于生产设备的配置、办公环境的整合、用料问题和芯片设计等中。 玻璃排版问题中的平面布局问题根据工程要求在一定的平面空间内如何达 到平面模块的最优化组合问题。本文中待布的模块为长方形玻璃模块，对布局 问题的研究仅限于使布局模块如何组合才能使其玻璃原料的利用率最高。目前 已有很多种算法实现了平面布局问题的优化，如线性非线性规划方法、启发式 算法、遗传算法、蚁群算法等等，但是利用粒子群优化算法来解决这类平面布 局问题到目前为止还没有人提出，本文首次将粒子群优化算法运用到平面布局 问题中，并得到了较好的优化效果。 平面布局问题也是是n p c 问题1 5 1 1 ，它的实质是一个二维布局问题，至今还 没有找到解决该问题的有效的多项式的算法。寻求其近似最优解的近似算法是 目前解决该问题的途径之一。 1 6 四川大学硕士学位论文 3 1 1 玻璃排版中布局问题的结构描述 平面布局问题属于切割和装填类问题，即把一组任意大小的长方形模块按 一定的位置摆放到坐标之内，这些模块根据实际要求进行翻转，且在相互之间 不覆盖的条件之下使得这些模块布局面积利用率最大。平面布局的一个基本问 题是布局模块间几何关系的描述，即布局结构表征模型，而描述方法在很大程 度上将影响模块的操作和布局过程中的复杂性。所