唐秋華　胡　進(jìn)　張利平　操小軍

1.武漢科技大學(xué),武漢,430081　　2.神龍汽車公司技術(shù)中心,武漢,430056

面向汽車投產(chǎn)排序的混合多目標(biāo)網(wǎng)格遺傳算法

唐秋華1胡進(jìn)1張利平1操小軍2

1.武漢科技大學(xué),武漢,4300812.神龍汽車公司技術(shù)中心,武漢,430056

汽車投產(chǎn)排序時，希望同時實(shí)現(xiàn)零部件消耗均衡化、車型調(diào)整費(fèi)用最小化、工位作業(yè)位置精準(zhǔn)化三個目標(biāo)，為此提出一種基于Pareto層級的混合多目標(biāo)網(wǎng)格遺傳算法(HmoGA)。先將個體排斥機(jī)制加入到Pareto層級構(gòu)造中，使非支配解的分布更均勻,再融合Pareto層級劃分、網(wǎng)格擁擠度評價與相鄰個體幾何距離計算，設(shè)計一種多目標(biāo)自適應(yīng)網(wǎng)格選擇機(jī)制，用于從動態(tài)變化的父代種群中選擇較優(yōu)個體構(gòu)成進(jìn)化種群、獲取交叉運(yùn)算的父代基因、改善非支配解集的分布質(zhì)量。混合雙基因位的遷移算子對非支配解進(jìn)行鄰域搜索，適時擴(kuò)大搜索空間，跳出局部最優(yōu)。利用三組不同規(guī)模的測試問題集,從非支配率、非支配解數(shù)量和相鄰個體距離偏差三個指標(biāo)方面進(jìn)行比較,實(shí)驗(yàn)證明HmoGA算法在收斂性、解的數(shù)量和分布性方面都比NSGA-Ⅱ算法有顯著優(yōu)勢。

Pareto層級；網(wǎng)格擁擠度;自適應(yīng)選擇;個體排斥機(jī)制；鄰域搜索

0　引言

隨著市場競爭的激烈化和客戶需求的個性化,面向訂單的多品種、小批量生產(chǎn)已逐步成為汽車等行業(yè)的主要生產(chǎn)模式。在其混流生產(chǎn)線上,多種產(chǎn)品的投產(chǎn)排序已經(jīng)成為一個重要決策,它不僅影響到企業(yè)的效率和成本[1]，而且關(guān)系到產(chǎn)品交貨期和客戶滿意度，推動著投產(chǎn)排序問題本身的演變，促其發(fā)展成為一種多目標(biāo)優(yōu)化問題。

解決多目標(biāo)優(yōu)化問題,應(yīng)用最廣泛的是多目標(biāo)進(jìn)化算法，如多目標(biāo)遺傳算法(MOGA)、非支配排序遺傳算法(NSGA)等。MOGA利用遺傳算法的精英保留機(jī)制，對所求出的非支配解進(jìn)行繼承。NSGA基于Pareto層級進(jìn)行個體排序，選擇最低層級(非支配解)或較低層級的個體進(jìn)行遺傳操作。上述經(jīng)典算法中，普遍存在Pareto層級構(gòu)造速度過慢、種群多樣性差、搜索空間狹窄等問題。

為提高Pareto層級構(gòu)造速度,Deb等[2]提出了改進(jìn)型非支配排序遺傳算法(NSGA-Ⅱ)，劉敏等[3]提出一種快速非支配排序算法,鮑培明等[4]使用了歸一化排序非支配集構(gòu)造方法。上述構(gòu)造方法在一定程度上加快了Pareto排序,但仍缺乏非支配個體重復(fù)進(jìn)入歸檔集的阻止機(jī)制，相同個體共同存在的可能性仍然很大,這對保持種群多樣性不利，容易早熟。

種群多樣性可有效防止算法陷入局部最優(yōu)。為維護(hù)種群的多樣性,楊虎等[5]將聚集密度方法應(yīng)用到粒子群算法中，利用粒子群的強(qiáng)大搜索性能和科學(xué)的個體聚集度評價方式，使非支配解分布更加均勻。李志強(qiáng)等[6]將聚類方法加入到NSGA-Ⅱ中,彌補(bǔ)了三目標(biāo)及三目標(biāo)以上情形下非支配解分布性不足的缺陷。然而,上述算法對非支配解集和進(jìn)化種群沒有相應(yīng)的調(diào)整策略，當(dāng)所獲得的非支配解數(shù)量大于進(jìn)化種群規(guī)模時，無法科學(xué)地選擇進(jìn)入下一代的個體；當(dāng)非支配解數(shù)量大于一定規(guī)模時,適應(yīng)度評價所耗費(fèi)的計算時間長，且難以持續(xù)達(dá)到理想的分布性。

拓展搜索空間是搜尋更多的非支配解和跳出局部最優(yōu)的唯一途徑。目前，擴(kuò)大搜索空間的主要方法有變步長搜索、啟發(fā)式搜索等。戚玉濤等[7]融合了啟發(fā)式局部搜索策略和變步長搜索機(jī)制，在進(jìn)化過程中，根據(jù)適應(yīng)度隨時進(jìn)行步長調(diào)整,在保證全局優(yōu)化的同時提高了局部搜索能力。賈寧等[8]結(jié)合啟發(fā)式搜索和反饋修正機(jī)制增加了算法的搜索性能,使算法快速且有效地尋找較優(yōu)的個體，最終確立了最佳的單路口交通控制方案。但對于裝配線投產(chǎn)排序問題，變步長方式實(shí)現(xiàn)困難，而啟發(fā)式搜索的搜索范圍過小則可能缺乏效果，過大又造成優(yōu)化復(fù)雜度過高，影響進(jìn)化效率。

