矩形排樣綜述

1、1. 矩形件排樣的問題描述： 22. 算法分類 22.1. 啟發(fā)式算法 22.1.1. 基于最低水平線算法2 . 基于最低水平線的二維搜索算法3 . 文獻(xiàn)8 . 基于二維裝箱問題的矩形件排樣算法9 62.1.2. Best-fit 算法 . A squeaky wheel optimisatio n pack ing methodology(SWP 4 92.1.3. 分層排布算法 . Modified size-alternating stack algorithm(SASm)5. Best

2、fit with stacki ng algorithm (BFS) . 其他啟發(fā)式算法 . 文獻(xiàn)10 . 文獻(xiàn)11 162.2. 智能算法 192.2.1. PSO 算法 . 文獻(xiàn)12 193. 上述算法在矩形排樣件中的應(yīng)用分類 214. 參考文獻(xiàn) 22部分2010年矩形件優(yōu)化排樣算法的研究進(jìn)展1矩形件排樣的問題描述：參見文獻(xiàn)1：矩形件排樣題指在給的矩形板材上將一系列矩形零件按最優(yōu)方式進(jìn)行排布。 即給定n個零件R=(Ri, R,，Rn),將零件置于寬度為 W,高度為L的板材 P上，使得板材的利用率最高，并要求滿足下列約束

3、條件：(1) Ri、Rj 互不重疊,i 工j, i, j=1,2,n;(2) Ri能夠且必須放在 P內(nèi)，i= 1,2,n;(3) 滿足一定工藝要求。2. 算法分類2.1. 啟發(fā)式算法2.1.1. 基于最低水平線算法. 基于最低水平線的二維搜索算法3為了提高矩形件排樣時材料的利用率，針對定序列矩形件優(yōu)化排樣問題，本文 在基于最低水平線的搜索算法的基礎(chǔ)上，提出了一種改進(jìn)的矩形件優(yōu)化排樣 算法一一基于最低水平線的二維搜索算法此改進(jìn)算法在基于最低水平線的搜 索算法基礎(chǔ)上，進(jìn)行了排樣寬度的二維搜索，即有如下改進(jìn)：基于最低水平線的 搜索算法只進(jìn)行入排寬度的搜索(即矩形寬度的搜索)，而本文提

4、出的排樣算法不 僅優(yōu)先進(jìn)行入排寬度的搜索，而且在入排寬度均不符合排樣要求時，還進(jìn)行了待排寬度的搜索(即矩形高度的搜索)。將該改進(jìn)算法與其他算法進(jìn)行實(shí)例排樣比較，排樣結(jié)果表明，改進(jìn)后的排樣算法能有效地利用排樣時產(chǎn)生的空白區(qū)域，在提高材料利用率上具有可行性和有效 性。在排樣方式中，“I”表示對應(yīng)的矩形橫放，“一 1”表示對應(yīng)的矩形豎放。此算法將參與排樣的矩形的長寬根據(jù)排樣方式的要求，劃分為入排寬度數(shù)集Ri和待排寬度數(shù)集Di（其中i為入排矩形件的序列號，i=1，2, 3, 4）。排樣 時，在本文的使用中，優(yōu)先搜索入排寬度數(shù)集 Ri（即矩形寬度搜索），當(dāng)入排寬度 數(shù)集m都不能滿足排樣要求時，再搜索待排

5、寬度數(shù)集 Di（即矩形高度搜索）。具 體的算法步驟如下所示：下圖中，Xc表示當(dāng)前待排矩形件。開始2.1.12 文獻(xiàn)8該分層排樣算法以文獻(xiàn)9提出的最低輪廓線搜索排樣法為基礎(chǔ)，討論的是2SP問題及符合“一刀切”的加工模式。針對在具有寬度一定、長度不限的板材 上進(jìn)行矩形件排樣的問題，結(jié)合模擬退火算法，設(shè)計(jì)了一種矩形件分層優(yōu)化排樣算 法。該算法以板材寬來分層，層數(shù)依據(jù)待排零件而定，靈活性強(qiáng)，并且通過算例驗(yàn)證 了該算法的有效性和合理性。算法以零件的長度值（矩形零件較長一邊值）來進(jìn)行排樣，更新后的輪廓線段 的首末點(diǎn)橫坐標(biāo)值必須在該層寬度所對應(yīng)線段首末點(diǎn)橫坐標(biāo)值之間。根據(jù)排樣結(jié)果顯示，該算法思想滿足先前提出

6、的“一刀切”工藝要求，且排 樣板材利用率在91%以上?；谧畹洼喞€分層排樣算法程序流程圖如下：其中l(wèi)min存儲剩余待排零件中的長度最小值，RC為當(dāng)前待排序列中的第一個零 件。開始將待排的所有矩形零件按長 度優(yōu)先、面積次先的規(guī)則，從大到小排序?qū)i排放在板材左下角記錄 最初的輪廓線，并把Ri長度賦值給l min排放完畢 丫N搜索最低輪廓線，更新l min值只有一條可排 輪廓線？N搜索最匹配的最Y低輪廓線排放FCN最低輪廓線長度lmin（l min對應(yīng)于Rk長度值）1YRc Rk搜索最匹配的零 件 R, Rc R搜索最匹配的零件Rm并 將零件旋轉(zhuǎn)90o, RcRmYRc及其后零件寬度值小 、此最

