基于貪婪元胞遺傳算法的工序排序優(yōu)化問題*

鄧燕蘭，熊菊霞，鄭宏宇，姚光磊

（廣西民族大學(xué)數(shù)學(xué)與物理學(xué)院，廣西南寧530006）

0 引言

計算機輔助工藝設(shè)計(Computer Aided Process Planning, CAPP)在計算機工藝規(guī)劃等方面有重要的應(yīng)用。[1]CAPP 主要分為三步：第一，特征識別，即對零件的特征進行分類和識別；[2]第二，確定提取出來的特征的加工操作和加工資源；[3]第三，在設(shè)計和制造實踐的條件約束下，確定加工成本最低的操作順序及其對應(yīng)的加工資源。[4]工序排序優(yōu)化問題屬于第三步，在已知加工特征,及其每個特征的加工操作和候選加工資源的基礎(chǔ)上，通過規(guī)劃得到最優(yōu)加工方案。它以最小化總成本為目標(biāo)；以確定滿足優(yōu)先關(guān)系約束的加工工序的順序，以及每個加工工序使用的加工資源為主要任務(wù)。

工序排序優(yōu)化問題的可行方案包括可行工序序列(Feasible Operation Sequence, FOS),及FOS 中每個工序?qū)?yīng)使用的機床資源、刀具資源和進刀方向(Tool Approach Direction, TAD)。工序的排序，候選加工資源的選擇是相互聯(lián)系、相互制約的，因此工序排序優(yōu)化問題已被證明是一類具有NP-hard 性質(zhì)的組合優(yōu)化問題。[5]它的求解方法主要分為兩類：一類是精確方法，主要包括分枝定界法[6]和線性規(guī)劃法[7]；另一類是近似方法。近幾年來隨著智能優(yōu)化算法的發(fā)展，很多專家和學(xué)者都開始利用智能優(yōu)化算法求解組合優(yōu)化問題。[8]針對工序排序的優(yōu)先級限制，Li等人[9]提出了求解工序排序優(yōu)化問題的混合遺傳算法和模擬退火算法，使用優(yōu)先約束調(diào)整算法對交叉和變異后生成的不可行解進行修復(fù)。Huang 等人[10]將圖論與矩陣?yán)碚撓嘟Y(jié)合，提出了一種混合圖遺傳算法，采用啟發(fā)式算法將變異算子生成的不可行方案調(diào)整到可行域。Yun 等人[11]提出了基于拓撲排序(TS)的遺傳算法，利用優(yōu)先關(guān)系的有向無環(huán)圖生成FOS，有效處理了初始種群加工工序的優(yōu)先關(guān)系約束問題。Su 等人[4]提出了求解工序排序優(yōu)化問題的改進遺傳算法(ESGA)，設(shè)計了使交叉后染色體仍然滿足優(yōu)先關(guān)系約束的交叉算子，在迭代過程中保持了加工方案的可行性。竇建平等人[12]提出基于可行工序序列的遺傳算法(FOSOGA)，設(shè)計了保持加工方案可行性的交叉算子和變異算子。除此之外，也有很多其他的算法應(yīng)用在工序排序優(yōu)化問題的求解中，比如Guo等人[13]提出了求解工序排序優(yōu)化問題的粒子群算法(PSO)，Hu 等人[14]提出了求解工序排序優(yōu)化問題的蟻群算法(ACO)等。

元胞遺傳算法(CGA)是將遺傳算法(GA)和元胞自動機相結(jié)合而形成的一種新的算法，利用元胞自動機的鄰域結(jié)構(gòu)實現(xiàn)遺傳算法的選擇操作，使其更符合現(xiàn)實世界的生物進化特點，通過重復(fù)的局部相互作用，實現(xiàn)全局計算。[15]CGA 算法在組合優(yōu)化問題中具有廣泛的應(yīng)用，例如：旅行商問題[16]、無線電能傳輸網(wǎng)路徑尋優(yōu)問題[17]、柔性車間調(diào)度問題[18]等。但是，目前CGA 算法在工序排序優(yōu)化問題上的應(yīng)用還很少。本文在CGA 算法的基礎(chǔ)上引入拓撲排序算法(TS)、貪婪算法和精英個體保留策略，提出一種求解工序排序優(yōu)化問題的貪婪元胞遺傳算法(GCGA)，從而有效地解決工序排序優(yōu)化問題。

