how to solve linear equations using genetic algorithm

Question

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

i am having difficulty in defining the crossover operation as the solution may consist of floating point values. how do i proceed. seems possible but this is my first encounter with genetic algorithms so your help would be great.

suppose we have to solve x + 2y = 1 2x + 8y = 3

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

how do we model the problem.

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

Answer 1

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

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 4

Hi! You will need to think about using a Real coded GA rather than the binary coded GA as suggested in the paper you have referred to. Infact, if you use a binary coded GA 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 GA. Either you can code the whole GA 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