Problema del viajante de comercio con algoritmos genéticos en Java

Los algoritmos genéticos son parte de una familia de algoritmos para la optimización global llamada Computación Evolutiva, que se compone de inteligencia artificial...

Introducción

Los algoritmos genéticos forman parte de una familia de algoritmos para la optimización global denominada Computación evolutiva, que se compone de metaheurísticas de inteligencia artificial con aleatorización inspiradas en la biología.

En el artículo anterior, Introducción a los Algoritmos Genéticos en Java, hemos cubierto la terminología y la teoría detrás de todas las cosas que necesita saber para implementar con éxito un algoritmo genético.

Implementación de un algoritmo genético

Para mostrar lo que podemos hacer con los algoritmos genéticos, resolvamos El problema del vendedor ambulante (TSP) en Java.

Formulación TSP: Un vendedor ambulante necesita recorrer n ciudades para vender su mercancía. Hay un camino entre cada dos ciudades, pero algunos caminos son más largos y peligrosos que otros. Dadas las ciudades y el costo de viajar entre cada dos ciudades, ¿cuál es la forma más económica para que el vendedor visite todas las ciudades y regrese a la ciudad inicial, sin pasar por ninguna ciudad dos veces?

Aunque esto puede parecer una hazaña simple, vale la pena señalar que se trata de un problema de NP-duro. No hay algoritmo para resolverlo en tiempo polinomial. El algoritmo genético solo puede aproximar la solución.

Debido a que la solución es bastante larga, la desglosaré función por función para explicarla aquí. Si desea obtener una vista previa o probar la implementación completa, puede encontrar el proyecto IntelliJ en GitHub.

Representación del genoma

Primero, necesitamos un individuo para representar una solución candidata. Lógicamente, para esto usaremos una clase para almacenar la generación aleatoria, la función de aptitud, la aptitud en sí, etc.

Para que sea más fácil calcular la aptitud de los individuos y compararlos, también implementaremos Comparable:

1
2
3
public class SalesmanGenome implements Comparable {
    // ...
}

A pesar de utilizar una clase, lo que es esencialmente nuestro individuo será sólo uno de sus atributos. Si pensamos en TSP, podríamos enumerar nuestras ciudades de 0 a n-1. Una solución al problema sería una matriz de ciudades de manera que se minimice el costo de recorrerlas en ese orden.

Por ejemplo, 0-3-1-2-0. Podemos almacenar eso en un ArrayList porque el Marco de colecciones lo hace realmente conveniente, pero puede usar cualquier estructura similar a un arreglo.

Los atributos de nuestra clase son los siguientes:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
// The list with the cities in order in which they should be visited
// This sequence represents the solution to the problem
List<Integer> genome;

// Travel prices are handy to be able to calculate fitness
int[][] travelPrices;

// While the starting city doesn't change the solution of the problem,
// it's handy to just pick one so you could rely on it being the same
// across genomes
int startingCity;

int numberOfCities;

int fitness;

Cuando se trata de constructores, haremos dos: uno que crea un genoma aleatorio y otro que toma un genoma ya creado como argumento:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// Generates a random salesman
public SalesmanGenome(int numberOfCities, int[][] travelPrices, int startingCity) {
    this.travelPrices = travelPrices;
    this.startingCity = startingCity;
    this.numberOfCities = numberOfCities;

    this.genome = randomSalesman();
    this.fitness = this.calculateFitness();
}

// Generates a salesman with a user-defined genome
public SalesmanGenome(List<Integer> permutationOfCities, int numberOfCities, int[][] travelPrices, int startingCity) {
    this.genome = permutationOfCities;
    this.travelPrices = travelPrices;
    this.startingCity = startingCity;
    this.numberOfCities = numberOfCities;

    this.fitness = this.calculateFitness();
}

// Generates a random genome
// Genomes are permutations of the list of cities, except the starting city
// so we add them all to a list and shuffle
private List<Integer> randomSalesman() {
    List<Integer> result = new ArrayList<Integer>();
    for (int i = 0; i < numberOfCities; i++) {
        if (i != startingCity)
            result.add(i);
    }
    Collections.shuffle(result);
    return result;
} 

