Genetic Algorithms
The course will introduce one of the evolutionary computation techniques:
the genetic algorithm.
The methodology of genetic algorithms will be described and
the course will demonstrate various applications of these algorithms.
More precisely, it will show how these probabilistic search algorithms,
modeled after organic evolution, can be used to obtain good solutions
when applied to NP-complete combinatorial optimization problems,
such as the maximum-cut, the minimum tardy task, the set covering,
the terminal assignment, scheduling problems and graph coloring problems.
The course will then explore the application of genetic algorithms to
the problems of multiple sequence alignment and DNA fragment assembly.
The course will also discuss the schemata theorem, including its
virtues and shortcomings. Walsh functions functions will also be
introduced. They form a convenient basis for the expansion of fitness
functions. These orthogonal, rectangular functions, have been used to
compute
the average fitness values of schemata, to decide whether a certain
function is hard or easy for a genetic algorithm, and to design
deceptive functions for the genetic algorithm.
We will investigate the use of Haar functions for the same purpose,
and compare them to Walsh functions.
The Fast Walsh-Haar transforms will be explored.