，*

（1.西華師范大學(xué)數(shù)學(xué)與信息學(xué)院，四川南充 637009；2.西華師范大學(xué)計(jì)算方法及應(yīng)用軟件研究所，四川南充 637009）

0 引言

汽車產(chǎn)業(yè)的飛速發(fā)展使得汽配件的生產(chǎn)呈現(xiàn)爆發(fā)性增長。外觀類汽配件通常需要進(jìn)行顏色噴涂，這樣既能滿足顧客對汽車外觀的審美需求，也能確保汽車在自然環(huán)境條件下的耐用性需求。生產(chǎn)線上的汽配件噴涂顏色時(shí)，若前后相鄰兩個汽配件需要噴涂不同的面漆色，則稱為一次“換色”，此時(shí)需要更換噴槍的涂料顏色，換色次數(shù)的多少會影響生產(chǎn)成本。

上述情形可稱為汽配件顏色噴涂順序問題，本文選取比較常見的一種環(huán)形噴涂生產(chǎn)線，如圖1 所示，生產(chǎn)線上設(shè)置有一定數(shù)量的滑橇，有特定的換件處和噴涂處。汽配件被依次安裝在滑橇上，隨滑橇在軌道上移到噴涂處進(jìn)行噴色，當(dāng)移到換件處則將其取下。

圖1 汽配件噴涂生產(chǎn)線Fig.1 Spraying production line for auto parts

在實(shí)際生產(chǎn)過程中，某些類別的汽配件由于形狀等因素會導(dǎo)致不能相鄰排列、某些顏色的汽配件由于顏色原料的特定要求會導(dǎo)致不能相鄰排列，這些因素都會影響到顏色切換次數(shù)進(jìn)而影響到生產(chǎn)成本，因此，研究和優(yōu)化一批生產(chǎn)任務(wù)內(nèi)的汽配件序列，可以理論指導(dǎo)生產(chǎn)實(shí)踐并幫助企業(yè)提高生產(chǎn)效率、降低生產(chǎn)成本。

上述問題實(shí)質(zhì)上是一類產(chǎn)品加工順序問題，也可看作是一類柔性作業(yè)車間調(diào)度問題。通常遇到這類調(diào)度問題首先考慮到用經(jīng)典的動態(tài)規(guī)劃方法來對問題進(jìn)行求解，但動態(tài)規(guī)劃方法在求解大規(guī)模問題時(shí)效率低、速度慢，而在對原問題的分析中發(fā)現(xiàn)在汽配件噴涂生產(chǎn)線上，每一個滑橇上安裝的汽配件都要噴涂且只噴涂一次，這非常類似于旅行商問題（Travelling Salesman Problem，TSP）［1］，故本文采用借鑒TSP建模的方法對汽配件噴涂順序問題進(jìn)行轉(zhuǎn)化建模。旅行商問題作為著名的NP-hard 問題，近年來許多專家學(xué)者對該問題的求解提供了許多的優(yōu)化算法，如遺傳算法［2-3］和模擬退火算法［4］、蟻群優(yōu)化（Ant Colony Optimization，ACO）算法［5］、粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法［6-7］、狼群算法［8］、煙花算法［9］，取得了比較豐富的研究成果。而遺傳算法自提出以來，在求解TSP 領(lǐng)域中取得了較好的成果。同傳統(tǒng)的PSO算法和ACO算法相比，遺傳算法的全局尋優(yōu)能力強(qiáng)、具有潛在的并行性，可以進(jìn)行多個個體的同時(shí)比較。盡管如此，遺傳算法的進(jìn)化概念不能直接應(yīng)用于求解汽配件噴涂順序問題，必須通過將原問題轉(zhuǎn)化為TSP，建立適應(yīng)的TSP 轉(zhuǎn)化模型，再用遺傳算法對模型進(jìn)行求解從而求解出汽配件噴涂的順序問題。為此，本文提出了一種基于TSP 轉(zhuǎn)化和遺傳算法的優(yōu)化和求解方法，實(shí)驗(yàn)結(jié)果表明該優(yōu)化模型刻畫準(zhǔn)確、求解算法高效實(shí)用。

1 TSP轉(zhuǎn)化與建模

1.1 定義TSP頂點(diǎn)及其距離