7、低輪廓線長度更新輪廓線*封閉該最低輪廓線在此輪廓線 上排放Rc在結(jié)合模擬退火算法時，按待排零件的長度優(yōu)先、面積次先的原則所排的順 序?yàn)槌跏柬樞?，并且按此順序把可以先排滿板材最底端的零件排到板材上。然后將剩下的零件采用十進(jìn)制編碼方式將每一個零件進(jìn)行編號，用零件的長度信息進(jìn) 行排樣。初始化X0為初始導(dǎo)入的排樣順序，之后在 Tk下不斷產(chǎn)生在解x的鄰域中產(chǎn)生新的可行解x 結(jié)合后流程圖如下:持扌岸兩形件按長度優(yōu)先商駅 次先的原則的釧始播徹順序r基于線 的分足排樣算輕樓擬退火JT法 調(diào)按拌樣順睜分層排樣算法結(jié)合模擬退火算法的流程圖2.1.13基于二維裝箱問題的矩形件排樣算法9針對在具有一定長寬尺寸的板材上

8、進(jìn)行矩形件排樣的問題，結(jié)合遺傳算法，設(shè) 計(jì)了一種矩形件優(yōu)化排樣算法.該算法考慮到排樣高度不超過板材長度的要求，可 以實(shí)現(xiàn)換板，使剩余待排矩形件在新板材上繼續(xù)排放.通過算例驗(yàn)證了該算法的有 效性和合理性.針對2BP問題。換板示意圖設(shè)待排的矩形零件分別有 R1, R2, R3, . , Rk,.,其中Rc表示當(dāng)前待排 零件。以零件的長度值（矩形零件較長一邊值）來進(jìn)行排樣。算法的具體程序流程 如圖3所示，其中l(wèi)min存儲剩余待排零件中的長度最小值，會隨排樣過程動態(tài)變 化；hnew表示排放當(dāng)前矩形零件后該零件頂端的高度值，用于判斷該零件排放是 否會超出板材高度。以下為基于二維裝箱問題的矩形件排樣算法程

9、序流程圖：開始*將Ri排放在板材左下角記錄 最初的輪廓線，并把Ri長度 賦值給i minir排放完畢丫搜索最低輪廓線，更新l min值乂最低輪廓線長度l min（i min對應(yīng)于R長度值）N最低輪廓線長度R長度NY搜索最匹配的最 低輪廓線排放FC只有一條可排 輪廓線？存儲從當(dāng)前零件開始后面的所有未排零件調(diào)入新的板材丫搜索最匹配的零件 Fj，F(xiàn)C FjFC及其后零件寬度值小于 此最低輪廓線長度搜索最匹配的零件 R,并將零件旋轉(zhuǎn)90o, R Fm更新輪廓線*封閉該最低輪廓線在此輪廓線 上排放RN計(jì)算hnew值*搜索R后面的是否丫存在R可排在當(dāng)前-hnew板材高度-板材4 更新 l min , Rc

