基于改進混合遺傳算法的工業刀具組合優化算法

鄭子儀

摘要：工業刀具被廣泛用于CNC制造加工中，但在實際生產過程中存在由于刀具組合不當而導致刀具閑置、利用率不高的問題。為了提升刀具利用率，降低刀具成本，文章提出一種基于改進混合遺傳算法的工業刀具組合優化算法，對生產線刀具組合進行優化。實驗結果表明，該算法在數據集上表現良好，并且較其他算法性能有所提升。

關鍵詞：遺傳算法；模擬退火算法；工業刀具；組合優化問題；工業軟件

中圖分類號：TP301.6；TP18? ? ?文獻標識碼：A

文章編號：1009-3044（2023）31-0128-04

開放科學（資源服務）標識碼（OSID）

0 引言

組合優化問題是一類在離散狀態下求極值的最優化問題[1]，本文所述刀具組合優化問題屬于其中一類。學術界常用啟發式算法解決組合優化問題，如禁忌搜索算法、粒子群算法等。在本文討論的問題中，某家發動機制造廠擁有多個生產車間，可以同時進行不同工件的生產。本文提出一種基于改進混合遺傳算法（Improved Hybrid Genetic Algorithm，IHGA） 的工業刀具組合優化算法，在多生產工單的生產需求的背景下，對每個生產工單使用的刀具組合進行優化，降低刀具的閑置浪費，提升刀具利用率，使得整體上達到最大的經濟效益。

1 基于改進混合遺傳算法的工業刀具組合優化

1.1 刀具組合問題參數定義

本小節對其中的相關參數和變量的定義與解釋如下：

[N]：生產工單總數；

[i]：生產工單的編號（[i=1，2…N]）；

[ni]：表示[i]號生產工單需要生產的工件總數；

[qi]：表示[i]號生產工單中單個工件的報價；

[K]：刀具的種類總數；

[B]：刀具的數量總數；

[j]：刀具的編號（[j=1，2…B]）；

[pj]：表示[j]號刀具的采購價格；

[kj]：表示[j]號刀具的所屬種類[（kj=1，2…K）]；

[aj]：表示[j]號刀具的初始壽命（單位：[%]） ；

[mj]：表示[j]號刀具的可修磨次數，若是不可修磨刀具，則[mj=0]；

[tj]：表示[j]號刀具進行單次修磨恢復的壽命，若是不可修磨刀具，則[tj=0]；

[cj]：表示[j]號刀具進行單次修磨的費用，若是不可修磨刀具，則[cj=0]；

[dik]：表示生產一個[i]號生產工單的工件所需[k]類刀具的壽命（%）；

[gij]：0、1變量，刀具組合優化的決策變量，當 [gij]為1時，表示[j]號刀具被用于[i]號生產工單的生產活動；當 [gij]為0時，表示[j]號刀具未被用于[i]號生產工單的生產活動。

1.2 編碼設計

編碼是遺傳算法（Genetic Algorithm，GA） 的重要組成部分，編碼實現了組合優化問題解空間到算法搜索空間的轉換。IHGA采用二進制編碼，一個染色體G代表一種刀具組合方案。每條染色體G包含N段，代表N個生產工單，每段包含B個基因，代表B把刀具。每個基因使用0、1編碼，代表該生產工單是否使用該刀具進行生產， 1代表使用，0代表不使用。實例如圖1所示，該實例中有3個工單，10把刀具，其中1號生產工單使用1號、4號刀具進行生產，2號生產工單使用2號、9號和10號刀具進行生產，3號生產工單使用3號和8號刀具進行生產。

1.3 目標函數、適應度函數及約束條件

目標函數[AG]是優化的目標，而適應度函數值[FG]是描述種群個體表現優劣的指標，GA的本質就是通過適應度函數值的大小來對種群個體實現“自然選擇、優勝劣汰”。適應度函數直接決定搜索群體的進化行為，適應度函數值越大，個體的表現就越好，其基因遺傳給下一代的可能性就越大。IHGA的目標函數[AG]如式（1） 所示，其中各個參數的計算如式（2） 和式（3） 所示。

