基于遺傳算法的監(jiān)理巡視線路優(yōu)化

聶相田，鄭 良，紀(jì)園可，王 鑫

(華北水利水電大學(xué)，河南 鄭州450045)

近年來隨著國民經(jīng)濟(jì)的增長(zhǎng)和社會(huì)發(fā)展的需要，國內(nèi)重大工程如南水北調(diào)、城市地鐵、高速鐵路等工程建設(shè)陸續(xù)展開，而這些大型工程皆為線性工程.線性工程線路長(zhǎng)，施工面多，各個(gè)工作現(xiàn)場(chǎng)分布在不同位置，往往由一家監(jiān)理機(jī)構(gòu)對(duì)若干個(gè)施工標(biāo)段履行監(jiān)理職責(zé)，監(jiān)理人員在對(duì)各個(gè)工作現(xiàn)場(chǎng)進(jìn)行日常巡視的先后順序不同組成了不同的巡視線路.良好的巡視線路可以提高監(jiān)理人員對(duì)工程控制的流暢度與效率.傳統(tǒng)的巡視線路安排多以自身的經(jīng)驗(yàn)為主，沒有形成量化指標(biāo)體系，對(duì)于監(jiān)理成本的控制和工作效率的提高有很大局限性.在線性工程中，如何建立最優(yōu)的巡視線路對(duì)降低監(jiān)理成本、提高工作效率具有重要意義. 筆者提出利用遺傳算法來解決監(jiān)理工程師在實(shí)際生產(chǎn)調(diào)度中的巡視線路問題.

1 遺傳算法簡(jiǎn)介

遺傳算法(Genetic Algorithm，GA)是一種利用生物遺傳進(jìn)化機(jī)制進(jìn)行系統(tǒng)優(yōu)化的方法. 在過去的20 多年中，遺傳算法在解決復(fù)雜的全局優(yōu)化問題方面，已取得了成功的應(yīng)用［1］.

在MATLAB 中應(yīng)用遺傳算法求解最優(yōu)化問題時(shí)，必須針對(duì)問題所設(shè)定的目標(biāo)環(huán)境轉(zhuǎn)換成對(duì)應(yīng)的適應(yīng)函數(shù)，并以隨機(jī)的方式產(chǎn)生初始種群，經(jīng)過模擬自然界演化的過程，包括3 個(gè)基本操作:選擇、交叉和變異，進(jìn)行反復(fù)進(jìn)化并產(chǎn)生新的物種［2］.

2 遺傳算法的基本求解步驟

1)染色體編碼.將所有的解數(shù)據(jù)映射到染色體的基因上，解數(shù)據(jù)的組合表現(xiàn)為染色體上的基因型結(jié)構(gòu)串，不同的組合形成不同的基因結(jié)構(gòu).

2)產(chǎn)生初始群體. 采用數(shù)字序號(hào)進(jìn)行編碼，首先由系統(tǒng)產(chǎn)生一組區(qū)間在［1，N］之間的N 個(gè)初始串結(jié)構(gòu)數(shù)據(jù)，隨機(jī)排列，構(gòu)成一個(gè)初始群體. 利用該組初始數(shù)據(jù)進(jìn)行遺傳算法的運(yùn)算時(shí)，產(chǎn)生的結(jié)果一般不滿足最優(yōu)要求，以這N 個(gè)串結(jié)構(gòu)作為初始點(diǎn)開始迭代，模擬進(jìn)化過程，選優(yōu)去劣.

3)適應(yīng)度評(píng)估檢測(cè).適應(yīng)度函數(shù)表明個(gè)體或解的優(yōu)劣性.不同的問題適應(yīng)度函數(shù)的定義方式不同.根據(jù)具體問題，計(jì)算群體中各個(gè)個(gè)體的適應(yīng)度.

4)父代選擇. 采用比例選擇因子，子孫的遺留可能性由個(gè)體相對(duì)于適應(yīng)度的概率所決定. 設(shè)定一個(gè)個(gè)體總數(shù)為M 的種群，M 個(gè)個(gè)體中，個(gè)體i 的適應(yīng)度為fi，則個(gè)體相對(duì)于適應(yīng)度的概率Pi=當(dāng)事先給定了個(gè)體被選擇的概率時(shí)，就可以由隨機(jī)產(chǎn)生的［0，1］之間的數(shù)決定參加交配的個(gè)體［3］.