為克服上述算法存在的早熟、分布性不足、局部最優(yōu)的缺點(diǎn),本文在快速Pareto層級評價時加入相同個體排斥機(jī)制,利用相鄰個體幾何距離的大小來對非支配解進(jìn)行篩選，運(yùn)用2-opt鄰域搜索機(jī)制對歸檔集進(jìn)行鄰域搜索，區(qū)別出相同目標(biāo)值的非支配解,保持了非支配解的良好分布性，擴(kuò)大了解空間的搜索性能。針對汽車投產(chǎn)排序問題，將所提出的算法與NSGA-Ⅱ進(jìn)行了性能比較。

1　多目標(biāo)投產(chǎn)排序問題

1.1前提假設(shè)及約束條件

假定混合流水裝配線的運(yùn)行滿足以下前提條件:①傳送帶以恒定速度運(yùn)行,且每個產(chǎn)品以固定生產(chǎn)節(jié)拍TC送到傳送帶進(jìn)行生產(chǎn);②各工作站j左右兩側(cè)均是開放的,工作站內(nèi)工人允許超出工作站范圍作業(yè);③前一個工位的工人對一輛車操作完畢后,下一個工位的工人才能對這輛車進(jìn)行裝配;④以最小生產(chǎn)循環(huán)為單位，進(jìn)行循環(huán)式生產(chǎn);⑤最小循環(huán)單元內(nèi)第一輛車在第一個工位的釋放時間為0，則第一個工位的首個產(chǎn)品的裝配時間為0。

基于上述假定，多車型混合流水生產(chǎn)投產(chǎn)排序問題可以概括為：將K種總數(shù)為S的汽車投入到由J個串行工位構(gòu)成的生產(chǎn)線上，求最優(yōu)投產(chǎn)序列，以達(dá)到所要求的目標(biāo)。其約束條件如下：

(1)

(2)

(3)

式中,tkj為車型k在工位j上的總操作時間，j∈{1，2,…,J}。

式(1)保證了在生產(chǎn)序列上每個位置有且僅有一輛車;式(2)保證每種車型的投產(chǎn)數(shù)量滿足生產(chǎn)需求規(guī)定；式(3)保證在最小生產(chǎn)循環(huán)內(nèi),每個工位的有效工作時間小于總時間，不存在超負(fù)荷而無法完成的情況。

1.2多目標(biāo)函數(shù)

在汽車投產(chǎn)排序時，決策者希望最終方案既滿足市場需求，同時還能保持生產(chǎn)的穩(wěn)定性。多目標(biāo)優(yōu)化是解決上述問題的有效方法，當(dāng)前研究考慮以下三個目標(biāo)：零部件消耗均衡化，車型調(diào)整費(fèi)用最小化，工位作業(yè)位置精準(zhǔn)化。

1.2.1零部件消耗均衡化

隨著同時生產(chǎn)的車型數(shù)量增多，線邊零部件的類型和數(shù)量劇增。在生產(chǎn)過程中，若線邊零部件的消耗量發(fā)生變動，則必然增大線邊物料存儲壓力。同時，上游零部件供應(yīng)商、物料供應(yīng)超市、物料配送人員的工作狀態(tài)也忙閑不均。長此以往，必然造成生產(chǎn)現(xiàn)場的紊亂。為更好地利用有限的線邊存儲空間，在投產(chǎn)排序時，應(yīng)促使物料消耗均衡化。其目標(biāo)函數(shù)為

(4)

式(4)從生產(chǎn)過程出發(fā)，對投產(chǎn)序列中的每臺車，控制其對各零件的實(shí)際消耗量與理論消耗量之間的偏差，促使零部件供應(yīng)與消耗基本匹配,從而減小線邊庫存的壓力。

1.2.2車型調(diào)整費(fèi)用最小化

汽車制造從以往的單品種大批量生產(chǎn)已逐步發(fā)展成為多品種、小批量生產(chǎn)。不同產(chǎn)品類型間的切換，需要調(diào)整準(zhǔn)備時間，還會產(chǎn)生價格不低的調(diào)整成本。例如，在涂裝車間進(jìn)行不同顏色間切換時，需更換和沖洗油漆噴頭，造成噴漆效率降低、生產(chǎn)成本增高、環(huán)境污染加劇等后果。因此，控制產(chǎn)品類型的切換也成為投產(chǎn)排序時的一個重要目標(biāo)：

(5)

式中,Cjkk′為工位j上從車型k變換到k′的調(diào)整費(fèi)用。

1.2.3工位作業(yè)位置精準(zhǔn)化

各臺車按照固定生產(chǎn)節(jié)拍投放到生產(chǎn)線上，但在焊接、噴漆和裝配車間，各工位的左右兩邊是開放的，相鄰工位間無嚴(yán)格界限。因此，工人們可能會偏離自己工位，造成相鄰工位間的干擾。故在投產(chǎn)排序時，盡量讓各工位的工作位置精準(zhǔn)化，減少擁擠或阻塞，避免生產(chǎn)的紊亂。