[AG=i=1Nxi×qi-j=1Bpj+mj×cj×zj]? （1）

[xi=mink=1…Kj=1Kgij×aj+mj×tj×fdik]? （2）

[f=1，若cj=k0，若cj≠k ，zj=1，若cj=i=1Ngij>00，若cj=i=1Ngij=0]? （3）

由于目標函數可能出現負數情況，不能直接將目標函數作為適應度函數，需要做目標函數到適應度函數的變換，該過程稱為標定。常見的標定方法有線性標定、冪律標定、窗口技術等。IGHA進行的標定如式（4） 所示。

[FG=AG，? ? 若G滿足約束條件0，? ? ? ? ? ? 若G不滿足約束條件]? ? （4）

目標函數主要為每個生產工單任務實際生產工件數與單個工件報價的乘積減去消耗的刀具成本。約束條件如式（5） 所示，對于任意一把刀具，其僅能被一個生產工單的生產活動占用。

[i=1Ngij≤1，?j]? ? ? （5）

1.4 選擇算子選擇

選擇操作是按照預定的選擇算子，隨機從父代中挑選一些適應度函數值大、表現良好的個體生存下來，其余的個體則被淘汰的過程。常見的選擇算子有輪盤賭選擇算子（Roulette Wheel Selection，RWS） 、排序選擇算子等[2]。IHGA使用RWS，其基本原理如式（6） 所示。其中[R（Gi）]表示[Gi]被選擇進下一代的概率，[M]為種群規模。在具體算法實現時，可以隨機生成一個范圍在0至1之間的隨機數[r]，若[0≤r≤R（Gi）]，則[Gi]被選擇進下一代；若[R（Gi）<r<1]，則[Gi]被淘汰。

[R（Gi）=A（Gi）i=1MA（Gi）]? ? （6）

1.5 交叉算子設計

交叉操作是在交叉概率[Pc]下，將選擇的兩條父代染色體按照預設的交叉算子進行重組，從而獲得不同于父代的子代染色體。交叉操作是GA中獲得新染色體的重要操作，不同的交叉算子對于算法性能和效率的影響也不同，常見的交叉算子有兩點交叉算子（Two-point Crossover Operator， TCO） 、有序交叉算子等[3]。IHGA對TCO進行改進，提出一種整體重組兩點交叉算子（Whole Recombination Two-point Crossover Operator，WRTCO） ，并將WRTCO和TCO相結合，應用于IGHA中。

TCO是在兩條父代染色體中，以交叉概率[Pc]選擇兩個固定的交叉點，交換交叉點之間的基因，從而產生兩條新的子代染色體。常規兩點交叉操作如圖2所示，隨機生成的交叉點[d1=4，d2=12]，父代染色體A和B交換4號到12號之間的基因，形成子代染色體C和D。

在TCO中，交叉點[d1與交叉點d2]都是隨機生成的，而WRTCO對交叉點[d1與交叉點d2]的生成進行了限定，限定條件如式（7） 所示，交叉點[d1]限定在某個生產工單編碼的開頭，交叉點[d2]限定在該生產工單編碼的結尾，從而達到整個生產工單整體編碼交叉重組的效果。實例如圖3所示，此時交叉點[d1=1]，交叉點[d2=B]，1號基因到B號基因實現整體交叉重組，其代表的實際意義為1號生產工單的兩個編碼方案實現交換重組，從而獲得子代染色體。

[d1=n×B+1，d2=d1+B-1，其中n=0，1...n-1]? （7）

