Constraint-oriented refinement-efficacious memetic algorithms for efficient optimization of computationally-expensive problems

• Main Author: Handoko, Stephanus Daniel
• Other Authors: Kwoh Chee Keong
• Format: Theses and Dissertations
• Language: English
• Published: 2013
• Subjects: DRNTU::Engineering::Computer science and engineering
• Online Access: https://hdl.handle.net/10356/54901
• Institution: Nanyang Technological University

Successes of the Memetic Algorithms (MAs) have since alleviated the problems of local optimum trap of the deterministic optimization techniques as well as of slow, imprecise convergence of the stochastic optimization approaches. Through the hybridization of local search and global search by interleaving deterministic and stochastic optimizers one after the other, the MAs have become capable of searching more efficiently than their conventional counterparts. Gradually, this has brought paradigm shift to the research works in the particular area—which currently are geared towards solving complex science and engineering problems that are computationally-expensive in nature. Where minutes to hours of CPU time is consumed per evaluation, local search for each individual as adopted by the simple MA is clearly not an efficient strategy. Surrogate models in place of the actual problem landscape have been proposed as a response. Alternatively, selective local search can be employed to refine only some potential individuals to ease the computational burdens. The choice of individuals in the population to undergo local refinement is indeed critical to not only the efficiency but also the effectiveness of the MA. Some simple heuristics can be pretty intuitive, e.g. refining only the top few individuals in the population. This, nevertheless, may compromise the effectiveness of the MA. Presented in this thesis is a framework of MA named Constrained-Oriented Refinement-Efficacious Memetic Algorithm (CORE-MA) that enables intelligent selection of the individuals to undergo local refinement. CORE-MA is the first optinformatics (learning-from-archive paradigm) for the constrained real-valued optimization. Oriented by constraint values that describe the problem topology, CORE-MA allows restraints on some unnecessary refinements thereby focusing the search efforts on the important regions of the search space and accelerating the identification of the global optimum. Feasibility Structure Modeling (FSM), as the first CORE-MA instantiation, formulates a classification problem within the optimization framework for the first time and uses Support Vector Machine (SVM) to solve it. The SVM prediction is subsequently used to determine if an individual is worth refining. Constrained Landscape Stratification (CLS), being the second CORE-MA instantiation, employs the simple nearest-neighbor-based dichotomizer directly after stratifying the problem landscape using the gradient information. This, consequently, eliminates the need for SVM. Less overhead is incurred as the result. Multi-fold accelerations were seen following experiments using the CORE-MA on the benchmark problems. Greater rate of descent with respect to the potential energy trace and up to 25 times speed-ups with respect to the docking time were witnessed upon the applications of the CORE-MA to the molecular mechanics and molecular docking problems, respectively.