在汽配件噴涂生產(chǎn)線上，每一個滑橇上安裝的汽配件都要噴涂且只噴涂一次，這非常類似于TSP。設(shè)一條生產(chǎn)線共有N個滑橇，將待噴涂的N組汽配件看作是N個TSP 頂點(diǎn)，對它們以一定順序編號，即構(gòu)成一個TSP 的頂點(diǎn)集，記為V={v1，v2，…，vN}。

與TSP不同，在汽配件噴涂順序問題中，任意兩組待噴涂的汽配件之間并沒有距離的概念?？紤]到問題的目標(biāo)是使噴涂生產(chǎn)線上換色次數(shù)盡量少，因此可以用任意兩組汽配件的顏色是否發(fā)生切換來定義頂點(diǎn)之間的距離。

設(shè)N組待噴涂汽配件的顏色共有L種，用自然數(shù)1，2，…，L來表示對應(yīng)的顏色號，頂點(diǎn)vi對應(yīng)的顏色號記為pi∈{1，2，…，L}，所有頂點(diǎn)顏色號記為P={p1，p2，…，pN}。定義任意兩個頂點(diǎn)是否需要換色（顏色是否相同）為其距離，若要換色則距離為1，否則為0，可表示為：

由dij構(gòu)成的頂點(diǎn)距離矩陣記為D=(dij)N×N，由于dij是0-1變量，因此N個頂點(diǎn)構(gòu)成的一條TSP路徑（一個噴涂序列）的距離之和剛好也能反映噴涂該序列的換色總次數(shù)。

1.2 構(gòu)建TSP模型

與標(biāo)準(zhǔn)TSP 的約束一樣，汽配件噴涂順序問題的N個頂點(diǎn)要構(gòu)成一條TSP 路徑，也要滿足任意頂點(diǎn)的出度為1、入度也為1，以及不構(gòu)成子回路這三種基本約束條件。此外，比起標(biāo)準(zhǔn)的TSP來說汽配件噴涂順序問題還應(yīng)當(dāng)滿足噴涂生產(chǎn)的兩類限制條件：某些配件的顏色因調(diào)色等因素具有互斥性，對應(yīng)的這些汽配件組將不能安裝在相鄰的滑橇上噴涂；某些配件的形狀容易導(dǎo)致相互之間碰撞和劃傷，對應(yīng)的這些汽配件組將不能安排在相鄰的滑橇上噴涂，故將借鑒TSP經(jīng)典模型，建立適合汽配件噴涂問題的TSP轉(zhuǎn)化數(shù)學(xué)模型。

類似于頂點(diǎn)距離的定義，可以對任意兩個頂點(diǎn)的顏色和類別是否允許相鄰進(jìn)行定義，再用它對TSP 路徑的顏色和類別限制進(jìn)行約束。為便于計(jì)算，首先對顏色或類別之間是否允許相鄰進(jìn)行量化定義。設(shè)汽配件的類別共有K種，用自然數(shù)1，2，…，K來表示對應(yīng)的類別號，則任意兩種顏色或類別是否允許相鄰可分別定義為：

由cij，tij構(gòu)成的顏色和類別的相鄰性矩陣分別記為C=(cij)L×L，T=(tij)K×K，矩陣C、T不一定是對稱陣，因?yàn)橛行╊伾蝾悇e之間的前后相鄰性并不完全相同。

設(shè)頂點(diǎn)vi的配件類別號為qi∈{1，2，…，K}，所有頂點(diǎn)的類別號記為Q={q1，q2，…，qN}，則任意兩個頂點(diǎn)的顏色和類別是否允許相鄰性可分別定義為：

由rij，sij構(gòu)成的頂點(diǎn)顏色和類別相鄰性矩陣分別記為R=(rij)N×N，S=(sij)N×N。

仿照標(biāo)準(zhǔn)TSP的0-1規(guī)劃模型，設(shè)有如下0-1變量：

則可建立汽配件噴涂順序問題的0-1規(guī)劃模型如下：

在模型中，約束條件（1）和（2）使得對每一個頂點(diǎn)只能有一條邊進(jìn)和一條邊出，約束條件（3）使得不會產(chǎn)生任何的子回路，約束條件（4）和（5）使得在TSP 路徑上的相鄰兩個頂點(diǎn)之間不會出現(xiàn)汽配件的顏色和類別不允許相鄰的情形。

