- Overview
- Task
- Embedding
- Genetic Algorithm
- Genetic Algorithm and Scheduling
- GENFLIP++
- GENFLIP++-The User Interface
- 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.

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 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.)

As there is no theory describing the right operators for a specific problem, designed a good genetic algorithm is some sort of black magic.

predecessor: A B C D E F swap A and F * * successor: F B C D E AThe position-based mutation can be written in pseudo-code as: pos-based()

pos1 is rand() pos2 is rand() (...,xpos2,.....,xpos1,....) is (...,xpos1,....,xpos2,....)

predecessor: A B C D E F push F in front of A *1 *2 successor: F A B C D EThe order-based mutation can be written in pseudo-code like this:

ord-based() pos1 is rand() pos2 is rand() (...,xpos1,.....,xpos2,...) is (...,xpos2,xpos1,...)

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.

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

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

- 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.

- 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

An entry will be inserted in both listed sorted by the fitness to allow an easy implementation of the survival strategies.

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.

- 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