Pasar un array de valores numéricos a escala percentual - atributo continuo -

Siguiendo con el post anterior esta vez se intentará reestructurar el código anterior y añadir la función "DiscretizarFine" que consiste en añadir en el rango mínimo y máximo (que son indeterminados) la media de los espacios que existen entre todos los valores del array. Esto en teoría afinaría en la precisión en el machine learning.


* Ejemplo gráfico para ver las diferencias entre los distintos modelos:

Código Java 1 (BloggerDiscretizar2.java):

package bloggerdiscretizar2;

import java.util.Arrays;

public class BloggerDiscretizar2 {
  
   public static void main(String[] args) {

      Array arr = new Array();

      double v_inicial[] = new double[16];
      double v_discretizar[] = new double[16];
      double v_discretizarFine[] = new double[16];

      for (int i = 0; i < v_inicial.length; i++) {
         v_inicial[i] = (double) Math.random() * 512;
      }
     
      //copiar v_inicial
      System.arraycopy(v_inicial, 0, v_discretizar, 0, v_inicial.length);
      System.arraycopy(v_inicial, 0, v_discretizarFine, 0, v_inicial.length);

      //discretizar percentual
      v_discretizar = arr.toDiscretizar(v_inicial);
      v_discretizarFine = arr.toDiscretizarFine(v_inicial);
     
      //ordenar arrays de menor a mayor
      Arrays.sort(v_inicial);
      Arrays.sort(v_discretizar);
      Arrays.sort(v_discretizarFine);
     
      //mostrar resultados
      System.out.println("vector inicial:");
      for (int i = 0; i < v_inicial.length; i++) {        
         System.out.println(v_inicial[i]);        
      }
     
      System.out.println("\nvector discretizado (atributo discreto):");
      for (int i = 0; i < v_discretizar.length; i++) {
         System.out.println(v_discretizar[i]);
      }
     
      System.out.println("\nvector discretizado_fino (atributo continuo):");
      for (int i = 0; i < v_discretizarFine.length; i++) {
         System.out.println(v_discretizarFine[i]);
      }

   }

}

Código Java 2 (Array.java):

bloggerdiscretizar2;

public class Array {

     /*
   Transformar un campo numérico a categórico usando percentiles
   Atributo discreto tiene un número finito o contable de valores   
    */
   public double[] toDiscretizar(double[] array) {
      double[] array2 = new double[array.length];
      //obtener min y max apartir del array base
      double min = this.getMin(array);
      double max = this.getMax(array);
      for (int i = 0; i < array.length; i++) {
         array2[i] = (array[i] - min) / (max - min);
      }
      return array2;
   }

   /*
   Transformar un campo numérico a categórico usando percentiles (afinado)
   Atributo continuo tiene un número indeterminado de valores (no se sabe el valor min ni el max)
    */
   public double[] toDiscretizarFine(double[] array) {
      double[] array2 = new double[array.length];
      double[] array3 = new double[array.length + 2];
      for (int i = 0; i < array.length - 1; i++) {
         array2[i] = array[i] - array[i + 1];//distancia entre valores
      }
      System.arraycopy(array, 0, array3, 2, array.length);

      //calculo aproximado del min y max y se añade al array
      array3[0] = this.getMin(array) - this.getMed(array2); //min
      array3[1] = this.getMax(array) + this.getMed(array2); //max
      return this.toDiscretizar(array3);
   }

   public double getMin(double[] array) {
      double min = array[0];
      for (int i = 0; i < array.length; i++) {
         if (min > array[i]) {
            min = array[i];
         }
      }
      return min;
   }

   public double getMax(double[] array) {
      double max = array[0];
      for (int i = 0; i < array.length; i++) {
         if (max < array[i]) {
            max = array[i];
         }
      }
      return max;
   }

   public double getMed(double[] array) {
      double med = 0;
      for (int i = 0; i < array.length; i++) {
         med = med + array[i];
      }
      return med / array.length;
   }

}


Resultado:

run:
vector inicial:
6.915959656
27.4665411
106.4488495
111.8923782
146.6526326
178.1616741
185.2529849
203.4995067
223.2984554
250.5640114
262.7295496
272.2483547
319.3729241
436.0795028
441.7362144
461.5955789

