基于知識(shí)進(jìn)化與自然進(jìn)化的優(yōu)化排樣算法研究

包夢(mèng)華，唐 平，朱章松，盧齊飛

（廣東工業(yè)大學(xué) 自動(dòng)化學(xué)院，廣東 廣州510006）

0 引 言

優(yōu)化排樣算法是指根據(jù)零件的特征設(shè)計(jì)一種算法，將規(guī)則或是不規(guī)則的零件按照算法的要求盡可能緊密的排放在一起，知識(shí)進(jìn)化和自然進(jìn)化是算法設(shè)計(jì)的依據(jù)。同時(shí)要求排樣過(guò)程中零件必須排放在板材內(nèi)，各個(gè)零件互不疊加，并滿(mǎn)足一定的工藝要求，使板材的利用率最高。

20世紀(jì)末期，隨著遺傳算法的成熟，許多學(xué)者開(kāi)始將它應(yīng)用于零件排樣中，取得了一些顯著成果。遺傳算法是模擬自然進(jìn)化的一種全局搜索算法，具有簡(jiǎn)單實(shí)用、魯棒性強(qiáng)的優(yōu)點(diǎn)，但是具體運(yùn)用中還存在一些不足。例如文獻(xiàn)［1］、文獻(xiàn) ［2］都是運(yùn)用常見(jiàn)的 “輪盤(pán)賭”選擇，隨機(jī)性太強(qiáng)。文獻(xiàn) ［3］利用遺傳算法和碰撞算法混合求解沖裁件自動(dòng)優(yōu)化排樣，碰撞算法可以大大提高板材的利用率，同時(shí)也大幅提高時(shí)間復(fù)雜度。文獻(xiàn) ［4］針對(duì)大規(guī)模零件和不規(guī)則石材下料優(yōu)化排樣問(wèn)題，提出了改進(jìn)的遺傳算法優(yōu)化排樣方法，提出了基于材料利用率、排樣圖的高度和排布最高點(diǎn)中最左邊頂點(diǎn)的x坐標(biāo)3個(gè)因素結(jié)合的適應(yīng)度函數(shù)，將適應(yīng)度函數(shù)的考慮因素大大擴(kuò)展，有效地提高了算法的搜索效率，本文在此基礎(chǔ)上又添加了一個(gè)考慮因素——零件排樣后的圖形重心，使排樣結(jié)果更盡如人意。上述工作都是為了提高板材利用率而忽視了時(shí)間復(fù)雜度，過(guò)分的強(qiáng)調(diào)板材利用率的提高并不能彌補(bǔ)時(shí)間復(fù)雜度帶來(lái)的損失，所以本文換了一種思維方式，在保證板材利用率不降低的情況下，大幅降低時(shí)間復(fù)雜度，借助時(shí)間的急劇縮短，提高整體排樣的效率。

本文基于提高不規(guī)則零件排樣效率的考慮，提出了基于知識(shí)進(jìn)化與自然進(jìn)化的優(yōu)化排樣算法。該算法的重點(diǎn)是大大提高選擇速度，利用知識(shí)規(guī)則和適應(yīng)度函數(shù)相結(jié)合的選擇方法，同時(shí)采用重心最低的排樣策略。實(shí)驗(yàn)數(shù)據(jù)分析得出：該算法不僅提高了板材利用率，還大大降低了算法的時(shí)間復(fù)雜度。

一是零件數(shù)量較大時(shí)；二是零件的形狀比較復(fù)雜，不能完全歸類(lèi)時(shí)，都會(huì)延長(zhǎng)計(jì)算時(shí)間，排樣的利用率也會(huì)隨之降低。從這兩個(gè)方面著手，以期達(dá)到提高排樣效率的目的。

1 知識(shí)進(jìn)化中規(guī)則建立原則

知識(shí)規(guī)則的建立是降低時(shí)間復(fù)雜度的一個(gè)重要方法，將所有的零件先按照知識(shí)規(guī)則進(jìn)行篩選，可以有效地避免對(duì)不符合要求的零件進(jìn)行多余的操作，浪費(fèi)時(shí)間。

