Logo
Distributed Genetic Programming Framework
print print

File org.dgpf.search.api.NonDominatedList.java

Here you can find all the information about the file org.dgpf.search.api.NonDominatedList.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-05-29 05:32:07
 * Original Filename: org.dgpf.search.api.NonDominatedList.java
 * Version          : 1.0.3
 * Last modification: 2006-06-06
 *                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.api;

import java.io.IOException;
import java.io.InputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.OutputStream;
import java.io.Serializable;
import java.util.Random;

import org.dgpf.search.api.comparators.DominationComparator;
import org.dgpf.search.api.utils.RandomizedList;
import org.sfc.collections.Arrays;
import org.sfc.io.IO;
import org.sfc.io.TextWriter;
import org.sfc.meta.MetaInformationWriter;
import org.sfc.utils.Typesafe;

/**
 * This class represents a buffer that's able to hold individuals which
 * are not dominated by any other one.
 * @param <Genotype> The genotype of the individuals to be stored.
 * @author Thomas Weise
 */

public final  class       NonDominatedList<Genotype extends Serializable>
              extends     RandomizedList<Individual<Genotype>>
              implements  Serializable
  {
/**
 * The serial version uid.
 */

  private static final long serialVersionUID = 1;
/**
 * The internal buffer.
 */

  private transient Individual<Genotype>[]  m_buffer  ;
/**
 * The internal buffer size.
 */

  private transient int                     m_count   ;
/**
 * The individual comparator to be used to determine if an individual is
 * dominating another one or not.
 */

  private           IndividualComparator    m_comparator  ;
/**
 * The fitness function count.
 */

  private final     int                     m_fc;
  
/**
 * Create a new domination based buffer.
 * @param p_count         The size of the buffer.
 * @param p_fitness_count The fitness function found.
 * @param p_comparator    The individual comparator to be used to determine
 *                        if an individual is dominating another one or not.
 */

  public  NonDominatedList  (       int                   p_count,
                             final  int                   p_fitness_count,
                             final  IndividualComparator  p_comparator)
    {
    super();
    
    Individual<Genotype>[]  l_b;
    
    if(p_count <= 0) p_count = 128;    
    this.m_buffer = l_b = Typesafe.cast(new Individual[p_count]);
    
    for(--p_count; p_count >= 0; p_count--)
      {
      l_b[p_count] = new Individual<Genotype>(p_fitness_count);
      }
    
    this.m_comparator = ((p_comparator != null) ? p_comparator :
                        DominationComparator.INSTANCE);
    this.m_fc         = p_fitness_count;
    }
  
/**
 * Check in an individual into the domination buffer.
 * @param p_individual  The individual to be checked in.
 * @return  <code>true</code> if and only if the individual made it into
 *          the list
 */

  public synchronized  final boolean  check_in
                          (final Individual<Genotype> p_individual)
    {
    final Individual<Genotype>[]  l_b;
          Individual<Genotype>    l_id;
    final IndividualComparator    l_cp;
          int                     l_c, l_m, l_mi, l_i, l_j, l_fc;
          boolean                 l_bb;
          Genotype                l_g;
          double                  l_d;
          
    l_cp = this.m_comparator;
    if(l_cp.is_useless(p_individual)) return false;
    
    l_b  = this.m_buffer;
    l_c  = this.m_count;        
    l_bb = true;
    l_g  = p_individual.get_individual();
    
    for(l_i = (l_c-1); l_i >= 0; l_i--)
      {
      l_id = l_b[l_i];      
      l_j  = l_cp.compare(p_individual, l_id);
      
      if(l_j < 0)
        {
        l_c--;
        if(l_i < l_c) l_id.assign(l_b[l_c]);        
        l_b[l_c].clear();
        }
      else
        {
        if(l_j > 0) l_bb = false;
        else if(l_bb && l_id.get_individual().equals(l_g)) l_bb = false;
        }
      }
    
    if(l_bb)
      {
      if(l_c < l_b.length)
        {
        l_b[l_c].assign(p_individual);        
        this.m_count = (l_c+1);
        return true;
        }
      
      l_mi = -1;
      l_m  = Integer.MIN_VALUE;
      l_fc = (this.m_fc-1);
      
      for(l_i = (l_c-1); l_i >= 0; l_i--)
        {
        l_id = l_b[l_i];
        
        l_c  = 0;          
        for(l_j = l_fc; l_j >= 0; l_j--)
          {
          l_d = (p_individual.get_fitness(l_j)-l_id.get_fitness(l_j));
               if(l_d < 0.0d) l_c--;
          else if(l_d > 0.0d) l_c++;
          }
        
        if(l_c > l_m)
          {
          l_mi = l_i;
          l_m  = l_c;
          if(l_m >= l_fc) break;
          }
        }
//if we dominate an individual in more than half of the fitness functions
      if(l_m > ((l_fc+1)>>>1))
        {
        l_b[l_mi].assign(p_individual);
        return true;
        }      
      }
    else this.m_count = l_c;
    
    return false;
    }
  
/**
 * Store the non-dominated elements stored in this buffer in an object
 * output stream.
 * @param p_oos   The destination output stream.
 * @throws  IOException Thrown if io fails. 
 */

  public synchronized final void write_objects(final ObjectOutputStream p_oos)
      throws IOException
    {
    int                     l_c;
    Individual<Genotype>[]  l_b;
    
    l_c = this.m_count;
    l_b = this.m_buffer;
    
    p_oos.writeInt(l_c);
    for(--l_c; l_c >= 0; l_c--)
      {
      p_oos.writeUnshared(l_b[l_c]);
      }
    }
  
/**
 * Store the non-dominated elements stored in this buffer in a arbitrary
 * destination.
 * @param p_dest   The destination to write to.
 * @throws  IOException Thrown if io fails. 
 */

  public  final void  write_objects (final Object p_dest)
                      throws IOException
    {
    OutputStream        l_os;
    ObjectOutputStream  l_oos;
    
    l_os = IO.get_output_stream(p_dest);
    if(l_os == null) throw new IOException();
    
    try
      {
      l_oos = new ObjectOutputStream(l_os);
      try
        {
        this.write_objects(l_oos);
        }
      finally
        {
        l_oos.close();
        }
      }
    finally
      {
      l_os.close();
      }
    }
  
/**
 * Read non-dominated elements and store them in this buffer.
 * @param p_ois   The source input stream.
 * @throws  IOException             Thrown if io fails. 
 * @throws  ClassNotFoundException  If some vital class is missing.
 */

  public synchronized final void read_objects(final ObjectInputStream p_ois)
      throws IOException, ClassNotFoundException
    {
    int                     l_c, l_i;
    Individual<Genotype>[]  l_b;
    Individual<Genotype>    l_x;
    
    l_c = p_ois.readInt();
    
    if(this.m_buffer == null)
      {
      this.m_buffer = l_b = Typesafe.cast(
                                new Individual[(l_c <= 0) ? 128 : l_c]);
      for(l_i = (l_c-1); l_i >= 0; l_i--)
        {
        l_b[l_i] = new Individual<Genotype>(this.m_fc);
        }
      }
    else l_b = this.m_buffer;
    
    for(; l_c > 0; l_c--)
      {
      l_x = Typesafe.cast(p_ois.readUnshared());
      this.check_in(l_x);
      }
    }
  
  
/**
 * Read non-dominated elements and store them in this buffer.
 * @param p_source  The source to read from.
 * @throws  IOException             Thrown if io fails. 
 * @throws  ClassNotFoundException  If some vital class is missing.
 */

  public  final void  read_objects (final Object p_source)
      throws IOException, ClassNotFoundException
    {
    InputStream       l_is;
    ObjectInputStream l_ois;
    
    l_is = IO.get_input_stream(p_source);
    if(l_is == null) throw new IOException();
    
    try
      {
      l_ois = new ObjectInputStream(l_is);
      try
        {
        this.read_objects(l_ois);
        }
      finally
        {
        l_ois.close();
        }
      }
    finally
      {
      l_is.close();
      }
    }
  
/**
 * Stores the buffer into the stream.
 * @param p_s The output stream.
 * @throws  IOException If something io-like went wrong.
 */

  private final void writeObject(final ObjectOutputStream p_s)
        throws IOException
    {
    p_s.defaultWriteObject();
    this.write_objects(p_s);
    }



/**
 * Reconstitute the buffer instance from a stream (that is,
 * deserialize it).
 * @param p_s The input stream.
 * @throws  IOException If something io-like went wrong.
 * @throws  ClassNotFoundException  If a needed class could not be found.
 */

  private final void readObject(final ObjectInputStream p_s)
        throws IOException, ClassNotFoundException
    {
    p_s.defaultReadObject();
    this.read_objects(p_s);
    }
  
/**
 * Print the contents of this buffer in human-readable form to a text
 * writer.
 * @param p_tw  The text writer to print to. 
 */

  @Override
  public  synchronized  final void  print (final TextWriter p_tw)
    {
    int                     l_c;
    Individual<Genotype>[]  l_b;
    
    l_c = this.m_count;
    p_tw.write("Non-dominated list includes ");
    p_tw.write_int(l_c);
    p_tw.write(" non-dominated individuals.");
    p_tw.write_linebreak();
    
    p_tw.write("Using the ");
    p_tw.write_object(this.m_comparator);
    p_tw.write("-comparator.");
    
    if(l_c > 0)
      {   
      l_b = this.m_buffer;
      
      for(--l_c; l_c >= 0; l_c--)
        {
        MetaInformationWriter.print_default(l_b[l_c], p_tw);
        }
      }
    
    p_tw.flush();
    }
  
  
  
/**
 * Returns the number of elements in this list.  If this list contains
 * more than <tt>Integer.MAX_VALUE</tt> elements, returns
 * <tt>Integer.MAX_VALUE</tt>.
 *
 * @return the number of elements in this list.
 */

  @Override
  public  final int size()
    {
    return this.m_count;
    }

/**
 * Returns <tt>true</tt> if this list contains no elements.
 *
 * @return <tt>true</tt> if this list contains no elements.
 */

  @Override
  public  final boolean isEmpty()
    {
    return (this.m_count <= 0);
    }

/** 
 * Returns <tt>true</tt> if this list contains the specified element.
 * More formally, returns <tt>true</tt> if and only if this list contains
 * at least one element <tt>e</tt> such that
 * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
 *
 * @param p_o element whose presence in this list is to be tested.
 * @return <tt>true</tt> if this list contains the specified element.
 * @throws ClassCastException if the type of the specified element
 *         is incompatible with this list (optional).
 * @throws NullPointerException if the specified element is null and this
 *         list does not support null elements (optional).
 */

  @Override
  public  final boolean contains(final  Object p_o)
    {
    Individual<Genotype>[] l_b;
    int                    l_i;
    
    if(p_o == null) return false;
    
    l_b = this.m_buffer;
    for(l_i = (this.m_count-1); l_i >= 0; l_i--)
      {
      if(l_b[l_i].get_individual().equals(p_o)) return true;
      }
    
    return false;
    }


/**
 * Returns an array containing all of the elements in this list in proper
 * sequence.  Obeys the general contract of the
 * <tt>Collection.toArray</tt> method.
 *
 * @return an array containing all of the elements in this list in proper
 *         sequence.
 */

  @Override
  public  final Object[] toArray()
    {
    Object[]  l_o;
    int       l_c;
    
    l_c = this.m_count;
    l_o = new Object[l_c];
    System.arraycopy(this.m_buffer, 0, l_o, 0, l_c);
    
    return l_o;
    }

/**
 * Returns an array containing all of the elements in this list in proper
 * sequence; the runtime type of the returned array is that of the
 * specified array.  Obeys the general contract of the
 * <tt>Collection.toArray(Object[])</tt> method.
 *
 * @param p_a the array into which the elements of this list are to
 *    be stored, if it is big enough; otherwise, a new array of the
 *    same runtime type is allocated for this purpose.
 * @param <T> The array item type.
 * @return  an array containing the elements of this list.
 * 
 * @throws ArrayStoreException if the runtime type of the specified array
 *      is not a supertype of the runtime type of every element in
 *      this list.
 * @throws NullPointerException if the specified array is <tt>null</tt>.
 */

  @Override
  public  final <T> T[] toArray(T[] p_a)
    {
    int l_c;
    
    l_c = this.m_count;
    
    if(p_a.length < l_c)
      {
      p_a = Typesafe.cast(
            Arrays.create(p_a.getClass().getComponentType(), l_c));
      }
    
    System.arraycopy(this.m_buffer, 0, p_a, 0, l_c);
    return p_a;
    }


    


    // Positional Access Operations

/**
 * Returns the element at the specified position in this list.
 *
 * @param p_index index of element to return.
 * @return the element at the specified position in this list.
 * 
 * @throws IndexOutOfBoundsException if the index is out of range (index
 *      &lt; 0 || index &gt;= size()).
 */

  @Override
  public  final Individual<Genotype>  get(final int p_index)
    {
    return this.m_buffer[p_index];
    }

/**
 * Obtain one random individual out of the non dominated list.
 * @param p_random  The random number generator to be used.
 * @return  The randomly selected individual.
 */

  @Override
  public final synchronized Individual<Genotype> get
                                          (final Random p_random)
    {
    return this.m_buffer[p_random.nextInt(this.m_count)];
    }
  

    // Search Operations

/**
 * Returns the index in this list of the first occurrence of the specified
 * element, or -1 if this list does not contain this element.
 * More formally, returns the lowest index <tt>i</tt> such that
 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
 * or -1 if there is no such index.
 *
 * @param p_o element to search for.
 * @return the index in this list of the first occurrence of the specified
 *         element, or -1 if this list does not contain this element.
 * @throws ClassCastException if the type of the specified element
 *         is incompatible with this list (optional).
 * @throws NullPointerException if the specified element is null and this
 *         list does not support null elements (optional).
 */

  @Override
  public  final int indexOf(final Object p_o)
    {    
    Individual<Genotype>[] l_b;
    int                    l_i, l_j;
    
    if(p_o == null) return -1;
    
    l_b = this.m_buffer;
    l_j = this.m_count;
    for(l_i = 0; l_i < l_j; l_i++)
      {
      if(l_b[l_i].get_individual().equals(p_o)) return l_i;
      }
    
    return -1;
    }

/**
 * Returns the index in this list of the last occurrence of the specified
 * element, or -1 if this list does not contain this element.
 * More formally, returns the highest index <tt>i</tt> such that
 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
 * or -1 if there is no such index.
 *
 * @param p_o element to search for.
 * @return the index in this list of the last occurrence of the specified
 *         element, or -1 if this list does not contain this element.
 * @throws ClassCastException if the type of the specified element
 *         is incompatible with this list (optional).
 * @throws NullPointerException if the specified element is null and this
 *         list does not support null elements (optional).
 */

  @Override
  public  final int lastIndexOf(final Object p_o)
    {    
    Individual<Genotype>[] l_b;
    int                    l_i;
    
    if(p_o == null) return -1;
    
    l_b = this.m_buffer;
    for(l_i = (this.m_count-1); l_i >= 0; l_i--)
      {
      if(l_b[l_i].get_individual().equals(p_o)) return l_i;
      }
    
    return -1;
    }

  
  
/**
 * Set the comparator to determine which elements dominate which others.
 * @param p_comparator  The comparator to be set.
 */

  synchronized final void set_comparator
                        (final IndividualComparator p_comparator)
    {
    Individual<Genotype>[]  l_b;
    Individual<Genotype>    l_id;
    int                     l_c, l_i, l_j, l_r;
                         
    if((p_comparator != null) && (!(p_comparator.equals(this.m_comparator))))
      {
      l_c = this.m_count;
      l_b = this.m_buffer;
     
      l_i = (l_c-1);

      while(l_i > 0)
        {
        l_id = l_b[l_i];
loop:
        for(l_j = (l_i-1); l_j >= 0; l_j--)
          {
          l_r = p_comparator.compare(l_id, l_b[l_j]);
          if(l_r > 0)
            {
            if(l_i < (--l_c)) l_b[l_i].assign(l_b[l_c]);
            l_b[l_c].clear();
            break loop;
            }
          else if(l_r < 0)
            {
            l_b[l_j].assign(l_b[--l_c]);
            l_b[l_c].clear();
            }
          }
        
        l_i = (((l_i < l_c) ? l_i : l_c) - 1);
        }
      
      this.m_comparator = p_comparator;
      this.m_count      = l_c;
      }
    }
  
/**
 * Obtain the comparator used to compare the individual's fitnesses.
 * @return The comparator used to compare the individual's fitnesses.
 */

  public  final IndividualComparator  get_comparator()
    {
    return this.m_comparator;
    }
  
/**
 * Clear the list.
 */

  final void  flush()
    {
    int                     l_i;
    Individual<Genotype>[]  l_f;
    
    l_f = this.m_buffer;
    for(l_i = (this.m_count-1); l_i >= 0; l_i--)
      {
      l_f[l_i].clear();
      }
    
    this.m_count = 0;
    }
  
/**
 * Creates and returns a copy of this object.  The precise meaning
 * of "copy" may depend on the class of the object.
 *
 * @return     A clone of this instance.
 *
 * @see java.lang.Cloneable
 */

  @Override
  public  Object  clone ()
    {
    NonDominatedList<Genotype> l_n;
    
    l_n              = Typesafe.cast(super.clone());
    l_n.m_buffer     = l_n.m_buffer.clone();
    
    return l_n;
    }
  }

File Information:

file name:NonDominatedList.java
package:org.dgpf.search.api
qualified name:org.dgpf.search.api.NonDominatedList.java
file type:Java Source File
download location:download http://dgpf.sourceforge.net/source/org/dgpf/search/api/NonDominatedList.java
size:18.832 KB (19284 B)
uploaded: 2015-07-22 04:11:00 GMT+0000
last update: 2006-08-25 11:51:14 GMT+0000
last access: 2017-11-24 00:22:28 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-24 00:22:28 GMT+0000.
Valid CSS Valid XHTML 1.1
Valid RSS SourceForge.net Logo