基于遺傳算法的電纜優(yōu)化分割系統(tǒng)的研究與開發(fā)

劉 亞，李勝華,袁 莉，萬書亭

(1. 華北電力大學能源動力與機械工程學院，河北保定071003; 2.國網(wǎng)江蘇省泰州供電公司，江蘇泰州225300)

基于遺傳算法的電纜優(yōu)化分割系統(tǒng)的研究與開發(fā)

劉 亞1，李勝華2,袁 莉2，萬書亭1

(1. 華北電力大學能源動力與機械工程學院，河北保定071003; 2.國網(wǎng)江蘇省泰州供電公司，江蘇泰州225300)

電力電纜的優(yōu)化分割問題屬于一維下料問題，針對多規(guī)格一維下料問題，在核心算法方面，提出了一種基于遺傳算法的求解方法。主要內(nèi)容是把電纜原材料編號的一種順序作為一個個體的染色體進行編碼，其中的每個編號就代表著一個基因，基因數(shù)量為所有需求電纜的數(shù)量和，同時，根據(jù)建立的數(shù)學模型確定適應(yīng)度函數(shù)，在種群進化過程中，應(yīng)用適應(yīng)度函數(shù)進行評價，通過選擇、交叉、變異得到最優(yōu)解。系統(tǒng)的算法由MATLAB工具實現(xiàn)，界面由VS工具實現(xiàn)，通過兩種工具混合編程實現(xiàn)軟件的編寫。實驗結(jié)果表明，系統(tǒng)計算速度較快，較好地解決了電纜優(yōu)化分割問題。

電纜；優(yōu)化分割；一維下料；遺傳算法

0 引言

電力電纜是電網(wǎng)建設(shè)的主要原材料，是用于傳輸和分配電能的電纜，電力電纜常用于城市地下電網(wǎng)、發(fā)電站引出線路、工礦企業(yè)內(nèi)部供電及過江海水下輸電線。隨著中國經(jīng)濟的持續(xù)快速發(fā)展，電力建設(shè)發(fā)展迅速，而在電力線路中，電纜所占比重正逐漸增加，而電纜原材料價格較高，每年在電纜的使用上耗資很大。電纜在使用時，要先切割成要求的規(guī)格，由于所需規(guī)格不同，切割時易產(chǎn)生資源浪費問題。因此，需要開發(fā)一種電纜優(yōu)化分割系統(tǒng)來減少資源的浪費。

電纜的優(yōu)化分割屬于一維下料問題[1-3]，近年來，在一維下料問題的研究算法上有了很大的發(fā)展，包括線性規(guī)劃算法[4-5]、啟發(fā)式算法[6-8]、遺傳算法[9-11]、蟻群算法[12]等，而研究內(nèi)容大多是單一規(guī)格的下料問題。近年來遺傳算法發(fā)展很快，是目前發(fā)展比較完善的一種優(yōu)化算法，可以很好地解決小規(guī)模以及大規(guī)模一維下料問題。因此，本文采用遺傳算法來研究多規(guī)格一維下料問題，并且應(yīng)用MATLAB與Microsoft Visual Studio 2010(VS)兩種工具來實現(xiàn)電纜優(yōu)化分割系統(tǒng)。

1 數(shù)學模型的建立

根據(jù)原材料的類型，一維下料問題可以分為單一規(guī)格(原材料的長度相等)一維下料問題和多規(guī)格(原材料長度不同)一維下料問題；根據(jù)原材料的數(shù)量，可以分為完全下料(原材料的數(shù)量足夠，可得到所有需求型材)和不完全下料(原材料數(shù)量有限，只能得到部分需求型材)問題。本文主要研究多規(guī)格完全一維下料問題。

本文要達到的目標是使電纜原材料的使用量達到最小，建立數(shù)學模型如下所示：

目標函數(shù)：

(1)

約束條件：

式中：N是正整數(shù)；F是原材料的使用量；p是第j種原材料下料方案的數(shù)量。

2 遺傳算法設(shè)計

2.1 遺傳算法原理

遺傳算法是模擬生物在自然環(huán)境下的遺傳和進化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索方法。采納了自然進化模型，從代表問題可能潛在解集的一個種群開始，種群由經(jīng)過基因編碼的一定數(shù)目的個體組成。每個個體實際上是染色體帶有特征的實體，初始種群產(chǎn)生后，按照適者生存和優(yōu)勝劣汰原理，逐代演化產(chǎn)生出越來越好的解。

2.2 編碼方法

