DocuFLIP++ - OptiFLIP++/GenFLIP++ library description
picture
GenFLIP++ library description
Contents
- Overview
- Task
- Embedding
- Genetic Algorithm
- History
- Methods
- Representation
- Initialization
- Evaluation Function
- Genetic Operators
- Strength and Weaknesses
- Genetic Algorithm and Scheduling
- Breeding Strategies
- Best n percent survive
- Best n percent descendants survive
- Proportional fitness survival
- Elitism
- Mutation
- Position-based mutation
- Order-based mutation
- Crossover
- Position-based crossover
- Order-based crossover
- GENFLIP++
- Interface
- Constants
- Methods
- GENFLIP++-The User Interface
- Strategy
- Crossover
- Mutation
- Repair-Steps
- References
This document describes a genetic algorithm that has been implemented
to optimize a given schedule within the FLIP++-Environment. The FLIP++
project intends to solve scheduling-problems by means of
Fuzzy-Logic. Fuzzy-Logic is used to describe the constraints that must be
taken into account to create a valid schedule and to evaluate it.
The CD-Labor for Experten Systeme has a library under development
which is able to solve scheduling-problems by means of Fuzzy-Logic.
One part of this library is the OPTIFLIP-modul which has the task of
making chances in the scheduling in such a way that the result is an
optimized schedule that does not violate given constraints.
Several methods will be implemented by the CD-Labor. The
implementation of a genetic algorithm becomes interesting when we try to find out
whether this method or specialized search-methods are more
sophisticated in solving scheduling problems.
A Part of DOMFLIP contains the optimization algorithms whereas the genetic
algorithm is implemented as a seperate object that is then linked to the
domflip-object.
The genetic algorithm must be included (#include "genalg.h") in the
domflip.h-File.
In domlib.h you can already find the enumeration-type optmethode that
has a "GeneticAlg" value. To set the Genetic Algorithm as the default
optimization method you have to call the set_opt_meth(GeneticAlg) of
the Domain-object.
The field of genetic algorithms has been founded by John Holland. His
publication of Adaptation in Natural and Artificial Systems (Holland 1975) describes the ability of simple
representations (bit strings) to encode complicated structures and
simple transformations which have enough power to improve such
structures. Holland showed that with the proper control structure,
rapid improvements of bit strings could occur under certain
transformations, so that a population of bit strings could be made to
evolve as a population of animals would.
An important formal result was that even in large and complicated
search spaces, genetic algorithms would tend to converge on solutions
that were globally optimal or nearly so.
A genetic algorithm to solve a problem must have 5 components:
- a chromosomal representation of solutions to the problem
- a way to create an initial population of solutions
- an evaluation function that plays the role of the environment, rating solutions in term of their "fitness"
- genetic operators that alter the composition of children during reproduction
- values of the parameters that the genetic algorithm uses (population size, probabilities of applying genetic operators, etc.)
In Holland's work chromosomes are bit strings. Some researchers have
explored the uses of other representations, often in connection with
industrial applications of genetic algorithms. Examples of other
representations include embedded lists (for scheduling problems) and
variable-element lists (for semiconductor layout).
Initialization routines vary. Moving from a randomly created
population to a well-adapted population is a good test of the
algorithm, since the critical features of the final solution will have
been produced by the search and recombination mechanism of the
algorithm, rather than the initialization procedure.
There are a great number of evaluation functions that enhance or
hinder a genetic algorithm's performance. An important question to be
considered in designing an evaluation function is the implementation
of constraints on solutions. Constraints that cannot be violated can
be implemented by imposing great penalties on individuals that violate
them.
Genetic operators for bit string representations have been extensively
studied, while operators for other representation types have not. A
good part of the engineering task at present in applying genetic
algorithms to industrial problems lies in choosing a chromosomal
representation of solutions and a set of genetic operators.
Genetic algorithms promise to be a reusable, easy to implement and
fast search method for vast search-spaces. No doubt that this is true,
the performance and results of genetic algorithms depend very strong
on the applied genetic operators and the evaluation function.
As there is no theory describing the right operators for a specific
problem, designed a good genetic algorithm is some sort of black
magic.
This breeding strategy assumes that the best n percent of all strings
survive. This means that parents and offspring are seen as one set.
This strategy is slightly different from "best n percent survive" but
this difference has a great impact on the overall population. Each
step the GA does all parents die and just the best n percent of the
offspring survive. This strategy comes close to the strategy nature
uses but has the disadvantage that good solutions can be forgotten.
This strategy assumes that strong (respectively good) individuals
produce more offspring than less good individuals. Therefore the
number of children is proportional to the fitness of the parents and
the possibility to die is the same for the whole population.
This strategy is quite non-biological but produces good results in the
case of computers. It assumes that the best individual survives no
matter whether it is from the parent population or a child. Further,
the best n percent of descendants survive. Should it be the case that
the fittest individual of the new generation is worse than the
unfittest individual of the parents generation, therefore the worst
individual of the new generation will be replaced by the best
individual of the parent generation.
The idea of the position-based mutation is to swap two genes in the
string by random.
predecessor: A B C D E F swap A and F
* *
successor: F B C D E A
The position-based mutation can be written in pseudo-code as:
pos-based()
pos1 is rand()
pos2 is rand()
(...,xpos2,.....,xpos1,....) is (...,xpos1,....,xpos2,....)
The idea of the order-based mutation is to push one randomly selected
gene in front of another randomly selected gen.
predecessor: A B C D E F push F in front of A
*1 *2
successor: F A B C D E
The order-based mutation can be written in pseudo-code like this:
ord-based()
pos1 is rand()
pos2 is rand()
(...,xpos1,.....,xpos2,...) is (...,xpos2,xpos1,...)
The idea of the crossover is that several characteristics of a number
of elements are combined into a new string. This can be described for
biological systems with the cutting of parent strings into several
pieces and rearranging them into a new string by making a selection
over the pieces.
This model can not be easily transformed for scheduling-problems as a
gene in a schedule has to describe a specific job. Just cutting the
parent strings and rearranging them could cause a duplication of
certain jobs.
The idea of the position-based crossover is to shift the gene to the
position corresponding to that of the other parent.
parents: offspring:
A B C D E F G A G C D E F B shift B in front of G
* *
G F E D C B A G A E D C B F shift F in front of A
The idea behind the order-based crossover is to swap the genes in the
order found at the other parent.
parents offspring:
A B C D E F G A G C D E F B swap B with G
* *
G F E D C B A G A E D C B F swap F with A
The interface of the genalg-object is implemented within the genalg.h-file.
The following public methods are accessible:
- set_crossover
- to define the crossover strategy the genetic algorithm
will use. The default value is the "position-based crossover".
- set_mutation
- to define the mutation strategy the genetic algorithm
will use. The default value is the "position-based mutation".
- set_strategie
- to define the survival-strategy the genetic algorithm
will use. The default value is the "best n percent survive strategy".
- set_percent_survivers
- to define how many individuals will survive. The
meaning of the value is connected with the survival-strategy.
- set_max_strings_number
- to define how many adults are allowed at one time.
- set_max_childs_number
- to define how many children are allowed at one time.
- set_max_init_mixture
- to define the maximum number of mutations that will be applied to the init-strings.
- set_repair(true/false)
- to define whether the repair-steps given by DOMFLIP will be applied or not.
- set_string
- to copy a schedule into the genetic algorithm directly e(pointer-reference).
- set_string_copy
- to copy a schedule into the genetic algorithm (a new instance within the genetic algorithm will be created).
- init_start_strings
- to initialize the genetic algorithm. Always call this routine before one of the following routines.
- one_step
- evaluates one genetic-step.
- several_steps
- evaluates the given number of genetic-steps.
- go_to_fitness
- evaluates a maximum number of genetic-steps (zero means infinity) and at the specified fitness.
- get_string_with_highest_fitness
- returns the schedule with the highest fitness directly (pointer reference).
- get_string_with_highest_fitness_copy
- returns the schedule with the highest fitness by creating a new instance.
The following constants are defined within the genalg.h-File.
- Kinds of mutations:
- POSITION_BASED_MUTATION
- ORDER_BASED_MUTATION
- Kinds of crossover:
- POSITION_BASED_CROSSOVER
- ORDER_BASED_CROSSOVER
- Kinds of survival strategies:
- BEST_N_PERCENT_SURVIVE
- BEST_N_PERCENT_DESCENDANTS_SURVIVE
The implementation of the genetic algorithm uses two double linked
lists. One (called actual_generation) holds the parent-schedules and
the schedules that survived a genetic algorithm step. The other
(called children) holds the descendants of the parent-schedules after
crossover and mutation.
An entry will be inserted in both listed sorted by the fitness to
allow an easy implementation of the survival strategies.
To select a strategy ,all the known strategies to the GA are listed in an
"Listbox". You can only select one Strategy at one time.
One part of the strategy is to determine the maximum number of
individuals and children for one step of the GA. Be careful in setting
these values, as you can produce an infinite amount of individuals
which will lead the program to stop when no more memory is available.
To select the crossover all crossover-methods supported by the GA are
listed in an "Listbox". You can only select one crossover-method at
a time.
To select the mutations that will by applied to our children all
supported crossover-methods are listed in a "Listbox". Here you are
allowed to make a multiple-selection.
To define that the repair-steps will be applied to a new element, a
toggle-button is provided to switch this feature on and off.
- Wolfgang Slany, "Fuzzy Scheduling"; CD-Technical Report 94/66
- Mario Girsch, "Optimierung von Schedules mit Genetischen Algorithmen und Iterativer Vertiefung"
- John Holland, "Adaptation in Natural and Artificial Systems"; (Holland 1975)
- Lawrence Davis and Martha Steenstrup, "Genetic Algorithms and Simulated Annealing"
- David E. Glover, "Solving a Comples Keyboard Configuration Problem Through Generalized Adaptive Search"
- Grefenstette, "Incorporating Problems Specific Knowledge into Genetic Algorithms"
(c)1996 Andreas Raggl, Mazen Younes, Markus Bonner, Wolfgang Slany
Last modified: Tue Jun 24 15:42:43 MET-DST 1997
by StarFLIP Team