operator.cpp

Local search is defined in terms of the neighborhood structure of the search space. This is implemented in NeighborOp from which specific operators such as Swap are derived. The user must define gen_mutation() and commit() for CircularPermutation specifically, using template specialization.

We illustrate the requirement in the SwapOp operator. In gen_mutation(), a random pair of indices of the solution, known as a mutation is generated. In commit(), a pair of ``mutation'' is applied to the circular permutation solution. The separation of these two methods is meant to make the system more efficient because often several neighbors are generated but only one or few committed, see chapter A.5.

template <>
void SwapOp<CircularPermutation>
  ::gen_mutation(const CircularPermutation &s,
                 mutation_element *mut)
{
  element_index random1, random2;  
  random1 = (rand() % s.get_size()) + 1 ;
  random2 = (rand() % s.get_size()) + 1;
  while(random2 == random1) random2 = (rand() % s.get_size())+1;
  
  mut->operation = Swap;
  if(random1<random2) mut->set_mutation(random1, random2);
  else mut->set_mutation(random2, random1);
}

template <>
void SwapOp<CircularPermutation>
  ::commit(CircularPermutation *s, 
           const mutation_element & mut)
{
  element first_element, second_element, tmp_element;
  element_index first_index = mut.first_index;
  element_index second_index = mut.second_index;

  first_element = s->element_lookup(first_index);
  second_element = s->element_lookup(second_index);
  
  tmp_element = s->perm[first_index];
  s->perm[first_index] = s->perm[second_index];
  s->perm[second_index] = tmp_element;
  
  tmp_element = s->inverse_perm[first_element];
  s->inverse_perm[first_element] = s->inverse_perm[second_element];
  s->inverse_perm[second_element] = tmp_element;
}