2 遺傳算法設(shè)計(jì)

在實(shí)際生產(chǎn)中，汽配件噴涂順序問題的規(guī)模較大，現(xiàn)代智能啟發(fā)式算法［10］是求解這類問題的主要算法，遺傳算法［11］就是其中一種高效實(shí)用、魯棒性強(qiáng)的算法，它借鑒生物遺傳學(xué)原理，模擬自然界生物的遺傳進(jìn)化過程，具有優(yōu)異的自適應(yīng)性、并行性和全局尋優(yōu)能力。遺傳算法首先需要為可行解選擇恰當(dāng)?shù)幕蚓幋a方案，并產(chǎn)生一定數(shù)量的初始種群，然后對種群進(jìn)行一定次數(shù)的遺傳進(jìn)化操作，包括適應(yīng)度評估、選擇、交叉、變異操作，最終獲得問題的近似最優(yōu)解。下面根據(jù)汽配件噴涂問題的特點(diǎn)，進(jìn)行遺傳算法的設(shè)計(jì)。

2.1 編碼方案

遺傳算法不能直接處理問題空間的參數(shù)，需要將其編碼成為遺傳空間的染色體。遺傳算法的魯棒性強(qiáng)，對基因編碼方案要求并不苛刻，但是編碼方案對遺傳操作有很大的影響，特別是交叉和變異操作。在TSP 的0-1 規(guī)劃模型中，所有的0-1 型變量xij就是問題空間的參數(shù)，共有N2個，如果將這些參數(shù)編碼成為二進(jìn)制形式的染色體，當(dāng)N較大時(shí)，會導(dǎo)致染色體的編碼長度太長，在計(jì)算機(jī)存儲和遺傳操作的運(yùn)算等方面都會難以處理。除此以外，xij還受到五類約束條件的限制，因此即使生成了編碼，也必然存在著大量的無效編碼，需要借助額外的算法進(jìn)行檢測和剔除，再重新補(bǔ)充生成合法有效的染色體編碼，這必然又增加算法的復(fù)雜性。

考慮到汽配件噴涂順序問題也是TSP 的一類擴(kuò)展應(yīng)用，需要求得的最優(yōu)解就是所有頂點(diǎn)（全部待噴涂的汽配件組）的某個特定的最優(yōu)順序，因此可以將這些頂點(diǎn)編號作為問題空間的參數(shù)進(jìn)行編碼：一方面滿足編碼方案的完備性、健全性和非冗余性；另一方面染色體的編碼長度從N2位下降到N位，這樣遺傳算法也容易實(shí)現(xiàn)，提高了算法的實(shí)用性。一般地，頂點(diǎn)編號以自然數(shù)表示，因此在本問題中，采用不重復(fù)的自然數(shù)對全部頂點(diǎn)進(jìn)行染色體編碼［12］，于是每一個個體的染色體編碼可表示為：

設(shè)初始種群規(guī)模為m，則可表示為X=[X1；X2；…；Xm]。

2.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)用于評估和區(qū)分種群個體的優(yōu)劣，是進(jìn)行遺傳選擇的依據(jù)。本問題中，由于有生產(chǎn)限制的約束條件，即使采用不重復(fù)的自然數(shù)編碼［13］方案，也仍然無法避免無效編碼的出現(xiàn)。此時(shí)有兩種解決方法：一是設(shè)計(jì)額外的檢測算法，剔除無效編碼，再補(bǔ)充生成有效編碼；二是將與無效編碼對應(yīng)的約束條件以懲罰分量的形式添加到目標(biāo)函數(shù)中，使得包含有無效編碼的個體在遺傳進(jìn)化過程中具有更差的適應(yīng)度。為降低算法的空間和時(shí)間復(fù)雜性，提高算法的實(shí)用性，本文采用第二種解決方法，并按以下方法構(gòu)造適應(yīng)度函數(shù)。

由第1 章可知，對任意一個噴涂序列τ={τ1，τ2，…，τN}（τi∈V且互不相同），它的路徑長度（換色總次數(shù)）、出現(xiàn)配件顏色不允許相鄰的總次數(shù)、出現(xiàn)配件類別不允許相鄰的總次數(shù)，可分別用以下公式計(jì)算：