為解決以上問題,最小化投產(chǎn)序列中各車輛在每工位的完工時間與生產(chǎn)節(jié)拍之間的最大偏差[9],目標(biāo)函數(shù)如下：

(6)

其中,fjs為j工位上第s輛車的裝配終止時間,其值等于裝配開始時間加上這輛車所需的裝配時間，即

(7)

式中，bjs為j工位上第s輛車的裝配開始時間。

在不同情形下利用如下公式計算bjs:

bjs=fj,s-1j=1,?s∈{2,3,…,S}

(8)

bjs=fj,s-1s=1,?j∈{2,3,…,J}

(9)

bjs=max(fj-1,s,fj,s-1)

?j∈{2,3,…,J},s∈{2,3,…,S}

(10)

式(8)表明在第一個工位中，后一輛車的裝配開始時間等于前一輛車的裝配結(jié)束時間;式(9)表明各個工位的第一個產(chǎn)品的開始時間等于前一個工位在這個產(chǎn)品上的結(jié)束時間；式(10)表明某工位工人將當(dāng)前車型操作完成之后，且前一個工位的工人對生產(chǎn)循環(huán)中的下一輛車操作完成之后，該工人才能對這輛車進(jìn)行裝配。

由式(6)可見,各工位的完工時間與生產(chǎn)節(jié)拍之間的最大偏差越小，各工位在有效工作位置內(nèi)完成給定任務(wù)的比例越高，相鄰工位間干擾的可能性就越小，操作也就越穩(wěn)定。

2　多目標(biāo)自適應(yīng)網(wǎng)格選擇機(jī)制

在最小生產(chǎn)循環(huán)單元內(nèi)，不同車型按照投產(chǎn)序列依次進(jìn)行生產(chǎn)，針對每個序列可得出上述三個目標(biāo)值。不同于單目標(biāo)優(yōu)化，多目標(biāo)問題不能單純依據(jù)某個目標(biāo)大小來評價該個體性能優(yōu)劣。在多目標(biāo)優(yōu)化算法中，往往采用Pareto層級排序來評價種群中不同個體的適應(yīng)度。當(dāng)個體的層級相同時，利用擁擠度來評價同層個體的適應(yīng)度。層級越低，擁擠度越小，個體則越優(yōu)，被選擇概率也會越大。

2.1Pareto層級構(gòu)造

考慮到Pareto層級構(gòu)造過程在處理大規(guī)模問題時的高計算復(fù)雜度,本文提出了一種非回溯的Pareto層級構(gòu)造方法，實(shí)時刪除Pareto層級構(gòu)造過程中產(chǎn)生的較差個體，大大加快了算法運(yùn)行效率。其構(gòu)造基本思想如下。

將父代種群納入構(gòu)造集中，從中選出一個比較個體(一般為種群中第一個個體)。用比較個體與歸檔集中其他個體進(jìn)行一一比較,若比較個體支配其他個體或與其他個體的目標(biāo)值相同，則將后者剔除。一輪比較過后，如果比較個體不被任何其他個體所支配，則比較個體即為非支配個體，將其納入非支配解集，否則比較個體在該輪比較結(jié)束時也被剔除。按照這種方法進(jìn)行下一輪比較，直至構(gòu)造集為空。

在經(jīng)過上述程序后，該構(gòu)造集的非支配解集構(gòu)造完成，其層數(shù)用1表示。隨后，刪除上一輪的所有非支配個體，形成新的構(gòu)造集。同理，在新的構(gòu)造集中，進(jìn)行下一層的非支配解集構(gòu)造,執(zhí)行上述搜索過程，直至完成所有個體的層級構(gòu)造。具體構(gòu)造過程如下：

定義Q為構(gòu)造集,Pop為比較集,q、q′是構(gòu)造集中任意個體,Q1為被q支配的個體集合,Q2是Q中支配q的個體集合,Q3為與q無關(guān)且目標(biāo)值不全相等的個體集合,Fi為第i層非支配解集。

(1)?q∈Q,令i=1,Pop=Q-q。

(2)令Q1=?,Q2=?,Q3=?,比較q和Pop中的每個個體q′的支配關(guān)系。若q支配q′,則令Q1←Q1+{q′}；若q′支配q,則令Q2←Q2+{q′};否則,若q、q′目標(biāo)值不同，則Q3←Q3+{q′}。

(3)若Q2=?，則Fi←Fi+{q}。

(4)Pop=Q2∪Q3,如果Pop中個體小于2個,則Fi←Fi+{Pop},轉(zhuǎn)步驟(5);否則,轉(zhuǎn)步驟(2)。

(5)Q←Q-Fi,Pop=Q,i←i+1。若Q=?,則停止。否則,轉(zhuǎn)步驟(2)。

2.2適應(yīng)網(wǎng)格劃分

圖1　雙目標(biāo)網(wǎng)格及邊界

若個體q落在網(wǎng)格外，如圖1中C點(diǎn),則它肯定不是非支配解，將其擁擠度賦值為

(11)

