acs.cpp

vrpsd -tabu搜索求解！！！！！！！！！！！！！！！！！！！！！！！

/***************************************************************************
                           acs.cpp   -   description
                            -----------------------
begin                   : Tuesday August 5 16:30:53 CET 2003
copyright               : (C) 2003 by Max Manfrin
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; either version 2 of the License, or      *
*   (at your option) any later version.                                    *
*                                                                          *
***************************************************************************/

#include "Problem.h"
#include "Solution.h"
#include "orOpt.h"
#include "orOptTSP.h"
#include "Control_acs.h"
#include "Random.h"
#include "farthestInsertion.h"
#include "Ant.h"
#include "util.h"

#include <fstream.h>
#include <iostream.h>
#include <math.h>
#include <limits.h>
#include <cfloat>
using namespace std;

vector<Ant*> colony;
Solution* bestglobalSolution;
double** pheromoneMatrix = NULL;

// PRINT PHEROMONE MATRIX
// pheromoneMatrix[problem->numberOfCustomers][problem->numberOfCustomers]
//
void print_pheromoneMatrix( Problem *problem) {
  cout << "PHEROMONE MATRIX" << endl;
  for (int j=0; j < problem->numberOfCustomers; j++) {
    cout << "Customer " << j << ":";
    for (int i=0; i < problem->numberOfCustomers; i++) {
      cout << pheromoneMatrix[i][j] << " ";
    }
    cout << endl;
  }
  cout << endl;
}

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

    
  // CREATE THE CONTROL OBJECT
  // PARSING THE COMMAND LINE
  //
  Control_acs control( argc, argv );


  // CREATE THE RANDOM NUMBER GENERATOR OBJECT
  // 
  Random* rnd = new Random((unsigned) control.getSeed());

  // CREATE THE PROBLEM OBJECT
  // LOADING DATA FROM THE INSTANCE FILE PASSED AT THE COMMAND LINE
  // 
  Problem *problem = new Problem( control );


  // RUN A NUMBER OF TRIES, CONTROL TAKE CARE OF THAT
  // 
  while( control.triesLeft() ) {

    // CONTROL START A NEW TRY 
    //
    control.beginTry();    

    if (! pheromoneMatrix){
      // CREATE THE PHEROMONE MATRIX
      // double** pheromoneMatrix[problem->numberOfCustomers][problem->numberOfCustomers]
      //
      pheromoneMatrix = DoubleMatrixAlloc(problem->numberOfCustomers, problem->numberOfCustomers);
    }
    
    // - Initialize bestglobalSolution
    //
    bestglobalSolution = new Solution( rnd, control, problem);
    (*bestglobalSolution).expectedCost = DBL_MAX;

    // CREATE THE ANT COLONY
    // Each ant build a starting solution using the randomized farthest insertion heuristic
    //
    for (int i=0; i < control.getCOLONYSIZE(); i++){
      colony.push_back(new Ant(rnd, control, problem));
#ifdef DEBUG
      cout << "[DEBUG] ant[" << i << "]: " << (*colony[i]->currentSolution).expectedCost << endl;
#endif
      if ((*colony[i]->currentSolution).expectedCost < (*bestglobalSolution).expectedCost) {
	(*bestglobalSolution).copySolution( (*colony[i]->currentSolution));
	control.setCurrentCost((*bestglobalSolution).computeExpectedCost());
      }
      //orOpt local search may improve currentSolution.
      //
      //      control.setCurrentCost((*colony[i]->currentSolution).computeExpectedCost());
#ifdef DEBUG
      cout << "[DEBUG]                before orOpt = " << (*colony[i]->currentSolution).expectedCost << endl;
#endif
      orOpt(rnd, control, (*colony[i]->currentSolution));
      (*colony[i]->currentSolution).computeExpectedCost();
      //#ifdef DEBUG	
      //      cout << "[DEBUG]                   after orOpt: " << (*colony[i]->currentSolution).expectedCost << endl;
      //#endif
    }

    // ******************************
    // ** 1 ** INITIALISATION PHASE
    // ******************************

    // - Initialize pheromoneMatrix[problem->numberOfCustomers][problem->numberOfCustomers] = TAU0
    //
    for (int i=0; i < problem->numberOfCustomers; i++) {
      for (int j=0; j < problem->numberOfCustomers; j++) {
	pheromoneMatrix[i][j] = control.getTAU0();
      }
    }
    
    // - Train the pheromone matrix with the initial solution 
    // Simulate 30 iteration for each 
    //
    // Ant applies the global update rule for evaporation
    // tau[i][j] = ((1.0 - RHO) * tau[i][j])
    //
    for (int k=0; k < 100; k++) {
      for (int i=0; i < problem->numberOfCustomers; i++) {
	for (int j=0; j < problem->numberOfCustomers; j++) {
	  pheromoneMatrix[i][j] = ((1.0 - control.getRHO()) * pheromoneMatrix[i][j]);
	}
      }
    }
    // Ant reinforce the elements of the pheromoneMatrix that are part of the
    // initial solutions 
    // 
    int source = 0;
    int destination = 1;
    for (int j=0; j < control.getCOLONYSIZE(); j++) {
      //#ifdef DEBUG
      //      cout << "[DEBUG] ant[" << j << "] reinforcing the pheromone matrix" << endl;
      //#endif
      for (int i=0; i < 100; i++) {
	source = 0;
	destination = 1;
	for (int step=1; step < (*problem).numberOfCustomers; step++) {
	  destination = (*colony[j]->currentSolution)[step];
	  pheromoneMatrix[source][destination] = ((1.0 - control.getRHO()) * pheromoneMatrix[source][destination]) + (control.getRHO() * (control.getQ() / (*bestglobalSolution).expectedCost));
	  source = destination;
	}
      }
    }
    
    //    cout << "PHEROMONE MATRIX INITIALIZED" << endl;
    //    print_pheromoneMatrix(problem);


    while (control.timeLeft() ) {
      
      control.incrementIterations();
#ifdef DEBUG
      cout << "[DEBUG] -= Iteration =- : " << control.getIterations() << endl;
#endif

      // *********************************
      // ** 2 ** BUILDING SOLUTION PHASE
      // *********************************

      // Ants build solution sequentially
      //
      for(int i=0; i < control.getCOLONYSIZE(); i++) {
	
	// Clear the visited customers array
	//
	(*colony[i]).customer_served.clear();
	for (int j=0; j < problem->numberOfCustomers; j++) {
	  (*colony[i]).customer_served.push_back(false);
	}
	
	// Build the a priori tour one customer after the other
	//
	source = 0;
	destination = 1;
	for (int step=0; step < (*problem).numberOfCustomers-1; step++) {
	  destination = colony[i]->solutionStep(step, source, rnd, control, problem, pheromoneMatrix);
	  (*colony[i]->currentSolution)[step+1] = destination;
	  
	  // ****************************
	  // ** 3 ** LOCAL UPDATE PHASE
	  // ****************************
	  //
	  // Ant applies the local update rule for encouraging diversification
	  // tau[i][j] = (((1 - psi) * tau[i][j]) + (psi * tau0))
	  //
	  pheromoneMatrix[source][destination] = (((1.0 - control.getPSI())* pheromoneMatrix[source][destination]) + (control.getPSI() * control.getTAU0()));	  	  
	  source = destination;
	}
	
	//    cout << "PHEROMONE MATRIX INITIALIZED" << endl;
        //    print_pheromoneMatrix(problem);
	
	//orOpt local search may improve currentSolution.
	//
	control.setCurrentCost((*colony[i]->currentSolution).computeExpectedCost());
#ifdef DEBUG
	cout << "[DEBUG]                before orOpt = " << (*colony[i]->currentSolution).expectedCost << endl;
#endif
	orOpt(rnd, control, (*colony[i]->currentSolution));
	(*colony[i]->currentSolution).computeExpectedCost();
	//#ifdef DEBUG	
	//	cout << "[DEBUG] ant[" << i << "] expected Cost after orOpt = " << (*colony[i]->currentSolution).expectedCost << endl;
	//#endif

	// Check if we found a new global best solution 
	//
	if ((*colony[i]->currentSolution).expectedCost < (*bestglobalSolution).expectedCost) {
	  (*bestglobalSolution).copySolution( (*colony[i]->currentSolution));
	  //#ifdef DEBUG
	  //	  cout << "[DEBUG] new global best: " << (*bestglobalSolution).expectedCost << endl;
	  //#endif
	}


      }
      // *****************************
      // ** 3 ** GLOBAL UPDATE PHASE
      // *****************************
      //
      // Ant applies the global update rule for evaporation and reinforcment on the elements of the
      // Pheromone Matrix that are part of the global best solution
      // tau[i][j] = ((1.0 - RHO) * tau[i][j]) + (RHO * (Q/L_best))
      //
      // 
      int source = 0;
      int destination = 1;
      for (int step=1; step < (*problem).numberOfCustomers; step++) {
        destination = (*bestglobalSolution)[step];
        //	cout << "[DEBUG] pheromoneMatrix["<<source<<"]["<<destination<<"] before global reinforcement:"<<pheromoneMatrix[source][destination]<<endl;
        pheromoneMatrix[source][destination] = ((1.0 - control.getRHO()) * pheromoneMatrix[source][destination]);
    	pheromoneMatrix[source][destination] += (control.getRHO() * (control.getQ() / (*bestglobalSolution).expectedCost));
        //	cout << "[DEBUG] pheromoneMatrix["<<source<<"]["<<destination<<"] after global reinforcement:"<<pheromoneMatrix[source][destination]<<endl;
        source = destination;
      }
    
    }
    control.endTry();
    (*bestglobalSolution).printOn(control.getOutputStream());
#ifdef DEBUG
    cout << "Iterations:" << control.getIterations() << endl;
#endif    
    // DESTROY THE ANT COLONY
    //
    for (int i=0; i < control.getCOLONYSIZE(); i++){
      colony.pop_back();
    }
  }
}