Computer Science November 23, 2007

# Genetic Algorithms 101

I have started working on my bachelor's thesis in physics. It's about using genetic algorithms for finding optimal solutions to physics problems. One of the problems I will solving is simulating equilibrium configurations of two dimensional systems of particles which can attract and repel (dipole systems). This problem is NP hard, which means there is no effective algorithm to find the exact solution in an adequate time. Several other algorithms can be used to approximate the solution and find near-equilibrium configurations, one of them being genetic algorithm technique.

The easiest situation is when the particles are bounded in a circle which border they can't trespass. The goal is to find how these particles will position themselves inside this circle.

This case has already been tackled using the simulated annealing method and the near-optimum solutions for hundreds of particles have been found. This method uses different principles than genetic algorithm method which I will describe shortly. The main idea of simulated annealing method is that the system is given an initial temperature which basically controls how much the particles will fluctuate inside the system. The greater the temperature, the bigger the fluctuations. The temperature gradually gets decreased and the fluctuations get smaller and smaller. Calculating the energy of the system and requiring it to be minimal at each step the temperature gets decreased eventually leads to a solution.

Here is how the solutions for 10, 11, 12, 13, 14 and 15 particles looks like, found using simulated annealing algorithms:

Notice how interestingly and non-intuitively the particles position themselves in a case when another particle gets added to a system of 12 particles. Instead of positioning the new particle somewhere in the middle as in transition from 11 particles to 12, the system decides to put it on the border.

In my thesis I will be using genetic algorithms to arrive at the solution for this problem.

Here is a general (not related to my topic of thesis) description of what genetic algorithms are.

## Genetic Algorithms 101

Genetic algorithms mimic the evolution by natural selection. The basic idea of genetic algorithms is very simple. Genetic algorithms feature populations of individuals which evolve with the use of the principles of selection, variation and inheritance.

One of the ways to implement this idea in computer programs is to represent individuals as strings of binary digits. Each bit in the string represents one gene. Each individual is assigned a numerical evaluation of its merit by a fitness function. The fitness function determines how each gene of an individual will be interpreted and, thus, what specific problem the population will evolve to solve.

Once all individuals in the population have been evaluated, their fitness values are used for selection. Individuals with low fitness get eliminated and the strongest get selected. Inheritance is implemented by making multiple copies of high-fitness individuals. The high-fitness individuals get mutated and they crossover to produce a new population of individuals. Mutation is implemented as flipping individual bits in the binary string representation of an individual and crossover happens as an exchange of binary substrings of two individuals to obtain a new offspring.

By transforming the previous set of individuals to a new one, the algorithm generates a new set of individuals that have better fitness than the previous set of individuals. When the transformations are applied over and over again, the individuals in the population tend to represent improved solutions to whatever problem was posed in the fitness function.

Here is an illustration how a genetic algorithm might work:

I look forward to finding what other interesting projects that I can make using the very useful information I have learnt.

PS. I am writing blog posts less often now because I am really, really busy with studies. Sorry about that.

### Comments

Gut! Viel Spass!

Care to post your fitness function?

Benjamin, I have only been working on this stuff for one week! The thesis is due May, 2008, I still have plenty of time. I'll post some of the results and code here later. Keep on checking back! :)

I'm not sure if this was a typo, but saying "genetic programming algorithms" in the first paragraph is a bit confusing. Genetic programming (GP) is the name of a different field, related to genetic algorithms (GA) but separate.

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

Good luck on the thesis!

Ray, thank you for correcting me. I meant GA not GP. (I didn't know the difference actually, been working on this just for a week). Thanks! :)

You might also check the No Free Lunch Theorem and Colevolutionary Free Lunches papers by Wolpert and Macready. Here's a quick wikipedia link: http://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization

I am myself considering using ga for solving a NP-complete problem that came up in work. It will be interesting to see how your work progresses. Good luck!

interesting! I would like to read more on your work and would wait for the VI editing mode cheat sheet too.

Good luck for the thesis.

Slavomir, never heard of those papers. It will be a good reading. Thanks :)

Ankush, next post is going to be on that! Give me a few more days :)

Very interesting, would that be possible to check when the internet for example run out of capacity? Or something like that.. ?!

Seems you have a nice readers list established already, WTG Peter :D

It's interesting you want to use a genetic algorithm for a spatial positioning task. I was wondering how you plan to encode the task domain into the genome?

Ruslan, :D

