亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        離散粒子群算法在矩形排樣問題上的應(yīng)用研究

        2018-08-10 05:39:26
        關(guān)鍵詞:排樣鏈表矩形

        陳 釗

        (安徽職業(yè)技術(shù)學(xué)院 實(shí)訓(xùn)中心,安徽 合肥 230011)

        關(guān)鍵字: 離散粒子群算法;矩形排樣;組合優(yōu)化;

        矩形件優(yōu)化排樣是在給定的板材上將待排矩形件按照最優(yōu)方式進(jìn)行排布, 以便最大限度地利用材料, 其實(shí)質(zhì)就是一個組合優(yōu)化的二維布局問題, 但至今仍無法找到解決該問題的有效多項式時間算法。對于矩形優(yōu)化排樣問題的研究,主要有啟發(fā)式算法的研究、基于人工智能算法的研究以及基于運(yùn)籌學(xué)方法的研究,都取得了很多成果。近年來,基于人工智能算法對于排樣問題的研究是現(xiàn)在和未來研究的重點(diǎn)。

        1 問題描述

        粒子群優(yōu)化算法( Particle Swarm Optimization) 是由Kennedy 和Eberhart[1,2]于1995 年在鳥群、魚群和人類社會行為規(guī)律的啟發(fā)下提出的一種基于群智能的演化計算技術(shù)。他們提出了PSO算法的離散二進(jìn)制版,但這只是在對經(jīng)典連續(xù)性PSO問題的針對性修改,并沒有考慮到離散型問題組合優(yōu)化的特點(diǎn)。Clerc[3]提出的DPSO算法,說明了解決離散型問題的關(guān)鍵在于對于問題域的定義及其對于PSO算法相關(guān)的數(shù)學(xué)對象和運(yùn)算規(guī)則的定義。鐘一文等[4]利用DPSO很好的解決了TSP問題。針對矩形優(yōu)化排樣問題,由于排樣序列不是連續(xù)的序列而是一串不重復(fù)且屬于一定范圍內(nèi)的離散型序列,因此屬于離散型組合優(yōu)化問題。本文通過固定的排樣規(guī)則(剩余矩形排樣法)將原本復(fù)雜的二維排樣問題轉(zhuǎn)換成為可以求解組合優(yōu)化的問題,對離散粒子群算法進(jìn)行了改進(jìn),根據(jù)所求解問題及離散量運(yùn)算的特點(diǎn),對粒子的位置、速度等量及其運(yùn)算規(guī)則進(jìn)行了重新定義,取得了很好的結(jié)果。

        2 建立解決問題模型

        2.1 下料規(guī)則(剩余矩形排樣法)

        本文采用的是剩余矩形排樣法,構(gòu)造了三個矩形鏈表,分別為剩余矩形鏈表、待排矩形鏈表、已排矩形鏈表。任何沒有被排樣的空間,都在矩形鏈表中表示。形成方法如下:

        (1)初始剩余矩形鏈表中僅有一個矩形,即母板(0,Height,Width,0)。

        (2)從待排矩形鏈表中取出一個矩形,同時刪除該結(jié)點(diǎn)。在剩余矩形集合中找到一個能放下該矩形件的剩余矩形,將該矩形件放置在剩余矩形的左下角(滿足BL條件),將位置記錄并加入已排矩形鏈表,同時剩余矩形鏈表中每個剩余矩形都減去該矩形所占的位置,形成新的剩余矩形,如下圖所示,切割后形成兩個剩余矩形R1和R2,它們有共同的重合部分(虛線部分)。

        剩余矩形排樣法排樣示意圖

        (3)由于新的剩余矩形的產(chǎn)生,會引起原剩余矩形鏈表的改變,因此對其(虛線部分)進(jìn)行調(diào)整:去掉面積為零的或已無法排下的所剩的任何一個矩形件的剩余矩形;去掉和已排矩形有相交關(guān)系的剩余矩形;把具有完全包含關(guān)系的剩余矩形中面積小的矩形去除、有相交關(guān)系的矩形全部保留。得到新的剩余矩形集合,為下一次排樣使用。

        (4)當(dāng)待排鏈表非空時,轉(zhuǎn)到第2步繼續(xù)進(jìn)行排樣。如空則結(jié)束排樣,計算出板材利用率。

        2.2 矩形排樣問題的數(shù)學(xué)模型

        根據(jù)上述排樣規(guī)則,可以總結(jié)本文研究的矩形排樣問題的目標(biāo)函數(shù)和約束條件為:

        (1)

        (2)

        3 改進(jìn)離散粒子群算法

        Clerc說明了解決離散型問題的關(guān)鍵在于對問題域的定義及PSO算法相關(guān)的數(shù)學(xué)對象和運(yùn)算規(guī)則的定義,包括:粒子的位置表示;粒子的速度表示;位置與速度的加法運(yùn)算規(guī)則;位置的減法運(yùn)算規(guī)則;速度的加法和乘法運(yùn)算規(guī)則。本文對于離散粒子群算法進(jìn)行重新定義,如下:

        (1)粒子的位置表示。粒子的位置X定義為一個整數(shù)序列X =(x1,x2, x3,……,xn),1≤i≤n,1≤Xi≤n。并且序列中所有成員不能重復(fù)并且屬于1-n(n為待排矩形件零件的個數(shù)),表示為待排矩形零件的排樣順序。Xi的值為待排矩形零件的編號,表示為編號為Xi的零件的排樣順序為i。例如:X = (3,2,1,4,5)就是一個位置,x1= 3表示編號為3的零件的排樣順序為1即第一個排。

        (2)粒子的速度表示。粒子的速度定義為一個整數(shù)序列V = (v1,v2,v3,……,vn),1≤i≤n,1≤Vi≤n。同樣序列中所有成員不能重復(fù)并且屬于1-n,表示為一個交換序列。Vi 的值為該位置Xi交換對象的坐標(biāo)。例如:V = (2,3,1,4,5)就是一個速度,v1= 2表示為x1的交換對象為x2。

        (3)位置與速度的加法運(yùn)算規(guī)則。位置與速度相加得到一個新的位置,X’= X + V ,即:

        (3)

        式(3)說明,如果Vi=i的話Xi不變,否則,Xi 與Xvi 交換。該交換序列從第1位到第n位依次進(jìn)行交換,循環(huán)執(zhí)行,交換的次數(shù)為vi≠i的個數(shù)。例如:X =(3,2,1,4,5),V = (2,3,1,4,5)則X + V = (3,1,2,4,5)。

        (4)位置的減法運(yùn)算規(guī)則。倆個位置相減得到一個速度,V=X′-X,即:

        X′i-Xi=j;X'j=Xi

        (4)

        式(4)說明,X′-X得到為Xi在X’中的下標(biāo)。例如:X =(3,2,1,4,5),V = (2,

        3,1,4,5)則X - V = (2,1,3,4,5)。

        (5)速度的加法和乘法運(yùn)算規(guī)則。兩個速度的相加即為兩個交換序列的相加,相加的規(guī)則和X + V類似。其中,Rand()為一個在0和1范圍之內(nèi)的隨機(jī)數(shù);V為以一定概率保留。

        (5)

        速度的乘法運(yùn)算為

        (6)

        (6)粒子的運(yùn)動方程。通過以上的定義,可以將經(jīng)典的PSO算法的公式改為:

        V’ =V+C1*(Xpbest-X) +C2*(Xgbest-X);

        (7)

        X’=X+V;

        (8)

        其中,慣性權(quán)值W=1,C1和C2為學(xué)習(xí)因子設(shè)為2。

        4 實(shí)驗及結(jié)果分析

        (1)實(shí)驗數(shù)據(jù)。該算法采用C++編寫,經(jīng)算法仿真數(shù)據(jù)的經(jīng)典算例,算例一為25個矩形的排樣問題:將15*40的矩形分成25個小矩形進(jìn)行排樣。算例二為50個矩形的排樣問題:將15*40的矩形分成50個小矩形進(jìn)行排樣。

        (2)參數(shù)設(shè)置。兩個算例的參數(shù)設(shè)置均為:W=1,C1=C2=2,初始種群的粒子數(shù)為100個,迭代終止條件為運(yùn)行100代。

        (3)實(shí)驗結(jié)果。算例一的實(shí)驗結(jié)果為高度15,寬度42,板材利用率為95.24%,對比結(jié)果如表1所示;算例二的實(shí)驗結(jié)果為高度15,寬度42,板材利用率為95.24%,對比結(jié)果如表2所示。

        表1 25矩形排樣問題

        表2 50矩形排樣問題

        實(shí)驗結(jié)果對比顯示本文提出的算法所求得的最優(yōu)解要優(yōu)于宋佩華等人[5]的離散粒子群算法,李滿江等人[6]與王竹婷[7]提出的遺傳算法所求得的最優(yōu)解,材料利用率更是達(dá)到了95%以上,說明了本文提出的改進(jìn)離散粒子群算法的有效性和先進(jìn)性。

        猜你喜歡
        排樣鏈表矩形
        兩矩形上的全偏差
        基于二進(jìn)制鏈表的粗糙集屬性約簡
        化歸矩形證直角
        跟麥咭學(xué)編程
        基于鏈表多分支路徑樹的云存儲數(shù)據(jù)完整性驗證機(jī)制
        基于壓縮因子粒子群的組合排樣的研究
        從矩形內(nèi)一點(diǎn)說起
        U形電器支架的多工位模具的排樣及模具設(shè)計
        人工智能技術(shù)在排樣技術(shù)上的發(fā)展現(xiàn)狀
        薄板沖模排樣設(shè)計及防跳廢料解決方案
        亚洲av影院一区二区三区四区| 国产高清在线精品一区app| 久久久久免费看成人影片| 国产精品福利视频一区| 亚洲av日韩片在线观看| 亚洲一区二区av免费观看| 国产亚洲成性色av人片在线观| 蜜桃视频无码区在线观看| 久草视频国产| 国产精品va无码一区二区| 色综合久久无码中文字幕app| 中文字幕av久久激情亚洲精品| 亚洲av日韩一卡二卡| 欧美又大又色又爽aaaa片| 亚洲欧美成人一区二区在线电影| 亚洲成a人片在线网站| 用力草我小逼视频在线播放| 99久久婷婷国产精品综合网站| 亚洲日韩小电影在线观看| 又粗又黄又猛又爽大片免费| 婷婷四房播播| 免费在线观看亚洲视频| 亚洲男人综合久久综合天堂| 国产自国产自愉自愉免费24区| 国产精品免费大片| 亚洲a人片在线观看网址| 男人天堂插插综合搜索| 久久久久久欧美精品se一二三四| 久久av无码精品人妻出轨| 巨臀精品无码AV在线播放| 日韩av天堂一区二区| 久久香蕉国产线看观看精品yw| 欧美一欧美一区二三区性| 精品国产三级国产av| 日本欧美大码a在线观看| 韩国精品一区二区三区无码视频| 国产精品涩涩涩一区二区三区免费| 毛片在线播放亚洲免费中文网| 无码国产精品一区二区免费式直播 | 天堂无码人妻精品av一区| 精品人妻中文av一区二区三区 |