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;
}
News: Mobile Devices’ 3D User Interface
October 27, 2010
The real useful 3D interface is here and should be out on devices very soon. This company called TAT is responsible for over 300 million devices’ user interface around the world. As you can see in the videos, their approach to 3D UI is pretty cool. According to TAT, many devices that uses the 3D cube interface are inefficient since it’s not utilizing the full potential of 3D spaces. You should be able to see many information while single out the one you want to focus on, not hiding them on the other side of the cube completely. Now we just have to wait for this 3D UI to pop out of the screen into real 3D! =)
Gadgets: “Hello? Yuri where are you?” … “DAMN IT MAN! I havent saved my Final Fantasy why did you call me?!”
October 27, 2010
Sony has finally made it OFFICIAL!
THE PLAYSTATION PHONE,
will be running on 3.0, with a 1GHz Qualcomm MSM8655 chip, 512MB RAM, 1GB of ROM, and 4″ size of screen.
It is provided with the slide out type touch screen, directional buttons and command buttons similar to the former Playstation, and also not forgetting the shoulder buttons on each left and right side.
The prototype has been tested although it still struggles with bugs and GUI thingy; nonetheless, Sony has officially pronounced that this beautiful one will come out as soon as next year!
Perhaps all of you are familiar with Playstation Portable, thus with the release of this gadget indicates that we can save our energy by only taking this gadget outside, instead of both cellphone and PSP.
Like the title says, i hope there won’t be any problem if there’s an interruption in the middle of game, and the gadget should be fast enough to run heavy games such as final fantasy or other RPGs.
However, the bottomline is..
I WANT IT!!
Hardware: Mid-end PC equals to ONE processor?! INTEL successfully brought this to reality
October 27, 2010
There you go,
Intel Core i7 Extreme Edition 980X 3.33 GHz Processor – Hexa-Core
for around $1000
Note that the word Hexa literally means it has 6 cores in it. Well it has 6 cores in it.. with 3.33GHz.. and L3 12mb cache..
hmm..
SO WHAT?! That price is insanely expensive!
would be reasonable if you have the same opinion as me.
I think it would make more sense if you parallelized a number of lower cost CPUs such us i7 870 for example? The performance wouldn’t make much difference.. More heat dissipating? Even after you added some high performance cooling system, you would get a lower price (or maybe even a greater performance) than this single product.
Anyway, this CPU is actually promoted as the best gaming CPU processor on the market today.
But however the price is too much dont you think??
英語じゃ。。。。
October 26, 2010
読めません！！
という方もいらっしゃるでしょ！
ではでは、
日本語でも頑張って書きまーす。
最初の日本語ポストやから、
自己紹介させていただきます！
BYGSというのは、Bird-Yuri-Gilang’sからの略です！
なんと、それは僕たちの最初の一文字から取った省略です！
（それぐらい分かるわぃ！って思う方には申し訳なく思います）
次々にまた日本語でポストしますんで、
Stay tune on BYGSでお願いします！^^
Apple: The Forbidden Fruit
October 26, 2010
Well you could say Apple is left naked without Flash and Java, but think for a second here. Apple alternative for not supporting Flash is the HTML 5, and while Java will be replaced with Objective-C++ applications. There are a couple reasons why this could work.
First of all, HTML has been a successful language and will surely continue to HTML 5 eventually. It’s open-source, and it doesn’t have bottle neck running the player like Flash does.
Second, there are hundreds of thousands application maker for iOS devices, and once the application store is available, it should do fine.
Third, Oracle doesn’t support Java for Apple fast enough and it’s always a version behind Windows.
So… @9ildy Let’s get it on!!! d(^_^)b
Remainder: Homeworks and Reports
October 26, 2010
Due: 28th of October, 2010
Class: TOPICS in IT 5, Introduction to Computer Games
Task: Create a Scrolling Shooter Game and a design document, atleast 1 page
Explanation and Ideas:
2 days ahead! I have done nothing T_T
before I go to the explanation, I got a story for you guys..
Last week we got the same homework’s task except that it was not a scrolling shooter game. We had to make a platform game, which for instance is the widely known game mario bros.
The thing is, i was not too familiar with Game Maker 8.0, so i went through a lot of problems. For example, i couldn’t make the sprites animated as it had to be. It just went crazy and doing animation automatically in a weird manner. Very tough….
It took me 11 hours straight from 20:00 to 07:00 to get it right! Was a pain in the a**..
But as the result i got a very nice plot for the game and succeed to make it interesting! yeah
Anyway,
We got a Scrolling Shooter game and the design document to be done the day after tomorrow..
I am thinking to make a Superman side scrolling shooter game, and guess what, the enemies are gonna be Megaman, nicely polished aircrafts, and some cute characters which i don’t get the names. Don’t worry i WILL state all credits reserved.
Here is the sprite i got on sdb.drshnaps.com, and of course it was freely distributed.
Hopefully i got this one done in a less than 11 hours!!
Thought of the Week
October 26, 2010
“Apple will be left naked, with no Flash, no Java, and no Fanbois.”
-and probably with no Jobs-
and we all just have to wait.
for now let’s just have fun with some fart apps from the new Mac Appstore.
Working our @$$ off!
October 26, 2010
Prepare for some serious blogging this week as Yuri, Gilang, and I are back for some more serious blogging on our thoughts. We are trying to get some more posts running through and hope everyone can learn from it. Stay tuned!
No more Java for Apple?
October 26, 2010
Java, one of the most universal programming language on the surface of this earth, is being abandoned by Apple. What will happen next? Apple recently announce that they will support mainly on HTML5 for the web, and application for iOS devices. Without Java, is apple planning to integrate the application support on the new Mac OS X Lion? As many programmers became inpatient, we are eager to find what will happen from here…
3ird
yuriardila
9ildy