10、R結(jié)束上述算法與遺傳算法結(jié)合使用尋求一種較優(yōu)的排樣順序，具體交叉及變異方法參照本算法文中提及的。以下基于遺傳算法的優(yōu)化排樣算法流程圖:待排零件初始排基于遺傳算法的優(yōu)化排樣算法流程圖通過文中自帶的算例，用本文算法與基于最低輪廓線搜索排放算法比較， 在 應(yīng)用于2BP問題時的板材利用率有所提高。2.1.2. Best-fit 算法. A squeaky wheel optimisation packing methodology （ SWP） SWP算法采取迭代的方式尋求矩形件排放的優(yōu)化，在迭代的過程中能夠找 尋到使排樣效果變差的矩形，將它們優(yōu)先排放以達(dá)到優(yōu)化的效果。 每一次迭代都 表

11、示一個完整的排樣過程。在每一次運(yùn)行時，每一個矩形件的初始懲罰值為0，在每一次迭代后，超出排樣實(shí)例最低邊界的矩形件的懲罰值將增加。而每次累積 的懲罰值將影響到到下一次迭代的排放選擇，懲罰值越高的矩形件下次迭代時將 被優(yōu)先排放。在排放搜索時，若能放入當(dāng)前槽的矩形件懲罰值相同，則以寬度長 者優(yōu)先；若寬度相同，則以長度長者優(yōu)先。Without penalty values, the constructive heuristic performs iden- tically to thebest-fit heuristic with the tallest neighbour place- ment p

12、olicy 5. The addition of pen alty values is a minor but fun dame ntal cha nge, which allows the heuristic to lear n which pieces are more difficult to allocate, over many iterati on s.（若該算法沒有懲罰 值，則這個結(jié)構(gòu)化的啟發(fā)式算法與“靠最高的邊排放”的best-fit算法是一樣的效果。）即SWP算法的改進(jìn)就是加入了懲罰值以達(dá)到更好的排樣效果。The additi on of pen alty values is

13、 a minor but fun dame ntal cha nge, which allows the heuristic to lear n which pieces are more difficult to allocate, over many iterati ons. （加入懲罰值以后是對best-fit算法的一個較小的但根本的變化，使啟發(fā)式算法在 多次迭代后能夠知道哪些矩形件較難調(diào)配，以達(dá)到優(yōu)化排放效果的目的。）SWP算法的偽代碼如下：初始化每一個樣件的懲罰值為0while經(jīng)過時間 i nsta nee lowerbo und the np.pe nalty =p.pe nalt

14、y + p.heightend ifend forend whileretur n best soluti on found在測試算法時使用的lower bound是以本次實(shí)例的情況而定的。若此例為已知的 測試用例，則以其zero-waste時排放的高度為lower bound,若是隨機(jī)產(chǎn)生的實(shí)例， 則用簡單的 continuous lower bound和與31相同的更復(fù)雜一些的 lower bound 計(jì)算。(注:31 Martello S, Monaci M, Vigo D. An exact approach to the strip-packing problem. INFORMS

15、Journal on Computing 2003;15(3):3109 )52.1.3. 分層排布算法2.131. Modified size-alternating stack algorithm(SASm)SASm算法改進(jìn)自SAS算法。因此簡介SAS算法如下：FFDH在矩形件高度相差懸殊的時候，效果是很差的每初始化一層，都比較兩集合中的第一個矩形件， 以其中最高的矩形(具有相等 高度的矩形可能有多個)初始化層。排放規(guī)則如下：如果初始化該層的矩形件來自于 L1，則將被排放列表設(shè)為L2, 反之亦然。當(dāng)將被排放的矩形所在列表已經(jīng)確定，則開始排放該列表中的矩形。 排放的時候，從層底往層的上界堆疊

