Date of Award
Doctor of Philosophy
Deterministic optimization methods such as steepest descent, conjugate gradient and Newton's methods are known for their robustness in iteratively reducing the objective function value for minimization problems. However, they are primarily suitable for solving single objective function problems that are unimodal and continuous. With increased sophistication in engineering problems, multimodal and multi-objective problems have become more prevalent drastically reducing the effectiveness of deterministic methods. This led to the development of heuristic methods, particularly evolutionary methods such as Genetic Algorithms, Ant Colony Optimization, and Particle Swarm Optimization. These methods have multiple design points exploring the design space over iterations as opposed to a single design point as in the case of deterministic methods.;Particle Swarm Optimization (PSO) is one of the very recent population based heuristic methods similar in characteristics to other evolutionary search methods. In a basic PSO, an initial randomly generated population swarm propagates towards the global optimum over a series of iterations. The direction of the swarm movement in the design space is based on an individual particle's best position in its history trail (pBest) through exploration, and the best particle in the entire swarm (gBest) through exploitation. This information is used to generate a velocity vector indicating a search direction towards a promising location in the design space. The primary advantage of this method is its ease in implementation with a very small number of user-defined parameters. Although a relatively young method as it was developed in 1995, it has been added to the list of global search methods due to its reliability in finding the global optimum for a variety of problems.;There are a few disadvantages of the method that suppress its efficiency and accuracy and is the premise for the research presented in this thesis. Only two candidates - pBest and gBest dictate the search direction for each swarm member. Much more information is available if characteristics of additional swarm members could be utilized. Additionally, poor move sets specified by pBest and gBest in the initial stages of optimization can trap the swarm in a local minimum or cause slow convergence. To address this issue, a new approach to PSO using digital pheromones to coordinate swarms within n-dimensional design space has been developed. Digital pheromones are mathematical representations of real pheromones in that they dissipate in time and do not move in addition to the fact that a stronger pheromone field indicates a greater possibility for finding an optimum in the design space. The methods developed using digital pheromones with PSO have substantially improved the accuracy, efficiency, and reliability characteristics when compared to a basic PSO. The implementation of this concept within a PSO is the first component in the development section of this thesis, where the challenges and method development are outlined. Statistical hypothesis testing is additionally performed to evaluate the efficacy of the developed method.;The second component of the research explores the possibility of multiple swarms searching the design space in a parallel computing environment. Two methods have been developed: (1) a synchronous coarse grain approach and (2) an asynchronous shared pheromone approach. These schemes leverage the computational capabilities offered by present day processor and network technologies in increasing the efficiency of particle swarms in reaching the global optimum in multimodal design spaces.;The third component of the research is to investigate hardware acceleration of PSO with digital pheromones using commodity graphics processing units (GPU). Methods have been developed to offload repetitive computations on to GPUs where they are computed in parallel and logical operations are carried out on the CPU that hosts the GPU. This computational outsourcing dramatically reduced the overall solution times without any significant compromise in the solution accuracy and reliability.;Realistic optimization problems are characterized by numerous inequality and equality constraints. To test the viability of digital pheromones within a PSO for solving constrained optimization problems, a sequential unconstrained minimization technique---Augmented Lagrange Multiplier (ALM) method has been implemented. This final research component was to examine the usability of digital pheromones within PSO to solve constrained optimization problems.;The performance of each developed method was evaluated through a series of relevant multidimensional multimodal test problems, and the results from digital pheromone PSO were benchmarked against basic PSO implementations. Unconstrained problems were tested on serial, distributed parallel computing environments and workstations with GPUs. Constrained optimization problems were tested on serial computing environments and results are presented. The testing of the developed methods showed promising results and provided encouraging motivation for future development in addressing a wide variety of problems (discrete optimization problems, multi-objective problems, etc). (Abstract shortened by UMI.)
Digital Repository @ Iowa State University, http://lib.dr.iastate.edu/
Vijay Kiran Kalivarapu
Kalivarapu, Vijay Kiran, "Improving solution characteristics of particle swarm optimization through the use of digital pheromones, parallelization, and graphical processing units (GPUs)" (2008). Retrospective Theses and Dissertations. 15700.