其中：f2，f3即是對模型中約束條件（4）和（5）的轉(zhuǎn)化，將其作為懲罰分量，添加到適應(yīng)度函數(shù)中，當(dāng)其值趨于0 時(shí)，噴涂序列中相鄰頂點(diǎn)的顏色和類別必定是符合生產(chǎn)要求的。

設(shè)三個分量的權(quán)重分別為λ1，λ2，λ3∈[0，1]，(λ1+λ2+λ3=1)，則適應(yīng)度函數(shù)為：

可以看到，當(dāng)適應(yīng)度函數(shù)達(dá)到最小時(shí)，若分量f2，f3趨于0，則分量f1恰好能近似等于噴涂序列的最少換色次數(shù)。

2.3 遺傳進(jìn)化策略

遺傳算法的遺傳進(jìn)化策略包括選擇、交叉和變異［14］，選擇策略可以將種群中適應(yīng)度高的個體選擇出來，交叉和變異策略可以在已選擇個體基礎(chǔ)上產(chǎn)生新個體，以提高種群的多樣性，提高收斂速度。一些研究表明，錦標(biāo)賽選擇策略通用于最大化和最小化問題，在求解精度和收斂速度方面性能優(yōu)異［15］。本文選擇錦標(biāo)賽選擇策略，以此為基礎(chǔ)來設(shè)計(jì)遺傳進(jìn)化策略。

體育運(yùn)動的錦標(biāo)賽最早是指單項(xiàng)運(yùn)動的冠軍賽，運(yùn)動員首先通過分組比賽，才能進(jìn)入決賽獲得冠軍。錦標(biāo)賽選擇策略正是借鑒這種賽制規(guī)則和賽程安排原理，基本思想是分組和優(yōu)選，主要操作方法是預(yù)先確定一個分組規(guī)模，將整個種群隨機(jī)地分成若干個種群小組，每個小組內(nèi)只選擇組內(nèi)最優(yōu)的個體作為遺傳的新個體，并將其復(fù)制若干份，以保持新個體的規(guī)模不變。為提高運(yùn)算速度，在復(fù)制新個體時(shí)，可以同步加入個體的交叉和變異策略。由于編碼方案是不重復(fù)的自然數(shù)編碼，個體之間進(jìn)行基因交叉，很容易導(dǎo)致兩個個體的基因都出現(xiàn)重復(fù)的數(shù)字，變成非法編碼，因此本文不采用交叉策略，著重設(shè)計(jì)了三種變異策略，分別用于不同的新個體，以提高新個體的多樣性。

第一種變異策略是兩點(diǎn)基因交換（Swap），即隨機(jī)產(chǎn)生兩個基因點(diǎn)，將個體中這兩個基因點(diǎn)的值進(jìn)行交換。第二種變異策略是基因片段翻轉(zhuǎn)（Flip），即隨機(jī)產(chǎn)生兩個基因點(diǎn)，將介于這兩個基因點(diǎn)內(nèi)的基因片段進(jìn)行翻轉(zhuǎn)。第三種變異策略是基因片段滑動（Slide），即循環(huán)移位，具體做法是隨機(jī)產(chǎn)生兩個基因點(diǎn)，將介于這兩個基因點(diǎn)之內(nèi)的基因片段作循環(huán)移位一次，可以向左移位，也可以向右移位。根據(jù)上述遺傳進(jìn)化策略去具體求解汽配件最優(yōu)噴涂順序的操作示例如圖2所示。

圖2 遺傳進(jìn)化策略的操作示例Fig.2 Operation example of genetic evolution strategy

2.4 算法流程

根據(jù)遺傳算法的基本流程，結(jié)合上述算法設(shè)計(jì)，汽配件顏色噴涂順序問題的遺傳算法求解流程如圖3所示。

其中，汽配件初始數(shù)據(jù)主要包括：待噴涂汽配件的類別K、顏色L、組數(shù)M，配件之間顏色不允許相鄰的情況C、類別不允許相鄰的情況T，以及由上述數(shù)據(jù)計(jì)算得到待噴涂序列的頂點(diǎn)集V、顏色號P、類別號Q、任意兩個頂點(diǎn)的換色距離矩陣D、顏色相鄰性矩陣R和類別相鄰性矩陣S。

