Multi-chromosome mixed encodings for heterogeneous problems

Genetic algorithms (GAs) are an effective optimization tool for use on problems that have a large complex set of possible solutions. Traditionally, GAs have been mainly applied to problems with homogeneous structure, eg. encodings with either a set of floating point numbers, a set of integers, a binary string, a permutation of symbols, or an expression tree. Recently, more attention has been devoted to more heterogeneous problems that require a compound encoding such as an expression tree, a set of integers, and a permutation of symbols. In the field of engineering these more complex problem types are common and each of the different components of the problem must be optimized concurrently. This paper presents a methodology for solving compound problems with a genetic algorithm. To illustrate this methodology a problem is presented that requires the simultaneous optimization of a permutation as well as a set of integer values. The problem is a modified travelling salesperson problem where at each city the salesperson must choose a type of transport for the next leg of the journey. There are associated costs with each transport type that are a function of the distance of the leg of travel as well as the number of legs that a single mode of transport is utilized.