Una forma sencilla y rápida de aprender JAVA, observando y deduciendo cómo se comporta el lenguaje a través de ejemplos prácticos.

Archivo del blog

miércoles, 10 de agosto de 2016

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 1Test 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.


Con la tecnología de Blogger.