文档介绍：基于改进型遗传算法的TSP算法
马明智
摘要本文基于传统的遗传算法,在变异步骤中采取精英策略的思想,保留最优秀个体,将其存入系统全局变量中,后面的每一代依旧重复此操作,确保系统最终得到的最优解是整个遗传操作过程中出现过的最优解。
关键词变异;遗传算法;精英策略
1 引言
现代社会虽然交通发达,两地之间有时甚至可以转瞬既至,但路径问题仍是当今算法界中比较热门的话题,也是一门比较实用的话题,比如现在的导航设备中的导航路线,在现代繁华的大都市中,找寻到一条可行且路程较短的路线并不是一件容易的事,因此为了满足人们的需求,各种搜寻软件应运而生,如,google的map等。
路径问题中一个经典的问题是旅行商问题,也证实了旅行商问题是NP难题,虽然旅行商现在已经拥有了各种解法,结果也很好,但仍是业界追捧的一大话题。本文也是基于旅行商问题来进行研究。
遗传算法GA( ic algorithm) 最早由美国密歇根大学的John Holland 提出。具有自组织、自适应、自学习和群体进化功能有很强的解决问题的能,在许多领域都得到了应用。
遗传算法以其广泛的适应性渗透到研究与工程的各个领域,已有专门的遗传算法国际会议,每两年召开一次,如今已开了数次,发表了数千篇论文,对其基本的理论、方法和技巧做了充分的研究。今天,遗传算法的研究已成为国际学术界跨学科的热门话题之一。
旅行商是一个古老且有趣的问题它可以描述为:给定n个城市以及它们之间的距离dij(城市i到城市j的距离),求解从其中一个城市出发对每个城市访问,且仅访问一次,最后回到出发的城市,应当选取怎样的路线才能使其访问完所有的城市后回到初始的城市且走过的路程最短。
旅行商问题已被证明是属优化组合领域的NP难题,而且在现实中的许多问题都可以转化为旅行商问题来加以解决。解决旅行商问题最一般的方法就是枚举出所有可能的路线然后对每一条进行评估最后选取出路程最短的一条即为所求解。
解决旅行商问题的各种优化算法都是通过牺牲解的精确性来换取较少的耗时,其他一些启发式的搜索算法则依赖于特定的问题域,缺乏通用性,相比较而言遗传算法是一种通用性很好的全局搜索算法。
2 遗传算法优缺点
任何一种算法都不可能十全十美,遗传算法依旧如此,它的优势是可以从多点出发,在解空间内搜寻最优解,而缺点同样较大,首先在编码上,传统的遗传算法是用二进制来编码的。下面从不同角度来对传统的遗传算法的优劣进行分析。
(1)遗传算法优点
不是从单个点,而是从多个点构成的群体开始搜索。之所以说是从多点而不是从单点出发,那是因为整个算法的开始是从一个初始种群开始搜索演练最优解,是从多个点开始搜索进化寻找,这样的做的一个好处是避免局部寻找最优解,从任一解出发,按照某种机制,以一定的概率在整个求解空间中探索最优解。由于它们可以把搜索空间扩展到整个问题空间,因而具有全局优化性能。同时也缩短了整个搜寻额时间,整体上效率更高、结果更接近最优解。
实现简单,没有复杂的数学计算,在算法中,一般都有大量且复杂的计算作为整个算法的支撑,同时数学计算也是一步比较耗资源和时间的操作,然后在遗传算法中,在搜索最优解过程中,只需要由目标函数值转换得来的适应度信息再加上简单的比较,而不需要导数等其它辅助信息,操作流程也比较简单,没有过多的转换控制操作,中间也没有多少中间变量,算法具有较强的自适应性。
搜索过程不易陷入局部最优点。目前,该算法已渗透到许多领域,并成为解决各领域复杂问题的有力工具,因为是在整个求解空间中探索最优解,所以,基本上不会陷入局部最优解中去。
在遗传算法中,将问题空间中的决策变量通过一定编码方法表示成遗传空间的一个个体,它是一个基因型串结构数据;同时,可以将目标函数值转换成适应值,它用来评价个体的优劣,并作为遗传操作的依据。
但是,传统的遗传算法同样拥有缺陷。
(2)遗传算法缺点
首先,传统的遗传算法编码和解码比较复杂,因为传统的遗传算法的染色体是用二进制编制的,一个染色体就是一串0和1组成的位串或是字符串,在进化前需要做复杂的编码工作,而在得到最优解后还要做复杂的解码工作,比较繁琐和复杂,在遗传操作过程中也不易掌控,容易出错;
其次,算法对初始种群的选择有一定的依赖性。
(3)遗传算法应用领域
遗传算法在人工智能的众多领域便得到了广泛应用[2]。例如,机器学习、聚类、控制(如煤气管道控制)、规划(如生产任务规划)、设计(如通信网络设计、布局设计)、调度(如作业车间调度、机器调度、运输问题)、配置(机器配置、分配问题)、组合优化(如TSP、背包问题)、函数的最大值以及图像处理和信号处理等等。
另一方面,人们又将遗传算法与其他智能算法和技术相结合,使其问题求解能力得到进一步扩展和提高。例如,将遗传算法与模糊技