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