Logo
Distributed Genetic Programming Framework
print print

File org.dgpf.search.algorithms.sa.SAEngine.java

Here you can find all the information about the file org.dgpf.search.algorithms.sa.SAEngine.java. You may explore it here or download it onto your local disk.
/*
 * Copyright (c) 2006 Thomas Weise
 * 
 * E-Mail           : tweise@gmx.de
 * Creation Date    : 2006-06-05 13:27:42
 * Created by       : Stefan Niemczyk, Marc Kirchhoff
 * Original Filename: org.dgpf.search.algorithms.sa.SAEngine.java
 * Version          : 1.0.2
 * Last modification: 2006-07-13
 *                by: Thomas Weise
 * 
 * License          : GNU LESSER GENERAL PUBLIC LICENSE
 *                    Version 2.1, February 1999
 *                    You should have received a copy of this license along
 *                    with this library; if not, write to the Free Software
 *                    Foundation, Inc., 59 Temple Place, Suite 330, Boston,
 *                    MA 02111-1307, USA or download the license under
 *                    http://www.gnu.org/copyleft/lesser.html.
 *                    
 * Warranty         : This software is provided "as is" without any
 *                    warranty; without even the implied warranty of
 *                    merchantability or fitness for a particular purpose.
 *                    See the Gnu Lesser General Public License for more
 *                    details.
 */


package org.dgpf.search.algorithms.sa;

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;

import org.dgpf.search.api.Assigner;
import org.dgpf.search.api.FitnessAccessor;
import org.dgpf.search.api.Individual;
import org.dgpf.search.api.IndividualComparator;
import org.dgpf.search.api.NonDominatedList;
import org.dgpf.search.api.SearchEngine;
import org.dgpf.search.api.SearchStateBag;
import org.dgpf.search.api.SearchTask;
import org.dgpf.search.api.SearchTaskQueue;
import org.dgpf.search.api.SearchTask.SearchMutate;
import org.dgpf.search.api.SearchTask.SearchNew;
import org.sfc.collections.Arrays;
import org.sfc.math.stochastic.Randomizer;
import org.sfc.math.stochastic.statistics.StatisticInfoBag;
import org.sfc.utils.Typesafe;

/**
 * The search engine implementing the simulated annealing algorithm.
 * @param <Genotype> The genotype of the elements to be evolved.
 * @author Stefan Niemczyk, Marc Kirchhoff
 */