知識(shí)進(jìn)化的規(guī)則包括：零件邊界判定、板材利用率判定和零件重疊判定。每次首先用知識(shí)規(guī)則對(duì)零件進(jìn)行初步選擇，同時(shí)符合知識(shí)進(jìn)化3個(gè)規(guī)則的零件接受適應(yīng)度函數(shù)的第二次選擇。

（1）判斷零件的邊界是否都處于板材內(nèi)部，選擇邊界不超過(guò)板材邊界或是與板材邊界重合的零件。

圖1可知，零件在板材內(nèi)部的分布情況有：

1）在板材內(nèi)部且不與板材相交；

2）在板材內(nèi)部，與板材邊界有交點(diǎn)。

圖1 零件是否在板材內(nèi)部的判斷

通過(guò)比較線條：A、B、C、D 和E，可得出結(jié)論：通過(guò)任意橫坐標(biāo)畫(huà)一條垂直線與板材有兩個(gè)任意交點(diǎn)M、N 與零件有兩個(gè)任意交點(diǎn)P 、K，P、K 到原點(diǎn)的距離大小總是大于板材上的縱坐標(biāo)最大的點(diǎn)M 到原點(diǎn)的距離并且小于板材上縱坐標(biāo)最小點(diǎn)N 到原點(diǎn)的距離。板材上4個(gè)點(diǎn)的關(guān)系符合式（1），可以判斷零件邊界沒(méi)有超過(guò)在板材邊界

其中，m、n為處于板材左右邊界之間的任意自然數(shù)，p≤y2≤k，xi為任意橫坐標(biāo)，ym為垂直線與板材相交時(shí)縱坐標(biāo)最大的交點(diǎn)的縱坐標(biāo)，yn為垂直線與板材相交時(shí)縱坐標(biāo)最小的交點(diǎn)的縱坐標(biāo)，y2為垂直線與零件相交時(shí)的交點(diǎn)的縱坐標(biāo)。

（2）判斷零件是否重疊

利用像素格式的位圖進(jìn)行零件之間的重疊檢測(cè)，首先將零件用像素格式的位圖表現(xiàn)出來(lái)，如圖2所示， “1”代表此處有零件覆蓋， “0”代表此處沒(méi)有零件覆蓋。圖2中的 “1”像素表達(dá)了一個(gè)不規(guī)則四邊形的零件。

圖2 像素格式表達(dá)的零件

假如兩個(gè)或是多個(gè)零件都覆蓋了相同的像素格，就是兩個(gè)或是多個(gè)零件在相同的像素格上都表現(xiàn)出 “1”，就說(shuō)明零件發(fā)生了重疊。運(yùn)用像素格式來(lái)檢測(cè)零件還是很比較節(jié)省時(shí)間的，首要條件是將矢量圖轉(zhuǎn)換成像素格式的位圖。

在用像素格式的位圖進(jìn)行重疊檢測(cè)時(shí)，像素格過(guò)大，檢測(cè)結(jié)果不準(zhǔn)備；像素格過(guò)小，勢(shì)必增加算法的事件復(fù)雜度和空間復(fù)雜度。在實(shí)際劃分像素格時(shí)，會(huì)出現(xiàn)一些意想不到的情況：兩個(gè)多邊形并不相交，但是由于另個(gè)多邊形占據(jù)了同一個(gè)像素格，根據(jù)像素格格判斷法的定義，兩個(gè)多邊形就是被判為相交。假如網(wǎng)格劃分的足夠精細(xì)，則可以判斷兩個(gè)多邊形并不重疊。

判斷像素格內(nèi)兩個(gè)多邊形是否重疊，可以利用查漏補(bǔ)缺法對(duì)重疊情況進(jìn)行檢測(cè)。這樣就不用對(duì)所有的像素格都進(jìn)行更細(xì)的劃分，只需要對(duì)無(wú)法判斷的像素格進(jìn)行細(xì)分即可，從而減少時(shí)間復(fù)雜度。像素格細(xì)分精度不夠的情況下，如圖3所示。

圖3 像素格細(xì)分精度不夠的情況下