式中,iq表示個體q的層級;yq′為個體q′的擁擠度,q,q′∈{1,2,…,n};n為個體總數(shù);cr為保留因子，考慮到網(wǎng)格外個體的多樣性,取cr=0.8,則圖1中C點(diǎn)的擁擠度為4。

網(wǎng)格劃分的精度選擇是算法設(shè)計時需考慮的問題。網(wǎng)格劃分次數(shù)越多，群體分布精度越高，但必然耗費(fèi)更多的計算時間。而過多的劃分次數(shù)會使得所有個體的擁擠度為1，導(dǎo)致個體擁擠度的評價失效。借鑒文獻(xiàn)[11]中的網(wǎng)格數(shù)確定思想，取網(wǎng)格劃分次數(shù)為

(12)

其中,M為目標(biāo)個數(shù),n為種群中個體數(shù)目。式(12)表示網(wǎng)格劃分次數(shù)取值為種群大小開目標(biāo)個數(shù)次方并進(jìn)行向上取整。

必須注意的是，在進(jìn)化過程中，Pareto前沿在不斷變化，網(wǎng)格邊界也因此適應(yīng)性地調(diào)整。新生個體的擁擠度需利用調(diào)整后的網(wǎng)格來確定。

2.3調(diào)整策略

考慮到所提出算法是基于歸檔集進(jìn)行運(yùn)算和輸出的，故父代種群經(jīng)過上述層級、擁擠度評價后，若所得非支配解數(shù)量超過歸檔集大小時，為保證算法運(yùn)行效率，需對非支配解集進(jìn)行篩選,并更新歸檔集。由于擁擠度評價針對的是所有個體，且非支配解層級為1，故引入了基于幾何距離的調(diào)整策略。其具體步驟如下：

(1)求出非支配解集中任意兩個個體間的相對距離：

(13)

其中,q,q′,q″∈{1,2,…,nnon},且q≠q′,nnon為非支配解數(shù)量,fqm為個體q的m維目標(biāo)值。

(2)找出整個非支配解集中相對距離最小的兩個個體q、q′。根據(jù)q、q′與非支配解集中余下個體的相對距離刪除相關(guān)的個體,如由下式找出相對距離最小值，刪除與該最小值相關(guān)的個體q或q′：

(14)

(3)將被刪除個體與其他個體的的相對距離賦值為無窮大。

(4)如果剩下的個體數(shù)量滿足條件則停止，否則轉(zhuǎn)步驟(2)。

如果新產(chǎn)生的非支配解落在上一代確定的邊界以外，則為了保持種群多樣性，將這些個體直接放入歸檔集中。

3　混合多目標(biāo)網(wǎng)格遺傳算法

針對多目標(biāo)汽車投產(chǎn)排序問題，本文提出一種新的混合多目標(biāo)網(wǎng)格遺傳算法(hybridmulti-objectivegridgeneticalgorithm,HmoGA)。該算法結(jié)合上文所提的多目標(biāo)自適應(yīng)網(wǎng)格選擇方法，利用遺傳算法的自然選擇機(jī)理和群體進(jìn)化機(jī)制完成尋優(yōu)。

3.1編碼與解碼

考慮到編碼的簡潔與實(shí)用，采用字母方式進(jìn)行編碼。將最小生產(chǎn)循環(huán)單元內(nèi)即將投產(chǎn)的全部產(chǎn)品排成一排，構(gòu)成一個染色體。基因位的位置對應(yīng)投產(chǎn)順序,基因位的內(nèi)容表示所投產(chǎn)的車型，染色體長度等于最小生產(chǎn)循環(huán)內(nèi)要投產(chǎn)的產(chǎn)品數(shù)量。假設(shè)有3種車型(A,B,C)，投產(chǎn)比例為2∶1∶2,則其一個投產(chǎn)順序可表示為(BCAAC)。

每隔一個生產(chǎn)節(jié)拍TC，就按此投產(chǎn)順序投放一個產(chǎn)品上線。每一個生產(chǎn)循環(huán)單元的開始時間與節(jié)拍時間一致。例如,節(jié)拍為2min,每個生產(chǎn)循環(huán)單元內(nèi)有5輛車,則第3個生產(chǎn)循環(huán)單元的開始時間為第21min。

根據(jù)上述投產(chǎn)順序，利用式(4)～式(10)即可算出零部件消耗均衡度、車型調(diào)整費(fèi)用、工位作業(yè)位置精準(zhǔn)度三個目標(biāo)值。

3.2歸檔集和進(jìn)化種群選擇

當(dāng)非支配解數(shù)量超過歸檔集大小時,利用上述調(diào)整策略，選取滿足歸檔集規(guī)定大小的個體。若未超過歸檔集規(guī)定大小，則直接將非支配解納入歸檔集中。若非支配解存在極值點(diǎn)，則考慮極值點(diǎn)在單目標(biāo)評價方面的優(yōu)越性，將其直接納入歸檔集中。歸檔集的更新從趨勢上反映出Pareto前沿的推進(jìn)過程，非支配解的選擇保證了所存儲非支配解的分布性。

同理，當(dāng)非支配解集超過進(jìn)化種群規(guī)定大小時，利用調(diào)整策略選取分布性較優(yōu)的、滿足進(jìn)化種群規(guī)模的個體，構(gòu)造出進(jìn)化群體。當(dāng)?shù)玫降姆侵浣饧∮诘扔谶M(jìn)化種群數(shù)量時，優(yōu)先選擇層級較小的個體,層級相同時選擇擁擠度較小的個體。

