ISSN 1000-1239 CN 11-1777/TP

• 论文 • 上一篇    下一篇

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

杨莉萍1,2 黄厚宽1   

  1. 1(北京交通大学计算机与信息技术学院 北京 100044) 2(山东财政学院计算机与信息工程学院 济南 250014) (ylp_117@sina.com)
  • 出版日期: 2010-09-15

A Pareto Coevolutionary Algorithm Integrated with Dimension Extraction

Yang Liping1,2 and Huang Houkuan1   

  1. 1(School of Computer & Information Technology, Beijing Jiaotong University, Beijing 100044) 2(School of Computer & Information Engineering, Shandong University of Finance, Jinan 250014)
  • Online: 2010-09-15

摘要: 保证评价的可靠性和有效性是协同进化算法面临的主要挑战.近期研究显示协同进化问题域内隐含存在着一个维度系统,决定了问题解的完整评价指标.分析了维度结构表现出的个体间特征收益关系,提出了一种在线维度抽取方法,并将其集成到协同进化算法中,在进化过程中,同步抽取问题的维度,建立维度系统,为个体提供准确评价,并指导选择和保优操作,以此确保进化稳定进展.抽象问题上的实验结果验证了本算法的可行性,并表明本算法在性能和维度抽取的准确性上均高于现存同类算法.

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

Abstract: 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.

Key words: coevolution, test-based problem, dimension extraction, accurate evaluation, reliable progress