Problema de vendedor ambulante con algoritmos genéticos en Java

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.

Te puede interesar:Tesseract: reconocimiento óptico de caracteres Java simple

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:

Te puede interesar:Anotaciones de Spring: Pruebas

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

Te puede interesar:Integración de Stripe con Java Spring para el procesamiento de pagos

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.

Te puede interesar:Trabajar con archivos zip en Java

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:

Te puede interesar:Clasificación topológica en Java

• 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 intento	50644	0 44 94 70 44 0 32 56 94 32 0 63 70 56 63 0	0 1 2 3 0	209
Segunda ejecución	50800	0 3 96 51 3 0 42 86 96 42 0 33 51 86 33 0	0 3 2 1 0	129
Tercera carrera	49928	0 51 30 93 51 0 83 10 30 83 0 58 93 10 58 0	0 2 3 1 0	149
Cuarta carrera	55359	0 17 94 3 17 0 49 14 94 49 0 49 3 14 49 0	0 3 2 1 0	118
Quinta carrera	59262	0 44 0 96 44 0 68 38 0 68 0 94 96 38 94 0	0 1 3 2 0	176
Sexta carrera	58236	0 44 10 20 44 0 57 69 10 57 0 44 20 69 44 0	0 3 1 2 0	156
Séptima carrera	60500	0 27 76 58 27 0 93 28 76 93 0 83 58 28 83 0	0 2 3 1 0	214
Octava carrera	56085	0 63 59 21 63 0 67 31 59 67 0 38 21 31 38 0	0 2 1 3 0	178
Novena carrera	41062	0 3 67 89 3 0 41 14 67 41 0 26 89 14 26 0	0 2 3 1 0	110
Décima carrera	37815	0 58 83 62 58 0 98 3 83 98 0 84 62 3 84 0	0 1 3 2 0	228

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.

Te puede interesar:Preguntas de la entrevista sobre cadenas de Java

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.