próximo »

[tronador]

Algoritmo Genetico[1]

Un algoritmo genético (AG) puede presentar diversas variaciones, dependiendo de cómo se aplican los operadores genéticos (cruzamiento, mutación), de cómo se realiza la selección y de cómo se decide el reemplazo de los individuos para formar la nueva población. En general, el pseudocódigo consiste de los siguientes pasos:
Algoritmo genético i: inicialización, f(X): evaluación, ?: condición de término, Se: selección, Cr: cruzamiento, Mu: mutación, Re: reemplazo, X*: mejor solución.

    * Inicialización: Se genera aleatoriamente la población inicial, que está constituida por un conjunto de cromosomas los cuales representan las posibles soluciones del problema. En caso de no hacerlo aleatoriamente, es importante garantizar que dentro de la población inicial, se tenga la diversidad estructural de estas soluciones para tener una representación de la mayor parte de la población posible o al menos evitar la convergencia prematura.

    * Evaluación: A cada uno de los cromosomas de esta población se aplicará la función de aptitud para saber cómo de "buena" es la solución que se está codificando.

    * Condición de término El AG se deberá detener cuando se alcance la solución óptima, pero ésta generalmente se desconoce, por lo que se deben utilizar otros criterios de detención. Normalmente se usan dos criterios: correr el AG un número máximo de iteraciones (generaciones) o detenerlo cuando no haya cambios en la población. Mientras no se cumpla la condición de término se hace lo siguiente:

          o Selección Después de saber la aptitud de cada cromosoma se procede a elegir los cromosomas que serán cruzados en la siguiente generación. Los cromosomas con mejor aptitud tienen mayor probabilidad de ser seleccionados.

          o Cruzamiento El cruzamiento es el principal operador genético, representa la reproducción sexual, opera sobre dos cromosomas a la vez para generar dos descendientes donde se combinan las características de ambos cromosomas padres.

          o Mutación modifica al azar parte del cromosoma de los individuos, y permite alcanzar zonas del espacio de búsqueda que no estaban cubiertas por los individuos de la población actual.

          o Reemplazo una vez aplicados los operadores genéticos, se seleccionan los mejores individuos para conformar la población de la generación siguiente


Ya despues de la teoria viene el codigo[2] en Java[3], en este caso se resuelve el problema del agente viajero (TSP), las instancias son archivos de TSPLIB[4]:

AlgoritmoGenetico.java

Código:

