鄭子儀

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

關(guān)鍵詞：遺傳算法；模擬退火算法；工業(yè)刀具；組合優(yōu)化問題；工業(yè)軟件

中圖分類號(hào)：TP301.6；TP18? ? ?文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2023）31-0128-04

開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）

0 引言

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

1 基于改進(jìn)混合遺傳算法的工業(yè)刀具組合優(yōu)化

1.1 刀具組合問題參數(shù)定義

本小節(jié)對(duì)其中的相關(guān)參數(shù)和變量的定義與解釋如下：

[N]：生產(chǎn)工單總數(shù)；

[i]：生產(chǎn)工單的編號(hào)（[i=1，2…N]）；

[ni]：表示[i]號(hào)生產(chǎn)工單需要生產(chǎn)的工件總數(shù)；

[qi]：表示[i]號(hào)生產(chǎn)工單中單個(gè)工件的報(bào)價(jià)；

[K]：刀具的種類總數(shù)；

[B]：刀具的數(shù)量總數(shù)；

[j]：刀具的編號(hào)（[j=1，2…B]）；

[pj]：表示[j]號(hào)刀具的采購(gòu)價(jià)格；

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

[aj]：表示[j]號(hào)刀具的初始?jí)勖▎挝唬篬%]） ；

[mj]：表示[j]號(hào)刀具的可修磨次數(shù)，若是不可修磨刀具，則[mj=0]；

[tj]：表示[j]號(hào)刀具進(jìn)行單次修磨恢復(fù)的壽命，若是不可修磨刀具，則[tj=0]；

[cj]：表示[j]號(hào)刀具進(jìn)行單次修磨的費(fèi)用，若是不可修磨刀具，則[cj=0]；

[dik]：表示生產(chǎn)一個(gè)[i]號(hào)生產(chǎn)工單的工件所需[k]類刀具的壽命（%）；

[gij]：0、1變量，刀具組合優(yōu)化的決策變量，當(dāng) [gij]為1時(shí)，表示[j]號(hào)刀具被用于[i]號(hào)生產(chǎn)工單的生產(chǎn)活動(dòng)；當(dāng) [gij]為0時(shí)，表示[j]號(hào)刀具未被用于[i]號(hào)生產(chǎn)工單的生產(chǎn)活動(dòng)。

1.2 編碼設(shè)計(jì)

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

1.3 目標(biāo)函數(shù)、適應(yīng)度函數(shù)及約束條件

目標(biāo)函數(shù)[AG]是優(yōu)化的目標(biāo)，而適應(yīng)度函數(shù)值[FG]是描述種群個(gè)體表現(xiàn)優(yōu)劣的指標(biāo)，GA的本質(zhì)就是通過適應(yīng)度函數(shù)值的大小來(lái)對(duì)種群個(gè)體實(shí)現(xiàn)“自然選擇、優(yōu)勝劣汰”。適應(yīng)度函數(shù)直接決定搜索群體的進(jìn)化行為，適應(yīng)度函數(shù)值越大，個(gè)體的表現(xiàn)就越好，其基因遺傳給下一代的可能性就越大。IHGA的目標(biāo)函數(shù)[AG]如式（1） 所示，其中各個(gè)參數(shù)的計(jì)算如式（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）

由于目標(biāo)函數(shù)可能出現(xiàn)負(fù)數(shù)情況，不能直接將目標(biāo)函數(shù)作為適應(yīng)度函數(shù)，需要做目標(biāo)函數(shù)到適應(yīng)度函數(shù)的變換，該過程稱為標(biāo)定。常見的標(biāo)定方法有線性標(biāo)定、冪律標(biāo)定、窗口技術(shù)等。IGHA進(jìn)行的標(biāo)定如式（4） 所示。

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

目標(biāo)函數(shù)主要為每個(gè)生產(chǎn)工單任務(wù)實(shí)際生產(chǎn)工件數(shù)與單個(gè)工件報(bào)價(jià)的乘積減去消耗的刀具成本。約束條件如式（5） 所示，對(duì)于任意一把刀具，其僅能被一個(gè)生產(chǎn)工單的生產(chǎn)活動(dòng)占用。

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