3.3交叉?zhèn)€體選擇

針對進(jìn)化群體，采用輪盤賭方法選出即將執(zhí)行交叉操作的個體，同時將個體的Pareto層級和擁擠度信息加入到輪盤賭選擇概率的計算中, 分別算出目標(biāo)層級和進(jìn)化個體的選擇概率和累計選擇概率，再基于概率選擇所需個體，目的是保證后代的收斂性、分布性。計算如下：

(15)

(16)

(17)

Zq=∑ziq

(18)

式中,pi為層級i的選擇概率;Pi為層級i的累計選擇概率;ziq為第i層個體集合中第q個個體的選擇概率;Zq為第i層個體集合中第q個個體的累計選擇概率;Ne為進(jìn)化種群數(shù)量;Nei表示層級為i的個體數(shù)量;yiq為第i層個體集合中第q個個體的擁擠度。

式(15)、式(16)保證了層級越低，被選擇概率越大;式(17)、式(18)保證在同一層級上，擁擠度越低，越可能被選擇。

基于Pareto層級和擁擠度的概率計算，建立起一種精英評判和選擇機(jī)制,使得父代中具有較好性能的基因片段能被繼承下來，同時還有細(xì)微的擾動能力。

3.4鄰域搜索

調(diào)整鄰域結(jié)構(gòu)在一定程度上可擴(kuò)大搜索空間,拓展局部搜索能力。Chutima等[12]提出一種2-opt鄰域搜索機(jī)制,在計算復(fù)雜度不高時有著良好的局部搜索性能。Ruiz等[13]采用轉(zhuǎn)移變異算子將某個隨機(jī)基因位上的基因插入到某兩個相鄰隨機(jī)基因位之間來擴(kuò)大搜索空間，并將該算子與相鄰基因交換變異算子、任意兩個基因交換變異算子進(jìn)行比較，得出轉(zhuǎn)移變異算子在鄰域搜索性能和保持父代優(yōu)秀基因等方面性能更優(yōu)的結(jié)論。本文結(jié)合二基因位鄰域搜索機(jī)制和轉(zhuǎn)移變異算子，針對投產(chǎn)排序問題，設(shè)計出圖2所示的2-opt鄰域轉(zhuǎn)移搜索算子。

圖2　2-opt鄰域轉(zhuǎn)移搜索

如圖2所示，在父代個體P中已有的基因位置上任意選擇兩個基因(opt1，opt2)作為轉(zhuǎn)移基因，再任意選擇兩個空位(po1, po2)作為轉(zhuǎn)移目的地。將選出的基因轉(zhuǎn)移到相應(yīng)的目的地中。其他基因位順次調(diào)整，生成后代個體O。

將該鄰域搜索機(jī)制混入已提出的遺傳算法中，改進(jìn)了非支配解的鄰域結(jié)構(gòu)，以保證種群的多樣性，提高集中搜索能力，加快收斂速度。

3.5算法流程

具體流程如圖3所示。可以看出，基于相鄰個體幾何距離的調(diào)整策略、Pareto層級劃分和擁擠度計算，在歸檔集構(gòu)造、進(jìn)化種群選擇和交叉?zhèn)€體選擇中起到了核心作用。同時，從進(jìn)化種群中選擇出來的個體，進(jìn)行直接后繼關(guān)系交叉(ISRX)[11]后生成子代Cchild1。對進(jìn)化種群和子代Cchild1進(jìn)行連續(xù)反演變異(INV)[11],生成子代Cchild2。對歸檔集進(jìn)行鄰域搜索生成子代Cchild3。將上述生成的所有子代群體和非支配解集的并集賦予父代種群。若達(dá)到了進(jìn)化代數(shù)，則停止，否則對新一代父代群體進(jìn)行Pareto層級劃分、擁擠度評價，進(jìn)一步完成歸檔集和進(jìn)化種群的更新。重復(fù)上述操作，直到滿足終止條件。

圖3　HmoGA流程圖

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

為檢驗(yàn)所提出的HmoGA的性能，利用MATLAB對上述算法和NSGA-Ⅱ[2]分別進(jìn)行編碼，并將運(yùn)行結(jié)果與NSGA-Ⅱ進(jìn)行比較。

4.1參數(shù)設(shè)定

某汽車廠生產(chǎn)線上有16個工位，需生產(chǎn)3種車型，排產(chǎn)比例為12∶10∶7,詳見表1的p5問題。以p5為原型,進(jìn)一步設(shè)計了表1所示的3個小規(guī)模(p1～p3)、1個中等規(guī)模(p4)和2個大規(guī)模(p6,p7)問題。其中,各種規(guī)模問題的復(fù)雜度即可行解數(shù)用下式進(jìn)行計算:

nc=(∑dk)!/∏(dk!)

(19)

根據(jù)現(xiàn)場情況,將各車型對每種零件的消耗量取[0,10]的隨機(jī)整數(shù)，各車型在每個工位上的操作時間取[60,120]s的隨機(jī)數(shù)，各車型的調(diào)整費(fèi)用取[0,10]元的隨機(jī)數(shù)?？紤]到計算時間的限制，將歸檔集的大小設(shè)置為500。種群大小、進(jìn)化代數(shù)等其他參數(shù)設(shè)置如表1所示。

