期刊
THEORETICAL COMPUTER SCIENCE
卷 411, 期 21, 页码 2084-2100出版社
ELSEVIER
DOI: 10.1016/j.tcs.2010.03.002
关键词
Particle swarm optimization; Runtime analysis
资金
- Deutsche Forschungsgemeinschaft (DFG) [SFB 531]
- German Academic Exchange Service
We investigate the runtime of a binary Particle Swarm Optimizer (PSO) for optimizing pseudo-Boolean functions f : {0, 1}(n) -> R. The binary PSO maintains a swarm of particles searching for good solutions. Each particle consists of a current position from 10, 11, its own best position and a velocity vector used in a probabilistic process to update its current position. The velocities for a particle are then updated in the direction of its own best position and the position of the best particle in the swarm. We present a lower bound for the time needed to optimize any pseudo-Boolean function with a unique optimum. To prove upper bounds we transfer a fitness-level argument that is well-established for evolutionary algorithms (EAs) to PSO. This method is applied to estimate the expected runtime for the class of unimodal functions. A simple variant of the binary PSO is considered in more detail for the test function ONEMAX, showing that there the binary PSO is competitive to EAs. An additional experimental comparison reveals further insights. (C) 2010 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据