16、排放，直到觸到層的上界或無法再放入該列 表的矩形為止。此時再交換下一個列表的矩形在該層排放。如此反復(fù)至該層的右 邊界與已排的矩形件右邊界之間再也放不下 L1或L2中的矩形件。在排放寬矩形件時，可能會出現(xiàn)如下圖所示的區(qū)域R1,則此區(qū)域?qū)⒄{(diào)用窄矩形排放，先選擇寬度最適合的窄矩形件排放，之后只要有合適的垂直和水平空 間，就選擇其寬度不超過最底端的窄矩形件，且高度不超過該層上界的窄矩形件。 進(jìn)行排放。排放寬矩形件產(chǎn)生空白區(qū)域用窄矩形件填充空白區(qū)域SASm中對SAS改進(jìn)的部分有：1）當(dāng)初始化一層的時候，找出寬矩形集 L2 （或W）中的最高者與窄矩形集L1（或N）中的 第一個矩形件進(jìn)行比較，而不是 L2中

17、的每一個矩形件。這樣 可優(yōu)化層的創(chuàng)建。2）在填充排放寬矩形件產(chǎn)生的空白空間時，選取了第一個窄矩形件之后，之后 排放的窄矩形件可以相臨并列排放，而不只是局限于堆疊式的排放，這樣可 以減少如下圖的空間浪費(fèi)。此方法可在排放了第一個窄矩形件后，采用FFDH 的方式排放其他的窄矩形件于其上的空白區(qū)域來達(dá)成。2.1.32 Best fit with stacking algorithm (BFS)5BFS算法對BFDH*進(jìn)行改進(jìn)，BFDH*簡介如下:BFDH* :對BFDH算法進(jìn)行了改進(jìn)，有如下兩點(diǎn)：1）在排放時，對當(dāng)前存在的所有層，BFDH的矩形件方向是不允許旋轉(zhuǎn)的，而 BFDH*算法在排放當(dāng)前矩形件時

18、，都嘗試該矩形件的兩種方向。若所有層都 不適合當(dāng)前矩形件，則以該矩形件 width height的方向初始化新層。2）提高空間的利用率。等該層底部排好后，將排入該層的矩形件如下圖從左至右排序（由于第一個改進(jìn)會破壞這種次序，因而重新排序），如此就會產(chǎn)生圖中所示的一些空白區(qū)域，這些空白區(qū)從左到右解決。對于每一個空白區(qū)域， 選取面積最大的樣件以最合適的方向和 BL的方式排入空白區(qū)，此時空白區(qū) 的左邊界更新至填充矩形件的右邊界，因此一個空白區(qū)域的填充可能是由幾個并排的矩形件完成的。free space 1: =l free 2:| | fr&e space 3:購3BFS:改進(jìn)了 BFDH*算法，有如

19、下幾點(diǎn)：1）初始化的時候，BFDH*采用DH方式排序，BFS采用DHDW方式排序。2）與BFDH*算法不同，BFS算法不必等到層的底部被排滿時再進(jìn)行空白區(qū)填 充。在將一塊矩形件排入該層底部后，以該矩形件寬為寬，矩形件高至層高 的差度為高的矩形空白區(qū)產(chǎn)生，此時采用FFDH的方式將待排矩形件填充入 此空白矩形區(qū)域中。若排入底部的矩形件的右邊空白區(qū)域?qū)挾忍《鵁o法放 入所有待排矩形，則該底部矩形件產(chǎn)生的空白區(qū)的右邊界擴(kuò)展至為條帶的右 邊界。2.1.4. 其他啟發(fā)式算法2.141. 文獻(xiàn)10對大規(guī)模矩形件正交排樣問題，提出了一種快速高效的啟發(fā)式排放算法。對當(dāng)前的可排放位置（水平線），用貪婪算法從未排矩

20、形件中選擇可排放于該水平 線的最優(yōu)矩形件組合塊；根據(jù)各個排放位置與其對應(yīng)的矩形件組合塊的匹配程度，選擇最優(yōu)的可排放位置（最優(yōu)水平線）優(yōu)先排放。在排放時，為了便于后續(xù)排放,先將待排放位置對應(yīng)的矩形件組合塊從高到低進(jìn)行排序，再排放。對E.Hopper提 供的規(guī)模最大的一類實(shí)例進(jìn)行計(jì)算，排樣率都在99%以上,平均排樣率達(dá)到了 99.38%,平均計(jì)算時間只用了 1.12秒。由于之前已提出的排放算法雖然取得了一定的效果，但當(dāng)問題規(guī)模較大時， 計(jì)算時間仍然較長。因此，一種高效的針對大規(guī)模矩形件的優(yōu)化排樣方法的產(chǎn)生 意義重大。在具體做法上，與一般文獻(xiàn)中將矩形件選擇和位置選擇分成兩步或者每次考慮一個未排矩形件

