Particle Swarm Optimization Combined with Query-Based Learning Using MapReduce
Particle swarm optimization (PSO) has shown its effectiveness to solve many complex optimization problems. However, PSO sometimes may fall into a local optimal solution rather than the global optimal solution of a given problem. For large-scale optimizati
- PDF / 881,711 Bytes
- 7 Pages / 439.363 x 666.131 pts Page_size
- 76 Downloads / 231 Views
Dept. Information Management, Tunghai University, Taichung, Taiwan [email protected] 2 Dept. Engineering Science and Oceanic Engineering, National Taiwan University, Taipei, Taiwan [email protected], [email protected]
Abstract. Particle swarm optimization (PSO) has shown its effectiveness to solve many complex optimization problems. However, PSO sometimes may fall into a local optimal solution rather than the global optimal solution of a given problem. For large-scale optimization problems, several parallelized PSOs have been proposed in the literature. In this paper, a query-based learning (QBL) approach is adopted to help PSO jump out of a local optimum. An Oracle is introduced that answers PSO whether there are too many particles in a flat region of the solution space. If yes, the algorithm will redistribute some of the particles in the flat region to somewhere else. A parallelized implementation, referred to as MRPSO-QBL, is developed in the Apache Hadoop MapReduce framework, as the framework provides a simpler and better parallel programming paradigm. The experiment results on several benchmark functions have demonstrated that MRPSO-QBL can find better solutions and converge faster. Keywords: Particle Swarm Optimization, MapReduce, Query-Based Learning.
1
Introduction
Bio-inspired meta-heuristic algorithms have interested many researchers in the last decades. They have been used to solve many complex problems in different fields. Among them, particle swarm optimization (PSO) [1-4] is very prominent due to its simplicity in concept and implementation, generality to be applicable in diverse areas, and effectiveness to fast converge to good approximating solutions. Generally speaking, in PSO, a particle represents a candidate in the solution space of a given problem. A fitness function is chosen to evaluate how good to the given problem a candidate solution can achieve. To experience difference fitness, a particle will move in the solution space. Initially, there are many particles generated randomly or heuristically in a population. All particles are evaluated using the fitness function. Then, each particle moves according to its inertia, its best personal experience, and the best particle in the population. Iteratively, all particles move in the solution space in the same manner until a stop condition is reached, e.g., a satisfied fitness is found or the time is up. The movement of particles is inspired by bird flocking. Since the James J. (Jong Hyuk) Park et al. (eds.), Future Information Technology, Lecture Notes in Electrical Engineering 309, DOI: 10.1007/978-3-642-55038-6_14, © Springer-Verlag Berlin Heidelberg 2014
91
92
J.-W. Lin, W.-C. Chi, and R.-I. Chang
best particle serves as a leader of all particles, PSO typically converges very fast and can find a good candidate solution. PSO sometimes may fall into a local optimal solution rather than the global optimal solution of a problem. Furthermore, PSO usually takes a lot of time, especially for those problems where the evaluation of the fitn
Data Loading...