1.4 選擇算子選擇

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

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

1.5 交叉算子設(shè)計(jì)

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

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

在TCO中，交叉點(diǎn)[d1與交叉點(diǎn)d2]都是隨機(jī)生成的，而WRTCO對(duì)交叉點(diǎn)[d1與交叉點(diǎn)d2]的生成進(jìn)行了限定，限定條件如式（7） 所示，交叉點(diǎn)[d1]限定在某個(gè)生產(chǎn)工單編碼的開頭，交叉點(diǎn)[d2]限定在該生產(chǎn)工單編碼的結(jié)尾，從而達(dá)到整個(gè)生產(chǎn)工單整體編碼交叉重組的效果。實(shí)例如圖3所示，此時(shí)交叉點(diǎn)[d1=1]，交叉點(diǎn)[d2=B]，1號(hào)基因到B號(hào)基因?qū)崿F(xiàn)整體交叉重組，其代表的實(shí)際意義為1號(hào)生產(chǎn)工單的兩個(gè)編碼方案實(shí)現(xiàn)交換重組，從而獲得子代染色體。

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

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

1.6 變異算子設(shè)計(jì)

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

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

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

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

[Ps=1，F(xiàn)G'>FGe- FG-FG'T，F(xiàn)G'≤FG]? ?（8）

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

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

在一般的搜索問題中，常見的迭代終止條件有多種，例如設(shè)置最大迭代時(shí)間，即給算法設(shè)置一個(gè)運(yùn)行時(shí)間閾值，當(dāng)算法運(yùn)行時(shí)間到達(dá)閾值運(yùn)行時(shí)間時(shí)，即便此時(shí)算法迭代仍然未結(jié)束，強(qiáng)行終止算法的運(yùn)行并輸出此時(shí)的最優(yōu)個(gè)體作為輸出結(jié)果；設(shè)置優(yōu)化目標(biāo)閾值，根據(jù)對(duì)問題的具體分析，預(yù)先設(shè)置一個(gè)優(yōu)化目標(biāo)閾值，當(dāng)某個(gè)個(gè)體達(dá)到該目標(biāo)時(shí)停止算法運(yùn)行并輸出結(jié)果；設(shè)置迭代次數(shù)閾值，當(dāng)算法迭代次數(shù)達(dá)到該閾值時(shí)，停止實(shí)驗(yàn)并輸出結(jié)果。IHGA在終止溫度條件基礎(chǔ)上，使用雙閾值終止條件，設(shè)置最優(yōu)解不變次數(shù)閾值[M1]和迭代次數(shù)閾值[M2]。當(dāng)連續(xù)超過[M1]次迭代最優(yōu)解都不變時(shí)，停止迭代并輸出最優(yōu)個(gè)體[G*]和最優(yōu)目標(biāo)函數(shù)值[A*]，避免多余的運(yùn)算；或者當(dāng)?shù)螖?shù)達(dá)到閾值[M2]時(shí)停止實(shí)驗(yàn)，避免過長(zhǎng)的實(shí)驗(yàn)時(shí)間。

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* ]

算法輸入為算法所需的一系列參數(shù)和數(shù)據(jù)，輸出為最優(yōu)個(gè)體與最優(yōu)目標(biāo)函數(shù)值，每個(gè)步驟具體描述如下：

步驟1：隨機(jī)初始化種群，對(duì)每個(gè)個(gè)體進(jìn)行合法性檢查以確保每個(gè)個(gè)體合法，計(jì)算每個(gè)個(gè)體的目標(biāo)函數(shù)值和適應(yīng)度函數(shù)值。

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

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

步驟4：基于IBFMO變異算子進(jìn)行變異操作，更新種群，同時(shí)基于動(dòng)態(tài)變異概率更新規(guī)則更新變異概率。

步驟5：找出新種群的最優(yōu)個(gè)體與原最優(yōu)個(gè)體相比，若是新種群最優(yōu)個(gè)體好于原最優(yōu)個(gè)體，則更新最優(yōu)個(gè)體和最優(yōu)目標(biāo)函數(shù)值，否則基于Metropolis準(zhǔn)則進(jìn)行判斷，同時(shí)記錄全局最優(yōu)解和全局目標(biāo)函數(shù)值。

