（计算机软件与理论专业论文）基于改进遗传量子算法的最小权三角剖分.pdf

中山大学硕士学位论文 摘要 基于改进遗传量子算法的最小权三角剖分 计算机软件与理论 硕士生：林育蓓 指导教师：王若梅副教授 摘要 平面上有限点集的三角剖分在数值逼近，有限元方法，数值分析，计算机 辅助几何设计，计算机图形学，计算机视觉，机器人技术等方面都扮演着重要 的角色。而平面上有限点集的最小权三角剖分( m w n 问题在计算几何领域中是 一个开放性的难题。 在学术界已公认传统的贪心算法和d c l 孤姐v 算法得到的三角剖分不是最 小权三角剖分的前提下，本文深入分析了基于传统遗传算法的最小权三角剖分 的缺陷，介绍了目前非常流行的遗传算法领域的一个新的分支遗传量子算 法，并将这种具有很强的勘探和开采能力的算法创新地引入到求解最小权三角 剖分问题当中，提出了新的三角剖分编码方式和新的量子“点权”的概念，利 用点权将量子位编码与三角剖分联系起来，并根据具体的闯题对遗传量子算法 提出了系列的改进措旋：由于遗传量子算法的固定初始化模式极易导致早熟 收敛，本文摒弃了这一做法，提出了新的随机初始化染色体量子位的思想；舍 弃了每代最优个体保留策略而提出了用全局最优个体保留策略作为量子位进化 的依据，从而有效地使算法逃脱局部极值。 最后，通过大量的算例测试，证明了该算法与传统遗传算法相比，所需确 定的参数更少，具有更强的全局寻优能力，大大缩小了种群规模而提高了收敛 速度，提高了最优解的命中率，并能得到比著名的贪心算法更优的结果。 关键词：最小权三角剖分、遗传算法、遗传量子算法 中山大学硕士学位论文 a b s r r c r m i n i r 吣mw e i g h tt r i a n g u l a t i o nb a s e do ni i i l p r o v e dg e n e t i cq u a n t u ma 1 9 0 r i t h m c o m p u t e rs o f t w a r ea n dt h e o r y n a e ：y u b e il i n s u p e r v i s o r ： a s s o c i a t ep r o f e s s o rr u o m e iw a n g a b s t r a c t t r i a n g u l a t i o np l a y sav c r yi m p o n a n ti o l ej n 衄m e f i c a l 印p m a 也丘n i t e - e l e m e m a p p r o a c h ，肌m e r i c a la n a l y s 远c o l l l p u t c | a i d c dg c o m e t r i cd c s i g n ，c o m p u t e rg r a p h i c ， c o n 币u t e rv 豇i o n ，r o b o t t e c h i o g ya ds oo n t h em i n i m u mw c i g h tt r j a n g u l a t i o n ( m 、向rs h o n ) ，i w l i i c ht h eo b j c c t i v ei sl om m i m i 黯t l l ew e i g h to ft r i a n g l l l a t i o no f as c to fp l a n 缸p 0 洫s ，i so o ft h co p c np f o b l e m si nc o 即u t a t i 0 1 l a lg e d i n e 蚵 r e s c a r c h 丘e l d i th a sh e np r o v e dt h a tn e j n l c rt h cg r e e d y 嫡a l 塔u l a t 如n o rt h ei ) e l a u n a y l r i a n g u l a t i d na p p f o x i 瑚t e s 耋h eo p t i n m m 。a f i c rd i v i i 毽i n t ot h cp m l ，b mo fm 婀 b 黯e do nt r a d i t i o n a lg c n e t i ca l p r i t h l n sa n da m l y z i n gt h cd c f i c i c n c i c so ft h c m ，t h e d j s r t a t i o np r e 踮n t st h cv c r yp o p u l a rg c n c t i cq u a n l u ma 培。血h l n a san e wb 碍c h o f g e 鹏t i ca l g o f i t h n 强，i th a sv e r yp o w e r f u lc 印a b i l i t yo fe 砷l o f a t b na n de x p l o i t a t i o n 1 1 圮nan o v e ia i g o r i t h mb a d0 ni t 如rt h cp r o b i e mo fm 、ti sd e v e l o p e d n c w e i 脚幽唱m e c h a 】1 i s m 如r 啊柚g u l a t 主d nj sp e s e n t c d a no 啦血a l 。o n c e p td fp o i n t w 毫i g h li sp m p o s e da du s c dt ob eal i i l l 【b e t w e e nt h cq u b i t sa n dt h cc a n d i d a t c t r i a n g l l h t i o n s m e a w h 丑c ，t l 把g e n c t i cq u 锄t u ma l g or i t ：h n l 缸i m p r o v c ds p e c i a l l yf o r t h cp r o b k mo fm w t _ 1 1 1 cm c h i n e d 瑚d es t r a l e g y0 fc h r o n 姗m e 血i t i a l i z a t i o n ， w h i c he a s i l yl e a d st op 砌m t l l r ec o n v e r g c n c c ，i sd i s c a r d c d 柚df c p l a c c db yt h cn e w s t r 缸c g yo ff a n d o mi 血i a l i z a t i o n 1 1 h cg l o b a h yb c s t l u t i c m 面s t e a do ft h cb c s t l u t i o o f e a c hg e n e r a t i o ni sr e s e r v e dt ob et h e 如u n d a t i o no f t h cq u b i t sc v o l i i t i o ns o a st 0e s c a p e t h c1 0 c a lo p t i n m m e v c n t u a y e x p e r i m e n t a l r c s u n sa r ed e n 踟s t 功t c d i 西p m v c dt h a l i n p 盯e d w i t ht h ct r a d j t i o m l g c n c t i ca i g 嘞b m ， t i l ci 删c d g e 舱t i cq u a n t u m a l g o r i t b m ( i g q a 如rs h o n ) f o r t h cp m b l e mo fm 、n h a s 删c hs t r o n g e rc 叩a b 丑i t yo f s e a r c | l j l l gt h eg 】o b a lo p t j i n u ma n dr a p i d e rc o n v c f g 如c e 。k s sp 甜a 端t c r sn e e dt ob c a s c c n a i l l e da n ds m a l l e rp o p u h t j o ns i z ca n dk s si t e r a t i o nc a nn l a k ct h ca l g o f i t l l l l l r c a c h 岫o p t j l n u m 确ef c s u ha j s os h o wf h a tt b ei g q a 铷l 妯c f e 舔et 1 1 cp r o b a b j 】i l y o fh i t t i n gt h eo p t i m u ma n dg e t 锄p c r i o rr e s u n st h a nt h o w h i c hc o m c 丘o mt h e w e - h i o w ng r c c d ya l g o r i t h l l l 中山大学硕士学位论文a b s t r a c t k e yw o r d s ：m i l l i m u mw b 遥皿t r i 柚g l l h t i o n ，g e n e t i ca 1 9 0 r i t h n l g e n e 啦q u a m u m a l g o r i t h m m 中山大学硕士学位论文 引言 引言 在计算机图形学、科学计算可视化、自然科学、地学领域等，经常需要处 理大量分布于某一区域内的离散数据。由于这些数据分布的不均匀性，就产生 了一个如何合理有效地利用这些宝贵数据的问题。有限元法广泛应用于解决这 些问题。由于三角形有描述方便、处理简单等特性，适用于对复杂区域简化处 理，因此三角形单元在有限元分析中被广泛采用。三角剖分是计算几何领域的 主要课题之，并具有广泛的应用前景。而最小权三角剖分作为这一领域中的 一个公开的难题，一直以来吸引了不少专家学者去探索和研究。 传统的贪心算法和d e l a u n a y 算法曾被认为是求解最小权三角剖分的最好 办法，遗憾的是这一结果后来被推翻了。在最小权三角剖分问题陷入了危机之 际，遗传算法被引入了这一领域。然而，传统遗传算法存在不少缺陷种群 大，进化次数多，待定参数多，早熟收敛等等，这些缺陷导致基于传统遗传算 法的最小权三角剖分求解时间长，权值易陷入局部极值，待定参数确定困难。 针对这些问题，本文首度将量子进化思想引入最小权三角剖分领域，并提出了 新的“点权”概念，新的三角剖分编码机制和两个优化算法的策略。 在我们研究的国家自然科学基金课题三维服装动力模型研究( 编号： 6 0 2 7 3 0 6 3 ) 中，三角剖分是一个基础的研究部分。在对穿衣人体进行受力分析 研究时，必须先对其进行离散化。离散化过程中应用了三角剖分技术。因此， 保证三角剖分的质量与算法的速度尤为重要。本文研究的算法对更好地解决有 限元方法的二维和三维点集的网格生成也会起到一定的启发作用。 本文的结构安排如下：第1 章介绍三角剖分的概念及属性，并描述了这一 领域的两种著名的三角剖分方法，以及最小权三角剖分的定义、应用、研究现 状和发展趋势，由此引出了本文的研究内容。第2 章具体描述了遗传算法的基 本原理，概括了这种算法的特点和不足之处，并分析了基于传统遗传算法的最 小权三角剖分的缺陷。第3 章阐述了遗传量子算法的各重要组成要素量子 位表示法，染色体状态表示法和量子遗传操作，接着进一步介绍了基于这些要 素的算法结构流程，这一章的最后讨论了算法的收敛性和特点。第4 章提出了 解决最小权三角剖分问题的改进遗传量子算法，阐述了这种算法的改进之处和 结合最小权三角剖分问题的具体实现，包括三角剖分的编码机制，适应值评价 函数，点权与染色体量子位之间的映射和点权构造三角剖分的方法，提出了两 个优化算法的策略随机初始化染色体策略和全局最优个体保留策略，最后 阐述了算法流程。第5 章介绍基于改进遗传量子算法的最小权三角剖分在实现 过程中的参数选取，并根据实验结果分析了算法的性能。 中山大学硕士学位论文第l 章绪论 第1 章绪论 在c a d c a m 、计算机图形学、有限元分析等领域中，经常要处理这样的问 题：给定空间中的一组散乱数据，首先要在肋l ，平面上对其进行三角剖分，然 后在三角域上构造插值曲面，最后以插值曲面为基础进行各种分析、计算及其 他处理。因此平面点集上的三角剖分是一个值得研究的基本问题。为简单起见， 本文假定平面点集中不存在三点共线的情况。 1 - 1 三角剖分的相关概念及属性 1 1 1 相交 与一般意义上的直线段相交不同，本文定义“相交”为：如果平面上的两 条直线段有且只有在非端点处有公共点，则认为这两条直线段是相交的。 1 1 2 三角剖分( t r i a n g u l a t i o n ) 三角剖分是指在多项式时间内将欧几里德平面上的有穷点集连成三角形， 使得任何两条边不在非端点处相交。对于给定的平面上有限点集p ，三角剖分 是以该点集中的点为端点的非相交线段的最大集，记为丁( 尸) 。 1 1 3 凸包( c o n v e xh u l l ) 点集p 的凸包是指一个最小凸多边形，满足p 中的点或者在此多边形边上， 或者在此多边形边内，记为c h ( p ) 。 p 的三角剖分将p 的凸包内部分成若干个三角片。例如，图l 一1 是平面上 一个点集大小为l o 的三角剖分ap l p p ：p ，p ，p ，( 按逆时针的顺序) 为这个点集 的凸包( 图卜2 所示) 。 2 中山大学硕士学位论文第l 章绪论 5 图卜l 平面上一点集的三角剖分 图卜2 平面上一点集和它的凸包 对于给定平面上的有限点集p ，如果它有多于3 个点，则它的三角剖分不 中山大学硕士学位论文 第l 章绪论 是唯一的。但是，无论如何进行剖分，剖分出来的结果都满足以下两个属性： c h 妒) r ( p ) ( 卜1 ) i t ( p i = 3 0 1 ) 一l c h ( p ) i ( 卜2 ) 其中，阁表示集合s 的基数。 1 2 两种著名的三角剖分 由于一个基数大于3 的点集的三角剖分不是唯一的，这就产生了一个问题 如何寻找一个最优的三角剖分。穷举所有可能的情况并进行比较当然是一 个解决问题的办法，但是这个办法需要消耗太多时间了，即时”非常小。为了 解决这个问题，国内外不少专家学者做了大量的研究工作，并得到了令人瞩目 的研究成果，当中包括两种著名的三角剖分方法一基于贪心算法的三角剖分 ( g t ) “1 和d e l a u n a y 三角剖分( d t ) “1 。 1 2 1 基于贪心算法的三角剖分( g r e e d yt r i a n g u l a t i o n ) 基于贪心算法的三角剖分是先把点集p 的完全图中的c ：条边按其欧几里 德长度的升序排列，再往初始为空的边集合逐条加入最短的且与已加入的边不 相交的边，直至这个边集合构成一个三角剖分。 1 2 2d e l a u n a y 三角音0 分( d e l a u n a yt r i a n g u l a t i o n ) 对于给定平面上的点集p ，尽管有多种方法实现点集p 的三角剖分，但是 俄国数学家d e l a u n a y 在1 9 3 4 年证明了：必定存在且仅存在一种剖分( 一般称 之为d e l a u n a y 三角剖分) 算法，使得所有三角形的最小内角之和最大。因此， d e l a u n a y 三角剖分具有平均形态比最大的性质，它能够尽可能地避免病态三角 形的出现，因而得到了广泛的应用。 1 3 最小权三角剖分的定义 在计算几何领域中，有一个开放性的难题平面上有限点集的最小权三 角剖分( 姗t ) 问题。 4 中山大学硕士学位论文第1 章绪论 1 3 1 直线段的权 设平面上每个点p ；的坐标为 ；，y 。) ，记( p i ，p ，) 为以点b ，p ，为端点的直线 段。直线段( p ：，p ，) 的权，记为w 0 ；，p ，) ，是点p ；，p j 间的欧几里德距离，即 “p f ，p ，) 一厄j 了瓦j j 了 ( 1 3 ) 1 3 2 三角剖分的权 三角剖分的权为三角剖分中所有直线段的欧几里德长度的总和，即 口( p ) ) ( 。，目( 竹h o 一，p ，) ( 1 4 ) 1 3 3 最小权三角剖分 对于给定平面上基数大于3 的有限点集p ，它的三角剖分不是唯一的。最 小权三角剖分就是给定平面上的有限点集p 上的所有三角剖分中具有最小权的 三角剖分，记为 f 。蹄7 ( p ) ，它的权记为矽( m ( p ) ) 。 1 4 最小权三角剖分的应用 平面上有限点集的三角剖分在数值逼近，有限元方法，数值分析，计算机 辅助几何设计，计算机图形学，计算机视觉，机器人技术等方面都扮演着重要 的角色。而最小权三角剖分常常被应用于二元函数的内插值逼近。y o e l i 提出 了一种叫做多面体方法。1 。已知空间上的一系列点n ，f 一0 1 ，2 ，n l ，及函数， 在这些点上的值，用多面体方法可以求得函数，在任意一点p 的值，( p ) 。在这 个方法中，函数曲面是用点a ，f o ，1 ，2 ，n 一1 的三角片来逼近的。当p 点落在 某个三角片上，就可以用这个三角片的三个顶点进行线性插值来逼近r ( p ) 。最 小权三角剖分具有良好的数值属性，它提供了一种很好的逼近函数曲面的途径。 5 中山大学硕士学位论文第l 章绪论 1 5 最小权三角剖分的研究现状和发展趋势 计算给定平面上任意点集的最小权三角剖分的复杂度问题自1 9 7 5 年s ha f i l o s 和h o e y 提出至今，仍然是计算几何领域的一个开放性难题“1 。至于最小权三角 剖分问题是否是n p 完全的，它能否在多项式时间内求得解，这些问题至今仍然 列于g a r e y 和j o h n s o n 的问题清单中。3 。 自二十世纪七十年代后期至今，三角剖分的研究有了很大的发展，国际上 有不少学者提出一些启发式算法尝试求解最小权三角剖分问题”“。在这些研究 成果当中，最令人瞩目的就是基于贪心算法的三角剖分( g t ) “1 和d e l a u n a y 三角 剖分( d t ) 哪。 然而令人失望的是l l o y d 给出了两个反例证明了无论g t 还是d t 均不是最 小权三角剖分，并证明了m w t 问题是n p 难题“1 。虽然他的结论没有被权威所接 受“1 ，但大多数人认为m w t 至少同n p 难题一样难。于是人们的研究热情转向去 求各种启发式算法。人们采用近似阶来评估一个三角剖分的优劣。一个三角剖 分r 的近似阶r 仃，p ) 是它的权矽仃( p ) ) 同最小权三角剖分m 1 v t 的权 矽( m 胛( p ) ) 的比值对于p 中的顶点数，l 的阶，即 r 叮，p ) 一f ( 们f t ) ( 卜5 ) 其中p 为任一平面点集。并规定近似阶为“o ”( 小于或等于) 或“口”( 相同) 的为近似算法，近似阶为“q ”( 大于或等于) 的不是近似算法。m a n a c h e r 和 z o b r i s t 证明了贪心算法和d e l a u n a y 算法都不是近似算法。1 。k i r k p a t r i c k 应 用点集“直径”的概念“，给出了第一个近似算法，但是因为其近似阶不理想， 被称为“悲观算法”。1 9 8 7 年，国内学者洪家荣和国外学者p l a i s t e dd a 给 出了另外一个近似算法a 【l “，并猜测常数阶的剖分算法存在。但是要找到它是十 分困难的事情，有待于方法上的突破。 传统的三角剖分方法类似于组合优化，它们的近似阶估计是基于最坏情况 分析。然而，人们发现“”，随着问题规模的扩大和难度的增加，最坏情况分析 越来越不起主导作用，相反却易陷入局部极优；而算法性能的统计分析将起到 越来越重要的作用，并容易摆脱局部极优。于是，人们越来越倾向于用基于统 计分析的方法，例如模拟退火算法( s a a ) i 】”和遗传算法( g a ) 去解姗t 问题删。 1 6 本文研究的内容 贪心算法和d e l a u n a y 算法曾被认为是求解最小权三角剖分的最好办法，遗 6 中山大学硕士学位论文第1 章绪论 憾的是这一结果后来被推翻了。在最小权三角剖分问题的求解陷入了危机之际， 遗传算法等基于统计分析的方法被引入了这一领域。然而，传统遗传算法存在 不少缺陷种群大，进化次数多，待定参数多，早熟收敛等等，这些缺陷导 致基于传统遗传算法的最小权三角剖分求解时间长，待定参数的确定困难，权值 易陷入局部极值。而遗传量子算法( g q a ) 是一种高效的并行算法，它大体上保留 了传统遗传算法( c g a ) 的流程，但使用量子位表示法而不是二进制数，数值或符 号来表示染色体，因而染色体的状态是一种叠加态或纠缠态。g q a 的遗传操作 不同于传统遗传算法的选择、交叉和变异操作，而代之简单的量子门运算。因 此它比传统遗传算法具有更快的收敛速度，更强的全局寻优能力，更高的优化 效率。 本文在研究基于传统遗传算法的最小权三角剖分的基础上，分析其不足， 针对最小权三角剖分问题，首度将量子进化思想引入最小权三角剖分领域，以 突破传统遗传算法，提高算法效率并取得更优的剖分结果为目标。研究的主要 内容有： 1 提出新的三角剖分编码机制以减少三角剖分在存储空间，从而提高 算法效率； 2 提出新的量子“点权”概念将染色体量子位和三角剖分对应起来， 从而使量子计算与最小权三角剖分问题有机结合起来； 3 用随机初始化染色体量子位策略和全局最优个体保留策略分别代替 遗传量子算法中的固定初始化模式和每代最优个体保留策略，以避 免早熟收敛的发生； 4 尽量减少算法的待定参数以减少寻找最合适的参数组合的工作量； 5 在计算机上实现该算法，并进行算法的验证。 中山大学硕士学位论文第2 章遗传算法( g e d e t i ca l g o r i t h 曲 第2 章遗传算法( g e n e ti ca lg o r it h m ) 传统的三角剖分被证实不是最小权三角剖分，而基于统计分析的算法由于 性能优越而越来越受到重视，遗传算法就是其中的一个佼佼者。 遗传算法( g a ) 是二十世纪七十年代由美国密执安大学的h 0 1 l a n d 教授提出 来的模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概 率搜索算法1 。它是一个反复迭代的过程。它采用多路径搜索，对变量进行编 码处理，用对码串的遗传操作代替对变量的直接操作，从而可以更好的处理离 散变量。“。g a 用目标函数本身建立寻优方向，无需求导求逆等复杂的数学运算， 且可以方便的引入各种约束条件，更有利于得到最优解，适合于处理混合非线 性规划和多目标优化问题。因此，遗传算法被认为是解决复杂的优化问题，特 别是组合优化问题的有效方法。 2 1 遗传算法的基本原理 g a 是建立在自然选择和群体遗传学机理基础上的随机、迭代、进化，具有 广泛适用性的搜索方法。g a 搜索结合了达尔文适者生存和随机信息交换原则。 前者消除了解中不适应的因素，后者利用了原有解中已有的知识，从而有力地 加快了搜索过程。 对于一个给定的优化问题，设目标函数为 ，= 厂0 ，y ，z ) ， ，y ，z ) q ，f r ( 2 1 ) 要求瓯，y 。，z 。) 满足( 不失一般性，假设求最大值) f _ ，o 。，y 。，z 。) 2 攒，o ，y ，z ) ( 2 2 ) 其中0 ，y ，z ) 为白变量，q 是0 ，y ，z ) 的定义域，z ，) ，z 可以是数值，也可以是符 号；f 是实数，是解的优劣程度的一种度量，称为适应值；，为解空间 o ，y ，z ) q 到实数域，r 的一种映射。那么g a 的求解步骤如下： ( 1 ) 编码 用一定的方式( 通常为二迸制、浮点数、实数) 对变量x ，y ，z 进行编码形成 基因码链，每一码链代表一个个体，表示优化问题的一个候选解。 ( 2 ) 初始群体 8 中山大学硕士学位论文第2 章遗传算法( g e n e t i ca l g o r i t 面 令f o ，随机产生n 个个体组成一个群体联f ) ，该群体代表优化问题的一 些候选解的集合。当然，一般来说，它们的素质都很差。g a 的任务是要从这个 群体出发，模拟进化过程，择优汰劣，最后得出非常优秀的群体和个体，满足 优化的要求。 ( 3 ) 评价 按编码规则，将群体p ( r ) 中的每一个个体的基因码所对应的自变量取值 o 。，y i ，毛) 代入公式( 2 1 ) ，算出其函数值鼻，f l 2 ，n 。e 越大，表示该个体 的适应值越高，越适应于，所定义的生存环境。适应值e 为群体进化时的选择 提供了依据。 ( 4 ) 选择 按一定的概率从群体p o ) 中选取m 对个体，作为双亲用于繁殖后代，产生 新的个体加入下一代群体p o + 1 ) 中，一般只与e 成正比，即适应于生存环境的 优良个体将有更多繁殖后代的机会，从而使优良基因得以遗传。选择算子是遗 传算法的关键，它体现了自然界中适者生存的思想。 ( 5 ) 交叉 对于选中的用于繁殖的每一对个体，在基因码链中随机选择一位置，将双 亲的基因码链在此位置相互交换，从而生成新的个体。交叉体现了自然界中信 息交换的思想。 ( 6 ) 变异 以一定概率从群体p o + 1 ) 中随机选取若干个体，对于选中的个体，随机选 取基因码链的某一位进行取反运算。同自然界一样，基因的每一位发生变异的 概率是很小的。变异模拟了生物进化过程中的偶然基因突变现象。g a 的搜索能 力主要是由选择和交叉算子赋予的，变异算子则保证了算法能搜索到问题解空 间的每一点，从而使算法具有全局最优，它进一步增强了g a 的能力。 对产生的新一代群体进行重新评价、选择、交叉、变异，如此循环往复， 使群体中最优个体的适应值和群体的平均适应值不断提高，直至最优个体的适 应值达到某一限值或最优个体的适应值和群体的平均适应值不再提高，则迭代 过程收敛，算法结束。 9 中山大学硕士学位论文第2 章遗传算法( g e n e t i ca l g o r i t h i ) 图2 1 传统遗传算法的流程图 2 2 遗传算法的特点及存在问题 综上所述，由于g a 不受问题本身的性质、优化准则形式、模型结构形式、 被优化参数数目和有无约束等的限制，仅用目标函数在概率准则引导下进行并 行全局自适应搜索，因此它能够处理传统优化方法难以解决的复杂问题，具有 极高的鲁棒性和广泛适用性，因而g a 在各个优化领域得到了广泛应用并成为跨 学科研究的热点。与传统的搜索方法相比，g a 的特点可归纳为以下几点： ( 1 ) g a 处理参数集合的编码，丽不是参数本身； 1 0 中山大学硕士学位沦文第2 章遗传算法( g e n e t i ca l g o r i t h 面 ( 2 ) g a 同时搜索解空间中的许多点，而不是一个点，因而能够快速全局收敛； ( 3 ) g a 只需一个适应值函数( 性能指标) ，而不需要导数或其他辅助信息，因 而具有广泛的适应性； ( 4 ) g a 使用概率规则指导搜索而不是确定性规则，因此能搜索离散的有噪声 的多峰值复杂空间； ( 5 ) 由于评价为选择提供了依据，g a 在解空间内进行充分的搜索而并不是盲 目的穷举或瞎碰，因此其搜索时耗和效率往往优于其他优化算法。 但是，g a 在实际应用中也存在一些不足和局限性迭代次数多，收敛速 度慢、易陷入局部极值和过早收敛等。由于g a 的收敛性主要通过选择实现。搜 索性主要通过交叉和变异实现，故g a 的收敛速度主要与选择方式有关，“早熟 收敛( p r e m t u r ec o n v e r g e n c e ) ”现象的发生主要与交叉和变异方式有关。因此， 克服选择中的竞争压力和如何通过交叉变异使g a 的种群多样性得以保持以提 高g a 的搜索性能，一直是g a 的研究和应用中要解决的问题；此外，g a 的群体 的大小，交叉、变异概率是实验参数，它们是很难确定的，对于不同的问题， 这些参数的选取通常都不一样。 2 3 基于传统遗传算法的最小权三角削分的缺陷 近年来，有学者开展了基于遗传算法的最小权三角剖分的研究“。这些 研究只在某些遗传算子的实现或者终止条件有差异。它们的共同点是求解最小 权三角剖分的方法都是基于传统遗传算法( c g a ) 的，都需要定义变量的编码方 式，变异算子，选择算子和交叉算子。在实现这些算子的过程中，算法有很多 控制参数需要确定。而这些参数的确定到目前为止还没有统一的方法和规则可 循，只能通过大量的算例测试在参数组合中寻找适合求得最优解的一组参数。 在一般情况下，传统遗传算法需要确定6 8 个控制参数，如果对控制参数的精 度要求为o 1 ，参数组合的测试量达到1 0 6 1 0 8 数量级。要从海量的参数组合 中挑选适合于找到最优解的一组参数无异于大海捞针。此外，使用传统遗传算 法去求解m 盯问题，还存在种群大，迭代次数多的特点，例如，在k e r r yc a p p 和b r y a n ta j u ls t r o m 的文献“”中指出，他们提出的基于传统遗传算法的最小 权三角剖分在求解具有5 0 个点的问题时所用的种群大小为5 0 0 ，迭代次数为l o o 次，而所用的运算时间竞超过5 个小时之多。 1 l 中山大学硕士学位论文第3 章遗传量子算法( 6 e h e t i c 如a n t u 田a 1 9 0 r i t 咖 第3 章遗传量子算法( g e n e t icq u a n t u maig o rjt h m ) 遗传算法是一种模拟自然界物种进化机制的启发式搜索算法，但是传统遗 传算法待定参数多、进化代数多、种群大使得在处理某些问题时计算量过大， 对有些问题难以找到最优解。这促使人们尝试将量子理论和遗传算法相结合， 以实现更加高效、快捷的遗传算法。 量子计算4 2 1 是一种新兴的计算模式，是量子理论与信息论和计算机科学相 结合的产物。它利用量子系统的叠加性、并行性和量子纠缠等特性实现比经典 计算更为高效的计算模式”“。经典计算是以比特作为信息单位，而量子计算是 以量子比特作为信息单位。量子比特的优点在于它不但可以处于o 或者1 这两 种状态中的一种状态，而且可同时处于这两种状态的叠加态上。当有两个比特 时，它们可处于o o ，0 1 ，l o ，1 1 四种状态的叠加态。在量子计算中，量子状态 用量子位来表示，量子计算的操作对象是量子叠加态和量子纠缠态，若以纯态 表示一个数，则叠加态可以表示很多数，从而对叠加态的操作就意味着对多个 数同时进行多路操作运算。其操作是使构成叠加态的各个基态通过量子门的作 用互相干涉，改变它们之间的相对相位，使概率幅发生变化，从而使各个由基 态所表示的运算结果被观测到的概率也发生变化。由此可见，量子计算有很强的 并行性。 k u k - h y u nh a n 和j o n g h w a nk i m 在2 0 0 0 年提出的遗传量子算法( g q a ) 是将 量子计算与遗传算法相结合的一种算法o “。他们将量子的态矢量表达引入遗传 编码，利用量子旋转门实现染色体基因的调整，使得该算法将来在量子计算机 上执行成为可能，并且给出了一种基因调整策略，并以此策略实现了0 1 背包 问题的求解，结果显示其性能要优于传统遗传算法。 3 1 量子位表示法 在g o a 中，染色体不是用确定性的值( 如二进制数、浮点数或符号等) 表示 而是用量子位表示，或者说是用随机概率方式表示。一个量子位可能处于“1 ” 状态或“o ”状态，或者处于“1 ”和“o ”之间的中间态，即“1 ”和“0 ”的 不同叠加态。一般地，用忍个量子位就可以同时表示2 4 个状态，因而，对于相同 的优化问题，g q a 的种群大小可比传统遗传算法小很多。 在g q a 中，一个量子位的状态可表示为 l 平) 一a i o ) + 声1 1 ) ( 3 1 ) 中山大学硕士学位论文第3 章遗传量子算法( g e n e t i c 如a n t u ma 1 9 0 r i t h m ) 其中口和卢是复数，表示相应状态的概率幅。川2 表示量子位为“o ”状态的概 率，例2 表示量子位为“1 ”状态的概率，且满足下列归化条件： 阡+ 孵一1 ( 3 2 ) 3 2 染色体状态表示法 于量子位表示法的方法来表示染色体的状态。一个量子位被一对复数值 ，卢) 定义为( ；) ，它满足公式( 3 _ 1 ) 和( 3 - 2 ) 0 若染色体的基因个数为川，则染色体 孙兹) 。， 其中k 1 2 + 1 a 1 2 - 1 ，f - o 2 ，坍一1 。这种表示方法的好处就是它可以表示任 意的叠加状态。例如，假设具有3 个量子位的系统的3 对概率幅的值为 ( 捌捌复 a ， 麦l o o o ) + 参l 0 0 1 ) + 壶+ 爰i 。1 ) s ) 这就表示状态为f 咖) ，f 0 0 1 ) ，f 1 0 0 ) 和l l 。1 ) 的概率分别是；，；，；和；。这样， 公式( 3 5 ) 就同时表示了具有3 个量子位的系统的4 种不同的状态。 由此可见，由于使用量子位表示法的进化计算方法可以表示叠加的状态， 因此它比经典的方法具有更好的个体多样性。如公式( 3 5 ) 所示一个染色体基因 足以表示4 种不同的状态，而经典的表示方法却至少得用4 个基因来表示i o o o ) ， j 0 0 1 ) ，j 1 0 0 ) 和j 1 0 1 ) 这4 种不同的状态。量子位表示法是逐步收敛的。当h 2 或 者吲2 趋向1 或者。时，染色体基因收敛到一个状态。这就是说，量子位表示 中山大学硕士学位论文 第3 章遗传量子算法( g e n e t i cq u a n t ma l g o r i t h n ) 3 3 量子遗传操作 在g q a 中，由于染色体的状态处于叠加或纠缠状态，因此g q a 的遗传操作 不同于c g a 的选择、交叉和变异等操作方式，而采用将量子门分别作用于各叠 加态或纠缠态的方式；子代个体的产生不是由父代群体决定的，而是由父代中 的最优个体及其状态的概率幅决定的。量子遗传操作主要是将构造的量子门作 用于量子叠加念或纠缠态的基态，使其相互干涉，相位发生改变，从而改变其 基态的概率幅。因此，量子门的构造既是量子遗传操作要解决的主要问题，也 是g q a 关键所在，它直接关系到g q a 的性能优劣。 量子门变换是可逆的，且由于概率归一化的条件，变换矩阵必须是酋正矩 阵。常用的量子门有非门，控制非门，旋转门和h a d 砌a r d 门等。 3 4 遗传量子算法的结构流程 基于量子位的表示方法和量子力学的态叠加原理，g q a 的流程描述如下： ( 1 ) 仞始化量子染色体种群q p ) ，q o ) 一 叮球= l 2 ，n 。其中，撑为种群大小： f 为遗传代数，初始为o ；口：为种群第f 代的个个体，且有 留；= ( 麓| 茗：j ：z ：) ，z l z ，n ， c 。一e ， 其中，m 为量子位数目，即量子染色体的长度。 ( 2 ) 根据q o ) 中概率幅的取值情况构造候选解p ( f ) ，p ( f ) 一“i 一1 ，2 ，以 ，其 中，f l ，2 ，胛，是长度为研的二进制解串。它的每一位是根据对应量子 位的概率得到的。对于在【o ，1 ) 区间内随机产生的见，如果p ，b 斤，则一的 第，位取1 ：否则，取o ，j 一0 ，1 ，2 ，m 一1 。 ( 3 ) 用适应值评价函数对尸0 ) 中的每个个体进行评价，并保留此代中的最优个 体。若获得了满意解或者算法终止条件满足，则算法终止：否则，转入( 4 ) 继续进行。 ( 4 ) 使用恰当的量子门u g ) 来更新q o ) 。 ( 5 ) 遗传代数f f + 1 ，算法转到( 2 ) 继续进行。 g q a 的流程如下图所示： 1 4 中山大学硕士学位论文 第3 章遗传量子算法( g e n e t i c 如a n t ma 1 9 0 r i t 嘟 图3 1 遗传量子算法的流程图 3 5 遗传量子算法的收敛性 1 9 9 0 年e i b e n 提出了g a 的一种抽象表示，将进化过程定义为马尔可夫链， 利用转移概率矩阵相乘来进行状态的变换，分析得出g a 收敛到最优解的条件。 g q a 与g a 类似，仅多出了由q o ) 生成p ( f ) 和进化q o ) 的过程。由g a 的收敛性， 不难证明g q a 同样可收敛于最优解。 中山大学硕士学位论文第3 章遗传量子算法( g e n e t i cq u a n t u ma l g o r i t h m ) 3 6 遗传量子算法的特点 从上述算法的流程中可看出，g q a 在搜索过程中通过选择使具有较高适应 值的个体不断增多，并且根据量子坍塌的机理，采用随机观察方法产生新的个 体，不断探索未知空间，像g a 那样，使搜索过程得到最大的积累收益；其次， g q a 采用量子染色体的表示形式，使一个量子染色体上携带着多个状态的信息， 能带来丰富的种群，进而保持了群体的多样性，克服“早熟收敛”；另外g q a 对 量子染色体采用一种“智能”进化的策略来引导进化，从而提高了收敛速度。 但是，g q a 也存在一些缺陷。它只是将当前代的最优个体进行保留，如果当 前代的最优个体是局部极值时，算法就会陷入局部极值中很难摆脱出来，导致 “早熟收敛”的发生。 1 6 巾山大学硕士学位论文第4 章基于i g q a 的最小权三角削分 第4 章基于lg o a 的最小权三角剖分 由于传统遗传算法在处理最小权三角剖分问题时计算量过大，为了解决这 个问题，本文尝试另辟蹊径，在传统遗传算法的基础上，引入新的元素来克服 传统遗传算法的缺点和弥补它的不足。 g q a 是一种高效的并行算法，它大体上保留了传统遗传算法的流程，但使 用量子位表示法而不是二进制数，数值或符号来表示染色体，因而染色体的状 态是一种叠加态或纠缠态。g q a 的遗传操作不同于传统遗传算法的选择、交叉 和变异操作，而代之简单的量子门运算，因此它比传统遗传算法具有更快的收 敛速度，更强的全局寻优能力，更高的优化效率。文献”“2 “州分别提出了遗传 量子算法，量子遗传算法和并行量子遗传算法，文献”1 使用量子进化算法来求 解背包问题，文献”使用量子进化算法来进行磁盘定位，文献。”使用量子进化 算法来进行人脸识别。结果表明，量子门的更新方法大大优于传统遗传算法， 更适合于求解组合优化问题，因为这种更新策略是基于事先已知所优化问题的 最优解原则。 而到目前为止，并未曾有人使用遗传量子算法去求解最小权三角剖分问题。 因此，本文在g q a 的基础上，提出一种针对解决最小权三角剖分问题的改进的 遗传量子算法，包括新的三角编码机制，首创的量子“点权”概念，点权与量 子位的映射方法以及两种改进策略。 4 1 三角剖分的编码机制 为了表示三角剖分的状态，本文使用作者在文献“7 1 中提出的编码机制。 对于平面上给定的有限点集p = a ：f - 0 ，l 2 ，凡一1 ，在这n 个点( 假设各 不相同且不存在三点共线的情况) 之间最多有托 一1 ) 2 不同的边。这个点集的 三角剖分的状态可用一个二进制串z 来表示，其中， r ；m o ，。( 】2 1 ，f i o 或1 ( 4 - 1 ) 就是说，当边( p f ，p ，) 存在时( f ，) ，则z 的第f ，l 缸位一1 ：否则， = 0 。 其中， 加缸= 罗七+ f ( 4 2 ) 岛 1 7 中山大学硕士学位论文第4 章基于i g q a 的最小权三角刹分 反过来，如果f 。= 1 ，这意味着边( p ；，p ，) 存在( f o1 o= o- l o 0o = o= 0o f a l s e= o 0o 0= o0 0 00 j 1 ) ( a ) l 。一 一、( a r ，) 7 卜、 ， 、 、 ! 峨 坤i ) ， 今、 j ： _ 1 jo7 1 | | 、， ， ， 、 、，、， 一1 中山大学硕士学位论文第4 章基于i g q a 的最小权二角剖分 j ( b ) f 1 ) 1 4 - ，屈) 7_ r 、 ， |、一 ， 嫡t 。j j 渖。 ， 吵| | j j j j ： 一1 ： j l ：o? j? 、，j 、 ， 、 ， 、 、 、 _ 一， 一1 4 8 算法流程 图4 - 4 量子旋转门的极坐标图 以本章前面所述的小节为基础，对于平面上任意点集，基于改进