Session:

EVH - Application of Hybrid Evolutionary Algorithms to Complex Optimization Problems

Title:

Hill-Climbers, a Memetic Algorithm and their Comparison on the Minimum Linear Arrangement Problem

Authors:

Bryant A. Julstrom

Abstract:

Memetic algorithms combine evolutionary, population-based search and local, individual search, and the local search operator is sometimes stochastic hill-climbing. Stochastic hill-climbers alone can search effectively, so here we build a memetic algorithm by applying infrequent episodes of recombination to a population of them. Independent stochastic hill-climbers with and without these episodes are compared on eleven instances of the minimum linear arrangement problem, which seeks an ordering of a graph’s vertices so as to minimize a sum over the graph’s edges. Episodes of recombination consistently and significantly improve the performance of the stochastic hill-climbers, and the resulting algorithm can compete with recent, good heuristics for the problem, at least on small the small instances addressed here.