不同支配關(guān)系的NSGA-III算法在機(jī)器人制造單元調(diào)度問(wèn)題中的應(yīng)用①

李曉輝,高 鐸,楊 晰,劉元東,趙 毅,董 媛

1(長(zhǎng)安大學(xué) 電子與控制工程學(xué)院,西安 710054)

2(陜西航天時(shí)代導(dǎo)航設(shè)備有限公司,寶雞 721099)

由于機(jī)器人制造單元對(duì)制造行業(yè)的生產(chǎn)效率和生產(chǎn)質(zhì)量有很大提高,近30年來(lái),生產(chǎn)調(diào)度問(wèn)題[1]已成為國(guó)內(nèi)外自動(dòng)控制領(lǐng)域、計(jì)算機(jī)科學(xué)等領(lǐng)域的研究熱點(diǎn).現(xiàn)代智能制造市場(chǎng)的需求越來(lái)越個(gè)性化、多樣化,使傳統(tǒng)的量產(chǎn)模式受到了極大的挑戰(zhàn).機(jī)器人制造單元在實(shí)現(xiàn)量產(chǎn)的同時(shí),能夠保持小批量定制生產(chǎn)的靈活性,能夠更好地適應(yīng)當(dāng)前智能制造發(fā)展的需求,而合理的優(yōu)化調(diào)度是機(jī)器人制造單元整體控制的一個(gè)重要方面.制造企業(yè)為了在激烈的競(jìng)爭(zhēng)環(huán)境中生存和發(fā)展,需要提供能夠滿足客戶各種需求的資源調(diào)度方案.單一目標(biāo)的尋優(yōu)已經(jīng)滿足不了人們?nèi)粘Ｉ畹男枰?工業(yè)上對(duì)于優(yōu)化目標(biāo)個(gè)數(shù)增多的要求使得求解問(wèn)題的難度顯著增加.目前,調(diào)度問(wèn)題的理論和實(shí)踐方法研究,仍不能滿足現(xiàn)實(shí)生產(chǎn)需求.傳統(tǒng)的優(yōu)化算法在解決復(fù)雜多目標(biāo)問(wèn)題中[2–5]常常效率低下,難以達(dá)到預(yù)期.智能優(yōu)化算法[6–9]通常是基于非劣解概念基礎(chǔ)上的現(xiàn)代啟發(fā)式算法,具有更好的處理高維多目標(biāo)問(wèn)題的能力.因此,在經(jīng)典車間調(diào)整理論的基礎(chǔ)上,本文要針對(duì)Pareto 支配關(guān)系在高維多目標(biāo)優(yōu)化中的支配能力不足,將另外兩種支配關(guān)系與NSGA-III 算法相結(jié)合去對(duì)生產(chǎn)調(diào)度問(wèn)題進(jìn)行求解去解決機(jī)器人制造單元優(yōu)化上的多目標(biāo)協(xié)同調(diào)度優(yōu)化問(wèn)題.

1 問(wèn)題描述

本文主要研究的是有關(guān)job-shop 類型的機(jī)器人的智能制造車間的搬運(yùn)問(wèn)題.Job-shop 類型的機(jī)器人制造單元主要由加工站、搬運(yùn)機(jī)器人和控制系統(tǒng)等組成.根據(jù)車間調(diào)度的工業(yè)路線特點(diǎn),可將job-shop 類型的機(jī)器人制造單元調(diào)度過(guò)程描述為:有n個(gè)工件J={J1,J2,···,Jn} 將在m臺(tái)加工機(jī)器M={M1,M2,···,Mm}上進(jìn)行加工,其中M0為裝載站兼卸載站.每個(gè)工件Ji有p道加工工序Oij={Oi1,Oi2,···,Oip},且每個(gè)工件都有預(yù)先設(shè)定好的工序加工順序,所有的工序都嚴(yán)格按照預(yù)定的加工工序順序在m臺(tái)機(jī)器上進(jìn)行.現(xiàn)已知每道工序的加工時(shí)間、每道工序?qū)?yīng)的加工機(jī)器和任意兩臺(tái)機(jī)器之間的搬運(yùn)時(shí)間.如圖1所示:調(diào)度基本過(guò)程可描述為,首先,n個(gè) 工件在M0上等待加工,當(dāng)加工任務(wù)開始時(shí),機(jī)器手按照工序順序,當(dāng)工件處于裝載區(qū)或工件上一道工序已完成時(shí),從該工件所在位置上取走工件并搬運(yùn)到該工件下一道工序?qū)?yīng)加工機(jī)器上,根據(jù)當(dāng)前加工機(jī)器狀態(tài)決定是否開始加工.當(dāng)最后一道加工工序完成后并由機(jī)器手將該工件搬運(yùn)至卸載站上時(shí),則為加工任務(wù)結(jié)束.

