Problema de vendedor ambulante con algoritmos genéticos en Java

P

Introducción

Los algoritmos genéticos son 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 inspirada en la biología.

En el artículo anterior, Introducción a los algoritmos genéticos en Java, cubrimos la terminología y la teoría detrás de todo lo que necesita saber para implementar con éxito un algoritmo genético.

Implementando 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 de TSP: Un vendedor ambulante debe pasar por n ciudades para vender sus mercancías. Hay una carretera entre cada dos ciudades, pero algunas son más largas y peligrosas que otras. Dadas las ciudades y el costo de viajar entre cada dos ciudades, ¿cuál es la forma más barata para que el vendedor visite todas las ciudades y regrese a la ciudad inicial, sin pasar por ninguna ciudad dos veces?

Aunque esto pueda parecer una hazaña simple, vale la pena señalar que se trata de una NP-duro problema. No existe un 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 y / o probar la implementación completa, puede encontrar el proyecto IntelliJ en GitHub.

Representación del genoma

Primero, necesitamos una persona que represente una solución candidata. Lógicamente, para esto usaremos una clase para almacenar la generación aleatoria, la función fitness, la aptitud en sí, etc.

Para que sea más fácil calcular la aptitud de las personas y compararlas, también lo haremos implementar Comparable:

public class SalesmanGenome implements Comparable {
    // ...
}

A pesar de usar una clase, lo que nuestro individuo es esencialmente será solo uno de sus atributos. Si pensamos en TSP, podríamos enumerar nuestras ciudades desde 0 to n-1. Una solución al problema sería una serie de ciudades de modo 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 una matriz.

Los atributos de nuestra clase son los siguientes:

// 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:

// 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 fitness

Es posible que haya notado que llamamos al calculateFitness() método 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. Queremos minimizar este costo, por lo que enfrentaremos un problema de minimización:

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 en ella:

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 se denomina a menudo tamaño de la población.
  • El tamaño del genoma es la longitud del genoma. ArrayList, que será igual al numberOfCities-1. Las dos variables están separadas para mayor claridad en el resto del código. Este parámetro también se denomina a menudo longitud del cromosoma.
  • El tamaño de reproducción es la cantidad de genomas que se seleccionarán para reproducirse y crear la próxima generación. Este parámetro también se denomina a menudo tasa de cruce.
  • La iteración máxima es el número máximo de generaciones que el programa evolucionará antes de terminar, en caso de que no haya convergencia antes de esa fecha.
  • La tasa de mutación se refiere a la frecuencia de mutaciones al crear una nueva generación.
  • Los precios de los viajes son una matriz de los precios de los viajes entre cada dos ciudades; esta matriz tendrá 0 en la diagonal y valores simétricos en su triángulo inferior y superior.
  • La ciudad inicial es el índice de la ciudad inicial.
  • 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 termine antes de tiempo. A veces, establecer una condición física objetivo 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 sean 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:
public enum SelectionType {
    TOURNAMENT,
    ROULETTE
}

Selección

Aunque el método de selección de torneos prevalece en la mayoría de los casos, hay situaciones en las que querrá utilizar otros métodos. Dado que muchos algoritmos genéticos utilizan 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 la selección de torneos y ruleta:

// 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 cruzáramos estos dos en el punto denotado con un |?

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 un crossover convencional, ¿qué usamos?

La técnica que usaremos se llama Crossover parcialmente mapeado o PMX para abreviar. PMX elige al azar 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:

Como se puede ver aquí, intercambiamos iel elemento de uno de los padres con el elemento equivalente en valor al iel 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 de los padres):

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, devolvemos el genoma original:

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:

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 maxIterations
  • la longitud de la ruta del mejor genoma es menor que la longitud de la ruta objetivo
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

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

tiempo (ms) Matriz de costos Solución Ruta Longitud

Primer intento506440 44 94 70
44 0 32 56
94 32 0 63
70 56 63 0
0 1 2 3 0209
Segunda ejecución508000 3 96 51
3 0 42 86
96 42 0 33
51 86 33 0
0 3 2 1 0129
Tercera carrera499280 51 30 93
51 0 83 10
30 83 0 58
93 10 58 0
0 2 3 1 0149
Cuarta carrera553590 17 94 3
17 0 49 14
94 49 0 49
3 14 49 0
0 3 2 1 0118
Quinta carrera592620 44 0 96
44 0 68 38
0 68 0 94
96 38 94 0
0 1 3 2 0176
Sexta carrera582360 44 10 20
44 0 57 69
10 57 0 44
20 69 44 0
0 3 1 2 0156
Séptima carrera605000 27 76 58
27 0 93 28
76 93 0 83
58 28 83 0
0 2 3 1 0214
Octava carrera560850 63 59 21
63 0 67 31
59 67 0 38
21 31 38 0
0 2 1 3 0178
Novena carrera410620 3 67 89
3 0 41 14
67 41 0 26
89 14 26 0
0 2 3 1 0110
Décima carrera378150 58 83 62
58 0 98 3
83 98 0 84
62 3 84 0
0 1 3 2 0228

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 requiere mucho menos tiempo que encontrar una solución perfecta para un problema.

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

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

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

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

Se utiliza una técnica similar en NeuroEvolución de topologías aumentadas, o NEAT, donde un algoritmo genético mejora continuamente una red neuronal e indica cómo cambiar la estructura para adaptarse a nuevos entornos.

Conclusión

Los algoritmos genéticos son una herramienta poderosa y conveniente. Puede que no sean tan rápidas 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 una cereza en la parte superior, 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 mini-evolució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 interferir con atributos como la tasa de mutación. , tamaño del torneo y similares.

 

About the author

Ramiro de la Vega

Bienvenido a Pharos.sh

Soy Ramiro de la Vega, Estadounidense con raíces Españolas. Empecé a programar hace casi 20 años cuando era muy jovencito.

Espero que en mi web encuentres la inspiración y ayuda que necesitas para adentrarte en el fantástico mundo de la programación y conseguir tus objetivos por difíciles que sean.

Add comment

Sobre mi

Últimos Post

Etiquetas

Esta web utiliza cookies propias para su correcto funcionamiento. Al hacer clic en el botón Aceptar, aceptas el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Más información
Privacidad