GCGA 算法與現(xiàn)有求解工序排序優(yōu)化問題的遺傳算法相比，其新穎之處主要在于：將CGA 算法應(yīng)用于工序排序優(yōu)化問題的求解，通過元胞自動機的鄰域結(jié)構(gòu)避免陷入局部最優(yōu)；引入貪婪算法生成初始種群的加工資源，降低初始種群中染色體的總成本；分別在交叉和變異后設(shè)置精英個體保留策略，避免劣解進入種群。

1 工序排序優(yōu)化問題

1.1 問題描述

工序排序優(yōu)化問題涉及加工工序排序、機床選擇、刀具選擇和TAD 選擇四個方面。加工工序排序受到優(yōu)先關(guān)系的約束，其約束可以用有向無環(huán)圖來描述，一般稱此有向無環(huán)圖為工序優(yōu)先圖，如圖1 為案例ANC-101 的工序優(yōu)先圖。[4]由于有向圖在運算時不方便使用，所以本文使用優(yōu)先矩陣來表示工序的優(yōu)先關(guān)系。

圖1 ANC-101 的工序優(yōu)先圖

機床、刀具和TAD 的選擇受到實際制造生產(chǎn)的約束，只能從候選資源中進行選擇。選擇不同的加工資源會產(chǎn)生不同的加工成本，具體的加工成本分為五部分：機床成本、刀具成本、機床變換成本、裝夾變換成本和刀具變換成本。產(chǎn)生上述變換成本的情況由表1～3 所示。

表1 機床變換條件

表2 裝夾變換條件

表3 刀具變換條件

由表1～3 可以看出，在連續(xù)兩次加工中使用不同的機床，將會產(chǎn)生機床變換成本；在連續(xù)兩次加工中使用不同的機床或者不同的TAD，將會產(chǎn)生裝夾變換成本；在連續(xù)兩次加工中使用不同的機床或者不同的刀具，將會產(chǎn)生刀具變換成本。因此，最小化總成本意味著最優(yōu)加工工序序列的機床、刀具和TAD 的變換次數(shù)較少。[19]

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

工序排序優(yōu)化問題的加工成本包括：機床成本、刀具成本、機床變換成本、裝夾變換成本和刀具變換成本。為計算成本引入表4 的符號定義，具體的計算公式如下。

表4 符號定義

總的機床成本，即所有加工工序所使用的機床成本之和，記為：TMC。工序數(shù)量為：N。

總的刀具成本，即所有加工工序所使用的刀具成本之和，記為：TTC。

總的機床變換成本記為：TMCC，機床變換次數(shù)記為：NMC。

總的裝夾變換成本記為：TSCC，裝夾變換次數(shù)記為：NSC。

總的刀具變換成本記為：TTCC，刀具變換次數(shù)記為：NTC。

總成本記為：TC，成本的權(quán)重分別為：w1,w2,w3,w4,w5。

2 貪婪元胞遺傳算法(GCGA)

貪婪元胞遺傳算法(GCGA)在元胞遺傳算法的基礎(chǔ)上，針對工序排序優(yōu)化問題的特點，使用拓撲排序算法(TS)生成初始種群的可行工序序列(FOS)，引入貪婪算法生成初始FOS 的加工資源，并且使用結(jié)合精英個體保留策略的交叉算子和變異算子來保持解的可行性和避免劣解進入解空間。

2.1 種群初始化

工序排序優(yōu)化問題的可行方案包括FOS 及其對應(yīng)的加工資源，加工工序使用整數(shù)編碼方式進行編碼，加工資源使用對應(yīng)編號表示，表5 給出了案例ANC-101 的一個最優(yōu)方案。初始種群的產(chǎn)生可分為兩個方面：FOS 的生成和加工資源的生成。

表5 ANC-101 最優(yōu)解

2.1.1 FOS 的生成

為了方便計算機計算，本文使用優(yōu)先矩陣表示加工工序的優(yōu)先關(guān)系。優(yōu)先矩陣由0 和1 組成，若第i行第j列的值為1，則代表工序i需要在工序j之后執(zhí)行，否則工序i和工序j無優(yōu)先關(guān)系。因此，整行全部為0 的工序表示此工序不需要在其他工序之后操作，可以選擇此工序作為第一個操作工序。當(dāng)執(zhí)行完第一個操作工序之后，原來需要在此工序之后執(zhí)行的操作就不再受此工序的約束，即可以將此列的所有非零值更改為0。使用優(yōu)先矩陣進行工序排序的過程與TS 使用有向圖生成FOS 的過程是類似的。

FOS 的生成步驟如下：

1)通過加工工序的優(yōu)先關(guān)系得到優(yōu)先矩陣。