圖1 以搬運(yùn)機(jī)械人為中心的制造單元

近年來(lái),在生產(chǎn)過(guò)程中人們?cè)絹?lái)越關(guān)注能夠使多項(xiàng)決策目標(biāo)都能得到滿足的生產(chǎn)調(diào)度方案.通常考慮多個(gè)目標(biāo)共同優(yōu)化的方案.同時(shí),由于對(duì)環(huán)境問(wèn)題的重視,本文又引入了加工總能耗,生產(chǎn)總成本等一系列的綠色調(diào)度目標(biāo).以下是本文要優(yōu)化的5 個(gè)目標(biāo):

1)最大完工時(shí)間:

2)加工總能耗:

3)交貨期提前量:

4)交貨期延遲量:

5)生產(chǎn)總成本:

其中,最大完工時(shí)間指所有工件完成加工后的總加工時(shí)間,N為工序總數(shù);Ci為第i個(gè)工件的完工時(shí)間.加工總能耗指調(diào)度過(guò)程中機(jī)器加工總功率與機(jī)器手搬運(yùn)總功率之和.M為機(jī)器總個(gè)數(shù);Ni為第i個(gè)機(jī)器上的加工工序數(shù);tij為第i個(gè)機(jī)器上第j道工序的加工時(shí)間;Pm,i為第i個(gè)機(jī)器的加工功率;ti,idle為第i臺(tái)機(jī)器空載時(shí)間;Pi,idle為第i臺(tái)機(jī)器空載功率;Nb為機(jī)器手搬運(yùn)次數(shù);tb,i為第i次 搬運(yùn)所花費(fèi)的時(shí)間;Pb為機(jī)器手拌搬運(yùn)功率;tb,idle為機(jī)器手空載時(shí)間;Pb,idle為機(jī)器手空載功率.交貨期為制造企業(yè)交付加工產(chǎn)品的時(shí)間.若工件在理想交貨時(shí)間前完成生產(chǎn)則為提前,在理想交貨時(shí)間后完成則為延遲.N為工件個(gè)數(shù);DTj為第j工件的理想交貨時(shí)間;RTj為第j工件的實(shí)際交貨時(shí)間.生產(chǎn)總成本為加工所需電費(fèi)與機(jī)床使用成本之和.coste為電價(jià)(單位能耗成本);Etotal為加工總能耗;Cu,i為第i臺(tái)機(jī)器單位時(shí)間的使用成本.

2 算法描述

NSGA-III[10]是Deb和Jain 在2014年提出來(lái)的用于處理多個(gè)優(yōu)化目標(biāo)的進(jìn)化優(yōu)化算法.其主要思路是在NSGA-II的基礎(chǔ)上引入了參考點(diǎn)機(jī)制,對(duì)于那些非支配并且接近參考點(diǎn)的種群個(gè)體進(jìn)行保留,相比NSGAII 擁有優(yōu)秀的處理更高維度目標(biāo)的能力.

2.1 NSGA-III 基本算法流程

本文以NSGA-III的算法基本框架,全局搜索以遺傳算法為基礎(chǔ),使用了一種符合調(diào)度問(wèn)題特點(diǎn)的交叉變異策略,并提出了兩種更改支配關(guān)系的改進(jìn)措施.改進(jìn)后的NSGA-III 將具有更好的處理高維數(shù)據(jù)的能力,用于解決本文所提出的機(jī)器人制造單元的高維多目標(biāo)調(diào)度問(wèn)題.NSGA-III的算法流程如下.

