charles darvin - natural selection

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:

dipole system

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:

operation of the genetic algorithm programming

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

antox Permalink
November 24, 2007, 14:01

Gut! Viel Spass!

November 24, 2007, 14:03

Care to post your fitness function?

November 24, 2007, 19:34

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! :)

November 24, 2007, 19:56

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!

November 24, 2007, 20:50

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! :)

Slavomir Kaslev Permalink
November 25, 2007, 00:06

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!

November 25, 2007, 06:20

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.

November 25, 2007, 09:04

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 :)

November 26, 2007, 05:41

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 Peteris :D

November 26, 2007, 14:35

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?

November 27, 2007, 03:23

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.

December 06, 2007, 02:44

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

December 06, 2007, 04:13

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 :)

Jazeps Permalink
December 06, 2007, 18:21

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.

July 29, 2008, 13:17

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

scott Permalink
June 12, 2009, 02:02

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.

elkhateib Permalink
March 29, 2011, 15:32

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

September 26, 2011, 21:09

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..

keivan Permalink
October 14, 2011, 10:06

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

November 30, 2011, 14:14

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/

May 28, 2014, 10:52

Ok is so nice to know that and thanks

June 01, 2014, 11:34

Ok thanks that might be so special help

June 02, 2014, 13:37

Really nice place and might help

June 04, 2014, 11:33

interesting! I would like to read more

June 05, 2014, 10:01

Ok is nice to read that

June 06, 2014, 07:33

maybe that will be a solution

June 07, 2014, 10:32

Ok is great

June 11, 2014, 06:22

Is so magic place and try that

June 13, 2014, 05:26

Maybe that will help

faheen Permalink
June 22, 2014, 04:43

