不規(guī)則樣片排樣與快進(jìn)路徑智能優(yōu)化方法及其應(yīng)用.pdf

1、二維不規(guī)則排樣是一個(gè)典型的平面優(yōu)化布局問題，母板和樣片為平面不規(guī)則形狀的多邊形，其目標(biāo)是在母板上尋求一個(gè)合理的樣片布局方案，使母板的利用率最大。需要滿足的約束條件為：樣片在母板內(nèi)部布局；樣片相互之間不發(fā)生重疊且可以以一定的角度進(jìn)行旋轉(zhuǎn)。對(duì)于一些加工企業(yè)，提高排樣的效率可以帶來巨大的經(jīng)濟(jì)效益，因此排樣在服裝裁剪、皮革加工、玻璃切割等領(lǐng)域有著廣泛的應(yīng)用。不規(guī)則排樣問題是一類具有極高計(jì)算復(fù)雜性的NP-hard問題，吸引了大量的學(xué)者對(duì)該問題進(jìn)行

2、廣泛的研究。目前二維不規(guī)則排樣中存在的主要問題有：臨界多邊形（No Fit Polygon，NFP）的快速計(jì)算、樣片布局速度、排樣利用率及樣片加工快進(jìn)路徑優(yōu)化等問題。針對(duì)以上主要問題，本論文做了如下幾個(gè)方面的工作：
　?。?）針對(duì)判斷樣片是否重疊需要大量幾何計(jì)算時(shí)間的問題，提出了一種改進(jìn)的基于移動(dòng)碰撞法的臨界多邊形生成算法，提高了生成臨界多邊形的計(jì)算速度，時(shí)間復(fù)雜度為O((m+n)mn)。改進(jìn)算法是以Burke等提出的移動(dòng)碰撞算法

3、為基礎(chǔ)，使用簡(jiǎn)便的向量運(yùn)算進(jìn)行靠接位置檢測(cè)；減少了求解移動(dòng)方向和可移動(dòng)向量的判定情況；提出了一種計(jì)算最小移動(dòng)距離的方法；簡(jiǎn)化了生成臨界多邊形的步驟。改進(jìn)后的算法有效地降低了幾何計(jì)算的復(fù)雜性，減少了生成臨界多邊形的計(jì)算時(shí)間。實(shí)驗(yàn)結(jié)果表明新的算法是有效可行的，計(jì)算速度較Burke算法有了較大的提高，為不規(guī)則排樣問題往智能優(yōu)化方向發(fā)展奠定了幾何計(jì)算的基礎(chǔ)。
　?。?）提出了基于形心臨界多邊形的布局策略和啟發(fā)式排樣算法，提高了樣片的布局速

4、度，時(shí)間復(fù)雜度為O(n)，使母板利用率明顯提高。對(duì)現(xiàn)有的不規(guī)則樣片布局策略進(jìn)行改進(jìn)，通過生成樣片的形心臨界多邊形，提出將形心NFP中最低頂點(diǎn)位置作為樣片的放置位置的布局策略，建立了以最大化母板利用率為優(yōu)化目標(biāo)的數(shù)學(xué)模型；將布局策略與爬山算法相結(jié)合，提出了一種啟發(fā)式排樣算法。不規(guī)則排樣基準(zhǔn)問題的測(cè)試結(jié)果表明啟發(fā)式排樣算法使母板的利用率得到明顯提高。
　?。?）提出了一種基于量子進(jìn)化算法的智能排樣算法，使排樣具有了較強(qiáng)的全局優(yōu)化能力，

5、取得了比啟發(fā)式排樣算法更優(yōu)的排樣效果。結(jié)合二維不規(guī)則排樣問題的具體特點(diǎn)，算法設(shè)計(jì)了基于排樣編號(hào)序列和旋轉(zhuǎn)角度索引序列的量子染色體個(gè)體，并以概率的方式進(jìn)行量子觀測(cè)；為改善量子進(jìn)化算法的性能，采用自適應(yīng)調(diào)節(jié)方式更新量子個(gè)體；通過構(gòu)造啟發(fā)式算法生成初始種群保證種群的質(zhì)量。基準(zhǔn)用例的測(cè)試結(jié)果和算法對(duì)比實(shí)驗(yàn)，驗(yàn)證了所提算法的可行性和有效性，表明智能排樣算法具有較強(qiáng)的全局優(yōu)化能力，能夠取得比啟發(fā)式算法更好的排樣效果。
　　（4）針對(duì)樣片加工快

6、進(jìn)路徑優(yōu)化問題，提出了一種基于自適應(yīng)遺傳模擬退火算法的求解方法，能夠有效地優(yōu)化快進(jìn)路徑，提高了裁剪機(jī)的加工效率。為提高遺傳算法的局部搜索能力，在進(jìn)化過程中融入模擬退火的Boltzmann更新方法；采用自適應(yīng)的方式對(duì)交叉和變異概率進(jìn)行調(diào)整；根據(jù)多輪廓加工最優(yōu)子結(jié)構(gòu)的特征，設(shè)計(jì)了基于動(dòng)態(tài)規(guī)劃法的個(gè)體適應(yīng)度評(píng)價(jià)方法。應(yīng)用實(shí)例驗(yàn)證了算法可有效構(gòu)建刀具的快進(jìn)路徑，標(biāo)準(zhǔn)問題測(cè)試結(jié)果表明了算法具有較高的優(yōu)化性能。
　　（5）在理論研究工作的基礎(chǔ)