Exemplo simples de algoritmo genetico usando o metodo de OneMax

genetico_onemax.cpp

#include <iostream>
#include <vector>
#include <stdlib.h>
#include <time.h>
/*
g++ -o onemax genetico_onemax.cpp -Wall
*/
#define TAM_GENES  10 // Quantidade de genes que terá cada individuo.
#define TAM_POP    50 // Quantos individuos terão.
#define TORNEIO    20 // Quantidade de cruzamentos.
#define GERACOES  100 // Quantidade de gerações que terá para alcançar o objetivo.
#define PROB_MUT  0.2 // Probabilidade de mutação.
#define PROB_CRUZ 0.7 // Probabilidade de cruzamento.

using namespace std;

void inicializa_populacao();
void mostrar_populacao();
int obter_pontuacao(vector<int> individuo);
void mutacao(vector<int> &individuo);
void cruzamento(int pai_1, int pai_2, vector<int> &filho);
int obter_melhor();
void run();

vector<vector<int> > populacao;

void inicializa_populacao(){
	for(int i=0; i<TAM_POP; i++){
		vector<int> individuo;
		for(int j=0; j<TAM_GENES; j++){
			int gene = rand()%2; // Gera um valor de 0 ou 1.
			individuo.push_back(gene);
		}
		populacao.push_back(individuo);
	}
}

void mostrar_populacao(){
	for(int i=0; i<TAM_POP; i++){
		cout << "individuo " << i << " [";
		for(int j=0; j<TAM_GENES; j++){
			cout << populacao[i][j] << " ";
		}
		cout << "] pontuaçao: " << obter_pontuacao(populacao[i]) << endl;
	}
}

int obter_pontuacao(vector<int> individuo){
	int soma = 0;
	for(int j=0; j<TAM_GENES; j++){ soma += individuo[j]; }
	return soma;
}

void mutacao(vector<int> &individuo){
	int gene = rand() % TAM_GENES;
	if(individuo[gene] == 0){ individuo[gene] = 1; }
	else{ individuo[gene] = 0; }
}

void cruzamento(int pai_1, int pai_2, vector<int> &filho){
	int ponto = rand()%TAM_GENES;
	for(int i=0; i<ponto; i++){ // Pega uma parte dos genes do pai 1.
		filho.push_back(populacao[pai_1][i]);
	}
	
	for(int i=ponto; i<TAM_GENES; i++){ // Pega o restante dos genes do pai 2;
				filho.push_back(populacao[pai_2][i]);
	}
}

int obter_melhor(){
	int indice_melhor = 0;
	int score_melhor  = obter_pontuacao(populacao[0]);
	
	for(int i=0; i<TAM_POP; i++){
		int score = obter_pontuacao(populacao[i]);
		if(score > score_melhor){
				indice_melhor = i;
				score_melhor  = score;
		}
	}
	return indice_melhor;
}

void run(){
	inicializa_populacao();
	cout << "População inicial:" << endl;
	mostrar_populacao();
	
	for(int i=0; i<GERACOES; i++){
		for(int j=0; j<TORNEIO; j++){
			double prob = ((double)rand() / ((double)RAND_MAX + 1));

			if(prob < PROB_CRUZ){
				int pai_1 = rand()%TAM_POP;
				int pai_2;
				do{
					pai_2 = rand()%TAM_POP;
				}while(pai_1 == pai_2);
				
				vector<int> filho;
				cruzamento(pai_1, pai_2, filho);
				prob = ((double)rand() / ((double)RAND_MAX + 1));
				
				if(prob < PROB_MUT){ mutacao(filho); }
				
				int score_pai   = obter_pontuacao(populacao[pai_1]);
				int score_filho = obter_pontuacao(filho);
				
				if(score_filho > score_pai){
					for(int k=0; k<TAM_GENES; k++){
						populacao[pai_1][k] = filho[k];
					}
				}
			}
		}
		int indice_melhor = obter_melhor();
		int score_melhor  = obter_pontuacao(populacao[indice_melhor]);
		cout << "Geraçao: " << i+1 << endl;
		cout << "Melhor: [";
		for(int i=0; i<TAM_GENES; i++){
			cout << populacao[indice_melhor][i] << " ";
		}
		cout << "]" << endl;
		cout << "Pontuação: " << score_melhor << endl << endl;
		
		if(score_melhor == TAM_GENES){ break; }
	}
	cout << "População final:" << endl;
	mostrar_populacao();

}

int main()
{
	srand(time(NULL));
	char op = '0';
	
	cout << "Algoritmo genetico baseado na regra OneMax.\n"
	"O sistema funciona da seguite forma:\n"
	"* É gerado uma população de " << TAM_POP << " individuos.\n"
	"* Cada individuo possui " << TAM_GENES << " genes.\n"
	"O objetivo é conseguir um individuo que possua genes perfeitos, ou\n"
	"seja, igual a " << TAM_GENES << " dentro do periodo de " << GERACOES << " geraçoes, caso o numero\n"
	"de geraçoes seja insuficiente, devemos pegar o melhor\n"
	"individuo.\n\n"
	"Para rodar o programa digite 1 ou qualquer tecla para sair: ";
	cin >> op;
	if(op == '1'){ run(); }

	return 0;
}