Skip to main content
main-content

Über dieses Buch

OmeGA: A Competent Genetic Algorithm for Solving Permutation and Scheduling Problems addresses two increasingly important areas in GA implementation and practice. OmeGA, or the ordering messy genetic algorithm, combines some of the latest in competent GA technology to solve scheduling and other permutation problems. Competent GAs are those designed for principled solutions of hard problems, quickly, reliably, and accurately. Permutation and scheduling problems are difficult combinatorial optimization problems with commercial import across a variety of industries.

This book approaches both subjects systematically and clearly. The first part of the book presents the clearest description of messy GAs written to date along with an innovative adaptation of the method to ordering problems. The second part of the book investigates the algorithm on boundedly difficult test functions, showing principled scale up as problems become harder and longer. Finally, the book applies the algorithm to a test function drawn from the literature of scheduling.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Development of the Ordering Messy Genetic Algorithm

Abstract
This chapter develops the ordering messy GA (OmeGA), a fast messy GA (fmGA) specialized for permutation problems. It represents the solutions by vectors of real numbers—the so-calledrandom keysintroduced by Bean (1994). In a number of experiments it is shown that the OmeGA significantly outperforms the simple GA in solving ordering deceptive problems, which are hard sequencing problems defined elsewhere (Kargupta et al., 1992).
Dimitri Knjazew

Chapter 2. Performance Analysis of the Omega

Abstract
The experimental results of the previous chapter have shown that the ordering messy GA is able to solve ordering deceptive problems of length 32. The problems were composed of eight order-four deceptive subfunctions. The OmeGA outperformed the random key-based simple GA for problems with loosely coded building blocks. However, the experiments were conducted with non-overlapping BBs of equal size and scale, that is, with uniform contribution to the fitness function.
Dimitri Knjazew

Chapter 3. Application to a Scheduling Problem

Abstract
In the previous chapters we tested the OmeGA and the RKGA only on artificial problems with a predefined structure of the BBs. However, as was said in the second chapter, it is hard or even impossible to estimate the building-block structure of real-world problems. We do not know the number, the size, or the scale of the BBs. It is also unclear whether they overlap or not.
Dimitri Knjazew

Chapter 4. Conclusions and Future Work

Abstract
In this book we have developed the ordering messy genetic algorithm and have successfully tested its performance in pilot experiments with ordering deceptive problems. By using an adaptive representation scheme, it becomes relatively independent from the underlying problem coding and outperforms the simple GA.
Dimitri Knjazew

Backmatter

Weitere Informationen