猎潜算法及其在TSP问题中的应用2

来源：核心期刊咨询网时间：12

摘要：1、算法思想直升机在大海中搜索潜艇时，先在海中投放若干个声纳（侦测点），然后根据每个声纳的信号强弱找出离潜艇最近的点，将此点作为基点，再在它周围继续投放新的侦测点，再将信号最强的侦测点作为基点继续侦测，周而复始，直至找到潜艇。本文算法将在搜

1、算法思想直升机在大海中搜索潜艇时，先在海中投放若干个声纳（侦测点），然后根据每个声纳的信号强弱找出离潜艇最近的点，将此点作为基点，再在它周围继续投放新的侦测点，再将信号最强的侦测点作为基点继续侦测，周而复始，直至找到潜艇。本文算法将在搜索空间中搜索最优解的过程看作搜索直升机的过程，即先随机产生若干候选解，然后将适应度最高的侯选解作为基点，再对基点进行突变，找到优于基点的新解，将此新解作为新的基点进行新轮搜索，直到找到最优解或满足中止条件为止。具体算法描述如下：1）随机生成若干候选解；2）计算各候选解适应度值；3）确定基点（适应度最大的）；4）根据搜索历史确定搜索方向；5）在指定搜索方向上对基点进行突变，产生新解；6）计算新解适应值；7）如果优于基点，返回第3步执行，将新解作为基点开始新一论搜索；8）是否符合终止条件？如不符合返回第4步，继续突变；9）如果符合终止条件，中止运行，当前基点即为本算法最优解。为证明算法的有效性，本文对两个经典应用进行了实验。一是TSP问题，二是智能组卷问题。前者已提出300多年，到目前尚无高效方法。智能组卷问题也有近50年的历史，但也未找到有效方法，应用本算法以后，该问题得以较好地解决，具体可参见文献[1]。2、TSP问题及常见求解算法旅行商问题(TSP) 是一个组合问题: 给定n 个城市两两之间的距离，要求确定一条从某一城市出发，经过各城市一次且只能经过一次，最后回到出发地的最短路线。TSP问题是典型的N P难题, 也是现在众多算法性有效性的首选问题。这一问题对物流配送，车辆调度，管道铺设等实际应用有指导意义。常见的TSP算法大至分精确算法和近似算法两大类，但精确算法的时间复杂度大，难以实际运用[2]。近似算法分启发式算法和智能优化算法，且启发式算法时间复杂度低，易限入局部最优解，而智能优化算法随着研究的深入，虽然人们采取了很多方法避免限入局部最优解，但也只能“求得一定精度内的近似完美解,在合理的运行时间内使其更接近完美解”[3]。3、猎潜算法在解决TSP问题中的应用(1) 突变算子所谓突变，是将路径中的某一个点（城市）或随机、或按一定的规律，与路径中的另一个点（城市）互换位置。如设现有路径Path(1,3,8,4,2,5,6,7,1)，根据某种方法，要对其中的第三个点（8）进行突变，用城市5代替，则最终的结是为Path(1,3,5,4,2,8,6,7,1)突变可以采用最短边法、较短边法、随

转载请注明来自：http://www.qikan2017.com/lunwen/dzi/443.html