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

GenFLIP++ library description

Contents

  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

Overview

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.

Task

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.

Embedding

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

History

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.

Methods

A genetic algorithm to solve a problem must have 5 components:

Representation:

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:

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.

Elitism:

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.

Mutation

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: 
ord-based()
	pos1 is rand()
	pos2 is rand()
	(...,xpos1,.....,xpos2,...) is (...,xpos2,xpos1,...)

Crossover

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

GENFLIP++

Interface

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.

Constants

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

Methods

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

Strategy

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.

Crossover

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.

Mutation

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.

Repair-Steps

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.

References

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