problema algoritmo genetico

[stiwi222]

bueno, he terminado la implementacion de un algoritmo genetico sencillo. le das un numero y te devuelve una cadena con una manera d llegar a ese numero.
por ejemplo, si el numero es 10 una posible solucion es "2*5" o "2+2+2+2+2" o "100/10", etc.

sin embargo, hay un punto del programa en el que salta"This application requested the Runtime to terminate in an unusual way. please contact..." y termina devolvieno 3 (el programa).

con un depurador he llegado al punto en el que se produce el error. este me dice "In __cxa_throw () ()". aparece en el bucle de la linea 122 .

bueno, este es el codigo:

Código C++:

#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(){
 
    srand((int)time(NULL));
 
    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 "";
}
 

agradeceria toda la ayuda posible

[Tikitios]

lo compile y me da error justo aqui : cruce(descendencia1, descendencia2);
(puse un system pause antes y despues de eso, por eso se que ahi es el error)

[stiwi222]

gracias :) . me pondre a revisar esa funcion.

[abacusar]

No tiene nada que ver, pero en la línea 250 creo que el acceso a buffer[i+1] en la última iteración se sale de rango.

[abacusar]

Ya encontré el problema:

en ruleta(), devuelves a menudo como cromosoma "" (cromosoma vacío).
Cuando devuelves uno de estos, al entrar en cruce() se buscan subcadenas.
La llamada a substr casca con out_of_range si el indice inicial está fuera de la cadena. En la cadena vacía, al acceder como índice a 'punto' que se supone mayor que 0, casca.

Por cierto, es mejor si pones la línea 13 así:

Código C:

#define NUM_ALE ((float)rand() / ((float)RAND_MAX+1))
 

para que no se queje :)

[stiwi222]

hola, siento no haber podido contestar antes. os agradezco mucho la ayuda a los 2 . voy a corregir el error y postearé el código completo.