freEvolutionaryStrategyOptimizer.txx

Go to the documentation of this file.

/*=========================================================================

  Program:   F.R.E.E. - flexible registration evaluation engine
  Version:   v.1.0.0
  Date:      $Date: 2006/09/01 12:00:00 $
  Module:    $RCSfile: freEvolutionaryStrategyOptimizer.txx,v $
  Language:  C++



  Copyright (c) 2007 Ralf o Floca (Department of Medical Informatics,
  Institute for Medical Biometry and Informatics, University of Heidelberg,
  Germany). All rights reserved.
  See FREECopyright.txt or http://www.mi.med.uni-hd.de/free/copyright.htm
  for details.

     This software is distributed WITHOUT ANY WARRANTY; without even 
     the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR 
     PURPOSE.  See the above copyright notices for more information.

=========================================================================*/
#ifndef _freEvolutionaryStrategyOptimizer_txx
#define _freEvolutionaryStrategyOptimizer_txx

#include "freEvolutionaryStrategyOptimizer.h"

namespace FREE
{
  namespace ES
  {

    template <class TIndividual>
    EvolutionaryStrategyOptimizer<TIndividual>
      ::EvolutionaryStrategyOptimizer()
    {
      m_ParentSelector = 0;
      m_Recombinator = 0;
      m_Mutation = 0;
      m_Selection = 0;
      m_NumberOfParents = 1;
      m_NumberOfChildren = 1;
      m_PopulationIsInitialized = false;
      m_MutateIntitialPopulation = false;
      m_CurrentChild = 0;
      m_SelectionVictims = 0;
      m_NewChildren = 0;
      this->MaximizeOn();
    }

    template <class TIndividual>
    EvolutionaryStrategyOptimizer<TIndividual>
      ::~EvolutionaryStrategyOptimizer() 
    {
    }

    template <class TIndividual>
    void
      EvolutionaryStrategyOptimizer<TIndividual>::
      SetParentSelector( ParentSelectorType * pParentSelector )
    {
      if ( m_ParentSelector != pParentSelector )
      {
        m_ParentSelector = pParentSelector ;
        this->Modified() ;
      }
    };

    template <class TIndividual>
    void
      EvolutionaryStrategyOptimizer<TIndividual>::
      SetRecombinator( RecombinatorType * pRecombinator )
    {
      if ( m_Recombinator != pRecombinator )
      {
        m_Recombinator = pRecombinator ;
        this->Modified() ;
      }
    };

    template <class TIndividual>
    void
      EvolutionaryStrategyOptimizer<TIndividual>::
      SetMutation( MutationType * pMutation )
    {
      if ( m_Mutation != pMutation )
      {
        m_Mutation = pMutation ;
        this->Modified() ;
      }
    };

    template <class TIndividual>
    void
      EvolutionaryStrategyOptimizer<TIndividual>::
      SetSelection( SelectionType * pSelection )
    {
      if ( m_Selection != pSelection )
      {
        m_Selection = pSelection ;
        this->Modified() ;
      }
    };

    template <class TIndividual>
    void
      EvolutionaryStrategyOptimizer<TIndividual>::
      PrintSelf(std::ostream& os, itk::Indent indent) const
    {

      Superclass::PrintSelf(os,indent);

      os << indent << "Number of parents " << m_NumberOfParents << std::endl;
      os << indent << "Numver of children " << m_NumberOfChildren << std::endl;

      os << indent << "Parent selector:  ";
      if (m_ParentSelector.IsNotNull())
      {
        os << std::endl;
        m_ParentSelector->Print(os, indent.GetNextIndent());
        os << std::endl;
      }
      else
      {
        os << indent << " none " << std::endl;
      }

      os << indent << "Recombinator:  ";
      if (m_Recombinator.IsNotNull())
      {
        os << std::endl;
        m_Recombinator->Print(os, indent.GetNextIndent());
        os << std::endl;
      }
      else
      {
        os << indent << " none " << std::endl;
      }

      os << indent << "Mutation:  ";
      if (m_Mutation.IsNotNull())
      {
        os << std::endl;
        m_Mutation->Print(os, indent.GetNextIndent());
        os << std::endl;
      }
      else
      {
        os << indent << " none " << std::endl;
      }

      os << indent << "Selection:  ";
      if (m_Selection.IsNotNull())
      {
        os << std::endl;
        m_Selection->Print(os, indent.GetNextIndent());
        os << std::endl;
      }
      else
      {
        os << indent << " none " << std::endl;
      }
    }

