（计算机软件与理论专业论文）混合遗传算法在服装自动排版中的应用研究.pdf

混合遗传算法在服装自动捧版中的应用研究 摘要 服装样片的自动排版问题，在经过对待排版的衣片轮廓进行预处理后，转化为 二维不规则多边形的自动最优布局问题，该问题属于n p 完全的组合优化难题，具有 真实和广泛的应用背景。到目前为止在这问题上取得较好求解效果的方法是启发 式搜索方法，但是该方法本质上属于局部寻优，不能得到满意的近似最优解。而遗 传算法是一类借鉴生物自然选择和自然遗传机制的随机搜索方法，从一个点群开始 寻优，而不是从一个初始点开始寻优。理论上已经证明“3 遗传算法能以随机的方式 寻求到问题的最优解。 标准遗传算法求解该问题时，算法的搜索空间随着多边形个数的增加而呈指数 增加，而且在执行过程中常常产生大量不可行解，需花费很多无谓的时间去处理它 们而造成收敛速度慢，效率低。另外，标准遗传算法具有通用性，求解方法往往不 是解决特定问题的最有效的方法，它比专门针对该问题的知识型启发算法的求解效 率要差，虽然这种知识型启发算法保证不了一定能够找到问题的最优解。因此，在 将遗传算法应用于自动排版的已有研究中，通常算法的效率低，实用性差。 本文针对启发式算法和标准遗传算法在求解该问题时各自的缺陷，结合二者的 优点，将从实际排版经验得到的启发式信息引入标准遗传算法，建立了种启发式 混合遗传算法，将问题的解空间压缩至某个包含高性能解的子空间上，再进行遗传 搜索。算法首先在结合实际服装c a d 排版的特点和目前国内外研究工作的基础上， 提出一种合理恰当的编码方案，然后将启发式信息应用到初始群体的生成中，缩小 了问题的解空间，避免了对大量无谓解的搜索。另外，在综合前人用启发式搜索方 法对该问题所做研究而取得最优算法的基础上，本文给出了详细的解码过程，并根据 问题的特性设计了遗传算法中的三个重要算子。 关键词：自动排版，服装c a d ，启发式搜索，遗传算法 混合遗传算法在服装自动捧版中的应用研究 t h ea u t o - m a r k e rp r o b l e mo fa p p a r e lp i e c e sc a nb ec o n v e r t e dt ot h ea u t o - m a r k e r p r o b l e mo ft h et w o - d i m e n s i o n a lr a n d o mp o l y g o n a l ，w h i c hi s an p - c o m p l e t eh a r d p r o b l e ma n dw i d e l ye x i s t si nm a n yp r a c t i c a li n d u s t r i e s t h ec l a s s i c a lw a yo fs o l v i n gs u c h p r o b l e mi st h eh e u r i s t i cs e a r c h i n gm e t h o d b u ti t s h a r df o r t h i sm e t h o dt of i n da s a t i s f y i n go p t i m a ls o l u t i o n g e n e t i ca l g o r i t h m ( g a ) i sak i n do fr a n d o ms e a r c h i n g m e t h o db a s e do nt h ei d e ao ft h en a t u r a le v o l u t i o na n di n h e r i t a n c em e c h a n i s m ，w h i c h s t a r t ss e a r c h i n gf o ra no p t i m a ls o l u t i o nf b mag e n e r a t i o ni n s t e a do fa ni n d i v i d u a l i th a s b e e n p r o v e d t h a t g a i s a b l e t o f i n d t h e o p t i m a ls o l u t i o n i nar a n d o m w a y h o w e v e r ，w h e nt h es t a n d a r dg a ( s o a ) i su s e di ns o l v i n gs u c hp r o b l e m ，t h e s e a r c h i n gs p a c ei n c r e a s e sg r e a t l yw i t ht h ei n c r e a s i n go ft h ep o l y g o nn u m b e r , a n dt h e r e a r cag r e a td e a lo fi n f e a s i b l es o l u t i o n st h a tt a k em u c ht i m et 0b ed e a l tw i t hs ot h a tt h e r u n n i n gs p e e di ss l o w e dd o w n f u r t h e r m o r e ，s g ai saq u i t eg e n e r a lo n ea n di sn o tt h e b e s tw a yd i r e c t e dt ot h eg i v e np r o b l e mf o rl a c k i n go fr e l a t e dh e u r i s t i ci n f o r m a t i o n ，s oi t s u s u a l l yl e s se f f i c i e n tt h a nt h eh e u r i s t i cs e a r c h i n gm e t h o d ，t h o u g hi tw o u l d n tn e c e s s a r i l y g e tt h eo p t i m a ls o l u t i o n t h i st h e s i sc o m b i n e st h ea d v a n t a g e so ft h eh e u r i s t i cs e a r c h i n ga l g o r i t h ma n dg ab y i m p o r t i n gt h eh e u r i s t i ci n f o r m a t i o nf o r m e df m m t h ep r a c t i c a la p p a r e lm a r k e re x p e r i e n c e i n t og a , t h u ss e t t i n gu pak i n do fh e u r i s t i ch y b r i dg a t h ep r o p o s e da l g o r i t h md e c r e a s e d t h el a r g es o l u t i o ns p a c et oac o m p a c t e do n ec o m p o s e do fh i g h - p e r f o r m a n c ec a n d i d a t e s o l u t i o n sa n dt h e ne x e c u t i n gg e n e t i cs e a r c h i n go nt h i sr e d u c e ds p a c e a tf i r s t ，ar e a s o n a b l ec o d i n gr u l eo ft h es o l u t i o ni sp r o p o s e db a s e do nt h ep r a c t i c a l c a dm a r k e rs y s t e ma n dc u r r e n ts t u d yo nt h i sp r o b l e mw i t h i na n do u to fc o u n t r y , t h e n t h eh e u r i s t i ci n f o r m a t i o ni sa p p l i e dt ot h ep r o d u c t i o no ft h ei n i t i a lg e n e m t i o no fs o l u t i o n s t h et h e s i sa l s og i v e sad e t a i l e dd e c o d i n gp r o c e s s ，t a k i n ga d v a n t a g eo ft h ee x i s t i n g o p t i m a la l g o r i t h m s a tl a s t ，t h r e ei m p o r t a n tg e n e t i co p e r a t i o n sa r ed e s i g n e da c c o r d i n gt o t h ep r o b l e m 。sc h a r a c t e r s k e yw o r d s ：a u t o m a r k e r ，a p p a r e lc a d ，h e u r i s t i cs e a r c h i n g ，h y b r i dg a 混合遗传算法在服装自动捧版中的应用研究 1 1 研究背景及意义 第一章绪论 关于组台优化问题的研究，特别是求解复杂组合优化问题方法的探索已成为众 多科学家关注的焦点，这不仅在于其内在的复杂性有其重要的理论价值，也在于它 们在现实生活中的很多方面有着广泛的应用，尤其是对于n p 完全问题，它们都有着 非常精确的数学描述和复杂性度量，而且在理论上存在精确解。但在计算机技术高 度发达的今天，即使用当今最快速的计算机，我们甚至无法求得其具有中小规模问 题的最优解，这无疑是对人类的一个巨大挑战o 】。 二维自动排版问题是组合优化问题范畴的一类代表性问题，它的提出具有真实 和广泛的应用背景，该问题广泛的存在于v l s i 制造、造船、金属切割、家具扳材切 割、皮革、航空航天等行业。以纺织和服装生产工业为例，在传统的服装生产工业 中，主要是由有经验的排版师人员在布料上进行手工操作。这种工作方式既费时， 费力又费料，生产效率很低。服装计算机辅助设计系统( a p p a r e lc o m p u t e ra i d e d d e s i g ns y s t e m ) 的应用为排版师提供了一个方便的工具。但是到目前为止，主要是 利用c a d 系统提供的工具进行人机交互式的工作，这要求对排版师进行长期培训， 使得他们具有丰富的经验，这样得到的布局结果才可以达到另实际生产所接受的程 度。为了提高劳动生产率和减少原材料的浪费，人们自然想到了利用计算机对这些 不规则的物体自动产生最优或者近似最优的布局。这种不规则物体的自动最优布局 问题在理论上具有巨大的挑战性，可以认为它是人类目前为止遇到的最困难问题的 典型代表之一，因而具有重要的研究价值。 1 2 服装自动捧版问题的研究现状 因为二维不规则形状实体的排版问题所具有的广泛应用价值和重要理论研究价 值，许多专家学者已经在这方面进行了长期的研究，做了大量工作。1 。已经尝试过 的方法有： 混合遗传算法在服装自动捧版中的应用研究 1 启发式算法( h e u r i s t i cm e t h o d s ) ：解决这个问题的一个最简单的方法就是 使用枚举的方法，对可能的布局进行逐个的尝试。但是可能有的布局数目相对于多 边形的个数是按指数方式增长的。 传统的人工智能搜索方法一般使用各种启发式的方法来对付这种组合爆炸。最 初应用于自动最优布局问题的方法也不例外。一种最简单的启发式算法是贪婪法 ( g r e e d ym e t h o d ) ：首先根据各个多边形的度量( 比如多边形的面积大小，方正度 等) 对它们进行排序，然后照此顺序对每一个多边形的位置进行了搜索，根据当前 最优依次安排每一个多边形。这种启发式方法的优点是简单且容易实现。事实上， 目前大多数c a d 的自动排版功能基本上都是采用这种方法实现的。 基于启发式的工作还有：z l 一应用线性规划的方法研究了在一个给定的布局中 如何将其中的多边形物体靠紧( c o m p a c t i o n ) 的问题；d a n i e l s 和m i l e n k a 鼯”应用 局部搜索的方法研究了如何将少量( s 3 ) 的多边形互不相交的放入一个不规则多边 形容器中的问题。但是，这些方法本质上都是一种局部的搜索方法，容易陷入局部 最优，一般不容易求得问题的全局最优解。 2 一般的遗传算法：用一般遗传算法对此问题进行研究时，利用了遗传算法全 局寻优的特点，试图找到最优解或近似最优解。但是在解决问题的过程中，由于问 题本身的复杂性，算法的搜索空间随着多边形个数和编码长度的增加而呈指数增加， 而在将遗传算法应用于服装自动排版的已有研究中，解的编码通常较长。因此算法 的效率通常较低，实用性差。另外，对很多问题而言，基本遗传算法的求解效果往 往不是解决这个问题的最有效的方法，它比专门针对该问题的知识型启发算法的求 解效率要差，虽然这种知识型启发算法并保证不了一定能够找到问题的最优解。所 以到目前为止，用该算法求解问题取得的成果并不比启发式算法更优。 3 模拟退火算法：模拟退火算法在局部搜索过程中引入了随机的因素，依据 m e t r o p o l i s ”1 准则接受新解，即在局部搜索中，当某个解的目标函数即使变坏时， 仍然以一定的概率保留向这个解移动的可能性，以免陷入局部最优解。这种算法和 物理上的退火过程很相似，整个过程由一个称为温度的参数来控制。 模拟退火算法的弱点是：当目标函数有较深的局部最优解时，仅仅利用随机性 来跳出局部最优解就无能为力了。模拟退火算法的另一个缺陷是，由于没有记录解 2 混合琏传算法在服装自动捧版中的应用研究 的履历，有可能多次搜索到同一个解。因此，这种方法基本上是一种盲目的搜索。 模拟算法在自动布局领域中的应用见叫。 4 基于学习的方法：这是一种比较复杂并且具有一定智能的方法，它使用一定 的学习策略模拟人类设计师的实际操作。在自动布局问题中一般采用的学习方法是 基于实例的类比推理方法( c a s eb a s e dr e a s o n i n g ) 。这种方法的基本思想是：首先 建立一个由优秀的人类设计师设计的一组较好布局实例组成的实例库，然后将新输 入的待布局实例与实例库中的已有实例进行类比，根据一定的推理规则求出待布局 问题的解。 基于实例的学习需要解决很多问题。例如，如何组织和管理个实例库，需要 进行类比推理时如何检索这个库以找到合理的类别对象。当有多个对象可参与类比 时如何排除二义性，选中最合适的对象。已及如何根据类比结果的成败与好坏去改 进实例库的组织与检索方法，也就是对实例库代表的知识进行求精。 这一方法的主要缺点是需要保持和管理一组数量庞大的实例，并且每当一个新 实例来临时都要花很多时间去搜索这个庞大的实例库，因此一般具有较大的时间和 空间复杂性。基于实例的推理方法在各种布局问题中都有人尝试过，例如服装c a d 中的自动排版问题州和新闻报业中的自动报纸版面布局“”等。这种方法基本上是一 种符合推理的方法，虽然具有很大的吸引力，但是由于使用这种方法解决一系列复 杂的问题以及各种具体问题要求的不同，已有的各种应用只是对这种方法的不同程 度的实现，离实际应用还有较远的距离。 5 图论方法：图论方法经常用于求解布局问题1 ，它是以图中的节点代表待 布局物体，弧线代表布局物体之间的联系，由此将布局问题转化为一个已知的连接 图中寻找最大独立集或最大权平面子图问题；然后借助于分枝界定、整数规划及动 态规划等方法进行问题的求解。 董社勤、洪先龙等“”针对n o n s l i c i n g 结构的布图规划和布局问题，提出了一种 新的基于约束图表示的模型。基于该模型和性质，可得到近似0 ( 曲时问复杂度的布 局算法。通过引入变形网格的假设，得到一种更精确的n o n - s l i c i n g 问题的模型。 虽然作为组合数学的重要组成部分的图论方法在许多领域有着广泛的应用并卓 有成效，但布局问题的图论方法只限于小规模规则物体布局问题的求解，仍然不能 混合遗传算法在服装自动捧版中的应用研究 充分表达布局知识和约束。当布局问题的规模较大并涉及不规则物体时，布局问题 的图论求解方法将不再适用。 6 人工神经网络方法：自从h o p f i e l d 利用神经网络成功地解决了旅行商( t s p ) 问题以来，神经网络方法在组合优化领域受到了越来越多的重视“。 人工神经网络具有自适应性、学习性、强容错性及巨并行性等许多人脑所具有的 特性。然而常规神经网络存在局部最小问题，它的解依赖于网格的初始状态，在许 多场合仅能得到次优解。 另外也有很多研究在解决此类问题时，先将二维不规则多边形简化为矩形然后 进行求解，大大降低了问蹶的复杂度，但是此举必然会造成材料的浪费，也不符合 某些生产中“一刀切”的工艺，实用性低。 1 3 混合遗传算法应用于自动排版的可行性 遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 是一种模拟生命进化机制的搜索和优 化方法，g a 是从一个点群开始寻优，而不是从一个初始点开始寻优，因而获得的是 全局最优解。遗传算法的主要优点有： 易写一个通用程序，具有广泛的通用性； 非线性，不需要函数的梯度信息，也不需要函数的连续性； 本质并行性， 包括内在并行性和内涵并行性。前者是指遗传算法本身非常 适合大规模并行，适合在目前所有的并行机或分雍式系统上并行处理；后者指的是 遗传算法采用种群方式组织搜索，从而可以同时搜索解空间的多个区域、并相互交 流信息。 但是遗传算法也有缺陷和不足，如需要较大的群体规模，重复分析次数过多， 导致搜索速度较慢：局部搜索能力不足，导致寻优迭代后期，收敛速度减慢；易出 现早熟收敛和随机漫游现象等。 近年来遗传算法取得了蓬勃的发展，其中的一个热点研究方向就是将算法与问 题的特定知识结合起来形成混合遗传算法，许多成功的应用都得益于这样的混合方 法“”。服装的自动排版问题在将衣片进行预处理后，等价为= 维不规则多边形的自 4 混合遗传算法在服装自动捧版中的应用研究 动最优布局问题，属于二维装箱问题。这个问题的经典解决方法是用启发式搜索方 法，但是不能保证求得令人满意的近似最优解。将此类问题的启发式信息融入到标 准遗传算法中形成的混合遗传算法，可以发挥了标准遗传算法和传统的启发式方法 的互补特性，在一个包含高性能解的子空问里进行全局寻优，既能得到更好的近似 最优解，又能加快标准遗传算法的收敛速度，提高效率。 1 4 本文的研究工作和特点 1 4 1 本文的研究工作 本文在研究综合前人工作和结合服装排版实际应用过程的基础上做了如下工 作： 1 结合实际提出了一种实际可行的编码方案。在此编码方案中，服装衣片可以 在【一硝，石1 的范围内进行旋转，也可以进行水平和垂直方向的对称镜射操作，符 合实际应用的需要。传统的启发式自动排版算法中不能对衣片进行任何的旋转或对 称镜射操作。 2 将问题特有的启发式信息应用到算法初始群体的生成及算法的解码评价过 程中，大大避免了对不必要的解空间的搜索，提高了算法效率。 3 综合利用已有的启发式排版算法，给出了较详细的解码评价过程。 4 编制程序实现了算法。 5 对结果进行分析并指出了下一步的研究方向。 1 4 2 研究特点 本研究以自动排版算法在服装c a d 系统中的应用为背景，将排版师在实际排版 操作中的经验“大片先排，小片插空排”引入遗传算法，建立了一种启发 式混合遗传算法，该算法也适用于其他如板材切割等涉及二维不规则多边形自动排 版一类问题的领域，具有很强的通用性和实用性。 5 混合遗传算法在服装自动捧版中的应用研究 实验的初步结果表明，混合遗传算法为二维不规则多边形的自动排版问题提供了一种 很可行且卓有成效的求解方法，与其他算法相比，具有良好的求解性能和运行效率。 但是算法还有不足之处，主要有以下两点： 1 本文利用到的该问题的启发式知识有限，只用到了按服装衣片面积大小的排 序规则信息，下一步的研究可以考虑更充分的利用到其他的启发式信息，比如衣片 的方正度，凹凸衣片的结合性等，以及如何将这些信息更好的与遗传算法相结合。 2 启发式信息引入初始群体的生成过程中，将问题的解空间缩至某个包含高性 能解的子空间，在提高算法效率的同时，带来一个问题，即搜索空间的收缩可能会 漏掉更好的解。为弥补这一缺陷，可考虑引入邻域搜索法( n s t ) 作为遗传算法的辅 助搜索工具，来寻找可能落在子空间外的更好的解。 6 混能传算法在服装自动捧版中的应用研究 第二章启发式搜索 2 1 问题求解和搜索 问题求解就是通过在某个可能的解空间搜索，以寻找一个能解决某类问题的解 的过程。用人工智能能的术语来说，闯题求解就是在广义图中寻找一条从初始状 态出发，到达目标状态的解树。由于求解问题的过程中分枝有很多，主要由求解过 程中求解条件的不确定性、不完备性造成，使得求解的路径很多，这就构成了一个 图，我们说这个图就是状态空间。问题的求解实际上就是在这个图中找到条路径 可以从开始到结果，这个寻找的过程就是状态空间搜索。例如旅行问题是解决从出 发点蛩i 达目的地的路线和工具问题；机器人装配机器，就是给出把一堆零件变成一 台机器的一系列操作；定理证明就是寻找一条从前提条件到达结论的通路等等。 搜索技术是人工智能中应用十分广泛的机械化推理技术之一，各种典型的逻辑 推理过程都是一个隐式图的搜索过程。一般来说，一个逻辑系统就是一个形式语言 系统，它包含一个基本符号集和一个基本运算集，利用这两个集合可以生成一些合 式公式。另外还有一个公理集和一个变形规则集，利用这些集合可以实现合式公式 的变形。一个逻辑推理问题就是实现一个从前提公式，到目标公式g 的变换。我们 可以用公式的本身来表示状态空间的状态，把公理和变形规则看成是操作，这样就 得到一个隐式图的状态空间：，是初始状态，g 是目标状态，每用规则推理一步就是 调用一个操作，并实现一步状态空间的搜索，整个推理过程就是一个隐式图的搜索 过程“1 。 问题的求解依赖于搜索一条从初始状态到目标状态的路径。这种搜索一方面可 以选择最佳路径，提高计算速度；另一方面当求解的问题很复杂时，如果要把问题 的所有状态空间都存储到计算机上是不必要的，甚至是不可能的“。为解决计算机 在时间与空间上的局限性，必须通过搜索来产生它所需要的部分状态，以便节省存 储空间，提高求解的效率。在搜索过程中，如果搜索过程是按照事先的某种策略来 进行的，且不考虑从搜索中获得的中间信息来改进控制策略，这样的搜索称为盲目 7 混合遗传算法在服装自动排版中的应用研究 搜索( b l i n ds e a r c h ) ；相反，如果在搜索过程中不断利用中间获得的信息来改进搜 索方向，就成为启发式搜索( h e u r i s t i cs e a r c h ) 。问题求解与搜索是人工智能研究 的核心课题，它是许多涉及规约、推断、规划和相关过程的核心概念1 6 】。 2 2 启发式的问题求解 “启发( h e u r i s t i c ) ”就是从人们生活实践中总结出的一些解决问题的经验、 策略、技巧、窍门或简化步骤，基本原则是好的优先。在人工智能中，启发是关于 发现和发明规则及方法的研究。在状态空间搜索中，启发式被定义成一系列规则， 它从状态空间中选择最有希望到达问题解的路径。 h a s i m e n 从心理学出发，分析并研究了人类活动的特点，他注意到人类尽管自 身能力和知识有限，却能自如地解决那些看来难以胜任的问题，并做出了正确的决 策和反应。其秘密在于，人们通常不是采用系统的，精确的方法去追求问题的最优 解，而是通过逐步尝试的方法。人类就是遥过这种方法，避免了计算复杂度高的阔 题，使原来看来是非多项式难解的问题迎刃而解，这就是有限合理原则，也就是所 谓启发式( h e u r i s t i c ) 的求解方法“”。 在实际解决一个具体闯题时，人们常常把一个具有复杂联系的实际问题抽象化， 保留某些主要因素，忽略掉大量次要因素，从而将这个实际问题转化成具有明确 结构的有限状态空间问题，这个空间中的状态和变化规律都是已知的有限集合，因 此可以找到一个求解该问题的算法。然而，在智能活动中使用最多的不是具有完备 性的算法，而是不一定完备的启发式方法，其原因有二： 首先，大多数情况下，智能系统不知道与实际问题有关的全部信息，因而无法 知道该问题的全部状态空间，不可能用一套算法来求解其中的所有问题，这样就只 能依靠部分状态空间和一些特殊的经验性规则来求解其中的部分问题。 其次，有些问题在理论上存在求解算法，但是在工程实践中，这些算法不是效 率太低，就是根本无法实现，为了提高解题的效率，不得不放弃使用这些算法，而 求助于一些经验性的启发式规则。 由此看来，启发式的问题求解，不仅在实践上是需要的，而且在理论上也是必 8 混合遗传算法在服装自动捧版中的应用研究 不可少的。 然而，和发明创造的所有规则一样，启发式策略也是极易出错的。在解决问题 的过程中启发仅仅是下一步将要采取措施的一个猜想，它常常根据经验和直觉来判 断。由于启发式搜索只有有限的信息，要想预测进一步搜索过程中状态空间的具体的 行为很难办到。一个启发式搜索可能得到一个次最佳解，也可能一无所获。这是启 发式搜索固有的局限性，这种局限性不可能由所谓更好的启发式策略或更有效的搜 索算法来消除。 2 3 启发式搜索 大体上说，搜索分两种，一种是盲目搜索，又称非启发式搜索，另一种是启发 式搜索。盲目搜索在搜索过程中不改变搜索策略，不利用搜索获得的中间信息。它 盲目性大，效率差，无法解决大型问题；而启发式搜索在搜索过程中加入了与问题 相关的启发式信息，用以指导搜索向着一个比较小的范围进行，加速求解的过程， 盲目搜索包括纯随机搜索( r a n d o mg e n e r a t i o na n dr a n d o mw a l k ) ，广度优先 搜索( b f s ) 、深度优先搜索( d f s ) 以及重复式搜索，不管何种盲目搜索方法，要寻 找一个通向目标的路径，都是耗费很大的。虽然这些方法原则上提供了一个路径寻 找问题的解，但是在应用上则是往往行不通的。因为在某条路径被找到之前，搜索 过程要扩展太多的结点，从而带来花费在搜索上的时间很长。盲目搜索效率太低， 有时甚至不可能完成，这就要用到启发式搜索了。启发式搜索在状态空间中的搜索 对每一个搜索的位鬓进行评估，得到最好的位置，再从这个位置进行搜索直到目标。 这样可以省略大量无谓的搜索路径，提高了效率“”。总之，盲目搜索随着搜索的进 行，需搜索的空间很快加大；启发式搜索随着搜索的进行，需搜索的空间有所增加， 但增加的幅度远小于非启发式搜索，问题空间中的有些地方因为中间信息的获得而 不用搜索了，如图2 3 所示： 9 混合遗传算法在服装自动捧版中的虚用研究 图2 3 搜索空问示意图f 1 b j 对问题空间进行搜索时，提高搜索效率需要有和被解问题的解有关的大量控制 性知识作为搜索的辅助性策略。有两种极端的情况：一种是没有任何这种控制性知 识作为搜索的依据，因而搜索的每一步完全是随意的，如随机搜索；另一种是有充 分控制性知识作为依据，因而搜索的每步选择都是正确的，这种搜索叫最佳搜索。 一般情况是介于二者之间，这些控制性信息反映在估价函数之中。 估价函数的任务就是估计待搜索结点的重要程度，给它们排定次序。估价函数 f ( x ) 可以是任意一种函数，如有的定义它是结点x 处于最佳路径上的概率，或是x 结点和目标结点之间的距离，或是x 格局的得分等等。一般来说，估价一个结点的 价值，必须综合考虑两方面的因素：已经付出的代价和将要付出的代价。一般把估 价函数f ( n ) 定义为从初始结点经过n 结点到达目标结点的最小代价路径的代价估 计值，它的一般形式是： ，( ) - g ( n ) + ( 厅) 其中譬6 是从初始结点到口的实际代价，h 倒是从疗到目标结点的最佳路径的 估计代价，主要是h ( n ) 体现了搜索的启发信息。因为实际代价g o ) 可以根据生成的 搜索树实际计算出来，而估计代价h ( n ) 却依赖于某种经验估计，它来源于我们对 问题的解的某些特性的认识，这些特性可以帮助我们更快地找到问题的解。以 f ( n ) 一占伽) + 伽) 为选择标准的搜索策略叫启发式搜索策略。由于，m ) 是对解的总 代价的一种估计，以它为标准的选择实际上是在直接选“最忧解”，所以启发式搜索 又可分为两种基本类型：局部择优搜索法和最好优先搜索法，它们都利用了启发函 数，但在具体的选取最佳搜索节点时的策略不同。 1 0 混合遗传算法在服装自动捧版中的应用研究 第三章遗传算法概述 3 1 遗传算法介绍 当今科学技术正进入多学科互相交叉、互相渗透、互相影响的时代。这一点在 计算机领域表现得尤为突出。随着人类生存空间的扩大和认识世界改造世界范围的 拓宽，人们又对计算机科学提出了新的要求和期望。近年来，随着人工智能应用领 域的不断拓广，传统的基于符号处理机制的人工智能方法在知识表示、处理模式及 解决组合爆炸等方面所碰到的问题已变得越来越突出，这些困难甚至使得某些学者 对强人工智能提出强烈批判，对人工智能的可能性提出了质疑o ”。 因此，寻找一种适于大规模并行且具有某些智能特征如自组织，自适应，自学 习等的算法已成为有关学科的一个研究目标。大自然是我们解决各种问题时获得灵 感的源。几百年来，将生物界所提供的答案应用于时间问题求解已被证明是一个成 功的方法，并且已经形成一个专门的分支一仿生学( b i o n i c s ) 。自然界所提供的答 案是经过漫长的自适应过程一演化过程而活动的结果。除了演化过程的最终结果， 我们也可以利用这一过程本身去解决一些较为复杂的问题。 遗传算法正是基于这种演化思想而发展起来的一种通用的问题求解方法。它采 用简单的编码技术来表示各种复杂的结构，并通过对一组编码表示进行简单的遗传 操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。 遗传算法( g e n e t i ca l g o r i t h m _ _ g ) ，是一类建立在自然选择和群体遗传学 机理基础上的通用问题求解算法，具有广泛的适用性。遗传算法最早是由美国著名 学者j h h o l l a n d 教授在1 9 6 2 年提出的，当时并未受到普遍重视。其主要原因是： 一是因为当时这些方法本身还不够成熟；二是由于这些方法需要较大的计算量，而 当时的计算机速度还跟不上要求，这样就限制了其应用：三是当时基于符号处理的 人工智能方法正处于顶峰状态，使人们难以认识到其他方法的有效性。1 9 7 5 年， h o l l a n d 教授出版了一本名为自然与人工系统的适配( a d a p t a t i o ni nn a t u r a la n d a r t i f i c i a ls y s t e m ) 的专著，标志着遗传算法的创立。作者在书中提出了一种理论， i i 混合遗传算法在服装自动捧版中的应用研究 并构造了一类对环境具有自适应能力的通用程序。作者在研究中已预见了适者生存 的选择机制和交叉操作在人工自适应中的重要地位，以及群体搜索方法的重要性， 并对此进行了大量的研究工作，丰富了这一算法的内容。 进入2 0 世纪8 0 年代，人们越来越清楚地意识到传统人工智能方法的局限性， 并且由于计算机速度的提高以及并行机的普及，使进化计算对机器速度的要求不再 是制约其发展的因素。1 9 8 5 年召开了第1 届遗传算法及其应用国际会议之后该会议 对遗传算法的关注越来越多，在机器学习、人工智能、神经元网络、k d d 等学术会 议上都有遗传算法专题，国际性刊物人工智能、机器学习、 i e e e t r a n s a c t i o n o i ln e u r a ln e t w o r k ) 等不断发表有关遗传算法的文章。目前，遗传算法已成为当今 个十分热门的研究课题，在优化、机器学习和并行处理等领域得到越来越广泛的 应用叫。 遗传算法有其自身的特点：智能性与本质并行性。遗传算法的智能性包括自组 织、自适应和自学习等，应用遗传算法求解问题时，在确定了编码方案、适应值函 数及遗传算予后，算法将应用演化过程中获得的信息进行自组织援索，适者生存的 选择策略赋予了遗传算法自适应的能力，同时也赋予了它根据环境的变化自动发现 环境的特征和规律的能力；遗传算法的本质并行性表现在两个方面：一是遗传算法 的内在并行性，即其本身非常适合大规模并行，二是遗传算法的内含并行性，即它 可以同时搜索解空间内的多个区域，并且相互之间进行信息交流，这种搜索方式使 得遗传算法可以以较少的计算获得较大的收益。另外它还具备多解性、不确定性和 非定向性等特点，这些特点使得遗传算法广泛应用于控制、规划、设计、组合优化、 图像处理、信号处理、机器人、人工生命等多个领域。 混合遗传算法在服装自动捧版中的应用研究 3 2 遗传算法与其饱搜索方法的比较 搜索方法可以分为三类，即解析法( c a l c u l u s - - b a s e d ) 、枚举法( e n u m e r a t i v e ) 和随机法。如图3 1 所示： r 直接法 解析法j l 间接法 ，t a b u 搜索 f 导向随机 随机法1 。瞄蜘 模拟退火 l 盲目随机、 ”“ l 演化算法j 萎竺：竺 枚举法：动态规划 l 演化规划 图3 1 搜索方法的分类。” 解析法在求解过程中主要使用目标函数的解析性质，如一阶导数、二阶导数等 这一方法又可以直接分为直接法和间接法。直接法根据目标函数的提到来确定下一 步搜索的方向，如n e w t o n 方法、共轭梯度法和变尺度法等。直接法采用的是一种“爬 山”策略，即根据最陡的方向爬上一个局部最优点，从而它难以找到整体最优解。 间接法则从极值的必要条件出发导出一组方程，然后求解方程组再通过比较求得极 值，然而导出的方程组一般是非线性的，它的求解是非常困难的，所以，对一些很 简单的问题才使用间接法。 与传统搜索方法相比，遗传算法具有以下的不同点1 ； 1 遗传算法不是直接作用在解空间上，而是利用解的某种编码表示； 2 遗传算法从一个群体即多个点而不是从一个点开始搜索，这是它能以较大的 概率找到整体最优解的主要原因之一： 搜索方法 混合遗传算法在服装自动排版中的应用研究 3 遗传算法只使用解的适应性信息( 即目标函数) ，并在增加收益和减小开销 之间进行权衡，而传统搜索算法一般要使用导数等其他辅助信息； 4 遗传算法使用随机转移规则而不是确定性的转移规则。 1 4 混合遗传算法在服装自动排版中的应用研究 3 3 遗传算法的基本思想及形式化表示 遗传算法的基本思想基于d a r w i n 的进化论和m e n d e l 的遗传学说。d a r w i n 的进化论认为：每一物种在不断的发展过程中越来越适应环境。每个个体的特征 被后代继承，但后代又不完全同于父代。适者生存。m e n d e l 的遗传学说认为： 遗传是作为一种指令遗传码封装在每个细胞中，并以基因的形式包含在染色体 中。基因杂交和突变可能产生对环境适应性强的后代。适应值高的基因结构保存 下来。 应用遗传算法求解问题时，常将问题的解表示成“染色体”，解的集合构成 一群“染色体”，即种群，将其置于问题的环境中，从中选择出适应环境的“染 色体”进行复制，郎再生，通过交换( c r o s s o v e r ) 和变异( m u t e ) 两种基因操 作产生出新一代的更适应环境的“染色体”群。如此一代代进化，最终收敛到一 个最适应环境的个体，得到问题的最优解。 遗传算法可以形式化的描述如下： g a - ( p ( 0 ) ，n ，1 ，5 ，g ，p ，f ) 这里p ( 0 ) 一( 口。( o ) ，a ：( o ) ，4 ，( 0 ) ) j ”，表示初始种群； i - b 一 0 m 表示长度为l 的二进制串全体，称为位串空间。 表示中群中含有个体的总数； ，表示二进制串的长度； 5 ：j ”一，”表示选择策略； f 表示遗传算子，通常它包括繁殖算子d ，；，一j ，杂交算子d c ：j x i 一，j 和变异算子0 。：j 一，： p 表示遗传算子的操作概率，包括繁殖概率b 、杂交概率p 。和变异概率p 。； ，：，一r + 是适应函数； t ：，”一 0 m 是终止准则。 不过，现在的遗传算法已不再局限于二进制编码，其他的编码方式还有g r a y 混合遗传算法在服装自动排版中的应用研究 编码，动态编码，实数编码，有序串编码，结构式编码等等，根据实际问题的需 要灵活确定编码方式，然而其基本思想和原则是一样的。 遗传算法的流程图如图3 2 所示。 图3 2 遗传算法流程图 1 6 混合遗传算法在服装自动排版中的应用研究 3 4 遗传算法的问题求解步骤 在设计遗传算法求解具体问题时，通常按以下的基本步骤进行： 1 确定编码方案：演化算法求解问题不是直接作用在问题的解空间上，而 是利用解的某种编码表示。选择何种编码表示有时将对算法的性能、效率产生很 大的影响。通常用的编码方式有：二进制编码，g r a y 编码，动态编码，实数编 码，有序串编码，结构式编码等等，根据实际问题的需要灵活确定编码方式。 2 确定适应函数：适应值是对解的质量的种度量，它通常依赖于解的行 为和环境( 即种群) 的关系。一般以目标函数或费用函数的形式来表示。解的适 应值是演化过程中进行选择的唯一根据。 3 选择策略的确定：优胜劣汰的选择机制使得适应值大的解有较高的存活 概率，这是演化算法与一般搜索算法的主要区别之一。不同的选择策略对算法的 性能也有较大的影响。常用的选择策略有基于适应比例的选择( 包括繁殖池选择 ( b r e e d i n gp 0 0 1 ) ，轮盘式选择( r o u l e t t ew h e e ls e l e c t i o n ) ，b o l t z m a n n 选 择等) 、基于排名的选择( 包括线性排名选择和非线性排名选择) 以及基于局部 竞争机制的选择( 包括锦标赛( t o u r n a m e n t ) ，( 1 1 ，九) 和( u + ) 选择，b o l t z m a n n 锦标赛选择等) 选择等。 4 控制参数的选取：控制参数主要包括种群的规模、算法执行的最大代数、 执行不同遗传操作的概率以及其他一些辅助性的控制参数。 5 遗传算予的设计：演化算法中的遗传算子，主要包括繁殖 ( r e p r o d u c t i o n ) 、杂交( c r o s s o v e r ) 、变异( m u t a t i o n ) 以及其他高级操作。 6 确定算法的终止准则：由于演化算法没有利用目标函数的梯度等信息， 所以在演化过程中，无法确定个体在解空间的位置。从而无法利用传统的方法来 判定算法的收敛与否来终止算法。常用的办法是预先规定一个最大的遗传代数或 算法在连续多少代后解的适应值没有什么明显的改进时，算法终止。 1 7 混合遗传算法在服装自动排版中的应用研究 图3 3 表示了遗传算法的执行过程： 1 囊井为 图3 3 遗传算法的执行过程 嚣：i 以上各基本步骤是密切相关的，编码方案与遗传算子的设计是同步考虑的， 遗传算法的基本结构框架可以描述如下： b e g i n t 一0 ； 随机初始化种群p ( o ) - 协，x ：，) ； 计算p ( o ) 中各个个体的适应值； w h i l e ( 不满足终止条件) d o b e g i n 由p ( f ) 通过遗传操作形成新的种i 咩p ( t + 1 ) ； 计算尸口+ 1 ) 中各个个体的适应值； t t + 1 ： e n d e n d 上述基本结构是一个比较粗略的框架，在具体实现时，需要对它进行细化操 作和改进。 1 8 混合遗传算法在服装自动排版中的应用研究 第四章混合遗传算法 4 1 混合遗传算法的思想 遗传算法由于其运算简单和解决问题的有效能力而被广泛应用到众多的领 域中。理论上已证明，遗传算法能以随机的方式寻求到问题的最优解。但另一方 面，应用实践表明，在遗传算法的应用中也会出现一些不尽人意的问题，这些问 题中最主要的是它容易产生早熟现象、局部寻优能力较差等。并且一般来说，对 很多问题而言，标准遗传算法的求解效果往往不是解决这个问题的最有效的方 法，它比专门针对该问题的知识型启发算法的求解效率要差，虽然这种知识型启 发算法并保证不了一定能够找到问题的最优解。另外，遗传算法也无法避免多次 搜索同一个可行解，这也是影响遗传算法运行效率的一个因素。 另一方面，梯度法、爬山法、模拟退火法、列表寻优法等一些优化算法却有 很强的局部搜索能力，而另一些含有问题与相关知识的启发式算法的运行效率也 比较高。可以预计，在遗传算法的搜索过程中融合这些优化方法的思想，构成一 种混合遗传算法( h y b r i dg e n e t i ca l g o r i t h m ) 是提高遗传算法运行效率和求解 质量的一个有效手段4 州。 应用研究表明，目前一些常规的遗传算法并不一定是针对某一问题的最佳求 解方法。而将遗传算法与问题的特有知识集成到一起所构成的混合遗传算法，却 有可能产生出求解性能极佳的方法，这也为继续提高遗传算法的搜索性能提供了 新的思路“1 。 4 2 混合遗传的策略 混合遗传的策略很多，下面是常见的两种混合策略：遗传算法与模拟退火算 法的混合、遗传算法与局部搜索策略的混合。 遗传算法与模拟退火算法的混合：模拟退火算法( s i m u l a t e da n n e a l i n g ， 简称s a )