21、不同，該文將矩形件的選擇和位置的選擇結(jié)合起來考慮，利用貪婪算法，對各個可排位置選擇出最合適的一組矩形件，即最優(yōu)矩形件組合。根據(jù)各可排位置與其最優(yōu)矩形件組合的匹配程度，選擇最優(yōu)的排放位置（最優(yōu)水平線）優(yōu)先排放，這使得當(dāng)前排放矩形件與已排矩形件盡可能緊湊。為了使當(dāng)前排放有利于后續(xù)排放，將排放位置對應(yīng)的矩形件組合塊按低到高排序后再進(jìn)行排 放。按照此排放過程，直到排完所有的矩形件或者無法排放為止。在圖2中，矩形1和4上方的水平線為槽形水平線；矩形 2的為凸形水平 線；矩形3與5上的為梯形水平線。初始排放狀態(tài)下，大矩形件的底邊為槽形水 平線，其相鄰的左右水平線，看成高為 H的梯形水平線。2145圖2水平

22、線圖另外，文中提出相應(yīng)的最優(yōu)組合算法與排放算法輔助選出最優(yōu)矩形組合及優(yōu) 化排放效果（見文獻(xiàn)中）。由于文中敘述步驟過多，以下為該算法的簡要步驟：1 若當(dāng)前最低槽形水平線的高h(yuǎn)min H，或所有小矩形件均被排放完，則轉(zhuǎn)步驟6;否則，轉(zhuǎn)步驟2。2在當(dāng)前排放狀態(tài)下，找出槽形水平線對應(yīng)的最優(yōu)組合矩形，計(jì)算第i條槽形水平線的長度與組合矩形總寬度之差 dij。找出最小差度dmin的集合I。3 判斷是否存在最優(yōu)槽形水平線（該槽形水平線對應(yīng)的矩形組合塊與該槽形水平線匹配得最好，以dmin=0為標(biāo)準(zhǔn)）。若只有一個最優(yōu)槽形水平線，則用其 對應(yīng)的矩形組合塊進(jìn)行排放；若有多條，則按文中規(guī)定的規(guī)則選擇其中一條 進(jìn)行排放。

23、排放完成后返回步驟1;若無最優(yōu)槽形水平線，則轉(zhuǎn)至步驟 4。4 判斷是否存在最優(yōu)梯形水平線（存在某未排矩形件排放于此，剛好能填充滿該水平線）。若存在這樣的梯形水平線，且只有一條，則直接排入。有多條， 則按文中規(guī)定的規(guī)則選擇其中一條進(jìn)行排放。返回步驟1;若不存在，則否則轉(zhuǎn)步驟5。5 到這一步，表明I中無最優(yōu)槽形水平線，且找不到最優(yōu)梯形水平線。則考慮I中的槽形水平線。若|I|=1，則對這條水平線對應(yīng)的最優(yōu)組合矩形塊進(jìn)行排放； 若|I|1，則按文中規(guī)定的規(guī)則進(jìn)行選擇并排放。返回步驟1。輸出排放圖。文中與相關(guān)文獻(xiàn)最好結(jié)果進(jìn)行了比較，結(jié)果表明該文算法解決大規(guī)模的矩形 件排樣具有高效性。表】 諫丈算法與其也

24、文猷算法結(jié)果比殺律法平均利用聿“船平均計(jì)茸時間&HH球法K6.63啊畀3 76.5.40筑心“眩匸W.72該文堆法W3R2.142. 文獻(xiàn)11為了有效地解決有約束的矩形件優(yōu)化排樣問題， 本文提出一種快速的求解算 法。通過比較待排樣矩形件的不同排樣模式， 選擇最優(yōu)排樣方案。算法完全基于 解析計(jì)算，雖不能尋找理論最優(yōu)解，但相比于各種啟發(fā)式算法大大提高了排樣速 度。實(shí)驗(yàn)結(jié)果表明，算法能夠在較短的計(jì)算時間內(nèi)獲得滿意的排樣效果，是一種效率較高的有約束矩形件排樣算法，應(yīng)用于 2BP問題和“一刀切”的加工模式。算法基本思想如下：如下圖，將矩形件排放左下角，有旋轉(zhuǎn)和不旋轉(zhuǎn)兩種旋 轉(zhuǎn)方式。另外，在放好左下角的矩

