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

        ?

        面向智能工廠應(yīng)用的啟發(fā)式板材排樣優(yōu)化算法

        2020-11-17 12:24:30張紅艷趙宏軍孫嘉玉李云志朱明皓
        關(guān)鍵詞:緊密度排樣模擬退火

        高 勃,張紅艷,趙宏軍,孫嘉玉,李云志,朱明皓

        (1.北京交通大學(xué) a.計(jì)算機(jī)與信息技術(shù)學(xué)院,b.經(jīng)濟(jì)管理學(xué)院, 北京 100044;2.北京機(jī)械工業(yè)自動(dòng)化研究所有限公司,北京 100120;3.國家工業(yè)信息安全發(fā)展研究中心 系統(tǒng)所,北京 100043)

        在智能制造過程中,企業(yè)為提高經(jīng)濟(jì)效益,需要最大化地節(jié)約成本,給出企業(yè)合理的訂購原材料的方案,減少材料浪費(fèi),提高企業(yè)效益.二維排料廣泛應(yīng)用于汽車制造、造船、鋼鐵切割、服裝設(shè)計(jì)剪裁,家具下料[1]等工業(yè)設(shè)計(jì)與生產(chǎn)中,屬于典型的NP完全問題.對二維排樣進(jìn)行優(yōu)化是必要的,以此來提高

        板材的利用率.在工業(yè)生產(chǎn)實(shí)踐中,有許多因素會(huì)影響原材料的利用率,比如操作人員的技術(shù)能力,設(shè)備的切割誤差,排樣方案等,其中排樣方案的好壞對原材料的利用率起著決定性的作用.

        目前國內(nèi)外學(xué)者對矩形件優(yōu)化排樣問題做了廣泛的研究,最初的排樣算法往往根據(jù)矩形件信息進(jìn)行直接排樣,例如文獻(xiàn)[2]提出基于動(dòng)態(tài)分割和合一的排樣算法.文獻(xiàn)[3]提出貪婪算法進(jìn)行矩形件的排樣,每次排樣時(shí)優(yōu)先選擇面積最大的矩形件,以此來實(shí)現(xiàn)板材利用率最高的目標(biāo).雖然算法簡單,但板材的利用率低.而后采用較多的方法是文獻(xiàn)[4-7]所提到的模擬退火算法,遺傳算法,蟻群算法等智能算法.雖然智能算法的應(yīng)用使得板材利用率有所提高,但智能算法計(jì)算開銷較大,隨著企業(yè)的生產(chǎn)規(guī)模變得越來越大,排料系統(tǒng)的可行性往往會(huì)因?yàn)橛?jì)算時(shí)間的劇增而不再具有實(shí)用性.近幾年學(xué)者根據(jù)零件特征對板材進(jìn)行啟發(fā)式填充處理,比如文獻(xiàn)[8]改進(jìn)了在矩形件排樣中的填充算法.文獻(xiàn)[9]提出矩形件簡單塊占角排樣方式的動(dòng)態(tài)規(guī)劃.文獻(xiàn)[10]采用基于粗糙集的矩形件優(yōu)化填充排樣方法.文獻(xiàn)[11]提出了啟發(fā)式動(dòng)態(tài)分解算法,根據(jù)矩形件對板材進(jìn)行正交動(dòng)態(tài)分解,計(jì)算放置耦合度選擇最佳子板,通過干涉關(guān)系對待排子板狀態(tài)更新.上述研究雖已取得一定的成果,但應(yīng)用不具有普遍性,仍存在一定的問題.

        基于以上分析,本文作者深入研究了在二維板材下矩形的問題,以最大化板材利用為目標(biāo),建立優(yōu)化排樣模型,在此基礎(chǔ)上提出了一種新的排樣算法——啟發(fā)式板材排樣優(yōu)化算法,以最大化板材利用率為目標(biāo),設(shè)計(jì)評價(jià)函數(shù),通過比較評價(jià)函數(shù)值進(jìn)行剪枝優(yōu)化,加快排樣過程中零件的定位及定序,進(jìn)而縮短時(shí)間,給出企業(yè)合理訂購原材料的方案,并通過案例分析驗(yàn)證了該算法的有效性.

        1 二維規(guī)則板材排樣問題與數(shù)學(xué)描述

        1.1 問題描述

        面對節(jié)約性和可持續(xù)發(fā)展的要求,在智能工業(yè)生產(chǎn)過程中,以減少原材料浪費(fèi)為目標(biāo),給出企業(yè)合理的原材料調(diào)度與儲(chǔ)備方案,需要在平面區(qū)域內(nèi)給出零件排列的最優(yōu)布局,最大化利用板材,減少材料的浪費(fèi).實(shí)際生產(chǎn)中,排料的種類有很多,常見的原材料和零件有矩形、圓形以及不規(guī)則的形狀.針對上述問題,本文主要采用針對二維規(guī)則板材下的矩形優(yōu)化切割排樣算法.

        對于規(guī)則板材的矩形件排樣問題具體數(shù)學(xué)表述如下

        (1)

        在矩形件排樣過程中需要滿足以下約束條件:1)矩形件rj排列在板材區(qū)域內(nèi);2)不同的矩形件ri和rj(i≠j)排列不能重疊;3)矩形件rj的邊與板材邊平行.

        1.2 排樣數(shù)學(xué)模型

        基于上述分析,以最大限度地節(jié)省原材料為目標(biāo)函數(shù),構(gòu)建優(yōu)化目標(biāo),即

        (2)

        定理1式(2)中的最小化優(yōu)化函數(shù)等價(jià)式(3)給出的最大化優(yōu)化函數(shù),即

        (3)

        證明 式(2)的優(yōu)化目標(biāo)等價(jià)為

        (4)

        (5)

        于是,定理1證畢.

        基于定理1,矩形件排樣過程中需要滿足

        (6)

        (7)

        xi+li≤W

        (8)

        yi+wi≤H

        (9)

        xi+li≤xj∪yi+wi≤yj

        (10)

        xj+lj≤xi∪yj+wj≤yi

        (11)

        xi,j,yi,j≥0

        (12)

        i=j=1,2,…,m

        (13)

        從所構(gòu)建的數(shù)學(xué)模型可知,其變量是離散不連續(xù)的,問題的解也是離散的,因此矩形件排樣問題是約束離散優(yōu)化問題.一方面,由于該問題是非線性的,傳統(tǒng)的解析法無法求解.同時(shí)由于排樣問題是NP完全問題,這類問題在理論上存在一種算法可求得最優(yōu)解,但求解時(shí)間隨著問題規(guī)模的增長呈指數(shù)關(guān)系增加,在生產(chǎn)實(shí)際中過長的求解時(shí)間是不可接受的.因此,本文提出一種基于啟發(fā)式的板材排樣優(yōu)化算法,通過剪枝優(yōu)化,在提高板材利用率的同時(shí),縮短時(shí)間,提高求解問題的效率.

        2 啟發(fā)式板材排樣優(yōu)化算法

        2.1 基本思想

        針對矩形件排樣,假定每次排樣總是將零件排列在板材(L,W)的左下方,排樣過程就是求解零件的最優(yōu)排列位置,將板材和零件置于同一個(gè)二維平面,則零件的位置(x,y)可根據(jù)矩形件的長寬和排列方式確定.實(shí)際中,約定按照大件優(yōu)先原則進(jìn)行排樣,取得盡可能大的利用率的原則進(jìn)行優(yōu)化排樣.以3個(gè)矩形(A,B,C)為例,在排樣的過程中,可看作為排樣樹,如圖2所示.

        由圖2可得,3個(gè)矩形所構(gòu)成的排樣樹分支數(shù)已經(jīng)很多,在實(shí)際的工業(yè)大規(guī)模生產(chǎn)中,工件種類多、數(shù)量大,構(gòu)成的排列樹的分支數(shù)會(huì)急劇增加,屬于計(jì)算復(fù)雜性較高的一類NP完全問題,隨著零件的增加解的數(shù)量成指數(shù)倍數(shù)增長,因此確定性算法在龐大的解空間中尋找最優(yōu)解的時(shí)間會(huì)急劇增加,達(dá)到讓人不可接受的程度.為了滿足生產(chǎn)需要,高效的求解矩形件排樣問題,并使排樣結(jié)果盡可能接近最優(yōu),本文提出了一種基于啟發(fā)式的板材排樣優(yōu)化算法,其是在狀態(tài)空間中的搜索對每一個(gè)搜索的位置進(jìn)行評估,得到最好的位置,再從這個(gè)位置進(jìn)行搜索直到最終目標(biāo).這樣可以省略大量無謂的搜索路徑,提高了效率.

        2.2 評價(jià)函數(shù)

        評價(jià)函數(shù)是啟發(fā)式算法剪枝優(yōu)化的重要依據(jù),關(guān)系到算法求解問題的效率,其設(shè)計(jì)取決于所要求解的優(yōu)化問題本身.評價(jià)函數(shù)利用當(dāng)前與問題有關(guān)的信息指導(dǎo)搜索過程,在排樣搜索過程中,通過比較評價(jià)函數(shù)值大小,決定要擴(kuò)展的下一個(gè)待排矩形件,省略大量無謂的矩形件試排搜索路徑,以免盲目地?cái)U(kuò)展搜索,從而加快排樣速度.針對板材排樣問題,給出了如下的評價(jià)函數(shù)

        (14)

        式中:ηrj表示當(dāng)前零件rj在板材上的利用率;γrj表示當(dāng)前零件rj的緊密度;srj為當(dāng)前零件面積;W為可行域面積,可行域指的是待排矩形件在當(dāng)前布局空間所有可行位置的集合.

        式(14)中定義了緊密度指標(biāo)γ,用于衡量量化零件之間的緊密程度.若緊密度越大,則這樣的啟發(fā)式放置將有效排列鄰接各物體,使得排樣中的未利用空隙越小,即容器的面積利用率越高.本文緊密度定義為當(dāng)前零件與已排零件之間的關(guān)系.

        假設(shè)已經(jīng)排列好的零件個(gè)數(shù)為k,放置新的零件時(shí),總是從已經(jīng)排好的零件出發(fā),使新排列的零件與已排列的零件具有緊密關(guān)系.假設(shè)當(dāng)前待排零件rj的中心點(diǎn)為(xj,yj),已排零件的中心點(diǎn)為(xci,yci),則中心點(diǎn)歐式距離為

        臺(tái)式高速冷凍離心機(jī)SG3-18K購于Sigma公司;5424R高速冷凍離心機(jī)購于德國 Eppendorf公司;CFX96 Deep Well Real-time System、QX200 Droplet dPCR系統(tǒng)購于美國Bio-rad公司;Tissue Lyser II組織研磨儀、QIAxpert核酸濃度檢測儀購于德國 Qiagen公司。

        在選擇排樣放置位置時(shí),選取最小歐式距離的零件,即當(dāng)前零件與已經(jīng)排列好的零件之間的距離為d=min (d1,d2,…,dk).如圖3所示,求當(dāng)前零件rj與已排零件B之間的距離.當(dāng)零件rj橫放時(shí),緊貼零件B,中心距離為d1;當(dāng)零件rj豎放時(shí),中心距離為d1′.

        依次類推,求出當(dāng)前待排零件與所有已排零件的距離,比較得出最小值d,記錄緊貼零件ri,記錄rj的擺放位置是橫放或豎放.距離越小,說明零件之間的緊密度越大,則緊密度記為γrj=1/d.

        2.3 算法流程

        在矩形件優(yōu)化排樣中,矩形件的排放順序和排放方式,影響著板材的利用率.

        2.3.1 排樣矩形件定序

        待排矩形件的排放順序(矩形件定序)是每種排樣算法不可避免考慮的問題.在排樣研究中,部分算法通??紤]矩形件自身屬性特征,比如面積大小、長寬比等.根據(jù)式(14)給出的評價(jià)函數(shù),提出的算法對尚未排樣的矩形件在矩形空間的利用價(jià)值進(jìn)行評價(jià),找到其中最大的評價(jià)函數(shù)值Fj=max (Fi,i=1,…,m),則rj作為當(dāng)前待排的矩形件.

        2.3.2 排樣矩形件定位

        確定待排矩形件的排放順序后,優(yōu)化當(dāng)前待排零件在布局空間中的擺放位置.根據(jù)2.2節(jié)提到的緊密度策略,得出:

        1)計(jì)算緊密度值最大放置矩形件,如存在多個(gè)零件與該零件的緊密度值最大,則進(jìn)行下一步驟;

        2)比較多個(gè)零件的中心坐標(biāo)值(xcj,ycj),若xck

        2.3.3 算法主要步驟

        算法的主要步驟如圖4所示.

        3 實(shí)驗(yàn)驗(yàn)證及算法性能分析

        3.1 實(shí)驗(yàn)環(huán)境及參數(shù)設(shè)置

        算法采用1.2節(jié)給出的板材排樣模型,采用 Hopper 和Turton給出的C1~C5組公開案例[12],同時(shí)另定義一組測試案例C6,板材大小為2 000 cm1 500 cm,所用矩形件規(guī)格和數(shù)量分別為:90 cm120 cm, 30;150 cm100 cm,30;280 cm120 cm,28;150 cm250 cm,20;60 cm50 cm,10;50 cm150 cm,5;180 cm220 cm,4;55 cm80 cm,4.

        為驗(yàn)證本文算法的有效性,將其與貪婪算法、模擬退火算法在相同的案例數(shù)據(jù)下分別進(jìn)行比較.貪婪算法因其算法簡單,在最初研究排樣時(shí)廣泛應(yīng)用,其基本思路是從問題的某個(gè)初始可行解出發(fā),逐步向目標(biāo)函數(shù)靠攏.模擬退火算法為當(dāng)前解決問題中常用的智能算法,是解決組合優(yōu)化問題的隨機(jī)搜索技術(shù),不斷對當(dāng)前解迭代,從而達(dá)到使目標(biāo)函數(shù)最優(yōu).

        模擬退火算法設(shè)置迭代次數(shù)為200,溫度T的初始值設(shè)置是影響模擬退火算法全局搜索性能的重要因素之一,雖T值越大性能越高,但速度也越慢,通常設(shè)置初始溫度T=1 000、終止條件T<1,衰減函數(shù)T′=0.9T.使用Matlab搭建了實(shí)驗(yàn)環(huán)境進(jìn)行了仿真實(shí)驗(yàn),針對實(shí)驗(yàn)結(jié)果進(jìn)行算法性能分析.

        3.2 算法性能分析

        3.2.1 板材利用率分析

        表1中給出3種算法在測試案例數(shù)據(jù)下的板材利用率,所用板材數(shù)以及算法運(yùn)行時(shí)間的情況.由表1中數(shù)據(jù)可得,在案例數(shù)據(jù)C1和C2中,本文算法得板材利用率雖不是最優(yōu),但隨著矩形件數(shù)量及種類的增加,本文算法相比于另外兩種算法都有較大的提高,因此,本文提出的啟發(fā)式優(yōu)化算法表現(xiàn)出較強(qiáng)的全局尋優(yōu)能力.

        表1 不同算法性能比較

        圖5為測試案例C6下3種算法的排樣結(jié)果.從圖5中可以看出本文算法排樣結(jié)果相對規(guī)整,產(chǎn)生的空隙廢料少,具有較好的排樣效果.

        3.2.2 時(shí)間復(fù)雜度分析

        根據(jù)表1可知,不同算法耗時(shí)情況隨著矩形件數(shù)量的增加,本文算法排樣時(shí)間仍保持較低增長且耗時(shí)遠(yuǎn)低于模擬退火算法,而模擬退火算法耗時(shí)急劇上升.另外,由于模擬退火算法中通過退火溫度控制著求解過程向最小值的優(yōu)化方向進(jìn)行,通常情況下,為了能夠使求解的值接近全局最優(yōu)解,退火速度會(huì)設(shè)置較小值,則增加了運(yùn)算規(guī)模.因此在大規(guī)模工業(yè)生產(chǎn)中,會(huì)耗費(fèi)大量時(shí)間,不符合實(shí)際生產(chǎn)需求.

        4 結(jié)論

        1)本文提出的啟發(fā)式板材排樣優(yōu)化算法,主要是利用問題本身的信息作為啟發(fā)式的搜索信息,通過分析零件之間的緊密度及利用率,設(shè)計(jì)評價(jià)函數(shù).在排樣過程中,通過比較評價(jià)函數(shù)值的大小,可進(jìn)行剪枝,在提高利用率的同時(shí),縮短時(shí)間.

        2)實(shí)驗(yàn)結(jié)果表明所提方案的有效性和可行性,符合現(xiàn)代大規(guī)模工業(yè)生產(chǎn)的需求.

        本算法還可以進(jìn)一步研究,比如考慮板材為不規(guī)則板材以及裁剪的零件為多邊形零件或不規(guī)則零件,使研究方案更加符合生產(chǎn)需求,尋找合理的方法解決后續(xù)的問題.

        猜你喜歡
        緊密度排樣模擬退火
        利用高通量表型平臺(tái)分析紫葉紫菜薹新組合19-520的表型特征
        時(shí)事政治融入高中思想政治課的及時(shí)性和緊密度研究
        模擬退火遺傳算法在機(jī)械臂路徑規(guī)劃中的應(yīng)用
        基于壓縮因子粒子群的組合排樣的研究
        中歐貿(mào)易發(fā)展?jié)摿Φ膶?shí)證分析
        基于模糊自適應(yīng)模擬退火遺傳算法的配電網(wǎng)故障定位
        基于情感緊密度的社交網(wǎng)絡(luò)推薦算法
        商(2016年2期)2016-03-01 08:52:18
        U形電器支架的多工位模具的排樣及模具設(shè)計(jì)
        SOA結(jié)合模擬退火算法優(yōu)化電容器配置研究
        人工智能技術(shù)在排樣技術(shù)上的發(fā)展現(xiàn)狀
        午夜视频在线在免费| 中文字幕一区二区三在线| 国产成人一区二区三区| 日本饥渴人妻欲求不满| 一夲道无码人妻精品一区二区| 狠狠久久久久综合网| 果冻蜜桃传媒在线观看| 东风日产车是不是国产的| 国产精品日本一区二区在线播放 | 亚洲乱在线播放| 十八禁视频网站在线观看| 色老头在线一区二区三区| 岛国大片在线免费观看| 国产精品女同二区五区九区 | 久久99国产精品久久| 久久久久久久久888| 久久99久久99精品免视看国产成人| 亚洲国产av综合一区| 伊人加勒比在线观看视频| 欧美成免费a级毛片| 亚洲中文字幕乱码| 啪啪视频一区二区三区入囗| 激情偷拍视频一区二区| 中文字幕一区二区三区四区| 日本无码欧美一区精品久久 | 中文字幕第一页亚洲观看| 女优av性天堂网男人天堂| 后入到高潮免费观看| 人妻丰满熟妇av无码区hd| 国产亚洲AV无码一区二区二三区| 亚洲中文字幕一区高清在线| 国产精品女同久久久久电影院| 男人边吻奶边挵进去视频| 亚洲日日噜噜噜夜夜爽爽| 中文字幕第一页人妻丝袜| 特级毛片爽www免费版| 激情人妻在线视频| 日本免费播放一区二区| 国产精品爽爽久久久久久竹菊| 精品乱码一区二区三区四区| 日韩精品成人一区二区三区久久久|