Step 1.初始化,隨機(jī)產(chǎn)生大小為N的父代種群Pt.更新操作,父代通過(guò)交叉、變異產(chǎn)生大小為N的子代種群Qt,合并為大小為2N的種群Rt=Pt+Qt.

Step 2.計(jì)算目標(biāo)值,通過(guò)非支配排序,將Rt劃分為不同的非支配層(F1,F2,···).

Step 3.選擇優(yōu)先級(jí)高的非支配子集保留到下一代,用S t來(lái)保留.設(shè)Fl為臨界層,臨界層為加上該層解數(shù)目大于等于N時(shí)的非支配層.若數(shù)目等于N則S t=S t∪Fi,i=1,2,···,l,否則S t=S t∪Fi,i=1,2,···,l?1. 令Pt+1=S t.用K=N?|Pt+1|來(lái) 記錄需要從Fl中補(bǔ)充的解的個(gè)數(shù).

Step 4.每一維度最大值作為極值點(diǎn),最小值作為理想點(diǎn),對(duì)每個(gè)解的目標(biāo)值做歸一化處理.

Step 5.以極值點(diǎn)構(gòu)造超平面,產(chǎn)生均布的C(M+H?1,H)個(gè)參考點(diǎn),M為維度數(shù),H為每維分割份數(shù).

Step 6.對(duì)S t中和Fl層中每個(gè)解找出距離最近的參考點(diǎn)分別進(jìn)行關(guān)聯(lián).

Step 7.對(duì)于S t中關(guān)聯(lián)少的參考點(diǎn),找出Fl層對(duì)應(yīng)參考點(diǎn)關(guān)聯(lián)的一個(gè)最近的解進(jìn)行補(bǔ)充.每添加一個(gè)解,就將該解從Fl中刪除,并將S t中關(guān)聯(lián)解的個(gè)數(shù)更新排序.重復(fù)Step 7 直至補(bǔ)充K個(gè)解.

Step 8.返回Step 2,直至迭代次數(shù)達(dá)到預(yù)設(shè)值,對(duì)當(dāng)前解集進(jìn)行非支配排序找出第一非支配層的解作為最終解集.

2.2 改進(jìn)的NSGA-III

隨著目標(biāo)數(shù)量的增加,算法對(duì)解的選擇壓力變小,基于Pareto 支配,解之間很難存在支配關(guān)系,這導(dǎo)致解集中很大部分的解都是非支配的.而算法本身就強(qiáng)調(diào)保留種群中的非支配解,所以在每一代種群中,就沒(méi)有太多的空間來(lái)保留新解.這樣就減緩了算法的搜索過(guò)程,使算法效率變得低下.使用改變支配關(guān)系的方法,將解的目標(biāo)值進(jìn)行調(diào)整,可以擴(kuò)大每個(gè)解的支配空間,從而提高解之間的區(qū)分度.本文分別將Lorenz 支配和CDAS 支配與NSGA-III 結(jié)合來(lái)進(jìn)行優(yōu)化.第2.2.1 節(jié)和第2.2.2 節(jié)分別介紹了 Lorenz 支配和CDAS 支配.

2.2.1 Lorenz 支配

Lorenz 支配(式(6))是將標(biāo)準(zhǔn)化后的每一個(gè)解的目標(biāo)值,按照從小到大進(jìn)行排列,之后在一個(gè)新列表里,第i個(gè)位置存放前i個(gè)目標(biāo)值的和(i=1,2,···,m),m為維度數(shù).所有解的目標(biāo)值f(x)都用Lorenz 修改過(guò)后,用此新的目標(biāo)值f′(x)來(lái)進(jìn)行非支配排序,修改過(guò)支配關(guān)系后,每個(gè)解的支配空間將會(huì)變大,每個(gè)解之間就有更好的區(qū)分度.

如圖2所示是一個(gè)雙目標(biāo)的例子,對(duì)于解S,基于Pareto 支配區(qū)域?yàn)?a),經(jīng)Lorenz 支配S的支配空間增加到(a)、(b)、(c).圖2中,X是一個(gè)解序列所求出對(duì)應(yīng)的目標(biāo)值的坐標(biāo).

