Class: Moea::Dominance

Inherits:
Object
  • Object
show all
Defined in:
../lib/dominance.rb

Overview

General purpose class for computing various pareto dominance metrics. It provides these types of dominance rankings: 


  * Dominance Count, 
  * Dominance Rank,
  * Dominance Depth (NSGA), 
  * Pareto Strength (SPEA)

See citeseerx.ist.psu.edu/viewdoc/dowload?doi=10.1.1.12.4172&rep=rep1&type=pdf for Dominance Count and Dominance Rank, see ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=996017 for Dominance depth, see ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=934438 or eprints.kfupm.edu.sa/52319/1/52319.pdf for Pareto Strength.

All Dominance methods assume that 


  1. the population is the Enumerable container of individuals and 
  2. the method individual.dominates?( other ) returning true if the individual dominates other one.

Defined Under Namespace

Classes: DominanceDepth, DominanceFields

Instance Attribute Summary (collapse)

Instance Method Summary (collapse)

Constructor Details

- (Dominance) initialize

A new instance of Dominance 



25
26
27
 
# File '../lib/dominance.rb', line 25

def initialize
  @at_least = nil
end

Instance Attribute Details

- (Object) at_least

How much individuals should be classified into Pareto Layers before the classification stops (nil means unlimited, ie. population.size) 



30
31
32
 
# File '../lib/dominance.rb', line 30

def at_least
  @at_least
end

Instance Method Details

- (Object) depth(population)

Compute Pareto Depth (see Deb’s NGSA-II) with the complexity O(MN^2) where N is the population size and M is the number of objectives. 


  Dominance.new.depth( population ) { |original,depth| ... }
  The block is called with the original population's individual and the depth value.
  The depth is the index of the dominance layer whose the individual is a member (see Dominance#layers)

The block need not to be called for individuals with the higher depth (see the at_least attribute). 



79
80
81
82
83
 
# File '../lib/dominance.rb', line 79

def depth population
  dom = depth_core( population ).first
  return dom unless block_given?
  dom.each { |fields| yield( fields.original, fields.depth ) }
end

- (Object) layers(population)

Compute Pareto Dominance Layers (see Deb’s NGSA-II) with the complexity O(MN^2) where N is the population size and M is the number of objectives. 


    layers = Dominance.new.depth( population )

The array of layers is returned. Each layer is an array of original individuals, such as: 


  * the layers[0] contains only nondominated individuals
  * layers[1] contains nondominated individuals of the population1 (ie the original population without layers[0] members)
  * layers[2] contains nondominated individuals of the population2 (ie the population1 without layers[1] members) 
  ...

Note the at_least attribute may limit the number of individuals classified to layers. The classification stops when 


   layers.flatten.size >= at_least.


99
100
101
102
103
 
# File '../lib/dominance.rb', line 99

def layers population
  depth_core( population ).last.map do |layer|
    layer.map { |item| item.original }
  end
end

- (Object) rank_count(population)

Compute Dominance Rank, Dominance Count and Pareto Strength for the individual i. There are two variants: 


  
    population2 = Dominance.new.rank_count population
    * population2[i].original ... original population's individual
    * population2[i].rank (Dominance Rank) ... the number of individuals by which the individual i is dominated
    * population2[i].count (Dominance Count)  ... the number of individuals dominated by the individual i
    * population2[i].spea (Pareto Strength) ... sum of Dominance Counts of all individals dominating the individual i

    or
    population2 = Dominance.new.rank_count( population ) { |original,rank,count,spea| ... }
      where the block is called for each individual in the population.


45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
 
# File '../lib/dominance.rb', line 45

def rank_count population
  dom = population.map { |orig| DominanceFields.new( orig, 0, Set.new, 0 ) }

  dom.each do |individual1|
    dom.each_with_index do |individual2,index2|
      if individual1.original.dominates? individual2.original
        individual1.dominates.add(index2)
        individual2.rank += 1
      end
    end
  end

  dom.each do |individual|
    individual.dominates.each { |index| dom[index].spea += individual.dominates.size }
    individual.count = individual.dominates.size
  end

  if block_given?
    dom.each { |fields| yield( fields.original, fields.rank, fields.count, fields.spea ) }
    return population
  end
  
  dom
end