A new uniform order-based crossover operator for genetic algorithm applications to multi-component combinatorial optimization problems

Abstract

In this thesis, a new uniform order-based crossover operator to be used in genetic algorithm applications to combinatorial optimization problems is presented. There are three pure types of combinatorial problems: assignment, sequencing and selection problems. Most real world combinatorial problems involve components from these three types at the same time. The new operator is applicable to multi-component combinatorial optimization problems which involve one sequencing and one or more selection components. Examples are in abundance and include communications network design problems, machine and project scheduling problems. The operator is called the multi-component uniform order-based crossover or MCUOX. MCUOX processes ordering and value information concurrently. It works within a natural and direct representation of the problems. It is both general and powerful by being able to effectively search all the components of the problem. It enhances building block propagation, never violates precedence constraints given the parents are precedence; feasible, and is able to deal with additional selection components without any significant overhead. The application and effectiveness of MCUOX is illustrated at the hand of three well known difficult problems: simultaneous scheduling of machines and automated guided vehicles, resource constrained project scheduling problem with discounted cash flows, and parallel machine scheduling with earliness and tardiness penalties.|Keywords: Crossover operators, genetic algorithms, combinatorial optimization