/**
 * @(#)AlgoritmoGenetico.java
 *
 *
 * @author
 * @version 1.00 2009/5/26
 */
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class AlgoritmoGenetico {

public int tamPoblacion;
public int tamElite;
public double tasaMutacion;
public double tasaCruzamiento;
public int numGeneraciones;
public ArrayList<Individuo> poblacion;
public TSP problema;
public int generacion;

    public AlgoritmoGenetico(int tampoblac, double mutacion, int elite, double cruzamiento, int generaciones, TSP p) {
   
    tamPoblacion = tampoblac;
    tamElite = elite;
    tasaMutacion = mutacion;
    tasaCruzamiento = cruzamiento;
    numGeneraciones = generaciones;
    poblacion = new ArrayList<Individuo>();
    problema = p;
    ejecutar();
    generacion = 0;
    }
   
    public void ejecutar(){
   
    generarPoblacion();
   
    long inicio = System.currentTimeMillis()/60000;
   
    while(System.currentTimeMillis()/60000 - inicio < 15)
    {
    calcularFitness();
    seleccion();
    cruzamiento();
    mutacion();
    generacion++;
    }
   
    }
   
    public void generarPoblacion()
    {
    ArrayList<Integer>genes = problema.ciudades;
   
    for(int i = 0; i < tamPoblacion; i++)
    {
    Individuo in = new Individuo();
    ArrayList<Integer>genesIndividuo = (ArrayList<Integer>)genes.clone();
    Collections.shuffle(genesIndividuo);
    in.cromosomas = genesIndividuo;
    poblacion.add(in);
   
    }
   
    }
   
    public void calcularFitness()
    {
   
    for(int i = 0; i < poblacion.size(); i++)
    {
    Individuo in = poblacion.get(i);
    double fitness = problema.valorCamino(in.cromosomas);
    in.fitness = fitness;
   
    }
    }
   
    public void seleccion()
    {
    Collections.sort((List)poblacion);
    ArrayList<Individuo> nuevaPoblacion = new ArrayList<Individuo>();
   
    if(generacion % 20 == 0)
    System.out.println("Mejor = "+poblacion.get(0).fitness+" : "+poblacion.get(0).toString());
   
    for(int i = 0; i < tamElite; i++)
    {
    Individuo in = poblacion.get(i);
    nuevaPoblacion.add(in);
    poblacion.remove(i);
    }
Random rnd = new Random();
    for(int i = 0; i < tamElite; i++)
    {
    int r = (int)(rnd.nextDouble() * poblacion.size());
    Individuo in = poblacion.get(r);
    nuevaPoblacion.add(in);
    poblacion.remove(r);
    }
       
    poblacion.clear();
    poblacion.addAll(nuevaPoblacion);
    }
   
    public void cruzamiento()
    {
    Random rnd = new Random();
    int padre, madre, r1, r2, r3, r4, i, j, k, puntoCruce;
    int cromosomas = poblacion.get(0).cromosomas.size();
   
    while(poblacion.size() < tamPoblacion)
    {
   
    r1 = (int)(rnd.nextDouble()*poblacion.size());
    r2 = (int)(rnd.nextDouble()*poblacion.size());
   
    if(poblacion.get(r1).fitness > poblacion.get(r2).fitness)
    {
    padre = r1;
    }
    else
    {
    padre = r2;
    }
   
    madre = padre;

while(madre == padre)
{
    r3 = (int)(rnd.nextDouble()*poblacion.size());
    r4 = (int)(rnd.nextDouble()*poblacion.size());   
   
    if(poblacion.get(r3).fitness > poblacion.get(r4).fitness)
    {
    padre = r3;
    }
    else
    {
    padre = r4;
    }   
}

puntoCruce = (int)(rnd.nextDouble()*cromosomas);

ArrayList<Integer> cromosomasHijo1 = new ArrayList<Integer>();
ArrayList<Integer> cromosomasHijo2 = new ArrayList<Integer>();

for(i = 0; i < cromosomas; i++)
{
cromosomasHijo1.add(null);
cromosomasHijo2.add(null);
}

ArrayList<Integer> cromosomasPadre = poblacion.get(padre).cromosomas;
ArrayList<Integer> cromosomasMadre = poblacion.get(madre).cromosomas;


for(i = 0; i < puntoCruce; i++)
{
cromosomasHijo1.set(i,cromosomasPadre.get(i));
}

i = puntoCruce;
j = puntoCruce;
k = 0;



while(i < cromosomas)
{
if(k < cromosomas)
{
if(!cromosomasHijo1.contains(cromosomasMadre.get(k)))
{
cromosomasHijo1.set(i,cromosomasMadre.get(k));
i++;
}
k++;
}

if(j < cromosomas)
{

if(!cromosomasHijo1.contains(cromosomasPadre.get(j)))
{
cromosomasHijo1.set(i,cromosomasPadre.get(j));
i++;
}
j++;
}
}


for(i = puntoCruce; i < cromosomas; i++)
{
cromosomasHijo2.set(i,cromosomasMadre.get(i));
}

i = 0;
j = 0;
k = puntoCruce;

while(i < puntoCruce)
{
if(j < cromosomas)
{

if(!cromosomasHijo2.contains(cromosomasPadre.get(j)))
{
cromosomasHijo2.set(i,cromosomasPadre.get(j));
i++;
}
j++;
}

if(k < cromosomas)
{

if(!cromosomasHijo2.contains(cromosomasMadre.get(k)))
{
cromosomasHijo2.set(i,cromosomasMadre.get(k));
i++;
}
k++;
}
}

Individuo children1 = new Individuo();
Individuo children2 = new Individuo();

children1.cromosomas = cromosomasHijo1;
children2.cromosomas = cromosomasHijo2;

poblacion.add(children1);

if(poblacion.size() < tamPoblacion)
poblacion.add(children2);

    }
   
    }
   
    public void mutacion()
    {
    Random rnd = new Random();
    int cromosomas = poblacion.get(0).cromosomas.size();
    int r1, r2;
       
    for(int i = tamElite; i < poblacion.size(); i++)
    {
    double random = rnd.nextDouble();
   
    if(tasaMutacion > random)
    {
    ArrayList<Integer> cromosomasMutante = poblacion.get(i).cromosomas;
   
    r1 = (int)(rnd.nextDouble()*cromosomas);
    r2 = (int)(rnd.nextDouble()*cromosomas);
   
    Integer temp = cromosomasMutante.get(r1);
    cromosomasMutante.set(r1,cromosomasMutante.get(r2));
    cromosomasMutante.set(r2,temp);
    }
    }
   
    tasaMutacion = tasaMutacion / 2;
    if(generacion % 20 == 0)
    tasaMutacion = 0.5;
    }
   
    public static void main(String args[])
    {
    TSP p = new TSP("st70.tsp");
    int tampoblac = 100;
    double mutacion = 0.5;
    int elite = 20;
    double cruzamiento = 0.9;
    int generaciones = 100;
   
    new AlgoritmoGenetico(tampoblac,mutacion,elite,cruzamiento,generaciones,p);
    }
   
   
}