圖2 Lorenz 支配關(guān)系

2.2.2 CDAS 支配

CDAS 支配(式(7))如圖3所示,式中,r為該解的目標(biāo)值點(diǎn)與原點(diǎn)之間的距離;ωi為該點(diǎn)與原點(diǎn)連線和第i維的夾角;φi為該點(diǎn)與第i維上一個(gè)可控的夾角,其大小由系數(shù)S控制.當(dāng)S=0.5時(shí),CDAS 支配與Pareto支配效果相同;當(dāng)S<0.5時(shí),CDAS 支配將使原目標(biāo)值點(diǎn)的支配區(qū)域擴(kuò)大;當(dāng)S>0.5時(shí),CDAS 支配將使原目標(biāo)值點(diǎn)的支配區(qū)域變小.圖3中,X是一個(gè)解序列所求出對(duì)應(yīng)的目標(biāo)值的坐標(biāo).

圖3 解x 修改前后第i 維目標(biāo)值

通過(guò)試驗(yàn)發(fā)現(xiàn),當(dāng)S取0.25 時(shí),求解多目標(biāo)優(yōu)化問(wèn)題的效果最佳.此時(shí)根據(jù)CDAS 支配將原目標(biāo)值f(x)修改為f′(x),擴(kuò)大該解的支配區(qū)域.

以雙目標(biāo)優(yōu)化問(wèn)題為例,如圖4所示,當(dāng)S=0.5,即Pareto 支配關(guān)系下解A、B、C 是互不支配的.取S=0.25,增大擴(kuò)張角,從圖中虛線部分可以看到每個(gè)解的支配區(qū)域都有所擴(kuò)大,解之間出現(xiàn)了更細(xì)微的序值分布,此時(shí),3 個(gè)解從互不支配變?yōu)榻釨 支配解C.

圖4 CDAS 修改后解支配關(guān)系

3 實(shí)驗(yàn)分析

為了驗(yàn)證本文提出的改進(jìn)算法的有效性,通過(guò)對(duì)本文算法與傳統(tǒng)的NSGA-Ⅲ算法進(jìn)行對(duì)比.并從以下3 個(gè)方面來(lái)測(cè)試算法性能.

1)收斂性:反映解集與真實(shí)Pareto 前沿趨近程度.

2)多樣性:反映是否所得的Pareto 最優(yōu)解集中的解都分布在 Pareto 前沿上.

3)均勻性:反映所得的Pareto 最優(yōu)解集中的解在目標(biāo)空間中分布的均勻程度.

本次實(shí)驗(yàn)采用世代距離GD (generational distance)、反向世代距離IGD (inverted generational distance)和間距Spacing 作為評(píng)價(jià)算法性能的指標(biāo).其中,GD 用于評(píng)價(jià)解集收斂性,IGD 用于評(píng)價(jià)解集收斂性和多樣性的綜合性能,Spacing 評(píng)價(jià)解集均勻程度.

本文提出的改進(jìn)優(yōu)化算法以 PyCharm Python 3.8為開發(fā)工具編程實(shí)現(xiàn),其中相關(guān)參數(shù)設(shè)置如下:實(shí)驗(yàn)設(shè)計(jì)環(huán)境和配置為Intel(R)Core(TM) i5-7300HQ CPU@2.50、8.00 GB RAM、Windows 10 64 位操作系統(tǒng).交叉概率設(shè)為1.0,變異概率設(shè)為0.5,迭代次數(shù)設(shè)為50,種群大小設(shè)為40.表1中,Ind表示案例編號(hào),J表示該案例工件個(gè)數(shù),M表示加工機(jī)器臺(tái)數(shù),S表示加工工序總數(shù),上標(biāo)1為C-NSGA-III 算法測(cè)試結(jié)果,上標(biāo)2為L(zhǎng)-NSGA-III 算法測(cè)試結(jié)果,上標(biāo)3為NSGA-III 算法測(cè)試結(jié)果,下標(biāo)AVG為均值,SD為標(biāo)準(zhǔn)差,MIN為最小值.本文挑選了由小到中到大型的案例共10 個(gè)進(jìn)行了實(shí)驗(yàn),用來(lái)測(cè)試本文所提出的算法的性能,各案例均按照一定規(guī)則隨機(jī)生成.每個(gè)案例運(yùn)行10 次,取均值作為測(cè)試結(jié)果.