本文研究的是多規(guī)格原材料一維下料問題，由于原材料的長度不同，不能按照一般遺傳算法編碼方式進行編碼，因為在后續(xù)進化過程中，經(jīng)過交叉、變異，不能確定所得需求電纜對應(yīng)哪一種長度的原材料?？紤]到建立的數(shù)學模型以及實際的下料情況，本文應(yīng)用一種類似于實數(shù)編碼的方法，個體的長度即為所有需求電纜的數(shù)量和，假設(shè)所有原材料都參與計算，給所有規(guī)格的原材料逐一進行編號，之后將上述編號隨機給個體賦值，即完成編碼。這種編碼方法涵蓋了模型里面的三個約束條件：下料使用的原材料數(shù)量不多于對應(yīng)庫存電纜原材料的數(shù)量；對相應(yīng)原材料進行切割，最后得到的下料方案里面，各需求電纜的數(shù)量與實際需要的數(shù)量相等；決策變量均為整數(shù)。

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

應(yīng)用遺傳算法求解問題時，常用適應(yīng)度函數(shù)來對結(jié)果進行判斷，適應(yīng)度值越大則表示得到的結(jié)果質(zhì)量越好。由于目標函數(shù)是使原材料的使用量最小，可考慮采用原材料使用量的倒數(shù)為適應(yīng)度函數(shù)，不過這樣會使適應(yīng)度值很小，很難做出其他方面的判斷。比如，由于個體是隨機編碼實現(xiàn)的，有可能會出現(xiàn)過多需求電纜集中到某一根原材料甚至超出其長度的情況，即產(chǎn)生不可行解的情況，為了減少以上情況的發(fā)生，將原材料的利用率設(shè)置為適應(yīng)度函數(shù)：

(3)

適應(yīng)度值最大為1，也就是原材料全部應(yīng)用與需求電纜的情況。

然而，當出現(xiàn)適應(yīng)度值大于1的情況時，也就是出現(xiàn)不可行解時，為了防止對計算結(jié)果產(chǎn)生較大的影響，需要對適應(yīng)度設(shè)置懲罰機制，引入罰函數(shù)，設(shè)計如下：

(4)

2.4 遺傳算子

(1)選擇算子

選擇的標準一般是按照適應(yīng)度來進行的。初始種群規(guī)模設(shè)置為N，個體在經(jīng)過交叉、變異之后，會得到兩個下一代，由于得到的兩個子代是具有一定隨機性的，因此得到的兩個子代質(zhì)量不一定高于上一代，也不一定會符合約束條件。為了得到最優(yōu)的子代，使種群得以進化，所以要對兩個子代以及上一代種群進行選擇。

三代種群中，對于不符合約束條件的個體進行懲罰，即采用對適應(yīng)度設(shè)置的懲罰機制進行處理。將三代個體按照適應(yīng)度從大到小的順序進行排列，將排在前面的N個個體作為父輩種群進入下一輪的進化。

(2)交叉算子

交叉算子在后代進化過程中起主要作用，將交叉概率pc設(shè)置為0.85，采用單點交叉算子完成個體的交叉。首先將上一步得到的父輩群體按照優(yōu)劣順序兩兩進行交叉，假設(shè)已確定進行交叉的兩個個體為X1、X2，個體的交叉點位置P隨機確定，之后個體X1得到P1、P2兩個分段，個體X2得到M1、M2兩個分段，將P1、M1分段進行交換，得到交叉后個體。計算得到新個體的適應(yīng)度，如果適應(yīng)度的值大于1，或者說該個體不滿足約束條件，則返回交叉前的個體，重新確定交叉點位置進行交叉。

(3)變異算子

在遺傳進化過程中，會發(fā)生一些突變，盡管突變得到的基因有好有壞，但這些突變在遺傳的進化過程中是起到很大作用的。在種群的進化過程中，引入變異算子。設(shè)置種群的變異率pm為0.05，上一步交叉后得到新的種群，通過種群的變異率隨機得到變異的個體，對相應(yīng)個體隨機確定兩點M1、M2，將M1、M2進行交換得到新的個體。由于變異具有隨機性，無法確定新個體的質(zhì)量，同樣計算得到新個體的適應(yīng)度，如果適應(yīng)度的值大于1，或者說該個體不滿足約束條件，則返回變異前的個體，重新確定變異位置進行變異。

2.5 算法流程

具體算法流程如下：

Step1 種群初始化：確定編碼機制，以及種群規(guī)模N，得到初始種群。

Step2 適應(yīng)度函數(shù)：根據(jù)建立的數(shù)學模型，確定適應(yīng)度函數(shù)。

Step3 交叉：隨機確定交叉?zhèn)€體，采用單點交叉的方式，得到新的種群。

Step4 變異：隨機確定變異個體，得到變異后種群。

Step5 選擇：從種群中選擇適應(yīng)度值最大的N個個體，得到新的種群。

Step6 判斷：滿足判斷條件，輸出最優(yōu)解；否則，轉(zhuǎn)到step3。

Step7 算法結(jié)束。

3 電纜優(yōu)化分割系統(tǒng)的設(shè)計與實現(xiàn)

