论文部分内容阅读
遗传算法是一种模仿生物自然进化过程的、自适应启发式的全局优化算法。由于在利用遗传算法求解问题时仅需要很少的辅助信息,容易与其它领域的知识相结合,且具有较好的自适应性和并行性,使得遗传算法在组合优化、机器学习、自适应控制、人工生命等领域得到了广泛的应用。虽然国内外都很重视遗传算法的理论和应用研究,并取得了很多令人瞩目的研究成果,但是遗传算法的理论和方法还尚未成熟,仍然存在一些不足有待于进一步改善。首先,本文以遗传算法在函数优化中的应用为实例,分析了遗传算法优化过程中基因编码相同的染色体重复出现的现象,且随着进化代数的不断增加重复个体出现的机率也越来越大。针对这个问题,本文通过引入合适规模的基因库用以存储重复出现个体的基因编码和对应的适应度值,并将基因库中的染色体按适应度值从大到小的顺序有序排列。对于基因库中有相同基因编码的染色体可以直接从基因库中获取其适应度值,进而解决重复个体适应度值的重复计算问题,降低算法的时间复杂度,提高算法的计算效率。其次,针对上述算法无法根据当前种群中个体的分布情况对遗传算子执行的控制参数进行动态调整的问题,本文按照自适应遗传算法的交叉概率和变异概率调节公式的设计原则,根据种群中个体的相似系数,利用Logistic曲线方程对遗传算法的交叉概率和变异概率进行自适应调整,进而提高算法的收敛性能。最后本文以典型的旅行商TSP问题为应用背景,以Malab R2009a和Microsoft Visual Studio2010作为开发环境,选取TSPLIB中的城市坐标数据为实例,实现了一个基于改进后算法的TSP问题求解系统,并对改进后算法的计算个体适应度值的时间代价与算法的收敛性进行测试和验证。测试结果表明:种群规模为50~150,基因库规模选取为种群规模的0.1倍~0.2倍时,本文算法能够有效地减少算法的时间复杂度,其加速比能够达到49.70%左右。在算法的收敛性方面,本文改进后的算法收敛速度快于基本遗传算法但稍慢于Srinivas等人提出的自适应遗传算法,且收敛效果要好于其它两种算法,其所得解与TSPLIB提供的最优解的平均相对误差最大不超过9.38%。