步驟6：通過終止溫度條件和雙閾值結(jié)束條件進(jìn)行結(jié)束判斷，若未滿足結(jié)束條件，則回到步驟2繼續(xù)執(zhí)行。

步驟7：輸出最優(yōu)個(gè)體和最優(yōu)目標(biāo)函數(shù)值。

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

2.1 數(shù)據(jù)集準(zhǔn)備

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

1號(hào)組數(shù)據(jù)中部分刀具信息如表2所示，每行數(shù)據(jù)記錄了一把刀具的基本信息。以1號(hào)刀具為例，該刀具屬于Ⅰ類刀具，每把該類刀具的采購(gòu)價(jià)是15.5元，初始?jí)勖鼮?00%，且該刀具屬于不可修磨刀具。

2.2 參數(shù)設(shè)置

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

2.3 算法有效性驗(yàn)證

為了驗(yàn)證IHGA算法的有效性，本小節(jié)設(shè)置算法有效性實(shí)驗(yàn)。本研究使用上述8個(gè)數(shù)據(jù)組進(jìn)行，每個(gè)數(shù)據(jù)組分別使用隨機(jī)組合法、傳統(tǒng)遺傳算法和IHGA進(jìn)行10次獨(dú)立重復(fù)實(shí)驗(yàn)，記錄8次實(shí)驗(yàn)的平均目標(biāo)函數(shù)值、最優(yōu)目標(biāo)函數(shù)值和最差目標(biāo)函數(shù)值，形成的結(jié)果如表3所示。在同一個(gè)實(shí)驗(yàn)組內(nèi)部，相比于隨機(jī)組合算法，傳統(tǒng)遺傳算法和IHGA在三個(gè)平均目標(biāo)函數(shù)值、最優(yōu)目標(biāo)函數(shù)值、最差目標(biāo)函數(shù)值三個(gè)指標(biāo)上都有一定的提升，且IHGA的提升效果最大。

以后實(shí)驗(yàn)組的平均目標(biāo)函數(shù)值為指標(biāo)，建立的分組柱狀圖如圖5所示。從中可以看到，在每個(gè)數(shù)據(jù)組中，隨機(jī)組合算法、傳統(tǒng)遺傳算法和IHGA在平均目標(biāo)函數(shù)值上的表現(xiàn)呈一個(gè)遞增的狀態(tài)，IHGA表現(xiàn)良好。同時(shí)通過觀察可以發(fā)現(xiàn)，相比于刀具數(shù)目和種類較少的3、4數(shù)據(jù)組，IHGA在刀具數(shù)目和種類更充裕的6、8數(shù)據(jù)組提升更明顯，這是由于在算法進(jìn)行時(shí)的種群多樣性更強(qiáng)，更容易出現(xiàn)優(yōu)良的個(gè)體，提升目標(biāo)函數(shù)值。

3 總結(jié)與展望

基于工業(yè)刀具組合優(yōu)化問題，文章將遺傳算法和模擬退火算法進(jìn)行結(jié)合，對(duì)其中的交叉算子、變異算子、變異概率和結(jié)束條件進(jìn)行優(yōu)化，提出了一種改進(jìn)混合遺傳算法。提升了傳統(tǒng)遺傳算法的性能，降低了局部收斂的概率。實(shí)驗(yàn)結(jié)果表明，該算法具有良好的可行性。

未來(lái)預(yù)計(jì)將其他改進(jìn)方法應(yīng)用于本算法，進(jìn)一步提升算法的性能，并在工業(yè)生產(chǎn)中繼續(xù)應(yīng)用與檢驗(yàn)。

參考文獻(xiàn)：

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

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

[3] 李書全，孫雪，孫德輝，等.遺傳算法中的交叉算子的述評(píng)[J].計(jì)算機(jī)工程與應(yīng)用，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ī)理研究[J].同濟(jì)大學(xué)學(xué)報(bào)（自然科學(xué)版），2004，32（6）：802-805.

【通聯(lián)編輯：梁書】