基于改進型遺傳算法的制造資源優(yōu)化配置方法研究

高新勤，荊彥臻，杜景霏

（西安理工大學 機械與精密儀器工程學院，西安 710048）

0 引言

近年來，云制造理念的提出與快速發(fā)展，促使制造業(yè)朝著全球化、智能化的方向邁進了一步。制造資源供需雙方可以充分利用云制造服務平臺進行線上匹配和交易，實現(xiàn)“分散資源集中使用，集中資源分散服務”[1]。但隨著制造資源和相關制造任務分別向著海量化和多元化的趨勢發(fā)展，新的問題應運而生，即如何為制造任務發(fā)起人提供所需的制造資源配置方案，使得最終的配置結(jié)果在某一方面或多個方面達到最優(yōu)。

大量學者對遺傳算法求解資源配置問題進行了研究。尹勝等提出了多任務和多目標的外協(xié)加工資源優(yōu)化配置模型，并運用遺傳算法對模型進行求解[2]。Kundakci and Kulak針對作業(yè)車間中的工人數(shù)量、設備數(shù)量等隨機動態(tài)事件，提出了運用混合遺傳算法解決動態(tài)作業(yè)車間的調(diào)度問題，并通過實例加以驗證[3]。袁慶霓等提出一種資源-任務關系矩陣編碼方式的遺傳算法，約束了制造資源間的關聯(lián)性[4]。張雪艷提出了一種自適應交叉率和變異率的遺傳算法，通過該方法優(yōu)化了算法的運算過程[5]?？偟膩碚f，已有大多數(shù)研究對遺傳算法運算過程的復雜性考慮較少。此外，云制造仍處于初期階段，在資源優(yōu)化配置的數(shù)學建模、求解算法設計等方面還存在諸多問題，需要繼續(xù)改進算法以適應不斷出現(xiàn)的各種復雜情況。

本文根據(jù)云制造的特點和目標，構(gòu)建資源優(yōu)化配置問題的評價函數(shù)模型。對傳統(tǒng)遺傳算法的選擇、交叉和變異等過程進行改進，提高求解算法的尋優(yōu)效率和收斂性。最后通過實例驗證了本文所提模型和改進算法的有效性。

1 制造資源配置問題描述

云制造是云計算向制造業(yè)的延伸，它將制造服務虛擬化到云制造服務平臺（簡稱云平臺）中實現(xiàn)制造服務的高度集成共享和高效利用[1]。制造資源是一個廣泛的概念，是指所有能在制造全生命周期中發(fā)揮作用的資源[6]。云平臺是實現(xiàn)云制造服務的重要載體，制造資源供需雙方分別通過云平臺將資源上傳至云端進行整合，通過智能化搜索技術進行優(yōu)化匹配，從而實現(xiàn)“制造即服務”的要求。

隨著制造業(yè)的飛速發(fā)展以及云平臺的不斷改善，平臺資源池中的制造資源會呈現(xiàn)多元化和海量化的趨勢。在大多數(shù)實際制造任務中不會單一地使用一種資源，而是多種資源相互組合、相互關聯(lián)，共同形成一條或多條制造任務鏈。因此，如何按照制造任務發(fā)起人的需求對眾多任務鏈進行優(yōu)化選擇成為了當前面臨的一個主要難題。如一項加工齒輪的任務集，任務發(fā)起人需要在云平臺中搜索各項加工任務所需的加工設備資源，并且要綜合考慮任務交付時間、加工成本以及加工質(zhì)量等多個目標要求。這類制造資源配置問題屬于多目標優(yōu)化問題，各目標之間存在無法比較或相互沖突的可能，基本上不存在所有目標都達到最優(yōu)的解，同時多目標問題的結(jié)果通常用一個解集來表示，且解之間不能單純地比較優(yōu)劣。

對制造資源優(yōu)化配置問題進行建模，設某制造任務包含n項分任務，用集合TaskSet表示為：

其中：Taski表示任務集的第i項分任務。

假定每項任務都需由不同的資源完成，Taski可供選擇的制造資源數(shù)量為mi，它們形成制造資源集TaskMRi，即：

