Strange SIGSEV on Genetic Algorithm

[edoz90]

Hi all!!
I made this program in C++ that should, by a genetic algorithm, build a word identical to the initial one improving itself recursively.

The code is:

main.cpp

    #include <stdio.h>
    #include <cstdlib>
    #include "Genetic.h"

    using namespace std;

    int main(int argc, char** argv) {
        srand(time(NULL));
        string word = "hello";   
       
        Genetic ga(word);
        std::vector<Genetic::Gene> result(ga.execute());
        cout << result[0].word << endl;

        return 0;
    }

Genetic.h

    #ifndef GENETIC_H
    #define   GENETIC_H

    #include <string>
    #include <stdlib.h>
    #include <vector>
    #include <math.h>
    #include <algorithm>
    #include <iomanip>
    #include <iostream>

    using namespace std;

    class Genetic {
    public:
        Genetic(std::string);
        Genetic(const Genetic& orig);
        virtual ~Genetic();

        struct Gene {
            std::string word = "";
            double rate = 0.0;
            int *code;
        };
        std::vector<Gene> execute();

    private:
        static const int POPULATION_SIZE = 20;
        static const int MUTATION_RATE = 10;
        static const int MUTATION_SIZE = 100;
        static const int SURVIVORS = 10;
        static const int SUCCESS_RATE = 1;
        const std::string LETTERS = "abcdefghijklmnopqrstuvwxyz ";
        static const int CHILDREN = 2;
        std::string text;
        int lenght;
        int population;
        double max_rate;
        double average_suc_rate;
        bool passed;
        int generation;
        std::vector<Gene> popGenes;
        std::vector<Gene> best;
       
        double check_success(std::string);
        int *mutate(int*);
        int *cross(int *, int *);
        void firstPopulation();
        int *genCode();
        Gene generate(int*, bool);
        std::vector<Gene> evolution(std::vector<Gene>);
        std::vector<Gene> populate();
        bool in_array(Gene);
        static bool sortByRate (const Gene &, const Gene &);
    };

    #endif   /* GENETIC_H */ 