Ramadan Wallpaper
Ramadan Wallpaper HD Download
Ramadan Wallpaper 2014
Ramadan Wallpaper 2014 Download
Ramadan Wallpaper 2014 HD Images
Ramadan Wallpaper 2014 Images
Ramadan Wallpaper quotes
Ramadan wallpaper greetings
Ramadan wallpaper 2014 greetings
Ramadan Wallpaper 2014 quotes
Ramadan Kareem 2014 images
Ramadan Kareem Mubarak Images
Ramadan Kareem Mubarak 2014 images
Ramadan Screen Saver 2014 download
Ramadan Mubarak images
Ramadan images 2014
Ramadan Mubarak greetings
Wish you happy Ramadan 2014
Happy Ramadan Wallpaper 2014
Ramadan wallpaper 2014
Wish you happy Ramadan 2014
ramadan Hd wallpaper 2014
Wish you happy Ramadan wallpaper 2014
Ramadan 2014 images
Ramadan 2014 pictures
wish you happy Ramadan 2014 images
Wish you happy Ramadan 2014 pictures
Happy ramadan 2014 wallpaper
Ramadan Kareem 2014 Wallpaper
Ramadan Mubarak 2014 wallpaper
Wallpaper Ramadan 2014
Ramadan HD wallpaper
Ramadan 2014 HD wallpaper
wish you Ramadan 2014 HD wallpaper
Happy Ramadan HD wallpaper
Happy Ramadan 2014 HD wallpaper
Wish you Ramadan HD wallpaper Download 2014
Ramadan HD wallpaper Download 2014
Ramadan HD wallpaper 2014 Download
Ramadan HD wallpaper 1080p
Ramadan 2014 HD wallpaper 1080p
Best Ramadan 2014 HD wallpaper
Top 10 Ramadan 2014 HD wallpaper
Best Collections Of Ramadan 2014 HD wallpaper
Ramadan 2014 HD wallpaper For Android
Ramadan 2014 best Screensaver download
Ramadan 2014 Screensaver download
screensaver download for mobile Ramadan 2014
Ramadan 2014 HD Screensaver Download
Ramadan 2014 download best screen saver
Screensaver for 2014 ramadan
Ramadan mubarak screensaver download
Ramadan mubarak 2014 best screen saver
Ramadan Kareem Mubarak 2014 best screen saver
Ramadan mubarak 2014 best screen saver
screen saver 2014 download free for android
Ramadan Kareem Mubarak Greetings 2014
Best Collections of Ramadan 2014 Greetings
Best Collections of Ramadan 2014 Greetings
Top Collections of Ramadan 2014 Greetings
Ramadan 2014 Greetings
Ramadan 2014 Greetings Free
Ramadan 2014 Greetings Kareem best
Best Collections of Ramadan 2014 Kareem Greetings
Best Collections of Ramadan 2014 Kareem Greetings
Best Collections of Ramadan 2014 kareem greetings
Top Ramadan 2014 wallpapers
Top Ramadan 2014 pictures
Top ramadan 2014 pictures for pc
Top ramadan 2014 Wallpaper for Android
Ramadan 2014 best softwares
Ramadan 2014 Best Images of Desktop
Ramadan 2014 best pictures for desktop
ramadan 2014 collection of Hd wallpaper
Ramadan 2014 Best collections
Ramadan 2014 top Hd wallpaper
Ramadan 2014 in uk
When Ramadan 2014 in Uk
ramadan 2014 in United Kingdom
When Ramadan 2014 in United States
When ramadan 2014 in America
Ramadan date in uk
Ramadan date in uk
Ramadan facts in united kingdom
Ramadan date in France
Ramadan 2014 in france
Ramadan 2014 date in france
Ramadan 2014 date in Frace country
Happy Ramadan 2014 best wallpaper
Ramadan Wallpaper best collections
Ramadan Kareem Wallpaper collections
wish you happy Ramadan wallpaper 2014
happy Ramadan wallpaper 2014
wish you happy Ramadan Hd wallpaper
Happy Ramadan 2014 HD wallpaper
Hd Ramadan wallpaper 2014
Wallpaper 2014 Hd in Ramadan
Ramadan wallpaper 2014 for Desktop Background
Best Islamic Ramadan wallpaper 2014
Wallpaper 2014 for facebook Cover
Best Wallpaper 2014 Download
Ramadan HD wallpaper 2014 Download
When ramadan in India 2014
Ramadan in India 2014
Ramadan in India 2014
Ramadan Kareem Greetings
Ramadan kareem Mubarak Greetings
Ramadan kareeem 2014 Greetings
Ramadan 2014 kareem Greetings
Ramadan 2014 kareem greetings
Ramadan Kareem Mubarak 2014
Ramadan kareem Mubarak 2014
Ramadan kareem Mubarak 2014
Ramadan Kareem greetings 2014
Ramadan Kareem greetings 2014
Ramadan Kareem greetings 2014
Ramadan Kareem greetings 2014
Ramadan Kareem greetings 2014
Ramadan Mubarak Greetings 2014
Ramadan Mubarak Greetings 2014
Ramadan Mubarak Greetings 2014
Ramadan Mubarak Greetings 2014
Ramadan Mubarak Greetings 2014
Ramadan Mubarak Greetings 2014
Ramadan Mubarak Greetings 2014
Ramadan Mubarak Greetings 2014
Ramadan Mubarak Greetings 2014
Ramadan Mubarak Greetings 2014
Ramadan Mubarak Greetings 2014
Inspirational pictures of ramadan 2014
Inspirational pictures of ramadan 2014
Inspirational pictures of ramadan 2014
Inspirational pictures of ramadan 2014
Inspirational pictures of ramadan 2014
Inspirational pictures of ramadan 2014
Inspirational pictures of ramadan 2014
Inspirational pictures of ramadan 2014
Inspirational pictures of ramadan 2014
Inspirational pictures of ramadan 2014
Ramadan 2014 Wallpaper and Mubarak pics
Ramadan 2014 Wallpaper and Mubarak pics
Ramadan 2014 Wallpaper and Mubarak pics
Ramadan 2014 Wallpaper and Mubarak pics
Ramadan 2014 Wallpaper and Mubarak pics
Ramadan 2014 Wallpaper and Mubarak pics
Ramadan 2014 Wallpaper and Mubarak pics
Ramadan 2014 Wallpaper and Mubarak pics
Ramadan 2014 Wallpaper and Mubarak pics
Ramadan 2014 Wallpaper and Mubarak pics
Ramadan 2014 Wallpaper and Mubarak pics
Awesome Post Ramadan Wallpaper Ramadan Wallpaper HD Download Ramadan Wallpaper 2014 Ramadan Wallpaper 2014 Download Ramadan Wallpaper 2014 HD Images Ramadan Wallpaper 2014 Images Ramadan Wallpaper quotes Ramadan wallpaper greetings Ramadan wallpaper 2014 greetings Ramadan Wallpaper 2014 quotes Ramadan Kareem 2014 images Ramadan Kareem Mubarak Images Ramadan Kareem Mubarak 2014 images Ramadan Screen Saver 2014 download Ramadan Mubarak images Ramadan images 2014 Ramadan Mubarak greetings Wish you happy Ramadan 2014 Happy Ramadan Wallpaper 2014 Ramadan wallpaper 2014 Wish you happy Ramadan 2014 ramadan Hd wallpaper 2014 Wish you happy Ramadan wallpaper 2014 Ramadan 2014 images Ramadan 2014 pictures wish you happy Ramadan 2014 images Wish you happy Ramadan 2014 pictures Happy ramadan 2014 wallpaper Ramadan Kareem 2014 Wallpaper Ramadan Mubarak 2014 wallpaper Wallpaper Ramadan 2014 Ramadan HD wallpaper Ramadan 2014 HD wallpaper wish you Ramadan 2014 HD wallpaper Happy Ramadan HD wallpaper Happy Ramadan 2014 HD wallpaper Wish you Ramadan HD wallpaper Download 2014 Ramadan HD wallpaper Download 2014 Ramadan HD wallpaper 2014 Download Ramadan HD wallpaper 1080p Ramadan 2014 HD wallpaper 1080p Best Ramadan 2014 HD wallpaper Top 10 Ramadan 2014 HD wallpaper Best Collections Of Ramadan 2014 HD wallpaper Ramadan 2014 HD wallpaper For Android Ramadan 2014 best Screensaver download Ramadan 2014 Screensaver download screensaver download for mobile Ramadan 2014 Ramadan 2014 HD Screensaver Download Ramadan 2014 download best screen saver Screensaver for 2014 ramadan Ramadan mubarak screensaver download Ramadan mubarak 2014 best screen saver Ramadan Kareem Mubarak 2014 best screen saver Ramadan mubarak 2014 best screen saver screen saver 2014 download free for android Ramadan Kareem Mubarak Greetings 2014 Best Collections of Ramadan 2014 Greetings Best Collections of Ramadan 2014 Greetings Top Collections of Ramadan 2014 Greetings Ramadan 2014 Greetings Ramadan 2014 Greetings Free Ramadan 2014 Greetings Kareem best Best Collections of Ramadan 2014 Kareem Greetings Best Collections of Ramadan 2014 Kareem Greetings Best Collections of Ramadan 2014 kareem greetings Top Ramadan 2014 wallpapers Top Ramadan 2014 pictures Top ramadan 2014 pictures for pc Top ramadan 2014 Wallpaper for Android Ramadan 2014 best softwares Ramadan 2014 Best Images of Desktop Ramadan 2014 best pictures for desktop ramadan 2014 collection of Hd wallpaper Ramadan 2014 Best collections Ramadan 2014 top Hd wallpaper Ramadan 2014 in uk When Ramadan 2014 in Uk ramadan 2014 in United Kingdom When Ramadan 2014 in United States When ramadan 2014 in America Ramadan date in uk Ramadan date in uk Ramadan facts in united kingdom Ramadan date in France Ramadan 2014 in france Ramadan 2014 date in france Ramadan 2014 date in Frace country Happy Ramadan 2014 best wallpaper Ramadan Wallpaper best collections Ramadan Kareem Wallpaper collections wish you happy Ramadan wallpaper 2014 happy Ramadan wallpaper 2014 wish you happy Ramadan Hd wallpaper Happy Ramadan 2014 HD wallpaper Hd Ramadan wallpaper 2014 Wallpaper 2014 Hd in Ramadan Ramadan wallpaper 2014 for Desktop Background Best Islamic Ramadan wallpaper 2014 Wallpaper 2014 for facebook Cover Best Wallpaper 2014 Download Ramadan HD wallpaper 2014 Download When ramadan in India 2014 Ramadan in India 2014 Ramadan in India 2014 Ramadan Kareem Greetings Ramadan kareem Mubarak Greetings Ramadan kareeem 2014 Greetings Ramadan 2014 kareem Greetings Ramadan 2014 kareem greetings Ramadan Kareem Mubarak 2014 Ramadan kareem Mubarak 2014 Ramadan kareem Mubarak 2014 Ramadan Kareem greetings 2014 Ramadan Kareem greetings 2014 Ramadan Kareem greetings 2014 Ramadan Kareem greetings 2014 Ramadan Kareem greetings 2014 Ramadan Mubarak Greetings 2014 Ramadan Mubarak Greetings 2014 Ramadan Mubarak Greetings 2014 Ramadan Mubarak Greetings 2014 Ramadan Mubarak Greetings 2014 Ramadan Mubarak Greetings 2014 Ramadan Mubarak Greetings 2014 Ramadan Mubarak Greetings 2014 Ramadan Mubarak Greetings 2014 Ramadan Mubarak Greetings 2014 Ramadan Mubarak Greetings 2014 Inspirational pictures of ramadan 2014 Inspirational pictures of ramadan 2014 Inspirational pictures of ramadan 2014 Inspirational pictures of ramadan 2014 Inspirational pictures of ramadan 2014 Inspirational pictures of ramadan 2014 Inspirational pictures of ramadan 2014 Inspirational pictures of ramadan 2014 Inspirational pictures of ramadan 2014 Inspirational pictures of ramadan 2014 Ramadan 2014 Wallpaper and Mubarak pics Ramadan 2014 Wallpaper and Mubarak pics Ramadan 2014 Wallpaper and Mubarak pics Ramadan 2014 Wallpaper and Mubarak pics Ramadan 2014 Wallpaper and Mubarak pics Ramadan 2014 Wallpaper and Mubarak pics Ramadan 2014 Wallpaper and Mubarak pics Ramadan 2014 Wallpaper and Mubarak pics Ramadan 2014 Wallpaper and Mubarak pics Ramadan 2014 Wallpaper and Mubarak pics Ramadan 2014 Wallpaper and Mubarak pics oHack Anna University Paper Valuation Anna University result 2014 Thanks for sharing

June 23, 2014, 07:32

That is so amazing and look for help

June 30, 2014, 05:59

It will be so special and helpful

July 02, 2014, 05:48

Totally think is nice plan to work

July 04, 2014, 05:19

That is nice work

July 05, 2014, 11:40

Ok that seems so nice

sonya Permalink
July 13, 2014, 09:39

I have searching for such post from very long time. These type of content is very rare to be found. Thanks for it. Means while you can browse for
درب اتوماتیک - کرکره برقی - درب اتوماتیک شیشه ای
- دوربین مدار بسته
.

Param Khiva Permalink
July 16, 2014, 17:16

Thank You For Sharing This Excellent Post,
Friendship Day 2014 Quotes
Happy Friendship Day Images
Thank You For Sharing.

Leave a new comment

(why do I need your e-mail?)

(Your twitter name, if you have one. (I'm @pkrumins, btw.))

Type the first letter of your name: (just to make sure you're a human)

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

Advertisements