其中：MRj表示完成分任務Taski的第j個制造資源。

制造資源優(yōu)化配置問題屬于NP難題[7]，本文將以該問題為研究對象，構(gòu)造評價函數(shù)并設計求解算法，最終獲得最優(yōu)的資源配置方案。

2 制造資源配置評價函數(shù)構(gòu)造

根據(jù)行業(yè)調(diào)研和實際需要，設定制造資源配置問題的優(yōu)化目標分別為交付時間、加工成本和加工質(zhì)量。

2.1 交付時間

交付時間由加工時間和聯(lián)結(jié)時間兩部分構(gòu)成。其中，加工時間指進行加工作業(yè)的時間；聯(lián)結(jié)時間指工件由本項任務所在地運輸至下一項任務所在地的時間。針對上述概念，構(gòu)造交付時間的評價函數(shù)為：

其中：TMi,j表示第i項任務的第j個資源對應的加工時間；TJi,i+1表示加工件從第i項任務所在地運送至第i+1項任務所在地的聯(lián)結(jié)時間。

2.2 加工成本

加工成本包括制造資源進行直接制造活動所產(chǎn)生的制造成本以及將工件運輸至下一任務所在地所產(chǎn)生的聯(lián)結(jié)成本。在云模式下，制造資源分布廣泛，不同區(qū)域的運費起步價位、燃油費等均存在差異，不能將運輸成本同運輸時間做等價處理。加工成本的評價函數(shù)構(gòu)造為：

其中：TMi,j表示第i項任務的第j個資源對應的制造成本；TJi,i+1表示加工件從第i項任務所在地運送至第i+1項任務所在地的聯(lián)結(jié)成本。

2.3 加工質(zhì)量

加工質(zhì)量指制造資源完成加工任務時在工藝、精度、規(guī)格等方面的優(yōu)劣程度。云模式下，加工質(zhì)量將依據(jù)資源本身的歷史活動分數(shù)進行評價。歷史活動分數(shù)是由以往使用過該特定資源的任務發(fā)起人對該資源在加工質(zhì)量方面所做出的直觀打分，并進行綜合平均計算后得到的結(jié)果，數(shù)值范圍為[0,1]。加工質(zhì)量是新任務發(fā)起人用來選擇制造資源的重要參考指標，評價函數(shù)為：

其中：Qi,j表示第i項任務的第j個制造資源對應的加工質(zhì)量。

3 制造資源配置求解算法設計

遺傳算法是智能算法研究領域中的熱點，并且云模式下資源的優(yōu)化配置與遺傳算法的自然選擇過程和適者生存的思想有一定的相似性[8]。傳統(tǒng)遺傳算法在解決多目標優(yōu)化問題時雖然具有相對完整的求解思路和運算體系，但它沒有充分利用每次迭代產(chǎn)生的反饋信息，造成迭代盲目、求解效率偏低等問題。雖然可以采用精英保留策略使經(jīng)過選擇操作后最優(yōu)的個體（即染色體）不參與交叉和變異而直接保留到新種群中，并代替經(jīng)過交叉、變異后的最劣個體，但該方法會在一定程度上抑制種群的多樣性，易造成算法的早熟。因此，對傳統(tǒng)遺傳算法進行改進，增強算法的尋優(yōu)效率和自適應性。本文將在對傳統(tǒng)遺傳算法進行充分研究的基礎上，針對云模式下制造資源的優(yōu)化配置問題對算法進行改進。設定算法種群規(guī)模為M，迭代次數(shù)為N，染色體長度，即基因數(shù)為n。

3.1 適應度函數(shù)設計