2)隨機選出一個整行全部為0 的工序i(與之前選擇過的工序不重復(fù))作為當(dāng)前操作的工序。

3)用0 替換第i列的所有值為1 的位置。

4)重復(fù)2)和3)，直到確定所有工序的次序。

下面展示了含有5 個加工工序的可行工序序列的生成示例。

1)生成優(yōu)先矩陣，如圖2(a)所示，此時矩陣第1、2行的值全為0，可隨機選擇工序1 和工序2。

2)若選擇工序1，則將矩陣第1 列的值全更改為0，得到的優(yōu)先矩陣如圖2(b)所示。此時矩陣第1、2 和3 行的值全為0，除去已選擇的工序1，可隨機選擇工序2 和工序3。

3)若選擇工序3，則將矩陣第3 列的值全更改為0，得到的優(yōu)先矩陣如圖2(c)所示。此時矩陣第1、2 和3 行的值全為0，除去已選擇的工序1 和工序3，只有唯一選擇工序2。

4)選擇工序2，并將矩陣第2 列的值全更改為0，得到的優(yōu)先矩陣如圖2(d)所示。此時矩陣第1、2、3 和4 行的值全為0，除去已選擇的工序1、2 和3，只有唯一選擇工序4。

圖2 可行工序序列生成示例的優(yōu)先矩陣

5)選擇工序4，此時只剩唯一選擇工序5，故直接選擇工序5，完成工序排序操作，最后得到的工序為1-3-2-4-5。

2.1.2 加工資源的生成

加工工序的加工資源分為3 個部分：機床、刀具和TAD，每一個工序都有其候選的加工資源，從中選擇不同的加工資源會產(chǎn)生不同的成本。若是從候選資源中隨機選擇加工資源，則得到的總成本會具有較大的隨機性，導(dǎo)致優(yōu)化性能的降低。為此，本文將貪婪算法應(yīng)用于初始FOS 的加工資源的生成，降低初始解的總成本。使用貪婪算法生成FOS 的機床資源的具體步驟如下：

1)選擇第一個操作工序的候選機床中成本最低的機床作為此工序使用的機床。

2)從第二個操作工序開始執(zhí)行以下步驟：

a)選擇當(dāng)前操作工序的候選機床中成本最低的機床Mac1。

b)選擇上一個操作工序使用的機床Mac2。

c)如果Mac2并不是當(dāng)前操作工序的候選機床，或者和Mac1相同，則令當(dāng)前操作工序使用的機床為Mac1。否則執(zhí)行下一步。

d)計算使用Mac1產(chǎn)生的成本C1和使用Mac2產(chǎn)生的成本C2。

e)如果C1＜C2，則令當(dāng)前操作工序使用的機床為Mac1，否則為Mac2。

使用貪婪算法生成FOS 的刀具資源和TAD 的步驟與上述使用貪婪算法生成FOS 的機床資源的步驟是類似的。若是刀具的選擇，則成本的計算公式更改為刀具成本、機床變換成本和刀具變換成本之和；若是TAD 的選擇，則由于TAD 本身不產(chǎn)生成本，因此無需計算成本，直接使用上一次操作工序的TAD，或者在候選資源中隨機選擇。

2.2 交叉和變異

交叉算子和變異算子是遺傳算法的精髓，是影響算法優(yōu)化性能的重要因素。[20]由于工序排序優(yōu)化問題的加工方案分為FOS 和FOS 的加工資源兩部分，所以需要分別對FOS 和FOS 的加工資源進行交叉和變異。本文設(shè)計了結(jié)合文獻[4]提出的交叉算子、文獻[12]提出的變異算子和精英個體保留策略的交叉算子和變異算子，在對FOS 執(zhí)行交叉和變異時能夠保持FOS 的可行性，并且使用精英個體保留策略決定保留的染色體，符合優(yōu)勝劣汰的自然法則。

2.2.1 交叉

針對工序排序優(yōu)化問題，本文先是在保持加工工序的加工資源不變的情況下對加工序列進行雙點交叉，交叉后比較母體和子代染色體的總成本，保留總成本較少的染色體。其次，在保持FOS 不變的情況下，分別使母體FOS 的每個加工工序的加工資源以0.5 的概率變?yōu)榱硪粋€母體的對應(yīng)工序的加工資源，得到新的子代染色體再和母體進行比較，同樣保留總成本較少的染色體。

針對母體P1和P2的FOS 的交叉步驟如下：

