solutionea.cpp

随机需求vrp

#include "SolutionEA.h"

using namespace std;

// Construct a solution for EA and a pointer to initialized problem data.
SolutionEA::SolutionEA( Random* rnd, Control& control,  Problem* p ) :
  Solution(rnd, control, p )
{}

// PMX crossover (implemented as described in Michalewicz, page 216)
void SolutionEA::pmx_crossover(SolutionEA* parent1, SolutionEA* parent2){

  int i,first,last,swap;

  int *map1, *conflict1;
  int city;

  map1 = new int[problem->numberOfCustomers+1];
  conflict1  = new int[problem->numberOfCustomers+1];
  for(i=0; i< problem->numberOfCustomers; i++) {
    map1[i] = conflict1[i] = 0;
  }

  /* First choose two random cross points */
  /* Gnerate the two points randomly. */
  first = (int) (rg->next()* (problem->numberOfCustomers));
  do {
    last = (int) (rg->next()* (problem->numberOfCustomers));
  } while (last == first);

  if (first > last) {		/* Make sure that they are in the */
    swap = first;		/* right order.                   */
    first = last;
    last = swap;
  }

  /* first the segments between the bounds are swapped */
  for (i=first;i<last;i++){
    (*this)[i] = (*parent2)[i];
    /* and define the mappings */
    map1[(*parent2)[i]] = (*parent1)[i];
    conflict1[(*parent2)[i]] = 1;
  }

  /* now read along the parent chromo: if there is a conflict ,
   * replace with the mapping, if not, copy the gene from parent1
   * to the chromo  */

  for (i=0;i<first;i++){
    if (conflict1[(*parent1)[i]] == 1){
      city = map1[(*parent1)[i]];
      while (conflict1[city])
	city = map1[city];
      (*this)[i] = city;
    }
    else
      (*this)[i] = (*parent1)[i];
  }

  for (i=last;i<(problem->numberOfCustomers);i++){
    //cout<<i <<" ";
    if (conflict1[(*parent1)[i]] == 1){
      city = map1[(*parent1)[i]];
      while (conflict1[city])
	city = map1[city];
      (*this)[i] = city;
    }
    else
      (*this)[i] = (*parent1)[i];
  }
  //cout<<endl;
  
  delete map1;
  delete conflict1;

}

// OX crossover (see Michalewicz, page 217) readapted to always start from the depot
void SolutionEA::ox_crossover(SolutionEA* parent1, SolutionEA* parent2){

  int i,first,last,swap,segLength,j,k,place,depot;
  int *segment1, *in_substring1, *perm;

  /* First choose two random cross points */
  /* Generate the two points randomly. */
  first = (int) (rg->next()* (problem->numberOfCustomers));
  do {
    last = (int) (rg->next()* (problem->numberOfCustomers));
  } while (last == first);

  if (first > last) {		/* Make sure that they are in the */
    swap = first;		/* right order.                   */
    first = last;
    last = swap;
  }

  /* Calculate the length of the segment that still needs to
   * be allocated, ie the number of genes not included in the substring
   * defined between the cut points */
  segLength = problem->numberOfCustomers-(last-first);

  perm = new int[problem->numberOfCustomers+1];
  segment1 = new int[segLength+1];
  in_substring1 = new int[problem->numberOfCustomers+1];

  for(i=0; i< problem->numberOfCustomers; i++) {
    in_substring1[i] = 0;
  }

  /* First we can copy the substrings defined by the cut points
   * straight into the children
   * and mark these alleles as out of the equation
   */

  for (i=first;i<last;i++){
    perm[i] = (*parent1)[i];
    in_substring1[(*parent1)[i]]  = 1;
  }
  if(first == 0)
    depot = 0;

  /* Now, starting from the second cut point of one parent, the alleles
   * from the other parent are copied in the same order, omitting alleles
   * already present
   */
  j = 0;
  k = 0;
  for (i=0;i< problem->numberOfCustomers;i++){
    place = last+i;
    if (place >= problem->numberOfCustomers)
      place = place- problem->numberOfCustomers;
    if (!in_substring1[(*parent2)[place]])
      segment1[j++] = (*parent2)[place];
  }

  /* Now we have the new segments, fill up the child genotypes,
   * starting at the 2nd cut point again
   */
  for (i=0;i<segLength;i++){
    place = last+i;
    if (place >= problem->numberOfCustomers)
      place = place-problem->numberOfCustomers;
    perm[place] = segment1[i];
    if(perm[place]==0)
      depot = place;
  }

  /*  Now put the permutation back in standard for with the 
   *  depot in the first position if necessary
   */
  for (i=0;i< problem->numberOfCustomers;i++){
    place = depot+i;
    if (place >= problem->numberOfCustomers)
      place = place-problem->numberOfCustomers;
    (*this)[i] = perm[place];	
  }

  /* Free the arrays */
  delete in_substring1;
  delete segment1;
}