vector discretizado (atributo discreto):
0
0.045197938
0.218907744
0.230879974
0.307329968
0.376629405
0.392225685
0.432356188
0.475901023
0.535867546
0.562623833
0.583559025
0.687202486
0.943881197
0.95632229
1

vector discretizado_fino (atributo continuo):
0
0.030742192
0.073161163
0.236190529
0.247426653
0.319176167
0.38421477
0.398852123
0.436515226
0.477382733
0.533662252
0.558773445
0.578421449
0.675692456
0.916589435
0.928265595
0.969257808
1
BUILD SUCCESSFUL (total time: 0 seconds)

Nota: Atributo continuo: Tiene un rango indeterminado de valores posibles.

Pasar un array de valores numéricos a escala percentual - atributo discreto -

En machine learning se le llama "discretizar array por percentiles", que consiste en uniformizar los valores numéricos de un array a escala [0:1]. Esta transformación es usada para ayudar en el aprendizaje automático de máquinas (machine learning) ya que adapta los términos absolutos del array a términos porcentuales.

Ejemplo:

Arrays iniciales:

    array1 (numérico):    0        1       2       5       7       10
    array2 (numérico):    653.7    1382    2403    4214    8890    9935
    ...
    ...

Arrays ya uniformizados (discretizados por percentiles):

    array1 (percentil):    0%      0.1%    0.2%    0.5%    0.7%    1%   
    array2 (percentil):    0%      0.07%   0.18%   0.38%   0.89%   1%
    ...
    ...

La diferencia entre los valores del array1 y array2 iniciales son dispares. Una vez transformados los campos numéricos a percentiles se observa de que los campos son más semejantes entre sí (misma escala).


Código java: (DiscretizarNormalizar.java)

//Transformar un campo numérico a categórico usando percentiles
package discretizarnormalizar;

public class DiscretizarNormalizar {

   public static void main(String[] args) {

      int nRegistros = 10;
      double[] v = new double[nRegistros];

      //crear array aleatorio
      for (int i = 0; i < nRegistros; i++) {
         v[i] = Math.random() * 10000;
      }

      //buscar valores minimos y maximos del array
      double min = v[0];
      double max = v[0];
      for (int i = 0; i < nRegistros; i++) {
         if (min > v[i]) {
            min = v[i];
         }
         if (max < v[i]) {
            max = v[i];
         }
      }

      //normalizacion-descretizar?
      double[] v2 = new double[nRegistros];
      for (int i = 0; i < nRegistros; i++) {
         v2[i] = (v[i] - min) / (max - min);
      }

      //mostrar resultado
      System.out.println("Array inicial:\t\tArray transformado:");
      for (int i = 0; i < nRegistros; i++) {
         System.out.println(i + "- " + v[i] + "\t" + v2[i]);
      }

   }

}


Resultado:

run:
Array inicial:          Array transformado:
0- 7671.886736201123    0.8019001791662852
1- 9479.117533535893    1.0
2- 4876.0856974944645   0.4954381126326166
3- 6808.418910630855    0.7072510497947576
4- 356.28849851238044   0.0
5- 6556.185784681601    0.6796024854096415
6- 5931.890253043281    0.6111702557535137
7- 8510.956094814934    0.8938748676529962
8- 589.2424296425359    0.02553527313027795
9- 1432.7279151298521   0.11799403589444743
BUILD SUCCESSFUL (total time: 0 seconds)


Nota: Atributo discreto: tiene un rango finito o contable de valores.

Copiar arrays. Uso de la instrucción "System.arraycopy".

Código java (CopiaArray.java):

package copiaarray;

public class CopiaArray {

