Parent

Files

Ai4r::GeneticAlgorithm::Chromosome

A Chromosome is a representation of an individual solution for a specific problem. You will have to redifine the Chromosome representation for each particular problem, along with its fitness, mutate, reproduce, and seed methods.

Attributes

data[RW]
normalized_fitness[RW]

Public Class Methods

mutate(chromosome) click to toggle source

mutation method is used to maintain genetic diversity from one generation of a population of chromosomes to the next. It is analogous to biological mutation.

The purpose of mutation in GAs is to allow the algorithm to avoid local minima by preventing the population of chromosomes from becoming too similar to each other, thus slowing or even stopping evolution.

Calling the mutate function will "probably" slightly change a chromosome randomly.

This implementation of "mutation" will (probably) reverse the order of 2 consecutive randome nodes (e.g. from [ 0, 1, 2, 4] to [0, 2, 1, 4]) if:

((1 - chromosome.normalized_fitness) * 0.4)
# File lib/ai4r/genetic_algorithm/genetic_algorithm.rb, line 204
def self.mutate(chromosome)
  if chromosome.normalized_fitness && rand < ((1 - chromosome.normalized_fitness) * 0.3)
    data = chromosome.data
    index = rand(data.length-1)
    data[index], data[index+1] = data[index+1], data[index]
    chromosome.data = data
    @fitness = nil
  end
end
new(data) click to toggle source
# File lib/ai4r/genetic_algorithm/genetic_algorithm.rb, line 165
def initialize(data)
  @data = data
end
reproduce(a, b) click to toggle source

Reproduction method is used to combine two chromosomes (solutions) into a single new chromosome. There are several ways to combine two chromosomes: One-point crossover, Two-point crossover, "Cut and splice", edge recombination, and more.

The method is usually dependant of the problem domain. In this case, we have implemented edge recombination, wich is the most used reproduction algorithm for the Travelling salesman problem.

# File lib/ai4r/genetic_algorithm/genetic_algorithm.rb, line 222
def self.reproduce(a, b)
  data_size = @@costs[0].length
  available = []
  0.upto(data_size-1) { |n| available << n }
  token = a.data[0]
  spawn = [token]
  available.delete(token)
  while available.length > 0 do 
    #Select next
    if token != b.data.last && available.include?(b.data[b.data.index(token)+1])
      next_token = b.data[b.data.index(token)+1]
    elsif token != a.data.last && available.include?(a.data[a.data.index(token)+1])
      next_token = a.data[a.data.index(token)+1] 
    else
      next_token = available[rand(available.length)]
    end
    #Add to spawn
    token = next_token
    available.delete(token)
    spawn << next_token
    a, b = b, a if rand < 0.4
  end
  return Chromosome.new(spawn)
end
seed() click to toggle source

Initializes an individual solution (chromosome) for the initial population. Usually the chromosome is generated randomly, but you can use some problem domain knowledge, to generate a (probably) better initial solution.

# File lib/ai4r/genetic_algorithm/genetic_algorithm.rb, line 251
def self.seed
  data_size = @@costs[0].length
  available = []
  0.upto(data_size-1) { |n| available << n }
  seed = []
  while available.length > 0 do 
    index = rand(available.length)
    seed << available.delete_at(index)
  end
  return Chromosome.new(seed)
end
set_cost_matrix(costs) click to toggle source
# File lib/ai4r/genetic_algorithm/genetic_algorithm.rb, line 263
def self.set_cost_matrix(costs)
  @@costs = costs
end

Public Instance Methods

fitness() click to toggle source

The fitness method quantifies the optimality of a solution (that is, a chromosome) in a genetic algorithm so that that particular chromosome may be ranked against all the other chromosomes.

Optimal chromosomes, or at least chromosomes which are more optimal, are allowed to breed and mix their datasets by any of several techniques, producing a new generation that will (hopefully) be even better.

# File lib/ai4r/genetic_algorithm/genetic_algorithm.rb, line 176
def fitness
  return @fitness if @fitness
  last_token = @data[0]
  cost = 0
  @data[1..-1].each do |token|
    cost += @@costs[last_token][token]
    last_token = token
  end
  @fitness = -1 * cost
  return @fitness
end

[Validate]

Generated with the Darkfish Rdoc Generator 2.