遺傳算法在進化搜索的過程中以適應度函數(shù)為依據(jù)。本文采用權重法對評價函數(shù)中的交付時間（T）、加工成本（C）及加工質(zhì)量（Q）進行整合優(yōu)化，并為每項評價函數(shù)分配相應的主觀權重。在實際問題中，不同類型的數(shù)據(jù)有不同的評價量綱，無法直接整合，需要對其進行標準化處理，即將不同類型的數(shù)據(jù)運用科學的數(shù)據(jù)變換方法壓縮到區(qū)間[0,1]上，使其具備相互可比較性。針對該問題，采用一種實用的數(shù)據(jù)標準化處理方式，綜合考慮各函數(shù)的優(yōu)化目標，并將目標函數(shù)T、C和Q構(gòu)造為單一目標的適應度函數(shù)F，即：

其中：ωT、ωC、ωQ表示各函數(shù)的權重系數(shù)，滿足ωT+ωC+ωQ=1，將依照制造任務發(fā)起人的要求進行設定；Tmax、Cmax、Qmax分別表示任務集對應的交付時間、加工成本和加工質(zhì)量的上限值。通常情況下該類數(shù)值需根據(jù)實際問題進行前期多次試算得出。

3.2 染色體編碼與生成

遺傳算法有多種編碼方式，其中實數(shù)編碼方式在基因型空間中的拓撲結(jié)構(gòu)與其表現(xiàn)型空間中的拓撲結(jié)構(gòu)一致，編碼和解碼操作簡單，適合于解決制造資源優(yōu)化配置問題。染色體X={x1,x2,...,xj,...,xn}表示任務集共由n項任務構(gòu)成，基因xj表示第j項任務所選取的制造資源的編號。這種編碼方式的關鍵在于如何保證種群中所有染色體的基因都能滿足問題的約束條件[9]。結(jié)合遺傳算法編程中的實際情況，提出一種基于上限約束的基因生成方法。設定上限染色體（或稱上限數(shù)組）為V={v1,v2,...,vj,...,vn}，其中vj對應第j項任務的候選資源數(shù)。在運算過程中設定每個基因位的取值范圍為[1，vj]，從而保證了基因生成的合法性，具體過程如圖1所示。

圖1 染色體合法生成流程

3.3 選擇

“選擇”提供了遺傳算法的驅(qū)動力，是遺傳算法向最優(yōu)解逐步邁進的主要手段。通常情況下較優(yōu)的個體會在算法的選擇操作后有更大的幾率存留下來。比較常見的策略有輪盤賭法和錦標賽法。

1）輪盤賭法

輪盤賭法的原理是根據(jù)每個個體適應度值的比例確定該個體的選擇概率或生存概率。由于本問題的適應度函數(shù)為越小越優(yōu)，因此設定選擇概率的計算公式為：

其中：fi表示個體i對應的選擇概率；Fi表示個體i對應的適應度值。

適應度函數(shù)值越小，選擇概率越大，表示個體的適應力越強，將會有更大的幾率被選中生存下去。

選擇概率計算完后，將其轉(zhuǎn)換成累計概率。個體i的累計概率Pi中下限Pimin和上限Pimax的計算公式為：

當種群中的個體差異較低，即優(yōu)質(zhì)個體與劣質(zhì)個體的適應度值偏差不大時，會影響輪盤賭法對較優(yōu)個體的選取效率，不利于種群的優(yōu)良化。但采用輪盤賭法進行選取操作有利于保持種群的多樣性，一定程度上可以避免算法的早熟。

2）錦標賽法

錦標賽法的原理是在種群中隨機抽取一定數(shù)量的個體（保證每個個體被抽中的幾率是相同的），之后選擇其中最優(yōu)的個體放入新種群中，并重復該操作，直到產(chǎn)生與之前規(guī)模相當?shù)男路N群。通常情況下錦標賽法的選取結(jié)果受每次選取的個體數(shù)量Ct影響，Ct設定越大，說明每次選取過程中參與比較的個體數(shù)量越多，因而最終保留的個體相對越優(yōu)良。但是，Ct越大也會使得每次選取后保留的個體趨于相同，從而破壞種群的多樣性，易造成算法的早熟。