   public static void main(String[] args) {

      double[] array1 = new double[5];
      double[] array2 = new double[10];
      double[] array3 = new double[array1.length + array2.length];

      //rellena array1
      for (int i = 0; i < array1.length; i++) {
         array1[i] = i;
      }

      //rellena array2
      for (int i = 0; i < array2.length; i++) {
         array2[i] = Math.random();
      }

      /*
         Parametros del System.arraycopy:
         Array origen,
         Posición inicial del array origen,
         Array destino,
         Posición incial en el array de destino,
         Numero de elementos a copiar del array origen al array destino
       */
     
      System.arraycopy(array1, 0, array3, 0, array1.length);
      System.arraycopy(array2, 0, array3, array1.length, array2.length);

      //mostrar resultados
      System.out.println("\nArray1");
      for (int i = 0; i < array1.length; i++) {
         System.out.println(i + "- " + array1[i]);
      }

      System.out.println("\nArray2");
      for (int i = 0; i < array2.length; i++) {
         System.out.println(i + "- " + array2[i]);
      }

      System.out.println("\nArray3");
      for (int i = 0; i < array3.length; i++) {
         System.out.println(i + "- " + array3[i]);
      }

   }

}


Resultado:

run:

Array1
0- 0.0
1- 1.0
2- 2.0
3- 3.0
4- 4.0

Array2
0- 0.5287887048803938
1- 0.46771014928163135
2- 0.8333523729100707
3- 0.4965787587571521
4- 0.26861092247251583
5- 0.822652997195613
6- 0.5053721779352607
7- 0.896713025382418
8- 0.9093387247823286
9- 0.8910677970677133

Array3
0- 0.0
1- 1.0
2- 2.0
3- 3.0
4- 4.0
5- 0.5287887048803938
6- 0.46771014928163135
7- 0.8333523729100707
8- 0.4965787587571521
9- 0.26861092247251583
10- 0.822652997195613
11- 0.5053721779352607
12- 0.896713025382418
13- 0.9093387247823286
14- 0.8910677970677133
BUILD SUCCESSFUL (total time: 0 seconds)

Generación de un número aleatorio basado en una función de probabilidad.

El siguiente algoritmo genera números aleatorios no uniformes. La premisa es dar un porcentaje de probabilidad para que aparezca cierto número en un rango dado.

Ejemplo:
Generar un número aleatorio del 1 al 350 del cual el número 56 tenga un 34.9% de probabilidad de que salga elegido. Las entradas serían las siguientes:

rango = 350
numero = 56
ratio = 0.349


Código Java 1 (AleatorioCondicionado1.java)

package aleatoriocondicionado1;

public class AleatorioCondicionado1 {

   public static void main(String[] args) {

      RandA randa = new RandA();     
      int max = 350;
      int num = 56;
      float ratio = 0.349F;
      int valor = randa.getRandA(max, num, ratio);
     
      System.out.println("Rango: [1:" + max + "]");
      System.out.println("Numero: " + num);
      System.out.println("Ratio%: " + ratio);     
      System.out.println("Valor obtenido: " + valor);

   }

}


Código Java 2 (RandA.java):

package aleatoriocondicionado1;

import java.util.Random;

public class RandA {

   Random r = new Random();

   int getRandA(int max, int num, float ratio) {
      float x;
      int rand = r.nextInt(max) + 1;
      x = max * ratio;
      if (rand <= x) {
         return num;
      } else {
         do {
            rand = r.nextInt(max) + 1;
         } while (rand == num);
         return rand;
      }
   }

}
 

Resultado:

run:
Rango: [1:350]
Numero: 56
Ratio%: 0.349
Valor obtenido: 56
BUILD SUCCESSFUL (total time: 1 second)

Nota: Si ejecutamos muchas veces el mismo código se comprueba de que el número 56 tiende a salir en una proporción mayor al resto de números, concretamente saldría en un 34.9 % de los casos.

Cálculo del grado de similitud entre dos palabras. Distancia de Levenshtein.

Una forma para obtener el grado de similitud entre dos palabras distintas es calculando la distancia de Levenshtein, que consiste en calcular el número mínimo de operaciones necesarias para transformar una cadena de caracteres en otra. Obtenida esta distancia podemos calcular fácilmente el grado de similitud porcentual (afinidad) entre las dos palabras:

Afinidad = 1 - (D / L)

D: Distancia de Levenshtein.
L: Longitud de la palabra más larga. 


Código Java 1: (Levenshtein1.java)

