遗传算法是一种概率搜索算法,其基本思想是模拟生物进化过程。由于遗传算法具有不受搜索空间的限制性假设的约束,不要求解空间有连续性、可导等性质,且固有并行性,目前它在许多领域得到了广泛的运用。 组合优化(combinatorial optimization)研究那些含有有限个可行解的、日常生活中(尤其是工程设计中)大量存在的问题。典型的组合优化问题包括:旅行商(TSP)问题、车间流水作业调度问题等。本文主要研究对遗传算法的改进算法及这些改进算法在组合优化上的应用。 本文对遗传算法的理论、优化及应用进行了一些研究与分析工作。首先,介绍了遗传算法基础原理——模式定理,并分析了其在一维染色体编码方案上的适用性:其次介绍了遗传算法的理论基础,对诸如:未成熟收敛、遗传漂移及如何保持种群的多样性等有关问题作了探讨;同时介绍了一些常见的改进方法,诸如:混合遗传算法、基于基因库的改进遗传算法、自适应遗传算法和小生境技术和共享函数等。针对标准遗传算法中初始种群产生的随机性,在借鉴基因库思想的基础上,本文提出了一种基于基因库的模拟退火混合遗传算法。这种改进遗传算法具有以下优点: 1.基于基因库和单亲遗传算法生成的初始种群。单亲遗传算子使用了基因库中的优质基因,使得初始种群中个体具有的优质基因比随机产生个体的优质基因要多,种群中每个个体都十分接近最优个体。因此,它们在种群演化较易产生最优解。 2.利用模拟退火算法较强的局部搜索能力,加快了算法的收敛速度,同时也提高了得到的全局最优解的可靠性。 同时,将这种改进算法应用于求解经典的货郎担(TSP)问题;试验结果表明:改进算法具有更好的收敛性,而且算法收敛速度快、收敛稳定性更好;且得到了目前该问题的最优解。 在上述改进的基础上,针对标准遗传过程中交叉概率和变异概率固定不变所带来的局限性,本文进一步提出了一种基于基因库的自适应遗传算法:使遗传过程中遗传算子能根据种群的集中程度自适应变化。这种改进遗传算法具有以下优点: 1.基于基因库和单亲遗传算法生成的初始种群中每个个体都十分接近最优个体,它们具有的优质基因比随机产生个体的优质基因要多,种群演化较易产生最优解。 2.遗传过程中遗传算子根据适应值集中程度,自适应地变化;确保了种群向性能好的方向演化,因此加快了算法的收敛速度。 同时,还将这种改进算法应用于求解流水作业排序问题;试验结果表明:改进算法在收敛速度、收敛稳定性上有了较大改进:并在执行效率上比改进前的算法有了显著的提高。最后,利用压缩映射原理和有限Markov链原理分别对两种改进算法进行了收敛性分析。