Supermultiplicative Speedups of Probabilistic Model-Building Genetic Algorithms

摘要

Substantial progress was achieved for all objectives stated in this proposal. Several effective efficiency enhancement techniques were proposed from specialized model-directed hybrids to methods capable of learning from prior runs on similar problems. Substantial speedups of an order of magnitude or more were obtained with several of these techniques on difficult classes of problems and evidence was provided of supermultiplicative speedups resulting from a combination of multiple efficiency enhancements. Theoretical models were developed to capture some of the facets of these techniques, providing inputs useful for a better use these techniques in practice. Progress in efficiency enhancement of FDAs resulted in several important large-scale applications, from the solution of a noisy optimization problem with over one billion variables to the analysis of flexible protein structures for proteins of over 900 amino acids. Model-based optimization techniques and other metaheuristics were also successfully applied to the quadratic assignment problem, potential function design in physics, and cancer chemotherapy treatment optimization with one or multiple drugs.