5)子代交叉. 采用單點(diǎn)交叉算子，只有1 個(gè)交叉點(diǎn).從上一步篩選產(chǎn)生確定的交配個(gè)體中任意選取2 個(gè)作為交叉對(duì)象，在隨機(jī)產(chǎn)生的交叉點(diǎn)位置，2個(gè)個(gè)體交換部分基因碼，便產(chǎn)生2 個(gè)子個(gè)體.

6)子代變異.以一定的概率從群體中隨機(jī)選取若干個(gè)體，對(duì)選中的個(gè)體隨機(jī)選取某一位使其變異.

7)終止條件判斷.若t≤T，則t←t+1，轉(zhuǎn)到步驟2;若t ＞T，則以進(jìn)化過程中所得到的具有最大適應(yīng)度的個(gè)體為最優(yōu)解輸出，終止運(yùn)算［4］.

3 遺傳算法的建模及求解

3.1 條件分析及假設(shè)

1)假設(shè)給定坐標(biāo)之間的距離代表實(shí)際巡視距離.

2)假設(shè)每個(gè)作業(yè)點(diǎn)的巡視時(shí)間是固定不變的，不以線路的改變發(fā)生變化，研究重點(diǎn)考慮路程時(shí)間，以點(diǎn)與點(diǎn)之間的距離作為約束指標(biāo)進(jìn)行優(yōu)化.

3)模型中不考慮路程中除時(shí)間以外的其他因素，如公路收費(fèi)、道路狀況等，以空間上達(dá)到線路最優(yōu)來提高工作效率和降低成本.

4)編碼串中每一組坐標(biāo)代表與之相對(duì)應(yīng)的一個(gè)作業(yè)點(diǎn)，涉及到沿線巡視可取巡視目標(biāo)中多個(gè)相近的點(diǎn)來實(shí)現(xiàn).

3.2 工程實(shí)例

南水北調(diào)中線一期工程總干渠黃河北—羑河北段，起點(diǎn)位于河南溫縣穿黃工程末端，終點(diǎn)位于河南湯陰縣羑河倒虹出口，全段長(zhǎng)195.249 km，共劃分9個(gè)設(shè)計(jì)單元，布置各類建筑物335 座.選取溫博段總干渠一個(gè)設(shè)計(jì)單元為研究對(duì)象. 溫博段總干渠長(zhǎng)26.62 km，其中渠道長(zhǎng)25.34 km，各類建筑物共有41 座.溫博段總干渠分為3 個(gè)施工標(biāo)段，由3 家施工單位進(jìn)行施工，一家監(jiān)理單位監(jiān)督管理，監(jiān)理人員日常巡視點(diǎn)較多，現(xiàn)選取3 個(gè)標(biāo)段中16 個(gè)重要控制作業(yè)點(diǎn)(見表1)進(jìn)行優(yōu)化.

表1 南水北調(diào)中線總干渠黃河北—羑河北段溫博段部分作業(yè)點(diǎn)坐標(biāo)值

3.3 算法步驟

監(jiān)理機(jī)構(gòu)項(xiàng)目部經(jīng)度和緯度為(113.07°，34.94°)，給項(xiàng)目部編號(hào)為1，作業(yè)點(diǎn)依次編號(hào)為2，3，…，17，最后項(xiàng)目部再重復(fù)編號(hào)為18，建立.txt 文件，將表1中的數(shù)據(jù)按先經(jīng)度后緯度的次序輸入，便于MATLAB 程序?qū)胗?jì)算. 距離矩陣為D =(dij)18×18，其中dij表示i，j 兩點(diǎn)的距離，i，j =1，2，…，18，這里D 為對(duì)稱矩陣.上文中已經(jīng)給定各個(gè)作業(yè)點(diǎn)的地理坐標(biāo)，求解兩點(diǎn)之間的實(shí)際距離可采用歐氏距離計(jì)算方法:但此法忽略了地圖投影引起的差異，在這里采用球面距離來計(jì)算. 設(shè)任意P，Q 的地理坐標(biāo)分別為(x1，y1)，(x2，y2)，P，Q 兩點(diǎn)間的實(shí)際距離就是過兩點(diǎn)間的大圓弧劣長(zhǎng).建立平面直角坐標(biāo)系，以地心O 為坐標(biāo)原點(diǎn)，赤道平面為XOY 平面，0° 經(jīng)線圈所在的平面為XOZ 平面［5］.則P，Q 兩點(diǎn)的直角坐標(biāo)分別為:

地球半徑R = 6 370，種群大小M = 50，最大代數(shù)G = 1 000. 計(jì)算流程如圖1所示.

1)染色體編碼. 采用十進(jìn)制編碼，用隨機(jī)數(shù)列ω1，ω2，…，ω18作為染色體，其中0 ＜ωi＜1，(i = 2，3，…，17)，ω1= 0，ω18= 1;每個(gè)隨機(jī)序列都和種群中的某一個(gè)體相對(duì)應(yīng).編碼位置i 代表作業(yè)點(diǎn)i，位置i 的隨機(jī)數(shù)表示作業(yè)點(diǎn)i 在巡回中的順序.

2)產(chǎn)生初始種群.利用經(jīng)典的近似算法得到一個(gè)較好的初始群:π1，π2，…，πu－1，πu，πu+1，…，πv－1，πv，πv+1，…，π18，且2 ≤u ≤v ≤17，2 ≤πu≤πv≤17，交換u 和v 的位置可得新路徑，若新路徑小于舊路徑則以新路徑進(jìn)行修改，直到不能修改為止.

圖1 遺傳算法的流程圖

3)建立目標(biāo)函數(shù).將巡視所有目標(biāo)的路徑長(zhǎng)度作為目標(biāo)函數(shù)，也為適應(yīng)度函數(shù)，即minf(π1，π2，

4)子代交叉. 采用單點(diǎn)交叉，取交叉率pc=1.隨機(jī)選取第t 個(gè)基因處為交叉點(diǎn)，經(jīng)過交叉運(yùn)算后得到子編碼為s1和s2，s1的基因由f1的前t 個(gè)基因和f2的后18－t 個(gè)基因構(gòu)成，s2的基因由f2的前t個(gè)基因和f1的后18－t 個(gè)基因構(gòu)成.

5)子代變異.取pm=0.1，對(duì)選定變異的個(gè)體隨機(jī)取3 個(gè)滿足條件的整數(shù)，把前2 個(gè)數(shù)之間的基因插到第3 個(gè)數(shù)的基因后面.

6)父代選擇.選擇目標(biāo)函數(shù)值最小的M 個(gè)個(gè)體進(jìn)化到下一代，以此保證父代的優(yōu)良特征.

3.4 運(yùn)行結(jié)果分析

監(jiān)理巡視線路優(yōu)化運(yùn)行結(jié)果如圖2所示，顯示經(jīng)過程序搜索后最佳路線為:1→11→3→2→17→4→6→15→14→10→9→12→8→7→13→5→16→1，最短線路為43.54 km.

圖2 監(jiān)理巡視線路最終結(jié)果圖

［1］雷英杰，張善文，李續(xù)武，等.MATLAB 遺傳算法工具箱及應(yīng)用［M］.西安:西安電子科技大學(xué)出版社，2005.

［2］呂曉峰，李保剛.基于遺傳算法的航空彈藥保障人員優(yōu)化配置［J］.計(jì)算機(jī)與現(xiàn)代化，2011(10):11－14.

［3］卓金武. MATLAB 在數(shù)學(xué)建模中的應(yīng)用［M］. 北京:北京航空航天大學(xué)出版社，2011.

［4］汪安南，史安娜，張?jiān)?，?遺傳算法在水利工程施工進(jìn)度控制優(yōu)化中的應(yīng)用［J］.水利經(jīng)濟(jì)，2006，24(4):55－57.

［5］張喜，張全壽.基于實(shí)數(shù)編碼遺傳算法的空車流量分配優(yōu)化方法研究［J］. 系統(tǒng)工程理論與實(shí)踐，2006(11):130－138.