3.1 優(yōu)化算法的調(diào)用

系統(tǒng)通過MATLAB與VS工具混合編寫程序?qū)崿F(xiàn)，其中核心算法的實現(xiàn)由MATLAB完成的，電纜相關(guān)數(shù)據(jù)的輸入部分，即系統(tǒng)的實現(xiàn)是由VS完成的。根據(jù)上一章確定的算法流程，應(yīng)用MATLAB編寫程序，核心算法編寫完成后，繼續(xù)應(yīng)用MATLAB工具將程序生成動態(tài)鏈接庫，即dll文件，為VS工具的調(diào)用做好準備工作。

3.2 系統(tǒng)的流程設(shè)計

系統(tǒng)流程如圖1所示。

圖1 軟件優(yōu)化計算流程圖

系統(tǒng)主要包括電纜庫存管理和優(yōu)化計算兩部分。庫存管理主要包括電纜原材料的添加、修改、刪除等，后臺連接的是Access數(shù)據(jù)庫，實現(xiàn)對電纜原材料庫存的管理與保存，在優(yōu)化分割系統(tǒng)中加入庫存管理功能，避免了用戶在每次使用前對于電纜原材料的手動輸入，減少了用戶的工作量，在一定程度上方便了用戶的使用。優(yōu)化計算部分主要包括需求電纜數(shù)據(jù)的輸入、對應(yīng)型號電纜原材料的導(dǎo)入、優(yōu)化計算以及結(jié)果的輸出等。

3.3 系統(tǒng)主界面設(shè)計

系統(tǒng)主界面設(shè)計如圖2所示。

界面右側(cè)添加了選項卡，內(nèi)容分別為庫存管理、優(yōu)化結(jié)果以及庫存統(tǒng)計。打開主界面，系統(tǒng)右側(cè)選項卡部分顯示的是庫存管理界面，系統(tǒng)連接Access數(shù)據(jù)庫，準確顯示出庫存電纜的基本信息。系統(tǒng)左側(cè)表格是需求電纜信息的輸入位置，計算前根據(jù)實際需要輸入需求電纜信息，然后在界面中間的庫存電纜信息位置選擇對應(yīng)型號的庫存電纜，導(dǎo)入數(shù)據(jù)，點擊優(yōu)化計算按鈕，完成計算。

圖2 軟件界面圖

3.4 系統(tǒng)運算實例

(1)小規(guī)模問題

某電力工程建設(shè)需要一定數(shù)目的電纜，其中對應(yīng)型號電纜的庫存原材料為500 m的電纜原材料3軸，800 m的電纜原材料2軸，其中需求電纜的信息如表1所示。

表1 需求電纜信息

應(yīng)用電纜優(yōu)化分割系統(tǒng)的計算平臺，輸入需求電纜基本信息，導(dǎo)入對應(yīng)庫存電纜信息，點擊優(yōu)化計算按鈕，計算完畢后，結(jié)果將顯示在主界面的優(yōu)化結(jié)果表格中。通過優(yōu)化計算，得到原材料的下料方案，結(jié)果如表2所示。共三種下料方式，優(yōu)化結(jié)果與電纜需求一致，不需要對優(yōu)化結(jié)果進行后續(xù)的處理，操作簡單、準確。

表2 遺傳算法優(yōu)化結(jié)果

表3為經(jīng)過線性規(guī)劃算法得到的優(yōu)化結(jié)果，由于應(yīng)用的線性規(guī)劃是將所有優(yōu)化下料方案優(yōu)化組合，從而得到最優(yōu)結(jié)果，運算速度較慢，而需求電纜數(shù)量固定，通過組合會出現(xiàn)無解的情況，出現(xiàn)這種情況時需將約束范圍擴大，得到如表3所示的近似最優(yōu)解。從中可以看出計算得到的方案與需求并非完全相符，之后需要進一步的優(yōu)化，較為繁瑣。

表3 線性規(guī)劃優(yōu)化結(jié)果

通過以上兩種算法的對比，可以看出系統(tǒng)運算速度快，操作簡單，得到的優(yōu)化結(jié)果與電纜需求保持一致，電纜原材料利用率高，質(zhì)量較好。

(2)大規(guī)模問題

某電力工程建設(shè)需要一定數(shù)目的電纜，其中對應(yīng)型號電纜的庫存原材料的長度分別為1 200 m、1 100 m、1 000 m、800 m、700 m、600 m、500 m，對應(yīng)庫存數(shù)量依次為2軸、3軸、5軸、3軸、1軸、3軸、2軸。需求電纜的信息如表4所示。

應(yīng)用電纜優(yōu)化分割系統(tǒng)的計算平臺，輸入需求電纜基本信息，導(dǎo)入對應(yīng)庫存電纜信息，優(yōu)化計算完畢后，得到結(jié)果如表5所示。