// Calculo del grado de similitud entre dos palabras distintas.
package levenshtein1;

public class Levenshtein1 {

   public static void main(String[] args) {

      String str1 = "identificar";
      String str2 = "identify";

      LevenshteinDistance ld = new LevenshteinDistance();
      ld.setWords(str1, str2);

      // Mostrar resultados
      System.out.println("Palabra1: " + str1);
      System.out.println("Palabra2: " + str2);
      System.out.println("\nDistancia de Levenshtein:\n" + ld.getDistancia());
      System.out.println("Afinidad:\n" + ld.getAfinidad() * 100 + " %");

   }

}


Código Java 2: (LevenshteinDistance.java)

package levenshtein1;

public class LevenshteinDistance {

   private String str1;
   private String str2;
   private int distancia;
   private int[][] matriz;

   public void setWords(String str1, String str2) {
      this.str1 = str1.toLowerCase();
      this.str2 = str2.toLowerCase();
      calculoLevenshtein();
   }

   public int getDistancia() {
      return distancia;
   }

   public float getAfinidad() {
      float longitud = str1.length() > str2.length() ? str1.length() : str2.length();
      return 1 - (distancia / longitud);
   }

   private void calculoLevenshtein() {
      matriz = new int[str1.length() + 1][str2.length() + 1];
      for (int i = 0; i <= str1.length(); i++) {
         matriz[i][0] = i;
      }
      for (int j = 0; j <= str2.length(); j++) {
         matriz[0][j] = j;
      }
      for (int i = 1; i < matriz.length; i++) {
         for (int j = 1; j < matriz[i].length; j++) {
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
               matriz[i][j] = matriz[i - 1][j - 1];
            } else {
               int min = Integer.MAX_VALUE;
               if ((matriz[i - 1][j]) + 1 < min) {
                  min = (matriz[i - 1][j]) + 1;
               }
               if ((matriz[i][j - 1]) + 1 < min) {
                  min = (matriz[i][j - 1]) + 1;
               }
               if ((matriz[i - 1][j - 1]) + 1 < min) {
                  min = (matriz[i - 1][j - 1]) + 1;
               }
               matriz[i][j] = min;
            }
         }
      }
      distancia = matriz[str1.length()][str2.length()];
   }

}


Resultado:

run:
Palabra1: identificar
Palabra2: identify

Distancia de Levenshtein: 4
Afinidad: 63.636364 %
BUILD SUCCESSFUL (total time: 0 seconds)

Tests de eficiencia sobre algoritmos de creación de números aleatorios sin repetición.

Código Java (AleatorioSinRepeticion1.java):

/**
 * Tests de eficiencia sobre diferentes algoritmos de creación de números
 * aleatorios sin repetición.
 */

package aleatoriosinrepeticion1;

import java.util.Random;
import java.util.Stack;

public class AleatorioSinRepeticion1 {

    public static void main(String[] args) {

        long precision = 1000000;
        int nNodos = 13;

        test1(nNodos, precision);// Eficiencia base
        test2(nNodos, precision);// Eficiencia +620%
        test3(nNodos, precision);// Eficiencia +1156%

    }

    private static void test1(int nNodos, long precision) {

        int perm[] = new int[nNodos];
        int pos;

        long tiempo1 = System.nanoTime();
        for (int k = 0; k < precision; k++) {
            Stack<Integer> pRuta = new Stack<Integer>();
            for (int i = 0; i < nNodos; i++) {
                pos = (int) Math.floor(Math.random() * nNodos);
                while (pRuta.contains(pos)) {
                    pos = (int) Math.floor(Math.random() * nNodos);
                }
                pRuta.push(pos);
                perm[i] = pos;
            }
        }
        long tiempo2 = System.nanoTime();

        System.out.println("Tiempo1: " + (tiempo2 - tiempo1) / 1e6 + " ms");
    }

