免疫遗传算法及其在tsp中的应用的研究

《免疫遗传算法及其在tsp中的应用的研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、分类号：TP312密级：公开UDC：单位代码：10424学位论文免疫遗传算法及其在TSP中的应用研究代冉申请学位级别：硕士学位专业名称：计算机软件与理论指导教师姓名：路燕职称：副教授山东科技大学二零零八年五月论文题目：免疫遗传算法及其在TSP中的应用研究作者姓名：代冉入学时间：2005年9月专业名称：计算机软件与理论研究方向：数据库理论指导教师：路燕职称：副教授论文提交日期：2008年5月10日论文答辩日期：2008年6月12日授予学位日期：RESEARCHONANIMMUNEGENETICALGORITHMAND

2、ITSAPPLICATIONONTSPADissertationsubmittedinfulfillmentoftherequirementsofthedegreeofMASTEROFPHILOSOPHYfromShandongUniversityofScienceandTechnologybyDaiRanSupervisor:AssociateProfessorLuYanCollegeofInformationScienceandEngineeringMay2008声明本人呈交给山东科技大学的这篇硕士学位论文，除了所列参考文献和世所公认的

3、文献外，全部是本人在导师指导下的研究成果。该论文资料尚没有呈交于其它任何学术机关作鉴定。硕士生签名：日期：AFFIRMATIONIdeclarethatthisdissertation,submittedinfulfillmentoftherequirementsfortheawardofMasterofPhilosophyinShandongUniversityofScienceandTechnology,iswhollymyownworkunlessreferencedofacknowledge.Thedocumenthasnotbee

4、nsubmittedforqualificationatanyotheracademicinstitute.Signature:Date:山东科技大学硕士学位论文摘要摘要遗传算法（GA）是一种模拟自然界生物进化的搜索算法，由于它简单易行、鲁棒性强，尤其是不需要专门的领域知识而仅用适应度函数作评价来指导搜索过程，从而使它的应用范围极为广泛。但是在遗传算法的实际工程优化应用中，常常存在早熟收敛、局部搜索能力不足和收敛速度慢的问题。本论文在深入研究这些问题的基础上，提出以下几点创新性工作：（1）借鉴生物免疫系统的某些优良特性，结合人工免疫算法

5、（AIA），提出了一种新的基于疫苗免疫浓度调节机制，融合了免疫记忆、多样性保持、自我调节、新陈代谢等功能的免疫遗传算法（IGA）框架，并对其性能进行理论分析，包括Markov链全局收敛性分析和模式增长分析。证明了保留最优个体的免疫遗传算法以概率1收敛到全局最优解；提出平均浓度阈值的概念，得出IGA模式定理，可知免疫操作使优良模式的增长速度加快。将提出的免疫遗传算法框架应用到旅行商问题（TSP）问题中，通过MATLAB仿真实验对TSPLIB标准测试库中的城市数据进行对比测试，仿真结果表明IGA在寻优结果和收敛速度方面均优于GA，验证了算法的可行

6、性和有效性；并定义了多样性评价函数，仿真结果验证了IGA的多样性保持能力，从而克服了GA早熟收敛和容易陷入局部最优的缺陷。（2）针对基于信息熵的AIA运行速度慢的缺陷，分析了影响其运行速度的原因，深入研究了信息熵的计算过程，提出了一种加速群体信息熵计算的方法，并进行了数值仿真实验。实验结果表明，基于改进方法构造的信息熵的人工免疫算法，其运行速度得到了大幅度提高。（3）针对TSP的特点，结合启发式交叉（HX）中的贪心思想和边重组交叉（ER）中的双向边思想，提出一种新的交叉算子——双向边贪心交叉算子（DEGX）。仿真实验表明，DEGX的寻优结果和

7、收敛速度均优于HX和ER，有效地增强了局部搜索能力，使收敛速度加快。关键词：遗传算法（GA），人工免疫算法（AIA），免疫遗传算法（IGA），信息熵，TSP山东科技大学硕士学位论文摘要AbstractGeneticAlgorithm(GA)isakindofsearchalgorithmwhichsimulatesnaturalbiologicalevolution.Itissimple,strongrobustandeasytoimplement,especiallyitdoesn’tneedthespecialknowledge,but

8、onlytodirectthesearchprocesswithfitnessfunction,soithasbeenusedinmanybroadfields.B