遺傳算法在多目標最佳路徑選取中的應用

王占武

遺傳算法在多目標最佳路徑選取中的應用

王占武

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

遺傳算法；最短距離；最優解

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

1　工程實例

有一測量船，要求從A（30，44）出發，經歷表1的所列各位置進行測量，最后回到A點，如何選擇行駛路線以達到行駛距離最近。

1.1染色體編碼

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

1.2種群初始化

1.3目標函數

目標函數即航行的路線長度，為此：

1.4交叉

1.5變異

變異是實現多樣性的一種手段，是全局尋優的保證，這里令變異率

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

（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　航行目的位置坐標

2　結語

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

［1］ 邊霞，米良. 遺傳算法理論及其應用研究進展 ［J］. 計算機應用研究，2010（7）.

［2］ 鄧亮，趙進，王新. 基于遺傳算法的網絡編碼優化 ［J］. 軟件學報，2009（8）.

［3］ 段玉倩，賀家李. 遺傳算法及其改進 ［J］. 電力系統及其自動化學報，1998（1）.

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

遼寧省交通高等專科學校遼寧沈陽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