傳統(tǒng)遺傳算法多采用輪盤賭法進行選擇操作，本文提出了一種基于輪盤賭法和錦標賽法的混合選取法，即在算法的交叉操作前對種群進行選取操作，使得進行交叉的父代染色體分別通過輪盤賭法和錦標賽法選取出來。該方法繼承了錦標賽法在選取優(yōu)良個體的高效性，又利用輪盤賭法保證了選取結(jié)果的多樣性，一定程度上降低了算法早熟的風險。

3.4 交叉

“交叉”是種群進化的必要保證。通過選擇操作挑選出M/2組染色體，每組染色體由兩條染色體組成，記為父代。之后對每組染色體依次進行交叉判斷，滿足交叉條件的染色體組進行交叉操作產(chǎn)生臨時新個體，直到種群中的所有染色體組完成交叉操作后產(chǎn)生臨時新種群。交叉率Pc為父代交叉操作的概率，確定其取值范圍比較困難，沒有任何標準可遵循，且不同類型的問題有不同的選取方式[10]。在算法迭代初期階段，為了保證個體多樣性，通常選取較高的交叉率；而在迭代后期，為了保證種群趨于穩(wěn)定，需要適當降低交叉率。本文采用一種線性遞減函數(shù)的方式對變異率進行自適應修正。設定初始交叉率和終止交叉率分別為Pc1和PcN，計算各代交叉率Pci的公式為：

其中：i為當前代數(shù)。

為防止算法的進化過程趨于隨機搜索，通常情況下可設定Pc取值范圍為[0.5,0.8]。交叉操作過程如圖2所示。

3.5 變異

交叉完成后將對臨時新種群中的所有染色體進行變異操作，變異是實現(xiàn)種群多樣性的重要途徑，并且可以預防算法的早熟現(xiàn)象。由于染色體上的每一個基因位都對應不同的取值范圍，因此變異過程存在基因約束。在傳統(tǒng)遺傳算法的變異操作中，染色體基因發(fā)生變異是隨機和盲目的，沒有任何原則可遵循，即變異不具備反饋特性，易造成算法盲目迭代、收斂速度慢等問題。本文將蟻群算法的正反饋特性引入遺傳算法中，通過信息素更新原則指導遺傳算法的變異規(guī)則[11]。在蟻群算法中，優(yōu)質(zhì)的路徑會吸引更多的螞蟻走過，從而留下更多的信息素，因此可用信息素量表示解的優(yōu)質(zhì)性，即信息素量越高，對應的解越優(yōu)質(zhì)。本文研究的問題為越小越優(yōu)，因此個體適應度值越低，信息素量則越高。

圖2 交叉操作流程

按照蟻群算法中信息素量決定交換變異點，確保交換后基因變異位置前后路徑上的信息素量比變異前的高。隨機選取某條染色體上的基因位j進行變異，對變異前后的基因位周圍進行信息素量比較，公式為：

其中：Phx,y表示染色體內(nèi)由基因x至基因y所產(chǎn)生的信息素量。

該方法不僅保護了種群迭代的多樣性，同時也避免了精英保留方式對算法搜索活性造成的影響，充分提高了算法的尋優(yōu)效率，優(yōu)化了求解的質(zhì)量?；谙伻核惴ǜ倪M變異算子的流程如圖3所示。

為了增強變異帶來的反饋特性，通常情況下選用多基因點變異的方式，并設置較高的變異率。但變異率過高不利于算法后期的快速收斂，且運算后期優(yōu)良個體的提升空間明顯縮小，此時對優(yōu)良個體進行變異操作只會額外增加算法的負擔。為保證正反饋特性，同時優(yōu)化算法收斂效果，這里提出了一種對主觀變異率Pm進行修正的方法，計算公式為：

圖3 變異操作流程

其中：P'm表示修正后的變異率；f表示被選個體的適應度值；favg表示種群中平均適應度值；fmin表示種群個體中的最小適應度值；α表示調(diào)整參數(shù)，取值范圍由問題適應度值范圍決定。

當個體的適應度值高于平均適應度值時，則按照正常變異率進行變異；當?shù)陀谄骄m應度值時，說明該個體在種群中較優(yōu)質(zhì)，則適當降低變異率。對變異率進行修正的意義在于保證了在同一代下相對較優(yōu)的個體有更小的幾率進行變異操作，從而在不失種群多樣性的基礎上保護了優(yōu)良的個體，促進了運算后期算法的逐步收斂和穩(wěn)定。