    template <class TIndividual>
    void
      EvolutionaryStrategyOptimizer<TIndividual>::
      Initialize(const PopulationType& population)
    {
      if (population.Size() != m_NumberOfParents) throwExceptionMacro("Error. Passed population has wrong size. NumberOfParents: "<<m_NumberOfParents<<"; population size: "<<population.Size());
      if ( m_ParentSelector.IsNull() ) throwExceptionMacro("Error: Parent selector is undefined (reference is NULL).");
      if ( m_Recombinator.IsNull() ) throwExceptionMacro("Error: Recombinator is undefined (reference is NULL).");
      if ( m_Mutation.IsNull() ) throwExceptionMacro("Error: Mutation is undefined (reference is NULL).");
      if ( m_Selection.IsNull() ) throwExceptionMacro("Error: Selection is undefined (reference is NULL).");

      if (m_Population.GetPointer()!=&population) m_Population = population.Clone();

      m_CurrentChild = 0;
      m_SelectionVictims = 0;
      m_NewChildren = 0;

      for (typename PopulationType::iterator pos = m_Population->begin(); pos!=m_Population->end(); ++pos)
      {
        (*pos)->ResetStrategicParameters();

        m_ParentSelector->RegisterStrategicIndividualParameters(*(*pos));
        m_Recombinator->RegisterStrategicIndividualParameters(*(*pos));
        m_Mutation->RegisterStrategicIndividualParameters(*(*pos));
        m_Selection->RegisterStrategicIndividualParameters(*(*pos));
      };

      m_ParentSelector->RegisterStrategicPopulationParameters(*(m_Population.GetPointer()));
      m_Recombinator->RegisterStrategicPopulationParameters(*(m_Population.GetPointer()));
      m_Mutation->RegisterStrategicPopulationParameters(*(m_Population.GetPointer()));
      m_Selection->RegisterStrategicPopulationParameters(*(m_Population.GetPointer()));

      m_PopulationIsInitialized = true;
    };

    template <class TIndividual>
    void
      EvolutionaryStrategyOptimizer<TIndividual>::
      Initialize()
    {
      if (!m_PopulationIsInitialized)
      {
        //generate template individual
        IndividualPointer templateIndividual = IndividualType::New();
        m_Population = PopulationType::New();
        m_Population->Reserve(m_NumberOfParents);

        for (unsigned long index = 0; index<this->GetInitialPosition().Size(); index++)
        {
          templateIndividual->ObjectiveParameters().push_back(this->GetInitialPosition()[index]);
        }

        for (unsigned long count = 0; count<m_NumberOfParents; count++)
        {
          IndividualPointer individual = templateIndividual->Clone();
          individual->SetIndividualID(m_Population->GenerateUniqueIndividualID());
          individual->SetGenerationID(m_Population->GetGenerationID());

          m_Population->InsertElement(count, individual);
        }

        Initialize(*(m_Population.GetPointer()));

        if (m_MutateIntitialPopulation)
        {
          for (unsigned long index = 0; index<m_NumberOfParents; index++)
          {
            m_Mutation->Mutate(m_Population->GetElement(index).GetPointer(),m_Population.GetPointer());
          }
        }
      }
    };

