全燕鳴 何一明

(華南理工大學(xué) 機(jī)械與汽車工程學(xué)院，廣東 廣州 510640)

近年來,隨著“中國制造2025”的不斷深入開展,智能制造行業(yè)和機(jī)器人行業(yè)獲得了快速發(fā)展,有關(guān)機(jī)器人的企業(yè)如雨后春筍般涌現(xiàn)。機(jī)器人由于可以代替人做一些重復(fù)而繁瑣的任務(wù),具有工作效率高及工作成本小的優(yōu)點(diǎn),正廣泛用于各行各業(yè),且需求量不斷增大[1]。多機(jī)器人任務(wù)分配調(diào)度方法是多機(jī)器人穩(wěn)定運(yùn)行的關(guān)鍵技術(shù),通過改進(jìn)多機(jī)器人任務(wù)分配調(diào)度方法有利于節(jié)省機(jī)器人的工作成本,延長(zhǎng)機(jī)器人的工作壽命,提高機(jī)器人的工作效率,且易于多機(jī)器人的進(jìn)一步推廣應(yīng)用[2]。

多機(jī)器人任務(wù)分配調(diào)度研究是大勢(shì)所趨,國內(nèi)外學(xué)者已經(jīng)對(duì)此展開了較多研究,但很多研究都偏向某個(gè)方面,難以做到全局統(tǒng)籌。Trigui等[3]提出了分布式市場(chǎng)化算法來解決多機(jī)器人任務(wù)分配問題,通過交換任務(wù)的方法進(jìn)行分配優(yōu)化,但其為局部調(diào)度,缺少考慮全局規(guī)劃的最優(yōu)性;David等[4]提出一種基于貝葉斯學(xué)習(xí)的多機(jī)器人協(xié)同方法,增強(qiáng)了多機(jī)器人局部的自適應(yīng)能力,但其偏向局部條件的應(yīng)對(duì),欠缺全局優(yōu)化效果;夏田等[5]建立了路徑調(diào)節(jié)的模型,并用蟻群算法去解決多AGV(一種移動(dòng)機(jī)器人)調(diào)度作業(yè)全局優(yōu)化問題,但蟻群算法相對(duì)其它算法來說計(jì)算速度慢、效率偏低且搜索過程容易出現(xiàn)“早熟”,欠缺穩(wěn)定性;徐海軍等[6]提出了一種改進(jìn)的A*算法來解決多AGV的沖突及調(diào)度問題,但A*算法計(jì)算量大,且局限于小規(guī)模計(jì)算,隨著任務(wù)數(shù)量的增加,此算法難以滿足全局調(diào)度的需求;Kala等[7]先用遺傳算法尋找最優(yōu)單路徑,再用進(jìn)化算法將最優(yōu)多路徑進(jìn)行整體優(yōu)化，從而實(shí)現(xiàn)多機(jī)器人的整體最優(yōu)調(diào)度;Tuncer等[8]提出一種改進(jìn)的遺傳算法,通過引進(jìn)新的變異算子,解決了動(dòng)態(tài)環(huán)境下多機(jī)器人調(diào)度的全局優(yōu)化問題;孟沖等[9]將多種群遺傳算法引入到兩階段路徑規(guī)劃策略,實(shí)現(xiàn)了多AGV全局路徑規(guī)劃的效果，他們?cè)跈C(jī)器人全局規(guī)劃方面做出了創(chuàng)新,但是也存在對(duì)單機(jī)器人的利用率方面考慮不足等問題。

針對(duì)多機(jī)器人多任務(wù)分配及調(diào)度優(yōu)化問題,本文提出一種應(yīng)用于多機(jī)器人任務(wù)分配調(diào)度的克隆選擇算法。此算法在一定條件下,建立多機(jī)器人、多工件及多工位并行作業(yè)的數(shù)學(xué)模型,分析約束條件和目標(biāo)函數(shù),使用克隆選擇算法進(jìn)行迭代計(jì)算,直到結(jié)果符合算法終止條件,最后輸出最優(yōu)調(diào)度結(jié)果,從而實(shí)現(xiàn)同一時(shí)間段內(nèi)多機(jī)器人完成多任務(wù)分配調(diào)度。文中還通過實(shí)驗(yàn),對(duì)比分析克隆選擇算法及遺傳算法在相同條件下對(duì)各項(xiàng)計(jì)算指標(biāo)(算法收斂時(shí)間、系統(tǒng)持續(xù)時(shí)間、單機(jī)器人最大消耗、多機(jī)器人總消耗)的優(yōu)化程度,從而驗(yàn)證克隆選擇算法的優(yōu)勢(shì)。

