遺傳算法在多目標(biāo)最佳路徑選取中的應(yīng)用

王占武

遺傳算法在多目標(biāo)最佳路徑選取中的應(yīng)用

王占武

遺傳算法是一種基于自然選擇原理和自然遺傳機(jī)制的尋優(yōu)算法，可經(jīng)過選擇、交叉、變異等操作尋找最優(yōu)解。隨著科技的不斷進(jìn)步，一些新的理論和方法在應(yīng)用研究中亦得到了迅速的發(fā)展，給遺傳算法增添了新的活力。遺傳算法的應(yīng)用研究已從初期的組合優(yōu)化求解擴(kuò)展到了更工程化的應(yīng)用方面。文章利用遺傳算法尋求測(cè)量船最短距離完成多目標(biāo)測(cè)量任務(wù)。

遺傳算法；最短距離；最優(yōu)解

遺傳算法是一類借鑒生物界的進(jìn)化規(guī)律演化而來的隨機(jī)化搜索方法。它是由美國(guó)的J.Holland教授在1975年首先提出，采用概率化的尋優(yōu)方法，得到最優(yōu)解。具體算法如下：首先確定種群的規(guī)模，然后進(jìn)行編碼，選取目標(biāo)函數(shù)，進(jìn)行交叉變異操作，從而得到最優(yōu)解。

1　工程實(shí)例

有一測(cè)量船，要求從A（30，44）出發(fā)，經(jīng)歷表1的所列各位置進(jìn)行測(cè)量，最后回到A點(diǎn)，如何選擇行駛路線以達(dá)到行駛距離最近。

1.1染色體編碼

編碼方法在很大程度上決定遺傳進(jìn)化的效率。在求解復(fù)雜問題上，二進(jìn)制編碼搜索空間會(huì)加大，進(jìn)化性能較差。本項(xiàng)目采用十進(jìn)制編碼，用隨機(jī)數(shù)列作為染色體，其中（1=2，3…101），第一個(gè)目標(biāo)和最后目標(biāo)為0，1。編碼位置i代表目標(biāo)，位置i的隨機(jī)數(shù)代表目標(biāo)i在航行中的順序。

1.2種群初始化

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

目標(biāo)函數(shù)即航行的路線長(zhǎng)度，為此：

1.4交叉

1.5變異

變異是實(shí)現(xiàn)多樣性的一種手段，是全局尋優(yōu)的保證，這里令變異率

利用遺傳算法最近的航行路線為：

（1，56，21，99，17，52，95，35，44，38，101，100，59，46，98，3，80，50，51，42，87，15，83，45，67，2，30，92，4，60，20，40，18，48，10，31，84，97，72，14，27，85，77，79，82，11，69，64，65，94，70，19，63，62，66，29，34，90，86，8，39，78， 88，57，47，23，58，81，26，25，68，7，22，71，37，32，13，24，49，28，61，16，91，41，4，73，33，9，36，43，93，55，54，76，75，12，53，89，96，6，102）

表1　航行目的位置坐標(biāo)

2　結(jié)語

遺傳算法具有良好的全局搜索能力，可以快速地將解空間中的全體解搜索出，而不會(huì)陷入局部最優(yōu)解，利用它的內(nèi)在并行性，可以方便地進(jìn)行分布式計(jì)算，加快求解速度。

［1］ 邊霞，米良. 遺傳算法理論及其應(yīng)用研究進(jìn)展 ［J］. 計(jì)算機(jī)應(yīng)用研究，2010（7）.

［2］ 鄧亮，趙進(jìn)，王新. 基于遺傳算法的網(wǎng)絡(luò)編碼優(yōu)化 ［J］. 軟件學(xué)報(bào)，2009（8）.

［3］ 段玉倩，賀家李. 遺傳算法及其改進(jìn) ［J］. 電力系統(tǒng)及其自動(dòng)化學(xué)報(bào)，1998（1）.

［4］ 改進(jìn)免疫遺傳算法用于圖像閾值分割 ［J］. 河南科學(xué)，2012（1）.

遼寧省交通高等專科學(xué)校遼寧沈陽110122

Application of genetic algorithm in multi objective optimal path selection

Wang Zhanwu

Genetic algorithm is a kind of optimization algorithm based on natural selection principle and genetic mechanism，which can find the optimal solution through selection，crossover，mutation and so on. With the continuous progress of science and technology，some new theories and methods in the application of the research has also been in rapid development，which adds new vitality to the genetic algorithm. The application of genetic algorithm has been extended to the engineering application. In this paper，genetic algorithm is used to find the shortest distance of the ship to complete the multi-objective measurement task.

genetic algorithm；shortest distance；optimal solution

TP 21

A