public class SAEngine<Genotype extends Serializable>
                               extends SearchEngine<Genotype>
  {
/**
 * The population of the simulatd annealing engine.
 */

  private       Individual<Genotype>[]          m_population  ;
/**
 * The task array.
 */

  private       SearchTask<Genotype>[]          m_tasks_array  ;
/**
 * The search tasks.
 */

  private       SearchTaskQueue<Genotype>       m_tasks ;
  
/**
 * Create a new simulated annealing engine without providing additional 
 * information or parameters. This method will be used when loading a 
 * snapshot mostly.
 */

  protected SAEngine()
    {
    super();
    }

/**
 * Create a simulated annealing engine.
 * @param p_parameters  The parameters object guiding the evolution process.
 * @param p_ndl_size    The size of the non-dominated list. Set this
 *                      to <code>-1</code> for don't care.
 */

  protected SAEngine(final SAParameters<Genotype> p_parameters, 
                     final int                    p_ndl_size)
    {
    super(p_parameters, p_ndl_size);
    }
  
/**
 * This method is used to create the search state (and its accessor bag) to
 * be used by this search engine.
 * @return  A new search state (and its accessor bag).
 */

  @Override
  protected SearchStateBag<Genotype>  create_state  ()
    {
    return new SAStateBag<Genotype>(this.get_parameters()
                                        .get_fitness_function_count());
    }
  
/**
 * Obtain the size of the next population to be. This might change over
 * time if, for example, in a client-server System new servers are added.
 * 
 * @return  The size of the next population.
 */

  protected int compute_population_size()
    {
    return Runtime.getRuntime().availableProcessors();
    }
/**
 * Update the population size.
 * @return The new population size.
 */

  private final int update_population_size()
    {
    SAState<Genotype> l_sas;
    
    l_sas = Typesafe.cast(this.get_state());
    return l_sas.set_population_size(this.compute_population_size());
    }
  
/**
 * This method is called to initialize the search engine. You must add all
 * initialization code here.
 * @param p_deserialized  <code>true</code> if and only if this
 *                        initialization was called due to an
 *                        deserialization process, <code>false</code> if it
 *                        is the normal initialization in the constructor.
 */

  @Override
  protected void  initialize  (final boolean p_deserialized)
    {
    Individual<Genotype>[]  l_p;
    int                     l_i, l_ffc;
    
    super.initialize(p_deserialized);
    
    l_ffc = this.get_state().get_fitness_function_count();
    
    l_i   = this.update_population_size();
    this.m_tasks_array = Arrays.create(SearchTask.class, l_i);
    
    if(!p_deserialized)
      {      
      l_p = Arrays.create(Individual.class, l_i);
      
      for(--l_i; l_i >= 0; l_i--)
        {
        l_p[l_i] = new Individual<Genotype>(l_ffc);
        }
      this.m_population = l_p;
      }
        
    this.m_tasks = new SearchTaskQueue<Genotype>(this.m_population.length);
    }
  
/**
 * Calculate the fitness of the last generation.
 */

  private final void  calculate_fitness ()
    {
          Individual<Genotype>[]        l_p;
          int                           l_i;
    final SAStateBag<Genotype>          l_gsb;
    final int                           l_ps, l_ffc;
    final StatisticInfoBag[]            l_ai;
          SearchTask<Genotype>[]        l_x;
          SAStateBag<Genotype>          l_sasb;
          FitnessAccessor               l_fa;
          IndividualComparator          l_ic;
          SAParameters<Genotype>        l_sap;
          Individual<Genotype>      l_swp, l_z;
    
    l_p   = this.m_population;
    l_x   = this.m_tasks_array;
    l_sap  = Typesafe.cast(this.get_parameters());    
    l_ffc = l_sap.get_fitness_function_count();
    l_ps  = ((SAState<Genotype>)(this.get_state())).get_population_size();
    l_gsb = Typesafe.cast(this.get_state_bag());
    l_ai  = l_gsb.m_stat;
    
    this.add_tasks(l_ps);
    
    l_i = l_p.length;
    if(l_i < l_ps)
      {
      l_p = Arrays.create(Individual.class, l_ps << 1);
      System.arraycopy(this.m_population, 0, l_p, 0, l_i);
      for(; l_i < l_p.length; l_i++)
        {
        l_p[l_i] = new Individual<Genotype>(l_ffc);
        }
      this.m_population = l_p;
      }
    
    for(l_i = (l_ps-1); l_i >= 0; l_i--)
      {
      Assigner.assign(l_p[l_i], l_x[l_i]);
      }
    
    l_sasb = Typesafe.cast(this.get_state_bag());
    
// <-> <- find ich lustig
    

// perform statistics
    for(l_i = (l_ffc-1); l_i >= 0; l_i--)
      {
      l_fa = FitnessAccessor.get_accessor(l_i);

      Arrays.sort(l_p, l_ps, l_fa);
      l_ai[l_i].gather_info_sorted(l_p, l_fa, 0, l_ps);
      l_sasb.check_best(l_p[0], l_i);
      }
// check best
    l_ic = l_sap.get_comparator();
    Arrays.sort(l_p, l_ps, l_ic);
//    l_sasb.check_best(l_p[0], l_ic);
  // -> Done automatically by notify_nondominated
    
//  check for new undominated elements
    l_swp = l_p[0];
    this.notify_nondominated(l_swp);
    for(l_i = 1; l_i < l_ps; l_i++)
      {
      l_z = l_swp;
      l_swp = l_p[l_i];
      if(l_ic.compare(l_z, l_swp) < 0) break;
      this.notify_nondominated(l_swp);
      }
    
//apply additional insertion - immigrate new individuals for instance
    if(this.immigrate(l_p, l_ps, l_ic))
      {
      //Arrays.sort(l_p, l_ps, l_ic);
      best_to_front(l_p, 0, l_ps, l_ic);
      }
    }
  
/**
 * This method can be used instead of sorting the population array, because
 * we only need the best individual to be the first one.
 * @param p_pop     The population array.
 * @param p_start   The start index.
 * @param p_end     The exlusive end index..
 * @param p_comp    The comparator to use.
 * @param <T>       The genotype.
 * @return  The best individual.
 */

  protected static  final <T extends Serializable>  Individual<T>
                      best_to_front (final Individual<T>[]      p_pop,
                                     final int                  p_start,
                                           int                  p_end,
                                     final IndividualComparator p_comp)
    {
    Individual<T> l_x, l_y;
    int           l_i;
    
    l_x = p_pop[p_start];
    l_i = 0;
    for(--p_end; p_end > p_start; p_end--)
      {
      l_y = p_pop[p_end];
      if(p_comp.compare(l_x, l_y) > 1)
        {
        l_x = l_y;
        l_i = p_end;
        }
      }
    
    l_y              = p_pop[p_start];
    p_pop[p_start]   = l_x;
    p_pop[l_i]       = l_y;
    
    return l_x;
    }
  
/**
 * Enqueue the tasks into the task queue.
 */

  private final void  enqueue_tasks ()
    {
    final int                           l_ps, l_ops;
    final NonDominatedList<Genotype>    l_ndl;
    final int                           l_ffc;
          Individual<Genotype>[]        l_p;
          Individual<Genotype>          l_b;
          int                           l_i, l_j;
          long                          l_ul;
          SearchTaskQueue<Genotype>     l_q;
          SearchMutate<Genotype>        l_t;
          SearchTask<Genotype>[]        l_x;
          SAState<Genotype>             l_sas;
          boolean                       l_bb, l_n;
    
//initialize some variables
    l_q   = this.m_tasks;
    l_p   = this.m_population;
    l_sas = Typesafe.cast(this.get_state());
    l_ffc = l_sas.get_fitness_function_count();
    l_x   = this.m_tasks_array;
    l_ul  = l_sas.get_update_level();
    
//keep the current (old) population size.
    l_ops = l_sas.get_population_size();
    
//get the new population size - maybe some servers have been added or 
//disappeared, so the size of the next population might differ
    l_ps  = this.update_population_size();
    
    l_ndl = this.get_rel_non_dominated();
    
//check whether we'll create new elements, improved after talk with students
    l_bb  = ((l_ul <= 0) ||
             (this.get_parameters().get_comparator().is_useless(l_p[0])) &&
              l_ndl.isEmpty());
    l_sas.set_population_is_new(l_bb);
    
//ensure that there are enough tasks to create the next population
update_tasks:
      {
      l_i = l_x.length;
      l_n = (l_bb ^ (l_x[0] instanceof SearchNew));
//adjust task count to population size
//also: we try to reuse the tasks
      if(l_i < l_ps)
        {
        l_j = l_i;
        l_i = (l_ps << 1);
        l_x = Arrays.create(SearchTask.class, l_i);
        
        if(!l_bb)
          {
          System.arraycopy(this.m_tasks_array, 0, l_x, 0, l_j);
          for(; l_j < l_i; l_j++)
            {
            l_x[l_j] = (l_bb ? new SearchNew<Genotype>(l_ffc)
                             : new SearchMutate<Genotype>(l_ffc));
            }
          this.m_tasks_array = l_x;
          break update_tasks;
          }
        this.m_tasks_array = l_x;
        }
      
      if(l_n)
        {
        for(--l_i; l_i >= 0; l_i--)
          {
          l_x[l_i] = (l_bb ? new SearchNew<Genotype>(l_ffc)
                           : new SearchMutate<Genotype>(l_ffc));
          }
        }
      }
    
    
    if(l_bb)        
      {
      for(l_i = (l_ps-1); l_i >= 0; l_i--)
        {
        l_q.add_task(l_x[l_i]);
        }
      }
    else
      {    
      l_b = compute_individual(l_p[0]);
      
      for(l_i = (l_ps-1); l_i >= 0; l_i--)
        {
        l_t = ((SearchMutate<Genotype>)(l_x[l_i]));
        l_t.set_parent(l_b);
        l_q.add_task(l_t);
        }
      
      if(l_ul > 1)
        {
        this.emigate(l_p, l_ops);
        }
      }
    }
  
/**
 * Calculate the individual which will be used to create the new generation
 * @param p_best_individual     The best individual of the last generation
 * @return             The individual to use.
 */

  private final Individual<Genotype> compute_individual(
      final Individual<Genotype> p_best_individual)
   {
   SAState<Genotype>             l_sas;
   Individual<Genotype>     l_rb;
   IndividualComparator         l_ic;
   SAParameters<Genotype>       l_sap;
   Randomizer                    l_r;
   double             l_t, l_p, l_d;
     
   l_sas=Typesafe.cast(this.get_state());
   l_rb=l_sas.get_rel_best();
   l_sap=Typesafe.cast(this.get_parameters());
   l_ic=l_sap.get_comparator();
   l_r=this.get_randomizer();
   l_t=l_sas.get_temperature();
   l_d=0;
  
//   if(p_best_individual.get_individual().equals(l_rb.get_individual()))
//     return p_best_individual;
   
   l_d=l_ic.get_scalar_difference(l_rb, p_best_individual);
   
   l_p=Math.exp(l_d/l_t);
   if(l_p>=l_r.nextDouble()) return p_best_individual;
   
   return l_rb;
   }
  
/**
 * Called after the update, should be used to select individuals to be
 * emigrated.
 * @param p_population  The population array.
 * @param p_count       The population size, i.e. the count of valid
 *                      individuals in the population.
 */

  protected void  emigate (final Individual<Genotype>[] p_population,
                           final int                    p_count)
    {
    //
    }
  

/**
 * This hook allows you to insert some additional individuals by overriding
 * existing ones.
 * @param p_population  The population array.
 * @param p_count       The population size, i.e. the count of valid items
 *                      inside the population array.
 * @param p_comparator  The comparator to be used for insertion.
 * @return  <code>true</code> if and only if at least one new individual
 *          has been injected into the population, <code>false</code>
 *          otherwise.
 */

  protected boolean immigrate
                      (final Individual<Genotype>[]   p_population,
                       final int                      p_count,
                       final IndividualComparator     p_comparator)
    {
    return false;
    }
  
  

/**
 * Perform an update of the parameters and state. When overriding this
 * method, make sure to update the state's statistics before calling this
 * method.
 * @return  <code>true</code> if and only if the search should continue,
 *          <code>false</code> otherwise.
 */

  @Override
  protected boolean  update  ()
    {
    this.m_tasks.wait_for();
    
    this.calculate_fitness();

    if(super.update())
      {
      this.inner_update();
      this.enqueue_tasks();

      return true;
      }

    return false;
    }
  


/**
 * Obtain the internal task queue to obtain the tasks from.
 * @return The internal task queue to obtain the tasks from.
 */

  protected final SearchTaskQueue<Genotype> get_task_queue()
    {
    return this.m_tasks;
    }


  
/**
 * This method aborts the activity. It is guaranteed to be called only once
 * for aborting and once for shutdown.
 * @see #abort()
 * @see #shutdown()
 */

  @Override
  protected void  do_abort  ()
    {
    super.do_abort();
    this.m_tasks.abort();
    }

/**
 * Startup the search. This method will be called by <code>start()</code>.
 * @see #start()
 */

  @Override
  protected void  do_start  ()
    {
    super.do_start();

    this.enqueue_tasks();
    this.begin_work();
    }
  
/**
 * <p>
 * This method will be called every generation after the fitness has been
 * calculated and the state was updated, but before the genetic tasks are
 * entered in the task queue.</p><p>
 * You may use it to update worker threads.</p>
 */

  protected void  inner_update  ()
    {
    //
    }
  
/**
 * Store a snapshot into an object output stream.
 * @param p_oos The object output stream to write to.
 * @throws  IOException If io fails.
 */

  @Override
  protected void  do_write_snapshot (final ObjectOutputStream p_oos)
        throws IOException
    {
    SAState<Genotype>       l_sas;
    int                     l_ps;
    Individual<Genotype>[]  l_i;

    super.do_write_snapshot(p_oos);

    l_sas = Typesafe.cast(this.get_state());
    l_ps = l_sas.get_population_size();
    l_i  = this.m_population;

    for(--l_ps; l_ps >= 0; l_ps--)
      {
      p_oos.writeUnshared(l_i[l_ps]);
      }
    }
  
/**
 * Read a snapshot from an object input stream.
 * @param p_ois  The object input stream to read from.
 * @throws  IOException             If io goes terribly wrong.
 * @throws  ClassNotFoundException  If a vital class could not be found.
 */

  @Override
  protected void  do_read_snapshot  (final ObjectInputStream  p_ois)
        throws IOException, ClassNotFoundException
    {
    final SAState<Genotype>       l_sas;
    final int                     l_ps, l_j, l_ffc;
          int                     l_z;
    final Individual<Genotype>[]  l_i;
          Individual<Genotype>    l_ii;

    super.do_read_snapshot(p_ois);

    l_sas = Typesafe.cast(this.get_state());
    l_ps = l_sas.get_population_size();
    l_j  = this.update_population_size();
    
    l_i  = Arrays.create(Individual.class, Math.max(l_j, l_ps));

    for(l_z = (l_ps-1); l_z >= 0; l_z--)
      {
      l_i[l_z] = Typesafe.cast(p_ois.readUnshared());
      }

    if(l_j != l_ps)
      {
      if(l_j > l_ps)
        {
        Arrays.sort(l_i, l_ps, this.get_parameters().get_comparator());
        
        l_ffc = l_sas.get_fitness_function_count();
        for(l_z = l_ps; l_z < l_j; l_z++)
          {
          l_ii     = new Individual<Genotype>(l_ffc);
          Assigner.assign(l_ii, l_i[l_z - l_ps]);
          l_i[l_z] = l_ii;
          }
        }
      }    
    
    Arrays.sort(l_i, l_j, this.get_parameters().get_comparator());
    
    this.m_population = l_i;
    }
  
  
/**
 * The human readable name of the search engine.
 * @return The human readable name of the search engine.
 */

  @Override
  public  String  toString  ()
    {
    return "Simulated Annealing Engine";
    }
  }

File Information:

file name:SAEngine.java
package:org.dgpf.search.algorithms.sa
qualified name:org.dgpf.search.algorithms.sa.SAEngine.java
file type:Java Source File
download location:download http://dgpf.sourceforge.net/source/org/dgpf/search/algorithms/sa/SAEngine.java
size:18.140 KB (18576 B)
uploaded: 2015-07-22 04:10:59 GMT+0000
last update: 2006-07-13 12:13:08 GMT+0000
last access: 2017-11-20 19:01:31 GMT+0000

statistics online since 2006-01-02.   RSS Feed
Contact us by sending an email to tweise@gmx.de to receive further information, to report errors, or to join our project.
All content on this site (http://dgpf.sourceforge.net/) is LGPL-licensed.
http://dgpf.sourceforge.net/scripts/source/source.php last modified at 2015-07-22 04:10:53 GMT+0000 served at 2017-11-20 19:01:31 GMT+0000.
Valid CSS Valid XHTML 1.1
Valid RSS SourceForge.net Logo