（3）計(jì)算排樣零件的面積和占板材總面積的比例 （板材利用率），比例超過(guò)50%的排樣群體作為子代。

計(jì)算零件和板材的面積：給出各個(gè)多邊形的頂點(diǎn)坐標(biāo)，利用頂點(diǎn)來(lái)求多邊形的面積，進(jìn)而通過(guò)多邊形的面積計(jì)算板材的利用率。任何多邊形的面積可以分割成幾個(gè)三角形面積之和來(lái)求得，通過(guò)多邊形各頂點(diǎn)坐標(biāo)可以求得各邊長(zhǎng)，再采用海倫公式，計(jì)算分割后的小三角形的面積。

海倫公式如下：

假設(shè)有一個(gè)三角形，邊長(zhǎng)分別為a，b，c，三角形的面積S 可有以下公式求得

對(duì)于復(fù)雜的多邊形由于頂點(diǎn)很多，劃分成小的三角形不是很方便，所以可直接采用多邊形頂點(diǎn)計(jì)算多邊形的面積。假設(shè)多邊形的頂點(diǎn)按順時(shí)針排序，利用下面公式計(jì)算復(fù)雜多邊形的面積

在式 （3）中，Xn＋1＝X1，Yn＋1＝Y(jié)1。在 式 （4）中，X0＝Xn，Y0＝Y(jié)n。從式 （3）和式 （4）可以看出，多邊形的面積等于相鄰兩個(gè)頂點(diǎn)縱橫坐標(biāo)交叉乘積。

綜上所述：同時(shí)滿(mǎn)足知識(shí)進(jìn)化 （1）（2）（3）這3個(gè)規(guī)則的零件，相當(dāng)于通過(guò)了第一次選擇，然后利用適應(yīng)度函數(shù)進(jìn)行第二次選擇，經(jīng)過(guò)兩次選擇后達(dá)標(biāo)的零件進(jìn)入自然進(jìn)化過(guò)程。

2 知識(shí)進(jìn)化和自然進(jìn)化相結(jié)合的排樣優(yōu)化算法

遺傳算法是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過(guò)程形成的一種全局優(yōu)化概率搜索算法。針對(duì)傳統(tǒng)的遺傳算法更擅長(zhǎng)全局搜索而局部搜索能力卻不足的問(wèn)題提出了基于知識(shí)進(jìn)化的改進(jìn)遺傳算法，在遺傳算法進(jìn)行子代選擇的過(guò)程中加入知識(shí)規(guī)則，大大提高選擇的效率。

基于知識(shí)進(jìn)化和自然進(jìn)化的算法首先通過(guò)知識(shí)規(guī)則和適應(yīng)度函數(shù)相結(jié)合的選擇方法對(duì)零件進(jìn)行選擇，然后將交叉、變異等操作算子作用于整個(gè)進(jìn)化群體，在設(shè)定的循環(huán)代數(shù)中得到問(wèn)題的最優(yōu)解或近似最優(yōu)解。圖4為改進(jìn)遺傳算法的基本流程圖。

2.1 圖形重心適應(yīng)度函數(shù)設(shè)計(jì)

適應(yīng)度函數(shù) （fitness function）是遺傳算法進(jìn)行選擇過(guò)程中決定每個(gè)染色體能不能進(jìn)入下代循環(huán)的重要依據(jù)。染色體的適應(yīng)度值越大，在遺傳操作中就更有可能被選中。

一般按下面一些要求設(shè)計(jì)：?jiǎn)沃敌?、非?fù)性、連續(xù)性、單調(diào)性；適用性強(qiáng)，可處理性好；充分顯示每個(gè)個(gè)體優(yōu)勢(shì)。

在零件排樣過(guò)程中，板材的利用率、零件排樣的高度、整體布局的重心都是我們?cè)谠O(shè)計(jì)適應(yīng)度函數(shù)時(shí)應(yīng)該注意的，綜上所述，設(shè)計(jì)出同時(shí)包含3個(gè)主要優(yōu)化條件的適應(yīng)度函數(shù)f（x）

圖4 基于知識(shí)進(jìn)化和自然進(jìn)化算法的流程