圖3 遺傳算法的流程Fig.3 Flowchart of genetic algorithm

3 仿真實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)數(shù)據(jù)準(zhǔn)備

為檢驗(yàn)算法的有效性和實(shí)用性，參考一些企業(yè)的實(shí)驗(yàn)生產(chǎn)數(shù)據(jù)，本文將待噴涂的汽配件個數(shù)最大設(shè)置為293 個，作為一條生產(chǎn)線的一個工作日的生產(chǎn)任務(wù)，這些汽配件包括31 個類別，需要噴涂的顏色有10 種，不同類別的汽配件、不同顏色的汽配件分為83組，全部初始實(shí)驗(yàn)數(shù)據(jù)如表1。

表1 待噴涂汽配件的初始數(shù)據(jù)Tab.1 Initial data of auto parts to be sprayed

汽配件的顏色約束為：顏色號｛1，2，3，6｝中的任意顏色之后不能接4 或10 號顏色；4 號顏色后面不能接7 或9 號顏色；10 號顏色前面只能是4 號顏色。汽配件的類別約束為：22 號配件不能與｛11，21，23，24，26-31｝中任意一種配件相鄰；23號配件不能與｛11，21，22，24，26-31｝中任意一種配件相鄰。

為更好地檢驗(yàn)上述TSP 模型及對應(yīng)遺傳算法對不同規(guī)模數(shù)據(jù)的求解性能，現(xiàn)將上述初始數(shù)據(jù)進(jìn)一步分組為較小規(guī)模、中等規(guī)模和較大規(guī)模的三組數(shù)據(jù)，具體數(shù)據(jù)如表2。

表2 三種規(guī)模的實(shí)驗(yàn)數(shù)據(jù)Tab.2 Experimental data of three scales

對上述三種規(guī)模數(shù)據(jù)，汽配件個數(shù)分別為64、93、293，對應(yīng)于TSP，即是分別有64、93、293個路徑頂點(diǎn)。由于本文討論的汽配件顏色噴涂問題的目標(biāo)是使換色次數(shù)盡量少，而上述三種規(guī)模數(shù)據(jù)中汽配件的顏色數(shù)分別為5、7、10，因此它們的理論最優(yōu)解分別為5、7、10。

3.2 結(jié)果分析

本次實(shí)驗(yàn)硬件環(huán)境為AMD A8-45000M CPU/8GB/Win 7系統(tǒng)，編程環(huán)境為Matlab R 2018a。對表2 的三種規(guī)模數(shù)據(jù)，按流程圖3編程，在不同算法參數(shù)下求解結(jié)果如表3。

表3 三種規(guī)模數(shù)據(jù)在不同算法參數(shù)下的求解結(jié)果Tab.3 Results of solving data with three scales under different algorithm parameters

從表3 中對中等規(guī)模和較小規(guī)模的求解結(jié)果中可以看出，在迭代次數(shù)和種群規(guī)模適中的情況下最優(yōu)適應(yīng)度f分別為7 和5，其中3 個分量都值為f1=10，f2=0，f3=0，即這兩種規(guī)模汽配件數(shù)的最優(yōu)噴涂序列換色次數(shù)都為顏色總數(shù)，違背顏色約束的次數(shù)都為0，違背配件類別約束的次數(shù)都為0。

同樣的，在迭代次數(shù)和種群規(guī)模適中的情況下，對較大規(guī)模的汽配件初始數(shù)據(jù)用本文設(shè)計(jì)的模型和算法進(jìn)行計(jì)算時(shí)求解結(jié)果得到的最優(yōu)適應(yīng)度為f=10，其中3 個分量值為f1=10，f2=0，f3=0，即上述最優(yōu)噴涂序列的最少換色次數(shù)為10次，違背顏色約束的次數(shù)為0，違背配件類別約束的次數(shù)為0。

從以上結(jié)果可以看出，不管數(shù)據(jù)規(guī)模的大小通過本算法的求解都可以得到最優(yōu)解，充分證明本文的基于TSP 轉(zhuǎn)化和遺傳算法求解汽配件最優(yōu)噴涂順序的優(yōu)化方法是有效的。隨著迭代次數(shù)和種群規(guī)模的增加，還可以進(jìn)一步提高算法優(yōu)化能力，限于篇幅這里不再一一列舉。

