# A Inver-over approach.

 

use strict;
use List::Util qw/shuffle/;
my $pop_size   = 50;
my $number_column = 20;
my @population;
my $p = 0.02;#mutation rate.
my @target = (0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19); 

 
#procedure inver-over
#random initialization of the population P.

for (0..$pop_size-1){
 $population[$_] = genotype();
}
 
for my $generation (0..1000) { #not satisfied termination condition of
+ generations
 print"generation: $generation\n";
 
 foreach my $gene (@population){
  my @temp_gene = split /,/, $gene;
  my $pos_c = int(rand($number_column));
  my $c =  $temp_gene[$pos_c];
  my $pos_c_prime=9999;
  my $c_prime = 9999;
  #print "temp gene: @temp_gene\n";
  #print "pos c: $pos_c\n";
  #print "c: $c\n";
  
  while(){# REPEAT
  
  if(rand()<$p){
    #select the city c' from the remaining S'
   while(($c_prime == $c) or ($c_prime == 9999)){   
    $c_prime = $temp_gene[int(rand($number_column))];
    #print"temp gene c prime : $c_prime\n";
   }
   
  }else{
      #select randomly an individual from P
           my @other_temp_gene = split /,/, ($population[int(rand($pop
+_size))]);
           #print "other temp gene: @other_temp_gene\n";
           #assign to c' the city next to the city c in the selected i
+ndividual
           my $found_c_flag = 0; 
           my $c_counter=0;
           while($found_c_flag == 0 and $c_counter<$number_column){
            if($other_temp_gene[$c_counter] == $c ){
            $c_prime = $other_temp_gene[$c_counter+1];
             $found_c_flag=1;
             #print "other temp c prime: $c_prime\n";
            }
            $c_counter++;
           }
  }
  # if next or previous city of city c in S'is c'
  if ($temp_gene[$pos_c+1] == $c_prime or $temp_gene[$pos_c-1]==$c_pri
+me){
           #print "goto Label\n";
      goto LABEL;#EXIT FROM REPEAT LOOP 
  }
  #inver next c to c'
  my $c_prime_positioner=0;
  while($pos_c_prime==9999){
      if($c_prime == $temp_gene[$c_prime_positioner]){
          $pos_c_prime=$c_prime_positioner;
      }
      $c_prime_positioner++;
  }
  my @seg;
  if ($pos_c<$pos_c_prime){
        @seg = @temp_gene[$pos_c+1..$pos_c_prime];    
        my @seg_temp = reverse @seg;
        for my $insert_index(0..$#seg_temp){
           $temp_gene[$pos_c+1+$insert_index]=$seg_temp[$insert_index]
+;
          }  
  }else{
          @seg = @temp_gene[$pos_c_prime..$pos_c-1];
          my @seg_temp = reverse @seg;
          for my $insert_index(0..$#seg_temp){
           $temp_gene[$pos_c_prime+$insert_index]=$seg_temp[$insert_in
+dex];
          }
  }
  
  #c<-c'
  $c = $c_prime;
  }#REPEAT
  
  LABEL: my $final_temp_gene = join ",", @temp_gene;
  #print"gene: $gene\n";
  #print"final temp gene: $final_temp_gene\n";
  #sleep 15; 
  my $fitness_temp_gene     = fitness($final_temp_gene);
  my $fitness_gene         = fitness($gene); 
  if($fitness_temp_gene<$fitness_gene){#evalS'<evalS
   #print"swap here\n";
   $gene = $final_temp_gene;
  }
 }
}


sub fitness {
    #print "input $_[0]\n";
    my @input =  split /,/, $_[0];
    my $right_count = 0;
    for my $i(0..$#input){
        $right_count = $right_count + abs($input[$i]-$target[$i]);
    }
    if($right_count==0){
        print"here: $right_count\n";
        print"@input";
        exit;
    }
    
    return $right_count;
}
 
sub genotype {
 my @gene = shuffle 0 .. $number_column-1;
 return  join ",", @gene;
}
[download]