其中s（x）為板材利用率，g（x）為零件排樣后的圖形重心，h（x）為排樣圖的高度，w（x）為排布最高點(diǎn)中最左邊頂點(diǎn)x 坐標(biāo)，k，l，m，n 為權(quán)重，k＋l＋m＋n＝1取k＝0.5，l＝0.2，m＝0.2，n＝0.1。

2.2 混合編碼方法

遺傳算法在解決排樣問(wèn)題時(shí)，編碼問(wèn)題也是至關(guān)重要的一個(gè)環(huán)節(jié)。編碼和遺傳算法的排樣效率有息息相關(guān)的聯(lián)系，可靠的編碼方法為后面的交叉、變異提供了高效運(yùn)行的基礎(chǔ)；不適合的編碼方法對(duì)整個(gè)遺傳算法的時(shí)間復(fù)雜度、運(yùn)算效率、還有最后的解碼工作都會(huì)帶來(lái)很多不便之處。

一個(gè)適宜的編碼方案往往是遺傳算法的重要追求目標(biāo)，但是不可能一個(gè)編碼方案適合于任何情況，每個(gè)編碼方案的設(shè)計(jì)都是與每個(gè)項(xiàng)目的背景有密切聯(lián)系的，但是每個(gè)編碼方案都符合這樣的規(guī)則：將所有的排樣結(jié)果表現(xiàn)為染色體的形式，所有的染色體就組成所謂的 “可行域”，每條染色體對(duì)應(yīng)可行域中的一個(gè)解?？紤]到零件的多樣性和數(shù)量巨大，本文采用二進(jìn)制與實(shí)數(shù)相結(jié)合的混合編碼方法，不僅擴(kuò)大了搜索范圍而且提高了搜索的效率。

零件的形狀可謂多種多樣，如果只是像撒網(wǎng)一樣將所有零件一擁而上進(jìn)行排樣，這些零件就會(huì)一個(gè)一個(gè)的進(jìn)行歸位，時(shí)間復(fù)雜度也會(huì)更高。為了便于零件能更快找到適合自己的最佳排樣位置，減少匹配的過(guò)程，本文特將所有的零件按頂點(diǎn)的多少和位置大概分為4類(lèi)：

（1）沒(méi)有頂點(diǎn)的零件：圓，圓環(huán)。

（2）3個(gè)頂點(diǎn)的零件：三角形和扇形。

（3）4個(gè)及4個(gè)頂點(diǎn)以上的凸型零件。

（4）4個(gè)及4個(gè)頂點(diǎn)以上的凹型零件。

給每個(gè)零件分配一個(gè)編號(hào)，只是為了便于排樣時(shí)區(qū)分不同的零件。零件在排樣的過(guò)程中需要通過(guò)旋轉(zhuǎn)確定適合的位置，我們將旋轉(zhuǎn)的角度范圍設(shè)為：0度到360度之間。但是為了減小零件之間的空隙，可以采用實(shí)數(shù)編碼。何類(lèi)圖形用2位二進(jìn)制數(shù)來(lái)表示，如圓為第 （1）類(lèi)圖形00，第（2）類(lèi)圖形01，第 （3）類(lèi)圖形10，第 （4）類(lèi)圖形為11。

2.3 具有知識(shí)規(guī)則的選擇方法

適應(yīng)度比例方法也被稱(chēng)為賭輪或蒙特卡羅選擇是現(xiàn)階段使用比較頻繁的選擇方法。本文選擇方法的原理：利用知識(shí)規(guī)則選出的個(gè)體被選中的概率和其在群體中所表現(xiàn)的適應(yīng)度值的大小成比例。

假設(shè)群體大小為n，知識(shí)規(guī)則選擇出個(gè)體i （i≤n）的適應(yīng)度為f＊i，則個(gè)體i被選取的概率表示為

