#include <iostream>
#include <string>
#include <math.h>
#include <time.h>
#include <stdlib.h>
#define CROMO_LON 300
#define GEN_LON 4
#define TAM_POBLACION 300
#define PROB_MUTAR 0.01
#define PROB_CRUCE 0.75
#define MAX_GENERACIONES 400
#define NUM_ALE ((float)rand() / (RAND_MAX+1))
using namespace std;
using std::string;
/* TABLA DE VALORES:
* 0000 -> 0
* 0001 -> 1
* 0010 -> 2
* 0011 -> 3
* 0100 -> 4
* 0101 -> 5
* 0110 -> 6
* 0111 -> 7
* 1000 -> 8
* 1001 -> 9
* 1010 -> +
* 1011 -> -
* 1100 -> *
* 1101 -> /
* 1110 -> NADA (se toman precauciones para que no sea tomado en cuenta)
* 1111 -> NADA (se toman precauciones para que no sea tomado en cuenta)
*/
// Prototipos
struct cromosoma{//unidad basica
string bits;
float aptitud;
cromosoma(): bits(""), aptitud(0.0f) {};
cromosoma(string m_bits, float m_aptitud): bits(m_bits), aptitud(m_aptitud){};
};
void MuestraSimboloGen(int valor);
int BinaDec(string bits);
int analiza_cromo(string bits, int *buffer);
void MuestraCromo(string cromosoma);
string genes_aleatorios(int longitud);
float determina_aptitud(string bits, int deseado);
void mutar(string &bits);
void cruce(string &descendencia1, string &descendencia2);
string ruleta(int aptitud_total, cromosoma* poblacion);
int main(){
while(true){ //nunca acaba... a no ser que lo cierres :)
cromosoma poblacion[TAM_POBLACION]; //nuestra particular poblacion
float objetivo;
cout<<"\nDame un número: ";
cin>>objetivo;
cout << endl << endl;
//creamos la poblacion, con unos genes aleatorios y una aptitud 0
for(int i=0; i<TAM_POBLACION; i++){
poblacion[i].bits = genes_aleatorios(CROMO_LON);
poblacion[i].aptitud = 0.0f;
}
int GeneracionesHastaSolucion = 0;
int encontrado = 0; //flag para saber si se ha encontrado una solución
while(!encontrado){
float AptitudTotal = 0.0f;
//actualizamos todas las aptitudes
for(int i=0; i<TAM_POBLACION; i++){
poblacion[i].aptitud = determina_aptitud(poblacion[i].bits, objetivo);
AptitudTotal += poblacion[i].aptitud;
}
for(int i=0; i<TAM_POBLACION; i++){
if(poblacion[i].aptitud == 999.0f){
cout<<"\n¡Solucion encontrada en "<<GeneracionesHastaSolucion<<"generaciones!"<<endl<<endl;
MuestraCromo(poblacion[i].bits);
encontrado = 1;
break;
}
}
//creamos la nueva poblacion. para ello necesitamos una "memoria intermedia"
cromosoma temp[TAM_POBLACION];
int pobl = 0;
while(pobl<TAM_POBLACION){
// creamos la poblacion a pares, selecionandolos con la ruleta
// y mas tarde cruzandolos y mutandolos
string descendencia1 = ruleta(AptitudTotal, poblacion);
string descendencia2 = ruleta(AptitudTotal, poblacion);
cruce(descendencia1, descendencia2);
mutar(descendencia1);
mutar(descendencia2);
//ahora les añadimos a la nueva poblacion, con una aptitud de 0
temp[pobl++] = cromosoma(descendencia1, 0.0f);
temp[pobl++] = cromosoma(descendencia2, 0.0f);
} //fin del bucle
//copiamos la poblacion temporal en la real
for(int i=0; i<TAM_POBLACION; i++){
poblacion[i] = temp[i];
}
GeneracionesHastaSolucion++;
if(GeneracionesHastaSolucion>MAX_GENERACIONES){
cout<<"no se encontro ninguna solucion en "<<MAX_GENERACIONES<<" generaciones";
encontrado = 1;
}
}
cout<<"\n\n\n";
} //fin while
return 0;
}
void MuestraSimboloGen(int valor){
if(valor<10)
cout<<valor<<" ";
else
switch(valor){
case 10:
cout<<"+";
break;
case 11:
cout<<"-";
break;
case 12:
cout<<"*";
break;
case 13:
cout<<"/";
break;
}
cout<<" ";
}
int BinaDec(string bits){
int valor = 0;
int valor_a_anyadir = 1;
for (int i = bits.length(); i > 0; i--)
{
if (bits.at(i-1) == '1')
valor += valor_a_anyadir;
valor_a_anyadir *= 2;
}//siguiente bit
return valor;
}
int analiza_cromo(string bits, int *buffer){
int posBuff = 0;
int gen;
int tipo = 1; // 1 si el valor es un numero, 0 si es operador
for (int i=0; i<CROMO_LON; i+=GEN_LON){
gen=BinaDec(bits.substr(i, GEN_LON));
if(tipo){
if((gen>13) || (gen<16))
continue;
else{
tipo=0;
buffer[posBuff++] = gen;
}
}
else{
if(gen>9)
continue;
else{
tipo=1;
buffer[posBuff++] = gen;
continue;
}
}
} //nuevo gen
// tratamiento de errores: comprobamos si existe una posible division entre 0
// de ser asi transformamos en '/' en '+'. simple pero eficaz
for(int i=0; i<posBuff; i++){
if((buffer[i] == 13) && (buffer[i+1] == 0) ){
buffer[i] = 10;
}
}
return posBuff;
}
void MuestraCromo(string cromosoma){
int buffer[CROMO_LON/GEN_LON];
int num_elementos = analiza_cromo(cromosoma, buffer);
for(int i=0; i<num_elementos; i++){
MuestraSimboloGen(buffer[i]);
}
}
string genes_aleatorios(int longitud){
string bits;
for(int i=0; i<=longitud; i++){
if(NUM_ALE>0.5f)
bits +="1";
else
bits +="0";
}
return bits;
}
float determina_aptitud(string bits, int deseado){
int buffer[CROMO_LON/GEN_LON];
int num_elementos = analiza_cromo(bits, buffer);
float resultado = 0.0f;
for(int i=0; i<num_elementos-1; i+=2){
switch(buffer[i]){
case 10:
resultado += buffer[i+1];
break;
case 11:
resultado -= buffer[i+1];
break;
case 12:
resultado *= buffer[i+1];
break;
case 13:
resultado /= buffer[i+1];
break;
} //switch
}
// comprobamos si el resultado coincide con el deseado
// si no coincide se asigna una aptitud, mas alta cuanto mas
// se aproxime al resultado deseado, de esta manera casi nos aseguramos
// de que pase a la siguente generacion
if(resultado == (float)deseado)
return 999.0f; //exito
else return 1/((float)fabs((double)(deseado
- resultado
))); // aptitud
}
void mutar(string &bits){
for(int i=0; i<=bits.length(); i++){
if(NUM_ALE < PROB_MUTAR){
bits.at(i) == 1 ? bits.at(i) = 0 : bits.at(i) = 1;
}
}
}
void cruce(string &descendencia1, string &descendencia2){
if(NUM_ALE < PROB_CRUCE){
int punto = (int) (NUM_ALE * CROMO_LON);
string t1 = descendencia1.substr(0, punto) + descendencia2.substr(punto, CROMO_LON);
string t2 = descendencia2.substr(0, punto) + descendencia1.substr(punto, CROMO_LON);
descendencia1 = t1; descendencia2 = t2;
}
}
string ruleta(int aptitud_total, cromosoma* poblacion){
// numero aleatorio entre 0 y la aptitud total
float porcion = (float) (NUM_ALE * aptitud_total);
//acumula las aptutudes
float AptitudHastaAhora = 0.0f;
for(int i=0; i<TAM_POBLACION; i++){
AptitudHastaAhora = poblacion[i].aptitud;
if(AptitudHastaAhora >= porcion)
return poblacion[i].bits;
}
return "";
}