3.6 其他參數(shù)設定

1）種群規(guī)模

種群規(guī)模M指群體中個體的數(shù)量，一般認為種群規(guī)模會影響算法的運算效率和效果。種群規(guī)模的選取與問題的規(guī)模相對應，M選取較大易增加算法的運算負擔，較小則抑制算法的活性。在以實數(shù)編碼方式的遺傳算法中，M的大小通常與染色體長度n存在一定的關聯(lián)性，取值范圍區(qū)間為[1.5n,2n/2]。

2）終止條件

終止條件通常由設定好的迭代次數(shù)N決定。隨著迭代次數(shù)的增加，較優(yōu)解在種群中所占的比例會逐漸增大，此時稱種群逐漸趨于收斂。在實際運算中，迭代次數(shù)N需要多次試算進行確認。

4 實例驗證

某型號齒輪的生產(chǎn)制造過程主要包括：粗車、精車、鉆孔、銑齒、倒角、磨孔、研磨和配對等八項任務，每項任務都要用到不同的加工設備。設定加工100件該型號齒輪?，F(xiàn)在任務發(fā)起人欲通過云平臺在資源池中搜索所有符合該任務加工作業(yè)的設備資源，同時綜合考慮交付時間、加工成本和加工質(zhì)量等目標，獲得較優(yōu)的資源配置方案。通過對云資源池中的相關制造資源進行選取，得到了每類資源的若干相似度較高的個體，如表1所示。所有資源都分布在A、B、C和D四個區(qū)域，設定最終交付地為E，區(qū)域之間的運輸時間和費用關系如表2所示。

表1 加工資源數(shù)據(jù)

續(xù)（表1）

表2 區(qū)域關系

運用C#編程語言設計適應于該問題的傳統(tǒng)遺傳算法與改進型遺傳算法，其中傳統(tǒng)遺傳算法采用輪盤賭法進行選擇操作，改進型遺傳算法采用混合輪盤賭+錦標賽選取法。對上述研究問題進行優(yōu)化配置，主要步驟如下：

步驟1：依照式(6)建立評價函數(shù)模型。在本實例中，Tmax和Cmax為動態(tài)值，經(jīng)過前期多次試算，得到試算值分別為3755和15747。在該值基礎上進行一定的增值，可防止計算過程中適應度值的非法溢出（＞1）。本文設定Tmax取值為3760，Cmax取值為15750。Qmax在本實例中為靜態(tài)值，直接求得結(jié)果為5.69。設定各個優(yōu)化目標的權重值為：ωT=0.3，ωc=0.4，ωQ=0.3。

步驟2：對問題進行編碼，得出染色體長度n為8，結(jié)合染色體長度與種群規(guī)模的關系，設置較為理想的M為14。通過隨機方式生成合法初始種群，用矩陣表示為

步驟3：經(jīng)過前期多次試算，設定兩種算法的迭代次數(shù)為80次?？紤]到M設置不大，為保證解的多樣性，在選擇操作中設置Ct為3，同時設定傳統(tǒng)遺傳算法的Pc為0.5、Pm為0.2，改進型遺傳算法的Pc1為0.5，PcN為0.2?？紤]到改進型遺傳算法在變異過程中引入了正反饋機制，因此采用雙點變異的方式，設定Pm為0.2、α為2以增強算法優(yōu)化方向。

步驟4：通過迭代運算得到兩種算法的適應度函數(shù)值收斂趨勢以及最終優(yōu)化結(jié)果，如圖4所示。

圖4 資源優(yōu)化配置結(jié)果

