site/src/documentation/content/xdocs/geneticAlgorithms.xml in ai4r-1.1 vs site/src/documentation/content/xdocs/geneticAlgorithms.xml in ai4r-1.2
- old
+ new
@@ -3,50 +3,10 @@
<document>
<header>
<title>Genetics Algorithms in Ruby :: ai4r</title>
</header>
<body>
- <section id="Introduction">
- <title>Introduction to Genetics Algorithms in Ruby</title>
- <p>The GeneticAlgorithm module implements the GeneticSearch and Chromosome classes. The GeneticSearch is a generic class, and can be used to solved any kind of problems. The GeneticSearch class performs a stochastic search
- of the solution of a given problem. It uses the following pseudocode:
- </p>
- <ol>
- <li>Choose initial population</li>
- <li>Evaluate the fitness of each individual in the population</li>
- <li>Repeat as many times as generations we allow
- <ol>
- <li>Select randomly best-ranking individuals to reproduce</li>
- <li>Breed new generation through crossover and mutation (genetic operations) and give birth to offspring</li>
- <li>Evaluate the individual fitnesses of the offspring</li>
- <li>Replace worst ranked part of population with offspring</li>
- </ol>
- </li>
- </ol>
- <p>The Chromosome is "problem specific". Ai4r built-in Chromosomeclass was designed to model the <a href="http://en.wikipedia.org/wiki/Traveling_salesman_problem" title="Link to Wikipedia">Travelling salesman problem</a>. You have to provide a matrix with the cost of traveling from one point to another (array of arrays of float values). If you want to solve other type of problem, you will have to modify the Chromosome class, by overwriting its fitness, reproduce, and mutate functions, to model you specific problem.</p>
- </section>
-
-<section id="how-to-run">
- <title>How to use it</title>
-<source>
-<![CDATA[
-#Cost of traveling from one point to another. E.g. Travelling from Node 0 to Node 2 costs 5.
-data_set = [ [ 0, 10, 5],
- [ 6, 0, 4],
- [25, 4, 0]
- ]
-
-GeneticAlgorithm::Chromosome.set_cost_matrix(data_set)
-
-search = GeneticAlgorithm::GeneticSearch.new(10, 20)
-result = search.run
-puts "Result cost: #{result.fitness}"
-puts "Result nodes: #{result.data.inspect}"
-]]>
-</source>
- </section>
-
<section id="Example">
<title>The European Rock Tour Problem (Also known as the Travelling salesman problem)</title>
<p>An ageing rock band was planning its (hopefully) last european tour. They were planning to visite 15 european cities: Barcelona, Berlin, Brussels, Dublin, Hamburg, Kiev, London, Madrid, Milan, Moscow, Munich, Paris, Rome, Vienna, and Warsaw.</p>
<p><img src="images/europe2.png" alt="European Tour" /></p>
<p>They start planning the trip, when they realize that they could save a lot of money, if they ordered the cities to minimize the traveling cost. So they decided to try all possible combinations. The sat in front of the computer, visited they favorite traveling site, and started typing. 53 hours and several liters of coffee later, they realized it was a little bit more complicated than what they expected. They called their drummer (who was on vacations) and explained the problem to him. Fortunately, their drummer had a Master in Computer Science degree.</p>
@@ -70,44 +30,60 @@
</p>
<p>I forgot to tell another restriction of this problem: This band is really bad (What did you expect? Their drummer is a computer geek!) so once they visited a city, they cannot go back there.
</p>
</section>
+ <section id="Introduction">
+ <title>Introduction to Genetics Algorithms in Ruby</title>
+ <p>A Genetic Algorithm is a particular class of evolutionary algorithm and stochastic search.
+ It aims to find the best possible solution in a solution domain, by selecting a simple
+ set of solutions (chosed randomly or with a simple heuristic), and making it "evolve".
+ </p>
+ <p>It works based on the following pseudocode:</p>
+ <ol>
+ <li>Choose initial population</li>
+ <li>Evaluate the fitness of each individual in the population</li>
+ <li>Repeat as many times as generations we allow
+ <ol>
+ <li>Select randomly best-ranking individuals to reproduce</li>
+ <li>Breed new generation through crossover and mutation (genetic operations) and give birth to offspring</li>
+ <li>Evaluate the individual fitnesses of the offspring</li>
+ <li>Replace worst ranked part of population with offspring</li>
+ </ol>
+ </li>
+ </ol>
+ </section>
-<section id="Results">
- <title>Results of using Genetic Algorithms to the The European Rock Tour Problem (or Travelling salesman problem)</title>
- <p>The cost of 3 randomly selected tours:</p>
- <ul>
- <li>$17486.01 : Madrid Vienna Moscow Berlin Brussels Munich Milan Barcelona London Hamburg Warsaw Dublin Kiev Paris Rome</li>
- <li>$20198.92 : London Rome Brussels Kiev Hamburg Warsaw Barcelona Paris Munich Dublin Vienna Moscow Madrid Milan Berlin</li>
- <li>$17799.34 : Madrid Milan Kiev Vienna Warsaw London Barcelona Hamburg Paris Munich Dublin Berlin Moscow Rome Brussels</li>
- </ul>
- <p>3 tours obtained with an initial population of 800, and after 100 generations:</p>
- <ul>
- <li>$7611.99 : Moscow Kiev Warsaw Hamburg Berlin Munich Vienna Milan Rome Barcelona Madrid Paris Brussels London Dublin</li>
- <li>$7596.74 : Moscow Kiev Warsaw Berlin Hamburg Munich Vienna Milan Rome Barcelona Madrid Paris Brussels London Dublin (See Image)</li>
- <li>$7641.61 : Madrid Barcelona Rome Milan Paris Dublin London Brussels Hamburg Berlin Vienna Munich Warsaw Kiev Moscow</li>
- </ul>
- <p><img src="images/europe3.png" alt="Best tour result using Genetic Algorithms in ruby" /></p>
- <p>The GeneticSearch class is an generic class to try to solve any kind of problem using genetic algorithms. If you
-want to model another type of problem, you will have to modify the Chromosome class, defining its fitness, mutate, and reproduce functions.</p>
- </section>
-
<section id="chromosome-impl">
<title>Implementation of Chromosome class for the Travelling salesman problem</title>
- <p>Although the GeneticSearch class is an generic class to try to solve any kind of problem using genetic algorithms, the Chromosome class is problem specific.</p>
+ <p>In AI4R, the GeneticAlgorithm module implements the GeneticSearch and Chromosome classes.
+ GeneticSearch is a generic class, and can be used to solved any kind of problems.
+ The GeneticSearch class performs a stochastic search following the algorithm mentioned in the
+ previous section.
+ </p>
+ <p>
+ However, the Chromosome class implementation is problem specific.
+ Ai4r built-in Chromosomeclass was designed to model the
+ <a href="http://en.wikipedia.org/wiki/Traveling_salesman_problem" title="Link to Wikipedia">
+ Travelling salesman problem.
+ </a>
+ You have to provide a matrix with the cost of traveling from one point to another
+ (array of arrays of float values).
+ If you want to solve other type of problem, you will have to modify the Chromosome class,
+ by overwriting its fitness, reproduce, and mutate functions, to model you specific problem.
+ </p>
<section id="chromosome-impl-data">
<title>Data representation</title>
<p>Each chromosome must represent a posible solution for the problem. This class conatins an array
with the list of visited nodes (cities of the tour). The size of the tour is obtained automatically from the traveling costs matrix. You have to assign the costs matrix BEFORE you run the genetic search. The following costs matrix could be used to solve the problem with only 3 cities:</p>
<source>
<![CDATA[
data_set = [ [ 0, 10, 5],
[ 6, 0, 4],
[25, 4, 0]
]
-GeneticAlgorithm::Chromosome.set_cost_matrix(data_set)
+Ai4r::GeneticAlgorithm::Chromosome.set_cost_matrix(data_set)
]]>
</source>
</section>
<section id="chromosome-impl-fitness">
<title>Fitness function</title>
@@ -120,12 +96,12 @@
<![CDATA[
data_set = [ [ 0, 10, 5],
[ 6, 0, 4],
[25, 4, 0]
]
-GeneticAlgorithm::Chromosome.set_cost_matrix(data_set)
-chromosome = GeneticAlgorithm::Chromosome.new([0, 2, 1])
+Ai4r::GeneticAlgorithm::Chromosome.set_cost_matrix(data_set)
+chromosome = Ai4r::GeneticAlgorithm::Chromosome.new([0, 2, 1])
chromosome.fitness
# => -9
]]>
</source>
<p>That is: From 0 to 2 costs 5. From 2 to 1 costs 4. Total cost is 9.</p>
@@ -183,11 +159,11 @@
<title>Initialize the search</title>
<p>You have to provide two parameters during instantiation: The initial population size, and the how many generations produce. Large numbers will usually converge to better results, while small numbers will have better performance.</p>
<source>
<![CDATA[
-search = GeneticAlgorithm::GeneticSearch.new(10, 20)
+search = Ai4r::GeneticAlgorithm::GeneticSearch.new(10, 20)
result = search.run
]]>
</source>
</section>
<section id="search-impl-run">
@@ -235,20 +211,39 @@
</source>
</section>
</section>
+<section id="how-to-run">
+ <title>How to use AI4R Genetic Search implementation</title>
+<source>
+<![CDATA[
+#Cost of traveling from one point to another. E.g. Travelling from Node 0 to Node 2 costs 5.
+data_set = [ [ 0, 10, 5],
+ [ 6, 0, 4],
+ [25, 4, 0]
+ ]
+Ai4r::GeneticAlgorithm::Chromosome.set_cost_matrix(data_set)
+search = Ai4r::GeneticAlgorithm::GeneticSearch.new(10, 20)
+result = search.run
+puts "Result cost: #{result.fitness}"
+puts "Result nodes: #{result.data.inspect}"
+]]>
+</source>
+ </section>
+
<section id="example-run">
<title>How to run the example</title>
<p>You can run the example with "ruby genetic_algorithm_example.rb". The genetic_algorithm_example.rb file
contains:</p>
<source>
<![CDATA[
-require File.dirname(__FILE__) + '/../../lib/genetic_algorithm/genetic_algorithm'
-require 'csv'
+require "rubygems"
+require "ai4r/genetic_algorithm/genetic_algorithm"
+require "csv"
# Load data from data_set.csv
data_set = []
CSV::Reader.parse(File.open("#{File.dirname(__FILE__)}/travel_cost.csv", 'r')) do |row|
data_set << row
@@ -256,20 +251,39 @@
data_labels = data_set.shift
data_set.collect! do |column|
column.collect { |element| element.to_f}
end
-GeneticAlgorithm::Chromosome.set_cost_matrix(data_set)
+Ai4r::GeneticAlgorithm::Chromosome.set_cost_matrix(data_set)
puts "Beginning genetic search, please wait... "
-search = GeneticAlgorithm::GeneticSearch.new(800, 100)
+search = Ai4r::GeneticAlgorithm::GeneticSearch.new(800, 100)
result = search.run
puts "Result cost: #{result.fitness}"
puts "Result tour: "
result.data.each { |c| print " #{data_labels[c]}"}
]]>
</source>
+ </section>
+
+<section id="Results">
+ <title>Results of using Genetic Algorithms to the The European Rock Tour Problem (or Travelling salesman problem)</title>
+ <p>The cost of 3 randomly selected tours:</p>
+ <ul>
+ <li>$17486.01 : Madrid Vienna Moscow Berlin Brussels Munich Milan Barcelona London Hamburg Warsaw Dublin Kiev Paris Rome</li>
+ <li>$20198.92 : London Rome Brussels Kiev Hamburg Warsaw Barcelona Paris Munich Dublin Vienna Moscow Madrid Milan Berlin</li>
+ <li>$17799.34 : Madrid Milan Kiev Vienna Warsaw London Barcelona Hamburg Paris Munich Dublin Berlin Moscow Rome Brussels</li>
+ </ul>
+ <p>3 tours obtained with an initial population of 800, and after 100 generations:</p>
+ <ul>
+ <li>$7611.99 : Moscow Kiev Warsaw Hamburg Berlin Munich Vienna Milan Rome Barcelona Madrid Paris Brussels London Dublin</li>
+ <li>$7596.74 : Moscow Kiev Warsaw Berlin Hamburg Munich Vienna Milan Rome Barcelona Madrid Paris Brussels London Dublin (See Image)</li>
+ <li>$7641.61 : Madrid Barcelona Rome Milan Paris Dublin London Brussels Hamburg Berlin Vienna Munich Warsaw Kiev Moscow</li>
+ </ul>
+ <p><img src="images/europe3.png" alt="Best tour result using Genetic Algorithms in ruby" /></p>
+ <p>The GeneticSearch class is an generic class to try to solve any kind of problem using genetic algorithms. If you
+want to model another type of problem, you will have to modify the Chromosome class, defining its fitness, mutate, and reproduce functions.</p>
</section>
<section id="more-genetic-run">
<title>More about Genetic Algorithms and the Travelling salesman problem</title>
<p><a href="http://en.wikipedia.org/wiki/Traveling_salesman_problem" title="Link to Wikipedia">Travelling salesman problem at Wikipedia</a></p>