1 問題描述

在智能制造系統(tǒng)中,工位并行協(xié)同加工工件,并按照不同加工流程完成多種不同工件的加工。工件的生產(chǎn)需要多工序,并通過多工位配合完成，而機(jī)器人則通過調(diào)度和運(yùn)輸功能使多工件和多工位建立聯(lián)系。多工位、多工件和多機(jī)器人組成智能制造系統(tǒng)的重要部分[10]。本文研究是基于智能制造系統(tǒng)中多機(jī)器人的任務(wù)分配及調(diào)度優(yōu)化問題，智能制造系統(tǒng)(下文簡(jiǎn)稱為系統(tǒng))示意圖如圖1所示。

圖1 智能制造系統(tǒng)示意圖

系統(tǒng)中,主要研究對(duì)象的設(shè)定如表1所示。

表1 研究對(duì)象設(shè)定Table 1 Research object setting

當(dāng)系統(tǒng)下達(dá)一組任務(wù)時(shí),R1先從H1將毛坯運(yùn)輸?shù)組1進(jìn)行J11,運(yùn)輸需要消耗10 s,運(yùn)輸完成后,R1解除占用狀態(tài),然后等待其他調(diào)度任務(wù),如果沒有其他調(diào)度任務(wù)，R1在M1等待J11完成，J11需要消耗30 s,然后R1將W1從M1運(yùn)輸?shù)組2，運(yùn)輸需要消耗25 s,工件在M2完成J12，J12需要消耗35 s，此時(shí)W1加工完畢,整個(gè)過程消耗100 s。在此實(shí)例中,系統(tǒng)的甘特圖如圖2所示。

圖2 實(shí)例中的甘特圖

通過甘特圖可以很直觀看出各工位和各機(jī)器人在連續(xù)時(shí)間下的工作狀態(tài)[11]。

在多任務(wù)條件下,多機(jī)器人運(yùn)輸多工件且按照各工件加工順序完成加工的任務(wù)分配調(diào)度優(yōu)化問題,這是本文的研究基礎(chǔ)。

2 數(shù)學(xué)模型的建立

2.1 初始條件

給定機(jī)器人集合為

R={R1,R2,…，Rn1}

(1)

給定工位集合為

M={M1,M2,…，Mn2}

(2)

給定工件集合為

W={W1,W2,…，Wn3}

(3)

所有目標(biāo)任務(wù)集合為

T={T1,T2,…，Tn4}

(4)

代價(jià)矩陣為

C=[cij]

(5)

式中,矩陣C中的元素cij表示機(jī)器人R從目標(biāo)i運(yùn)動(dòng)到目標(biāo)點(diǎn)j(i,j=1,2,…，m)的消耗值[12]。

2.2 約束條件

(Ⅰ)工位約束:工件W的相應(yīng)工序J由指定的工位M加工,工位M在同一時(shí)刻不能同時(shí)進(jìn)行多工序J的加工。

(Ⅱ)時(shí)間約束:工件的前一工序Ji1加工完成才能進(jìn)行后一工序Ji2,設(shè)此任務(wù)過程中的時(shí)間點(diǎn)為tA,工序J完成的時(shí)間點(diǎn)為tA(J),即

tA(Jia)

(6)

工位要完成前一加工任務(wù)T1才能進(jìn)行后一加工任務(wù)T2,即