1)隨機生成兩個切點k1和k2，同時令Q1=P1,Q2=P2。

2)選擇Q1中位于k1和k2兩切點之間工序Q1(k1:k2)，在P2中找到工序Q1(k1:k2)。

3)以P2中工序Q1(k1:k2)的先后順序重排Q1(k1:k2)，但不改變工序的加工資源，即可得到P1的子代Q1。

4)使用Q2和P1分別替代Q1和P2執(zhí)行第2 步和第3 步，得到P2的子代Q2。

5)分 別 計 算P1、P2、Q1和Q2的 總 成 本S1、S2、T1和T2。

6)如果S1＞T1或S2＞T2，則 令P1=Q1或P2=Q2，否則不保留Q1或Q2。

FOS 進行交叉操作之后得到的子代染色體的加工工序仍然滿足工序優(yōu)先關(guān)系的約束條件，保證了解空間的可行性。此外，針對FOS 的交叉操作不改變加工工序的加工資源，所以子代染色體的機床成本和刀具成本是不變的。但是，加工工序順序的改變可能會使機床變換成本、裝夾變換成本和刀具變換成本發(fā)生改變。所以，為了避免劣解進入解空間，F(xiàn)OS進行交叉操作后再進行精英個體保留策略是非常有必要的。同時，加工資源的選擇也是影響總成本的重要因素，F(xiàn)OS 進行交叉后需要再對加工工序的加工資源進行交叉。針對母體P1和P2的FOS 的加工資源的交叉步驟如下：

1)令Q3=P1,Q4=P2，從母體P1的第一操作工序開始執(zhí)行第二步。

2)生成 隨 機 數(shù)r，若r＞0.5，則選擇P2對應(yīng)工序的加工資源作為Q3的加工資源。

3)對所有的加工工序執(zhí)行完第2 步后，即可得到P1的 子代Q3。

4)令Q4和P1分別替代Q3和P2執(zhí) 行第2 步，得到P2的 子代Q4。

5)分 別 計 算P1、P2、Q3和Q4的 總 成 本S1、S2、T3和T4。

6)如果S1＞T3或S2＞T4，則 令P1=Q3或P2=Q4，否則不保留Q3或Q4。

2.2.2 變異

為了保持FOS 的可行性，使用結(jié)合TS 的雙點變異。同時，在對FOS 進行變異操作之后進行與交叉操作類似的精英個體保留策略。針對FOS 加工工序的加工資源的變異操作，以0.5 概率將原加工資源替換為隨機選擇的候選資源中的加工資源。對母體P的變異操作的具體步驟如下：

1)隨機生成兩個切點k1和k2，同時令Q=P。

2)選擇Q中位于k1和k2兩切點之間工序Q(k1:k2)，生成工序Q(k1:k2)的優(yōu)先矩陣。

3)按照2.1.1 中生成FOS 的步驟生成工序Q(k1:k2)的新次序并取代舊次序，加工資源不變。

4)分別計算P和Q的總成本S和T。

5)如果S＞T，則令P=Q，否則不保留Q。

6)隨機生成兩個切點l1和l2，同時令R=P。

7)對R的兩個切點l1和l2之間的加工序列對應(yīng)的加工資源執(zhí)行以下步驟。

a)生成隨機數(shù)r，若r＜0.5，則不改變當(dāng)前工序的加工資源，否則執(zhí)行下一步。

b)隨機選擇候選資源中的加工資源替換當(dāng)前工序的加工資源。

8)得到P的子代R，再計算P和R的總成本S和Y。

9)如果S＞Y，則令P=R，否則不保留R。

2.3 GCGA 的流程

貪婪元胞遺傳算法(GCGA)在二維空間中對染色體進行遺傳操作，即將種群中的每個染色體放置在一個二維網(wǎng)格中，然后對每一個染色體及其最優(yōu)的鄰居染色體進行交叉和變異操作。在元胞自動機模型中，常用的2 維元胞自動機的鄰居類型有：von Neumann 型、Moore 型以及擴展的Moore 型[21]，如圖3所示。本文所使用的鄰居類型為Moore 型，一共有8個鄰居。

圖3 2 維元胞自動機的鄰居類型

圖4 為GCGA 算法的流程圖，其具體步驟如下：

圖4 GCGA 算法的流程圖

1)輸入加工工序的優(yōu)先矩陣及其候選加工資源，可選機床的成本、可選刀具的成本、機床、刀具和裝夾變換一次的成本，交叉概率和變異概率，種群規(guī)模和最大迭代次數(shù)。

