Come risolvere equazioni lineari utilizzando un algoritmo genetico?

Question

Voglio risolvere un sistema di equazioni lineari n contenenti n variabili utilizzando un algoritmo genetico.

Ho difficoltà nel definire l'operazione di crossover come la soluzione può essere costituito da valori a virgola mobile. Come procedo? Sembra possibile, ma questo è il mio primo incontro con gli algoritmi genetici.

Supponiamo che dobbiamo risolvere

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

La risposta sarebbe x = 1/2 e y = 1/4.

Come possiamo modellare il problema?

Aggiorna : vedere se si poteva decifrare nulla dalla carta http://www.masaumnet.com/archives/mjbas/volume1/issue2/mjbas010205.pdf .

Answer 1

Una via è quella di scegliere il proprio rappresentazione in virgola mobile, che si libera a molto con i valori che si desidera. Naturalmente, che ti fa responsabile per l'attuazione operazioni aritmetiche. Forse si potrebbe trovare una libreria bignum si potrebbe alterare.

Si potrebbe anche scomporre punti Piattaforma galleggiante-native che utilizzano ad esempio frexp durante la fase di crossover, poi ricombinare durante l'abbattimento.

Answer 2

Il cromosoma potrebbe essere i numeri in virgola mobile (n doppie), oppure si può reinterpretare come stringhe di bit utilizzando un'unione:

const int n = 100;

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

... quindi è possibile utilizzare i valori doppi per l'interpretazione del valore della soluzione / fitness, ei bit per la riproduzione / Crossover / mutazione.

In bocca al lupo!

Answer 3

semplicemente non. Ci sono un sacco di diversi metodi che è possibile applicare per risolvere i sistemi lineari. Ma "algoritmi genetici" non è qualcosa che viene in mente. Devi usare algoritmi genetici per risolvere i problemi combinatorical (raccogliendo un elemento da un finito set).

Di solito risolvere sistemi lineari che utilizzano fattorizzazioni (QR, LU) o algoritmi iterativi (Gauss-Seidel, CG, ...)

Answer 4

Sarà necessario pensare di utilizzare un algoritmo genetico vero e proprio codice, piuttosto che il codice binario algoritmo genetico come suggerito nel documento che avete denominato. In realtà, se si utilizza un codice binario algoritmo genetico, allora non sarà in grado di trovare la soluzione alle equazioni se la 'x', 'y' può assumere valori negativi.

Quindi è necessario utilizzare un algoritmo genetico vero e proprio codice. O è possibile codificare l'intero algoritmo genetico da soli, oppure si può semplicemente utilizzare un buon codice RGA esistente per risolvere il problema. Sarà sufficiente per personalizzare la funzione di fitness per il vostro bisogno. Qui è possibile utilizzare quello che viene suggerito nel documento. E 'stato abbastanza facile!

Si può considerare usando l'implementazione RGA da http://www.iitk.ac .in / kangal / codes.shtml .