表1　投產(chǎn)測試集問題

由于生產(chǎn)節(jié)拍設(shè)置須滿足生產(chǎn)需求，故先找出最小生產(chǎn)循環(huán)內(nèi)總工作時間最長的工位，求取其每輛車的平均操作時間作為生產(chǎn)節(jié)拍。假定p1問題中各工位操作時間如表2所示，求得其生產(chǎn)節(jié)拍為112 s。

表2　p1問題的各工位操作時間　s

4.2排序方案性能分析

為檢驗(yàn)使用HmoGA算法所求投產(chǎn)方案的正確性，以p1問題為例，求解得到了若干非支配解，見表3。同時，也利用枚舉法求出p1問題的真實(shí)前沿解。

表3　p1問題非支配解及其目標(biāo)值

兩者對照表明,HmoGA得到了p1問題所有的真實(shí)前沿解，證明在小規(guī)模問題上該算法具有最優(yōu)性。同時，在所有解中，零件消耗偏差、車型調(diào)整費(fèi)用相差不大，而作業(yè)精準(zhǔn)率的變化比較大。對于大規(guī)模問題，由于不可能用枚舉法一一列出所有可行解來對其進(jìn)行層級評價以求出其真實(shí)前沿解，因此HmoGA所求得的非支配解的屬性無法通過與真實(shí)前沿比較來檢驗(yàn)。后面將會通過和其他算法(NSGA-Ⅱ)對比來驗(yàn)證其非支配解性能。

在具體決策時，可根據(jù)各目標(biāo)在生產(chǎn)實(shí)際中的重要性，以及所得非支配解中各目標(biāo)值的變化率大小，確定各目標(biāo)權(quán)重，選擇最終投產(chǎn)方案。按照上述思想確定出p1問題的最優(yōu)投產(chǎn)序列為(BCCABC)。由圖4可見，若按此序列組織生產(chǎn),則各工位裝配總時間較均勻，不僅零件消耗偏差和車型調(diào)整費(fèi)用較小，還能較好保證各工位的作業(yè)精準(zhǔn)率。

圖4　多車型混流生產(chǎn)作業(yè)甘特圖

4.3算法性能分析

NSGA-Ⅱ算法是當(dāng)前綜合性能最好、應(yīng)用最廣泛的多目標(biāo)算法[1]，其求解效率高，收斂性能優(yōu)，分布性能好，故選擇該算法作為比較對象來評價HmoGA算法的性能。具體評價指標(biāo)包括非支配率[10]、非支配解個數(shù)、相鄰個體距離偏差[14]、相對百分偏差[13],計算結(jié)果見表4。在此基礎(chǔ)上完成算法收斂性和多樣性分析。

表4　兩種算法所得投產(chǎn)排序方案性能比較

4.3.1收斂性分析

圖5為p5問題利用HmoGA計算得到的非支配解收斂性優(yōu)化圖?？梢园l(fā)現(xiàn)，在進(jìn)化過程中非支配解不斷增加。第一代非支配解數(shù)量偏少，各目標(biāo)值偏大。隨著優(yōu)化過程的進(jìn)行，非支配解數(shù)量越來越多，收斂速度也越來越快，非支配解也越來越接近真實(shí)前沿。到100代時，收斂速度明顯放緩，但還是在持續(xù)進(jìn)行,到200代時還找到了一個新的分支。新算法極大改進(jìn)了非支配解。

圖5　HmoGA收斂性分析圖

比較HmoGA和NSGA-Ⅱ兩種算法的收斂性指標(biāo)可知：在小規(guī)模問題中兩種算法幾乎找到了所有的非支配解；從中等規(guī)模問題開始，HmoGA所求非支配解基本上不被支配,而NSGA-Ⅱ的非支配解中至少有一半被支配。例如，HmoGA非支配率達(dá)到98%以上，其相對百分偏差最大值高達(dá)10 400%。

上述結(jié)果表明，HmoGA對中大規(guī)模問題具有更強(qiáng)的適應(yīng)性，其非支配解更接近真實(shí)前沿。分析可知，通過層級評價機(jī)制，可使非支配解在進(jìn)化前期迅速靠近真實(shí)前沿。同時，由于極值點(diǎn)保留機(jī)制和鄰域搜索的存在，始終具有搜索到更多鄰域結(jié)構(gòu)的可能性。

4.3.2多樣性分析

進(jìn)化種群的多樣性一般從兩個方面進(jìn)行分析：在一定空間內(nèi)的個體數(shù)量、種群個體分布的均勻程度。圖6示出了另一組隨機(jī)參數(shù)下p4問題的非支配解數(shù)量和分布性指標(biāo)隨迭代次數(shù)增加的變動趨勢?？梢钥闯觯谶M(jìn)化初期非支配解數(shù)量很少，分布性較差。隨著不斷進(jìn)化，非支配解逐漸增多，相鄰個體距離偏差持續(xù)減小，種群分布更均勻。當(dāng)進(jìn)化代數(shù)達(dá)到120代時，非支配解數(shù)量接近歸檔集大小，分布性指標(biāo)基本不變。當(dāng)非支配解數(shù)量超過歸檔集規(guī)定大小時(135代)，運(yùn)用調(diào)整策略對非支配解進(jìn)行篩選，保持了非支配解的分布性。