綜上所述，IHGA使用的交叉算子設計方案如下：首先進行常規雙點交叉操作，以交叉概率[Pc]隨機生成交叉點[d1]與交叉點[d2]，交換交叉點[d1]與交叉點[d2]之間的基因從而獲得子代染色體。若常規雙點交叉操作未發生，則進行整體重組雙點交叉操作，以同樣的交叉概率[Pc]和限定條件（7） 生成交叉點[d1]與交叉點[d2]，交換交叉點[d1]與交叉點[d2]之間基因的獲得子代染色體。同時為了保證染色體的合法性，對于每次交叉產生的子代染色體都要進行合法性檢查。

1.6 變異算子設計

變異操作是模擬生物基因突變產生新特征的過程。在GA中，變異算子作用于選擇和交叉操作后產生的子代染色體，以交叉概率[Pm]使得染色體的某些基因發生變異，從而獲得新染色體。變異操作增強了種群個體的多樣性，但由于變異操作帶有損害種群個體表現的風險以及高變異率會使得GA向隨機搜索算法靠近，[Pm]一般設得較低，過低的[Pm]又會影響種群多樣性。常見的變異算子有位翻轉變異算子（Bit Flipping Mutation Operator，BFMO）） 、交換變異算子、反轉變異算子等。

BFMO是在固定變異概率[Pm]下，對染色體中一個或多個基因進行0、1翻轉變異。IGHA基于實際問題背景，基于提升種群個體多樣性及算法效率的考慮，提出一種改進位翻轉變異算子（Improved Bit Flipping Mutation Operator，IBFMO） 。IBFMO的變異操作如下：在變異概率[Pm]下，首先在每個生產工單基因段隨機選擇一個基因進行變異，若在不同的生產工單基因段選擇了同一基因位，則重新進行選擇。若選擇的基因是0，則將其翻轉為1，且其他生產工單基因段對應位都設置為0；若選擇的基因是1，則將其翻轉為0，在其他生產工單基因段中任選一段，將其對應基因設置為1。同時，IGHA采取動態變異概率[Pm]，初始變異概率為[Pb]，若某次迭代都發生變異，則將變異概率[Pm]增加0.01，最終變異概率[Pl]但不超過閾值[PM]。示例如圖4所示。1號、2號和3號生產工單基因段分別選擇了1號基因位、5號基因和8號基因進行翻轉操作。1號生產工單基因段將1號基因從1翻轉成0，并選擇將2號生產工單基因段1號基因從0翻轉成1；2號生產工單基因段將5號基因從0翻轉成1，并選擇將3號生產工單基因段5號基因從1翻轉成0；3號生產工單基因段將8號基因從1翻轉成0，并選擇將1號生產工單基因段8號基因從0翻轉成1。

1.7 退火過程與終止條件判定

GA具有良好的全局搜索能力和較快的運算速度，但在搜索過程中有概率陷入局部收斂。IGHA將模擬退火算法（Simulated Annealing Algorithm，SAA）與GA結合，通過SAA的Metropolis準則使得算法可以以一定的概率[Ps]接受較差解[4]，使得算法結果跳出局部最優解。概率[Ps]的計算公式如式（8） 所示，在某次迭代過程中，[G]是種群在經過選擇、交叉、變異操作前的最優個體，[G']種群在經過選擇、交叉、變異操作后的最優個體?；贛etropolis準則判斷，若[G']在適應度函數上的表現優于[G]，則接受[G']為當前種群最優解；若[G']在適應度函數上的表現劣于[G]，則以[e- FG-FG'T]的概率接受[G']為當前種群最優解。在溫度[T]值較大時，Metropolis準則判斷能以一個較大的概率接受較差解當作當前種群最優解，能夠有效地跳出局部最優點。同時，為了避免優良解在算法迭代過程中的丟失，設置具備記憶功能的最優個體[G*]，每一次迭代都會對[G*]進行更新，從而盡可能地保留最優個體。

