（微电子学与固体电子学专业论文）电池碎片自动排布算法的研究.pdf

摘要 摘要 排布问题，就是在一个给定的空间区域内，按照一定的优化方式将待排物 体合理地摆放在布局空间中，满足一定的约束条件，并使空间利用率达到最高。 自动排布问题在工业生产中应用十分广泛，前人已经证明，排布问题属于n p 完 全问题，而紧密合理的排布在工业生产中可以大大提高生产效率，节约成本， 因而具有重要的研究意义和实用价值。 本文针对晶体硅电池碎片封装工艺中的排布问题提出了一种自动排布算 法，可以实现电池碎片的自动排布。由于二维不规则图形的排布问题属于n p 完 全问题，因此解决计算的可解性和难解性是问题的关键。 本文将电池碎片的图形经过前期预处理，生成轮廓多边形，使其满足c a d 排布的格式。针对规则的电池碎片采用最低水平线法进行排布，空间利用率可 以达到8 4 7 。针对不规则的电池碎片，采用启发式搜索的策略，按照先排大片 后排小片的原则，根据空间利用率这个启发信息确定待排碎片的选取规则和定 位规则。对有方向约束的电池碎片，采用先对碎片做出旋转后排布的方法，实 现空间利用率达到6 9 3 ；对于无方向约束的电池碎片，采用人机交互式排布， 实现空间利用率达到6 9 8 。这两种方式可以满足不同的工艺要求。 本文提出的算法不仅适用于电池碎片的排布问题，对于其他各种排布问题 也有很好的借鉴意义，最后我们给出了几组电池碎片的排布实例，该算法在空 间利用率和运算速度上都可以满足要求。 关键词：电池碎片自动排布启发式搜索碰撞检测 a b s t r a c t a b s t r a c t p a c k i n gp r o b l e m si sa 1 1o p t i m i z a t i o np r o b l e m w h i c hi sc o n c e r n e dw i t hf i n d i n ga a r r a n g e m e n to fm u l t i p l ed i f f e r e n t s i z e do b j e c t si nal a r g ec o n t a i n i n gr e g i o nw i t h o u t o v e r l a p s a u t o m a t i cp a c k i n gp r o b l e m i sw i d e l yu s e di ni n d u s t r yp r o d u c t i o n p a c k i n g p r o b l e mi sp r o v e dt ob ean pc o m p l e t ep r o b l e m ，a n dag o o ds o l u t i o nc a l l s a v et h e t i m ea n de n e r g yi nt h ei n d u s t r yp r o d u c t i o n ，s oi th a si m p o r t a n tr e s e a r c hv a l u ea n d u s e v a l u e t h i sp a p e rg i v e saa u t o m a t i cp a c k i n ga l g o r i t h ma i m e dt os o l v et h ep a c k i n g p r o b l e m i nt h ec r y s t a ls o l a rc e l lf r a g m e n te n c a p s u l a t i o n i tc a l la c h i e v et h ea u t o m a t i c p a c k i n go fs o l a rc e l lf r a g m e n t t h ek e y t os o l v et h ea u t o m a t i cp a c k i n gp r o b l e mo f t w o d i m e n s i o n a li r r e g u l a rs h a p e do b j e c t s ，w h i c hi san pc o m p l e t ep r o b l e m ，i st od o w i t ht h ep r o b l e mo f c a p a b i l i t ya n di n t r a c t a b i l i t y t h i sp a p e rp r e t r e a t st h eg r a p ho fs o l a rc e l lf r a g m e n t ，a n df i n d st h eo u t l i n e p o l y g o n ，a n df i t s i ti nw i t ht h ef o r m a to fc a dp a c k i n g t ot h er e g u l a rs o l a rc e l l f r a g m e n t s ，w ef i n i s hp a c k i n gb yaa l g o r i t h mc a l l e dt h el o w e s th o r i z o n t a ll i n e ，a n dt h e s p a c eu s ee f f i c i e n c yi s8 4 7 t ot h ei r r e g u l a rs o l a r c e l lf r a g m e n t s ，w ef i n i s hp a c k i n g b yh e u r i t i s cs e a r c h i n g w ep a c kt h eb i g g e rf i a g m e n t sf i r s ta n d t h e nt h es m a l l e ro n e s t h ec h o i c ec r i t e r i o na n do r i e n t a t i o n c r i t e r i o na r ec o n f i r m e db yt h es p a c eu s e e f 五c i e n c v t ot h ed i r e c t i o nr e s t r i c t e df r a g m e n t s ，w ec i r c u m r o t a t et h e mf i r s ta n d t h e n p a c kt h e m t h es p a c eu s ee f f i c i e n c yi s 6 9 3 ；t ot h eo t h e r s ，w ep a c kt h e mb y m a l l m a c h i n ea l t e r n a t i o n , a n dt h eu s ee f f i c i e n c yi s6 9 8 t h et w ow a y sc a r lf u l f i l l t h ed i f f e r e n tc r a f td e m a n d t h ea l g o r i t h mi nt h i sp a p e rc a nb ee a s i l ya d j u s t e dt oo t h e rp a c k i n gp r o b l e m s ， b e s i d e st h es o l a rc e l lf r a g m e n tp a c k i n gp r o b l e m a tt h ee n do ft h ep a p e r ，t h e r ea r e s o m ee x a m p l e so fs o l a rc e l lf r a g m e n tp a c k i n g t h eu s ee f f i c i e n c y a n dt i m e c o m p l e x i t yo ft h eo p e r a t i o nc a nb ea c c e p t e d k e yw o r d s ：s o l a r c e l lp i e c e s p a c k i n gp r o b l e m h e u r i s t i cs e a r c h c o l l i s i o nd e t e c t i o n i i 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：王襁 训罗年岁月冶日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名：王耗立 w 罗年上月 第一章引言 第一章引言 第一节太阳电池碎片封装工艺的研究与意义 1 1 1 太阳电池的研究意义与面临的问题 能源问题是人类进入二十一世纪面临的严峻挑战，开发可再生能源已经成 为十分迫切的课题。太阳能是人类取之不尽用之不竭的清洁能源，太阳位于离 地球一亿五千万公里远的地方，因核聚变反应而产生的巨大能量，每秒辐射到 地球的能量为1 7 1 0 1 7 w ，相当于人类活动所耗费的能量的五万倍还多。太阳每 天到达地球表面的辐射能相当于全球所有发电厂运行2 5 0 年的总发电量；大气 层外的太阳光能量密度为1 3 6 6 w m z 。被大气层反射、吸收以后，投射到地面上 的平均能量仍然达到1 0 0 0 w m 2 ，总功率可达1 2 5 1 0 8 g w 【l j 。 光伏产业是世界发展速度最快的行业之一。为实现能源和环境的可持续发 展，世界各国均将光伏发电作为发展的重点。在各国政府的大力扶持下，世界 光伏产业发展迅猛【2 】，近十年的平均增长率达到3 3 。2 0 0 8 年，业内世界著名 的( ( p h o t o ni n t e m a t i o n a l ) )( 光子国际) 杂志发表了光伏发电产业的权威预测： 2 0 0 7 年全球光伏电池的产量已达4 0 g w ，预计2 0 11 年将达2 0 5 g w 。 目前，人们研制和开发了各种各样的太阳能电池，主要有晶体硅电池、薄 膜太阳电池和有机太阳电池等，其中晶体硅电池工艺最为成熟，也是目前在太 阳电池市场上占据主体地位的电池。目前晶体硅电池在太阳电池市场中占据了 8 5 以上的份额。晶体硅电池一般由厚度为2 0 0 3 0 0 a m 的硅片制成。薄膜电池 是在最近几年才迅速发展起来的，目前正在向产业化方向发展。许多国家开始 积极推进薄膜电池生产线和示范项目的建设。专家认为，未来1 0 年晶体硅太阳 能电池所占份额尽管会因薄膜太阳能电池的发展等原因而下降，但由于光伏产 业总体的发展和扩大，晶体硅太阳能电池总产量依然会以很高的速度增加。 提高转换效率和降低成本是太阳电池制备中考虑的两个主要因素【3 】，而在目 前晶体硅系列的太阳电池中，要想进一步大幅度提高转换效率是比较困难的。 第一章引言 加之受到薄膜电池低成本的冲击，要想在太阳电池发电中占据主导地位，就必 须找出大幅度降低生产成本的新途径和新方法。现有的高转换效率的太阳电池 都是在高质量的硅片上制成的，这是制造晶硅电池最费钱的部分。因此，在保 证转换效率的情况下降低衬底的成本就显得尤为重要，这也是今后太阳电池发 展急需解决的问题之一。 1 1 2 电池碎片封装工艺的提出和研究意义 晶体硅太阳电池以其完善的工艺和高效率占据着光伏市场的大部分份额。 然而，晶体硅电池片非常薄，而且易碎，在工业化生产中不可避免地产生电池 碎片。目前利用碎片的方法主要是清洗后重新熔化铸锭或拉单晶。这种回收利 用方法耗能高，材料利用率低。 这些电池碎片本身具有较高的光电转换效率，只是由于尺寸不规则，用常 规的封装技术无法将其封装成组件。 晶体硅太阳电池生产工艺中，一般采用丝网印刷的方法在电池表面制备细 密的收集栅做电子收集极，所有的电子收集极栅线通过一条或两条宽的引出极 连接起来。太阳电池表面产生的光电流经过收集极栅线到达引出极，从而得到 输出电流。对于面积较大，形状规则一致的太阳电池，这种结构制作工艺简单， 性能稳定可靠。但是，对于面积较小，形状不规则的电池碎片，无法用一两条 引出极将所有碎电池片上产生的光电流引出来。我们采用金属丝栅网作引出电 极，可以将电池碎片产生的光电流引出。用这方法可以直接将电池碎片封装成 太阳电池，使太阳电池碎片重新得到利用，变废为宝，不仅直接节约了大量的 能源，还能产生更多的电力，使太阳电池产业的整体成本降低。 2 第一章引言 第二节太阳电池碎片的封装工艺和碎片排布研究的意义 1 2 1 金属栅引出极封装工艺的基本过程 金属栅引出极封装工艺是基于丝网印刷技术和塑料压膜成型技术提出来 的，它采用丝网印刷技术的原理，用铜丝制成金属丝网，在p e t 的热熔状态下 将电池片、金属电极封装在一起。 主要的封装工艺工程如下： 一、清洗 实验所用的电池碎片是多晶硅太阳电池生产中破碎的电池片。由于是生产 过程中的废料，必然有大量浮尘附着在电池碎片上，为了达到更好的透光效果， 保证良好的金属电极接触，必须得对碎片进行清洗。一般采用去离子水和超声 做简单处理即可。图1 1 是清洗前后的电池碎片对比。 c a ) 精洗前的电池碎片( b ) 清洗后的电池碎片 囤l _ 1 电池碎片 二、筛选 这些作为废料处理的电池片，质量差异很大，所以需要对电池碎片进行筛 选。衡量太阳电池性能的主要参数有开路电压、短路电流、填充因子和转换效 率等。而电池片的开路电压测量简单，速度快，在一定程度上能够反映出电池 的质量。通常开路电压较大时，填充因子也较大，电池的转换效率较大【4 】。实验 3 第一章引言 中选择开路电压在5 0 0 m v 以上、电池片的大小在1 锄2 以上、银栅收集极栅线质 量好的电池片进行封装。 三、制作栅网 金属栅引出极用铜丝制成栅网，铜丝直径为0 1 5 m m ，表面浸锡。栅网间距 为5 m m ，栅网的一端焊接宽2 m m 、厚02 m m ，长度大于栅网的铜带作为输出电 极。栅网的间距小于电池片的尺寸，使每一个电池片都能被两根以上的金属栅 线覆盖。引出极栅线的排列方向与收集极栅线的捧列方向互相交叉，使每一个 收集极与引出极至少有一个交叉接触点，以便收集极中的电流能够通过引出板 输出。如图1 2 所示： - 圈1 2 丝网 四、碎片的铺排 将电池碎片平铺在金属丝栅网上。电池片收集极栅线的方向与金属丝的方 向基本保持垂直，使收集极栅线与金属栅交叉接触。电池片排列尽可能密集， 但不能有重叠。电池片排满后用另一个金属丝栅网盖在太阳电池片上面作为上 电极。上下栅网排列方向互相平行，并且交错2 5 m m ，这样可避免在电池碎片 的缝隙处上下栅网之间短路。 碎片的铺排在整个工艺过程中是一个难点问题，存在着如何解决丝网和每 一电池碎片的正银印刷栅线相交的问题，铺排速度的问题，铺排紧凑的问题， 碎片拼接合理性的问题，铺排过程中碎片相互重叠的问题。目前在实验室，我 们采用的是人工经验铺排，本文将针对计算机辅助排布进行研究。 第一章引言 五、真空条件下的加热封装 这是金属栅引出极封装工艺最关键的一步，它将直接影响整个封装的成败。 用两片厚度为02 1 r a m 的p e t 膜将金属丝栅网与电池片夹在中间，外面用两块 加热板夹紧，在p e t 膜与加热板之间垫上聚四氟乙烯薄膜，以防止p e t 膜与加 热扳粘在一起，放进真空室中，抽真空至0 1 p a 以下，然后进行加热。当温度达 到2 5 0 ( 2 以上时，熔化的p e t 在压力作用下将电池碎片之间的缝隙填满。当温 度达到2 7 0 时，停止加热，并立刻向真空室充气。在大气的压力下，可使p e t 与硅片和栅网之间接触更紧密，粘接更牢固。 六、裁剪成型 将取来的组件迅速冷却，然后将太阳电池片取出，将四周边缘溢出的p e t 剪齐，电池碎片被封装成1 2 0 x 6 0 m m 2 的太阳电池片。如图1 3 ： 图1 3 封粒成的太阳电池组件 1 2 2 电池碎片排布的研究意义 在金属栅引出极太阳电池封装过程中很重要的一步就是对不规则的电池碎 片进行紧密而又不重叠的排布。采用金属栅对太阳电池碎片的封装的目的是为 了降低成本，高效的回收利用太阳电池碎片，因而单位面积上电池碎片的空间 占有率越高，那么做成的组件效率就越高，材料的利用率也就越高。 人工的排布通常无法达到壤佳的效果，在计算机高速发展的二十一世纪， 借助于计算机进行辅助排布是一种必然趋势。本论文主要研究的就是利用计算 机对电池碎片的排布进行最优化的处理，旨在使电池组件的效率尽可能的高。 第一章引言 第三节计算机自动排布问题的研究现状 1 3 1 自动排布问题 自动排布问题( p a c k i n gp r o b l e m ) 又称自动布局，布局问题在工业生产中的 应用十分广泛，布局的构思是否合理直接影响到成本的高低，因此布局问题非 常重要。优化布局是指在给定尺寸的面积内，尽可能多的排放二维不规则图形， 使得空间利用率最高。从其计算的复杂性来看，前人已经证实布局问题属于非 确定多项式问题，即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 ) ，目前还没有 找到一个合理的算法来解决这一问题，因此排布问题具有重要的研究价值和应 用价值。本文提出的排布思想不仅适用于电池碎片的自动排布，在其他行业， 例如服装裁剪，板材加工，皮革加工等问题上也有很好的借鉴意义。 根据布局空间和待排物体的形状，二维排布问题可以分为以下两类： ( 1 ) 二维规则形状排布问题。例如：矩形件排布问题，装盘问题，玻璃下料， 一刀切问题等。 ( 2 ) 二维不规则形状排布问题。例如：服装自动排布，板材切割，装入问题 竺【5 】 寸o 由于长期以来，不规则形状的布局问题并没有得到很好的解决，因此人们 就在不断地寻找新的办法。现代人工智能中的启发式搜索算法、进化算法、遗 传算法、基于学习的方法都用于求解布局问题。 1 3 2 自动排布问题的研究现状 目前，对于不规则电池碎片的自动排布问题，尚没有人进行研究。然而由 于布局问题在上个世纪六十年代就已经在工业生产和计算机辅助设计中起重要 作用，二维布局问题己成为众多学者研究的重点。随着计算机技术，优化技术， 计算机图形学，人工智能，数据存储等的发展，人们对于二维布局问题有了更 深的研究。二维不规则图形的布局问题在各个不同的领域各有不同的特点，但 其解决问题的基本思想大致相同。 平面布局物体可分为规则形状物体( 如矩形、圆形) 和不规则形状物体。由于 不规则形状物体的形状复杂性在具体处理上的困难，使得现有的布局算法的处 6 第一章引言 理对象大多局限于规则形状物体，而将不规则形状物体简化为矩形、圆形等规 则几何形状物体。针对不同的布局问题，人们提出了不同的布局方法。大量不 规则物体的自动布局问题属于复杂布局问题。复杂布局问题是多约束多目标的 组合优化问题。由于布局知识( 约束、目标) 的多样性，这种组合优化问题无法用 单一的数值优化模型来表达，因而属于一种广义优化问题。下面分别介绍国内 外对排布问题研究的历史和现状。 1 3 2 1 国外研究概况 对于不规则物体的排布问题，目前所采用的解决方法归纳起来主要有以下 三种【7 1 。在实际研究中，这三种方法并不能截然加以区分，甚至有时候可以同时 使用两种或者两种以上的方法。 ( 1 ) 近似矩形法，即把单个或几个不规则物体组合成矩形单元，然后对矩 形单元进行排布。 1 9 7 6 年纽约大学的m a d a m o w i c z 在所发表的博士论文中利用矩形模块分两 阶段对二维不规则零件进行排布。随后，他和意大利p i s a 大学的a a l b a n o 合作， 做了进一步的研究与完善工作。1 9 7 7 年a a l b a n o 发表论文【8 1 ，论文的基本思想 是“两步法”和“人机交互法”。在这篇文章中，首先通过启发式方法与动态规划方 法的组合，由计算机产生一个初始排布方案，然后再通过人机交互的方法对其 进一步加以改进。 1 9 9 1 年，c h e o k 和n e e 9 】提出了用于造船业的三步自动排布方法。第一阶段， 称为形状处理，通过去除诸如倒角、圆角等小的特征简化零件轮廓。然后，将 这些简化的轮廓进行分类。第二阶段，根据先前的经验，匹配己分类的零件， 产生好的或紧密排列的矩形单元。第三阶段，采用矩形排布方法排列这些单元。 c y u z u t l o 】也曾于1 9 8 7 年提出了基于这种方法的用于服装裁剪的专家系统。在这 种方法中对于每一种服装类型，如男式衬衫，均给出一大套特定的规则。可是 对于这些规则的细节和应用并没有进行详细的讨论。 ( 2 ) 启发式推理方法，此方法模仿人工排布，定义大量的规则，使用启发 式推理方法，由计算机决定排布方案，不需要人的参与，但是组建这样的系统 需要丰富的经验。 7 第一章引言 f r e e m a n 于1 9 6 4 年【l l 】和后来的r a d a c k 与b a d l e r 于1 9 8 2 1 2 】年提出一个与排 布问题十分类似且很有趣的问题一拼板玩具问题。r a d a c k 与b a d l e r 提出了用边 界中- t b 极坐标编码代表零件轮廓的新颖方法来决定边界的匹配情况。但应用 f r e e m a n 或r a d a c k 与b a d l e r 所提出的方法是困难的，因为在排布中完全类似于 其所提出规则的轮廓匹配情况很少存在。 1 9 8 0 年，a a l b a n o 和s a p u p p o 1 3 】提出了一种自动排布方法，在论文中他们 使用了人工智能的典型启发式搜索策略，将排布问题转换为寻找一条最优路径 的问题。 1 9 8 9 年，c h u n g 及其合作者【1 4 】解决了复杂轮廓的钣金排布问题。他们使用 一系列技术定位零件，运用启发式搜索方法匹配零件的凹凸特征，分别对四个 基本位置( 9 0 。，1 8 0 。，2 7 0 。，3 6 0 。) 寻找最好的毗邻零件。一旦一个零件定 位，它的下一个最好毗邻零件被测定。但是，他并没有给出“最好的毗邻零件” 的定义。而且，对于四个基本方位的约束，虽然对轮廓近似于矩形的零件是合 理的，但对于形状更加复杂的零件，则需要具有更多的自由性。 ( 3 ) 智能优化法，即以最小浪费率为目标函数，采用诸如人工神经网络， 模拟退火算法，遗传算法等智能优化方法，在整个解空间中进行搜索。 近年来，国际上掀起了一股人工神经网络的研究热潮。神经网络的应用研 究取得了很大的成绩，涉及面非常广泛。就应用的技术领域而言有计算机视觉， 语言的识别、理解与合成，优化计算，智能控制及复杂系统分析，模式识别， 神经计算机的研制，知识处理，专家系统与人工智能。涉及的学科有神经生理 学，认识科学，数理科学，心理学，信息科学，计算机科学，微电子学，光学， 生物电子学等【l5 1 。人工神经网络独特的结构和处理信息的方法，使其在许多应 用领域中取得了显著的成效，能够解决些传统计算难以解决的问题。 一些学者已经将人工神经网络技术应用到排布领域中，但在这方面所进行 的研究还处于探索阶段。下面作一些简要介绍： m s r i r a m 和s m k a n g ( 1 9 9 0 ) 1 6 j 利用改进的h o p f i e l d 人工神经网络解决了二 维模块的线路排布问题。文章以总线长最小为目标函数来构造排布模型。通过 使网络的互连权矩阵依赖于网络的状态，并且在能量函数中包含四次项来改造 h o p f i e l d 神经网络。经过这种改造后，原来的二维排布问题被分解成两个一维问 题。同时文章中采用了最小排布布局的分层方法，使得网络的大小与模块的数 目呈线性关系。计算结果表明，这种方法与般的启发式方法相比有较多优点。 8 第一章引言 c x z h a n g 和d a m l y n s k i ( 19 9 0 ) t 1 7 j 运用k o h o n e n ( 19 8 2 ) 和耻t e r ( 19 8 6 ) 提出的 人工神经网络模型的拓扑映射特征解决大规模集成电路的排布问题。文章将集 成电路中排布问题所具有的特性与神经网络模型的映射特性结合在一起。通过 输入空间与输出空间的拓扑映射关系来建立可移动模块与芯片上槽之间的关 系。并且用c 语言编程，在v a x1 1 7 5 0 计算机上实现了所提出的算法。所得的 排布结果与传统的排布算法的结果相比，在效率和时间上均有所提高。 目前，人们己经将模拟退火算法运用到二维排布问题中。模拟退火算法是 一种著名的全局优化算法【18 1 ，是采用概率搜索方法的组合优化技术。模拟退火 算法是基于m o n t ec a r l o 迭代求解的一种启发式随机搜索法，它非常适合解决具 有大范围搜索空间的问题。 例如，s h a h o o k a r 和m a z u m b e r ( 1 9 9 1 ) 1 内j 运用这种算法解决了大规模集成电路 中的布局问题。h e r a g u 和a l g a ( 1 9 9 2 ) t 2 0 】利用模拟退火算法解决印刷中的排布问 题。j a i n f e n y e s 以及r i c h t e r ( 1 9 9 2 ) z 1 j 用此算法解决了二维冲裁零件排布问题。 c h o ( 1 9 9 3 ) t 2 2 】也对钣金冲裁零件排布问题加以解决。 为了验证模拟退火算法的搜索能力，k a d o w n s l a n d ( 1 9 9 3 ) t 2 3 】用模拟退火算 法对许多的组合优化问题进行了试验验证。结果表明，模拟退火算法是一种有 效的全局搜索方法，并说明了该算法的基本要求是定义适当的邻域结构。邻域 结构是决定在搜索过程中所产生的新解是被接受还是被放弃的主要参数，所产 生的解的好坏对此参数的选取很敏感。同时，作者把模拟退火算法应用到包装 领域的排布问题中，进行了一系列试验，用来证明模拟退火算法解决此问题的 有效性。并提出了最合理的邻域结构和最优参数的选取问题。 上述文献中单纯采用了模拟退火算法或者遗传算法，虽然在理论上可以搜 索到全局最优方案，但是单纯采用模拟退火算法或遗传算法具有一个致命的缺 点，就是运算速度慢，效率低。 1 3 2 2 国内研究情况 国内对优化排布的研究尽管起步较晚，但也做了大量工作，常用的方法主 要源于苏联学者a k h y p b a p a h j i o b 的板材冲压最佳排料图编制过程的自动 化。针对排布问题的不同方面，最早提出的有加密点法，人机对话法，随后 出现点阵判交法：平行线分割一步平移法等【2 4 2 6 1 。 9 第一章引言 1 9 9 2 年，李新军、熊火轮等发表点阵判交一一种计算机自动排样系统设 计的新方法 2 刀。文章介绍了一种新的非几何判交方法。指出判断两个几何元 素是否存在交点，即求交，是排布的基础性工作之一。其方法的优劣直接影响 着排布程序的可靠性和效率。判断两个几何元素是否相交，从图形上看是十分 容易的，但运用解析法在计算机上用程序实现却很费周折。文章论述了屏幕光 栅点阵判交的中心思想是判断某一直线所要经过的点是否已经被打亮。 1 9 9 8 年，华中理工大学的董长双、杨楚民、宾鸿赞发表了冲裁零件二维 排样优化【2 8 1 。文章提出了在以往的冲裁件优化排布的计算机求解方案中，人 们一般将卷板当作无限长的条料或将有限长、宽的板料裁成若干条等宽度的条 料，所采用的优化模型也是建立在此基础上的。当将有限长宽的整体板料在冲 压设备上进行x ，y 轴双向送料冲裁时，上述建立的模型将不再适用。这篇文章 给出了以在有限长、宽的整体板料上能冲裁出的最大样件个数为目标的整体优 化模型及算法。 浙江大学的周泓一、金廷赞的二维不规则形状的最优布局问题一计算机 辅助服装裁片自动排料系统 2 9 】，将计算机图形学和人工智能相结合，运用人 工智能的启发式方法把裁片的二维最优布局问题转化为在一个状态空间中寻找 一条最优路径的问题。将从初始状态出发的所有可能达到的状态集合视为个有 向图，其中节点对应状态，边对应算子，将问题视为一个寻找从初始节点到日 标节点路径的搜索过程。 上海交大的杨世胜、吕荣发表了服装自动排料初探【3 0 j ，提出了用服装 样板几何图形的数学模型来实现图形的输入，以及对图形进行各种判断、处理。 其最优排布方案的材料利用率达9 2 。判断板样是否相交，贯穿于整个排布过 程。 第四节基于启发式搜索算法的可行性 在金属栅引出极封装工艺中，电池碎片的排布工作主要是指将一系列形状 各异的不规则的太阳电池片在一个矩形区域内按最优方式进行排布，提高空间 的利用率。即矩形区域是固定的，要求在该区域内排布尽可能多的电池片。 1 0 第一章引言 对于这类问题的表述一般是：将一系n - 维不规则形状的电池片s i ，s 2 ，s n 合理的排列在矩形区域s 内，使区域面积的利用率最高，并要满足下列约束条 件： 1 s i ，s j 互不重叠；f ，歹= 1 ，2 ，n ；i j ； 2 s i 必放在s 内； 3 必须满足s i 上的银栅和金属栅线有交叉。 对于电池碎片的排布研究是本文的重点。由于碎片的自动排布问题属于n p ( 非多项式时间问题) 完全问题，随着待排碎片的数量的增加，解空间成指数 倍地扩大，会出现组合爆炸现象，即时间的无限延长。用动态规划、分支界定 等基于穷举思想的算法都无法解决。 采用启发式搜索算法的原因之一是启发式搜索算法是经典的状态空间的求 解算法；第二，现在启发式搜索算法又重新焕发起生命力，许多新的研究成果 和结论是原来的经典算法得到了拓展；第三，由于传统的人工智能方法遇到了 种种难以克服的困难以及计算机速度的提高，计算机网络并行分布式系统的普 及，以及计算机的速度不再是制约其发展的因素。 目前对于不规则物体的排布的求解方法比较认同的是采用启发式搜索的方 法。本文第二章就n p 完全问题的描述和常用的解决方法进行了详细的介绍。第 三章则主要针对电池碎片的特殊图形进行排布前的预处理，对排布过程中用到 的检测算法进行了研究。第四章是本文的核心内容，对电池碎片的排布进行了 分类说明，给出了算法流程和实现效果图。第五章对本文采用的算法进行了总 结，并给出了下一步研究的建议。 第二章自动排布算法 第二章自动排布算法 在工业生产中所需要解决的自动排布问题，最终都要归结到数学模型的求 解问题。本章将会重点介绍解决自动排布问题的常用算法。 2 1 1n p 完全问题的引出 第一节n p 完全问题 构造算法的目的是能够解决问题的所有实例而不单单是某一个实例。问题 是需要回答的一般性提问，通常含有若干个满足一定条件的参数。问题通过下 面的描述给定：( 1 ) 描述所有参数的特性，( 2 ) 描述答案所满足的条件。 问题中的参数赋予了具体值的例子称为实例。衡量一个算法的好坏通常是 用算法中的加、减、乘、除和比较等基本运算的总次数c ( ，) 同实例i 在计算机 计算时的二进制输入数据( 输入规模长度d ( i ) ) 的大小关系来度量。算法的计算 复杂度为： c ( j ) = 厂( d ( 聊( 2 1 ) 假设问题和解决该问题的一个算法己经给定，若给定该问题的一个实例i ， 存在多项式函数g ( x ) ，使得计算时间： c ( ，) = 口g ( 三( ) )( 2 2 ) 成立，我们称该算法对实例i 是多项式时间算法( p o l y n o m i a lt i m e a l g o r i t h m ) 。若存在g ( x ) 为多项式函数且对该问题任意的一个实例i ，都有( 2 2 ) 成立，则称该算法为解决该问题的多项式时间算法。当不存在多项式函数g ( x ) 使 得上式成立时，称相应的算法是非多项式时间算法，或指数时间算法( e x p o n e n t i a l t i m ea l g o r i t h m ) 。 1 2 第二章自动排布算法 对于给定的一个优化问题，若存在一个求解该问题最优解的多项式时间算 法，则称给定的优化问题是多项式可解问题，或者简称多项式问题，所有多项 式问题集记为( p o l y n o m i a l ) 。 评价一个算法的依据是该算法在最坏实例下的计算时间与实例输入模式的 关系： c ( z ) 兰口g ( e ( 助或者c ( z ) = o g ( d ( o )( 2 3 ) 存在多项式函数g ( x ) 满足上式时，算法为多项式算法。存在多项式算法的 问题集合为多项式问题类( p ) 。 比多项式问题类更广泛的一个问题类是非确定多项式( n o n d e t e r m i n i s t i c p o l y n o m i a l ，简称n p l 问题类。n p 类是通过判定问题引入的。如果一个问题的 每一个实例只有“是”或“否”两种答案，则称这个问题为判定问题 ( d e c i s i o n r e c o g n i t i o n f e a s i b i l i t yp r o b l e m ) 。称有肯定答案的实例为“是”实例 ( y e s i n s t a n c e ) 。称答案为“否”的实例为“否”实例或者非“是”实例( n o i n s t a n c e ) 。考 虑将求解判定问题的算法分为两个阶段： ( 1 ) 猜测阶段，求出或猜测出该问题的一个解； ( 2 ) 检查或验证阶段：一旦解已经选定，将猜测的解作为输入，验证此解 是否为该示例“是”的答案。我们称实例“是”回答的解为实例的可行解，否则称为 不可行解。 若存在一个多项式函数g ( x ) 和一个验证算法h ，对一类判定问题a 的任何 一个“是”实例i ，都存在一个字符串s 是i 的可行解，满足其输入长度d ( s ) 不超 过g ( d ( ，) ) ，其中d ( i ) 为i 的输入长度，且算法h 验证s 为实例i 的可行解的结 算时间f ( h ) 不超过g ( d ( 助，则称判定问题a 是非确定多项式的。构造字符串 的过程及验证算法h 一起构成一个算法，成为非确定多项式时间算法。所有非 确定多项式问题的集合用n p 表示，一般认为p n p 。 已知判定问题a l 和a 2 ，若存在多项式函数蜀( x ) 和g ：( x ) ，使得对a l 的任 何实例i ，在多项式时间内构造a 2 的一个实例，其输入长度不超过g ，( d ( 厂) ) ，并 对a 2 的任何一个算法h 2 ，都存在问题a l 的一个算法h l ，使得h l 算法调用h 2 算法且使得计算时间： 厶，( d ( ，) ) 9 2 ( 厶：( d ( ，) ) ) 1 3 ( 2 4 ) 第二章自动排布算法 其中厶。( d ( 助和厶：( x ) 分别表示算法h 1 和h 2 的计算时间与实例输入长度x 之间的关系，则称问题a l 多项式归约为问题a 2 。 对于判定问题a ，若a n p 且n p 中的任何一个问题可在多项式时间内规 约为a ，则称a 为n p 完全问题( n p c o m p l e t e 或n p 完全) ，可以表示为a | p c 【3 1 】 o 2 1 2 解决n p 完全问题的思路 n p 完全问题是n p 类中最困难的问题。对于n p 完全问题，有证据表明， 此类的许多重要问题，至今无法找到多项式算法，因此不能被快速的解决。因 而，求其有效的近似解法是必由之路，关于n p 完全问题的近似解法还有待进一 步发展。对于这类问题，以目前己成熟的计算理论和算法，或者根本无法求解， 或者其求解的计算量是爆炸性的，即使用最快的计算机进行计算，所花费的机 时和费用将不是人们所能接受的。 解决n p 完全问题虽然是相当困难的，但是n p 完全问题又是人们常常碰到 的问题，所以人们还是千方百计采用各种方法来解决或者近似解决n p 完全问 题。 目前，解决n p 完全问题一般有下面四种思路： ( 1 ) 采用启发式的( h e u r i s t i c ) 方法。采用问题的相关信息作为启发，在局部 最优的情况下来近似解决n p 完全问题，最后的结果往往不是最优的，但是却是 足够“好的”。 ( 2 ) 近似地而不是精确地解决问题。一般的，可以找到一个比较快的算法， 但是它不能精确的解决n p 完全问题，而只能证明最后的结果很接近n p 完全问 题的结果。 ( 3 ) 采用指数级时间的解决方法。不管怎样，如果要精确地解决n p 完全 问题的话，可以编一个需要花指数级时间的算法程序来解决n p 完全问题，这样 就不必担心最后是否能够得到最优的结果了。 ( 4 ) 提取问题的一个较好模型，然后进行解决。当在对具体n p 完全问题 进行抽象化时，往往忽略了看上去好像不重要的而在现实处理中又很复杂的部 分或者因素，从而简化了问题。不过看上去不重要的部分或者因素也许正是重 1 4 第二章自动排布算法 要的部分或者因素，很可能会把n p 完全问题变成了非n p 完全问题了，改变了 问题的本质 3 2 】。 2 1 3 排布问题的实质 排布的实质性问题就是一种一维或二维的布局问题，也就是一个最优化的 问题。现有的算法有许多种，一般根据计算的复杂度来判断算法的好坏。 算法对时间和空间的需要量称为算法的时间复杂度和空间复杂度。算法或 问题的复杂度一般是问题规模m 的函数，时间复杂度记为丁( ，z ) 。在算法分析和 设计中，把求解问题的关键操作，如加法、乘法、比较等运算指定为基本操作， 然后把算法执行基本操作的次数定义为算法的时间复杂度，算法执行期间占用 的存储单元则定义为算法的空间复杂度。在排布优化问题中，比较和搜索被指 定为基本操作，基本操作的执行次数随问题规模的增长以一定的方式增长。 在分析复杂度时，可以求出算法的复杂度函数f ( m ) ，也可以很方便地用复 杂度函数主要项的阶d ( 厂( m ) ) 表示。若算法a 的时间复杂度l ( 聊) 是m 的多项 式函数，则称算法a 为多项式时间算法，一般称之为好的算法。时间复杂度不 能包含于多项式时间的算法统称为指数时间算法。 对于一维的布局情况( 如条材的下料问题) 可以假设用于布局的零件个数为 ，1 、i m ，则其最大的布局方式为竺兰。若以布局方式间的比较为基本操作，则需要 2 螋一1 进行的基本操作数量是 2 ，若以遍历所有布局方式的算法求其最优解， 兀研) ：亟型一1 则时间复杂度为、7 2 ，若是考虑二维布局和三维布局的情况，其时 间复杂度将更差。电池碎片的排布问题是一个二维布局问题，求解排布的问题， 也就是找出兼顾解的质量及运行时间的较好的算法。 第二节常见的几种算法的介绍 解决布局问题的现代化方法中经常被人们采用的是遗传算法、模拟退火算 法和启发式算法。下面分别做一下介绍。 1 5 第二章自动排布算法 2 2 1 遗传算法 遗传算法【3 3 1 是仿真生物遗传学和自然选择机理，通过人工方式所构造的一 类搜索算法，从某种程度上说遗传算法是对生物进化过程进行的数学方式仿真。 霍兰德( 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 da r t i f i c i a ls y s t e m s ) ) 首次提 出遗传算法，并主要由他和他的学生发展起来的。 生物种群的生存过程普遍遵循达尔文进化准则，群体中的个体根据对环境的 适应能力而被大自然所选择或淘汰。进化过程的结果反映在个体的结构上，其 染色体包含若干基因，相应的表现型和基因型的联系体现了个体的外部特性与 内部机理间逻辑关系。通过个体之间的交叉、变异来适应大自然环境。生物染 色体用数学方式或计算机方式来体现就是一串数码，仍叫染色体，有时也叫个 体；适应能力是对应着一个染色体的一个数值来衡量；染色体的选择或淘汰则 按所面对的问题是求最大还是最小来进行。 遗传算法已用于求解带有应用前景的一些问题，例如遗传程序设计、函数 优化、排序问题、人工神经网络、分类系统、计算机图像处理和机器人运动规 划等。 遗传算法类似于自然进化，通过作用于染色体上的基因寻找好的染色体来 求解问题。与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的 仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适 应性好的染色体有更多的繁殖机会。在遗传算法中，通过随机方式产生若干个 所求解问题的数字编码，即染色体，形成初始群体；通过适应度函数给每个个 体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作， 经过遗传操作后的个体集合形成下一代新的种群，对这个新种群进行下一轮进 化。这就是遗传算法的基本原理。 下面就是遗传算法思想： ( 1 ) 初始化群体； ( 2 ) 计算群体上每个个体的适应度值； ( 3 ) 按由个体适应度值所决定的某个规则选择将进入下一代的个体； ( 4 ) 按概率p 。进行交叉操作； ( 5 ) 按概率p 。进行突变操作； ( 6 ) 没有满足某种停止条件，则转第( 2 ) 步，否则进入( 7 ) ； 1 6 第二章自动排布算法 (