EGTCrossover.h

Go to the documentation of this file.

/****************************************************************************

$Id: EGTCrossover.h,v 1.1.1.1 2002/10/19 08:14:51 motegi Exp $
Copyright (C) 2002 Higuchi Lab. All rights reserved.

*****************************************************************************/
#ifndef INCLUDE__CROSSOVER_H__FILE
#define INCLUDE__CROSSOVER_H__FILE

#include "defs.h"
#include "env.h"
#include "EGException.h"
#include "EGRandom.h"
#include "EGTVector.h"

template<class TP>
class EGTCrossover {
public:
  typedef TP                       Pop;
  typedef typename Pop::Graph      Graph;
  typedef EGTVector<const Graph*>  Graphs;
  typedef typename Graph::SubGraph SubGraph;

  virtual ~EGTCrossover() { }
  virtual UInt Crossover(const Graphs& src, Pop& dest);

protected:
  virtual bool DoCrossover(const Graph& graph1, const Graph& graph2, Pop& dest);
};

//============================================================================
template<class TP>
UInt EGTCrossover<TP>::Crossover(const Graphs& src, Pop& dest)
{
  Float fCrossoverRate = Env::Instance().CrossoverRate();
  UInt uPopSize = Env::Instance().PopSize();

  if (fCrossoverRate > 1.0) {
    fCrossoverRate = 1.0;
  }
  UInt uMax = src.Size();
  if (uMax < 2) {
    throw EGException("EGTCrossover::Crossover()"
                      "Can't perform the crossover operation: "
                      "the number of individuals is less than 2.",
                      __FILE__, __LINE__);
  }

  // Number of crossover operations
  UInt uCrossoverCount = (UInt)(uPopSize * fCrossoverRate) / 2;

  UInt uSel = (UInt)(uMax * EGRandom::NextReal());
  const Graph *pg1;
  const Graph *pg2;

  UInt n = 0;
  for (UInt i=0; i<uCrossoverCount; ++i) {
    if (uSel == uMax) {
      pg1 = src[0];
      pg2 = src[1];
      uSel = 2;
    }
    else if (uSel+1 == uMax) {
      pg1 = src[uSel];
      pg2 = src[0];
      uSel = 1;
    }
    else {
      pg1 = src[uSel];
      pg2 = src[uSel+1];
      uSel += 2;
    }
    if (DoCrossover(*pg1, *pg2, dest) == true) {
      ++n;
    }
  }
  return n;
}

//============================================================================
template<class TP>
bool EGTCrossover<TP>::DoCrossover(const Graph& graph1, const Graph& graph2,
                                   Pop& dest) {
  UInt uSel1, uSel2, uSelIndex;
  const SubGraph* psg1a;
  const SubGraph* psg2a;
  SubGraph* psg1b;
  SubGraph* psg2b;

  UInt uGraph1NumSubGraphs = graph1.GetNumSubGraphs();
  if (uGraph1NumSubGraphs == 0) {
    return false;
  }
  EGTVector<UInt> tIndex(uGraph1NumSubGraphs);
  for (UInt i=0; i<uGraph1NumSubGraphs; ++i) {
    tIndex[i] = i;
  }

  UInt uMaxNodeSize = 2 * Env::Instance().MaxNodeSize();
  while (1) {
    if (tIndex.Size() == 0) {  // No compatible SubGraphs between two Graphs.
      return false;
    }
    // Selects a SubGraph randomly from Graph 1.
    uSelIndex = EGRandom::NextInt(0, tIndex.Size()-1);
    uSel1 = tIndex[uSelIndex];
    psg1a = graph1.GetSubGraph(uSel1);
    tIndex.Erase(tIndex.Begin() + uSelIndex);

    // Selects a compatible SubGraph with "psg1a" from Graph 2.
    psg2a = graph2.GetSubGraph(*psg1a, &uSel2);
    if (psg2a != 0) {
      UInt uMax1b = uMaxNodeSize - psg2a->GetNumNodes();
      UInt uMax2b = uMaxNodeSize - psg1a->GetNumNodes();
      psg1b = graph1.CreateComplementarySubGraph(uSel1, uMax1b);
      psg2b = graph2.CreateComplementarySubGraph(uSel2, uMax2b);
      if (psg1b == 0 || psg2b == 0) {
        delete psg1b;
        delete psg2b;
      }
      else {
        break;
      }
    }
  }

  Graph* ptNewGraph1 = new Graph;
  Graph* ptNewGraph2 = new Graph;

  // Combines "psg1a" with "psg2b".
  // Combines "psg1b" with "psg2a".
  if (ptNewGraph1->InitGraph(*psg2b, *psg1a, 1) == false ||
      ptNewGraph2->InitGraph(*psg1b, *psg2a, 1) == false) {
    delete ptNewGraph1;
    delete ptNewGraph2;
    delete psg1b;
    delete psg2b;
    return false;
  };

  ptNewGraph1->SetOperator(OP_CROSSOVER);
  ptNewGraph2->SetOperator(OP_CROSSOVER);
  ptNewGraph1->SetMother(graph2.GetGraphID());
  ptNewGraph1->SetFather(graph1.GetGraphID());
  ptNewGraph2->SetMother(graph1.GetGraphID());
  ptNewGraph2->SetFather(graph2.GetGraphID());
  
  dest.AddGraph(ptNewGraph1);
  dest.AddGraph(ptNewGraph2);

#ifdef CROSSOVER_DETAIL
  std::cout << "The crossover operation performed.\n";
  std::cout << "*** SubGraph1a ***\n";  psg1a->Display(std::cout);
  std::cout << "*** SubGraph1b ***\n";  psg1b->Display(std::cout);
  std::cout << "*** SubGraph2a ***\n";  psg2a->Display(std::cout);
  std::cout << "*** SubGraph2b ***\n";  psg2b->Display(std::cout);
#endif

  delete psg1b;
  delete psg2b;
  return true;
}

#endif  //INCLUDE__CROSSOVER_H__FILE