BBC Home

Explore the BBC

Front Page

Life | The Universe | Everything | Advanced Search
 
Front PageReadTalkContributeHelp!FeedbackWho is Online

Click here to complete your registration.

 
3. Everything / Maths, Science & Technology / Artificial Life & Genetics
3. Everything / Maths, Science & Technology / Mathematics

Genetic Algorithms

A genetic algorithm (GA) is a process that uses mechanisms analogous to those found in biological evolution to solve multi-constraint (many variable) problems.

The Process

The problem must first be encoded such that it can be concisely described and manipulated. This usually involves concatenating1 place holders for each of the variables in some kind of string or list of objects. An initial population of these strings or lists (genomes) is then generated with completely random values in the place holders (genes).

Each string is then tested against some function to obtain a fitness value. The fitness values of all strings are then compared and some policy for selecting mating couples is brought to bear. This policy can vary from one implementation to another and has a significant impact on the convergence of the population.

Pairs of strings are mated by partitioning them at some random point along their length and swapping, or crossing, half of each string at that point. Whist randomly chosen, the crossover point should be common to both parents to ensure that resulting strings keep the same length.

Crossover is executed one or more times on a mating pair, generating a new child each time.

Randomly selected children may be modified at a randomly chosen point along their length (locus) at birth to simulate mutation.

Newly generated children are then fitness tested and inserted into the population wherever their fitness value is found to be higher than an existing member. Weaker members are deselected in this way.

After fitness testing, crossover and replacement have been executed, the process is repeated on the new population.

As generations advance, fitness values will rise and the strings in a population might eventually converge on a particular set of values. This is not necessarily a good thing as the point at which they converge might be a false peak on the fitness landscape for this problem.

Any multi-constraint problem is a potential target for the application of GAs. Time tabling, route planning and scheduling systems are ideal.


1 Concatenating means to bring things together.

Discuss this Entry  People have been talking about this Guide Entry. Here are the most recent Conversations:

<whoosh>
(Last Posting: Mar 2, 2003)

Genetic Algorithms... Ooooh...
(Last Posting: Nov 10, 2000)

Genetic Algorithms
(Last Posting: Apr 14, 2002)




Add your Opinion!

There are tens of thousands of h2g2 Guide Entries, written by our Researchers. If you want to be able to add your own opinions to the Guide, simply become a member as an h2g2 Researcher. Tell me More!

 
Entry Data
Entry ID: A281774 (Edited)

Written and Researched by:
Si

Edited by:
U276


Date: 29   March   2000


Text only
Like this page?
Send it to a friend


Referenced Guide Entries
Algorithms


Most of the content on this site is created by h2g2's Researchers, who are members of the public. The views expressed are theirs and unless specifically stated are not those of the BBC. The BBC is not responsible for the content of any external sites referenced. In the event that you consider anything on this page to be in breach of the site's House Rules, please click here to alert our Moderation Team. For any other comments, please start a Conversation below.
 


Front PageReadTalkContributeHelp!FeedbackWho is Online

Most of the content on h2g2 is created by h2g2's Researchers, who are members of the public. The views expressed are theirs and unless specifically stated are not those of the BBC. The BBC is not responsible for the content of any external sites referenced. In the event that you consider anything on this page to be in breach of the site's House Rules, please click here. For any other comments, please start a Conversation above.


About the BBC | Help | Terms of Use | Privacy & Cookies Policy