Comment résoudre des équations linéaires en utilisant un algorithme génétique?

Question

Je veux résoudre un système d'équations linéaires n contenant n variables en utilisant un algorithme génétique.

J'éprouve des difficultés dans la définition de l'opération de croisement en tant que solution peut consister en valeurs à virgule flottante. Comment dois-je procéder? Il semble possible, mais ceci est ma première rencontre avec des algorithmes génétiques.

Supposons que nous ayons à résoudre

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

La réponse est x = y = 1/2 et 1/4.

Comment pouvons-nous modélisons le problème?

Mise à jour : voir si vous pouvez déchiffrer quoi que ce soit du papier http://www.masaumnet.com/archives/mjbas/volume1/issue2/mjbas010205.pdf .

Answer 1

Une voie est de choisir votre propre représentation à virgule flottante, ce qui vous évite de bien avec les valeurs que vous voulez. Bien sûr, cela vous rend responsable de la mise en œuvre des opérations arithmétiques. Peut-être que vous pourriez trouver une bibliothèque bignum vous pouvez modifier.

Vous pouvez également décomposer les points Floating plate-forme native en utilisant par exemple frexp lors de l'étape de croisement, recombiner puis pendant l'abattage.

Answer 2

Votre chromosome pourrait être les nombres à virgule flottante n (doubles), ou vous pouvez les réinterpréter sous forme de chaînes de bits en utilisant une union:

const int n = 100;

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

... alors vous pouvez utiliser les valeurs doubles pour l'interprétation de la valeur solution / remise en forme, et les bits pour la reproduction / croisement / mutation.

Bonne chance!

Answer 3

Vous ne tout simplement pas. Il y a beaucoup de différentes méthodes que vous pouvez appliquer pour résoudre des systèmes linéaires. Mais « algorithmes génétiques » ne sont pas quelque chose qui vient à l'esprit. Vous souhaitez utiliser des algorithmes génétiques pour résoudre les problèmes combinatorical (choisir un élément d'un fini set).

Vous résolvez généralement des systèmes linéaires à l'aide de factorisation (QR, LU) ou des algorithmes itératifs (Gauß-Seidel, CG, ...)

Answer 4

Vous devrez penser à utiliser un véritable algorithme génétique codé plutôt que l'algorithme génétique codé binaire tel que suggéré dans le document que vous avez parlé. En fait, si vous utilisez un algorithme génétique codé binaire alors vous ne serez pas en mesure de trouver la solution aux équations si votre « x », « y » peut prendre des valeurs négatives.

Par conséquent, vous devez utiliser un algorithme génétique réel codé. Soit vous pouvez coder l'algorithme génétique tout vous-même, ou vous pouvez simplement utiliser un bon code RGA existant pour résoudre votre problème. Vous aurez juste à personnaliser la fonction de remise en forme pour votre besoin. Ici, vous pouvez utiliser celui qui est suggéré dans le document. Il était assez facile!

Vous pouvez envisager d'utiliser la mise en œuvre de RGA http://www.iitk.ac .in / kangal / codes.shtml .