DocuFLIP++ - OptiFLIP++/GenFLIP++ library description

GenFLIP++ library description


  1. Overview
  2. Task
  3. Embedding
  4. Genetic Algorithm
    1. History
    2. Methods
      1. Representation
      2. Initialization
      3. Evaluation Function
      4. Genetic Operators
    3. Strength and Weaknesses
  5. Genetic Algorithm and Scheduling
    1. Breeding Strategies
      1. Best n percent survive
      2. Best n percent descendants survive
      3. Proportional fitness survival
      4. Elitism
    2. Mutation
      1. Position-based mutation
      2. Order-based mutation
    3. Crossover
      1. Position-based crossover
      2. Order-based crossover
  6. GENFLIP++
    1. Interface
    2. Constants
    3. Methods
  7. GENFLIP++-The User Interface
    1. Strategy
    2. Crossover
    3. Mutation
    4. Repair-Steps
  8. 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.

Genetic Algorithm


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:


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.

Evaluation Function:

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:

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.

Strength and Weaknesses:

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.

Genetic Algorithm and Scheduling

Breeding Strategies

Best n percent survive:

This breeding strategy assumes that the best n percent of all strings survive. This means that parents and offspring are seen as one set.

Best n percent descendants survive:

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.

Proportional fitness survival:

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.


Position-based mutation:

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

Order-based mutation:

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

Position-based crossover:

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

Order-based crossover

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:
to define the crossover strategy the genetic algorithm will use. The default value is the "position-based crossover".
to define the mutation strategy the genetic algorithm will use. The default value is the "position-based mutation".
to define the survival-strategy the genetic algorithm will use. The default value is the "best n percent survive strategy".
to define how many individuals will survive. The meaning of the value is connected with the survival-strategy.
to define how many adults are allowed at one time.
to define how many children are allowed at one time.
to define the maximum number of mutations that will be applied to the init-strings.
to define whether the repair-steps given by DOMFLIP will be applied or not.
to copy a schedule into the genetic algorithm directly e(pointer-reference).
to copy a schedule into the genetic algorithm (a new instance within the genetic algorithm will be created).
to initialize the genetic algorithm. Always call this routine before one of the following routines.
evaluates one genetic-step.
evaluates the given number of genetic-steps.
evaluates a maximum number of genetic-steps (zero means infinity) and at the specified fitness.
returns the schedule with the highest fitness directly (pointer reference).
returns the schedule with the highest fitness by creating a new instance.


The following constants are defined within the genalg.h-File.


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.

GENFLIP++-The User Interface


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.


Back to DocuFLIP++ overview StarFLIP home page.

(c)1996 Andreas Raggl, Mazen Younes, Markus Bonner, Wolfgang Slany

Last modified: Tue Jun 24 15:42:43 MET-DST 1997 by StarFLIP Team