Running time analysis of multiobjective evolutionary algorithms on Pseudo-Boolean functions

被引:128
作者
Laumanns, M [1 ]
Thiele, L [1 ]
Zitzler, E [1 ]
机构
[1] Swiss Fed Inst Technol, ETH, Comp Engn & Networks Lab, CH-8092 Zurich, Switzerland
关键词
convergence time; evolutionary algorithms; (EAs); multiobjective optimization; running time analysis;
D O I
10.1109/TEVC.2004.823470
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
This paper presents a rigorous running time analysis of evolutionary algorithms on pseudo-Boolean multiobjective optimization problems. We propose and analyze different population-based algorithms, the simple evolutionary multiobjective optimizer (SEMO), and two improved versions, fair evolutionary multiobjective optimizer (FEMO) and greedy evolutionary multiobjective optimizer (GEMO). The analysis is carried out on two biobjective model problems, leading ones trailing zeroes (LOTZ) and count ones count zeroes (COCZ), as well as on the scalable m-objective versions mLOTZ and mCOCZ. Results on the running time of the different population-based algorithms and for an alternative approach, a multistart (1+1)-EA based on the epsilon-constraint method, are derived. The comparison reveals that for many problems, the simple algorithm SEMO is as efficient as this (1+1)-EA. For some problems, the improved variants FEMO and GEMO are provably better. For the analysis; we propose and apply two general tools, an upper bound technique based on a decision space partition and a randomized graph search algorithm, which facilitate the analysis considerably.
引用
收藏
页码:170 / 182
页数:13
相关论文
共 27 条
[1]  
ALON N, 2002, COMMUNICATION JAN
[2]  
[Anonymous], 2001, PROCEEDINGS OF THE INTERNATIONAL SYMPOSIUM ON INFORMATION SCIENCE INNOVATIONS IN ENGINEERING OF NATURAL AND ARTIFICIAL INTELLIGENT SYSTEMS ISI 2001
[3]   How to analyse evolutionary algorithms [J].
Beyer, HG ;
Schwefel, HP ;
Wegener, I .
THEORETICAL COMPUTER SCIENCE, 2002, 287 (01) :101-130
[4]  
Chankong V., 1983, Multiobjective Decision Making: Theory and Methodology
[5]  
Coello C. A. C., 2002, EVOLUTIONARY ALGORIT
[6]  
Deb K., 2001, Multi-Objective Optimization using Evolutionary Algorithms
[7]   On the analysis of the (1+1) evolutionary algorithm [J].
Droste, S ;
Jansen, T ;
Wegener, I .
THEORETICAL COMPUTER SCIENCE, 2002, 276 (1-2) :51-81
[8]   A Rigorous Complexity Analysis of the (1+1) Evolutionary Algorithm for Separable Functions with Boolean Inputs [J].
Droste, Stefan ;
Jansen, Thomas ;
Wegener, Ingo .
EVOLUTIONARY COMPUTATION, 1998, 6 (02) :185-196
[9]   Statistical distribution of the convergence time of evolutionary algorithms for long-path problems [J].
Garnier, J ;
Kallel, L .
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2000, 4 (01) :16-30
[10]   Rigorous Hitting Times for Binary Mutations [J].
Garnier, Josselin ;
Kallel, Leila ;
Schoenauer, Marc .
EVOLUTIONARY COMPUTATION, 1999, 7 (02) :173-203