2)初始化種群中染色體的FOS。

3)初始化FOS 的加工資源。

4)計算種群中每個染色體的總成本。

5)當(dāng)?shù)螖?shù)小于最大迭代次數(shù)時，執(zhí)行以下步驟:

a)對種群中的每一個染色體，選擇其最優(yōu)的鄰居染色體組成母體。

b)生成隨機數(shù)，如果隨機數(shù)小于交叉概率，則對母體的FOS 執(zhí)行交叉操作。同時對母體的FOS 的加工資源執(zhí)行交叉操作。

c)生成隨機數(shù)，如果隨機數(shù)小于變異概率，則對母體執(zhí)行變異操作。

d)計算當(dāng)前種群最優(yōu)染色體并保存。

3 實驗分析

3.1 實驗參數(shù)

為驗證GCGA 的優(yōu)化性能，實驗采用文獻[4]及文獻[9-14]共同使用的案例ANC-101。ANC-101為具有20 個加工工序的工序排序優(yōu)化問題，其工序優(yōu)先關(guān)系如圖1 所示，機床資源如表6 所示，刀具資源如表7 所示，特征和操作信息如表8 所示。機床、裝夾和刀具變換一次的成本分別為160、100 和20，5 種成本的權(quán)值均為1。根據(jù)文獻[4]和文獻[9-14]使用的種群規(guī)模和最大迭代次數(shù)，把種群規(guī)模設(shè)置為144，最大迭代次數(shù)設(shè)置為200。實驗獨立重復(fù)進行10 次。

表6 機床信息

表7 刀具信息

表8 ANC-101 的特征、操作、TADS 和制造資源

實驗條件：MATLAB 2018b，處理器為Intel(R)Core(TM) i7-10510U CPU @1.80 GHz 2.30 GHz，內(nèi)存為12 G。

3.2 實驗結(jié)果及分析

經(jīng)過10 次獨立重復(fù)實驗，得到如下實驗結(jié)果：在10 次獨立重復(fù)實驗中，每一次均能得到最優(yōu)值2530，表5 為其得到的最優(yōu)方案，并且最早收斂代數(shù)為9，圖5 為其進化曲線。由此可見，GCGA 算法具有較高的穩(wěn)定性。

圖5 進化曲線

為了驗證GCGA 算法的優(yōu)化性能，將GCGA 算法與文獻[4]提出的ESGA 算法、文獻[9]提出的混合遺傳算法和模擬退火算法、文獻[10]提出的混合圖遺傳算法、文獻[11]提出的TSGA 算法、文獻[12]提出的FOSOGA 算法、文獻[13]提出的PSO 算法和文獻[14]提出的ACO 算法等7 種算法進行對比，10 次獨立重復(fù)實驗得到的總成本的最優(yōu)值、最差值、平均值和最早收斂代數(shù)的對比結(jié)果如表9 所示。

由表9 可以看出：在上述8 種算法中，只有文獻[4]提出的ESGA 算法、文獻[12]提出的FOSOGA 算法、文獻[14]提出的ACO 算法和本文提出的GCGA算法獲得了最優(yōu)值2530，其余的算法獲得的最優(yōu)值都較大。并且，本文提出的算法獲得的平均值和最差值都優(yōu)于其余的7 種算法。同時，在10 次獨立重復(fù)實驗中，最早收斂代數(shù)為9，比文獻[12]提出的FOSO?GA 的最早收斂代數(shù)38 要早。

表9 8 種算法的計算結(jié)果

實驗數(shù)據(jù)結(jié)果充分表明：GCGA 算法在求解工序排序優(yōu)化時具有較高的穩(wěn)定性、收斂速度及收斂精度。

4 結(jié)論

為了解決CAPP 中的工序排序優(yōu)化問題，本文提出貪婪元胞遺傳算法(GCGA)。該算法在元胞遺傳算法的基礎(chǔ)上，引入元胞自動機的Moore 型鄰域結(jié)構(gòu)避免陷入局部最優(yōu)；利用優(yōu)先矩陣實現(xiàn)拓撲排序算法，確保初始種群中每個染色體的加工順序滿足優(yōu)先關(guān)系的約束；引入貪婪算法生成初始種群的加工資源，提高初始方案的質(zhì)量；設(shè)計結(jié)合精英個體保留策略的交叉算子和變異算子，保證解空間在迭代過程中的可行性。GCGA 算法能夠有效解決工序排序優(yōu)化問題，能為實際工業(yè)生產(chǎn)提供豐富的理論指導(dǎo)。