int SolutionEA::addToList(int* adj_list, int len, int val){
  int i;
  for(i=0; i<len;i++){
    if(adj_list[i] == val){
      //cout<<val <<" c'era gia'"<<endl;
      return 0;
    }
  }
  //cout<<"aggiungo new val "<<val<<endl;
  adj_list[len] = val;
  return 1;
}

void SolutionEA::removeFromList(int* adj_list, int len, int val){
  int i;
  for (i = 0; i < len - 1; i++){
    if(adj_list[i] ==val)
      adj_list[i] = adj_list[len-1];
  }
}

// Edge recombination crossover (see Michalewicz, page 221) readapted to always start from the depot
void SolutionEA::edge_crossover(SolutionEA* parent1, SolutionEA* parent2){
  int i,current,next,previous,pos,bestNext, bestCount, neighbour;
  //  static
  int **edgeMap = 0;

  if(edgeMap == 0){
      edgeMap = new int*[problem->numberOfCustomers]; 
      for(i = 0;i < problem->numberOfCustomers;i++)
	edgeMap[i] = new int[4];
  }
  //static
  int* edgeCount = new int[problem->numberOfCustomers]; 
  //static
  int* visited = new int[problem->numberOfCustomers];
  for(i=0; i< problem->numberOfCustomers; i++){
    edgeCount[i] = 0;
    visited[i] = 0;
  }
  for (i=0;i< problem->numberOfCustomers;i++){
    next = (i+1)%problem->numberOfCustomers;
    previous = (i + problem->numberOfCustomers - 1)%problem->numberOfCustomers;
    current = (*parent1)[i];
    //cout<<"current "<< current<<" count "<< edgeCount[current]<< endl;
    edgeCount[current] += addToList(edgeMap[current],edgeCount[current],(*parent1)[next]);
    edgeCount[current] += addToList(edgeMap[current],edgeCount[current],(*parent1)[previous]); 
    current = (*parent2)[i];
    edgeCount[current] += addToList(edgeMap[current],edgeCount[current],(*parent2)[next]); 
    edgeCount[current] += addToList(edgeMap[current],edgeCount[current],(*parent2)[previous]);
  }
  current = (*parent1)[0];
  (*this)[0] = current;
  pos =1;
  while(pos < problem->numberOfCustomers){
    visited[current] = 1;
    if (edgeCount[current]){ //remove current from edge map of adjacent nodes 
      for (i = 0; i < edgeCount[current]; i++){
	removeFromList (edgeMap[ edgeMap[current][i] ],edgeCount[ edgeMap[current][i] ], current); 
	edgeCount[ edgeMap[current][i] ]--;
      }

      bestNext = -1, bestCount = 5;
      for (i = 0; i < edgeCount[current]; i++){
	neighbour = edgeMap[current][i];
	//cout<<"neighbour "<<neighbour<<endl;
        if (edgeCount[neighbour] < bestCount){ 
	  bestNext =neighbour;
	  bestCount = edgeCount[neighbour];
	}
      }
      //cout<<"bestNext "<<bestNext<<endl;
      (*this)[pos++] = bestNext;
      current = bestNext;
    } 
    else{
      if (pos == problem->numberOfCustomers) 
	break;
      for (current = 0; visited[current]; current++); 
      (*this)[pos++] = current;
      //cout<<" edge failure "<<(*this)[pos-1]; 
    }
  }
  /* Free the arrays */
  for(i = 0;i < problem->numberOfCustomers;i++) 
   delete edgeMap[i];
  delete edgeMap;
  delete edgeCount;
  delete visited;
}

