Logo
Distributed Genetic Programming Framework
print print

File org.dgpf.search.algorithms.ga.GeneticEngine.java

Here you can find all the information about the file org.dgpf.search.algorithms.ga.GeneticEngine.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-04-10 09:49:19
 * Original Filename: org.dgpf.search.algorithms.ga.GeneticEngine.java
 * Version          : 2.1.10
 * Last modification: 2006-07-09
 *                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.ga;

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.SearchParameters;
import org.dgpf.search.api.SearchStateBag;
import org.dgpf.search.api.SearchTaskQueue;
import org.dgpf.search.api.SearchTask.SearchCrossover;
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;

/**
 * This is the base class for all genetic engines. It provides the standard
 * behavior allowing to evolve a population of solution candidates,
 * so-called individuals.
 *
 * @param <Genotype>    The sort of genotype used to represent individuals.
 *                      This must be a serializable type.
 *
 * @author Thomas Weise
 */

public abstract class GeneticEngine<Genotype extends Serializable>
       extends  SearchEngine<Genotype>
  {
/**
 * The population of the genetic engine.
 */

  private       Individual<Genotype>[]          m_population  ;
/**
 * The repository for "crossover"-tasks.
 */

  private       SearchCrossover<Genotype>[]     m_crossover ;
/**
 * The repository for "mutate"-tasks.
 */

  private       SearchMutate<Genotype>[]        m_mutate  ;
/**
 * The repository for "new"-tasks.
 */

  private       SearchNew<Genotype>[]           m_new ;
/**
 * The search tasks.
 */

  private       SearchTaskQueue<Genotype>       m_tasks ;
/**
 * The count of crossover tasks.
 */

  private       int                             m_ctc ;
/**
 * The count of mutation tasks.
 */

  private       int                             m_mtc ;
/**
 * The count of new tasks.
 */

  private       int                             m_ntc ;
/**
 * <code>true</code> if our population is not sorted.
 */

  private       boolean                         m_unsorted;

/**
 * Create a new genetic engine without providing additional information or
 * parameters. This method will be used when loading a snapshot mostly.
 */

  protected GeneticEngine  ()
    {
    super();
    }

/**
 * Create a genetic 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 GeneticEngine  (final GeneticParameters<Genotype> p_parameters,
                            final int                         p_ndl_size)
    {
    super(p_parameters, p_ndl_size);
    }


/**
 * 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 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 GeneticStateBag<Genotype>(
                    this.get_parameters().get_fitness_function_count());
    }

/**
 * This method is called to initialize the search engine. You must 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)
    {
    int                             l_fc, l_ps, l_mc, l_cc, l_nc  ;
    GeneticState<Genotype>          l_gs;
    Individual<Genotype>[]    l_i;
    SearchNew<Genotype>[]           l_n;
    SearchMutate<Genotype>[]        l_m;
    SearchCrossover<Genotype>[]     l_c;

    super.initialize(p_deserialized);

    l_gs = Typesafe.cast(this.get_state());

    l_fc = l_gs.get_fitness_function_count();
    l_ps = l_gs.get_population_size();
    l_mc = (int)(1.5d + (l_ps * l_gs.get_mutation_rate()));
    l_cc = (int)(1.5d + (l_ps * l_gs.get_crossover_rate()));
    l_nc = Math.max(0, (l_ps - l_cc - l_mc));

//    if(this.m_population == null)
//      {
    if(!p_deserialized)
      {
      l_i = Arrays.create(Individual.class, l_ps);
      for(--l_ps; l_ps >= 0; l_ps--)
        {
        l_i[l_ps] = new Individual<Genotype>(l_fc);
        }
      this.m_population = l_i;
      }
//      }

    l_n = Arrays.create(SearchNew.class, l_nc);
    for(--l_nc; l_nc >= 0; l_nc--)
      {
      l_n[l_nc] = new SearchNew<Genotype>(l_fc);
      }
    this.m_new        = l_n;

    l_m = Arrays.create(SearchMutate.class, l_mc);
    for(--l_mc; l_mc >= 0; l_mc--)
      {
      l_m[l_mc] = new SearchMutate<Genotype>(l_fc);
      }
    this.m_mutate     = l_m;

    l_c = Arrays.create(SearchCrossover.class, l_cc);
    for(--l_cc; l_cc >= 0; l_cc--)
      {
      l_c[l_cc] = new SearchCrossover<Genotype>(l_fc);
      }
    this.m_crossover = l_c;

    this.m_tasks  = new SearchTaskQueue<Genotype>(l_ps);
    }


/**
 * 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();
    }


/**
 * 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();    
    }





/**
 * This method allows you to perform additional selection based operations
 * on the population. By doing so, you can, for example, select some
 * individuals for migration if implementing genetic algorithms that use
 * island hopping.  The individuals in the array are ordered by the search's
 * current comparator, with the fittest individual at index <code>0</code>
 * and the worst at index <code>p_count-1</code>.
 * @param p_population    The population array.
 * @param p_count         The population count.
 * @param p_selection     The selection algorithm to use.
 * @param p_random        A randomizer that can be used.
 * @param p_ndl           The non-dominated individual list.
 * @param p_elp           The elitism percentage.
 */

  protected void  select_additional
                      (final Individual<Genotype>[]     p_population,
                       final int                        p_count,
                       final SelectionAlgorithm         p_selection,
                       final Randomizer                 p_random,
                       final NonDominatedList<Genotype> p_ndl,
                       final double                     p_elp)
    {
    //
    }

/**
 * This hook allows you to insert some additional individuals by overriding
 * existing ones.
 * @param p_population  The population array.
 * @param p_count       The count of individuals in 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 insert_additional
                      (final Individual<Genotype>[]   p_population,
                       final int                            p_count,
                       final IndividualComparator           p_comparator)
    {
    return false;
    }

/**
 * Calculate the fitness of the last generation.
 */

  private final void  calculate_fitness ()
    {
    final GeneticState<Genotype>          l_gs;
    final GeneticStateBag<Genotype>       l_gsb;
    final int                             l_ps, l_fc;
          int                             l_i, l_k, l_mc, l_cc, l_nc;
          Individual<Genotype>[]          l_pop;
    final SearchNew<Genotype>[]           l_sn;
    final SearchMutate<Genotype>[]        l_sm;
    final SearchCrossover<Genotype>[]     l_sc;
    final StatisticInfoBag[]              l_ni, l_mi, l_ci, l_ai;
          FitnessAccessor                 l_fa;
    final IndividualComparator            l_ic;
          Individual<Genotype>            l_swp, l_z;
    final SearchParameters<Genotype>      l_gp;

    l_gs  = Typesafe.cast(this.get_state());
    l_ps  = (this.m_ctc + this.m_mtc + this.m_ntc);
    l_pop = this.m_population;
    l_i   = l_pop.length;
    l_fc  = l_gs.get_fitness_function_count();
    l_sn  = this.m_new;
    l_sm  = this.m_mutate;
    l_sc  = this.m_crossover;
    l_gsb = Typesafe.cast(this.get_state_bag());
    l_ni  = l_gsb.m_new_stat;
    l_mi  = l_gsb.m_mutation_stat;
    l_ci  = l_gsb.m_crossover_stat;
    l_ai  = l_gsb.m_all_stat;
    l_gp  = this.get_parameters();

    this.add_tasks(l_ps);

    if(l_ps > l_i)
      {
      l_pop = Arrays.create(Individual.class, (l_ps * 3) >>> 1 );
      System.arraycopy(this.m_population, 0, l_pop, 0, l_i);
      for(; l_i < l_ps; l_i++)
        {
        l_pop[l_i] = new Individual<Genotype>(l_fc);
        }
      this.m_population = l_pop;
      }
    else
      {
      if(l_i > (3*l_ps))
        {
        l_pop = Arrays.create(Individual.class, l_ps);
        System.arraycopy(this.m_population, 0, l_pop, 0, l_ps);
        this.m_population = l_pop;
        }
      }

// clear the population
    for(l_i = (l_ps-1); l_i >= 0; l_i--)
      {
      Assigner.clear(l_pop[l_i]);
      }
    
// copy results
    l_mc = this.m_mtc;
    l_i  = 0;

    for(l_k = (l_mc-1); l_k >= 0; l_k--)
      {
      Assigner.assign(l_pop[l_i++], l_sm[l_k]);
      }

    l_cc = this.m_ctc;
    for(l_k = (l_cc-1); l_k >= 0; l_k--)
      {
      Assigner.assign(l_pop[l_i++], l_sc[l_k]);
      }

    l_nc = this.m_ntc;
    for(l_k = (l_nc-1); l_k >= 0; l_k--)
      {
      Assigner.assign(l_pop[l_i++], l_sn[l_k]);
      }

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

      Arrays.sort(l_pop, l_ps, l_fa);
      l_ai[l_i].gather_info_sorted(l_pop, l_fa, 0, l_ps);
      l_gsb.check_best(l_pop[0], l_i);

      Arrays.sort(l_sm, l_mc, l_fa);
      l_mi[l_i].gather_info_sorted(l_sm, l_fa, 0, l_mc);

      Arrays.sort(l_sc, l_cc, l_fa);
      l_ci[l_i].gather_info_sorted(l_sc, l_fa, 0, l_cc);

      Arrays.sort(l_sn, l_nc, l_fa);
      l_ni[l_i].gather_info_sorted(l_sn, l_fa, 0, l_nc);
      }

// find best
    l_ic = l_gp.get_comparator();
    Arrays.sort(l_pop, l_ps, l_ic);
//    l_gsb.check_best(l_pop[0], l_ic);
  // -> Done automatically by notify_nondominated
    
// check for new undominated elements
    l_swp = l_pop[0];
    this.notify_nondominated(l_swp);
    for(l_i = 1; l_i < l_ps; l_i++)
      {
      l_z = l_swp;
      l_swp = l_pop[l_i];
      if(l_ic.compare(l_z, l_swp) < 0) break;
      this.notify_nondominated(l_swp);
      }
    
//    l_z  = l_pop[0];
//    for(l_i = (l_ps-1); l_i > 0; l_i--)
//      {
//      l_swp = l_pop[l_i];
//      if(l_ic.compare(l_swp, l_z) < 0) l_z = l_swp;
//      }
//    l_gsb.check_best(l_z, l_ic);
    


// apply additional insertion.
    this.m_unsorted = this.insert_additional(l_pop, l_ps, l_ic);
    
    
//moved to the enqueue tasks method
//// sort using the serting algorithm.
//    ((GeneticParameters<?>)(l_gp)).get_selection_algorithm()
//                                  .get_sorting_algorithm()
//                                  .sort(l_pop, l_ps, l_ic, l_x);
//    
////removed since we now sort in an other way.
////    if(this.insert_additional(l_pop, l_ps, l_ic))
////      {
////      Arrays.sort(l_pop, l_ps, l_ic);
////      }
//
////apply diversity
//    for(l_nc = l_gs.get_diversity_swaps(); l_nc > 0; l_nc--)
//      {
//      l_mc        = l_r.nextInt(l_ps);
//      l_cc        = l_r.nextInt(l_ps);
//      l_swp       = l_pop[l_mc];
//      l_pop[l_mc] = l_pop[l_cc];
//      l_pop[l_cc] = l_swp;
//      }
    }