    private static void test2(int nNodos, long precision) {

        Stack<Integer> pRef = new Stack<Integer>();
        int perm[] = new int[nNodos];
        Random rnd = new Random();
        int pos;

        long tiempo1 = System.nanoTime();
        for (int k = 0; k < precision; k++) {
            for (int i = 0; i < nNodos; i++) {
                pRef.add(i);
            }
            for (int i = 0; i < nNodos; i++) {
                pos = rnd.nextInt(pRef.size());
                perm[i] = pRef.remove(pos);
            }
        }
        long tiempo2 = System.nanoTime();

        System.out.println("Tiempo2: " + (tiempo2 - tiempo1) / 1e6 + " ms");
    }

    private static void test3(int nNodos, long precision) {

        int[] aux_perm = new int[nNodos];
        Random rnd = new Random();
        int[] perm = new int[nNodos];
        int aux_nNodos = nNodos;
        int pos;

        long tiempo1 = System.nanoTime();
        for (int index = 0; index < precision; index++) {
            aux_nNodos = nNodos;
            for (int i = 0; i < nNodos; i++) {
                aux_perm[i] = i + 1;
            }
            for (int i = 0; i < nNodos; i++) {
                pos = rnd.nextInt(aux_nNodos);
                perm[i] = aux_perm[pos] - 1;
                aux_perm[pos] = aux_perm[aux_nNodos - 1];
                aux_nNodos--;
            }
        }
        long tiempo2 = System.nanoTime();

        System.out.println("Tiempo3: " + (tiempo2 - tiempo1) / 1e6 + " ms");
    }

}

Resultado:

run:

Tiempo1: 9470.44684 ms

Tiempo2: 1515.179325 ms

Tiempo3: 823.204608 ms

BUILD SUCCESSFUL (total time: 11 seconds)

Uso CPU Multinúcleo. Cálculo TSP por el Método Montecarlo.

Este es un ejemplo de cálculo del TSP utilizando método Montecarlo y ejecución de N hilos simultáneos. Para ello se dispone de un apartado de configuración donde se pondrá el número de hilos a ejecutar simultáneamente y la precisión (número de interacciones). A más interacciones, mayor precisión en los cálculos.


* Entrada de parámetros de configuración:

  >Parámetro 1 (Número de CPUs/Hilos):
  Mi PC consta de una CPU Intel Core 2 Duo (2 núcleos), por lo que lo ideal en este caso seria indicarle 2 Hilos (Fig.1)
  

Fig 1. Test velocidad según número de hilos ejecutados simultáneamente [sobre una CPU Intel Core 2 Duo]

  >Parámetro 2 (Precisión):

  En el ejemplo consta de 13 nodos que permite hasta un total de 6.227.020.800 rutas distintas. Si le indicamos una precisión de 100.000.000 interacciones obtendremos una ruta bastante óptima con un 18.84% de probabilidades de dar con la ruta más corta posible.

Fig. 2 - Relación entre el Número Interacciones (método Montecarlo) con el % de probabilidades de dar con la ruta más óptima posible.

Código 1 (TSP_Optimizar.java):