Individuo.java

Código:

/**
 * @(#)Individuo.java
 *
 *
 * @author
 * @version 1.00 2009/5/26
 */
import java.util.ArrayList;

public class Individuo implements Comparable{

public ArrayList<Integer>cromosomas;
public double fitness;

    public Individuo() {
    }
   
    public String toString()
    {
    String s = "";
   
    for(int i = 0; i < cromosomas.size()-1; i++)
    {
    s = s + cromosomas.get(i).toString() + "-";
    }
    s = s + cromosomas.get(cromosomas.size()-1).toString();
   
    return s;
    }
   
    public int compareTo(Object o)
    {
    Individuo b = (Individuo)(o);
    if(fitness < b.fitness)
    {
    return -1;
    }
    else if(fitness > b.fitness)
    {
    return 1;
    }
    else
    {
    return 0;
    }
    }
}

TSP.java

Código:

/**
 * @(#)TSP.java
 *
 *
 * @author
 * @version 1.00 2009/5/20
 */
import java.io.*;
import java.util.*;

public class TSP {
public ArrayList infoArchivo;
public ArrayList<Double>x;
public ArrayList<Double>y;
public double matrizCosto[][];
public ArrayList<Integer>ciudades;

    public TSP(String url) {
   
    infoArchivo = new ArrayList();
    x = new ArrayList<Double>();
    y = new ArrayList<Double>();
    ciudades = new ArrayList<Integer>();
   
    cargarDatos(url);
    cargarMatrizCostos();
       
    }
   
   
    public void cargarDatos(String url)
{
           

try
{
File archivo = new File(url);
if(archivo.exists())
{
FileReader reader = new FileReader(archivo);
BufferedReader read = new BufferedReader(reader);
String linea = "";
while((linea = read.readLine())!=null)
{
infoArchivo.add(linea);
System.out.println(linea);
}
read.close();
}else{System.out.println("No existe "+archivo.getCanonicalPath());}
}catch(Exception e){e.printStackTrace();}

boolean lee = false;

for(int k = 0; k < infoArchivo.size(); k++)
{
String linea = (String)infoArchivo.get(k);

System.out.println(linea);
if(linea.trim().startsWith("1"))
{
lee = true;
}

if(lee && !linea.trim().startsWith("EOF"))
{
String[] info1 = getValores(linea.trim().split(" "));
   
x.add(Double.valueOf(info1[1])) ;
y.add(Double.valueOf(info1[2])) ;
ciudades.add(Integer.valueOf(info1[0]));


//System.out.println("c="+info1[0]);
//System.out.println("x="+info1[1]);
//System.out.println("y="+info1[2]);
}


}




}

public void cargarMatrizCostos()
{
matrizCosto = new double[ciudades.size()][ciudades.size()];
for(int i = 0; i < ciudades.size()-1; i++)
{
for(int j = i+1; j < ciudades.size(); j++)
{
double xd = x.get(i).doubleValue()-x.get(j).doubleValue();
double yd = y.get(i).doubleValue()-y.get(j).doubleValue();
double d = Math.sqrt(xd*xd + yd*yd);

matrizCosto[i][j] = d;
matrizCosto[j][i] = d;

}
}


}

public double valorCamino(ArrayList<Integer>ruta)
{
double s = 0.0;

for(int i = 0; i < ciudades.size()-1; i++)
{

s = s + matrizCosto[ruta.get(i).intValue()-1][ruta.get(i+1).intValue()-1];
}

s = s + matrizCosto[ruta.get(ciudades.size()-1).intValue()-1][ruta.get(0).intValue()-1];

return s;
}
   
}

[1][2][3] Edit temporal, ahora vuelvo a poner el texto q iba aqui ...
[4] Instancias de TSPLIB, el usado como prueba fue el st70.tsp

Saludos

[flacman]