/**
 * Enqueue the tasks into the task queue.
 */

  private final void  enqueue_tasks ()
    {
    final GeneticState<Genotype>        l_gs;
    final Individual<Genotype>[]        l_pop;
          SearchNew<Genotype>[]         l_sn;
          SearchMutate<Genotype>[]      l_sm;
          SearchCrossover<Genotype>[]   l_sc;
    final int                           l_ps, l_nc, l_mc, l_cc, l_fc;
          int                           l_l, l_mx, l_cx;
    final SelectionAlgorithm            l_sa;
    final GeneticParameters<Genotype>   l_gp;
    final SearchTaskQueue<Genotype>     l_tq;
    final Randomizer                    l_r;
          SearchCrossover<Genotype>     l_sct;
          Individual<Genotype>          l_swp;
    final NonDominatedList<Genotype>    l_ndl;
    final double                        l_elp;

    l_gs  = Typesafe.cast(this.get_state());
    l_ps  = l_gs.get_population_size();
    l_fc  = l_gs.get_fitness_function_count();
    l_gp  = Typesafe.cast(this.get_parameters());
    l_sa  = l_gp.get_selection_algorithm();
    l_tq  = this.m_tasks;
    l_r   = this.get_randomizer();
    l_pop = this.m_population;    
    l_ndl = this.get_rel_non_dominated();
    l_elp = (l_ndl.isEmpty() ? -1E5 : l_gs.get_elitism_percentage());
    
// sort using the serting algorithm.
   l_sa.get_sorting_algorithm().sort(l_pop, l_ps, l_gp.get_comparator(),
                                     this.m_unsorted);
//apply diversity
    for(l_l = l_gs.get_diversity_swaps(); l_l > 0; l_l--)
      {
      l_mx        = l_r.nextInt(l_ps);
      l_cx        = l_r.nextInt(l_ps);
      l_swp       = l_pop[l_mx];
      l_pop[l_mx] = l_pop[l_cx];
      l_pop[l_cx] = l_swp;
      }

    if(l_gs.get_update_level() <= 0)
      {
      l_nc = l_ps;
      l_mc = 0;
      l_cc = 0;
      }
    else
      {
      l_mc = (int)(0.5d + (l_ps * l_gs.get_mutation_rate()));
      l_cc = (int)(0.5d + (l_ps * l_gs.get_crossover_rate()));
      l_nc = (l_ps - l_cc - l_mc);
      }

    this.m_mtc = l_mc;
    this.m_ctc = l_cc;
    this.m_ntc = l_nc;

// add the new tasks
    if(l_nc > 0)
      {
      l_sn = this.m_new;
      l_l  = l_sn.length;

      if(l_l < l_nc)
        {
        l_sn = Arrays.create(SearchNew.class, ((3*l_nc) >>> 1));
        System.arraycopy(this.m_new, 0, l_sn, 0, l_l);
        for(; l_l < l_nc; l_l++)
          {
          l_sn[l_l] = new SearchNew<Genotype>(l_fc);
          }
        this.m_new = l_sn;
        }
      else
        {
        if(l_l > (3*l_nc))
          {
          l_sn = Typesafe.cast(new SearchNew[l_nc]); 
          //Arrays.create(SearchNew.class, l_nc);
          System.arraycopy(this.m_new, 0, l_sn, 0, l_nc);
          this.m_new = l_sn;
          }
        }

      for(l_l = (l_nc-1); l_l >= 0; l_l--)
        {
        l_tq.add_task( l_sn[l_l] );
        }
      }

// add the mutation tasks
    if(l_mc > 0)
      {
      l_sm = this.m_mutate;
      l_l  = l_sm.length;

      if(l_l < l_mc)
        {
        l_sm = Arrays.create(SearchMutate.class, ((3*l_mc) >>> 1));
        System.arraycopy(this.m_mutate, 0, l_sm, 0, l_l);
        for(; l_l < l_nc; l_l++)
          {
          l_sm[l_l] = new SearchMutate<Genotype>(l_fc);
          }
        this.m_mutate = l_sm;
        }
      else
        {
        if(l_l > (3*l_mc))
          {
          l_sm = Typesafe.cast(new SearchMutate[l_mc]); 
          //Arrays.create(SearchMutate.class, l_mc);//l_sm);
          System.arraycopy(this.m_mutate, 0, l_sm, 0, l_mc);
          this.m_mutate = l_sm;
          }
        }

      for(l_l = (l_mc-1); l_l >= 0; l_l--)
        {
        l_sm[l_l].set_parent( (l_r.nextDouble() < l_elp) ? l_ndl.get(l_r) :
                               l_sa.select(l_r, l_pop, l_ps) );
        l_tq.add_task( l_sm[l_l] );
        }
      }

// add the crossover tasks
    if(l_cc > 0)
      {
      l_sc = this.m_crossover;
      l_l  = l_sc.length;

      if(l_l < l_cc)
        {
        l_sc = Arrays.create(SearchCrossover.class, ((3*l_cc) >>> 1));
        System.arraycopy(this.m_crossover, 0, l_sc, 0, l_l);
        for(; l_l < l_cc; l_l++)
          {
          l_sc[l_l] = new SearchCrossover<Genotype>(l_fc);
          }
        this.m_crossover = l_sc;
        }
      else
        {
        if(l_l > (3*l_cc))
          {
          l_sc = Typesafe.cast(new SearchCrossover[l_cc]); 
          //Arrays.create(SearchCrossover.class, l_cc);//l_sc);
          System.arraycopy(this.m_crossover, 0, l_sc, 0, l_cc);
          this.m_crossover = l_sc;
          }
        }

      for(l_l = (l_cc-1); l_l >= 0; l_l--)
        {
        l_sct = l_sc[l_l];
        l_sct.set_parent_1( (l_r.nextDouble() < l_elp) ? l_ndl.get(l_r) :
                               l_sa.select(l_r, l_pop, l_ps) );
        l_sct.set_parent_2( (l_r.nextDouble() < l_elp) ? l_ndl.get(l_r) :
                               l_sa.select(l_r, l_pop, l_ps) );
        l_tq.add_task( l_sct );
        }
      }

// select additional tasks for whatever
    if((l_mc > 0) || (l_cc > 0))
      {
      this.select_additional(l_pop, l_ps, l_sa, l_r, l_ndl, l_elp);
      }
    }