package tsp_optimitzar;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class TSP_Optimitzar {

    @SuppressWarnings("empty-statement")
    public static void main(String[] args) throws InterruptedException {
        String[] nombre_nodos = {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M"};
        int nNodos = nombre_nodos.length;

        System.out.println("Configuración:\n");
        System.out.println(">Número de CPUs/Hilos?");
        Scanner reader = new Scanner(System.in);
        int nHilos = Integer.parseInt(reader.next());
        System.out.println(">Precisión?");
        reader = new Scanner(System.in);
        double precision = Double.parseDouble(reader.next());

        float[] vDistancias = {
            0.0F, 820.8666F, 475.23F, 630.9444F, 175.44064F, 360.75314F, 755.7496F, 186.8207F, 591.06683F, 298.11227F, 681.6526F, 289.17914F, 995.64746F,
            8.357133F, 0.0F, 366.78992F, 83.80908F, 217.9351F, 237.86781F, 581.63153F, 925.394F, 453.48624F, 636.67017F, 200.24031F, 695.21234F, 890.6944F,
            70.59399F, 368.34445F, 0.0F, 764.7878F, 182.2146F, 93.2886F, 194.98314F, 180.56621F, 363.5746F, 443.70917F, 641.6165F, 549.982F, 931.1095F,
            874.7707F, 874.603F, 605.9038F, 0.0F, 25.786762F, 147.78946F, 533.5506F, 47.42154F, 108.01653F, 471.1008F, 261.24738F, 656.25104F, 99.16098F,
            4.8551674F, 361.6684F, 245.69385F, 652.172F, 0.0F, 100.449036F, 633.9419F, 670.09125F, 150.59242F, 907.34863F, 275.1372F, 938.0571F, 38.05818F,
            652.2065F, 238.30981F, 927.4687F, 318.43414F, 429.15936F, 0.0F, 595.4067F, 431.22238F, 388.80447F, 283.0264F, 249.39452F, 8.14694F, 899.722F,
            671.8014F, 811.3296F, 355.1809F, 8.395913F, 157.35182F, 596.0345F, 0.0F, 306.99182F, 192.86949F, 298.59897F, 432.59073F, 633.6216F, 817.70074F,
            301.66046F, 462.99008F, 147.49551F, 730.2186F, 902.4855F, 160.01877F, 485.22964F, 0.0F, 495.07837F, 358.40677F, 555.7709F, 983.111F, 318.58316F,
            160.77138F, 3.104256F, 998.9104F, 310.08047F, 295.39194F, 466.86356F, 673.8137F, 499.67224F, 0.0F, 423.98648F, 855.799F, 779.7313F, 947.50555F,
            372.0423F, 715.80835F, 866.05927F, 57.02963F, 696.6522F, 65.42037F, 388.12494F, 826.8198F, 912.82697F, 0.0F, 304.32504F, 886.0547F, 788.8762F,
            157.58907F, 235.23514F, 575.64496F, 682.70575F, 689.79407F, 57.43567F, 877.0111F, 659.9925F, 658.1151F, 196.0468F, 0.0F, 549.32043F, 440.2496F,
            957.9573F, 699.2848F, 57.796417F, 461.52716F, 881.24054F, 752.86084F, 748.3989F, 42.0304F, 459.0128F, 424.106F, 206.15532F, 0.0F, 386.36868F,
            69.71372F, 877.4519F, 881.0224F, 954.1217F, 924.6164F, 813.5333F, 743.41473F, 956.4676F, 509.52542F, 867.4073F, 202.12968F, 515.76715F, 0.0F};


        List<String> lista_nombre_nodos = new ArrayList<>();
        lista_nombre_nodos.addAll(Arrays.asList(nombre_nodos));
        
        // mostrar tabla distancias
        tDistancias(vDistancias, nNodos);

        System.out.println("\nCalculando...");
        long tiempo1 = System.nanoTime();
        TSP_Montecarlo tsp[] = new TSP_Montecarlo[nHilos];
        for (int i = 0; i < nHilos; i++) {
            tsp[i] = new TSP_Montecarlo(lista_nombre_nodos, vDistancias, precision, nHilos);
            tsp[i].start();
        }

        // Control de finalización hilos
        int cont;
        do {
            try { // +15%
                Thread.sleep(500);
            } catch (Exception e) {
            }
            cont = 0;
            for (int i = 0; i < nHilos; i++) {
                if (!tsp[i].isAlive()) {
                    cont++;
                }
            }
        } while (cont != nHilos);

        long tiempo2 = System.nanoTime();

        // Balance final hilos
        float minimo = Float.MAX_VALUE;
        String ruta = "";
        System.out.println("\nResultados Hilos:");
        for (int i = 0; i < nHilos; i++) {
            System.out.println("Thread " + i + ": " + tsp[i].getDistancia());
            if (tsp[i].getDistancia() < minimo) {
                minimo = tsp[i].getDistancia();
                ruta = tsp[i].getRuta();
            }
        }

        // Mostrar resultados
        System.out.println("\nResultado más óptimo encontrado: ");
        System.out.println("Ruta: " + ruta + "\nDistancia: " + minimo);
        System.out.println("Tiempo empleado: " + (tiempo2 - tiempo1) / 1e6 + " ms");

    }

    private static void tDistancias(float[] vDistancias, int n) {
        n = (int) Math.sqrt(vDistancias.length);
        double[][] tabla = new double[n][n];
        String str;
        int cont = 0;
        System.out.println("\nTabla distancias:");
        for (int x = 0; x < n; x++) {
            str = "| ";
            for (int y = 0; y < n; y++) {
                tabla[y][x] = vDistancias[cont];
                str += tabla[y][x] + " | ";
                cont++;
            }
            System.out.println(str);
        }
    }

}

Código 2 (TSP_Montecarlo.java):

package tsp_optimitzar;

import java.util.List;

import java.util.Random;

public class TSP_Montecarlo extends Thread {

    // Entradas

    private final List<String> lista_nombre_nodos;

    private final float[] v_distancias;

    private final double precision;

    // Resto variables 

    private float minimo = Float.MAX_VALUE;

    private float sumatorio = 0;

    private int[] vRuta = null;

    private final int nNodos;

    // Contructor

    public TSP_Montecarlo(List<String> lista_nombre_nodos, float[] v_distancias, double precision, int nHilos) {

        this.lista_nombre_nodos = lista_nombre_nodos;

        this.nNodos = lista_nombre_nodos.size();

        this.v_distancias = v_distancias;

        this.precision = Math.abs(precision / nHilos);

    }

    @Override

    public void run() {

        // Control parametros correctos

        if (lista_nombre_nodos.size() == Math.sqrt(v_distancias.length)) {

            float[][] t_distancias = conversorVT(v_distancias);

            int[] aux_perm = new int[nNodos];

            int[] perm = new int[nNodos];

            Random rnd = new Random();

            int aux_nNodos = nNodos;

            int cont = 0;

            int res;

            do {

                sumatorio = 0;

                // Busqueda de rutas aleatorias evitando repeticiones de nodos.

                // +1338%

                aux_nNodos = nNodos;

                for (int i = 0; i < nNodos; i++) {

                    aux_perm[i] = i + 1;

                }

                for (int i = 0; i < nNodos; i++) {

                    res = rnd.nextInt(aux_nNodos);

                    perm[i] = aux_perm[res] - 1;

                    aux_perm[res] = aux_perm[aux_nNodos - 1];

                    aux_nNodos--;

                }

                

                sumatorio += t_distancias[perm[nNodos - 1]][perm[0]];

                for (int i = 0; i < (nNodos - 1); i++) {

                    sumatorio += t_distancias[perm[i]][perm[i + 1]];

                    if (sumatorio > minimo) { // +200%

                        break;

                    }

                }

                if (sumatorio < minimo) {

                    minimo = sumatorio;

                    vRuta = perm.clone();

                }

            } while (cont++ < precision);

        }

    }

    public float[][] conversorVT(float[] v_distancias) {

        float[][] t_distancias = new float[nNodos][nNodos];

        int cont = 0;

        for (int i = 0; i < nNodos; i++) {

            for (int j = 0; j < nNodos; j++) {

                t_distancias[j][i] = v_distancias[cont];

                cont++;

            }

        }

        return t_distancias;

    }

    public float getDistancia() {

        return minimo;

    }

    public String getRuta() {

        String ruta = lista_nombre_nodos.get(vRuta[0]) + " - ";

        for (int i = 1; i < nNodos - 1; i++) {

            ruta += lista_nombre_nodos.get(vRuta[i]) + " - ";

        }

        ruta += lista_nombre_nodos.get(vRuta[nNodos - 1]);

        return ruta;

    }

}

Resultado:

run:

Configuración:
>Número de CPUs/Hilos? 
2
>Precisión? 
100000000

Tabla distancias:
| 0.0 | 820.8665771484375 | 475.2300109863281 | 630.9443969726562 | 175.44064331054688 | 360.7531433105469 | 755.7495727539062 | 186.82069396972656 | 591.0668334960938 | 298.1122741699219 | 681.652587890625 | 289.17913818359375 | 995.6474609375 | 
| 8.357132911682129 | 0.0 | 366.7899169921875 | 83.80908203125 | 217.9351043701172 | 237.86781311035156 | 581.6315307617188 | 925.3939819335938 | 453.4862365722656 | 636.670166015625 | 200.2403106689453 | 695.2123413085938 | 890.6943969726562 | 
| 70.59398651123047 | 368.3444519042969 | 0.0 | 764.7877807617188 | 182.214599609375 | 93.2885971069336 | 194.98313903808594 | 180.5662078857422 | 363.5745849609375 | 443.70916748046875 | 641.6165161132812 | 549.9819946289062 | 931.1094970703125 | 
| 874.7706909179688 | 874.60302734375 | 605.90380859375 | 0.0 | 25.786762237548828 | 147.78945922851562 | 533.5505981445312 | 47.421539306640625 | 108.01653289794922 | 471.1007995605469 | 261.24737548828125 | 656.2510375976562 | 99.16098022460938 | 
| 4.855167388916016 | 361.66839599609375 | 245.69384765625 | 652.1719970703125 | 0.0 | 100.44903564453125 | 633.94189453125 | 670.0912475585938 | 150.59242248535156 | 907.3486328125 | 275.13720703125 | 938.05712890625 | 38.05818176269531 | 
| 652.2064819335938 | 238.309814453125 | 927.4686889648438 | 318.43414306640625 | 429.15936279296875 | 0.0 | 595.4066772460938 | 431.2223815917969 | 388.8044738769531 | 283.0263977050781 | 249.39451599121094 | 8.146940231323242 | 899.7219848632812 | 
| 671.8013916015625 | 811.32958984375 | 355.180908203125 | 8.395913124084473 | 157.35182189941406 | 596.0344848632812 | 0.0 | 306.9918212890625 | 192.86949157714844 | 298.5989685058594 | 432.5907287597656 | 633.62158203125 | 817.7007446289062 | 
| 301.66046142578125 | 462.9900817871094 | 147.49551391601562 | 730.2186279296875 | 902.4854736328125 | 160.01876831054688 | 485.2296447753906 | 0.0 | 495.078369140625 | 358.4067687988281 | 555.7708740234375 | 983.1110229492188 | 318.5831604003906 | 
| 160.77137756347656 | 3.1042559146881104 | 998.910400390625 | 310.0804748535156 | 295.3919372558594 | 466.8635559082031 | 673.813720703125 | 499.6722412109375 | 0.0 | 423.9864807128906 | 855.7990112304688 | 779.7313232421875 | 947.5055541992188 | 
| 372.04229736328125 | 715.808349609375 | 866.0592651367188 | 57.02962875366211 | 696.6522216796875 | 65.42037200927734 | 388.12493896484375 | 826.81982421875 | 912.8269653320312 | 0.0 | 304.3250427246094 | 886.0546875 | 788.876220703125 | 
| 157.5890655517578 | 235.23513793945312 | 575.6449584960938 | 682.7057495117188 | 689.7940673828125 | 57.4356689453125 | 877.0111083984375 | 659.9924926757812 | 658.1151123046875 | 196.0467987060547 | 0.0 | 549.3204345703125 | 440.2496032714844 | 
| 957.957275390625 | 699.2847900390625 | 57.796417236328125 | 461.52716064453125 | 881.2405395507812 | 752.86083984375 | 748.39892578125 | 42.030399322509766 | 459.0127868652344 | 424.1059875488281 | 206.1553192138672 | 0.0 | 386.3686828613281 | 
| 69.7137222290039 | 877.451904296875 | 881.0223999023438 | 954.1217041015625 | 924.6163940429688 | 813.5333251953125 | 743.4147338867188 | 956.4675903320312 | 509.5254211425781 | 867.4072875976562 | 202.1296844482422 | 515.7671508789062 | 0.0 | 

Calculando...

Resultados Hilos:
Thread 0: 1497.1041
Thread 1: 1340.8267

Resultado más óptimo encontrado: 
Ruta: M - E - A - B - I - D - J - G - C - H - L - F - K - 
Distancia: 1340.8267
Tiempo empleado: 44039.191597 ms
BUILD SUCCESSFUL (total time: 56 seconds)


Nota: Lo marcado como [// +XXX%] significa el grado de mejora en la eficiencia del algoritmo con respecto a códigos anteriores.