[Ps=1，FG'>FGe- FG-FG'T，FG'≤FG]? ?（8）

基于Metropolis準則判斷過后是降溫過程。初始溫度為[T0]，終止溫度為[Tf]，降溫系數為[r]。IHGA算法使用指數式降溫方法[5]，當前溫度[T]為[T0]，一輪降溫后，當前溫度[T]的變化如式（9） 所示，直至[T]小于終止溫度[Tf]時停止降溫。

[T=T×r]? ? ? ? ? （9）

在一般的搜索問題中，常見的迭代終止條件有多種，例如設置最大迭代時間，即給算法設置一個運行時間閾值，當算法運行時間到達閾值運行時間時，即便此時算法迭代仍然未結束，強行終止算法的運行并輸出此時的最優個體作為輸出結果；設置優化目標閾值，根據對問題的具體分析，預先設置一個優化目標閾值，當某個個體達到該目標時停止算法運行并輸出結果；設置迭代次數閾值，當算法迭代次數達到該閾值時，停止實驗并輸出結果。IHGA在終止溫度條件基礎上，使用雙閾值終止條件，設置最優解不變次數閾值[M1]和迭代次數閾值[M2]。當連續超過[M1]次迭代最優解都不變時，停止迭代并輸出最優個體[G*]和最優目標函數值[A*]，避免多余的運算；或者當迭代次數達到閾值[M2]時停止實驗，避免過長的實驗時間。

1.8 算法完整流程

IHAG算法完整步驟如Alg.1所示。

[Algorithm 1： Improved Hybrid Genetic Algorithm （IHGA） Input： Number of workorder N， matrix of workpiece demand quantity by each workorder NI

， matrix of workpiece quotation by each workorder Q， number of tool kinds K， number of tools B， matrix of purchase price of each tool P， matrix of kind number of each tool KT ， matrix of initial life of each tool AJ， matrix of grinding time of each tool MJ， matrix of life recover per grinding of each tool TJ， matrix of tool demand per workorder D， population size S， matrix of population Gs， crossover probability Pc， mutation probability Pm， mutation probability threshold PM， mutation probability increase limit value W， initial temperature T0， final temperature Tf， cooling rate r， optimal individual? invariant degree threshold M1， iteration threshold M2 Output： Optimal individual G*， optimal objective function value A* 1： Initialize Gs ←Generate H individual G randomly with validity checking

For every G in Gs do

A（G） ， F（G）←Calculate objective function and fitness function end 2： Gs ←Select individual G with RWS for S times and update Gs 3： Gs ←At a probability of PC ， update Gs with WRTCO ，TCO and validity checking 4： Gs ←At a probability of Pm ， update Gs with IBFMO

If continuous iterations without mutation reach W and Pm[ <] PM

Then Pm←Pm + 0.01? Endif 5： G’←Sort and get the best Individual from Gs

If A（G）< A（G’）

Then G←G’

Else judge by Metropolis rule

Endif

If A（G*）< A（G）

Then G*←G’，A* ←A（G’）

Else judge by Metropolis rule

Endif 6： Iteration end judgment by M1 and M2

If not reach end condition

Then goto step2

Endif 7： Output G*，A* ]

算法輸入為算法所需的一系列參數和數據，輸出為最優個體與最優目標函數值，每個步驟具體描述如下：

步驟1：隨機初始化種群，對每個個體進行合法性檢查以確保每個個體合法，計算每個個體的目標函數值和適應度函數值。

步驟2：基于RWS選擇算子進行選擇操作，更新種群。

步驟3：基于WRTCO，TCO交叉算子進行交叉操作，更新種群。

步驟4：基于IBFMO變異算子進行變異操作，更新種群，同時基于動態變異概率更新規則更新變異概率。

步驟5：找出新種群的最優個體與原最優個體相比，若是新種群最優個體好于原最優個體，則更新最優個體和最優目標函數值，否則基于Metropolis準則進行判斷，同時記錄全局最優解和全局目標函數值。

步驟6：通過終止溫度條件和雙閾值結束條件進行結束判斷，若未滿足結束條件，則回到步驟2繼續執行。

步驟7：輸出最優個體和最優目標函數值。

2 實驗與結果分析

2.1 數據集準備

本實驗的數據來源于某工廠的歷史生產數據，為保證實驗的有效性，本文刪除了部分時間久遠的數據和因其他因素導致的異常數據，形成8組數據。以1號數據組為例，如表1所示，1號數據組中總共包括了6個生產工單的相關信息，每行數據記錄了一個生產工單要求生產的工件數目、生產每個工件的消耗刀具壽命情況以及每個工件的報價。以2號生產工單為例，該生產工單要求生產1500個工件，生產每一個該種工件需要消耗0.25%壽命的Ⅱ類刀具，0.5%壽命的Ⅲ類刀具以及0.5%壽命的Ⅳ類刀具，且每個工件的報價是0.35元（其中覆蓋了原料、人力等方面的成本）。

1號組數據中部分刀具信息如表2所示，每行數據記錄了一把刀具的基本信息。以1號刀具為例，該刀具屬于Ⅰ類刀具，每把該類刀具的采購價是15.5元，初始壽命為100%，且該刀具屬于不可修磨刀具。

2.2 參數設置

依據相關文獻研究和問題實際情況對算法參數進行設置，種群規模[M]設定為500，交叉概率[Pc]=0.95，初始變異概率[Pb]=0.05，變異概率增量[?P]=0.01，變異概率閾值[PM]=0.1。在SAA相關參數設置中，初始溫度[T0]=1000，降溫系數[r]=0.99，終止溫度[Tf]=0.1。在中止條件判斷條件設置中，最優解不變次數閾值[M1]=200，迭代次數閾值[M2]=1000。

2.3 算法有效性驗證

為了驗證IHGA算法的有效性，本小節設置算法有效性實驗。本研究使用上述8個數據組進行，每個數據組分別使用隨機組合法、傳統遺傳算法和IHGA進行10次獨立重復實驗，記錄8次實驗的平均目標函數值、最優目標函數值和最差目標函數值，形成的結果如表3所示。在同一個實驗組內部，相比于隨機組合算法，傳統遺傳算法和IHGA在三個平均目標函數值、最優目標函數值、最差目標函數值三個指標上都有一定的提升，且IHGA的提升效果最大。

以后實驗組的平均目標函數值為指標，建立的分組柱狀圖如圖5所示。從中可以看到，在每個數據組中，隨機組合算法、傳統遺傳算法和IHGA在平均目標函數值上的表現呈一個遞增的狀態，IHGA表現良好。同時通過觀察可以發現，相比于刀具數目和種類較少的3、4數據組，IHGA在刀具數目和種類更充裕的6、8數據組提升更明顯，這是由于在算法進行時的種群多樣性更強，更容易出現優良的個體，提升目標函數值。

3 總結與展望

基于工業刀具組合優化問題，文章將遺傳算法和模擬退火算法進行結合，對其中的交叉算子、變異算子、變異概率和結束條件進行優化，提出了一種改進混合遺傳算法。提升了傳統遺傳算法的性能，降低了局部收斂的概率。實驗結果表明，該算法具有良好的可行性。

未來預計將其他改進方法應用于本算法，進一步提升算法的性能，并在工業生產中繼續應用與檢驗。

參考文獻：

[1] PERES F，CASTELLI M.Combinatorial optimization problems and metaheuristics：Review， challenges， design， and development[J].Applied Sciences，2021，11（14）： 6449.

[2] 葛繼科，邱玉輝，吳春明，等.遺傳算法研究綜述[J].計算機應用研究，2008，25（10）：2911-2916.

[3] 李書全，孫雪，孫德輝，等.遺傳算法中的交叉算子的述評[J].計算機工程與應用，2012，48（1）：36-39.

[4] VENKATESWARAN C，RAMACHANDRAN M，KURINJIMALAR R，et al.Application of simulated annealing in various field[J].Materials and Its Characterization，2022，1（1）：1-8.

[5] 陳華根，吳健生，王家林，等.模擬退火算法機理研究[J].同濟大學學報（自然科學版），2004，32（6）：802-805.

【通聯編輯：梁書】