基于遺傳算法的二維不規(guī)則圖形排料問(wèn)題的研究與應(yīng)用.pdf

1、排料問(wèn)題應(yīng)用范圍非常廣泛，如服裝行業(yè)、皮革行業(yè)、機(jī)械行業(yè)。提高板材利用率能降低企業(yè)的生產(chǎn)成本，會(huì)給企業(yè)帶來(lái)經(jīng)濟(jì)效益，所以，排料問(wèn)題的研究具有重要的經(jīng)濟(jì)價(jià)值。二維不規(guī)則排料問(wèn)題具有很高的復(fù)雜性，屬于NP完全問(wèn)題，即不能在多項(xiàng)式時(shí)間內(nèi)找到問(wèn)題的最優(yōu)解，所以，排料問(wèn)題的研究具有重要的理論價(jià)值。 遺傳算法(GA)是一種全局優(yōu)化的現(xiàn)代啟發(fā)式算法，通過(guò)交叉、變異來(lái)避免陷入局部極小。與傳統(tǒng)優(yōu)化方法相比，遺傳算法僅僅利用個(gè)體的適應(yīng)度進(jìn)行群體的進(jìn)

2、化，不需要優(yōu)化模型中目標(biāo)函數(shù)和約束函數(shù)的導(dǎo)數(shù)信息，因而具有極強(qiáng)的魯棒性，適合于解決各種優(yōu)化問(wèn)題。本文從遺傳算法的產(chǎn)生背景、基本思想以及收斂性理論方面進(jìn)行了細(xì)致的說(shuō)明。 本文將遺傳算法應(yīng)用到二維不規(guī)則排料領(lǐng)域中，得到了很好的效果。出于對(duì)帶圓弧圖形的考慮，本文應(yīng)用了自動(dòng)提取零件數(shù)據(jù)的算法和求解逼近多邊形的方法。 在自動(dòng)排料計(jì)算的過(guò)程中，如何找到零件之間在什么位置靠接緊密并且不重疊是一個(gè)關(guān)鍵的問(wèn)題。為了減少多邊形之間重疊性判斷

3、的計(jì)算量，提高算法效率，在本文中采用了臨界多邊形算法，并對(duì)現(xiàn)有的臨界多邊形算法進(jìn)行了改進(jìn)，主要是針對(duì)兩個(gè)凹多邊形臨界多邊形的改進(jìn)，首先通過(guò)將一個(gè)凹多邊形進(jìn)行凸化，然后求出凹多邊形和凸多邊形的臨界多邊形，再把凸化得到的邊轉(zhuǎn)化成對(duì)應(yīng)的凹邊，進(jìn)而得到兩個(gè)凹多邊形的臨界多邊形。由于實(shí)際生產(chǎn)中往往需要用到多張板材，所以本文也考慮了多張板材的排料。 此外，本文設(shè)計(jì)了自動(dòng)排料算法中其它一些相關(guān)的圖形學(xué)算法，如凸包算法和合成多邊形算法。