指针网络改进遗传算法求解旅行商问题

关键词：指针网络;遗传算法;旅行商问题

中图法分类号：TP301 文献标识码：A

遗传算法作为一种最优化算法，其主要通过模拟自然界物种的进化过程和规律，并根据模拟物种进化的过程实现基因的交叉互换和变异等过程，最终生产新的个体甚至种群。从理论上看，遗传算法的持续优化会使下一代个体或者种群的性能明显优于上一代。但从现实情况看，受种群基因质量的影响，通过遗传算法生成的个体或者种群在质量上并不完全是直线上升的。换言之，遗传算法会受其他因素的影响而出现性能和寻优速度下降的情况。因此，需要根据情况对遗传算法进行改进。指针网络作为一种能从离散输入序列中获取输出序列条件概论的神经网络，在改进遗传算法中的种群因素、提高预测的准确度等方面具有明显的效果。本文重点以求解旅行商问题为载体，对指针网络改进遗传算法进行相应的研究。

1旅行商问题概述

旅行商问题是涉及计算机科学、工程学、数学、运筹学等诸多学科的一项基础性问题。该问题是指一位旅行商需要到n个城市去推销自己的产品，要求从某一城市出发，经过n-1个城市，并且经过这些城市的次数只能是一次，最后再回到出发城市，要求解的问题是旅行商的最短路程。

关于求解旅行商问题，通常情况是将旅行商的最短路径作为目标函数，将除出发城市外，其余n-1个城市必须经过且只能经过一次作为约束条件。在现实生活和社会发展中，类似旅行商问题的情况比较常见，这也使得关于这一典型问题的研究成为各类算法研究与应用中重点关注和探索解决的问题。

2遗传算法求解旅行商问题的方法

传统基于遗传算法求解旅行商问题的流程如图1所示。从原理上看，遗传算法是在模拟达尔文的遗传选择和自然淘汰规则的基础上产生的生物进化过程计算模型，其是一种通过模拟自然进化的过程来探索确定最优解的方法。在一般的算法应用中，遗传算法的实现主要包括城市生成模块、地图选择模块、参数设置模块、交叉算子选择模块、变异算子选择模块、具体输出信息显示模块。其中，城市生成模块主要是生成旅行商问题中涉及的城市数量和城市名称或者代码;地图选择模块是根据问题研究的需要，选择不同的地图，并对各个城市在地图上的分布情况进行确定。目前使用得比较多的地图是基于直角坐标系的地图和圆形地图;参数设置模块是用户根据具体的研究情况，设置遗传算法应用中的相关参数，这些参数主要包括交叉率、变异率、种群大小、世代数、进化设置等;交叉算子选择模块主要是用户根据研究的需要，选择相应的交叉算法;变异算子选择模块主要是在基于次序的变异、基于位置的变异和倒位变异这三种变异实现方式中进行选择;具体输出信息限制模块是为了使程序运行时具体算法和各种数据信息能够更明晰地显示出来而设置的输出方式，一般显示的信息主要有计算结果、算法运行时间、所选遗传算子等。

虽然遗传算法能够达到取得最优值或者次优质的预期目的，但由于该算法容易受种群等情况的影响而出现陷入局部最优和收敛速度慢等问题，最终可能会影响旅行商问题求解的效果。

3指针网络改进遗传算法求解旅行商问题的方法

基于指针网络改进遗传算法求解旅行商问题，是将指针网络引入遗传算法中的初始种群的改造，使遗传算法能够更准确地学习组织优化问题的组合规则。在此次研究中，主要将指针网络应用到遗传算法的初始化方案中，以此改善遗传算法的初始种群构造，提高整个算法的性能。

4基于指针网络改进遗传算法应用的流程

图2展示的是基于指针网络改进遗传算法的具体应用流程。通过该图可以看出，改进后的遗传算法主要包括四个重要的步骤———即生成高质量初始种群、形成新初始种群、改进初始种群构造结构和进行自适应处理。其中，改进初始种群构造结构是指针网络应用的关键，在该环节，主要包括最优子代融合和基于汉明距离轮盘赌进行初始种群结构优化。

在最优子代融合中，通过图2可以看出，需要首先生成初始种群S和指针网络解集T，然后对S和T分别进行个体适应度的计算，保留优良的个体，最后对S和T分别取适应度最高的子集加入新解集中。

在将适应度最高的子集加入新解集中时，可以按照特定的权重进行处理，以保证最大程度保留指针网络解集T中的个体的优势。

在基于漢明距离轮盘赌的过程中，主要使用汉明距离来测量个体之间的差异，其根据两个长度相等的字符串中，对应位置不相同的个数来确定距离值。在此次求解旅行商问题中，假设两个个体X₁和X₂之间的韩明距离为rH（X₁，X₂）。需要注意的是，为掌握种群之间的多样性，需要对种群中每个个体之间的汉明距离进行计算，最后计算中种群的平均汉明距离，其计算公式如下。

在按照上述公式计算出汉明距离后，即可将剩余个体中距离最短的个体加入初始解集中。

5结语

旅行商问题作为一项经典的算法问题，其在现实生活中的行为决策方面具有普遍的代表性。由于基于传统遗传算法在求解旅行商问题方面存在缺陷和不足，本次研究提出了基于指针网络改进遗传算法的思路，并以求解旅行商问题为案例进行了研究。最终的研究结果表明，在求解旅行商问题中，指针网络能够在中低规模的旅行商模拟数据中获得高准确度的结果。并且，基于指针网络改进的遗传算法可以显著提高求解的质量和收率速度，这较同类型的初始化方法具有更明显的特点和优势。因此，可以确定的是基于指针网络改进的遗传算法在求解旅行商问题方面的效果突出。

作者简介：

沈涤（1973—），硕士，工程师，研究方向：人工智能、多媒体、GIS。