The problem is: when running with gdb it gave me this
1 2 3 4 5 6 7 8 9 10
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??
#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;
returnthis->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());
returnthis->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);
elseif (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);
returnthis->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) returnfalse;
// 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)
returntrue;
returnfalse;
}
// funzione di ordinamento dei geni per rate
bool Genetic::sortByRate(const Genetic::Gene &lhs, const Genetic::Gene &rhs) {
return lhs.rate > rhs.rate;
}
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
1 2 3 4 5
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
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 )
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
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