為了更好的描述最優(yōu)方案的調(diào)度過(guò)程,可以通過(guò)甘特圖來(lái)分析工件的加工順序與機(jī)器人的搬運(yùn)順序,如圖5為案例CS-3-16-5的甘特圖.該案例包含3 個(gè)工件,5 臺(tái)加工機(jī)器,16 道工序.圖中,橫坐標(biāo)為時(shí)間軸,縱坐標(biāo)為加工機(jī)器序號(hào),M0為裝載卸載站.純色矩形代表加工過(guò)程,虛線矩形代表工件在當(dāng)前機(jī)器上的等待時(shí)間,實(shí)線代表機(jī)器人帶載過(guò)程,虛線代表空載過(guò)程.“J00”代表工件0的第0 道工序,之后以此類推.則案例CS-3-16-5的加工過(guò)程可描述為:機(jī)器人將工件2 從M0 搬出至M3 進(jìn)行工序J20的加工,搬運(yùn)后機(jī)器人返回至M0 開始搬運(yùn)工件0 至M1 進(jìn)行工序J00的加工,隨后返回M0 搬運(yùn)工件1 至M5 加工工序J10.隨后機(jī)器人轉(zhuǎn)至M3 取走在M3 上完成加工的且已在輸出緩沖區(qū)上等待的工件2,搬運(yùn)至M2 加工工序J21.以此類推,直到所有工件加工結(jié)束.

圖5 案例CS-3-16-5 甘特圖

表1、表2、表3分別為C-NSGA-III、L-NSGAIII和NSGA-III 算法在GD、IGD、Spacing 上的對(duì)比結(jié)果.通過(guò)對(duì)比可以得出,C-NSGA-III和L-NSGAIII 都在GD 上表現(xiàn)良好,在絕大部分案例上數(shù)值都小于NSGA-III,且標(biāo)準(zhǔn)差不大,說(shuō)明改進(jìn)算法較為穩(wěn)定.在GD 最小值上,C-NSGA-III 始終為0,總體可得兩種改進(jìn)算法在收斂性上都要優(yōu)于NSGA-III.但在IGD 值上,NSGA-III 幾乎始終占優(yōu),說(shuō)明C-NSGA-III和LNSGA-III 在多樣性上會(huì)變差,分析原因是兩算法均加大了支配空間,它們的解相當(dāng)于Pareto 關(guān)系下的解的子集,所以解的多樣性會(huì)變差.比較Spacing 值可知,兩改進(jìn)算法在解集均勻程度上,較優(yōu)于NSGA-III.總體來(lái)說(shuō),C-NSGA-III和L-NSGA-III 算法有效地提升了解集的收斂性和均勻性,在多樣性上表現(xiàn)一般.

表1 C-NSGA-III、L-NSGA-III 與NSGA-III 算法GD 指標(biāo)對(duì)比表

表2 C-NSGA-III、L-NSGA-III 與NSGA-III 算法IGD 指標(biāo)對(duì)比表

表3 C-NSGA-III、L-NSGA-III 與NSGA-III 算法Spacing 指標(biāo)對(duì)比表

4 結(jié)論與展望

本文針對(duì)研究機(jī)器人制造單元的多目標(biāo)協(xié)同調(diào)度問(wèn)題,同時(shí)優(yōu)化5 個(gè)目標(biāo):最大完工時(shí)間,加工總能耗,交貨期提前量,交貨期延遲量及生產(chǎn)總成本.針對(duì)job-shop的特點(diǎn),分別將Lorenz 支配和CDAS 支配與NSGAIII 結(jié)合來(lái)進(jìn)行優(yōu)化并將結(jié)果與NSGA-III 進(jìn)行比較,證明該算法有效.