用于组合优化的人工免疫算法设计与分析

摘要

克隆选择算法是人工免疫系统领域中的重要算法之一。作为克隆选择算法中重要的算子，元动力学算子很少受到关注。另一方面，进化非选择算法是基于生物免疫进化机制和免疫非选择机制而提出的一种新的算法，可应用于组合优化和异常检测等问题。但是，迄今为止，尚未有相关文献专门研究用于组合优化问题的进化非选择算法的时间复杂度。
　　 本文主要针对人工免疫系统中的这两个算法进行研究，具体工作包括以下几个方面。
　　 (1)从实验角度分析和讨论了不同元动力学策略对于克隆选择算法性能的影响。传统的元动力学策略是对二进制染色体中的每一位，以相同的概率生成0或者1。然而，对于有些问题，这种元动力学策略实际上并不能真的增加种群的多样性。例如，该问题的解与0或者1的个数有关，而与0或者1在二进制染色体中的位置没有关系的时候。因此，本文提出了三种新的元动力学策略。针对上面所提到的这类问题，这三种元动力学可以很明显的起到均匀采样的作用。实验结果表明，本文提出的这三种元动力学策略在这一类问题上具有较好的性能。
　　 (2)基于一个典型的组合优化问题，对比分析了采用不同匹配阈值的进化非选择算法在该问题上的平均时间复杂度。理论分析和实验结果表明，有合适匹配阈值的进化非选择算法的性能优于传统进化算法的性能。由此可知，非选择算子对于提升进化类算法的性能有重要作用。
　　 (3)一方面，有合适匹配阈值的进化非选择算法的性能优于传统进化算法的性能。另一方面，当匹配阈值不合适时，进化非选择算法的性能未必优于传统进化算法。为此，本文进一步分析和讨论了，匹配阈值在一定范围内变化时，进化非选择算法的性能会有怎样的变化。理论结果和实验结果表明，合适的匹配阈值在常数范围内变化时，进化非选择算法的性能仍然优于传统进化算法；而当不合适的匹配阈值在常数范围内变化时，进化非选择算法的性能未必优于传统进化算法的性能。
　　 总的来说，本文首先提出了三种新的元动力学策略，分析了元动力学算子对克隆选择算法性能的影响。然后，分析了进化非选择算法在一个组合优化问题上的平均时间复杂度，以及匹配阈值对进化非选择算法性能的影响。本文的研究成果不仅对用于组合优化问题的人工免疫算法设计具有重要意义，而且对人工免疫算法的理论分析和应用研究都具有参考价值。

目录

文摘

英文文摘

论文说明：图表目录

声明

第1章 绪论

1.1克隆选择算法概述

1.1.1克隆选择的生物机理

1.1.2克隆选择算法的流程

1.1.3克隆选择算法的研究现状

1.2进化非选择算法

1.2.1用于组合优化的进化非选择算法流程

1.2.2进化非选择算法研究现状

1.3本论文的主要研宄内容及组织安排

1.3.1本文主要内容

1.3.2本文的组织安排

第2章 克隆选择算法中元动力学算子的研究

2.1相关工作

2.2元动力学策略

2.3实验结果及分析

2.3.1 Two Max函数

2.3.2 Almost Positive函数

2.3.3 N Almost Positive函数

2.3.4一个DUF函数

2.4讨论

2.5本章小结

第3章 进化非选择算法在一个组合优化问题上的时间复杂度

3.1相关工作

3.2预备知识

3.2.1进化非选择算法

3.2.2 Two Max函数

3.3进化非选择算法的平均时间复杂度分析

3.3.1匹配阈值为r=n/2

3.3.2匹配阈值为r=1

3.4模拟实验

3.5讨论

3.6本章小结

第4章 匹配阈值对进化非选择算法的性能影响分析

4.1问题的提出

4.2时间复杂度的对比分析

4.2.1匹配阈值为n/2-c

4.2.2匹配阈值为c

4.3模拟实验和讨论

4.3.1匹配阈值为(n/2-c)

4.3.2匹配阈值为c

4.4讨论

4.5本章小结

第5章 总结与展望

参考文献

致谢

读硕期间发表的学术论文与参加的科研项目

作者简历