Cooperative Particle Swarm Optimization for Combinatorial Problems

Simple item page
dc.contributor.advisorReggia, James Aen_US
dc.contributor.advisorKingsford, Carl Len_US
dc.contributor.authorLapizco Encinas, Grecia del Carmenen_US
dc.contributor.departmentComputer Scienceen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.date.accessioned2010-02-19T06:49:49Z
dc.date.available2010-02-19T06:49:49Z
dc.date.issued2009en_US
dc.description.abstractA particularly successful line of research for numerical optimization is the well-known computational paradigm <italic>particle swarm optimization</italic> (PSO). In the PSO framework, candidate solutions are represented as particles that have a position and a velocity in a multidimensional search space. The direct representation of a candidate solution as a point that flies through hyperspace (i.e., R<sub>n</sub>) seems to strongly predispose the PSO toward continuous optimization. However, while some attempts have been made towards developing PSO algorithms for combinatorial problems, these techniques usually encode candidate solutions as permutations instead of points in search space and rely on additional local search algorithms. In this dissertation, I present extensions to PSO that by, incorporating a cooperative strategy, allow the PSO to solve combinatorial problems. The central hypothesis is that by allowing a set of particles, rather than one single particle, to represent a candidate solution, combinatorial problems can be solved by collectively constructing solutions. The cooperative strategy partitions the problem into components where each component is optimized by an individual particle. Particles move in continuous space and communicate through a feedback mechanism. This feedback mechanism guides them in the assessment of their individual contribution to the overall solution. Three new PSO-based algorithms are proposed. <italic>Shared-space CCPSO</italic> and <italic>multispace CCPSO</italic> provide two new cooperative strategies to split the combinatorial problem, and both models are tested on proven NP-hard problems. <italic>Multimodal CCPSO</italic> extends these combinatorial PSO algorithms to efficiently sample the search space in problems with multiple global optima. Shared-space CCPSO was evaluated on an abductive problem-solving task: the construction of parsimonious set of independent hypothesis in diagnostic problems with direct causal links between disorders and manifestations. Multi-space CCPSO was used to solve a protein structure prediction subproblem, sidechain packing. Both models are evaluated against the provable optimal solutions and results show that both proposed PSO algorithms are able to find optimal or near-optimal solutions. The exploratory ability of multimodal CCPSO is assessed by evaluating both the quality and diversity of the solutions obtained in a protein sequence design problem, a highly multimodal problem. These results provide evidence that extended PSO algorithms are capable of dealing with combinatorial problems without having to hybridize the PSO with other local search techniques or sacrifice the concept of particles moving throughout a continuous search space.en_US
dc.identifier.urihttp://hdl.handle.net/1903/9901
dc.subject.pqcontrolledArtificial Intelligenceen_US
dc.subject.pqcontrolledComputer Scienceen_US
dc.subject.pquncontrolledcombinatorial heuristicsen_US
dc.subject.pquncontrolledparticle swarm optimizationen_US
dc.subject.pquncontrolledprotein side chain packingen_US
dc.subject.pquncontrolledprotein structure predictionen_US
dc.subject.pquncontrolledswarm intelligenceen_US
dc.titleCooperative Particle Swarm Optimization for Combinatorial Problemsen_US
dc.typeDissertationen_US

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
LapizcoEncinas_umd_0117E_10855.pdf
Size:
2.77 MB
Format:
Adobe Portable Document Format
Download

Collections

UMD Theses and Dissertations
Computer Science Theses and Dissertations