{?tA=a

?Mi∈M

count(TMi)≤1

(7)

式中,count(·)為統(tǒng)計(jì)個(gè)數(shù)函數(shù)。

工件Wi在工位M的工序Jij完成前,不允許被機(jī)器人R運(yùn)輸,即

{?tA

?Ri∈R

count(TRi)=0

(8)

(Ⅲ)任務(wù)約束:完成所有任務(wù)T,相同的任務(wù)T不能重復(fù)執(zhí)行,即

(9)

(?i,j∈{1,2,…，m},i≠j)

∪Ri∈RTRi=T

(10)

Ti∩Tj=?, ?i≠j∈R

(11)

2.3 目標(biāo)函數(shù)

(Ⅰ)設(shè)各工位作業(yè)時(shí)間為t(x),系統(tǒng)持續(xù)時(shí)間由最大工位作業(yè)時(shí)間決定。使系統(tǒng)持續(xù)時(shí)間最小,則目標(biāo)函數(shù)為

min ɡ1=min[maxt(x)]

(12)

(Ⅱ)計(jì)算各機(jī)器人R執(zhí)行運(yùn)輸任務(wù)的消耗,使得單機(jī)器人最大消耗最小,則目標(biāo)函數(shù)為

min ɡ2=min{max[f(R1,TR1),…，f(Rn,TRn)]}

(13)

(14)

式中,chk是機(jī)器人Ri沿規(guī)劃好的路徑從目標(biāo)h移動(dòng)到目標(biāo)k的消耗值,消耗值與運(yùn)輸時(shí)間正相關(guān),可以用運(yùn)輸時(shí)間代表。

(Ⅲ)設(shè)總消耗值為cost(x),使所有機(jī)器人R的總消耗最少,則目標(biāo)函數(shù)為

(15)

考慮上述3個(gè)優(yōu)化因素,總的目標(biāo)函數(shù)為

min ɡ=min(C1ɡ1+C2ɡ2+C3ɡ3)

(16)

式中,C1、C2、C3均為權(quán)重系數(shù),反映ɡ1、ɡ2、ɡ3的相對(duì)重要性。

3 克隆選擇算法的任務(wù)分配調(diào)度方法

3.1 克隆選擇算法的總體流程

克隆選擇算法受生物系統(tǒng)克隆選擇原理啟發(fā)而誕生,其計(jì)算思想是通過對(duì)候選解產(chǎn)生克隆、變異等操作,產(chǎn)生一個(gè)候選解的領(lǐng)域解,通過擴(kuò)大搜索范圍強(qiáng)化局部搜索,通過領(lǐng)域解和候選解的競(jìng)爭(zhēng)進(jìn)行選擇以提高算法快速全局搜索能力[13]。其計(jì)算流程如圖3所示。

圖3 克隆選擇算法的計(jì)算流程

3.2 初始化種群

設(shè)定當(dāng)前種群代數(shù)k=0,隨機(jī)產(chǎn)生一個(gè)規(guī)模N=n的初始染色體種群P(0)={p1,p2,…，pn},采用整數(shù)編碼方法進(jìn)行染色體編碼[14]。

染色體由u個(gè)基因(下文用英文G表示)組成,每個(gè)基因長(zhǎng)度為v，則染色體長(zhǎng)度為

L=uv

(17)

一個(gè)染色體代表一個(gè)調(diào)度方案。基因按從左到右的執(zhí)行順序排列,本文每個(gè)基因從左到右由3部分編碼組成,分別為工件類型、工序編號(hào)及機(jī)器人編號(hào);染色體長(zhǎng)度等于任務(wù)總數(shù)。一種基因編碼例子如表2所示,此為9工序、4工位、1機(jī)器人(編號(hào)為z)的基因編碼。

表2 基因編碼例子Table 2 Example of gene coding

表2中,G11z表示Rz把毛坯運(yùn)輸?shù)組1進(jìn)行J11；G12z表示Rz到M1運(yùn)輸完成J11的W1，到M2進(jìn)行G12;其他基因G的意義以此類推。當(dāng)以上8個(gè)任務(wù)均完成時(shí),意味著3種工件全部加工完畢,系統(tǒng)任務(wù)完成。

由于在染色體中,基因按執(zhí)行順序排列,基因順序代表著執(zhí)行順序,所以工序編號(hào)可以由程序進(jìn)行解析,而不需要在基因中標(biāo)出。例如染色體中第1次出現(xiàn)的G1X代表RX運(yùn)輸W1去進(jìn)行J11，第2次出現(xiàn)的G1Y代表RY運(yùn)輸W1去進(jìn)行J12。圖4是一個(gè)基于上述條件的染色體編碼例子。

圖4 染色體編碼例子

3.3計(jì)算親和度

親和度源于免疫系統(tǒng)中抗原與抗體的親和力概念,表示抗體對(duì)抗原的匹配程度。克隆選擇算法中,親和度是指?jìng)€(gè)體相對(duì)于結(jié)果的期望值。親和度越高,個(gè)體越優(yōu)秀。文中算法致力于提高個(gè)體親和度[15]。計(jì)算親和度前,要對(duì)染色體進(jìn)行解析,以計(jì)算系統(tǒng)持續(xù)時(shí)間ɡ1、單機(jī)器人最大消耗g2及多機(jī)器人總消耗ɡ3。