    template <class TIndividual>
    void
      EvolutionaryStrategyOptimizer<TIndividual>::
      StartOptimization()
    {
      if ( m_CostFunction.IsNull() )
      {
        return ;
      }

      if ( m_ParentSelector.IsNull() ) throwExceptionMacro("Error: Parent selector is undefined (reference is NULL).");
      if ( m_Recombinator.IsNull() ) throwExceptionMacro("Error: Recombinator is undefined (reference is NULL).");
      if ( m_Mutation.IsNull() ) throwExceptionMacro("Error: Mutation is undefined (reference is NULL).");
      if ( m_Selection.IsNull() ) throwExceptionMacro("Error: Selection is undefined (reference is NULL).");

      m_Stop = false ;

      unsigned int spaceDimension = m_CostFunction->GetNumberOfParameters();
      const Optimizer::ScalesType& scales = this->GetScales() ;

      // Make sure the scales have been set properly
      if (scales.size() != spaceDimension)
      {
        itkExceptionMacro(<< "The size of Scales is "
          << scales.size()
          << ", but the NumberOfParameters for the CostFunction is "
          << spaceDimension
          << ".");
      }

      m_Mutation->SetGeneralObjectiveScales(scales);
      m_Selection->SetMaximumIsBest(this->GetMaximize());

      this->Initialize();

      this->InvokeEvent( itk::StartEvent() );

      //Evaluate the first generation of parents.
      this->EvaluatePopulation(m_Population);

      this->SetBestIndividual(m_Population);

      this->SetCurrentPosition( this->ConvertIndividualToParameter(this->GetBestIndividual()));

      this->InvokeEvent( itk::IterationEvent() );   

      //begin with evolution
      m_CurrentIteration = 0 ;

      m_Started = true;

      if (!m_Stop)
      {
        ResumeOptimization();
      }
      else
      {
        this->InvokeEvent( itk::EndEvent() );
      }
    };

    template <class TIndividual>
    void
      EvolutionaryStrategyOptimizer<TIndividual>::
      ResumeOptimization()
    {
      Superclass::ResumeOptimization();

      //resume evolution
      for (; m_CurrentIteration < GetMaximumIteration() ; m_CurrentIteration++) 
      {
        if ( m_Stop )
        {
          break ;
        }

        //start new population cycle
        m_SelectionVictims = 0;
        m_ParentSelections.clear();

        m_NewChildren = PopulationType::New();
        m_NewChildren->SetGenerationID(m_Population->GetGenerationID()+1);
        m_NewChildren->Reserve(m_NumberOfChildren);

        //mutate strategic population parameters
        m_ParentSelector->MutateStrategicPopulationParameters(*(m_Population.GetPointer()));
        m_Recombinator->MutateStrategicPopulationParameters(*(m_Population.GetPointer()));
        m_Mutation->MutateStrategicPopulationParameters(*(m_Population.GetPointer()));
        m_Selection->MutateStrategicPopulationParameters(*(m_Population.GetPointer()));

        //generate new children
        for (unsigned long count = 0; count < m_NumberOfChildren; count++)
        {
          //select the parents from the generation
          typename ParentSelectorType::ParentSelectionType parents = m_ParentSelector->Select(*(m_Population.GetPointer()));

          //recombine parents to new child.
          m_CurrentChild = m_Recombinator->Recombine(parents);

          m_CurrentChild->SetGenerationID(m_Population->GetGenerationID()+1);
          m_CurrentChild->SetIndividualID(m_Population->GenerateUniqueIndividualID());

          //mutate the child
            //mutate strategic parameters
          m_ParentSelector->MutateStrategicIndividualParameters(*(m_CurrentChild.GetPointer()), *(m_Population.GetPointer()));
          m_Recombinator->MutateStrategicIndividualParameters(*(m_CurrentChild.GetPointer()), *(m_Population.GetPointer()));
          m_Mutation->MutateStrategicIndividualParameters(*(m_CurrentChild.GetPointer()), *(m_Population.GetPointer()));
          m_Selection->MutateStrategicIndividualParameters(*(m_CurrentChild.GetPointer()), *(m_Population.GetPointer()));
            //mutate objective parameters
          m_Mutation->Mutate(m_CurrentChild.GetPointer(),m_Population.GetPointer());

          this->InvokeEvent(NewChildGenerationEvent());

          //evaluate the child
          this->EvaluateIndividual(m_CurrentChild.GetPointer());

          this->InvokeEvent(NewChildEvaluationEvent());

          m_NewChildren->InsertElement(count, m_CurrentChild);

          //generate parent selection vector and heritage map for protocol etc.
          IndividualSelectionType selectedIDs;
          for (typename ParentSelectorType::ParentSelectionType::const_iterator pos = parents.begin(); pos!= parents.end(); ++pos)
          {
            selectedIDs.push_back((*pos)->GetIndividualID());
          }

          typedef std::pair<IndividualIDType,IndividualSelectionType> HeritageMapPairType;
          m_ParentSelections.insert(HeritageMapPairType(m_CurrentChild->GetIndividualID(),selectedIDs));
          
          m_CurrentChild = 0;
        }

        //Add children to population
        for (unsigned long index = 0; index < m_NewChildren->Size(); index++)
        {
          m_Population->InsertElement(m_Population->Size(), m_NewChildren->GetElement(index));
        }

        //Select the population for the next generation
        m_SelectionVictims = m_Selection->Select(m_Population, m_NumberOfParents);

        //increase population generation
        m_Population->SetGenerationID(m_Population->GetGenerationID()+1);

        //check for best individual
        this->SetBestIndividual(m_Population);

        this->SetCurrentPosition(this->ConvertIndividualToParameter(this->GetBestIndividual()));
        m_CurrentCost = this->GetBestIndividual()->GetObjectiveValue();
        
        this->InvokeEvent( itk::IterationEvent() );   
        itkDebugMacro(<< "Current position: " << this->GetCurrentPosition()) ;

        if (!m_Stop)
        {
          if (this->GetMaximize())
          {
            m_Stop = m_CurrentCost>=m_Threshold;
          }
          else
          {
            m_Stop = m_CurrentCost<=m_Threshold;
          }
        }
      }
      m_Started = false;
      this->InvokeEvent( itk::EndEvent() );
    };

