协同进化算法(Coevolutionary Algorithm, CEA)是借鉴生态学上多物种相互作用、彼此驱动、协同进化机理而建立的一组新型进化算法。协同进化算法扩展了传统进化算法的应用范围,能有效地解决一些传统进化算法难以解决的复杂问题。在人工智能的机器学习领域,有相当一部分问题无明确的目标评价函数,候选解的性能需要通过测试进行评价,比如分类策略学习问题、博弈策略学习问题等。典型情况下,可能的测试样本数目巨大,无法在完整测试集上进行评价,而选择一个固定测试集又易于造成过适应。协同进化算法将候选解和测试样本构造成两个竞争关系的种群,让它们一起进化,个体适应度通过与对方个体直接竞争获得,从原理上为解决该类问题开辟了一条有效的途径。但是,协同进化算法的动态性评价方式容易导致评价的不稳定,以至在进化中常常出现复杂的动态性,如循环、特化等,致使进化脱离预定的目标,不能可靠地进化。如何组织、设置这种动态性评价才能确保协同进化算法成为一个有效、可靠的搜索方法是算法研究面临的一个主要挑战。研究显示“基于测试”(test-based)问题域内隐含存在一组信息维,它们架构了问题域的评价空间。可将评价信息压缩到一个小的维度集上,每一个维度可看作一个基本目标,并按照进化多目标优化的观点,对候选解进行评价。本文以此为研究基础,提出了几种针对“基于测试”问题的可靠协同进化算法设计方案。(1)提出了一个基于信息维识别的协同进化存档方案,改善了目前可靠存档算法存档量过大,执行效率低的现状。在协同进化期间,借助动态维度识别,仅选择代表各维度最新进展的测试个体进档保留,并以它们作为评价基准,选择保留优秀候选解,以此阻止进化倒退,辅助协同进化可靠有效地推进。本方案在确保可靠地进化的同时最小化存档量。其中,维度识别是本方案的实施关键。针对问题类型的难易,提供了两种维度识别方法和配套实施策略：针对COMPARE-ON-ONE类问题,其特征是域内每一个测试个体仅能提供一个维度上的评价信息,构建了算法EPCA;针对一般二值收益问题,构建了算法DI-CA。两算法均通过实验进行了验证,结果显示较以前的存档算法均有更好的性能和效率。(2)提出了一个在线维度抽取方法,并在此基础上构建了一个带有维度抽取的协同进化算法PCA-DE。在线维度抽取方法借助个体间的特征收益关系来实施维度抽取,再根据维度固有的顺序性对抽取的维度进行修正,使抽取到的维度具有更高的准确性。在PCA-DE算法的执行过程中,同步抽取问题域的维度系统,并以此对个体实施准确评价,保留最优个体,引导进化单调有效地进展。实验证实了PCA-DE的可行性,并显示出比同类算法更高的性能和维度抽取准确率。(3)提出了一个非确定性双向维度抽取方案,降低了维度抽取条件,并在此基础上构建了一个基于双向维度抽取的协同进化存档算法CA-BDE。在进化过程中,算法借助测试端的维度抽取,选择具有维度代表特征的测试个体存档保留,用于为后续进化提供完整评价支持；同时算法借助于从对偶端进行的候选维度抽取,选择具有维度代表特征的高性能候选个体存档保留,用于保优并兼顾为测试个体维度特征的后续鉴别提供支持。尽管采用的非确定性抽取方法不能保证维度抽取的准确性,但在进化中,具有维度信息特征的测试个体不断受到激励,会逐渐集中到各个真实维度上,同时,侯选档案始终保持着最有价值的个体,不会过度庞大。实验表明CA-BDE有更强的普适性、更高的可行性和更优的性能。