25、形件后切割的方式又可以分為橫切和豎切兩種， 所以總共有4種排樣模式。其中R1，R2，R3, R4為切割后產(chǎn)生的子板材。RLJQR4R3R2R4R3矩形件不旋轉(zhuǎn)肘 的兩種排樣模式5）矩形牛旋轉(zhuǎn)時的兩種排樣模式一個待排矩形件的排樣模式圖因此，對一塊板材進(jìn)行排樣，首先從這塊板材的左下角開始試探地排放待排矩形件，對它的4種排樣模式用某種評價標(biāo)準(zhǔn)進(jìn)行評估，選出評價最好的那種模式，再將這個評估值與其他所有待排矩形件的較好評估值進(jìn)行比較，選出最好的排樣模式，并按該排樣模式進(jìn)行板材切割。然后按深度優(yōu)先的原則不斷地對 一刀切產(chǎn)生的兩塊新的子板材重復(fù)上述過程，最終完成一塊板材的全部排樣。由 于算法完全是解析計(jì)算，

26、不存在尋優(yōu)過程，雖不能獲得理論最優(yōu)解，但運(yùn)行效率 大大提高。如下所述，則可計(jì)算評價函數(shù) BK（ R）,為該算法奠定評價基礎(chǔ)，BK（ R） 可以用快速貪婪法近似解決：步驟1初始化：設(shè)z=0, z為排樣的總有效面積，它的最后結(jié)果即為評價函數(shù)值 BK（ R）。 c=LW，c為未排樣空間的面積大小。矩形零件集合中的元素按面積從大到小排列。設(shè)j=1，j為當(dāng)前時刻考慮的矩形零件的編號。z*=0，只排一種矩形零件（編號為j*）能排放的最大有效面積。步驟2 BK（ R）計(jì)算：uj =min bj - n， IIL /1i，|IW /wi xj =minuj ， IIc / vj z = z + Vj Xjc

27、= c - Vj Xj如果 Vj Xj z* ，z* = VjUj ，j* = j。步驟3如果jz，z=z*，返回最終的z值為評價函數(shù)值BK （ R） o有了以上計(jì)算評價函數(shù)BK （ R）算法的基礎(chǔ)后，排放算法的詳細(xì)步驟如下所述： 初始化：設(shè)L=R，為待排樣的板材集合。設(shè)P=O，為已排樣的矩形件鏈表集合。設(shè)VT = 0，為已排樣的總有效面積。待排樣的矩形件集合S按照其面積從大到小排序，面積相同的則將長和寬之差的絕對值大的排在前面。每種待排矩形件i已排數(shù)量ni = 0。步驟1如果LM，取出一種板材(Lk ,Wk ,Nk)，并將其加入堆棧C。 步驟2如果C=O，則回步驟1。否則：從C中取出一個元素

28、(L, W)作為將被切割的板材。 對于每種待排矩形件i, i=1 , 2,，m,進(jìn)行如下循環(huán)： 如果，待排矩形件i有紋理方向要求(即不能旋轉(zhuǎn))，則如果 li L, wi W, ni 0，貝U按照Bj所確定的排樣模式進(jìn)行排樣切割。將切 割后產(chǎn)生的兩塊子板材 R1、R2或R3、R4加入C。否則，Bj = 0，說明當(dāng)前的子板材(L , W)放不下任何待排矩形件， 所以將它當(dāng)作余料或廢料處理，加入余料列表。返回步驟2。結(jié)果對比：衣2不同算法結(jié)果對比文獻(xiàn)岡算法文獻(xiàn)算洙本文算法運(yùn)行時間蟲利用率()運(yùn)行時間嗨利用$/(%)運(yùn)行時間冉利用率)4729&435695+435497.95表中所指文獻(xiàn)為：8 Mha

29、nd H.Exact algorithms for the guilloti ne strip cutt in g/pack ingproblemJ.Computers and Operations Research 1998, 25:925-940.10馬廣焜，劉嘉敏，黃有群，等.一種有約束矩形排樣問題的求解算法J.沈陽工業(yè)大學(xué)學(xué)報，2006，28（4）: 449-453.2.2.智能算法2.2.1. PSO算法. 文獻(xiàn)12本文的算法是一種改進(jìn)基于最低水平線搜索算法，結(jié)合 GA算法產(chǎn)生的改進(jìn) 粒子群優(yōu)化算法。在本文應(yīng)用最低水平線搜索算法時，若有多個矩形件適合最低 水平線，則從中

