• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

    基于遺傳算法對二維下料問題的研究

    2020-03-24 11:51:15田康
    科技風(fēng) 2020年9期
    關(guān)鍵詞:遺傳算法

    摘要:切割問題是生活中常見的一類問題。本文依據(jù)線性規(guī)劃方程和遺傳算法來研究矩形切割問題。對于復(fù)雜的二維下料問題,所需木板樣件的種類樣式增多,可采用遺傳算法,改變木板切割的適應(yīng)度函數(shù),從而實現(xiàn)木板切割的利用率最大化。

    關(guān)鍵詞:線性規(guī)劃方程;遺傳算法;二維下料

    矩形切割問題是二維切割一個重要研究方向,怎樣實現(xiàn)木材最優(yōu)化切割,使木板的利用率達到最高,是工業(yè)生產(chǎn)的重要課題。近幾年來,隨著傳統(tǒng)算法的發(fā)展,各種智能算法的不斷完善著矩形切割的方案。而本文是利用遺傳算法探究在一塊木板上的二維下料問題。

    一、單一木板切割模型的建立

    僅含一種約束條件:假設(shè)對一個長為3000mm、寬為1500mm的矩形木板進行切割,需要得到n個矩形原件P1(長為373mm寬為201mm)。不考慮木板的厚度,怎樣切割才能得到最多的矩形原件P1,實現(xiàn)木板的利用率最大化呢?

    木板利用率與切割出的小矩形的數(shù)量成正相關(guān)。依據(jù)運籌學(xué)中的整數(shù)規(guī)劃問題,可將切割問題分為橫向切割和縱向切割兩種方案。由于斜向切割會造成原料的濫用且討論情況更復(fù)雜,所以不采用斜向切割的方式。通過構(gòu)建線性規(guī)劃方程組,以木板的長、寬為限制條件,得出使木板材料剩余面積最小的方案。

    根據(jù)木板的排放方式,建立整數(shù)規(guī)劃方程組:

    式中:木板的長與寬分別為L、W;P1原件的長與寬分別為l1、w1;m表示將P1原件的寬w1沿著木板的L方向排列的個數(shù);b指P1原件的長l1沿著木板的W方向排列的個數(shù)。運用LINGO軟件對方程組求解得:m=13,n=1,a=0,b=4.即目標(biāo)值z=44888,但并不是最優(yōu)方案。

    分析求解結(jié)果得,P1原件的寬沿著木板的長排列最多可排13列;P1原件的長沿著木板的寬排列最多可排4行。此時木板的長邊剩余387mm,寬邊剩余8mm,所以可再放置一個P1原件的長邊。故仍可以排放7個P1原件。綜上所述,在木板上切割P1原件時,當(dāng)切割59個P1板時,木板利用率為98.3%,達到最高利用率。

    二、多元木板切割模型的建立

    兩種約束條件的切割方案:現(xiàn)多考慮一個矩形原件P3(長度為406mm,寬為229mm)。由于矩形原件P3的切排樣方式不定,加深求解的難度。針對NP類問題可建立有關(guān)遺傳算法的數(shù)學(xué)模型進行求解。

    構(gòu)建一個函數(shù):

    k(x)=1x0

    0x<0(1)

    由于切割原件在排放時受到木板尺寸的影響,且每個原件之間的排放互不重疊,依此建立如下方程:

    k(xli-xrj)+k(yti-ybj)+k(xlj-xri)+k(ytj-ybi)1(2)

    式中:第i個原件排放在第j個原件后面,且i

    (1)遺傳算法的建立:

    首先初始化種群,對各個矩形原件采用符號編碼,將兩種原件命名為1、2。原件既可橫排也可豎排,取橫排為正,豎排為負。下面以P1、P3原件在長為635mm,寬為610mm的木板上的排放為例,p={1,1,2,2}表示底層豎排一個原件P1,再橫排一個原件P1,第二層先橫排一個原件P3,再豎排一個一個原件P3。

    其次構(gòu)建適應(yīng)度函數(shù)。將木板利用率作為函數(shù),得到適應(yīng)度函數(shù)方程:

    H(p)=h(p)LW=∑niliwiLW(3)

    式中:H(p)表示算子,指編碼為p的個體的面積,ni為標(biāo)號為i的原件的出現(xiàn)次數(shù),li、wi分別表示標(biāo)號為i的原件的長與寬(這里的i與方程(4)約束條件中的i有區(qū)別)。其余參量均取默認值。

    (2)初始化種群的構(gòu)建:

    由于初始化種群的編碼較多,一般初始種群的大小要在20個以上,可采用逐層排列生成初始化種群。

    步驟一:建立一個坐標(biāo)系,確定上限寬度與長度(即木板尺寸)。

    步驟二:生成一個隨機序列數(shù),取值在集合{2,1,1,2}內(nèi),表示待排樣的原件。

    步驟三:根據(jù)隨機數(shù),將木塊從左往右按層排列。

    步驟四:當(dāng)排樣高度達到寬度限度時,跳出循環(huán),給出排列編碼。

    步驟五:重復(fù)上述步驟,直至給出20個以上的初始個體,構(gòu)建成一個初始化種群。

    (3)模型的求解:

    運用MATLAB實現(xiàn)遺傳算法,可得三種利用率較高的方案:

    在實際生產(chǎn)中,所需原材料的種類是多樣的(不僅限于矩形),求解情況更加復(fù)雜。對于多種約束條件,仍然利用遺傳算法,加入新的約束條件,對適應(yīng)度函數(shù)進行改造。

    H(p,N)=h(p)NLW=∑niliwiNLW

    P=P{p1,p2,…,pn}(4)

    式中:ni是已知量,N是待求解量。然后改造初始化種群,對所加的參數(shù)Ci對原件進行計數(shù),引入?yún)?shù)N對木板計數(shù)。合并每個板的編碼排序,一個板組成一個編碼,原件全部排完時構(gòu)成P。進一步對初始種群改造,再次建立坐標(biāo)系。

    三、評價與總結(jié)

    本文構(gòu)建的模型中沒有給出具體的解碼算法和篩選算法,另外遺傳算法也的穩(wěn)定性較差,因為算法屬于隨即類算法,對初始種群有很強的依賴性,不同的初始種群得到結(jié)果與速度也不盡相同??刹捎媚M退火算法和蟻群算法相結(jié)合,當(dāng)面臨實際解決時,可以通過構(gòu)建這兩個算法解決人力解碼的問題。

    參考文獻:

    [1]馬廣焜,劉嘉敏,黃有群,等.一種有約束矩形排樣問題的求解算法[J].沈陽工業(yè)大學(xué)學(xué)報,2006,28(4).

    [2]趙新芳,崔耀東,楊瑩,等.矩形件帶排樣的一種遺傳算法[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報,2008,20(4):540544.

    作者簡介:田康(2000),男,漢族,安徽銅陵人,本科,研究方向:信號處理。

    指導(dǎo)老師:楊靜(1980),漢族,安徽濉溪人,博士,副教授,研究方向:DNA計算與組合優(yōu)化。

    猜你喜歡
    遺傳算法
    基于遺傳算法的模糊控制在過熱汽溫控制系統(tǒng)優(yōu)化中的應(yīng)用
    電子制作(2019年16期)2019-09-27 09:34:44
    遺傳算法對CMAC與PID并行勵磁控制的優(yōu)化
    基于自適應(yīng)遺傳算法的CSAMT一維反演
    基于遺傳算法的建筑物沉降回歸分析
    一種基于遺傳算法的聚類分析方法在DNA序列比較中的應(yīng)用
    基于遺傳算法和LS-SVM的財務(wù)危機預(yù)測
    遺傳算法識別模型在水污染源辨識中的應(yīng)用
    協(xié)同進化在遺傳算法中的應(yīng)用研究
    軟件發(fā)布規(guī)劃的遺傳算法實現(xiàn)與解釋
    基于改進的遺傳算法的模糊聚類算法
    讷河市| 泽库县| 鲁山县| 介休市| 榆中县| 重庆市| 呼伦贝尔市| 杭州市| 荆州市| 芜湖市| 丹凤县| 凤阳县| 会同县| 固阳县| 大连市| 依安县| 海安县| 大洼县| 开鲁县| 神木县| 泗阳县| 南陵县| 休宁县| 高邮市| 林西县| 大理市| 琼海市| 英吉沙县| 荃湾区| 金阳县| 佛冈县| 天柱县| 中方县| 错那县| 邛崃市| 凉城县| 洛浦县| 扎赉特旗| 江永县| 疏勒县| 克东县|