eatsp.cpp

随机需求vrp

/***************************************************************************
                          eaTSP.cpp  -  description

               A "flimflam" Simple Memetic Algorithm to solve the VRPSD
               using TSP evaluation function for the orOpt local search
                   developed for the Metaheuristics Network
                             -------------------
    begin                : Fri Aug 8 2003  
    last modified        : Fri Aug 8 2003
    version              : 0.1  
    copyright            : (C) 2003 by Olivia Rossi-Doria
    email                : [e-mail]
 ***************************************************************************/

/***************************************************************************
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation.                                         *
 *                                                                         *
 ***************************************************************************/

#include "Control.h"
#include "Problem.h"
#include "SolutionEA.h"
#include "orOptTSP.h"
#include "Random.h"
#include "farthestInsertion.h"
//#include "nearestNeighbour.h"

#include <fstream.h>
#include <iostream.h>

using namespace std;

Random* rnd;

bool compareSolution(SolutionEA * sol1, SolutionEA * sol2)
{
 return sol1->expectedCost < sol2->expectedCost;
}

SolutionEA* selection(SolutionEA** pop, int popSize ){

  // tournament selection with tornament size 2
  int first, second;
  first = (int)(rnd->next()*popSize);
  second = (int)(rnd->next()*popSize);

  if(pop[first]->expectedCost <= pop[second]->expectedCost)
      return(pop[first]);
  else
      return(pop[second]);

}

double adaptive(double mute_rate,SolutionEA* parent1, SolutionEA* parent2)
{
  int loop, count;
  double prob;
  int geno_size = (int)((*parent1).size());
  count = 0;
  for (loop = 0; loop < geno_size; loop += 1) {
    if ((*parent1)[loop] == (*parent2)[loop])
      count++;
  }
  /* Proportion = observed / total. */
  prob = ((double) count) / ((double) geno_size);
  //cout<<"mute_rate "<<prob * mute_rate<<endl;
  return (prob * mute_rate);
}

double nonadaptive(double mute_rate,SolutionEA* parent1, SolutionEA* parent2){
  return (mute_rate);
}

double (*mrate) (double mute_rate,SolutionEA* parent1, SolutionEA* parent2) = adaptive;

int main( int argc, char** argv ) {

  //Create a control object from the command line arguments.
  Control control( argc, argv );

  //Random object.
  rnd = new Random((unsigned) control.getSeed());

  //ostream& output = control.getOutputStream();

  //Initialize the problem instance, using input file stream and input data given by control.
  Problem *problem = new Problem(control);

  int popSize;
  int isadaptive; // 0 false, 1 true
  double m_rate;
  int gen =0;

  if( control.parameterExists( "-popSize" ) ) {
    popSize = control.getIntParameter( "-popSize" );
  } else {
    popSize = 10; // default
  }

  if( control.parameterExists( "-mr" ) ) {
    m_rate = control.getDoubleParameter( "-mr" );
  } else {
    m_rate = 0.2; // default
  }

  if( control.parameterExists( "-a" ) ) {
    isadaptive = control.getIntParameter( "-a" );
  } else {
    isadaptive = 0; // default
  }
  if (isadaptive)
    mrate = adaptive;
  else
    mrate = nonadaptive;	

  while( control.triesLeft() ) {

    control.beginTry();

    // construction of the heuristic
    SolutionEA* pop[popSize];

    for(int i=0; i < popSize; i++){
      pop[i] = new SolutionEA(rnd, control, problem);
      //pop[i]->initializeRandomSolution();
      randomizedFarthestInsertion(rnd, (*pop[i]));
      pop[i]->computeExpectedCost();
      /*farthestInsertion((*pop[i]));
      cout<<"pop "<<i <<" "<<pop[i]->computeExpectedCost()<<endl;
      pop[i]->printOn(cout);
      pop[i]->inversion(0.8);
      cout<<" after inversion "<<pop[i]->computeExpectedCost();*/
      orOptTSP(rnd, control, *pop[i]);
      //cout<<" after orOpt "<<pop[i]->computeExpectedCost()<<endl;
    }
    /*for(int i=popSize/2; i < popSize; i++){
      pop[i] = new Solution(rnd, control, problem);
      //pop[i]->initializeRandomSolution();
      nearestNeighbour((*pop[i]));
      cout<<"pop "<<i <<" "<<pop[i]->computeExpectedCost()<<endl;
      pop[i]->printOn(cout);
      orOpt(rnd, control, *pop[i]);
      cout<<"dopo orOpt "<<pop[i]->computeExpectedCost()<<endl;
      }*/
    // sort the population by cost
    sort(pop, pop + popSize, compareSolution);
    //pop[0]->printOn(cout);
    control.setCurrentCost( pop[0]->expectedCost );  
    //cout << "Best initial individual "<< pop[0]->expectedCost<< " time " << control.getTime() <<endl;

    SolutionEA* parent1;
    SolutionEA* parent2;

    SolutionEA* child = new SolutionEA(rnd, control, problem);

    while( control.timeLeft() ) {
      // heuristic iteration
      gen++;
      // selection
      parent1 = selection(pop, popSize);	/* Select two parents. */
      parent2 = selection(pop, popSize);
      /*cout<<"parent1"<<endl;
      parent1->printOn(cout);
      cout<<"parent2"<<endl;
      parent2->printOn(cout);*/
      child->edge_crossover(parent1, parent2);	/* Cross them */
      child->computeExpectedCost();
      //cout<<"child "<<child->expectedCost<<endl;
      //child->printOn(cout);
      //child->swap_mute(m_rate);
      child->swap_mute(mrate(m_rate,parent1, parent2));
      //child->swap_mute(m_rate);
      //orOpt local search may improve the child solution
      orOptTSP(rnd, control, (*child));
      //cout<<"after LS " <<child->expectedCost <<" ricalcolo " <<child->computeExpectedCost()<<endl;
      //child->computeExpectedCost();

      //replace worst
      pop[popSize - 1]->copySolution((*child)); 	/* Insert the child into */

      // sort the population by cost
      sort(pop, pop + popSize, compareSolution);

      control.setCurrentCost( pop[0]->expectedCost );  

    }
    //cout<<"number of generations "<< gen<<endl;
    // clean up your heuristic
    delete child;

    control.endTry();
    pop[0]->printOn(control.getOutputStream()); 

    //remember to clean up the population
    for(int i=0; i < popSize; i++){
      delete pop[i];
    }
  }

  // clean up the problem
  delete problem;
  delete rnd;
}