API tools faq
paste
Advertisement
Garro

Algoritmo Evolutivo - NetLogo

Garro
Dec 5th, 2016
108
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 13.86 KB | None | 0 0
raw download clone embed print report
  1. import java.util.concurrent.TimeUnit;
  2. import java.util.*;
  3. import java.io.*;
  4. import java.lang.*;
  5.  
  6. public class AlgoritmoEvolutivo{
  7.     static BufferedReader reader;
  8.     static ArrayList<int[]> list = new ArrayList<int[]>();      //La estructura de int[] es: {x1,y1,x2,y2,x3,y3,x4,y4,x5,y5,time}
  9.     static String fileName = "plan.plan";                       //El archivo que se leera.
  10.     static int[][] matrix;                                      //La matriz donde se guarda el plano.
  11.     static int validWallValue = 32;                             //Valor personalizado que usara la matriz para determinar paredes validas
  12.     static int validWallCount = 0;                              //Cantidad de paredes validas, utilizada en algoritmos de generacion al azar.
  13.     static int nIteraciones = 30;                              
  14.     static int nIndividuos = 30;
  15.     static int nMutaciones = 5;
  16.     //Cantidad de vectores (conjunto de 5 puertas) por iteracion.
  17.  
  18.     public static void main(String[]args){
  19.         int[] map_lenght = readBlueprintSize();
  20.         matrix = new int[map_lenght[1]+1][map_lenght[0]+1];
  21.         int[] vector = new int[11];
  22.  
  23.         populateMatrix();
  24.         setValidWalls();
  25.         printMatrix();
  26.  
  27.         for(int i=0; i < nIndividuos; i++){
  28.             list.add(evaluate(generateRandomTestValues()));
  29.         }
  30.  
  31.         writeList();
  32.  
  33.         //Comienzan las iteraciones.
  34.         for(int i = 1; i<=nIteraciones; i++){
  35.             Random rng = new Random();
  36.  
  37.             //1. ordenar poblacion
  38.             //inserte codigo aqui
  39.            
  40.  
  41.  
  42.             //2. De los 10 más optimos en la lista, se cruzan en pares aleatorios.
  43.             //De este cruzamiento se generan 5 hijos que se agregan al fondo de la lista.
  44.             List<int[]> topTen = list.subList(0,10);
  45.             ArrayList<int[]> bottomFive = new ArrayList<int[]>();
  46.  
  47.             while(topTen.size()>0){
  48.                 //extrae padre A y posicion aleatoria.
  49.                 int a = rng.nextInt(topTen.size()-1);
  50.                 int[] parentA = list.get(a);
  51.                 topTen.remove(a);
  52.                 //extrae padre B y posicion aleatoria.
  53.                 int b = rng.nextInt(topTen.size()-1);
  54.                 int[] parentB = list.get(b);
  55.                 topTen.remove(b);
  56.                 bottomFive.add(crossValues(evaluate(parentA),evaluate(parentB)));
  57.             }
  58.  
  59.             //Remueve los ultimos 5 objetos de la lista.
  60.             for(int k = list.size()-5; k < list.size(); k++){
  61.                 list.remove(k);
  62.             }
  63.  
  64.             //Agrega los 5 nuevos objetos a la lista.
  65.             for(int j=0;j<bottomFive.size();i++){
  66.                 list.add(bottomFive.get(j));
  67.             }
  68.  
  69.             //3. Muta n valores al azar de los individuos en medio (no top ten y no bottom five)
  70.             for(int j=0;j<nMutaciones;j++){
  71.                 int aux = rng.nextInt(list.size()-16)+10;
  72.                 list.set(aux,evaluate(mutateValue(list.get(aux),3)));
  73.             }
  74.  
  75.             //4. calcular promedio y encontrar el mayor
  76.             int optimo = 10000;
  77.             int promedio = 0;
  78.             for(int j=0;j<list.size();j++){
  79.                 int aux = list.get(j)[10];
  80.                 if(aux < 9000){
  81.                     promedio += aux;
  82.                     if(aux < optimo){
  83.                         optimo = aux;
  84.                     }
  85.                 }
  86.             }
  87.  
  88.             System.out.println("Iteracion n."+i+": Mejor valor: "+optimo+", Promedio: "+promedio);
  89.             writeList();
  90.         }
  91.     }
  92.  
  93.     //Evalua el vector y devuelve el tiempo de la simulacion. Este metodo componen
  94.     //la escritura de doors.plan, la ejecucion de NetLogo y la lectura de seconds.output.
  95.     public static int[] evaluate(int[] vector){
  96.             writeDoorsPlan(vector);
  97.             execNetLogo();
  98.             vector[10] = readDoorsTime();
  99.             return vector;
  100.     }
  101.  
  102.  
  103.     //Calcula las dimensiones del plano en fileName, devuelve un array de dos valores
  104.     //con el ancho y alto del plano en ese orden.
  105.     public static int[] readBlueprintSize(){
  106.         String line;
  107.         int map_width = 0;
  108.         int map_height = 0;
  109.         int temp;
  110.  
  111.         openFile(fileName);
  112.        
  113.         try{
  114.             line = reader.readLine();
  115.             do{
  116.                 temp = Integer.parseInt(line.substring(0,line.indexOf(' ')));
  117.                 if (temp > map_width) map_width = temp;
  118.  
  119.                 temp = Integer.parseInt(line.substring(line.indexOf(' ')+1,line.lastIndexOf(' ')));
  120.                 if (temp > map_height) map_height = temp;
  121.  
  122.                 line = reader.readLine();
  123.             }while(line != null);
  124.         }catch(IOException e){
  125.             System.out.println("ERROR: Fallo al leer el archivo '"+fileName+"'.");
  126.         }
  127.         int[] result = {map_width,map_height};
  128.         closeFile();
  129.         return result;
  130.     }
  131.  
  132.     //Populate the matrix with the values in the file "fileName".
  133.     public static void populateMatrix(){
  134.         int temp_x;
  135.         int temp_y;
  136.         int value;
  137.         String line;
  138.  
  139.         openFile(fileName);
  140.  
  141.         try{
  142.             line = reader.readLine();
  143.             do{
  144.                 temp_x = Integer.parseInt(line.substring(0,line.indexOf(' ')));
  145.                 temp_y = Integer.parseInt(line.substring(line.indexOf(' ')+1,line.lastIndexOf(' ')));
  146.                 value = Integer.parseInt(line.substring(line.lastIndexOf(' ')+1));
  147.                
  148.                 matrix[temp_y][temp_x] = value;
  149.  
  150.                 line = reader.readLine();
  151.             }while(line != null);
  152.         }catch(IOException e){
  153.             System.out.println("ERROR: Fallo al leer el archivo '"+fileName+"'.");
  154.         }
  155.     }
  156.  
  157.     //Analiza la estructura de la matriz, reconoce las paredes que sirven
  158.     //para la evaluacion. Paredes seleccionadas utilizan el valor 32 en la matriz.
  159.     public static void setValidWalls(){
  160.         validWallCount = 0;
  161.  
  162.         for (int i = 0; i < matrix.length; i++){
  163.             for (int j = 0; j < matrix[i].length; j++){
  164.                 if(matrix[i][j] == 64){
  165.                     try{
  166.                         if(matrix[i][j+1] == 2 && matrix[i][j-1] == 0) matrix[i][j] = validWallValue;
  167.                         if(matrix[i][j-1] == 2 && matrix[i][j+1] == 0) matrix[i][j] = validWallValue;
  168.                         if(matrix[i+1][j] == 2 && matrix[i-1][j] == 0) matrix[i][j] = validWallValue;
  169.                         if(matrix[i-1][j] == 2 && matrix[i+1][j] == 0) matrix[i][j] = validWallValue;
  170.                         if(matrix[i][j] == validWallValue) validWallCount++;
  171.                     }catch(ArrayIndexOutOfBoundsException e){
  172.                         System.out.println("ADVERTENCIA: Pared detectada en los ejes de la matriz.");
  173.                     }
  174.                 }
  175.             }
  176.         }
  177.  
  178.     }
  179.  
  180.     //Genera 5 numeros al azar que sirven para elegir de forma aleatoriamente las coordenadas de
  181.     //5 paredes que esten categorizadas como validas en la matriz. El metodo devuelve un vector
  182.     //(array) de integrales de 10 valores que conforman las coordenadas de las paredes a usar, en el
  183.     //orden {x1,y1,x2,y2,x3,y3,x4,y4,x5,y5,time = 0}.
  184.     public static int[] generateRandomTestValues(){
  185.         Random rng = new Random();
  186.         //Propiedades de  Random: ints son minimo y maximo, distinct es que no se repitan, limit es
  187.         //la cantidad de randoms que se generara, exporta a un array.
  188.         int[] randomNum = new Random().ints(1, validWallCount+1).distinct().limit(5).toArray();
  189.         int[] randomCoord = new int[11];
  190.         int temp_count = 0;         //Cuenta desde 0 hasta la cantidad total de paredes validas.
  191.         int index_pointer = 0;      //Puntero para el array de cordinadas.
  192.  
  193.         for (int i = 0; i < matrix.length; i++){
  194.             for (int j = 0; j < matrix[i].length; j++){
  195.                 if(matrix[i][j] == validWallValue){
  196.                     temp_count++;
  197.                     if (arrayContains(randomNum,temp_count)){
  198.                         try{
  199.                             randomCoord[index_pointer] = i;
  200.                             randomCoord[index_pointer+1] = j;
  201.                             index_pointer = index_pointer +2;
  202.                         }catch(ArrayIndexOutOfBoundsException e){
  203.                             System.out.println("ERROR: Algo salio mal al obtener paredes al azar.");
  204.                         }
  205.                     }
  206.                 }
  207.             }
  208.         }
  209.         //System.out.println("Random: ("+randomCoord[0]+","+randomCoord[1]+") ("+randomCoord[2]+","+randomCoord[3]+") ("+randomCoord[4]+","+randomCoord[5]+") ("+randomCoord[6]+","+randomCoord[7]+") ("+randomCoord[8]+","+randomCoord[9]+").");
  210.  
  211.         return randomCoord;
  212.     }
  213.  
  214.     //Algoritmo de cruzamiento, se toman dos vectores llamados padres, y se genera
  215.     public static int[] crossValues(int[] parent1, int[] parent2){
  216.         Random rng = new Random();
  217.         int[] heritage = new Random().ints(0,2).limit(5).toArray();
  218.         int[] child = parent1.clone();
  219.         int index_pointer = 0;      //Puntero para el array de cordinadas.
  220.  
  221.         for(int k = 0; k < heritage.length; k++){
  222.             if(heritage[k] == 1){
  223.                 child[k*2] = parent2[k*2];
  224.                 child[k*2+1] = parent2[k*2+1];
  225.             }
  226.         }
  227.         child[10] = 0;
  228.         return child;
  229.     }
  230.  
  231.     //Algoritmo de mutación, selecciona una posición al azar del padre para tomar coordenadas (x,y) y posteriormente mutarlas
  232.     public static int[] mutateValue(int[] parent, int mutations){
  233.         Random rng = new Random();
  234.         for(int i=0;i<mutations;i++){
  235.             //selecciona par al azar
  236.             int index = rng.nextInt(5)*2;
  237.             int [] selected = {parent[index],parent[index+1]};
  238.             //selecciona una coordenada al azar y le suma un numero al azar entre -5 y 5
  239.             //si al sumar en una coordenada el resultado no es una pared válida, se repite el proceso para la otra coordenada
  240.             //si ninguna combinacion es valida, no se realizan cambios sobre el arreglo original
  241.             try{
  242.                 switch(rng.nextInt(2)){
  243.                     case 0:
  244.                     selected[0] += rng.nextInt(11)-5;
  245.                     if(matrix[selected[0]][parent[index+1]]==validWallValue){
  246.                         parent[index]=selected[0];
  247.                     }
  248.                     else{
  249.                         selected[1] += rng.nextInt(11)-5;
  250.                         if(matrix[parent[index]][selected[1]]==validWallValue){
  251.                             parent[index+1]=selected[1];
  252.                         }
  253.                     }
  254.                     break;
  255.  
  256.                     case 1:
  257.                     selected[1] += rng.nextInt(11)-5;
  258.                     if(matrix[parent[index]][selected[1]]==validWallValue){
  259.                         parent[index+1]=selected[1];
  260.                     }
  261.                     else{
  262.                         selected[0] += rng.nextInt(11)-5;
  263.                         if(matrix[selected[0]][parent[index+1]]==validWallValue){
  264.                             parent[index]=selected[0];
  265.                         }
  266.                     }
  267.                     break;
  268.                 }
  269.             }catch (ArrayIndexOutOfBoundsException e){
  270.                 System.out.println("ADVERTENCIA: La mutacion proboco salida de Arrays.");
  271.             }
  272.         }
  273.         return parent;
  274.     }
  275.  
  276.     //Revisa si el valor esta dentro de un array de INTs.
  277.     public static boolean arrayContains(int[] array, int value){
  278.         for(int x = 0; x < array.length; x++){
  279.             if(array[x] == value) return true;
  280.         }
  281.         return false;
  282.     }
  283.  
  284.     //Imprime la matriz en sistema. Los simbolos son:
  285.     // "_" : Espacio interior
  286.     // "." : Espacio exterior
  287.     // "X" : Pared interior
  288.     // "0" : Pared exterior (Valida)
  289.     public static void printMatrix(){
  290.         for (int i = 0; i < matrix.length; i++){
  291.             for (int j = 0; j < matrix[i].length; j++){
  292.                 if (matrix[i][j] == 64) System.out.print("X");
  293.                 else if (matrix[i][j] == 2) System.out.print(".");
  294.                 else if (matrix[i][j] == validWallValue) System.out.print("0");
  295.                 else System.out.print("_");
  296.             }System.out.println();
  297.         }
  298.     }
  299.    
  300.     //Abre el archivo de nombre "name" en el BufferedReader estatico.
  301.     public static void openFile(String name){
  302.         try{
  303.             reader = new BufferedReader(new FileReader(name)); 
  304.         }catch(IOException e){
  305.             System.out.println("ERROR: Archivo '"+name+"' no existe.");
  306.         }
  307.     }
  308.  
  309.     //Cierra el archivo actual en el BufferedReader estatico.
  310.     public static void closeFile(){
  311.         try{
  312.             reader.close();
  313.         }catch (IOException e){
  314.             System.out.println("ERROR: Fallo al cerrar el archivo.");
  315.         }
  316.     }
  317.  
  318.     //Genera el archivo "doors.plan" con las coordenadas especificadas en
  319.     //el argumento de entrada, en el orden (x1,y1,x2,y2,x3,y3,x4,y4,x5,y5)
  320.     public static void writeDoorsPlan(int[] coords){
  321.         try{
  322.             PrintWriter writer = new PrintWriter("doors.plan", "UTF-8");
  323.             for(int z = 0; z < 10; z = z + 2) writer.println(coords[z]+" "+coords[z+1]);
  324.             writer.close();
  325.         }catch (IOException e) {
  326.            System.out.println("ERROR: Fallo al escribir doors.plan en el dispositivo. ("+e.getMessage()+")" );
  327.         }catch (ArrayIndexOutOfBoundsException e){
  328.             System.out.println("ERROR: Algo salio mal leer los indices de las cordenadas. ("+e.getMessage()+")");
  329.         }
  330.     }
  331.  
  332.     public static void writeTimeout(){
  333.         try{
  334.             PrintWriter writer = new PrintWriter("seconds.output", "UTF-8");
  335.             writer.println("999999");
  336.             writer.close();
  337.         }catch (IOException e) {
  338.            System.out.println("ERROR: Fallo al escribir seconds.output en el dispositivo. ("+e.getMessage()+")" );
  339.         }
  340.     }
  341.     //Lee el archivo "seconds.output" que genera NetLogo, devuelve el tiempo en el archivo.
  342.     public static int readDoorsTime(){
  343.         int time = -1;
  344.         openFile("seconds.output");
  345.         try{
  346.             time = Integer.parseInt(reader.readLine());
  347.         }catch (IOException e){
  348.             System.out.println("ERROR: Problema al leer el valor del archivo seconds.output.");
  349.         }
  350.         closeFile();
  351.         return time;
  352.     }
  353.  
  354.     //Ejecuta NetLogo en linea de comando
  355.     public static void execNetLogo(){
  356.         try {
  357.             System.out.println("Simulando...");
  358.             Process p = Runtime.getRuntime().exec("java -Xmx1024m -Dfile.encoding=UTF-8 -cp NetLogo.jar org.nlogo.headless.Main --model escape4.nlogo --experiment simulation");
  359.             if(!p.waitFor(10, TimeUnit.SECONDS)) {
  360.                 p.destroy();
  361.                 System.out.println("ADVERTENCIA: Expiro el tiempo de simulación.");
  362.                 writeTimeout();
  363.             }else{
  364.                 System.out.println("Simulacion completa.");
  365.             }
  366.         } catch (IOException ex) {
  367.             System.out.println("ERROR: "+ex);
  368.         } catch (InterruptedException ie){
  369.             System.out.println("ERROR: "+ie);
  370.         }
  371.     }
  372.  
  373.     //Determina los dos numeros mas pequeños entre 4, utilizado para determinar los nuevos
  374.     //padres en el cruzamiento. El numero usa la escala binaria para representar los dos
  375.     //numeros (num1 = 1, num2 = 2, num3= 4, num4= 8).
  376.     public static int compareNum(int num1, int num2, int num3, int num4){
  377.         if(num1 < num2 && num1 < num3 && num1 < num4){
  378.             if(num2 < num3 && num2 < num4) return 3;
  379.             else if(num3 < num4) return 5;
  380.             else return 9;
  381.         }else if (num2 < num3 && num2 < num4){
  382.             if(num1 < num3 && num1 < num4) return 3;
  383.             else if(num3 < num4) return 6;
  384.             else return 10;
  385.         }else if (num3 < num4){
  386.             if(num1 < num2 && num1 < num4) return 5;
  387.             else if(num2 < num4) return 6;
  388.             else return 12;
  389.         }else{
  390.             if(num1 < num2 && num1 < num3) return 9;
  391.             else if(num2 < num3) return 10;
  392.             else return 12;
  393.         }
  394.     }
  395.     public static void writeList(){
  396.         int[] temp;
  397.         try{
  398.             PrintWriter writer = new PrintWriter("log.csv", "UTF-8");
  399.             for(int z = 0; z < list.size(); z++){
  400.                 temp = list.get(z);
  401.                 writer.print(temp[10]);
  402.                 if(z != list.size()-1) writer.print(",");
  403.             }
  404.             writer.println();
  405.             writer.close();
  406.         }catch (IOException e) {
  407.            System.out.println("ERROR: Fallo al escribir doors.plan en el dispositivo. ("+e.getMessage()+")" );
  408.         }catch (ArrayIndexOutOfBoundsException e){
  409.             System.out.println("ERROR: Algo salio mal leer los indices de las cordenadas. ("+e.getMessage()+")");
  410.         }
  411.     }
  412. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!