圖4 是不同規(guī)模實(shí)驗(yàn)數(shù)據(jù)下選擇第三行數(shù)據(jù)所做的適應(yīng)度值隨運(yùn)行次數(shù)的變化曲線。從圖4 中可以看出隨著迭代次數(shù)的增加，適應(yīng)度的值逐漸接近于理論最優(yōu)解。

圖4 不同規(guī)模數(shù)據(jù)的適應(yīng)度進(jìn)化曲線Fig.4 Fitness evolution curve of data with different scales

3.3 算法求解性能分析

表4是3.2節(jié)中不同規(guī)模數(shù)據(jù)求解結(jié)果的效率對比，其中當(dāng)較小規(guī)模數(shù)據(jù)設(shè)置為表3 的第3 行參數(shù)時(shí)取得最優(yōu)解5 的百分比為60%；參數(shù)為中等規(guī)模第3 行數(shù)據(jù)時(shí)，取得最優(yōu)解7的百分比為76%；當(dāng)參數(shù)設(shè)置為較大規(guī)模第3 行數(shù)據(jù)時(shí)取得理論最優(yōu)解10的百分比為42%。

表4 本文算法對三種規(guī)模數(shù)據(jù)在100次運(yùn)行下的求解性能Tab.4 Solution performance of the proposed algorithm on data with three scales under 100 runs

從表4 中可以看出，在迭代次數(shù)和種群規(guī)模適中的情況下，不管大小規(guī)模的初始數(shù)據(jù)在本文設(shè)計(jì)的優(yōu)化方法的計(jì)算下都可以多次得到理論最優(yōu)解，并且得到最優(yōu)解的規(guī)模的平均值都已經(jīng)非常接近最優(yōu)解，標(biāo)準(zhǔn)差也非常小，表明本文設(shè)計(jì)的遺傳算法，在種群規(guī)模適中的情形下，可以得到非常優(yōu)質(zhì)的遺傳進(jìn)化效果。

圖5 是對應(yīng)于圖4 的100 次運(yùn)行的適應(yīng)度波動曲線，由此圖5 可以看出適應(yīng)度一直在最優(yōu)適應(yīng)度附近波動，表明本算法有較高的概率可以求得精確最優(yōu)解或非常接近最優(yōu)解的值。所以，本文所建立的數(shù)學(xué)模型及設(shè)計(jì)的遺傳算法是穩(wěn)定和實(shí)用的，對汽配件噴涂順序問題的優(yōu)化效果顯著。

圖5 100次運(yùn)行適應(yīng)度波動曲線Fig.5 Fitness fluctuation curve of 100 runs

本文的數(shù)學(xué)模型及遺傳算法對更大規(guī)模的汽配件噴涂順序問題仍然是有效和實(shí)用的，限于篇幅，這里不再論述。

4 結(jié)語

本文借鑒TSP 的建模和求解思路，建立了汽配件噴涂順序問題的數(shù)學(xué)模型，設(shè)計(jì)了針對性和實(shí)用性強(qiáng)的遺傳算法來求解，通過實(shí)驗(yàn)數(shù)據(jù)的驗(yàn)證，求解結(jié)果完全能滿足實(shí)際的生產(chǎn)要求，對企業(yè)減少生產(chǎn)成本、提高生產(chǎn)效率具有很好的指導(dǎo)意義。

本文的數(shù)學(xué)模型及遺傳算法仍然適用于數(shù)據(jù)規(guī)模更大的汽配件噴涂問題，還可以推廣應(yīng)用于其他企業(yè)生產(chǎn)作業(yè)調(diào)度［16］等問題。但是由于實(shí)際生產(chǎn)實(shí)踐中汽配件噴涂問題的復(fù)雜性，本文的方法還有不足之處，有待今后繼續(xù)進(jìn)行研究完善。如果綜合考慮到大規(guī)模汽配件噴涂時(shí)放置汽配件的支架數(shù)目對汽配件噴涂順序的影響，如果動態(tài)調(diào)度配件種類顏色以及汽配件數(shù)目，建立的模型將更加有實(shí)際意義。