Class: Ai4r::GeneticAlgorithm::TspChromosome

Inherits:
ChromosomeBase show all
Defined in:
lib/ai4r/genetic_algorithm/tsp_chromosome.rb

Overview

Chromosome implementation for the Travelling Salesman Problem.

Instance Attribute Summary

Attributes inherited from ChromosomeBase

#data, #normalized_fitness

Class Method Summary collapse

Instance Method Summary collapse

Methods inherited from ChromosomeBase

#initialize

Constructor Details

This class inherits a constructor from Ai4r::GeneticAlgorithm::ChromosomeBase

Class Method Details

.mutate(chromosome, mutation_rate = 0.3) ⇒ Object

Parameters:

  • chromosome (Object)
  • mutation_rate (Object) (defaults to: 0.3)

Returns:

  • (Object) 


26
27
28
29
30
31
32
33
34
35
36
37
 
# File 'lib/ai4r/genetic_algorithm/tsp_chromosome.rb', line 26

def self.mutate(chromosome, mutation_rate = 0.3)
  return unless chromosome.normalized_fitness && rand < ((1 - chromosome.normalized_fitness) * mutation_rate)

  data = chromosome.data
  # Swapping the first two cities can sometimes keep the fitness
  # unchanged depending on the cost matrix. Pick an inner segment
  # instead to ensure the route actually changes.
  index = (1...(data.length - 1)).to_a.sample
  data[index], data[index + 1] = data[index + 1], data[index]
  chromosome.data = data
  chromosome.instance_variable_set(:@fitness, nil)
end

.reproduce(a, b, crossover_rate = 0.4) ⇒ Object

Parameters:

  • a (Object)
  • b (Object)
  • crossover_rate (Object) (defaults to: 0.4)

Returns:

  • (Object) 


43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
 
# File 'lib/ai4r/genetic_algorithm/tsp_chromosome.rb', line 43

def self.reproduce(a, b, crossover_rate = 0.4)
  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.positive?
    next_token = if token != b.data.last && available.include?(b.data[b.data.index(token) + 1])
                   b.data[b.data.index(token) + 1]
                 elsif token != a.data.last && available.include?(a.data[a.data.index(token) + 1])
                   a.data[a.data.index(token) + 1]
                 else
                   available.sample
                 end
    token = next_token
    available.delete(token)
    spawn << next_token
    a, b = b, a if rand < crossover_rate
  end
  new(spawn)
end

.seed ⇒ Object

Returns:

  • (Object) 


67
68
69
70
71
72
73
74
 
# File 'lib/ai4r/genetic_algorithm/tsp_chromosome.rb', line 67

def self.seed
  data_size = @@costs[0].length
  available = []
  0.upto(data_size - 1) { |n| available << n }
  seed = []
  seed << available.delete(available.sample) while available.length.positive?
  new(seed)
end

.set_cost_matrix(costs) ⇒ Object

Parameters:

  • costs (Object)

Returns:

  • (Object) 


78
79
80
 
# File 'lib/ai4r/genetic_algorithm/tsp_chromosome.rb', line 78

def self.set_cost_matrix(costs)
  @@costs = costs
end

Instance Method Details

#fitness ⇒ Object

Returns:

  • (Object) 


10
11
12
13
14
15
16
17
18
19
20
21
 
# File 'lib/ai4r/genetic_algorithm/tsp_chromosome.rb', line 10

def fitness
  return @fitness if @fitness

  last_token = @data[0]
  cost = 0
  @data[1..].each do |token|
    cost += @@costs[last_token][token]
    last_token = token
  end
  @fitness = -1 * cost
  @fitness
end