圖6　多樣性分析圖

下面通過分析表4中的數(shù)據(jù)，進(jìn)一步討論非支配解的多樣性。關(guān)于非支配解的分布性，在小規(guī)模案例中，兩種算法基本能找出所有非支配解，分布性能基本相同。隨著問題規(guī)模的增大,HmoGA的優(yōu)勢越來越明顯。如表4所示，對于p3、p4、p7問題，HmoGA所得非支配解的分布性指標(biāo)相對于NSGA-Ⅱ所得非支配解的分布性指標(biāo)提高約150%。關(guān)于非支配解的數(shù)量，對于任一問題，HmoGA搜尋到的非支配解數(shù)遠(yuǎn)多于NSGA-Ⅱ。在小規(guī)模案例中兩種算法都得到了相同的非支配解。隨問題規(guī)模的增大，HmoGA所得到的非支配解數(shù)大大增加。以p4問題(圖7)為例，其非支配解數(shù)小于歸檔集規(guī)模，HmoGA獲得了426個非支配解，而NSGA-Ⅱ只獲得68個。

圖7　HmoGA與NSGA-Ⅱ前沿比較

在問題規(guī)模很大時，如圖8所示的P7問題，HmoGA所得非支配解數(shù)在110代時超過了歸檔集大小，若不采用調(diào)整策略,則搜索到的非支配解逐漸增多，相應(yīng)的運(yùn)行時間也會遞增。采用分布性調(diào)整策略后，通過對非支配解集內(nèi)部進(jìn)行篩選，使非支配解數(shù)量保持在一定的范圍內(nèi)，同時算法的運(yùn)行效率得到大幅提升。

綜上所述，當(dāng)算法陷入局部最優(yōu)時，HmoGA的鄰域搜索機(jī)制和突變操作可幫助算法尋找新的進(jìn)化區(qū)域，能夠適時地擴(kuò)大搜索空間，跳出局部最優(yōu)。 另外，相同個體排斥機(jī)制、擁擠度評價策略的存在能夠及時刪除目標(biāo)值相同的個體，并以更大的概率選擇分布性較好的個體，從而提高種群分布性。

5　總結(jié)

(1)針對某汽車公司的投產(chǎn)排序問題，提出了一種混合多目標(biāo)網(wǎng)格遺傳算法HmoGA,以便同時實(shí)現(xiàn)零件消耗偏差小、車型調(diào)整費(fèi)用低和工位作業(yè)精準(zhǔn)三個目標(biāo)。針對上述實(shí)際問題和投產(chǎn)目標(biāo)，設(shè)計了大、中、小三種規(guī)模投產(chǎn)案例，運(yùn)用非支配率、非支配解數(shù)量和相鄰個體距離偏差三個指標(biāo)，對所提算法與經(jīng)典多目標(biāo)算法 NSGA-Ⅱ進(jìn)行了性能比較,證明HmoGA算法在收斂性、解的數(shù)量和分布性方面都具有明顯優(yōu)勢，特別是中大規(guī)模問題中其優(yōu)越性更顯著。

(2)將相同個體排斥機(jī)制加入到層級評價過程中，可使非支配解的分布更加均勻。

(3)融合基于相鄰個體距離的種群調(diào)整策略，可增加算法的運(yùn)行效率，促進(jìn)均衡分布。

(4)利用2-opt遷移算子對非支配解進(jìn)行鄰域搜索，拓展了優(yōu)秀基因的鄰域結(jié)構(gòu)。

綜合性能較高的多個非支配解的存在，為企業(yè)后期決策提供更多的選擇，對平衡生產(chǎn)線負(fù)載、提高員工積極性、縮短供貨周期、增強(qiáng)核心競爭力，具有很大的作用。

[1]唐秋華,席忠民,陳平和,等.高效精準(zhǔn)混裝作業(yè)調(diào)度策略研究[J].中國機(jī)械工程,2007,18(9):1108-1111.

Tang Qiuhua,Xi Zhongmin,Chen Pinghe,et al.Research on Scheduling Strategy for High Efficiency & Punctuality in Mixed Model Assembly Line[J].China Mechanical Engineering,2007,18(9):1108-1111.

