[ Foro de C# ]

Algoritmos Geneticos

05-Mar-2016 22:33
Invitado (Lhican)
2 Respuestas

Para responder a mi pregunta, necesito que sepan bien como funciona un algoritmo genético.

Me dejaron un problema que es el siguiente:

En una aplicación de consola, crear un laberinto de la siguiente manera: una cuadricula de 10x10 casillas, una de esas casillas va a ser la entrada y otra va a ser la salida. Se deben de crear la entrada y la salida al azar (es decir con coordenadas aleatorias).

El problema consiste en los siguiente: por medio de algoritmos genéticos, encontrar la ruta que me conduzca de la entrada a la salida en 19 movimientos (siendo estos atrás, adelante, izquierda y derecha).  

Lo que se me ocurrió fue crear a mis individuos (rutas) de la siguiente forma: arreglos de 19 casillas, y en cada casilla se le asignara un movimiento aleatorio, es decir un número al azar del 0 al 3, porque así represente los movimientos:  0=atrás, 1=adelante, 2=izquierda, 3=derecha.

public class Ruta
   {
       int[] ruta = new int[19];
       Random r = new Random();

       int fitness;

       public Ruta()
       {
             int[] ruta = new int[39];

           for(int i=0; i<=39 ; i++)
           {
               int a = r.Next(0, 3);
               ruta[i] = a;
            }
       }

public void adecuar()
       {
           
       }

Mi pregunta es la siguiente: ¿cómo codificó mi función adecuación (método adecuar) de manera que ésta me arroje la distancia de donde me encuentre después de ya haberme movido 19 veces  a donde se encuentre la salida?


06-Mar-2016 05:24
DG. Corporation. (+4)

Buenas.

Lo que entendí de este ejercicio es que tienes que buscar la ruta mas corta a la salida, con menos de 19 movimientos.

Por lo que no le puedes poner a la persona que se mueva aleatoriamente, se tiene que hacer un algoritmo para que busque la ruta más corta de una manera organizada.

Por lo que hice un código que creo que es una solución:


using System;


namespace Ejercicio
{
   class Coordenadas{
    private int coordx=0; private int coordy=0;


    public String Coordenada{
     get {
      return "(" + coordx + "," + coordy +" )";
     }    
    }//Para devolver la coordenada en String.

    public int X{
     get{ return this.coordx;}
    }//Para el valor de X.

    public int Y{
     get{ return this.coordy;}
    }//Para el valor de Y.

    public Coordenadas(int x,int y){
     this.coordx= x; this.coordy= y;
    }//Constructor de la clase Coordenadas.


   }//Fin de la clase Coordenadas.


   //Clase Laberinto.
   class Laberinto{
       
    class Persona{

     private Coordenadas PosicionActual;
     private Coordenadas Salida;
     private int OperacionX = 1;
     private int OperacionY = 1;
     //Fin de variables importantes.

     public Coordenadas Posicion{
      get{ return PosicionActual;}
     }//Fin de para capturar la posicion de la persona.


     public Persona(Coordenadas Entrada, Coordenadas Salida, int operacionX,int operacionY){
      this.PosicionActual = Entrada;
      this.Salida = Salida;
      this.OperacionX = operacionX;
      this.OperacionY = operacionY;
     }//Fin del constructor de la persona.
     
     public int Calcular(int Posicion,int Salida, int operacion){
      if(Posicion != Salida){  return Posicion  + ( 1 * operacion );}
      else{ return Posicion;}
     }//Fin de para calcular la trayectoria.


     public void Mover(){
      int x = this.Calcular(PosicionActual.X,Salida.X,OperacionX);
      int y = this.Calcular(PosicionActual.Y,Salida.Y,OperacionY);
      this.PosicionActual = new Coordenadas(x,y);
     }//Fin de para mover a la persona.

     public Boolean Equals(Coordenadas Comparar){
      return (this.PosicionActual.X == Comparar.X && this.PosicionActual.Y == Comparar.Y);
     }//Para comparar las coordenadas.

    }//Fin de la clase Personas.



   Random r=new Random();//Valor importante de la clase laberinto.

   private Coordenadas PosicionAleatoria(){
    return new Coordenadas(r.Next(9),r.Next(9));
   }//Para dar la posiciones aleatorias (Entrada y salida).

   private int Comparar(int entrada,int salida){
    int operacionX=1;
    if (entrada == salida){ operacionX= 0;}
    else{
     if(entrada > salida){ operacionX= -1;}
    }
    return operacionX;
   }//Fin del metodo para comparar las rutas.



    public void Iniciar(){

     Coordenadas Entrada = PosicionAleatoria();
     Coordenadas Salida  = PosicionAleatoria();

     int operacionX=this.Comparar(Entrada.X,Salida.X);
     int operacionY=this.Comparar(Entrada.Y,Salida.Y);


     Persona  Persona = new Persona(Entrada,Salida,operacionX,operacionY);

     int movimientos = 0;//Para contar los movimientos.

     for(int i=0;i< 100; i++){
      if(Persona.Equals(Salida)){
       break;
      }//Fin de que si encuentra la salida.
      else{
       Persona.Mover();
      }//Fin de que si no ha encuentrado la salida.
      movimientos++;
     }//Fin del for para encontrar la salida.

     Console.WriteLine("Coordenada de entrada: "+Entrada.Coordenada);
     Console.WriteLine("Coordenada de posicion final: " + Salida.Coordenada);
     Console.WriteLine("Se llego al final de laberinto en: "+movimientos+" movimientos.");
     Console.ReadKey();
    }//Fin del metodo para iniciar el desafio del laberinto.

   }//Fin de la clase Laberinto.



   class Program
   {
       static void Main(string[] args)
       {
          Laberinto d=new Laberinto();
          d.Iniciar();
       }
   }
}

                                                                                                                                             Buena suerte.


06-Mar-2016 06:42
DG. Corporation. (+4)

Hice una aplicación en Windows Forms demostrando ese algoritmo:

Es un ejecutable:

Descargalo de esta pagina:

http://www.mediafire.com/download/dhl1t4bmyk81bv8/Laberinto.exe






(No se puede continuar esta discusión porque tiene más de dos meses de antigüedad. Si tienes dudas parecidas, abre un nuevo hilo.)