考慮數(shù)學(xué)模型的目標(biāo)函數(shù),親和度計(jì)算公式為

f(x)=B-ɡ=B-C1ɡ1-C2ɡ2-C3ɡ3

(18)

式中,參數(shù)B為親和度總值,取用一個(gè)較大值的正整數(shù),目的是使得個(gè)體親和度值越高,個(gè)體品質(zhì)越好。

計(jì)算各個(gè)體親和度f(p1),f(p2),…，f(pn),將種群P(k)按親和度降序排列。為了防止“早熟”并提高算法的全局搜索能力,根據(jù)排列順序按比例2:5:3劃分種群P(i)為優(yōu)Pr(i)、中Ps(i)、差Pt(i)3個(gè)種群,即

P(i)={Pr(i),Ps(i),Pt(i)}

(19)

(r:s:t=2:5:3)

式中,參數(shù)r、s、t分別為3個(gè)種群中的個(gè)體數(shù)目。

計(jì)算個(gè)體間相似度S(0≤S≤1),用于表示兩個(gè)體px和py間的相似程度:

(20)

式中，axk為個(gè)體px的染色體編碼第k位數(shù)值。

采用個(gè)體濃度D反映種群多樣性,定義個(gè)體px的濃度為

(21)

式中,n為種群規(guī)模。式(21)表明,個(gè)體間相似度越小,則個(gè)體濃度D越小。個(gè)體濃度主要用于調(diào)整克隆規(guī)模,保持種群多樣性。

3.4 克隆

根據(jù)各個(gè)體親和度大小,計(jì)算其相應(yīng)克隆次數(shù),進(jìn)行克隆復(fù)制操作。

對(duì)P(i)中的個(gè)體pj(j=1,2,…，ni),按照個(gè)體克隆規(guī)模qj進(jìn)行復(fù)制:

(22)

式中,ni為第i代種群規(guī)模,ceil(·)為向上取整函數(shù),Nc為種群克隆規(guī)模。其中,

(23)

式中,pj(i)為第i代個(gè)體pj。

克隆產(chǎn)生子代種群Pc(i)。式(22)和(23)表明:克隆規(guī)模依賴于個(gè)體親和度和個(gè)體濃度,個(gè)體親和度越大,個(gè)體克隆規(guī)模越大;個(gè)體濃度越大,個(gè)體克隆規(guī)模越小。

3.5 變異

對(duì)克隆個(gè)體采取變異操作。按式(24)分配克隆個(gè)體pj(j=1,2,…，ni)的變異概率:

(24)

式(24)表明,變異概率取決于個(gè)體親和度大小,個(gè)體親和度越大,個(gè)體變異概率越小。

變異包含突變和交換兩個(gè)過程。突變過程是對(duì)個(gè)體中基因的第2位進(jìn)行變更,變更后整數(shù)編碼要限定在合理范圍內(nèi),如圖5所示。

圖5 基因突變過程

交換過程是對(duì)個(gè)體中任意兩個(gè)基因進(jìn)行交換,如圖6所示。

圖6 基因交換過程

子代優(yōu)秀種群Pcr(i)和子代中等種群Pcs(i)通過變異分別轉(zhuǎn)化為種群P′cr(i)和P′cs(i)。

3.6 選擇

選擇是算法的重要搜索過程,目的在于篩選出優(yōu)秀個(gè)體,從而產(chǎn)生新種群[16]。

Pdr(i+1)={P′cr(i),Pr(i)}

(25)

根據(jù)式(25),從種群Pdr(i+1)中選出親和度最高的r個(gè)個(gè)體組成P′dr(i+1)。

Pds(i+1)={P′cs(i),Ps(i)}

(26)

根據(jù)式(26),從種群Pds(i+1)中選出親和度最高的s個(gè)個(gè)體組成P′ds(i+1)。

