劉 亞，李勝華,袁 莉，萬(wàn)書亭

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

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

劉 亞1，李勝華2,袁 莉2，萬(wàn)書亭1

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

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

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

0 引言

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

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

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

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

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

目標(biāo)函數(shù)：

(1)

約束條件：

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

2 遺傳算法設(shè)計(jì)

2.1 遺傳算法原理

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

2.2 編碼方法

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

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

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

(3)

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

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

(4)

2.4 遺傳算子

(1)選擇算子

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

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

(2)交叉算子

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

(3)變異算子

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

2.5 算法流程

具體算法流程如下：

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

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

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

Step4 變異：隨機(jī)確定變異個(gè)體，得到變異后種群。

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

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

Step7 算法結(jié)束。

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

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

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

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

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

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

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

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

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

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

圖2 軟件界面圖

3.4 系統(tǒng)運(yùn)算實(shí)例

(1)小規(guī)模問(wèn)題

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

表1 需求電纜信息

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

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

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

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

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

(2)大規(guī)模問(wèn)題

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

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

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

表4 電纜原材料庫(kù)存信息

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

4 結(jié)論

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

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

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

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

[3]王小東,李剛,歐宗瑛.一維下料優(yōu)化的一種新算法[J].大連理工大學(xué)學(xué)報(bào),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]萬(wàn)書亭,韓國(guó)棟.MATLAB與C#.net混合編程的電纜優(yōu)化分割研究[J].中國(guó)電力,2013,46(6):48-51.

[6]方昶,劉心報(bào),裴軍,等.基于順序啟發(fā)式進(jìn)化算法的多目標(biāo)一維下料問(wèn)題[J].中國(guó)管理科學(xué),2012(s1): 94-100.

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

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

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

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

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

[12]徐平平,郭蘊(yùn)華.基于改進(jìn)蟻群算法的不定長(zhǎng)原管一維下料廢料率優(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。

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

TM757

A

1672-0792(2017)03-0013-05

劉亞(1990-)，女，碩士研究生，研究方向?yàn)殡娏υO(shè)備優(yōu)化理論及應(yīng)用。