Hierarchical asynchronous genetic algorithms for parallel/distributed simulation-based optimization.

Persistent Link:
http://hdl.handle.net/10150/186831
Title:
Hierarchical asynchronous genetic algorithms for parallel/distributed simulation-based optimization.
Author:
Kim, Jinwoo.
Issue Date:
1994
Publisher:
The University of Arizona.
Rights:
Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.
Abstract:
The objective of this dissertation is to develop a multi-resolution optimization strategy based on the evolution algorithms in the parallel/distributed simulation environment. The system architecture is constructed hierarchically with multiple clusters which consist of an expert system (controller) and set of genetic algorithm optimizers (agents). We propose an asynchronous genetic algorithm (AGA) which continuously updates the population in parallel genetic algorithms. Asynchronous evaluation of population in a parallel computer improves the utilization of the processors and reduces search time when the evaluation time of individuals is highly variable. Further, we have devised a noise assignment scheme which resolves the pre-convergence drawback of the genetic algorithms. In this scheme, binary representation (discrete sampling) of an individual is combined with a random number (analog sampling), so that the genetic algorithm can investigate the entire search space regardless of the bit-size of an individual. Real application problems require the evaluation of a large number of parameters and their search complexity grows beyond the capability of a single level GA-optimizer. In response, we have developed a novel scheme called Hierarchical Genetic Algorithms. This multilevel GA optimization strategy is based on an Intelligent Machine Architecture which supporting non-deterministic computation, intensive and irregular memory access patterns, and large potential for parallel computing. The clusters in the Hierarchical GAs are coordinated hierarchically and creation and deletion of nodes are performed dynamically based upon performance. During the optimization process, the clusters cooperate together to solve different levels of the abstracted problem. A candidate solution at a higher level creates a lower level cluster which utilizes previously optimized parameter information. It can also contribute to the search process of a higher level by sending the feedback information. Hierarchical GAs demonstrate performance with various experiments. We have compared the performance of the Hierarchical GAs and simple GA (single-level). The Hierarchical GAs adaptively changes its structure to allocate more computing resources to the promising nodes. With the same amount of memory size for population, the simulation results shows that the Hierarchical GAs find a solution faster than the simple GA.
Type:
text; Dissertation-Reproduction (electronic)
Degree Name:
Ph.D.
Degree Level:
doctoral
Degree Program:
Electrical and Computer Engineering; Graduate College
Degree Grantor:
University of Arizona
Committee Chair:
Zeigler, Bernard P.

Full metadata record

DC FieldValue Language
dc.language.isoenen_US
dc.titleHierarchical asynchronous genetic algorithms for parallel/distributed simulation-based optimization.en_US
dc.creatorKim, Jinwoo.en_US
dc.contributor.authorKim, Jinwoo.en_US
dc.date.issued1994en_US
dc.publisherThe University of Arizona.en_US
dc.rightsCopyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.en_US
dc.description.abstractThe objective of this dissertation is to develop a multi-resolution optimization strategy based on the evolution algorithms in the parallel/distributed simulation environment. The system architecture is constructed hierarchically with multiple clusters which consist of an expert system (controller) and set of genetic algorithm optimizers (agents). We propose an asynchronous genetic algorithm (AGA) which continuously updates the population in parallel genetic algorithms. Asynchronous evaluation of population in a parallel computer improves the utilization of the processors and reduces search time when the evaluation time of individuals is highly variable. Further, we have devised a noise assignment scheme which resolves the pre-convergence drawback of the genetic algorithms. In this scheme, binary representation (discrete sampling) of an individual is combined with a random number (analog sampling), so that the genetic algorithm can investigate the entire search space regardless of the bit-size of an individual. Real application problems require the evaluation of a large number of parameters and their search complexity grows beyond the capability of a single level GA-optimizer. In response, we have developed a novel scheme called Hierarchical Genetic Algorithms. This multilevel GA optimization strategy is based on an Intelligent Machine Architecture which supporting non-deterministic computation, intensive and irregular memory access patterns, and large potential for parallel computing. The clusters in the Hierarchical GAs are coordinated hierarchically and creation and deletion of nodes are performed dynamically based upon performance. During the optimization process, the clusters cooperate together to solve different levels of the abstracted problem. A candidate solution at a higher level creates a lower level cluster which utilizes previously optimized parameter information. It can also contribute to the search process of a higher level by sending the feedback information. Hierarchical GAs demonstrate performance with various experiments. We have compared the performance of the Hierarchical GAs and simple GA (single-level). The Hierarchical GAs adaptively changes its structure to allocate more computing resources to the promising nodes. With the same amount of memory size for population, the simulation results shows that the Hierarchical GAs find a solution faster than the simple GA.en_US
dc.typetexten_US
dc.typeDissertation-Reproduction (electronic)en_US
thesis.degree.namePh.D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.disciplineElectrical and Computer Engineeringen_US
thesis.degree.disciplineGraduate Collegeen_US
thesis.degree.grantorUniversity of Arizonaen_US
dc.contributor.chairZeigler, Bernard P.en_US
dc.contributor.committeememberCellier, Francois E.en_US
dc.contributor.committeememberCarothers, Jo Daleen_US
dc.identifier.proquest9506965en_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.