分析式 （6）可知，如果適應(yīng)度函數(shù)值越大，則個(gè)體被選中的機(jī)率越大；反之，如果適應(yīng)度越小，則個(gè)體被選中的的機(jī)率也越小。確定出優(yōu)秀排樣個(gè)體或是排樣個(gè)體的序列，作為精英基因保存。同時(shí)在后代中還要保存劣等基因，主要是指適應(yīng)度低于設(shè)定值的基因個(gè)體。劣等零件的排樣個(gè)體在后續(xù)的優(yōu)化中一旦發(fā)現(xiàn)，及時(shí)將其否決。

2.4 兩點(diǎn)交叉與變異

通過(guò)交叉和變異來(lái)增加個(gè)體的多樣性是遺傳算法的一個(gè)特點(diǎn)，交叉和變異可以避免算法因?yàn)閭€(gè)體的單調(diào)性而陷入局部最優(yōu)。

采用三角形兩點(diǎn)交叉的方法，圖5所示首先將父代基因圍城三角形的形狀，然后選擇任意兩點(diǎn)作為交叉點(diǎn)，互相交換父代基因長(zhǎng)度相同的部分，得到新的完整基因作為作為子代基因。

圖5 三角形兩點(diǎn)交叉

染色體的基因位 （x、y、β、h）中既包含有排樣件序號(hào)的屬性，X 軸平移距離x、Y 軸平移距離y、旋轉(zhuǎn)角度β及幅度變換量h，因此這里將變異運(yùn)算分成X 軸平移距離變異、Y 軸平移距離y 變異、旋轉(zhuǎn)角度α變異、幅度變換量s變異4個(gè)子運(yùn)算來(lái)進(jìn)行。

遺傳算法中交叉概率Pc和變異概率Pm是影響遺傳算法行為和性能的關(guān)鍵因素，直接影響著遺傳算法的收斂性和搜索效率，在本文中所采用的自適應(yīng)遺傳算法中Pc和Pm是能夠隨種群中個(gè)體的適應(yīng)度自動(dòng)改變的

其中fmax是每代種群中的個(gè)體的最大適應(yīng)度；favg是每代種群適應(yīng)度的平均值：f1每次進(jìn)行交叉的個(gè)體中較大的適應(yīng)度值；f 是即將要變異的個(gè)體的適應(yīng)度；PcA＝0.8，PCb＝0.5，PmA＝0.09，PmB＝0.001。

2.5 最低重心排樣策略

利用臨界多邊形找到零件重心的最低位置。具體步驟：將零件置于板材內(nèi)部，利用幾何圖形的性質(zhì)找到零件的重心，以重心為參考點(diǎn)，找出零件每旋轉(zhuǎn)一個(gè)角度對(duì)應(yīng)的臨界多邊形 （零件必須在板材內(nèi)部旋轉(zhuǎn)）在這些臨界多邊形上找到重心的最低位置，零件按最低位置對(duì)應(yīng)的坐標(biāo)和旋轉(zhuǎn)角度進(jìn)行排樣，就是最佳排樣位置。零件旋轉(zhuǎn)變化范圍：0－360°，可以較準(zhǔn)確找出零件的最低重心位置。利用臨界多邊形找到零件最低重心，如圖6所示。

圖6 利用臨界多邊形找到零件最低重心

3 仿真與結(jié)果分析

（1）零件輸入方法

在對(duì)零件進(jìn)行排樣前，必須考慮先將零件以圖形的形式輸入計(jì)算機(jī)中，利用零件的輪廓圖對(duì)零件進(jìn)行排樣。頂點(diǎn)序列法、等距掃描法、網(wǎng)格擬合法是幾種比較常用多邊形零件表達(dá)方法。根據(jù)零件的復(fù)雜度可以選擇適合的零件表達(dá)方法。

頂點(diǎn)序列法的具體步驟是，首先把圖形各個(gè)頂點(diǎn)的坐標(biāo)表示出來(lái)，然后將各個(gè)頂點(diǎn)坐標(biāo)按一定的順序排成一個(gè)隊(duì)列，這個(gè)隊(duì)列中的每個(gè)頂點(diǎn)都有自己對(duì)應(yīng)的編碼。如一個(gè)按順時(shí)針?lè)较蚓幋a的n 邊形的各個(gè)頂點(diǎn) （以橫坐標(biāo)最小的頂點(diǎn)作為起始頂點(diǎn)）依次為A、B、C……，這些頂點(diǎn)隊(duì)列構(gòu)成的圖形，如圖7所示。

