Class: FeldtRuby::Optimize::Archive

Inherits:
Object
  • Object
show all
Includes:
Logging
Defined in:
lib/feldtruby/optimize/archive.rb

Overview

An archive keeps a record of all “interesting” candidate solutions found during optimization. It has two purposes: to contribute to the optimization itself (since seeding a search with previously “good” solutions can improve convergence speed) but also to provide a current view of the best and most interesting solutions found.

Interestingness is hard to define but we posit that two elements are always important:

1. Being good, i.e. having good values for one or many of the sub-objectives
2. Being different, i.e. behaving differently (phenotypic diversity) or 
     looking different (genotypic diversity), than other candidate solutions.

Different types of optimization can require different trade-offs between these elements but all archives should support both types inherently. The default choices for the main class is to use the quality calculated by the objective class to judge “being good” and to use a diversity objective to judge “being different”.

We also posit that it is not enough only to be diverse (although there is some research showing that novelty search in itself may be as good/important as directed search) so the default behavior is to only add a solution to the diversity top lists if it is within a certain percentage of the best solutions on the other (being good) top list. Thus the basic design is to keep one top list per fitness goal, one overall aggregate fitness top list and then one top list per diversity goal.

We note that diversity is just another type of objective (although a relative rather than an absolute one) and we can use the existing classes to implement that. A default diversity objective looks at genotypic and fitness diversity by default but more elaborate schemes can be used.

One way to make this model easier to understand is to call the three types:

generalists    (overall good, aggregated fitness best)
specialists    (doing one thing very, very good, sub-objective fitness best)
weirdos        (different but with clear qualitites, ok but diverse)

Defined Under Namespace

Classes: GlobalTopList, GoalTopList, WeirdoTopList

Constant Summary collapse

DefaultParams = 
{
  :NumTopPerGoal => 5, # Number of solutions in top list per individual goal
  :NumTopAggregate => 20, # Number of solutions in top list for aggregate quality

  # Number of solutions in diversity top list. This often needs to 
  # be larger than the other top lists since there are "more" ways to be 
  # diverse than to be good... OTOH it costs CPU power to have large values
  # here since the quality values needs to be recalculated whenever there is
  # a new best. So we keep them small.
  :NumTopDiversityAggregate => 10,

  # Max percent distance (given as a ratio, i.e. 0.05 means 5%) from best 
  # solution (top of Aggregate list) that a solution is allowed to have 
  # to be allowed on the diversity list. If it is more than 5% from best
  # we don't consider adding it to a diversity list.
  :MaxPercentDistanceToBestForDiversity => 0.05
}

Instance Attribute Summary collapse

Attributes included from Logging

#logger

Instance Method Summary collapse

Methods included from Logging

#__find_logger_set_on_instance_vars, #new_default_logger, #setup_logger_and_distribute_to_instance_variables

Constructor Details

#initialize(fitnessObjective, diversityObjective, params = DefaultParams.clone) ⇒ Archive

Returns a new instance of Archive.



67
68
69
70
71
72
73
 
# File 'lib/feldtruby/optimize/archive.rb', line 67

def initialize(fitnessObjective, diversityObjective, params = DefaultParams.clone)
  @objective = fitnessObjective
  self.diversity_objective = diversityObjective
  @params = DefaultParams.clone.update(params)
  init_top_lists
  setup_logger_and_distribute_to_instance_variables(@params)
end

Instance Attribute Details

#diversity_objective ⇒ Object

Returns the value of attribute diversity_objective.



63
64
65
 
# File 'lib/feldtruby/optimize/archive.rb', line 63

def diversity_objective
  @diversity_objective
end

#generalists ⇒ Object (readonly)

Returns the value of attribute generalists.



65
66
67
 
# File 'lib/feldtruby/optimize/archive.rb', line 65

def generalists
  @generalists
end

#objective ⇒ Object (readonly)

Returns the value of attribute objective.



63
64
65
 
# File 'lib/feldtruby/optimize/archive.rb', line 63

