How to solve linear equations using a genetic algorithm?

Question

I want to solve a system of n linear equations containing n variables using a genetic algorithm.

I am having difficulty in defining the crossover operation as the solution may consist of floating point values. How do I proceed? It seems possible, but this is my first encounter with genetic algorithms.

Suppose we have to solve

 x + 2y = 1
2x + 8y = 3

The answer would be x = 1/2 and y = 1/4.

How do we model the problem?

Update: see if you could decipher anything from the paper http://www.masaumnet.com/archives/mjbas/volume1/issue2/mjbas010205.pdf.

Answer 1

One route is to pick your own floating point representation, which frees you to much with values as you want. Of course, that makes you responsible for implementing arithmetic operations. Perhaps you could find a bignum library you could alter.

You could also decompose platform-native floating points using e.g. frexp during the crossover step, then recombine it during culling.

Answer 2

Your chromosome could be the n floating point numbers (doubles), or you could reinterpret them as bit strings by using a union:

const int n = 100;

union Chromosome {
  double val[n];
  unsigned char bits[n * sizeof(double)];
};

...then you can use the double values for interpretation of the solution/fitness value, and the bits for breeding/crossover/mutation.

Good luck!

Answer 3

You simply don't. There are lots of different methods you can apply to solve linear systems. But "genetic algorithms" is not something that comes to mind. You'd use genetic algorithms to solve combinatorical problems (picking one element out of a finite set).

You usually solve linear systems using factorizations (QR, LU) or iterative algorithms (Gauß-Seidel, CG, ...)

Answer 4

You will need to think about using a real coded genetic algorithm rather than the binary coded genetic algorithm as suggested in the paper you have referred to. In fact, if you use a binary coded genetic algorithm then you won't be able to find the solution to the equations if your 'x', 'y' can take negative values.

Hence you need to use a real coded genetic algorithm. Either you can code the whole genetic algorithm yourself, or you can just use a good existing RGA code to solve your problem. You will just have to customise the fitness function for your need. Here you can use the one that is suggested in the paper. It was pretty easy!

You can consider using the RGA implementation from http://www.iitk.ac.in/kangal/codes.shtml.