二維不規(guī)則圖形的排樣算法.pdf

1、優(yōu)化排樣問題是指尋求二維圖形在特定長度，寬度區(qū)域內(nèi)的擺放盡可能多，以使區(qū)域的利用率達到最優(yōu)。它在服裝、皮革制品、體育用品、機械等制造行業(yè)中都有應用。國內(nèi)有成千上萬家這樣的企業(yè)，大部分企業(yè)仍處于手工排樣下料階段，下料利用率較低，造成原材料的浪費。因此有效提高原材料的利用率，降低生產(chǎn)成本，是增加企業(yè)效益的有效途徑之一。二維不規(guī)則圖形的優(yōu)化排樣問題是一個在許多生產(chǎn)實踐中有關鍵應用的重要問題，也是一個計算機科學和運籌學中的基本問題。在理論上屬于

2、NP--完全(困難)問題，因為存在實際形狀的復雜性和計算上的復雜性，求解十分困難。 目前研究較多的是規(guī)則零件(如矩形)的排樣問題，對不規(guī)則件的研究較少。對不規(guī)則件的處理基本上是基于規(guī)則零件排樣處理的矩形近似方法和對不規(guī)則零件直接處理兩種方法。本文應用一種名為擠壓算法的近優(yōu)算法。它是一種基于對不規(guī)則零件直接處理的方法。使用該算法能提高材料的利用效率，它通過在排樣過程中對相鄰的兩個和兩排的圖形進行向左，向下的移動，通過減少它們之間的

3、空隙來實現(xiàn)此目的。在排樣計算的過程中，如何找到零件之間在什么位置靠接緊密并且不重疊是一個關鍵的問題。此外，它會利用到一些與圖形學相關算法。以下為它的基本步驟： 1、通過預處理，將所有的待擺放的多邊形分別繞它們的重心旋轉(zhuǎn)一個角度，從而可以得到它們最佳包絡矩形。 2、計算相鄰的兩個和兩排的圖形的最小距離。 3、根據(jù)這個最小距離，移動它們，從而減少它們之間的空隙。 但僅有此算法不能對整個排樣問題進行優(yōu)化處理。因

4、為它要求在實際的擺放前必須得到一個多邊形的擺放序列。它必須和某種具有全局搜索能力能提供這種擺放序列的算法相結合運用，才能達到我們所需的效果。遺傳算法是一種很好的全局優(yōu)化算法。它以達爾文的生物進化論為啟發(fā)而創(chuàng)建，借助選擇、交叉、變異等操作逐步逼近最優(yōu)解。具有隱含并行機制和自適應性。本文對遺傳算法的發(fā)展現(xiàn)狀進行分析。在對基本遺傳算法的優(yōu)缺點進行分析后，主要針對它的局部搜索能力差，全局搜索速度較慢和早熟現(xiàn)象提出改進。主要是針對遺傳算法進行遺傳