xD cre oq si iker lee el código lo mata jajaja .... no pero aguanta, la verdad nunk habia visto un algoritmo d estos en acción jeje. Por otro lado, ¿la mutación si es tan aleatoria?
Digamos que de AG no se mucho, pero si se algo de Renes neuronales y ps los cambios en los potenciales de acción siempre se dan debido a cierta función f (que lo hace mas cercano a su objetivo).

Por otro lado, en el cuento del cruzamiento, esto no puede llegar a un punto en el que todas las cromosomas sean iguales? ps digo, se elimina una y se reemplaza por una follada de un padre y una madre xD, lo cual hace que todas en algún momento puedan llegar un mismo punto... aleatorio (es decir, todas pueden llegar a tomar cualquiera de las formas de solución), o estoy mal?

[tronador]

Digamos que de AG no se mucho, pero si se algo de Renes neuronales y ps los cambios en los potenciales de acción siempre se dan debido a cierta función f (que lo hace mas cercano a su objetivo).

Aca las mutaciones se hacen solo para evitar que el algoritmo se quede en un minimo local, alli la unica modificacion que hice con respecto a los AG originales es que la tasa de mutacion es variable, es decir inicialmente es alta y luego va disminuyendo y despues de 20 generaciones vuelve y aparece xD.

Por otro lado, en el cuento del cruzamiento, esto no puede llegar a un punto en el que todas las cromosomas sean iguales? ps digo, se elimina una y se reemplaza por una follada de un padre y una madre xD, lo cual hace que todas en algún momento puedan llegar un mismo punto... aleatorio (es decir, todas pueden llegar a tomar cualquiera de las formas de solución), o estoy mal?

El cruzamiento se hace de esta forma:



Primero se elige a los padres de un hijo especifico (antes seleccionaba solo dos padres que sirvieran para hacer todos los nuevos de la siguiente generacion pero me di cuenta de que las soluciones no eran tan buenas)

El cruzamiento consiste en seleccionar un punto aleatoriamente en ambos padres, dividiendo los cromosomas padres en dos, la primera mitad de un padre se copia intacta sobre un hijo, y la segunda mitad del otro padre se copia idénticamente sobre el otro hijo.

Los cromosomas descendientes se completan copiando los genes faltantes tomándolas de los cromosomas padres alternando entre ellos, solamente se copia aquellas genes que falten en los descendientes.

Antes ocurria el problema que mencionas cuando el padre elegido al azar resultaba ser al mismo tiempo madre, en este caso lo solucione asi:

madre = padre;
while(madre == padre)
 //seleccionar madre diferente

pero viendolo bien aun puede darse el caso y puede que en algun momento (con probabilidad baja) todas las soluciones lleguen a ser iguales (ademas tambien puede darse el caso de que se quede en ese while por siempre xD)


Saludos


P.D: Coloca algo de info que sirva como introduccion a las redes neuronales porque de eso entiendo muy poco y me interesa bastante xD 

[flacman]

jeje si, eso lo dije por esa "condición de carrera" q se podía generar justamente en esa parte del código

La verdad tal como intro en inet no he encontrado nada muy bueno :S, pero tengo bibliografía física en mi ksa, si me consigna lo de las fotocopias y en envio le mando el par de libritos que tengo (la verdad el único bueno que tengo es el de kohonen pero solo cubre RN de kohen (mapas auto-organizados))

[tronador]

de hecho no se me habia ocurrido buscar bibliografia fisica (xD), estare revisando por aca y si no encuentro adecuada entonces te contacto para cuadrar lo de las fotocopias

[flacman]

jajaja y si encuentra me manda xD

[glycerol]

Encuetnro este error en el codigo provisto

location: class TSP
                String[] info1 = getValores(linea.trim().split(" "));

cannot find symbol method getValores(java.lang.String[])

que podria hacer
estoy compilando con jcreator

[tronador]

parece que el codigo lo pegue incompleto xD, agrega esta funcion que hacia falta.

Código:

public String[] getValores(String[] info)
{
String[] valores = new String[3];
int i = 0;
for(int k = 0; k < info.length; k++)
{
if(!info[k].equals(""))
{
valores[i] = info[k];
i++;
}
}
return valores;
}

[eskiwis]

hola interesante el codigo de algoritmo genetico pero me da un error al correrlo en esta linea del método valor Camino

 s=s+matrizCosto[ruta.get(ciudades.size()-1).intValue()-1][ruta.get(0).intValue()-1];

ArrayIndexOutOFBoundexception

ojala me pudieras indicar que debo corregir, soy nueva en esto

saludos

[rcgcalume]

adjunto

[flacman]

tiene pinta d q lo hizo ud... si es cierto?