Enhancing Evolutionary Algorithm Performance with Knowledge Transfer and Asynchronous Parallelism
Date
2022
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Search and optimization problems are widespread throughout business and engineering, but these computational problems are often complex enough that they must be approached with heuristic algorithms. Evolutionary algorithms (EAs) offer a very general framework for solving many of these tasks, but their computational complexity can be difficult to manage when they are applied to mature and large-scale classes of problems. From my experience working on EA applications, I became concerned about two EA efficiency challenges that have been inadequately addressed to date: 1) parallelization strategies for evolutionary algorithms routinely suffer from idle CPU resources that go unused, and 2) customizing evolutionary algorithms with the domain-specific prior knowledge that they require in order to solve useful problems often requires costly and time-consuming research programs. In response to the idle-resources problem, I have engaged in a detailed study of asynchronous steady-state evolutionary algorithms (ASEAs) and their ability to better utilize large clusters of CPU resources. I studied issues of speedup, evaluation-time bias, and excess computational effort in ASEAs—concluding in particular that evaluation-time bias is a less severe problem for these algorithms than many practitioners have assumed. Next, I have addressed the problem of prior knowledge in EAs by engaging in a broad preliminary study of evolutionary knowledge transfer (EKT) and multi-task optimization. Motivated by natural examples of "innovation engines'' that repurpose solutions to past tasks to find solutions to complex future tasks, I studied issues of transferability in different problem classes, negative transfer, and representation-based knowledge transfer approaches for evolutionary algorithms. My contributions in this area include proofs of a new set of no-free-lunch theorems for various types of transfer optimization, and several novel algorithms to address EKT challenges—including a many-source population-seeding algorithm that avoids negative transfer fairly easily, a multi-task Cartesian genetic programming approach, and a representation-learning algorithm that is able to learn and transfer genotype-phenotype maps across problem classes.
Description
Keywords
Evolutionary algorithms, Evolutionary Computation, Multi-Task Learning, Optimization, Transfer Learning