    template <class TIndividual>
    void
      EvolutionaryStrategyOptimizer<TIndividual>::
      EvaluatePopulation(PopulationType* pPopulation) const
    {
      for (typename PopulationType::iterator pos = pPopulation->begin(); pos!=pPopulation->end(); ++pos)
      {
        if (!((*pos)->GetObjectiveValueIsSet()))
        { //Calculate objective value
          EvaluateIndividual(*pos);
        }
      }
    };

    template <class TIndividual>
    void
      EvolutionaryStrategyOptimizer<TIndividual>::
      EvaluateIndividual(IndividualType* pIndividual) const
    {
      typedef typename IndividualType::ObjectiveValueType IndividualObjectiveValueType;

      if (pIndividual)
      { //Calculate objective value
        try
        {
          CostFunctionParametersType param = ConvertIndividualToParameter(pIndividual);
          IndividualObjectiveValueType value = (IndividualObjectiveValueType) this->GetCostFunction()->GetValue( param );
          pIndividual->SetObjectiveValue(value);
        }
        catch(...)
        { //error while try to evaluate child (e.g. metric cannot evaluate
          //because all points mapped outside the image region).
          //thus set the objective value to the worsest value possible.
          this->InvokeEvent(InvalidChildEvaluationEvent());
          if (this->GetMaximize())
          {
            pIndividual->SetObjectiveValue(itk::NumericTraits< IndividualObjectiveValueType >::NonpositiveMin());
          }
          else
          {
            pIndividual->SetObjectiveValue(itk::NumericTraits< IndividualObjectiveValueType >::max());
          }
        }
      }
    };