30、選取長度或?qū)挾茸钸m合最低水平線寬度的矩形件進(jìn)行排放。算法提出者考慮到用標(biāo)準(zhǔn)的 PSO算法來更新原子比較困難，故利用 GA的 算法特點(diǎn)，結(jié)合GA改進(jìn)了 PSO算法：通過GA的交叉和變異來更新原子。在交叉時，當(dāng)前解將和個體最佳及全局 最佳進(jìn)行交叉，產(chǎn)生的新解將決定原子在解空間的新位置。交叉的時候運(yùn)用的是文獻(xiàn)13里的交叉算法步驟如下：先選擇一個固定的交叉位置，該點(diǎn)前的基因保持不變，其后的基因進(jìn)行交叉操作 比較兩條染色體非交叉部分的基因，除去兩者中相同的基因；將兩條染色體不交叉部分余下的基因按原序保存在數(shù)組p和q當(dāng)中；進(jìn)行交叉時，將兩染色體交叉部分的基因和數(shù)組p或q中的基因進(jìn)行對比，若不相同，則直接交

31、換；否則用對應(yīng)數(shù)組p或q中的基因替換后，再交換兩染色體交叉的部分； 完成染色體的交叉操作。例如：染色體 A= 3,2,4,5,9,8,7,6,1,10 ,B= 9,1,10,3,2,5,4,6,7,8.執(zhí)行交換時，產(chǎn)生交叉點(diǎn)：A= 3,2,4,5,9,|8,7,6,1,10 ,B= 9,1,10,3,2,|5,4,6,7,8， 有 P=4,5，q = 1,10。將兩染色體交叉部分的基因和數(shù)組p或q中的基因進(jìn)行對比后：A= 3,2,4,5,9,|8,7,6,4,5 ,B= 9,1,10,3,2,|10,1,6,7,8最后，交換兩染色體中交叉部分，則形成新的染色體A =3,2,4,5,9,|10,

32、1,6,7,8，B =9,1,10,3,2,|8,7,6,4,5適應(yīng)度函數(shù)：f=h/l (h=刀(w.h)/W，l為排放完成后的最大長度)混合了 GA的改進(jìn)PSO算法描述如下：Xtj為原子j的當(dāng)前位置，f(Xtj )為適應(yīng)度，gbest為當(dāng)前所有原子的最佳，pbest 為原子j當(dāng)前最佳。for(i=O;i tmax;i+ +)for(j= 0; j pbestj)t+1 pbestj=f(X j);for(k= 0;k f(gbest)gbest = pbesk;3. 上述算法在矩形排樣件中的應(yīng)用分類序號作者算法名研究類型1楊傳華，李亞斤等基于最低水平線的二維搜索算法3RF ,2SP2Edm

33、und K.Burke,MatthewR.Hyde* ,GrahamKe ndallA squeaky wheel optimisati on(SWP 4OF ,2SP3Fran kG.Ortma nn,Nthabise ng Nte ne,Jan H. van Vuure n *Modifiedsize-alter nat ingstack algorithm(SASm)5RG ,2SP4Fran kG.Ortma nn,Nthabise ng Nte ne,Jan H. van Vuure n *Best fitwithstack ingalgorithm (BFS) 5RG ,2SP5張

34、偉，安魯陵，邵曉明，鄭 盈盈.一種矩形件分層排樣算法8RG ,2SP6張偉,安魯陵,孫金虎基于二維裝箱冋題的矩形件排樣算法10RF ,2BP7陳仕軍，曹矩矩形件優(yōu)化排樣的一種啟發(fā)式算法11OF ,2SP8彭文一種快速的有約束矩形件的優(yōu) 化排樣模型12RG ,2SP9QI Ji, HUANGLan, TANYingImprovedParticleSwarmOptimizati on Algorithm for Recta ngularCutt in g-StockProblem13OF ,2SP4. 參考文獻(xiàn)1 鄧東梅，周來水矩形件排樣的研究進(jìn)展.AEROSPAC時ATERIALS& TECHN

35、OLOGY.2006 36(5).2趙曉東.矩形件優(yōu)化排樣算法的研究與實(shí)現(xiàn).大連交通大學(xué)碩士學(xué)位論文，20023. 楊傳華，吳錦文，李亞匠，郭士清，康金波，姜東化 .定序列矩形件優(yōu)化排 樣的二維搜索算法.佳木斯大學(xué)學(xué)報(自然科學(xué)版),2010 28(3).4. Edmund K.Burke, MatthewR.Hyde* ,Graham Kendall.A squeaky wheel optimisati on methodology for two-dime nsio nal strip pack in g.Computers and Operations Research (2010), doi:10.1016/j.cor.2010.10.0055. Frank G. Ortmann, Nth