在圖4中，線條TGA代表傳統(tǒng)遺傳算法，AGA代表改進型遺傳算法。由于改進型遺傳算法在選擇操作中采用了輪盤賭和錦標賽混合選取法，并在變異過程中加入了正反饋特性，明確了變異的優(yōu)化方向，因此選擇優(yōu)良個體的能力明顯強于傳統(tǒng)遺傳算法，從而收斂速度明顯加快，且保證了種群多樣性，使得計算過程逐漸趨于最優(yōu)。同時改進型遺傳算法的交叉率和變異率受迭代次數(shù)和適應度值的影響而自適應調(diào)整，在不失活性的同時保證了運算后期對優(yōu)良個體的保護，因此比傳統(tǒng)遺傳算法更穩(wěn)定，也更易獲得最優(yōu)解。最終通過改進型遺傳算法得到資源的最優(yōu)配置結(jié)果，用染色體編碼表示為X={3,3,3,2,1,1,3,2}。

任務集中每項任務所選擇的資源編號為染色體X中對應的基因序號，因此得到資源的最優(yōu)配置依次為：

立車C9351→自動轉(zhuǎn)塔車床（編號3）→搖臂鉆床Z304→銑齒機N0609→圓弧倒角機（編號1）→立磨WX034A→研磨YKD2552→配對機YB957。

5 結(jié)束語

隨著云制造的發(fā)展，制造資源和制造任務海量化、多元化的趨勢日益明顯，資源與任務之間的快速配置難度增大。針對傳統(tǒng)遺傳算法在求解制造資源配置問題時存在盲目迭代、求解效率低、收斂速度慢等問題，對遺傳算法進行優(yōu)化改進，提出了一種輪盤賭法和錦標賽法相結(jié)合的選取機制，并賦予變異過程正反饋特性，明確了優(yōu)化方向，提高了尋優(yōu)效率。同時采用交叉率和變異率自適應的方法，在確保算法不失活性的前提下優(yōu)化了求解過程，提高了算法的收斂性和穩(wěn)定性。最后以某型號齒輪的生產(chǎn)加工過程為例驗證了本文所提模型和改進算法的有效性?；诟倪M型遺傳算法，提出制造資源優(yōu)化配置方法，為云模式下多主體業(yè)務協(xié)同和制造資源優(yōu)化共享提供了新思路。

[1]李伯虎,張霖,王時龍,等.云制造—面向服務的網(wǎng)絡化制造新模式[J].計算機集成制造系統(tǒng),2010,16(1)：1-7.

[2]尹勝,尹超,劉飛,等.多任務外協(xié)加工資源優(yōu)化配置模型及遺傳算法求解[J].重慶大學學報,2010,33(3)：49-55.

[3]Kundakci Nilsen, Kulak Osman. Hybrid genetic algorithms for minimizing makespan in dynamic job shop scheduling problem [J].Computers & Industrial Engineering,2016,96：31-51.

[4]袁慶霓,謝慶生,許明恒,等.Web服務平臺下基于遺傳算法的制造資源服務選擇[J].計算機應用研究,2009,26(4)：1266-1268.

[5]張雪艷,梁工謙,董仲慧.基于改進自適應遺傳算法的柔性作業(yè)車間調(diào)度問題研究[J].機械制造,2016,54(6)：1-4.

[6]陶飛,張霖,郭華,等.云制造特征及云服務組合關鍵問題研究[J].計算機集成制造系統(tǒng),2011,17(3)：477-486.

[7]MR Garey, DS Johnson. Computers and Intractability： A Guide to the Theory of NP-Completeness[M].New York：W.H.Freeman and Company,1979.

[8]付景枝,張友良.基于遺傳算法的網(wǎng)格制造資源優(yōu)化選擇[J].小型微型計算機系統(tǒng),2007,28(4)：674-677.

[9]杜軒,李登橋,朱康.基于矩陣編碼遺傳算法的PCB生產(chǎn)線元件分配優(yōu)化[J].三峽大學學報,2015,37(1)：89-93.

[10]馬雪芬,戴旭東,孫樹棟.面向網(wǎng)絡化制造的制造資源優(yōu)化配置研究[J].計算機集成制造系統(tǒng),2004,10(5)：523-527.

[11]翟梅梅.基于蟻群算法的改進遺傳算法[J].安徽理工大學學報,2009,29(3)：58-63.