Optimal Mapping between Problem Models and Parallel Genetic Algorithms

Principal Investigator:
Leung, Kwong Sak

Co-investigator(s):
Wong, C. K.
Leung, Yee

Summary:
Genetic algorithms (GAs) are stochastic global search and optimization techniques inspired by nature's evolution process and population genetics. They have been demonstrated to be effective and robust in solving many difficult and complex problems such as design and planning, network optimizations and knowledge acquisition. Due to its global search approach, it is not particularly efficient. However, the GAs have extremely strong implicit parallelism which can be exploited to substantially speed up the computation. A lot of work has been done in the field of parallel GAs (PGAs). In some cases, even superlinear speedups can be achieved. However, the importance of classifying a problem and finding an optimal PGA for it has not been addressed adequately and formally.

Therefore, the project is to formalize the mappings and relationships between the problems to be solved and the PGAs used, so that we could find an optimal PGA for a problem easily. With the thorough understanding of the relationships, we should also be able to further improve and accelerate the PGAs. We will develop a generic software tool for PGAs in appropriate environments; establish and formalize the relationships between the problems, their models, the potential accelerators and the PGAs; and evaluate and apply the system to large scale real-life problems related to Hong Kong industry. The contribution to the theory and applicability of PGAs will be significant.