Fast and Efficient Genetic Algorithm’s Parents Generator for Travelling Salesman Problem: Random Permutation Sequence of Arrays Using Durstenfeld’s Algorithm

written by Yuri Ardila

Durstenfeld’s algorithm was first introduced by Richard Durstenfeld in the early 1960’s. He enhanced the functional term of Fisher-Yates Shuffle Algorithm that was described in 1938 by Ronald A. Fisher and Frank Yates, in their book Statistical tables for biological, agricultural and medical research.

Please refer to:

http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

For more information about the algorithm.

Travelling Salesman Problem is known as one of Genetic Algorithm(GA)’s difficult problem. In short, a program has to find the shortest distance or the minimum cost for a salesman, given a condition that he has to travel all towns for the most satisfying result. Mostly, under the circumstance that the number of existing towns exceeds more than two dimensional loops can efficiently process the possibilities.
Please refer to:

http://en.wikipedia.org/wiki/Travelling_salesman_problem

For more information about TSP.

Now, the possibly fast and efficient way to generate initial parents for the GA, is to adopt Durstenfeld’s algorithm. As you now may have read about the shuffle algorithm, i am only going to explain how it works to generate GA’s parents:

For instance, there are 8 towns:
0 1 2 3 4 5 6 7
these numbers will be put in a temp array called i_swap[], thus:
i_swap[0] = 0,
i_swap[1] = 1,
i_swap[2] = 2,
.
.
.
i_swap[7] = 7,

and we want to start naming towns from capital letter A, so we do #define letter_start = 65.

Therefore, we only have to assign the result of (letter_start + i_swap) to the parent, and use rand() to take an i_swap variable.

temp = rand() % size; /* size = 8, hence temp will be a random number ranged 0 to 7 */
parents[i][j] = letter_start + i_swap[temp];

Then, we iterate size by -1 (size–), and also change the swapindex to n-1 (swapindex–).

Here’s how it works basically:

1.

- swapindex = 7 /* last item of i_swap */

- i_swap:

0 1 2 3 4 5 6 7

- rand() % size produced a random number ranged 0 – 7, for example, 5

- parents[i][0] = letter_start + i_swap[5] = 65 + 5 = 70 = ‘F’

- parents[i] = F

- bring i_swap[swapindex] value to i_swap[5], and change i_swap[swapindex] value to swapindex

- current i_swap:

0 1 2 3 4 7 6 7

- swapindex = 6

- size = 7

2.

- swapindex = 6

- i_swap:
0 1 2 3 4 7 6 7

- rand() % size produced 3, a random number ranged 0 – 6

- parents[i][1] = letter_start + i_swap[3] = 65 + 3 = 68 = ‘D’

- parents[i] = F D

- bring i_swap[swapindex] value to i_swap[3], and change i_swap[swapindex] value to swapindex

- current i_swap:

0 1 2 6 4 7 6 7

- swapindex = 5

- size = 6

3.

- swapindex = 5
- i_swap:
0 1 2 6 4 7 6 7

- rand() % size produced 5, a random number ranged 0 – 5

- parents[i][1] = letter_start + i_swap[5] = 65 + 7 = 72 = ‘H’

- parents[i] = F D H

- bring i_swap[swapindex] value to i_swap[5], and change i_swap[swapindex] value to swapindex

- current i_swap:

0 1 2 6 4 5 6 7

- swapindex = 4

- size = 5

4.

- swapindex = 4
- i_swap:
0 1 2 6 4 5 6 7

- rand() % size produced 2

- parents[i][1] = letter_start + i_swap[2] = 65 + 2 = 67 = ‘C’

- parents[i] = F D H C

- bring i_swap[swapindex] value to i_swap[2], and change i_swap[swapindex] value to swapindex

- current i_swap:

0 1 4 6 4 5 6 7

- swapindex = 3

- size = 4

5.

- swapindex = 3
- i_swap:
0 1 4 6 4 5 6 7

- rand() % size produced 0

- parents[i][1] = letter_start + i_swap[0] = 65 + 0 = 65 = ‘A’

- parents[i] = F D H C A

- bring i_swap[swapindex] value to i_swap[0], and change i_swap[swapindex] value to swapindex

- current i_swap:

6 1 4 3 4 5 6 7

- swapindex = 2

- size = 3

6.

- swapindex = 2
- i_swap:
6 1 4 3 4 5 6 7

- rand() % size produced 1

- parents[i][1] = letter_start + i_swap[1] = 65 + 1 = 66 = ‘B’

- parents[i] = F D H C A B

- bring i_swap[swapindex] value to i_swap[1], and change i_swap[swapindex] value to swapindex

- current i_swap:

6 4 2 3 4 5 6 7

- swapindex = 1

- size = 2

7.

- swapindex = 1
- i_swap:
6 4 2 3 4 5 6 7

- rand() % size produced 0

- parents[i][1] = letter_start + i_swap[0] = 65 + 6 = 71 = ‘G’

- parents[i] = F D H C A B G

- bring i_swap[swapindex] value to i_swap[1], and change i_swap[swapindex] value to swapindex

- current i_swap:

4 1 2 3 4 5 6 7

- swapindex = 0

- size = 1

last, 8.

- swapindex = 0
- i_swap:
4 1 2 3 4 5 6 7

- rand() % size can only produce 0

- parents[i][1] = letter_start + i_swap[0] = 65 + 4 = 69 = ‘E’

- parents[i] = F D H C A B G E

- bring i_swap[swapindex] value to i_swap[1], and change i_swap[swapindex] value to swapindex

- current i_swap:

0 1 2 3 4 5 6 7

- swapindex = -1

- size = 0

There it is, a nicely random sequence in parent, F D H C A B G E, and an initialized i_swap for the next parent generation. and since swapindex = -1 and size = 0, we just simply have to initialize them back to swapindex = 7, and size = 8.
And also don’t forget to give rand() a different seed, like time(NULL) – 1, or any different seed than the former will also work.

Note that this shuffle algorithm may also be implemented in any form of generating random permutation sequences.

This is the code written in C.

/*
Fast and Efficient Genetic Algorithm’s Parents Generator for Travelling Salesman Problem: Random Permutation Sequence of Arrays Using Durstenfeld’s Algorithm
Copyright© by Yuri Ardila, November 2010.
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define parentsize 16 /* 16 towns */
#define letter_start 65

void swap(int* , int, int);

int main(void){
int parentnumber;
int i, j, k;
int temp;

unsigned int randseed = time(NULL);

scanf(“%d”, &parentnumber);

char parents[parentnumber][parentsize];
int swapindex; /* last item of the corresponding array */
int size; /* temporary var for size */
int i_swap[parentsize]; /* check whether an item already exists */

/* initialize i_swap */
for(i = 0; i < parentsize; i++){
i_swap[i] = i;
}

srand(randseed); /* seed rand() */

/* intial parents generator */
for(i = 0; i < parentnumber; i++){
for(swapindex = parentsize – 1,   size = parentsize, j = 0; j < parentsize; j++, swapindex–, size–, randseed–){
temp = rand() % size;
parents[i][j] = letter_start + i_swap[temp];
swap(i_swap, swapindex, temp);
}
srand(randseed);
}

for(i = 0; i < parentnumber; i++){
for(j = 0; j < parentsize; j++){
printf(“%c “, parents[i][j]);
}
printf(“\n”);
}
return 0;
}

/* swapping items for a better efficiency */

void swap(int* im_swapping, int swap_index, int the_random){
im_swapping[the_random] = im_swapping[swap_index];
im_swapping[swap_index] = swap_index;
}

Advertisement