遗传算法在多目标最佳路径选取中的应用

王占武

遗传算法在多目标最佳路径选取中的应用

王占武

遗传算法是一种基于自然选择原理和自然遗传机制的寻优算法，可经过选择、交叉、变异等操作寻找最优解。随着科技的不断进步，一些新的理论和方法在应用研究中亦得到了迅速的发展，给遗传算法增添了新的活力。遗传算法的应用研究已从初期的组合优化求解扩展到了更工程化的应用方面。文章利用遗传算法寻求测量船最短距离完成多目标测量任务。

遗传算法；最短距离；最优解

遗传算法是一类借鉴生物界的进化规律演化而来的随机化搜索方法。它是由美国的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