The problem is: when running with gdb it gave me this

    warning: Could not load shared library symbols for linux-vdso.so.1.
    Do you need "set solib-search-path" or "set sysroot"?
    CREATA LA PRIMA POPOLAZIONE
    PARTE L'EVOLUZIONE
    TROVATO BEST: fzlrq
    TROVATO BEST: hglhe

    Program received signal SIGSEGV, Segmentation fault.
    0x000000000040720e in Genetic::Gene::Gene (this=0x7fffff7ff030) at Genetic.h:20
    20       struct Gene { 

The line corresponds to the struct declaration.
How can I solve this problem??

P.S. every 1000 executions it runs well.

[edoz90]

The class code is:

Genetic.cpp

    #include "Genetic.h"

    Genetic::Genetic(std::string s) {
        this->text = s;
        this->lenght = s.length();
        this->population = 0;
        this->max_rate = 0;
        this->average_suc_rate = 0;
        this->passed = false;
        this->generation = 0;
        this->popGenes.resize(Genetic::POPULATION_SIZE);
        this->best.clear();
    }

    Genetic::Genetic(const Genetic& orig) {
    }

    Genetic::~Genetic() {
    }

    // imposta la popolazione e avvia l'evoluzione
    std::vector<Genetic::Gene> Genetic::execute() {
        // creo la prima popolazioni di geni
        this->firstPopulation();
        cout << "PARTE L'EVOLUZIONE" << endl;
        return this->evolution(this->popGenes);
    }

    // avvia il processo di evoluzione
    std::vector<Genetic::Gene> Genetic::evolution(std::vector<Gene> genes_data) {
        if (genes_data[0].rate >= Genetic::SUCCESS_RATE) {
            cout << "PAROLA TROVATA DOPO: " << this->population << endl;
            return genes_data;
        } else {
            if (this->best.size() > this->popGenes.size()) {
                for (int i = this->best.size() - 1; i < this->popGenes.size(); i++) {
                    this->best.pop_back();
                }
            }
            std::copy(this->best.begin(), this->best.end(), this->popGenes.begin());
            return this->evolution(this->populate());
        }
    }

    std::vector<Genetic::Gene> Genetic::populate() {
        this->generation++;
        //cout << "INIZIO DELLA GENERAZIONE: " << this->generation << endl;
        Gene son1, son2;
        bool mutation = false;
        for (int k = 0; k < Genetic::CHILDREN; k++) {
            for (int i = 0; i < this->popGenes.size(); i++) {
                if (this->generation % Genetic::MUTATION_SIZE == 0) {
                    mutation = true;
                }
                if (this->popGenes[i].rate >= this->max_rate) {
                    son1 = this->generate(this->popGenes[i].code, true);
                } else {
                    if (this->popGenes[i].code != this->popGenes[i + 1].code && i < this->popGenes.size() - 1)
                        son1 = this->generate(this->cross(this->popGenes[i].code, this->popGenes[i + 1].code), mutation);
                    else if (this->popGenes[i].code != this->popGenes[i + 2].code && i < this->popGenes.size() - 2)
                        son1 = this->generate(this->cross(this->popGenes[i].code, this->popGenes[i + 2].code), mutation);
                }

                if (son1.rate > this->max_rate && !(this->in_array(son1))) {
                    cout << "TROVATO BEST: " << son1.word << endl;
                    this->max_rate = son1.rate;
                    this->best.push_back(son1);
                }
            }
        }
        std::sort(this->best.begin(), this->best.end(), this->sortByRate);
        std::sort(this->popGenes.begin(), this->popGenes.end(), this->sortByRate);
        return this->popGenes;
    }

    void Genetic::firstPopulation() {
        //cout << "CREO LA PRIMA POPOLAZIONE" << endl;
        Gene new_ind;
        for (int i = 0; i < this->popGenes.size(); i++) {
            this->population++;
            bool mutation = true; // è la prima popolazione quindi muto tutti
            // completo la generazione del Gene
            new_ind = this->generate(this->genCode(), mutation);
            this->popGenes[i].code = new_ind.code;
            this->popGenes[i].rate = new_ind.rate;
            this->popGenes[i].word = new_ind.word;
            //cout << setw(2) << i << setw(this->lenght + 1) << this->popGenes[i].rate
            //<< setw(this->lenght + 1) << this->popGenes[i].word << endl;
        }
        cout << "CREATA LA PRIMA POPOLAZIONE" << endl;
    }

    // crea un Gene con una parola random

    Genetic::Gene Genetic::generate(int *gene_code, bool mutation) {
        if (mutation) {
            // applico una mutazione al gene
            gene_code = this->mutate(gene_code);
        }
        std::string new_word = "";
        for (int i = 0; i < this->lenght; i++) {
            // prendo la lettera di posizione gene_code[i]
            std::string letter = this->LETTERS.substr(gene_code[i], 1);
            // creo la parola
            new_word.append(letter);
        }

        Gene new_ind;
        new_ind.code = gene_code;
        new_ind.word = new_word;
        // controllo se la parola creata è quella giusta
        new_ind.rate = this->check_success(new_word);
        return new_ind;
    }

    // genera un array di numeri da 0 a lenght

    int *Genetic::genCode() {
        // il numero indica la lettera dell'alfabeto
        int *code = (int*) malloc(sizeof (int) * this->lenght);
        for (int i = 0; i < this->lenght; i++) {
            // creo un numero da zero alla lunghezza della parola da trovare -1
            code[i] = rand() % Genetic::LETTERS.size();
        }
        return code;
    }

    // funzione per applicare una mutazione ad un gene

    int *Genetic::mutate(int *code) {
        // quante lettere devo mutare
        int mutate_letter_num = floor(Genetic::MUTATION_RATE * this->lenght / 100);
        int index;
        // creo un nuovo codice
        for (int i = 0; i < mutate_letter_num; i++) {
            // l'indirizzo della lettera da mutare
            index = rand() % this->lenght;
            // eseguo la mutazione
            code[index] = rand() % this->LETTERS.size();
        }
        return code;
    }

    // funzione che esegue il crossover su due Geni

    int *Genetic::cross(int *g1, int *g2) {
        int *code = (int*) malloc(sizeof (int) * this->lenght);
        for (int i = 0; i < this->lenght; i++) {
            int r = rand() % 2;
            if (r > 0) {
                code[i] = g1[i];
            } else {
                code[i] = g2[i];
            }
        }
        return code;
    }

    // controlla la fitness della stringa

    double Genetic::check_success(std::string word) {
        double rate = 0.0;
        //cout << word << endl;
        // controllo carattere per carattere se ci sono lettere uguali
        for (int i = 0; i < this->lenght; i++) {
            if (this->text.at(i) == word.at(i))
                rate++;
        }
        // calcolo la fitness
        return (rate / this->lenght);
    }


    // funzione per controllare se un Gene è nel vettore best
    bool Genetic::in_array(Genetic::Gene needle) {
        int max = this->best.size();
        if (max == 0) return false;
        // se ha code, rate e word uguali allora sono uguali
        for (int i = 0; i < max; i++)
            if (this->best[i].code == needle.code && this->best[i].rate == needle.rate && this->best[i].word == needle.word)
                return true;
        return false;
    }

    // funzione di ordinamento dei geni per rate
    bool Genetic::sortByRate(const Genetic::Gene &lhs, const Genetic::Gene &rhs) {
        return lhs.rate > rhs.rate;
    }

[ne555]

I've got an stack overflow in 'Genetic::evolution()', you may change the recursion to iteration.
However, the problem is that the 'rate' is not improving.

Check out your mutation factor and your crossover. It seems to be converging (really quickly) to a local maximum.
Also, consider increasing the population size, and to decrease the success rate


By the way

        struct Gene {
            std::string word = "";
            double rate = 0.0;
            int *code;
        };

that will give you trouble. The copy constructor of 'Gene' would do a shallow copy and you would have a double delete (well you would if you do deallocate the memory)
If the size would be constant, consider an array, otherwise std::vector

//Genetic::populate
if (this->popGenes[i].code != this->popGenes[i + 1].code && i < this->popGenes.size() - 1)
   son1 = this->generate(this->cross(this->popGenes[i].code, this->popGenes[i + 1].code), mutation);
else if (this->popGenes[i].code != this->popGenes[i + 2].code && i < this->popGenes.size() - 2)
   son1 = this->generate(this->cross(this->popGenes[i].code, this->popGenes[i + 2].code), mutation);

those test are wrong and produce an invalid read
Note that you dereference the value and later ask if the index could be valid.
if (i < this->popGenes.size() - 1 and this->popGenes[i].code != this->popGenes[i + 1].code )

[edoz90]

Thank for the reply!!

I think that I've not understood what you said....
The problem is the recursion that cause an allocation/deallocation of Gene?

Sorry but I've been using C++ since a week.


Last version:

https://github.com/edoz90/DecoderGA.git

Algorithm updated -> same problem

[ne555]

I'll try to make myself clearer.
You've got several independent problems:
- the recursion in 'evolution()' is too deep, change it to iteration.
- you are leaking memory, as you never deallocate the 'code' arrays
- your Gene copy constructor makes a shallow copy

I took another look at your code and think that you've got a bad approach.
- your fitness function simply counts the correct letter in the correct position, so the function have an step shape. You may use the distance of the letters, so 'helln' has better rate than 'hella'
- your best individuals do not breed, they just mutate. Again, taking into account the fitness function, you've got a lot of 'best' individuals, that do not breed. You end searching with mutations.
- individuals reproduce with other of near rate. Also, 'better' individuals do not reproduce more. I think that that generates a high convergence, to a local maximum.
- your population is too small and the constraint too big. 20 individuals looking for 1 solution of 14 million


An example:
Let's group the individuals by the number of correct (value and position) letters. Because of your 'in order' reproduction, only individuals of the same group 'cross'
Suppose that in the initialization there were three groups:
- two correct
- one correct
- zero correct
All in the group 'two' share the best rate. They do not reproduce, so they need to mutate in order to advance.
All in the 'zero' group are useless. They may never improve another rate, so may only advance with mutations in the sons.
In the 'one' group is the only one were reproduction matters. However, if they improve, they would pass to the 'two' group, where they would stanch

[edoz90]

Thanks for the reply and the patience! :)

I know that my algorithm is not optimal and I thank you for your advice; I did not think someone would have answered, and he was so knowledgeable about genetic algorithms.


With some fix now the code runs well and it finds the correct word.

For now I'll settle for this experiment but a short, making use of your tips, I'll try to improve it or parallelize it with CUDA.

My second experiment is to create a basic and simple ACO algorithm for solve the same problem of the words.
I think that we'll meet here again!!


P.S. if you have any other suggestions I'd be honored

Thanks again! :D