本文由三个部分组成,第一部分是对研究背景的介绍,给出了最优化问题的描述,概括了求解最优化问题的数学方法和演化计算方法。第二部分是对遗传算法的研究:对传统的遗传算法进行了简要的分析,介绍了一些改进的遗传算法,在此基础上,提出了一种基于相似性的遗传算法。第三部分是遗传算法的应用实践:将所设计的算法应用到代表性的旅行商问题(Traveling Salesman Problem,简称TSP)和车间调度问题,并将结果与传统的方法进行比较,结果显示本文设计的算法表现出了良好的性能。本文的主要工作和创新点: 1、定义了距离、相似性和邻域等概念,用距离反映个体间的差异程度,用相似性描述个体间的类似程度,用邻域实现对种群的划分。 2、在新解的产生过程中引入了分级策略,对种群按照适应值进行划分,对处于不同级别的个体采用不同的遗传操作,使得个体在相似性的指导下产生新解,避免了新解产生的盲目性,从而使得子代较好继承了父代的优势特征。此外,用一定概率保留较差个体和对于重复个体用随机产生的个体替换保证了种群的多样性。从而使算法的效果和效率达到较好的平衡。为了使算法更快地搜索到最优解,还设计了加速算子。 3、提出了一种基于相似性的遗传算法。将该算法运用到TSP问题中,其中结合了TSP问题的特点,定义了TSP问题的距离、相似性和邻域等并设计了符合TSP问题的加速算子。数值实验表明该算法收敛速度快,结果也较好。 4、对TSP问题进行了综述。介绍了TSP问题的历史和研究现状、数学模型、时间复杂度、评价标准。然后以综合性能的角度对解TSP算法进行了一定的归纳和分析。最后介绍了遗传算法求解TSP问题的研究进展。