Article Preview
Top1. Introduction
Many real-world optimization problems are dynamic by nature. As conditions change what might be regarded as optimum at one time might not be optimal at next minute. A dynamically changing environment (generally speaking, optimal solutions may change, but solution space will not change) presents a challenge in tracking an optimal solution. Due to the continual changing of both the external environment and parameters, the optimal solution in the environment will also change with time. In contrast to optimization towards a static objective, dynamic optimization problems demand optimal algorithms which not only find the optimal solution but also track the trajectory of the optimal solution.
The Particle Swarm Optimization (PSO) method is a member of a wider class of swarm intelligence methods used for solving Global Optimization (GO) problems. The method was originally proposed by Kennedy and Eberhart (1995, 2001) as a simulation of social behavior of bird flock and was initially introduced as an optimization method in 1995. PSO has been applied to many complex and difficult optimization problems (Clerc & Kennedy, 2002; Kennedy & Eberhart, 1995, 2001) and proved to be effective and quickly convergent. However most of these problems are treated as a task of finding a single global optimum in a static environment. Tracking optimum in dynamic environments using PSO is still a relatively new area. Traditional PSO algorithms lack the ability to track the optimal solution in a dynamic environment.
In a PSO algorithm, each individual (particle) which represents a candidate solution to the problem at hand flies through a multidimensional search space to find the optima or sub-optima. The particle evaluates its position against a goal (objective function) at each iteration, and particles in a local neighborhood share memories of their “best” positions and use these memories to adjust their own velocities and thus subsequent positions. It has already been shown that the PSO algorithm is comparable in performance with and may be considered as an alternative to the Genetic Algorithm (GA) (Angeline, 1998).
However, as proved by Van Den Bergh (2001) PSO does not guarantee a global convergence because the particle is restricted to a finite sampling space for each of the iterations. This restriction may weaken the global search ability of the algorithm and may lead to premature convergence in many cases. Recently, a new version of PSO, called quantum-behaved particle swarm optimization (QPSO), has been proposed in order to improve the global search performance of the original PSO (Sun, Feng, & Xu, 2004; Sun, Xu, & Feng, 2004). QPSO is guaranteed to be global convergence, and besides, has fewer parameters to control, which makes it easier to implement.
When handing changes in a dynamic system an optimization method needs to have the mechanism to respond to the environment change so that the optimum can still be tracked. Hu and Eberhart (2002) proposed a method in which the GBEST and second-best GBEST were monitored. Carlisle and Dozier (2000, 2002) presented an Adaptive Particle Swarm Optimizer (APSO) to track dynamic environments. One or more sentry particles were used in APSO to find out the change of the environments. However most of the algorithms mentioned above were firstly presented in uniformly changing environments which was introduced by Angeline (1997). The environment is not suitable to indicate the adaptability of the algorithm in complex dynamic environment. Li and Dam (2003) compared several methods based on PSO in the dynamic environment generated by DF1 (Morrison & De Jong, 1999). The results insinuated that PSO-based methods can track the changing optimum but the performance was not excellent. In Shan and Deng (2006), an adapted PSO was proposed to enhance the track ability of PSO, but the adapted algorithm was only applied to find a single global optimum and its ability in locating multiple optima was not proven.