一种带有维度抽取的Pareto协同进化算法  

A Pareto Coevolutionary Algorithm Integrated with Dimension Extraction

作　　者：杨莉萍[1,2] 黄厚宽[1] 

机构地区：[1]北京交通大学计算机与信息技术学院,北京100044 [2]山东财政学院计算机与信息工程学院,济南250014

出　　处：《计算机研究与发展》2010年第9期1504-1513,共10页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60443003)

摘　　要：保证评价的可靠性和有效性是协同进化算法面临的主要挑战.近期研究显示协同进化问题域内隐含存在着一个维度系统,决定了问题解的完整评价指标.分析了维度结构表现出的个体间特征收益关系,提出了一种在线维度抽取方法,并将其集成到协同进化算法中,在进化过程中,同步抽取问题的维度,建立维度系统,为个体提供准确评价,并指导选择和保优操作,以此确保进化稳定进展.抽象问题上的实验结果验证了本算法的可行性,并表明本算法在性能和维度抽取的准确性上均高于现存同类算法.Coevolution offers an adaptive evaluation method for problems where performance can be measured using tests. How to ensure the reliability and efficiency of evaluation is a central challenge in coevolution research. Recent studies have shown that within coevolutionary problem domains[0], there exist a set of implicit dimensions that can structure the evolution information of problem domains, on which the performance of each individual can be accurately evaluated. Therefore, by means of dimension information of problems, reliable evaluation can in principle be provided using only a possible small subset of all tests. Based on the above studies, the characteristic outcome relationships between individuals possessed by dimension structures are first analyzed, and then an online dimension extraction approach based on the characteristic outcome relationships is proposed. Furthermore, a coevolutionary algorithm integrated with the dimension extraction approach is designed. The algorithm synchronously extracts the dimensions of the problem during execution and utilizes this information to provide accurate evaluation for individuals, and to guide selection and reservation so as to guarantee monotonic progress. Experimental results on abstract test problems demonstrate the feasibility of the proposed algorithm, and show that it outperforms other existing similar algorithms in both performance and accuracy of dimension extraction.

关 键 词：协同进化 基于测试问题 维度抽取 准确评价 可靠进展 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]