1

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.

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
Rohit Banga
  • 18,458
  • 31
  • 113
  • 191

4 Answers4

6

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!

Drew Hall
  • 28,429
  • 12
  • 61
  • 81
  • yes but the floating point representation would have to be taken into account. performing a crossover of random bits would do any good? – Rohit Banga Nov 07 '09 at 11:05
  • You'll have to try it--I suspect it would take a long time to converge but would work eventually. You could have your fitness function essentially kill off chromosomes that contained really extreme values. – Drew Hall Nov 07 '09 at 11:44
  • You can do crossover (and mutation) however you want. Just cross between floating point numbers... have mutations just randomize a float... – Inverse Nov 22 '09 at 22:10
5

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

sellibitze
  • 27,611
  • 3
  • 75
  • 95
  • right, i have chosen this as a course project for AI. i didn't have much time to decide and now i don't have much time to code. this is a related paper www.masaumnet.com/archives/mjbas/volume1/.../mjbas010205.pdf but it does not explain the details. – Rohit Banga Nov 07 '09 at 10:42
  • http://www.masaumnet.com/archives/mjbas/volume1/issue2/mjbas010205.pdf in case the above link does not work – Rohit Banga Nov 07 '09 at 10:58
  • 4
    I don’t see why *linear* equations should a priory be any less amenable to a solution via genetic algorithms than any other function type. The procedure is the same. Notice that in *all* such cases you try to *optimize* a function – in this case the difference between the real, exact solution and the one found via the GA. GA is a general schema to traverse a solution landscape, not limited to a finite set of solutions. – Konrad Rudolph Nov 07 '09 at 15:04
  • thanks for encouraging, i'll try to code it and see if i have any problem in getting the solution to converge. – Rohit Banga Nov 07 '09 at 15:11
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.

outis
  • 75,655
  • 22
  • 151
  • 221
1

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.

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131