對于數(shù)據(jù)較多的大規(guī)模問題，每種原材料對應(yīng)的下料方案過多，應(yīng)用線性規(guī)劃算法運算速度較慢，很難得到最優(yōu)方案。表5為應(yīng)用電纜優(yōu)化分割系統(tǒng)得到的優(yōu)化結(jié)果，優(yōu)化后下料方案與需求電纜信息一致，質(zhì)量較好，說明系統(tǒng)在處理數(shù)據(jù)較多的問題時是可行的。

表4 電纜原材料庫存信息

表5 優(yōu)化計算結(jié)果

4 結(jié)論

以電纜原材料編號的一種隨機排列為一個個體，其中每個編號就代表著一個基因，基因數(shù)量設(shè)置為需求電纜的總數(shù)量。進化過程中，通過選擇、交叉、變異，一步步得到近似最優(yōu)解。系統(tǒng)軟件部分由VS工具編寫，調(diào)用核心算法，實際應(yīng)用中計算速度較快，并且通過在軟件中的進一步計算、整理，可以得到電纜分割的最優(yōu)下料方案。

系統(tǒng)操作簡單、方便，運算速度較快，可以得到質(zhì)量較好的優(yōu)化方案，較好地解決了多規(guī)格一維下料問題，也在一定程度上方便了對電纜原材料庫存的管理。

[1] 崔耀東,周密,楊柳.多線材一維下料問題的求解策略[J].廣西師范大學學報(自然科學版),2012,30(3):149-153.

[2]劉林,葛菲菲,劉心報.多目標一維下料決策方法研究[J].中國機械工程,2013,24(7): 951-955，963.

[3]王小東,李剛,歐宗瑛.一維下料優(yōu)化的一種新算法[J].大連理工大學學報,2004,44(3):407-411.

[4]LEE J．In situ column generation for a cutting Stock problem[J]．Computers & Operations Research，2007，34(8)：2345-2358.

[5]萬書亭,韓國棟.MATLAB與C#.net混合編程的電纜優(yōu)化分割研究[J].中國電力,2013,46(6):48-51.

[6]方昶,劉心報,裴軍,等.基于順序啟發(fā)式進化算法的多目標一維下料問題[J].中國管理科學,2012(s1): 94-100.

[7]祝勝蘭,饒運清.一維下料問題的啟發(fā)式方法[J].機械制造與自動化,2014,43(1):52-55.

[8]程浩,劉心報,方昶.基于混合順序啟發(fā)式算法的一維下料問題[J].中國機械工程,2014(16):2191-2195，2203.

[9]王曉偉,劉林,周謐.蜂群遺傳算法在一維下料問題中的應(yīng)用[J].微型機與應(yīng)用,2012,31(6):66-68，71.

[10]壽周翔,王琦暉,王李冬,等.一維下料的改進遺傳算法優(yōu)化[J].計算機時代,2014(1):36-37，41.

[11]李斌,賀飛.求解一維下料問題的改進混合遺傳算法[J].內(nèi)蒙古大學學報(自然科學版),2014,45(3):245-250.

[12]徐平平,郭蘊華.基于改進蟻群算法的不定長原管一維下料廢料率優(yōu)化[J].船海工程,2016,45(1):113-116.

Research and Development of Optimal Cutting System of Cable Based on Genetic Algorithm

LIU Ya1,LI Shenghua2,YUAN Li2,WAN Shuting1

(1.School of Energy Power and Mechanical Engineering, North China Electric Power University, Baoding 071003,China; 2.State Grid Taizhou Power Supply Company, Taizhou 225300,China)

The optimal cutting problem of the power cable belongs to the one-dimensional cutting stock field. A new method based on the genetic algorithm is proposed to solve the problem of one-dimensional cutting stock with multi dimensions. The cable material uses a sequential numbers as an individual identification. Each of these numbers represents a gene. The number of genes is equal to the number of the demanded cables. At the same time, the fitness function is determined according to the established mathematical model. In the process of population evolution, the fitness function is used for evaluation, and the optimal solution is obtained by selecting, crossing and mutating. The algorithm of the system is realized by MATLAB tool, and the interface is realized by VS tool. Through two kinds of tools, the preparation of the software is achieved. The experimental results show that the system calculation speed is fastened, and it can solve the problem of optimal cutting of the cable.

cable; optimal cutting; one-dimensional cutting stock; genetic algorithm

10.3969/j.ISSN.1672-0792.2017.03.003

2016-09-12。

國家自然科學基金(51177046)；河北省自然科學基金(E2015502008)。

TM757

A

1672-0792(2017)03-0013-05

劉亞(1990-)，女，碩士研究生，研究方向為電力設(shè)備優(yōu)化理論及應(yīng)用。