/**
 * <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  ()
    {
    //
    }

/**
 * 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;
    }


/**
 * 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
    {
    GeneticState<Genotype>  l_gs;
    int                     l_ps;
    Individual<Genotype>[]  l_i;

    super.do_write_snapshot(p_oos);

    l_gs = Typesafe.cast(this.get_state());
    l_ps = l_gs.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 GeneticState<Genotype>        l_gs;
    final int                           l_ps;
          int                           l_z;
    final Individual<Genotype>[]        l_i;

    super.do_read_snapshot(p_ois);

    l_gs = Typesafe.cast(this.get_state());
    l_ps = l_gs.get_population_size();
    l_i  = Arrays.create(Individual.class, l_ps);

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

    Arrays.sort(l_i, l_ps, 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 "Genetic Engine";
    }
  }

File Information:

file name:GeneticEngine.java
package:org.dgpf.search.algorithms.ga
qualified name:org.dgpf.search.algorithms.ga.GeneticEngine.java
file type:Java Source File
download location:download http://dgpf.sourceforge.net/source/org/dgpf/search/algorithms/ga/GeneticEngine.java
size:21.335 KB (21848 B)
uploaded: 2015-07-22 04:10:59 GMT+0000
last update: 2006-08-16 06:38:02 GMT+0000
last access: 2017-11-22 09:26:52 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-22 09:26:52 GMT+0000.
Valid CSS Valid XHTML 1.1
Valid RSS SourceForge.net Logo