[2]Deb K,Pratap A,Agarwal S,et al.A Fast and Elitist Multi-objective Genetic Algorithm:NSGA-Ⅱ[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.

[3]劉敏, 曾文華, 趙建峰. 一種快速的雙目標(biāo)非支配排序算法[J].模式識別和人工智能,2011,24(4):538-547.

Liu Min,Zeng Wenhua,Zhao Jianfeng.A Fast Bi-objective Non-dominated Sorting Algorithm [J].Pattern Recognition and Artificial Intelligence,2011,24(4):538-547.

[4]鮑培明,朱慶保.用于多目標(biāo)進(jìn)化的歸一化排序非支配集構(gòu)造方法[J].電子學(xué)報,2009,37(9):23-28.

Bao Peiming,Zhu Qingbao.A Technique of Building Non-dominated Set Based on Normalized Sort in Evolutionary Multi-objective Optimization[J].Acta Mechanica Sinica,2009,37(9):23-28.

[5]楊虎,許峰.基于聚集密度的粒子群多目標(biāo)優(yōu)化算法[J].計算機(jī)工程與應(yīng)用,2013,49(17):190-194.

Yang Hu,Xu Feng.Multi-objective Particle Sarm Optimization Algorithm Based on Crowding-density.Computer Engineering and Applications,2013,49(17):190-194.

[6]李志強(qiáng),藺想紅.基于聚類的NSGA-Ⅱ算法[J].計算機(jī)工程,2013,39(12):186-190.

Li Zhiqiang,Lin Xianghong.Non-dominated Sorting Genetic Algorithm II Based on Clustering[J].Computer Engineering,2013,39(12):186-190.

[7]戚玉濤,劉芳,常偉遠(yuǎn),等.求解多目標(biāo)問題的Memetic免疫優(yōu)化算法[J].軟件學(xué)報,2013,24(7):1529-1544.

Qi Yutao,Liu Fang,Chang Weiyuan,et al.Memetic Immune Algorithm for Multi-objective Optimization[J].Journal of Software,2013,24(7):1529-1544.

[8]賈寧,馬壽峰.基于啟發(fā)式搜索和反饋修正的單路口控制方法[J]. 系統(tǒng)工程理論與實(shí)踐, 2013, 33(2):444-449.

Jia Ning,Ma Shoufeng.A Traffic Signal Control Method for an Isolate Intersection Based on Heuristic Search and Feedback Correction[J].Systems Engineering Theory and Practice,2013,33(2):444-449.

[9]Tang Qiuhua,Li Jie,Floudas C A,et al.Optimization Framework for Process Scheduling of Operation-dependent Automobile Assembly Lines[J].Optimization Letters,2012,6(4):797-824.

[10]鄭金華. 多目標(biāo)進(jìn)化算法及其應(yīng)用[M].北京：科學(xué)出版社，2007.

[11]Hyun Chulju,Kim Yeongho,Kim Yeokeun.A Genetic Algorithm for Multiple Objective Sequencing Problems in Mixed Model Assembly Lines[J].Computers & Operations Research,1998,25(7/8):67.

[12]Chutima P,Naruemitwong W.A Pareto Biogeography-based Optimisation for Multi-objective Two-sided Assembly Line Sequencing Problems with a Learning Effect[J].Computers & Industrial Engineering,2014,69:89-104.

[13]Ruiz R,Maroto C,Alcaraz J.Two New Robust Genetic Algorithms for the Flowshop Scheduling Problem[J].Omega,2006,34(5):461-476.

[14]Coello Coello C A,Pulido G T,Lechuga M S.Handling Multiple Objectives with Particle Swarm Optimization[J].IEEE Trans. on Evolutionary Computation,2004,8(3):256-27.

(編輯蘇衛(wèi)國)

A Hybrid Multi-objective Grid Genetic Algorithm for Automobile Production Sequencing Problems

Tang Qiuhua1Hu Jin1Zhang Liping1Cao Xiaojun2

1.Wuhan University of Science & Technology,Wuhan,430081 2.Dongfeng-Peugot-Citroen Automation Co., Ltd.,Wuhan,430056

Three objectives were expected to be achieved simultaneously when sequencing automobiles in process,including equaling the spare parts consumption,minimizing the total adjustment cost resulting from exchanging automobile models,calibrating the work position for each automobile on any station.A new hybrid multi-objective grid genetic algorithm(HmoGA) was proposed based on Pareto stratum.In the algorithm,a new rejection mechanism was first considered in the sorting process of Pareto stratum,for the purpose of getting the even distribution of the non-dominated solutions.Then an adaptive grid selection scheme was designed by integrating Pareto stratum evaluation,crowding degree calculation and distance estimation among adjacent individuals.Thus,higher quality population can be generated,better parent chromosomes can be selected,and the distribution of the Pareto front can be improved constantly.Finally,the 2-opt shift operator was hybridized into the proposed genetic algorithm so as to broaden the search space and escape from local optimum.Three groups of experiments have done and three metrics including non-dominated ratio,the number of Pareto optimal solutions and the deviation of distances between neighbors were used as the performance measures.The results reveal that the proposed HmoGA dramatically outperforms NSGA-Ⅱ in terms of convergence and diversification.

Pareto stratum;crowding degree;adaptive grid selection;rejection mechanism;local search

2014-11-17

國家自然科學(xué)基金資助項(xiàng)目(51275366,51305311);高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金資助項(xiàng)目(20134219110002,2013M542073)；湖北省教育科學(xué)“十一五”規(guī)劃課題(2007B215)

TH16;TP39DOI：10.3969/j.issn.1004-132X.2015.16.008

唐秋華,女,1970年生。武漢科技大學(xué)機(jī)械自動化學(xué)院教授、博士研究生導(dǎo)師。主要研究方向?yàn)樯a(chǎn)過程與調(diào)度。胡進(jìn),男,1990年生。武漢科技大學(xué)機(jī)械自動化學(xué)院碩士研究生。張利平,女,1983年生。武漢科技大學(xué)機(jī)械自動化學(xué)院講師。操小軍,男,1970年生。神龍汽車公司技術(shù)中心首席工程師。