改进免疫遗传算法在组合优化问题中的应用研究

摘要

一方面,随着计算机技术的发展,遗传、蚁群等启发式算法得到了广泛的应用。另一方面,随着近代工业的发展,如何更好的求解组合优化问题不仅成为学术界研究热点,而且会带来不可估量的的经济效益。本文在立足于前人研究的基础之上,在遗传算法求解组合优化问题方面进行研究,通过对遗传算法进行改进,力求得出组合优化问题的全局最优解。本文尤其结合实际应用中较多的CVRP、FJSP问题的具体算例进行具体研究。对改进的遗传算法的效果进行验证。本文共分以下六个章节逐层递进研究:
　　 第一部分:概括介绍本文的研究背景和研究意义,现阶段国内外遗传算法及其组合优化问题的研究现状,进而阐述研究的主要内容和方法。
　　 第二部分:介绍遗传算法、免疫遗传算法的基本原理、基本概念、运行流程、存在的问题以及免疫遗传算法的生物学原理并介绍了其它解决组合优化问题的常用的方法。
　　 第三部分:针对本文提出的两种改进遗传算法,自适应和克隆选择的免疫遗传算法,对其原理、操作流程、基本公式等进行了全面、详尽的介绍和分析。是本文的一个重点。
　　 第四部分:承接第三部分,结合CVRP问题的典型算例对克隆选择免疫遗传算法求解CVRP问题进行了实例验证。
　　 第五部分:承接第三部分,结合FJSP问题的典型算例对自适应免疫遗传算法求解FJSP问题进行了实例验证。
　　 第六部分:总结本文研究工作,得出结论,并对未来的研究工作进行展望。
　　 本文在基本遗传算法的基础上提出了克隆选择的免疫遗传算法和自适应的免疫遗传算法分别用于求解CVRP和FJSP问题。其中,克隆选择的免疫遗传算法通过克隆增值的方式避免了交叉过程中产生的不符合编码规则的现象。并通过高频的倒位操作的变异方法提高了个体变异的频率,从而避免算法陷入局部最优。另外,本方法通过免疫注射和提取疫苗的方法使得种群高效进化。自适应的免疫遗传算法采用了动态的自适应提取疫苗的策略,根据种群的相似度自适应的得出种群交叉和变异概率。