动态竞争策略的链式多智能体遗传算法的研究

论文摘要

遗传算法（Genetic Algorithm）是根据生物进化理论和遗传变异理论提出的一种基于种群搜索的优化算法。由于其具有简单易行、鲁棒性强,以及不需要很多专业领域先验知识等特点,所以遗传算法在众多领域有良好的应用前景。但传统遗传算法有时会出现早收敛及搜索效率不高的现象,制约了它的进一步推广应用。针对这两个不足,提出了一种链式智能体遗传算法CAGA（Chainlike Agents Genetic Algorithm）。该算法是一种单种群智能体遗传算法,采用实数编码,用生存在链式环境中的智能体代表候选解,通过智能体间的竞争与合作来搜索最优解。同时,该算法通过动态邻域竞争、邻域正交交叉、自适应变异等改进措施,提高智能体的搜索效率从而提高算法的优化性能。实验采用多个国际标准测试函数对该算法和其它几种改进遗传算法进行了多次函数优化性能测试。实验结果表明,该算法能有效防止早收敛现象,比其它多种改进GAs有较高的搜索效率。对于一些复杂性和难度较大的应用问题,CAGA这种单种群智能体遗传算法仅采用一个种群进化,无法实现多种群并行搜索的性能,其算法的优化速度仍不能满足系统的实时性要求。基于此,本文进一步展开研究,提出了多子群协同链式智能体遗传算法（Multi-population Agents Genetic Algorithm,MPAGA）。该算法结合协同进化思想,采用了多子群并行搜索模式。其思路是:首先整个种群被划分为多个子群;其次,每个子群采用CAGA的方式进行进化,子群间通过共享智能体进行遗传信息的分享与传递,以实现多个子群协同寻找满意解的目的,有效提高了优化速度。本文采用多个国际标准的复杂测试函数对该算法的优化性能进行了测试。测试结果表明,与其它多种改进GAs相比,该算法不仅有较高质量的满意解,而且有较短的算法运行时间,能有效提高算法的优化速度。此外,本文简短讨论了链式智能体遗传算法在特征选择中的应用。为了适应特征选择应用的需要,本文采用二进制编码作为搜索算法的编码方式,选用距离测度作为评价准则,并使用BP神经网络作为分类器对所选特征子集进行了分类测试。文末采用机器学习的经典数据集作为待分类数据集进行了多次测试。实验结果表明,与其它几种改进GAs相比,该算法能以较短的运算时间搜索到入选特征数较少但识别率较高的特征子集。

论文目录

• 摘要
• ABSTRACT
• 1 引言
• 1.1 本课题研究的背景和目的
• 1.2 本课题研究的工作内容
• 1.3 本论文的结构安排
• 2 遗传算法与多智能体系统
• 2.1 遗传算法的基本概念
• 2.1.1 遗传算法的基本流程
• 2.1.2 遗传算法的特点
• 2.2 多智能体系统的基本概念
• 2.3 多智能体系统用于遗传算法改进
• 3 链式智能体遗传算法
• 3.1 算法描述
• 3.1.1 链式多智能体网络结构
• 3.1.2 动态邻域竞争算子
• 3.1.3 正交交叉算子
• 3.1.4 自适应变异算子
• 3.1.5 精英保留策略
• 3.1.6 停止准则
• 3.1.7 CAGA 算法流程
• 3.2 实验结果与分析
• 3.2.1 测试函数
• 3.2.2 CAGA 低维函数优化实验
• 3.2.3 CAGA 中高维函数优化试验
• 3.2.4 2～100 维函数优化收敛性能测试
• 3.3 本章小结
• 4 多子群协同链式智能体遗传算法
• 4.1 算法描述
• 4.1.1 多子群协同链式智能体网络结构
• 4.1.2 动态邻域竞争算子
• 4.1.3 正交交叉算子
• 4.1.4 自适应变异算子
• 4.1.5 收敛性分析
• 4.1.6 MPAGA 算法流程
• 4.2 实验结果与分析
• 4.2.1 测试函数
• 4.2.2 MPAGA 低维函数优化实验
• 4.2.3 MPAGA 中高维函数优化实验
• 4.2.4 2～100 维函数优化收敛性能测试
• 4.2.5 共享智能体数量分析
• 4.2.6 子群规模分析
• 4.3 本章小结
• 5 链式智能体遗传算法用于特征选择的研究
• 5.1 遗传算法用于特征选择的一般流程
• 5.2 用于特征选择的链式智能体遗传算法
• 5.2.1 遗传算子及流程说明
• 5.2.2 实验结果分析
• 5.3 本章小结
• 6 总结
• 致谢
• 参考文献
• 附录