圖7 頂點(diǎn)序列法

頂點(diǎn)序列法主要是以一定的順序?qū)㈨旤c(diǎn)搜集起來(lái)組成隊(duì)列，不僅需要記錄多邊形的每個(gè)頂點(diǎn)還需要將這些頂點(diǎn)進(jìn)行排序、編號(hào)。對(duì)于簡(jiǎn)單的多邊形比較適合，頂點(diǎn)較多的多邊形工作量就會(huì)大大提高。網(wǎng)格擬合法只能進(jìn)行水平和垂直兩個(gè)方向的移動(dòng)，同時(shí)每個(gè)零件能移動(dòng)的最小距離是一個(gè)網(wǎng)格的距離，存在誤差。

等距掃描法采用間隔相等的水平線或是垂直線掃描零件，零件的輪廓與這些線條的交點(diǎn)集合就構(gòu)成一個(gè)完整的零件圖。這種方法比頂點(diǎn)序列法的工作量減少，比網(wǎng)格擬合法的移動(dòng)距離更精確。所以本文采用等距掃描法來(lái)進(jìn)行多邊形的輸入，如圖8所示。

圖8 等距掃描法

（2）試驗(yàn)中設(shè)種群數(shù)N 為10，進(jìn)化代數(shù)Gm＝100，交叉概率Pc＝0.8，變異概率Pm＝0.1，總共進(jìn)行2次實(shí)驗(yàn)。30個(gè)零件的基本信息見(jiàn)表1。兩種算法進(jìn)行排樣的結(jié)果如圖9，圖10所示。

通過(guò)表2可知，基于知識(shí)進(jìn)化的遺傳算法和傳統(tǒng)的遺傳算法相比，雖然時(shí)間復(fù)雜度明顯降低，但是板材利用率并不算高，而且與傳統(tǒng)遺傳算法相比提高不明顯。

4 結(jié)束語(yǔ)

本文通過(guò)對(duì)不規(guī)則零件排樣的研究，提出了一種基于知識(shí)進(jìn)化的遺傳算法來(lái)達(dá)到優(yōu)化排樣的目的。利用遺傳算法排樣時(shí)，板材利用率低，時(shí)間復(fù)雜度高，并且傳統(tǒng)的選擇方法隨機(jī)性太強(qiáng)，針對(duì)這些難題我們采取知識(shí)進(jìn)化規(guī)則和適應(yīng)度函數(shù)相結(jié)合的選擇方法。知識(shí)進(jìn)化規(guī)則包括邊界判定、板材占有率判定、零件重疊判定等，大大提高選擇的速度。提出了重心最低的排樣策略和等距掃描零件輸入法，降低零件的排樣和輸入時(shí)間。通過(guò)實(shí)驗(yàn)，本文算法在處理大量不規(guī)則零件排樣的問(wèn)題上的時(shí)間復(fù)雜度明顯降低，并且板材利用率和時(shí)間復(fù)雜度都超越了傳統(tǒng)的遺傳算法，但是本文的板材利用率并不理想，還有待進(jìn)一步提高，知識(shí)規(guī)則的設(shè)計(jì)可能不是很全面，希望大家能夠提供寶貴意見(jiàn)。

表1 30個(gè)零件的基本信息

表2 兩種算法排樣結(jié)果比較

［1］LI Chen，NING Hongyun.The improved genetic algorithm selection ［J］.Journal of Tianjin Polytechnic University，2008（12）：1－4 （in Chinese）.［李晨，寧紅云.改進(jìn)的遺傳算法選擇算子 ［J］.天津理工大學(xué)學(xué)報(bào)，2008 （12）：1－4.］

［2］MA Xuan，ZHANG Yalong.Based on the genetic algorithm of optimal layout of rectangular pieces of a mass ［J］.Journal of Intelligent Systems，2007，2 （5）：49－52 （in Chinese）.［馬炫，張亞龍.基于遺傳算法的大規(guī)模矩形件優(yōu)化排樣 ［J］.智能系統(tǒng)學(xué)報(bào)，2007，2 （5）：49－52.］

