Information Exchange and Conflict Resolution in Particle Swarm Optimization Variants
MetadataShow full item record
Single population, biologically-inspired algorithms such as Genetic Algorithm and Particle Swarm Optimization are effective tools for solving a variety of optimization problems. Like many such algorithms, however, they fall victim to the curse of dimensionality. Additionally, these algorithms often suffer from a phenomenon known as hitchhiking where improved solutions are not unequivocally better for all variables. Insofar as individuals within these populations are deemed to be competitive, one solution to both the curse of dimensionality and the problem of hitchhiking has been to introduce more cooperation. These multi-population algorithms cooperate by decomposing a problem into parts and assigning a population to each part. Factored Evolutionary Algorithms (FEA) generalize this decomposition and cooperation to any evolutionary algorithm. A key element of FEA is a global solution that provides missing information to individual populations and coordinates them. This dissertation extends FEA to the distributed case by having individual populations maintain and coordinate local solutions that maintain consensus. This Distributed FEA (DFEA) is demonstrated to perform well on a variety of problems and, sometimes, even if consensus is lost. However, DFEA fails to maintain the same semantics as FEA. To address this issue, we develop an alternative framework to the ``cooperation versus competition'' dichotomy. In this framework, information flows are modeled as a blackboard architecture. Changes in the blackboard are modeled as merge operations that require conflict resolution between existing and candidate values. Conflict resolution is handled using Pareto efficiency, which avoids hitchhiking. We apply this framework to FEA and DFEA and develop revised DFEA, which performs identically to FEA. We then apply our framework to a single population algorithm, Particle Swarm Optimization (PSO), to create Pareto Improving PSO (PI-PSO). We demonstrate that PI-PSO outperforms PSO and sometimes FEA-PSO, often with fewer individuals. Finally, we extend our information based approach by implementing parallel, distributed versions of FEA and DFEA using the Actor model. The Actor model is based on message passing, which accords well with our information-centric framework. We use validation experiments to verify that we have successfully implemented the semantics of the serial versions of FEA and DFEA.