為了防止“早熟”,再次隨機(jī)生成規(guī)模大小為n的種群Pdt(i+1),取其中親和度最高的t個(gè)個(gè)體組成P′dt(i+1)。

新一代種群產(chǎn)生,此種群集合為

P(i+1)={P′dr(i+1),P′ds(i+1),P′dt(i+1)}

(27)

3.7 終止條件

本文算法不預(yù)設(shè)固定期望值和最大迭代次數(shù),而是通過判斷連續(xù)多個(gè)子代最大親和度值是否相等作為算法收斂判斷依據(jù),當(dāng)連續(xù)20代子代最大親和度值和父代最大親和度值相等時(shí),算法收斂,即符合算法終止條件。

當(dāng)新一代種群產(chǎn)生時(shí),需要判斷是否符合算法終止條件。若符合算法終止條件,則算法停止,選擇親和度最高的個(gè)體作為結(jié)果輸出;否則,轉(zhuǎn)到圖3 的選擇步驟,繼續(xù)進(jìn)行迭代循環(huán)運(yùn)算[17]。

4 實(shí)驗(yàn)與分析

構(gòu)建仿真場(chǎng)景模型,考慮條件:機(jī)器人數(shù)量count(R)=3，任務(wù)數(shù)量count(T)=45。零件加工時(shí)間如表3所示，為了避免不同含義的基因編碼混淆,大于1位的整數(shù)編碼用逗號(hào)隔開。

機(jī)器人從各工位起點(diǎn)將工件運(yùn)輸?shù)礁鞴の唤K點(diǎn)消耗的時(shí)間如表4所示。

計(jì)算前要初始化算法參數(shù):設(shè)置種群規(guī)模N=80,種群克隆規(guī)模Nc=80,親和度總值B=500,權(quán)重系數(shù)C1=0.80,C2=0.10,C3=0.10。在Matlab 2016a環(huán)境下進(jìn)行克隆選擇算法程序編程,在配置為Intel Core i5處理器、8 GB RAM內(nèi)存的計(jì)算機(jī)上運(yùn)行,通過232次迭代計(jì)算,算法收斂,輸出結(jié)果為G411,G711,G911,G11,11,G10,11,G12,12,G212,G312,G512,G113,G613,G813,G13,13,G14,13,G15,13,G321,G521,G14,21,G10,21,G15,21,G622,G122,G922,G11,22,G723,G423,G823,G13,23,G12,23,G223,G631,G431,G831,G15,31,G10,31,G732,G332,G13,32,G12,32,G232,G133,G533,G933,G14,33,G11,33。

表3 零件加工時(shí)間Table 3 Workpiece processing time

表4 機(jī)器人運(yùn)輸消耗的時(shí)間Table 4 Time spent in robot transportation s

根據(jù)上述結(jié)果,畫出此系統(tǒng)的甘特圖,如圖7所示。

圖7 系統(tǒng)的甘特圖

由圖7可得,最后完成加工的工位是M6,系統(tǒng)持續(xù)時(shí)間ɡ1(x)=635 s,運(yùn)輸時(shí)間最長(zhǎng)的機(jī)器人是R2,單機(jī)器人最大消耗ɡ2(x)=523 s,多機(jī)器人總消耗ɡ3(x)=1 519 s。實(shí)驗(yàn)表明,此多機(jī)器人任務(wù)分配調(diào)度方法合理,達(dá)到了任務(wù)分配調(diào)度優(yōu)化目的。

單條件下單次實(shí)驗(yàn)偶然性大,因此,在考慮不同實(shí)驗(yàn)條件的基礎(chǔ)上,分別用克隆選擇算法(下文簡(jiǎn)稱CSA)和遺傳算法(下文簡(jiǎn)稱GA)進(jìn)行求解,以對(duì)CSA和GA進(jìn)行對(duì)比。

使用GA求解此問題時(shí),為了提高可比性,GA的初始參數(shù)需要和CSA的初始參數(shù)保持一致,GA的選擇、交叉、變異概率使用CSA返回的初代概率?？傻肅SA的初代參數(shù)值為:種群規(guī)模N=n1,選擇概率a=a1,交叉概率b=b1,變異概率c=c1。則設(shè)置GA參數(shù)為:種群規(guī)模N′=n1,選擇概率a′=a1,交叉概率b′=b1,變異概率c′=c1,進(jìn)行Matlab編程。