［3］ZHAO Zhiguo，LU Jun，JIA Lili.Genetic algorithm and collision algorithm automatic blanking pieces layout problem solving ［J］.Journal of Engineering Drawing，2008，9 （1）：38－42 （in Chinese）.［趙治國(guó)，盧軍，賈俐俐.遺傳算法和碰撞算法自動(dòng)排樣問(wèn)題求解沖裁件［J］.工程圖學(xué)報(bào)，2008，9 （1）：38－42.］

［4］LU Qifei，TANG Ping，ZHANG Guangfu，et al.The improved genetic algorithm to optimize two－dimensional irregular graphics layout［J］.Computer Engineering and Design，2013，34 （4）：1410－1414 （in Chinese）.［盧齊飛，唐平，張光富，等.改進(jìn)的遺傳算法優(yōu)化二維不規(guī)則圖形排樣 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2013，34 （4）：1410－1414.］

［5］LIU Huyao，HE Yuanjun.2D irregular nesting algorithm based on gravity center NFP ［J］.Chinese Mechanical Engineering，2007，18 （6）：723－731（in Chinese）.［劉胡瑤，何援軍. 基于重心NFP 的不規(guī)則形狀排樣算法 ［J］.中國(guó)機(jī)械工程，2007，18 （6）：723－731.］

［6］TANG Jiangang，LIU Cong，ZHANG Lihong.Irregular shapes layout based on improved genetic algorithm ［J］.Computer Engineering，2010，36 （21）：185－187 （in Chinese）.［唐堅(jiān)剛，劉從，張麗紅.基于改進(jìn)遺傳算法的不規(guī)則圖形排樣［J］.計(jì)算機(jī)工程，2010，36 （21）：185－187.］

［7］LIANG Lidong，YE Jiawei.Research of irregular parts packing with genetic algorithm ［J］.Computer Engineering and Applications，2009，24 （2）：223－228 （in Chinese）.［梁利東，葉家偉.基于遺傳算法的不規(guī)則件優(yōu)化排樣研究 ［J］.計(jì)算機(jī)工程與應(yīng)用，2009，24 （2）：223－228.］

［8］MEI Ying.Hull construction plank out sample nesting system optimization algorithm and touch by technology research ［D］.Guangzhou：South China University of Technology，2010 （in Chinese）.［美穎.船體建造板材套料系統(tǒng)中排樣優(yōu)化算法與碰靠技術(shù)研究 ［D］.廣州：華南理工大學(xué)，2010.］

［9］GU Zhenhua.Two－dimensional irregular layout CAD system design ［D］.Shanghai：Shanghai Jiao Tong University，2007（in Chinese）.［顧振 華.二維不規(guī) 則 排樣CAD 系統(tǒng)的 設(shè) 計(jì)［D］.上海：上海交通大學(xué)，2007.］

［10］LIU Huyao.Based on the critical poly 2dlayout algorithm research ［D］.Shanghai：Shanghai Jiao Tong University，2007（in Chinese）.［劉胡瑤.基于臨界多邊形的二維排樣算法研究［D］.上海：上海交通大學(xué)，2007.］

［11］HUANG Feng，QI Ji，TAN Ying，et al.A kind of genetic a discrete particle swarm optimization algorithmolving rectangular layout problem ［J］.Journal of Electronics，2012，40 （6）：1104－1106 （in Chinese）.［黃嵐，齊季，譚穎，等.一種求解矩形排樣問(wèn)題的遺傳一離散粒子群優(yōu)化算法 ［J］.電子學(xué)報(bào)，2012，40 （6）：1104－1106.］

［12］WU Jun，ZHANG Jingjuan.Using genetic algorithm of multimachine free flight conflict free policy ［J］.Journal of Intelligent Systems，2013，8 （1）：1－5 （in Chinese）.［吳君，張京娟.采用遺傳算法的多機(jī)自由飛行沖突解脫策略 ［J］.智能系統(tǒng)學(xué)報(bào)，2013，8 （1）：1－5.］