Elena Perez web page: top image

HOME | RESEARCH | PROJECTS

 

  

 

Newcomers to GAs

                                                                                                                                                                                                                                                               

 

Last update: 06/2011
 

    OPTIMIZATION PROBLEMS
 

There are three types of optimization problems.

  • The first one tries to solve problems with only one optimization function and only one global optimum.

  • The second type (called multi-objective problem) tries to optimize problems with several optimization functions .

  • The third (called multi-modal problem) type focuses on problems with only one optimization function but with several global and local optima.

 
 

    GENETIC ALGORITHMS

 

A Genetic Algorithm (GA) is a global search technique used in computing to find solutions to search and optimization problems. GAs emerged in the 1960's. They use principles inspired by biology such as inheritance, mutation, selection, and crossover.

 

The main parts of GAs are the following:

 

■ Coding the solutions

 

■ Evaluation

 

■ Selection & Recombination

 

■ Replacement
 

Simple Pseudo-code:

1. Coding the solutions

2. Choose the initial population of individuals

3. Evaluate the fitness of each individual in that population

4. Repeat on this generation until termination: (time limit, sufficient fitness achieved, etc.)

1. Select the best-fit individuals for reproduction

2. Breed new individuals through crossover and mutation operations to give birth to offspring

3. Evaluate the individual fitness of new individuals

4. Replace least-fit population with new individuals

5. Decoding the solutions

 
 

    GAs' BASIC CONCEPTS
 

 

Resumen extendido

 (only in Spanish)  

 

GAs' basic concepts are illustrated by the Travelling Salesman Problem (TSP). Given a list of cities (m) and their pairwise distances, the TSP�s task is to find a shortest possible tour that visits each city exactly once. TSP is defined by a matrix of pairwise distances between the cities.

Concept Biology meaning TSP

Solution

living organism

cities� tour

Chromosome

(also called genome)

Set of parameters which define a living organism (proposed solution to the problem)

An string whose length is m:

[-, -, -, -, -]

Genotype

Genetic constitution of a living organism. One's genotype differs subtly from one's genomic sequence.

A permutation of m numbers.

One possible solution: [1, 2, 3, ...m], which indicates the visiting order of the cities: firstly, the city coded by 1, etc.

Gene

Basic unit of heredity in a living organism.

Each integer of the string

Fenotype

Observable characteristic

The decoding of the string:

[city-1, city-2, city-3,..,city-m]

 
   

Universidad de Valladolid. Webmaster � Marta Posada