對(duì)每個(gè)不同條件分別進(jìn)行10次獨(dú)立重復(fù)的Matlab仿真實(shí)驗(yàn),獲取最終輸出結(jié)果,并計(jì)算其各項(xiàng)指標(biāo)平均值。將CSA和GA各項(xiàng)平均值指標(biāo)對(duì)比,比較的指標(biāo)分為兩個(gè)方面:一是算法的計(jì)算性能,包括迭代次數(shù)和收斂時(shí)間,即達(dá)到穩(wěn)定的迭代時(shí)間;二是算法的優(yōu)化能力,包括系統(tǒng)持續(xù)時(shí)間、單機(jī)器人最大消耗和多機(jī)器人總消耗。比較結(jié)果如圖8和9所示。

圖8和9中,實(shí)驗(yàn)編號(hào)1到20是在相同機(jī)器人數(shù)量(count(R)=3)基礎(chǔ)上,對(duì)任務(wù)數(shù)量從12到69進(jìn)行逐漸增加來進(jìn)行實(shí)驗(yàn);實(shí)驗(yàn)編號(hào)21到30是在相同任務(wù)數(shù)量(count(T)=45)基礎(chǔ)上,對(duì)機(jī)器人數(shù)量從1到10進(jìn)行逐漸增加來進(jìn)行實(shí)驗(yàn)的。

圖8 CSA和GA計(jì)算性能比較柱狀圖

圖9 CSA和GA優(yōu)化能力比較柱狀圖

由圖8可知,CSA在迭代次數(shù)和收斂時(shí)間方面的表現(xiàn)均優(yōu)于GA。CSA明顯減少了迭代次數(shù),雖然CSA增加了每代計(jì)算時(shí)間,但是CSA的平均收斂時(shí)間也比GA少,且隨著實(shí)驗(yàn)條件復(fù)雜化,CSA的收斂時(shí)間更有優(yōu)勢(shì)。由此可見,CSA的計(jì)算性能優(yōu)于GA。

由圖9可知,無論在相同機(jī)器人數(shù)量、不同任務(wù)數(shù)量下還是在相同任務(wù)數(shù)量、不同機(jī)器人數(shù)量下對(duì)各項(xiàng)優(yōu)化能力指標(biāo)(包括系統(tǒng)持續(xù)時(shí)間、單機(jī)器人最大消耗和多機(jī)器人總消耗)進(jìn)行比較,CSA的表現(xiàn)均優(yōu)于GA,即CSA的優(yōu)化能力強(qiáng)于GA?？梢钥闯?當(dāng)機(jī)器人數(shù)量相同時(shí),隨著任務(wù)數(shù)量增加,調(diào)度條件復(fù)雜化,相比于GA,尤其在單機(jī)器人最大消耗和多機(jī)器人總消耗方面,CSA的優(yōu)勢(shì)逐漸變大；當(dāng)任務(wù)數(shù)量相同時(shí),隨著機(jī)器人數(shù)量的增加,CSA和GA各項(xiàng)優(yōu)化能力指標(biāo)間的差異逐漸變??；當(dāng)機(jī)器人數(shù)量增加到一定程度并使其達(dá)到飽和狀態(tài)時(shí),即使繼續(xù)增加機(jī)器人數(shù)量,CSA和GA的系統(tǒng)持續(xù)時(shí)間、單機(jī)器人最大消耗和多機(jī)器人總消耗也不會(huì)下降。

使用GA時(shí),事先要設(shè)定好交叉、變異和選擇概率等參數(shù),采用適應(yīng)度評(píng)估的方法進(jìn)行優(yōu)秀子代的選擇[18]。為了改進(jìn)GA收斂速度偏慢的缺點(diǎn),CSA引入親和度函數(shù),目的在于動(dòng)態(tài)修改CSA的控制參數(shù),將原本在GA中保持固定的參數(shù)設(shè)置成隨著迭代變化,并利用親和度函數(shù)所提供的信息對(duì)克隆、變異及選擇操作方式進(jìn)行校準(zhǔn),從而引導(dǎo)算法向提高親和度的搜索方向進(jìn)行,進(jìn)而使種群朝著全局最優(yōu)的方向進(jìn)化,最終減少了冗余的搜索過程,所以能有效降低迭代次數(shù)并提高收斂速度。

