Optimization by simulating molecular evolution

Abstract

Based on the analogy between mathematical optimization and molecular evolution and on Eigen's quasi-species model of molecular evolution, an evolutionary algorithm for combinatorial optimization has been developed. This algorithm consists of a versatile variation scheme and an innovative decision rule, the essence of which lies in a radical revision of the conventional philosophy of optimization: A number of configurations of variables with better values, instead of only a single best configuration, are selected as starting points for the next iteration. As a result the search proceeds in parallel along a number of routes and is unlikely to get trapped in local optima. An important innovation of the algorithm is introduction of a constraint to let the starting points always keep a certain distance from each other so that the search is able to cover a larger region of space effectively. The main advantage of the algorithm is that it has more chances to find the global optimum and as many local optima as possible in a single run. This has been demonstrated in preliminary computational experiments.