    template <class TIndividual>
    typename EvolutionaryStrategyOptimizer<TIndividual>::IndividualPointer
      EvolutionaryStrategyOptimizer<TIndividual>::
      FindBestIndividual(PopulationType* pPopulation) 
    {
      typename IndividualType::ObjectiveValueType bestValue;
      IndividualPointer bestIndividual;
      typename PopulationType::iterator pos = pPopulation->begin();

      if (pos!=pPopulation->end())
      {
        bestIndividual = *pos;
        bestValue = (*pos)->GetObjectiveValue();

        for (++pos; pos!=pPopulation->end(); ++pos)
        {
          typename IndividualType::ObjectiveValueType value = (*pos)->GetObjectiveValue();

          if ((this->GetMaximize() && (value>bestValue)) ||
            (this->GetMinimize() && (value<bestValue)))
          {
            bestIndividual = *pos;
            bestValue = (*pos)->GetObjectiveValue();
          }
        }
      }
      return bestIndividual;
    };

    template <class TIndividual>
    void
      EvolutionaryStrategyOptimizer<TIndividual>::
      SetBestIndividual(PopulationType* pPopulation)
    {
      IndividualPointer bestGenerationIndividual = FindBestIndividual(pPopulation);

      pPopulation->SetBestIndividual(bestGenerationIndividual);

      if (!pPopulation->GetBestIndividualEver())
      {
        pPopulation->SetBestIndividualEver(bestGenerationIndividual);
      }
      else
      {
        if ((this->GetMaximize() && (bestGenerationIndividual->GetObjectiveValue()>pPopulation->GetBestIndividualEver()->GetObjectiveValue())) ||
          (this->GetMinimize() && (bestGenerationIndividual->GetObjectiveValue()<pPopulation->GetBestIndividualEver()->GetObjectiveValue())))
        {
          pPopulation->SetBestIndividualEver(bestGenerationIndividual);
        }
      }
    };

    template <class TIndividual>
    typename EvolutionaryStrategyOptimizer<TIndividual>::CostFunctionParametersType
      EvolutionaryStrategyOptimizer<TIndividual>::
      ConvertIndividualToParameter(const IndividualType* pIndividual) const
    {
      if (!pIndividual) throwExceptionMacro("Error. Passed individual is NULL.");

      CostFunctionParametersType params(pIndividual->ObjectiveParameters().size());

      for (unsigned int index=0; index<params.Size(); index++)
      {
        params.SetElement(index,pIndividual->ObjectiveParameters()[index]);
      }

      return params;
    };

    template <class TIndividual>
    const typename EvolutionaryStrategyOptimizer<TIndividual>::HeritageMapType&
      EvolutionaryStrategyOptimizer<TIndividual>::
      GetRecentParentSelections() const
    {
      return m_ParentSelections;
    };

    template <class TIndividual>
    const typename EvolutionaryStrategyOptimizer<TIndividual>::PopulationPointer&
      EvolutionaryStrategyOptimizer<TIndividual>::
      GetRecentPopulationSelections() const
    {
      return m_SelectionVictims;
    };

    template <class TIndividual>
    const typename EvolutionaryStrategyOptimizer<TIndividual>::PopulationPointer&
      EvolutionaryStrategyOptimizer<TIndividual>::
      GetNewChildren() const
    {
      return m_NewChildren;
    };

    template <class TIndividual>
    const typename EvolutionaryStrategyOptimizer<TIndividual>::IndividualType*
      EvolutionaryStrategyOptimizer<TIndividual>::
      GetBestIndividualEver() const
    {
      if (m_Population.IsNotNull())
      {
        return m_Population->GetBestIndividualEver();
      }
      return 0;
    };

    template <class TIndividual>
    const typename EvolutionaryStrategyOptimizer<TIndividual>::IndividualType*
      EvolutionaryStrategyOptimizer<TIndividual>::
      GetBestIndividual() const
    {
      if (m_Population.IsNotNull())
      {
        return m_Population->GetBestIndividual();
      }
      return 0;
    };

  } // end of namespace ES
} // end of namespace free
#endif

---