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

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

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

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

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