基于免疫算法的TSP问题求解..docVIP

基于免疫算法的TSP问题求解 摘要：TSP问题(Traveling Salesman Problem )是一个典型的组合优化问题，有效地解决 TSP 问题在可计算理论上有着重要的理论价值，本文介绍了一种基于免疫算法的解决TSP问题的方法，体现了免疫算法在进化计算过程中的抗原学习、记忆机制、浓度调节机制以及多样性抗体保持策略等优良特性，这使得免疫算法有较强的收敛性和较好的求解结果。 关键词：TSP、免疫算法、记忆机制、抗体 Solving The TSP Problem Based on Immune Algorithm Abstract： The TSP (Traveling Salesman Problem) is a typical combinatorial optimization problem effectively solve the problem in computability theory TSP has important theoretical value, this paper presents a method to solve the TSP immune algorithm based on immune algorithm reflects antigen learning process of evolutionary computation, memory mechanism, the antibody concentration was adjusted to maintain the diversity of mechanisms and strategies of excellent features, which makes it immune algorithm has strong convergence and better solution results. Keywords：TSP,Immune Algorithm,Memory mechanism,Antibody 1.引言 近年来，越来越多的学者把生物免疫系统的一些行为引入到传统的仿生算法中，构造出的免疫算法可以大大提高传统仿生算法的效率。生物免疫系统的免疫功能是通过抗体消灭入侵的病原体的（抗原）来实现的，人工免疫算法就是模拟生物免疫系统的这一功能实现的。TSP问题是典型的组合优化问题，本文描述了免疫算法中的一种框架结构，该算法在进化计算过程中的抗原学习、记忆体制、浓度调节机制和抗体多样性保持策略都有着优良特性，加快了求解的效率，更有效的避免了在进化过程中的未成熟收敛，表明了免疫算法在解决组合优化问题时的优良性能。 2.免疫算法 2.1免疫算法的生物学基础 生物免疫系统是由某些特殊的化学分子、细胞、组织、器官组成的分布式复杂自适应系统。免疫系统的主要功能是区分体内所有的细胞或分子是否对身体有害，并对有害的物质进行清除。 生物免疫过程：生物体内具有针对不同抗原特性的多样的B细胞，抗原侵入机体后，在T细胞的识别和控制下，选择并刺激相应的B细胞系，使之分化、复制产生特异性抗体与对应的抗原相结合。免疫记忆则是指免疫系统在对侵入的抗原产生抗体之后，会将抗体作为记忆细胞保存下来，当同类抗原再次入侵时，会快速产生大量抗体，缩短了免疫反应的时间。并且在免疫反应过程中，产生大量的抗体之后，抗原对免疫细胞的刺激减小，从而抑制了抗体的继续产生，同时产生的抗体之间也存在着相互制约的关系，这种相互制约的关系保证了机体的免疫平衡。免疫系统有很强的自适应性，入侵的抗原有性异物对于免疫系统来说具有不可预知性，免疫系统无法预先产生抗体来对付抗原。但是免疫系统会有一个自适应的机制来保证初次应答的成功，并通过免疫记忆细胞的产生，使得二次应答更加地高效。 2.2免疫算法的描述 免度算法是抽取和反映生机体免疫系统的上述特点，结合工程应用而描述的一种计算模型，抗原对应于待求解的问题，而抗体则对应于问题的一个解。免疫算法的结构如图1所示。 图1 免疫算法结构框图 算法的主要步骤如下： 步骤 1 抗原产生：最优化问题的目标函数和约束条件的描述。 步骤 2 初始抗体产生：把抗体定义为目标函数在约束条件下的可行解。 步骤 3 亲和力计算：计算解群中每一个解的亲和力或者适应度，并为后面的记忆细胞的产生提供依据。 步骤 4 产生记忆细胞：按亲和度的高低进行排序，从中选择亲和度较高的个体构成新的群体,取前几个抗体构成记忆库。 步骤 5 抗体的促进和抑制：计算抗体的浓度，并结合前面的抗体适应度来确定抗体的死亡和分裂的概率。 步骤 6 群体更新：利用交叉和变异算子对抗体进行进化更新。 步骤 7 终止条件判断：判断是否满足终止条件(找到最优解或达到最大迭代次数) ：是则算法