此外,CSA在提高收斂速度的同時(shí)可能會(huì)產(chǎn)生收斂過快以及無法進(jìn)行足夠探索的問題。收斂過快的特征表現(xiàn)在:種群中個(gè)體間相似度高,種群多樣性急劇減少,缺乏有效等位基因,在決策算子作用下不能生成高階競(jìng)爭(zhēng)模式,即“早熟”[19]。此現(xiàn)象會(huì)使算法過早收斂于局部最優(yōu),而非全局最優(yōu)。尤其是處于迭代后期時(shí),經(jīng)過算法的多代篩選,優(yōu)秀個(gè)體已經(jīng)在種群中占據(jù)大部分,此時(shí),交叉操作對(duì)于相同優(yōu)秀個(gè)體幾乎不產(chǎn)生影響。雖然變異操作能夠?yàn)樗惴ㄑa(bǔ)充新個(gè)體,但是此操作對(duì)算法影響相對(duì)較小。如果增大算法的變異概率會(huì)破壞種群中的優(yōu)良個(gè)體,導(dǎo)致算法繼承能力及優(yōu)化能力降低。

防止“早熟”是搜索算法設(shè)計(jì)的重點(diǎn)。為了在提高收斂速度的同時(shí)防止“早熟”現(xiàn)象,本文通過增大種群規(guī)模和克隆規(guī)模,將種群分為優(yōu)、中、差3種類型分別進(jìn)行選擇操作,同時(shí)在選擇步驟中隨機(jī)引入新種群的方法以提高種群基因多樣性,從而在一定程度上防止“早熟”。實(shí)驗(yàn)結(jié)果表明,CSA表現(xiàn)優(yōu)良,并未出現(xiàn)明顯“早熟”現(xiàn)象。

5 結(jié)論

文中基于智能制造系統(tǒng)中多機(jī)器人任務(wù)分配調(diào)度問題,分析多機(jī)器人在智能制造系統(tǒng)中的調(diào)度條件,構(gòu)建合理的數(shù)學(xué)模型,并基于多機(jī)器人任務(wù)分配調(diào)度應(yīng)用CSA。在迭代過程中引入適當(dāng)?shù)挠H和度函數(shù),動(dòng)態(tài)改變克隆、變異、選擇參數(shù),從而加快算法的收斂速度;同時(shí)通過增大種群規(guī)模和克隆規(guī)模,進(jìn)行種群分類篩選和隨機(jī)引入新種群的方法防止“早熟”,使算法性能得到提高。最后，文中通過實(shí)驗(yàn)證明其可行性,分析CSA相對(duì)于GA的優(yōu)勢(shì)。相比于GA,CSA的計(jì)算性能和優(yōu)化能力具有優(yōu)勢(shì),對(duì)收斂時(shí)間、系統(tǒng)持續(xù)時(shí)間、單機(jī)器人最大消耗、多機(jī)器人總消耗等指標(biāo)優(yōu)化較好。隨著調(diào)度任務(wù)增加,調(diào)度條件復(fù)雜化,CSA相比于GA在計(jì)算性能和優(yōu)化能力方面優(yōu)勢(shì)更加明顯。當(dāng)任務(wù)數(shù)量相同時(shí),隨著機(jī)器人數(shù)量增加,CSA和GA各項(xiàng)優(yōu)化能力指標(biāo)間的差異逐漸變小。當(dāng)機(jī)器人數(shù)量增加到一定程度并使其達(dá)到飽和狀態(tài)時(shí),即使繼續(xù)增加機(jī)器人數(shù)量,CSA和GA的系統(tǒng)持續(xù)時(shí)間、單機(jī)器人最大消耗和多機(jī)器人總消耗也不會(huì)下降。

本文所用模型還存在如下不足:多機(jī)器人運(yùn)動(dòng)過程中路徑?jīng)_突和避碰問題并沒有在調(diào)度過程中加以考慮;在復(fù)雜調(diào)度情況下,本文在調(diào)度優(yōu)化過程中機(jī)器人出現(xiàn)故障時(shí)的容錯(cuò)處理沒有加以考慮。因此，在后續(xù)相關(guān)研究中會(huì)進(jìn)行這些問題的仔細(xì)探究。