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.

    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.

     

    Etiquetas:

    Deja una respuesta

    Tu direcci贸n de correo electr贸nico no ser谩 publicada. Los campos obligatorios est谩n marcados con *