Okke, it's pretty tricy but I want to do it using genetic algorithms. I have been researching this stuff only for a week and I still have 6.5 months to figure it all out :)

One of the ways I could solve it is by discretize the problem, create a triangular mesh and let the particles settle at node points.
Other way I could think of using real values to represent genes.

I'll post results to my blog later.

Hi, when beginning to work with GA, you should be aware that there are many techniques of all the stages of GA: selection, mutation, crossover, survival.

Elitist selection (selecting the fittest, eliminating the weakest) is not very popular, because it's easy to throw away some generally good chromosomes (leading to good ones) and fall into local maximums instead. Usually stochastic methods are preferred. For example, there is tournament selection. You select a number of individuals randomly and then select one, two or more best ones. There is also a roulette-wheel selection where you give each individual a probability of being selected according to its fitness. Each individual is given a probability of being selected based on its fitness, so that the fittest individuals are more likely to be selected but still not throwing away the weakest individuals.

There are also more ways to perform mutation. Bitflip is only of them. You may do a uniform mutation. You flip each bit with a probability of 1/[b] where [b] is the number of bits in chromosome.

Crossover also may take many forms: 1point, 2point, uniform.

Here is a good collection of introductory papers on evolutionary computation:

Evolutionary Computation 1
Basic Algorithms and Operators
Edited by Thomas Back, David B Fogel and Zbigniew Michalewicz

Hey, Jazeps. Thanks for your great comment. Really informative. I didn't know some of this stuff. I'll see if I can get the book :)

Hello again. Do not pay attention to my comment much. Actually I'm just doing my first steps in Evolutionary Computation and today I found out that some things are not really the way I told you above. Because the book is partly out-of-date and because I had not read it properly.

It's true that there a lots of variations on how you carry out the stages of GA, but don't pay attention to what i said about next generation selection. My advisor told me today that stochastic approach is not used there today much.

Just confused little bit. It's been long time since i studied physics last time. I am going to read physics once again.
Ooooops!.......

Hello, I am wondering if you have any programming ideas for predicting the landing point of a roulette ball.

The start point would likely be very basic. Whether the wheel is moving clockwise or counter-clockwise. The velocity of the wheel. The initial velocity of the ball thus calculating the acceleration (-). The number where the ball was launched from. The fall point - where the ball leaves the rim and begins to enter the bowl.

From this point, a scatter will occur. Sometimes the ball will bounce for a while, sometimes it will roll a full revolution before coming to rest in a pocket. This is what I would presume would entail a chaos-type program.

If one were to draw a picture of various ball stopping points - pockets - relative to the start point, fall point, clockwise - and perhaps counter-clockwise - velocities of the wheel, along with the initial velocity of the ball and the ultimate resting place relative to the start point - and the number at that point, one could have a good idea of where to predict a ball would land.

A program that would work with perhaps one mechanical button - two if necessary - to enter criteria observed to calculate time for one - perhaps 1/4 of one - revolution of the wheel for the wheel velocity input. The next click or two to time the velocity/deceleration of the ball calculated as time for one revolution - perhaps two - and so on could be devised and applied to a small unit. An enhanced device to verbally relay the "answer" in some form such as same area, 1/2 way around the wheel, 1/4 way around the wheel etc would needed OR a tapping/vibrating signal for such.

Any suggestions?

Thanks.

can any one help me please for this
i need a formula if you do it for 750236938
the answer will be 388857077
A +,-,/,* ? = b

it shuold be one formula for all the next :

a) 750236938
b) 388857077

a) 1889225097
b) 1258389622

a) 947774784
b) 65481919

a) -1262787430
b) 1893618329

a) -526728927
b) 620754720

I am new to this field.. I have read the theoretical basics but problem lies in the implementation. Currently I am working on a project the involves a GA to be implemented on global grids for scheduling workflow applications.
If someone is working in the same area.. please guide me through a bit..

hi dear ,
could u please give me your source codes which u use to solve this problem , i'm searching lot about that but i've never found anything codes , im a programmer , i used to learn c# too ,thanks

Great post. I have done some work on GAs, but in the field of finding optimal paths in telecoms networks.

See this post for further details, which I am in the process of updating:

http://www.technical-recipes.com/2011/a-genetic-algorithm-based-routing-optimization-tool/

### Leave a new comment

(Your twitter handle, if you have one.)

Type the word "cdrom_37": (just to make sure you're a human)

Please preview the comment before submitting to make sure it's OK.