Función de fitness {#función de fitness}

Es posible que haya notado que llamamos al método calculateFitness() para asignar un valor de aptitud al atributo del objeto durante la construcción. La función funciona siguiendo el camino trazado en el genoma a través de la matriz de precios y sumando el costo.

La aptitud resulta ser el costo real de tomar cierto camino. Querremos minimizar este costo, por lo que nos enfrentaremos a un problema de minimización:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
public int calculateFitness() {
    int fitness = 0;
    int currentCity = startingCity;
    
    // Calculating path cost
    for (int gene : genome) {
        fitness += travelPrices[currentCity][gene];
        currentCity = gene;
    }
    
    // We have to add going back to the starting city to complete the circle
    // the genome is missing the starting city, and indexing starts at 0, which is why we subtract 2
    fitness += travelPrices[genome.get(numberOfCities-2)][startingCity];
    
    return fitness;
}

La clase de algoritmo genético

El corazón del algoritmo tendrá lugar en otra clase, llamada TravelingSalesman. Esta clase realizará nuestra evolución, y todas las demás funciones estarán contenidas dentro de ella:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
private int generationSize;
private int genomeSize;
private int numberOfCities;
private int reproductionSize;
private int maxIterations;
private float mutationRate;
private int[][] travelPrices;
private int startingCity;
private int targetFitness;
private int tournamentSize;
private SelectionType selectionType;
  • El tamaño de la generación es el número de genomas/individuos en cada generación/población. Este parámetro también suele denominarse tamaño de la población.
  • El tamaño del genoma es la longitud del genoma ArrayList, que será igual a numberOfCities-1. Las dos variables están separadas para mayor claridad en el resto del código. Este parámetro también suele denominarse longitud cromosómica.
  • El tamaño de la reproducción es la cantidad de genomas que se seleccionarán para reproducirse y formar la próxima generación. Este parámetro también suele denominarse tasa de cruce.
  • La iteración máxima es el número máximo de generaciones que evolucionará el programa antes de terminar, en caso de que no haya convergencia antes de eso.
  • La tasa de mutación se refiere a la frecuencia de mutaciones al crear una nueva generación.
  • Precios de viaje es una matriz de los precios de viaje entre cada dos ciudades - esta matriz tendrá 0 en la diagonal y valores simétricos en su triángulo inferior y superior.
  • La ciudad de inicio es el índice de la ciudad de inicio.
  • La aptitud objetivo es la aptitud que debe alcanzar el mejor genoma de acuerdo con la función objetivo (que en nuestra implementación será la misma que la función de aptitud) para que el programa finalice antes de tiempo. En ocasiones, establecer un objetivo de condición física puede acortar un programa si solo necesitamos un valor específico o mejor. Aquí, si queremos mantener nuestros costos por debajo de un cierto número, pero no nos importa qué tan bajos exactamente, podemos usarlo para establecer ese umbral.
  • El tamaño del torneo es el tamaño del torneo para la selección del torneo.
  • El tipo de selección determinará el tipo de selección que estamos usando - implementaremos tanto la ruleta como el torneo. Aquí está la enumeración para SelectionType:
1
2
3
4
public enum SelectionType {
    TOURNAMENT,
    ROULETTE
}

Selección

Aunque el método de selección de torneo prevalece en la mayoría de los casos, hay situaciones en las que desearía utilizar otros métodos. Dado que muchos algoritmos genéticos usan la misma base de código (los individuos y las funciones de aptitud cambian), es una buena práctica agregar más opciones al algoritmo.

Implementaremos tanto la selección de la ruleta como la del torneo:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// We select reproductionSize genomes based on the method
// predefined in the attribute selectionType
public List<SalesmanGenome> selection(List<SalesmanGenome> population) {
    List<SalesmanGenome> selected = new ArrayList<>();
    SalesmanGenome winner;
    for (int i=0; i < reproductionSize; i++) {
        if (selectionType == SelectionType.ROULETTE) {
            selected.add(rouletteSelection(population));
        }
        else if (selectionType == SelectionType.TOURNAMENT) {
            selected.add(tournamentSelection(population));
        }
    }

    return selected;
}

public SalesmanGenome rouletteSelection(List<SalesmanGenome> population) {
    int totalFitness = population.stream().map(SalesmanGenome::getFitness).mapToInt(Integer::intValue).sum();
    
    // We pick a random value - a point on our roulette wheel
    Random random = new Random();
    int selectedValue = random.nextInt(totalFitness);
    
    // Because we're doing minimization, we need to use reciprocal
    // value so the probability of selecting a genome would be
    // inversely proportional to its fitness - the smaller the fitness
    // the higher the probability
    float recValue = (float) 1/selectedValue;
    
    // We add up values until we reach out recValue, and we pick the
    // genome that crossed the threshold
    float currentSum = 0;
    for (SalesmanGenome genome : population) {
        currentSum += (float) 1/genome.getFitness();
        if (currentSum >= recValue) {
            return genome;
        }
    }
    
    // In case the return didn't happen in the loop above, we just
    // select at random
    int selectRandom = random.nextInt(generationSize);
    return population.get(selectRandom);
}

// A helper function to pick n random elements from the population
// so we could enter them into a tournament
public static <E> List<E> pickNRandomElements(List<E> list, int n) {
    Random r = new Random();
    int length = list.size();

    if (length < n) return null;

    for (int i = length - 1; i >= length - n; --i) {
        Collections.swap(list, i , r.nextInt(i + 1));
    }
    return list.subList(length - n, length);
}

// A simple implementation of the deterministic tournament - the best genome
// always wins
public SalesmanGenome tournamentSelection(List<SalesmanGenome> population) {
    List<SalesmanGenome> selected = pickNRandomElements(population, tournamentSize);
    return Collections.min(selected);
}

Transversal

El cruce de TSP es atípico. Debido a que cada genoma es una permutación de la lista de ciudades, no podemos simplemente cruzar dos padres de manera convencional. Mire el siguiente ejemplo (la ciudad inicial 0 es implícitamente el primer y último paso):

2-4-3|1-6-5

4-6-5|3-1-2

¿Qué pasaría si cruzamos estos dos en el punto indicado con |?

2-4-3-3-1-2

4-6-5-1-6-5

UH oh. Estos no pasan por todas las ciudades y visitan algunas ciudades dos veces, violando múltiples condiciones del problema.

Entonces, si no podemos usar el crossover convencional, ¿qué debemos usar?

La técnica que usaremos se llama Crossover parcialmente mapeado o PMX para abreviar. PMX elige aleatoriamente un punto de cruce, pero a diferencia del cruce de un punto, no solo intercambia elementos de dos padres, sino que intercambia los elementos dentro de ellos. Encuentro que el proceso es más comprensible a partir de una ilustración, y podemos usar el ejemplo con el que hemos tenido problemas anteriormente:

pmx technique{.img-responsive}

Como puede verse aquí, intercambiamos el iésimo elemento de uno de los padres con el elemento equivalente en valor al iésimo elemento del otro. Al hacer esto, preservamos las propiedades de las permutaciones. Repetimos este proceso para crear también el segundo hijo (con los valores originales de los genomas principales):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public List<SalesmanGenome> crossover(List<SalesmanGenome> parents) {
    // Housekeeping
    Random random = new Random();
    int breakpoint = random.nextInt(genomeSize);
    List<SalesmanGenome> children = new ArrayList<>();

    // Copy parental genomes - we copy so we wouldn't modify in case they were
    // chosen to participate in crossover multiple times
    List<Integer> parent1Genome = new ArrayList<>(parents.get(0).getGenome());
    List<Integer> parent2Genome = new ArrayList<>(parents.get(1).getGenome());
    
    // Creating child 1
    for (int i = 0; i < breakpoint; i++) {
        int newVal;
        newVal = parent2Genome.get(i);
        Collections.swap(parent1Genome, parent1Genome.indexOf(newVal), i);
    }
    children.add(new SalesmanGenome(parent1Genome, numberOfCities, travelPrices, startingCity));
    parent1Genome = parents.get(0).getGenome(); // Reseting the edited parent
    
    // Creating child 2
    for (int i = breakpoint; i < genomeSize; i++) {
        int newVal = parent1Genome.get(i);
        Collections.swap(parent2Genome, parent2Genome.indexOf(newVal), i);
    }
    children.add(new SalesmanGenome(parent2Genome, numberOfCities, travelPrices, startingCity));

    return children;
}

Mutación

La mutación es bastante sencilla: si pasamos una verificación de probabilidad, mutamos intercambiando dos ciudades en el genoma. De lo contrario, simplemente devolvemos el genoma original:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
public SalesmanGenome mutate(SalesmanGenome salesman) {
    Random random = new Random();
    float mutate = random.nextFloat();
    if (mutate < mutationRate) {
        List<Integer> genome = salesman.getGenome();
        Collections.swap(genome, random.nextInt(genomeSize), random.nextInt(genomeSize));
        return new SalesmanGenome(genome, numberOfCities, travelPrices, startingCity);
    }
    return salesman;
}

Políticas de reemplazo de generación

Estamos usando un algoritmo generacional, por lo que creamos una población de niños completamente nueva:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
public List<SalesmanGenome> createGeneration(List<SalesmanGenome> population) {
    List<SalesmanGenome> generation = new ArrayList<>();
    int currentGenerationSize = 0;
    while (currentGenerationSize < generationSize) {
        List<SalesmanGenome> parents = pickNRandomElements(population, 2);
        List<SalesmanGenome> children = crossover(parents);
        children.set(0, mutate(children.get(0)));
        children.set(1, mutate(children.get(1)));
        generation.addAll(children);
        currentGenerationSize += 2;
    }
    return generation;
}

Terminación

Terminamos bajo las siguientes condiciones:

  • el número de generaciones ha llegado a maxIterations
  • la mejor longitud de la ruta del genoma es menor que la longitud de la ruta objetivo
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
public SalesmanGenome optimize() {
    List<SalesmanGenome> population = initialPopulation();
    SalesmanGenome globalBestGenome = population.get(0);
    for (int i = 0; i < maxIterations; i++) {
        List<SalesmanGenome> selected = selection(population);
        population = createGeneration(selected);
        globalBestGenome = Collections.min(population);
        if (globalBestGenome.getFitness() < targetFitness)
            break;
    }
    return globalBestGenome;
}

Tiempo de ejecución {#tiempo de ejecución}

La mejor manera de evaluar si este algoritmo funciona correctamente es generar algunos problemas aleatorios y evaluar el tiempo de ejecución:


             time(ms)       Cost Matrix    Solution       Path Length

Primera ejecución 50644 0 44 94 70\ 0 1 2 3 0 209 44 0  32 56\
94 32 0  63\
70 56 63 0

Segunda ejecución 50800 0  3  96 51\ 0 3 2 1 0 129 3  0  42 86\
96 42 0  33\
51 86 33 0

Tercera ejecución 49928 0 51 30 93\ 0 2 3 1 0 149 51 0  83 10\
30 83 0  58\
93 10 58 0

Cuarta ejecución 55359 0 17 94 3\ 0 3 2 1 0 118 17 0  49 14\
94 49 0  49\
3  14 49 0

Quinta ejecución 59262 0 44 0 96\ 0 1 3 2 0 176 44 0  68 38\
0  68 0  94\
96 38 94 0

Sexta ejecución 58236 0 44 10 20\ 0 3 1 2 0 156 44 0  57 69\
10 57 0  44\
20 69 44 0

Séptima ejecución 60500 0 27 76 58\ 0 2 3 1 0 214 27 0  93 28\
76 93 0  83\
58 28 83 0

Octava Ejecución 56085 0 63 59 21\ 0 2 1 3 0 178 63 0  67 31\
59 67 0  38\
21 31 38 0

Novena Ejecución 41062 0 3 67 89\ 0 2 3 1 0 110 3  0  41 14\
67 41 0  26\
89 14 26 0

Décima Ejecución 37815 0 58 83 62\ 0 1 3 2 0 228 58 0  98 3\
83 98 0  84\
62 3  84 0


Nuestro tiempo de ejecución promedio es de 51972 ms, que es de aproximadamente 52 segundos. Esto es cuando la entrada es de cuatro ciudades, lo que significa que tendríamos que esperar más para un mayor número de ciudades. Esto puede parecer mucho, pero implementar un algoritmo genético toma mucho menos tiempo que encontrar una solución perfecta para un problema.

Si bien este problema específico podría resolverse con otro método, ciertos problemas no pueden.

Por ejemplo, la NASA utilizó un algoritmo genético para generar la forma óptima de una antena de nave espacial para obtener el mejor patrón de radiación.

¿Algoritmos genéticos para optimizar los algoritmos genéticos?

Como un aparte interesante, los algoritmos genéticos a veces se usan para optimizarse a sí mismos. Usted crea un algoritmo genético que ejecuta otro algoritmo genético y califica su velocidad de ejecución y salida como su aptitud y ajusta sus parámetros para maximizar el rendimiento.

Una técnica similar se usa en Neuroevolución de las topologías de aumento, o NEAT, donde un algoritmo genético mejora continuamente una red neuronal e insinúa cómo cambiar la estructura para adaptarse a nuevos entornos.

Conclusión

Los algoritmos genéticos son una herramienta poderosa y conveniente. Es posible que no sean tan rápidos como las soluciones diseñadas específicamente para el problema en cuestión, y es posible que no tengamos muchas pruebas matemáticas de su eficacia, pero pueden resolver cualquier problema de búsqueda de cualquier dificultad y no son demasiado difíciles de dominar. y aplicar Y como guinda del pastel, son infinitamente fascinantes de implementar cuando piensas en los procesos evolutivos en los que se basan y en cómo eres el cerebro detrás de una minievolución propia.

PD

Si desea seguir jugando con TSP implementado en este artículo, este es un recordatorio de que puede encontrarlo en GitHub. Tiene algunas funciones útiles para imprimir generaciones, costos de viaje, generar costos de viaje aleatorios para un número determinado de ciudades, etc. para que pueda probar cómo funciona en diferentes tamaños de entrada, o incluso entrometerse con atributos como la tasa de mutación. , tamaño del torneo y similares.