1995年：遗传算法优化TSP问题的创新方法

本文主要探讨了1995年12月发表在《北方交通大学学报》上的一篇论文，题目为"遗传算法用于TSP问题的研究"。该研究关注的是旅行商问题(Traveling Salesman Problem, TSP)，这是一种经典的组合优化问题，旨在找到一条遍历所有n个城市且仅访问一次的最短路径。作者廖晓明和罗四维利用遗传算法这一搜索方法，结合爬山搜索法的思想，提出了一种新的遗传算子，以解决TSP问题。 遗传算法是一种基于自然选择和遗传机制的计算搜索技术，它模仿生物进化过程，通过一代代的变异、交叉和选择操作，逐步优化解决方案。在TSP问题中，编码方式是用n个数码表示n个城市，形成一个位串（染色体），同时需要确保每个城市只访问一次，这就需要特殊的约束条件，如避免重复数码。 适值函数的选择是关键，作者选取了一个与路径总路程相关的函数，即f=1-C/Cmax，其中C是路径的总路程，而Cmax是一个预估的最大可能路程。这样做的目的是确保适值函数非负且随着路径长度减小而增大。 论文中提及的交叉算子是遗传算法的核心部分。传统的交叉方法可能会导致非法位串，即某些城市被访问多次或遗漏。为了解决这个问题，作者提出了一种改进的交叉算法：首先确保两个交叉的位串在交叉部分具有相同的数码；如果不同，就需要在其中一个串内进行交换，以确保约束条件的满足。 这篇论文通过结合遗传算法和爬山搜索法，提出了一个有效解决TSP问题的新方法，并通过实验验证了其显著的优化效果。这种研究不仅提升了TSP问题求解的效率，也为遗传算法在优化问题中的应用提供了新的视角。文章还被分类在TP301.6类别下，反映了其在计算机科学特别是运筹学领域的学术价值。