// Inver-over operator (Tao and Michalewicz PPSN V, page 803) readapted to always start from the depot
void SolutionEA::inverover(SolutionEA* pop, int popSize){
  int current, next;
  current = (int) (rg->next()* (problem->numberOfCustomers));
  //while(){
    if(rg->next()<0.1){
      next = (int) (rg->next()* (problem->numberOfCustomers));
    }
    else{

    }
    //}

}

// swap based mutation
void SolutionEA::swap_mute(double rate)
{
  int swap1,swap2;
  int tmp;

  if ( rg->next() < rate){
    swap1 =  (int) (rg->next()* (problem->numberOfCustomers));
    while(swap1 == 0)
      swap1 =  (int) (rg->next()* (problem->numberOfCustomers));

    /* swap2 is and adjacent loci, randomly choose if left or right */
    /* (being careful if we have chosen an end !) */
    /* (and that the depot is not moved from the first position)*/

    if (swap1 == problem->numberOfCustomers-1)
      swap2 = swap1 -1;
    else if (swap1 == 1)
      swap2 = swap1+1;
    else if (rg->next()*2==0)
      swap2 = swap1+1;
    else
      swap2 = swap1-1;

    tmp = (*this)[swap1];
    (*this)[swap1] = (*this)[swap2];
    (*this)[swap2] = tmp;
  }

}

/* order based mutation */
/* this operator picks 2 loci at random and exchanges their alleles*/
/* taking care that thedepot remains first in the permutation*/
void SolutionEA::obm_mute(double rate)
{
  int swap1,swap2;
  int tmp;

  if (rg->next() < rate){
    swap1 = (int)(rg->next()* (problem->numberOfCustomers-1)) + 1;
    swap2 = (int)(rg->next()* (problem->numberOfCustomers-1)) + 1;

    while (swap2 == swap1)
      swap2 = (int)(rg->next()* (problem->numberOfCustomers-1)) + 1;
    
    tmp = (*this)[swap1];
    (*this)[swap1] = (*this)[swap2];
    (*this)[swap2] = tmp;
  }
}

/* inversion operator*/
void SolutionEA::inversion(double rate)
{
  int i,first,last,swap,segLength,j;
  int *segment;

  if (rg->next() < rate){
    /* First choose two random cut points */
    /* taking care none of the two is the depot */
    first = (int)(rg->next()*(problem->numberOfCustomers-1)) + 1;
    do {
      last = (int)(rg->next()*(problem->numberOfCustomers-1)) + 1;
    } while (last == first);

    if (first > last) {		/* Make sure that they are in the */
      swap = first;		/* right order.                   */
      first = last;
      last = swap;
    }

    /* Calculate the length of the segment that needs to
     * be inverted, ie the number of genes included in the substring
     * defined between the cut points */
    segLength = (last-first);
    segment = new int[segLength+1];
    /* First we can copy the inverted substring defined by the cut points
     * into a segment
     */
    j=0;
    for (i=first;i<=last;i++){
      segment[i-first] = (*this)[last-j++];
      //cout<<(*this)[i]<<" "<<segment[i-first]<<endl;
    }
    /* Now copy the inverted alleles between the two cut points*/
    for (i=first;i<= last;i++){
      (*this)[i] = segment[i-first];
    }
    /* Free the array */
    delete segment;
  }
}