def objective
  @objective
end

#specialists ⇒ Object (readonly)

Returns the value of attribute specialists.



65
66
67
 
# File 'lib/feldtruby/optimize/archive.rb', line 65

def specialists
  @specialists
end

#weirdos ⇒ Object (readonly)

Returns the value of attribute weirdos.



65
66
67
 
# File 'lib/feldtruby/optimize/archive.rb', line 65

def weirdos
  @weirdos
end

Instance Method Details

#add(candidate) ⇒ Object

Add a candidate to the top lists if it is good enough to be there. Throws out worse candidates as appropriate.



99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
 
# File 'lib/feldtruby/optimize/archive.rb', line 99

def add(candidate)
  @specialists.each {|tl| tl.add(candidate)}

  # Detect if we get a new best one by saving the previous best.
  prev_best = best
  @generalists.add candidate

  # If there was a new best we invalidate the diversity quality values since
  # they are relative and must be recalculated. Note that this might incur
  # a big penalty if there are frequent changes at the top.
  if prev_best != best
    prev_qv = prev_best.nil? ? "" : @objective.quality_of(prev_best)
    logger.log_data :new_best, {
      "New best" => best,
      "New quality" => @objective.quality_of(best),
      "Old best" => prev_best,
      "Old quality" => prev_qv}, "Archive: New best solution found", true

    # We must delete weirdos that are no longer good enough to be on the 
    # weirdos list.
    to_delete = []
    @weirdos.each {|w| 
      # Invalidate quality since it must now be re-calculated (since it will
      # typically depend on the best and we have a new best...)
      @diversity_objective.invalidate_quality_of(w)

      to_delete << w unless good_enough_quality_to_be_interesting?(w)
    }
    #puts "Deleting #{to_delete.length} out of #{@weirdos.length} weirdos"
    #@weirdos.delete_candidates(to_delete)

  elsif good_enough_quality_to_be_interesting?(candidate)
    # When we add a new one this will lead to re-calc of the diversity quality
    # of the previous ones if there has been a new best since last time.
    @weirdos.add candidate
  end
end

#best ⇒ Object 



81
82
83
84
 
# File 'lib/feldtruby/optimize/archive.rb', line 81

def best
  # The top of the Generalists top list is the overall best
  @generalists[0]
end

#good_enough_quality_to_be_interesting?(candidate) ⇒ Boolean

Is quality of candidate good enough (within MaxPercentDistanceToBestForDiversity from quality of best candidate)

Returns:

  • (Boolean) 


139
140
141
142
143
144
145
 
# File 'lib/feldtruby/optimize/archive.rb', line 139

def good_enough_quality_to_be_interesting?(candidate)
  qv_best = @objective.quality_of(best).display_value
  qv = @objective.quality_of(candidate).display_value
  res = ((qv_best - qv).abs / qv_best) <= @params[:MaxPercentDistanceToBestForDiversity]
  #puts "qvbest = #{qv_best}, qv = #{qv}, res = #{res}"
  res
end

#init_top_lists ⇒ Object 



86
87
88
89
90
91
92
93
94
95
 
# File 'lib/feldtruby/optimize/archive.rb', line 86

def init_top_lists
  @specialists = Array.new
  @objective.num_goals.times do |i|
    @specialists << GoalTopList.new(@params[:NumTopPerGoal], @objective, i)
  end

  @generalists = GlobalTopList.new(@params[:NumTopAggregate], @objective)

  @weirdos = WeirdoTopList.new(@params[:NumTopDiversityAggregate], @diversity_objective, @objective)
end

#to_json(*a) ⇒ Object 



247
248
249
250
251
252
253
254
255
 
# File 'lib/feldtruby/optimize/archive.rb', line 247

def to_json(*a)
  {
    'json_class'   => self.class.name,
    'data'         => {
      'generalists' => @generalists,
      'specialists' => @specialists,
      'weirdos' => @weirdos},
  }.to_json(*a)
end