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.