Algoritmos genéticos para colorear gráficos | idea de proyecto

1. Idea de proyecto

En este artículo, presentamos una técnica que utiliza algoritmos genéticos para resolver el problema de coloración de gráficos , y nuestro objetivo es encontrar el número mínimo de colores necesarios para colorear un gráfico .   

Este artículo pretende demostrar lo siguiente.  

1. Compruebe si un gráfico es k-coloreable encontrando una k-coloración válida.
2. Encontrar el número cromático de un gráfico
3. Usa la coloración de gráficos para resolver un Sudoku

2. Introducción  

La coloración de grafos es un problema NP-Completo . Aunque una solución a un problema NP-Complete puede verificarse “rápidamente”, no existe una forma conocida de encontrar una solución rápidamente. Por lo tanto, los problemas NP-Completos a menudo se abordan mediante el uso de algoritmos de aproximación o métodos heurísticos . Es tentador, por lo tanto, utilizar heurísticas de búsqueda como algoritmos genéticos.  

La coloración de gráficos es una asignación de etiquetas, tradicionalmente llamadas «colores», a los vértices de un gráfico sujeto a la condición de que no se asigne la misma etiqueta/color a dos vértices incidentes con un borde. El menor número de colores necesarios para colorear un gráfico G se conoce como su número cromático. Una coloración que utiliza como máximo n colores se denomina n-coloración. Un gráfico al que se le puede asignar una n-coloración es n-coloreable.  

El problema de coloración de grafos es uno de los problemas más estudiados y es un campo de investigación muy activo, principalmente por su aplicación en:  

• Planificación
• Asignación de registro
• Mapa para colorear
• Rompecabezas matemáticos

3. Algoritmo propuesto  

Graph Coloring se trata de minimizar la cantidad de colores utilizados para colorear los vértices del gráfico. Nuestro algoritmo comienza con un límite superior al número cromático, digamos k. Cuando se encuentra una coloración válida para k colores, disminuimos k y ejecutamos nuestro algoritmo nuevamente para encontrar una coloración válida usando k-1 colores. Este proceso se repite hasta que ya no es posible que nuestro algoritmo encuentre una coloración válida utilizando el número de colores dado. Por lo tanto, esperamos que nuestro algoritmo encuentre o al menos establezca un límite superior ajustado en el número cromático del gráfico.  

Algoritmo : GA para la coloración de gráficos  

Datos : Array de Adyacencia de un grafo G  

Salida : una coloración k válida del gráfico, donde k = número cromático del gráfico  

% best_fitness : mejor valor de fitness encontrado hasta ahora % fittest_individual: individuo que posee best_fitness  

% de población : array que contiene todos los individuos de la generación actual % Best(P): arroja la mejor aptitud en la población P begin  

begin 
    generation = 0 
    while ( best_fitness != 0 ): 
        selection(population) 
        crossover(population) 
        mutation(population) 
        if ( Best(population) < best_fitness ): 
            then best_fitness = Best(population) 
        generation += 1 
    end while 
    return best_fitness 
end

    3.1 Creando la Población  

Nuestra población comprende ‘individuos’ que son vectores de longitud n, que contienen números enteros en el rango de 1 a k. Aquí n es el orden de nuestro gráfico, mientras que k es el número de colores con el que queremos colorearlo. Nuestra población de primera generación es una array cuyas columnas son números aleatorios del 1 al k. Así, cada columna corresponde a una propuesta de coloración del gráfico aunque incorrecta.  

Al principio, k es uno más que el grado mayor de un vértice. Esto se hace así, ya que es el límite superior del número cromático de un gráfico.  

           χ(G) ≤ Δ(G) + 1

Para definir una función de aptitud, asignamos una penalización de 1 para cada borde que tenga los mismos vértices coloreados que inciden sobre él.

 penalización (i, j) = 1 si hay un borde entre i y j

                   =​ 0 De lo contrario

Así, la aptitud de un individuo será la suma de esta función de penalización sobre todos los bordes del gráfico.

         fitness = ∑ penalización(i, j) 

    3.2 Selección  

Siendo este un problema de minimización, el individuo que tiene la menor magnitud de “aptitud” es el individuo “más apto”. Examinamos dos algoritmos de selección para este problema. Selección de Torneos y Selección de Ruedas de Ruleta.  

Torneo de Selección: Primero se baraja la población. Agrupamos a los individuos en parejas (tamaño del torneo = 2), y el más apto pasa a la siguiente generación. Si el tamaño de nuestra población es N, hasta ahora se han seleccionado N/2 individuos. Repetimos este proceso, obteniendo así N/2 individuos más, manteniendo así el tamaño de la población. Esta técnica asegura que haya 2 copias del individuo más apto y ninguna copia del individuo menos apto.  

Selección de la rueda de la ruleta: esta selección se basa en los valores relativos de aptitud entre los individuos y la probabilidad. A una «rueda de la ruleta» se le asignan trozos para cada individuo, siendo el tamaño de cada trozo proporcional a la «bondad» del individuo. Luego se generan números aleatorios uniformes, de forma análoga a hacer girar la rueda. La rueda se hace girar (es decir, se generan números aleatorios) N veces, deteniéndose cada vez en el «trozo» del individuo, que se selecciona para la próxima generación.  

    3.3 Cruce  

Crossover es un operador de recombinación utilizado para combinar información genética de dos padres para generar nueva descendencia. El cruce utilizado aquí es el cruce de un solo punto. Vamos a mostrar cómo funciona este crossover.  

Un punto en la representación vectorial de ambos padres se elige al azar y se designa como un «punto de cruce». Los colores a la derecha de ese punto se intercambian. Esto da como resultado dos nuevos colores del gráfico, cada uno con información genética de ambos padres.  

     3.4 Mutación  

La mutación se utiliza para mantener la diversidad genética de una generación a la siguiente. Es una pequeña perturbación de la solución, que puede ayudar a las soluciones atascadas en los óptimos locales a escapar de la cuenca de atracción. La mutación se realiza con bastante moderación. Por lo tanto, tiene sentido realizarlo con alguna pequeña probabilidad, generalmente inferior al 5% o al 10%. Una cosa que se destacó al ejecutar nuestros algoritmos fue la tendencia de las soluciones a quedarse estancadas en el óptimo local (como se mostrará con los gráficos en la Sección 4.1). Por lo tanto, se decidió mantener esta probabilidad tan alta como 20%.

El operador de mutación selecciona un vértice al azar y cambia su color. Esta operación pequeña pero efectiva es crucial para que el algoritmo no solo llegue a una solución sino que también acelere el proceso. 

Otros detalles  

A medida que el algoritmo evoluciona y dado que el algoritmo no conoce el número cromático del gráfico, χ(G), aumentamos o reducimos el número de colores cada vez que se logra una coloración factible con k colores. El algoritmo se detiene cuando falla en mejorar la cantidad de colores después de algunas generaciones, digamos 10,000 generaciones para gráficos pequeños.

4 resultados experimentales  

    4.1 Coloreado de gráficos  

Ejecutemos el algoritmo en un gráfico que contiene 40 vértices. Generamos la array de adyacencia de dicho gráfico asignando aleatoriamente las entradas de la array como 0 o 1. Nuestro gráfico se ve así:

 El grado máximo de un vértice en este gráfico es 27. Por lo tanto, comenzamos con 28 colores, el límite superior del número cromático.

Usando un tamaño de población de 200, ejecutamos nuestro algoritmo en el gráfico. Cada 10 generaciones, imprimimos al individuo más apto y su forma física. Para 28 colores, tenemos:

Generación: 10 Best_Fitness: 4 Individual: [28, 8, 25, 21, 3, 27, 16,17, 9, 28, 11, 14, 2, 13, 3, 14, 25, 12, 27, 6, 9 , 14, 10, 11, 6, 23, 20, 27, 5, 24, 20, 22, 2, 26, 19, 15, 16, 18, 2, 4]  

Generación: 20 Best_Fitness: 4 Individual: [19, 25, 12, 19, 11, 26, 17, 17, 9, 28, 11, 27, 24, 12, 7, 9, 25, 21, 26, 6, 9 , 14, 10, 11, 6, 22, 28, 22, 12, 23, 27, 13, 8, 10, 7, 20, 16, 18, 2, 16]    

Generación: 30 Best_Fitness: 0 Individual: [19, 25, 12, 19, 11, 26, 17, 17, 9, 28, 3, 26, 22, 13, 19, 4, 25, 21, 7, 9, 27 , 5, 2, 23, 19, 6, 22, 10, 14, 6, 4, 1, 24, 10, 7, 20, 16, 12, 21, 21]  

Usando 28 colores:

Generación: 30 Best_Fitness: 0 Individual: [19, 25, 12, 19, 11, 26, 17, 17, 9, 28, 3, 26, 22, 13, 19, 4, 25, 21, 7, 9, 27 , 5, 2, 23, 19, 6, 22, 10, 14, 6, 4, 1, 24, 10, 7, 20, 16, 12, 21, 21]  

Esta es una coloración válida del gráfico utilizando como máximo 28 colores. El primer elemento del vector Individuo corresponde a asignar el primer vértice, la etiqueta 19, el segundo vértice 25, y así sucesivamente. Un valor Best_Fitness de 0 corresponde a una coloración válida, ya que implica que no existen infracciones.

El resultado final del programa es:

The graph is 9 colorable

Presentamos algunos gráficos para ayudar a visualizar cómo la aptitud del individuo más apto varía con las generaciones:

• Al colorear con 22 colores:

Generación: 10 Best_Fitness: 6 Individual: [8, 7, 20, 14, 19, 11, 17, 17, 18, 10, 20, 3, 16, 3, 8, 13, 4, 15, 8, 4, 19 , 20, 10, 20, 1, 11, 6, 1, 16, 12, 9, 8, 6, 18, 15, 9, 22, 2, 11, 21]

Generación: 20 Best_Fitness: 6 Individual: [20, 5, 22, 8, 1, 15, 4, 3, 14, 18, 5, 9, 14, 8, 20, 19, 14, 17, 3, 6, 16 , 2, 21, 20, 22, 6, 10, 12, 8, 21, 1, 8, 19, 13, 3, 11, 8, 18, 11, 21]  

Generación: 30 Best_Fitness: 2 Individual: [20, 5, 22, 8, 1, 15, 6, 17, 15, 18, 18, 8, 9, 1, 11, 14, 10, 5, 22, 12, 15 , 20, 21, 7, 9, 17, 7, 12, 10, 21, 1, 8, 6, 13, 22, 11, 1, 2, 5, 3]

Generación: 40 Best_Fitness: 2 Individual: [16, 20, 15, 14, 19, 15, 6, 17, 15, 18, 18, 8, 9, 4, 13, 14, 10, 5, 10, 12, 22 , 14, 14, 7, 9, 17, 14, 12, 10, 21, 18, 8, 6, 13, 15, 11, 1, 2, 5, 3]  

Generación: 50 Best_Fitness: 2 Individual: [8, 7, 20, 12, 1, 11, 17, 3, 15, 5, 5, 9, 9, 4, 13, 14, 10, 5, 16, 19, 15 , 20, 8, 7, 22, 17, 10, 22, 1, 2, 1, 8, 19, 6, 4, 8, 22, 2, 11, 18]  

Usando 22 colores:

Generación: 58 Best_Fitness: 0 Individual: [14, 11, 15, 14, 1,15, 17, 3, 15, 18, 5, 8, 9, 1, 13, 14, 10, 11, 10, 12, 16 , 20, 8, 1, 9, 17, 21, 4, 16, 2, 1, 8, 19, 13, 4, 4, 22, 2, 11, 21]  

A medida que nos acercamos al número cromático del gráfico, notamos una tendencia interesante en el gráfico anterior. Al principio, la aptitud disminuye rápidamente, sin embargo, cuando se acerca a la solución, tiende a atascarse y la aptitud no mejora mucho durante un número significativo de generaciones. Algo así:

Para combatir esto, introducimos dos mutaciones diferentes. Uno que tiene lugar en las primeras 200 generaciones, y el otro que se ejecuta después de eso. La diferencia está en las probabilidades. El primero tiene una mayor probabilidad de mutar un Individuo que el segundo. Esto asegura que al principio el espacio de búsqueda se explore adecuadamente rápido, y al final, solo se hagan ligeras perturbaciones a las existentes para que no perdamos las «buenas» soluciones si las soluciones convergentes se desvían.

Nuestro programa finaliza cuando no puede encontrar una coloración válida usando 8 colores. Permitimos que funcione durante 10000 generaciones. Al no llegar a una solución válida en las generaciones dadas, se puede creer que no existe una coloración de 8 para el gráfico, o que el valor de salida de nuestro algoritmo es bastante cercano al número cromático real.

Generación: 9990 Best_Fitness: 4 Individual: [1, 5, 8, 5, 4, 4, 3, 6, 5, 6, 7, 3, 2, 2, 8, 1, 8, 4, 2, 5, 5 , 8, 8, 1, 3, 6, 6, 4, 7, 2, 7, 2, 6, 4, 2, 1, 7, 1, 3, 3]      

Generación: 10000 Best_Fitness: 4 Individual: [1, 5, 8, 5, 4, 4, 3, 6, 5, 6, 7, 3, 2, 2, 8, 1, 8, 4, 2, 5, 5 , 8, 8, 1, 3, 6, 6, 4, 7, 8, 7, 2, 6, 4, 2, 1, 7, 1, 3, 3]      

Usando 8 colores:      

Generación: 10000 Best_Fitness: 4 Individual: [1, 5, 8, 5, 4, 4, 3, 6, 5, 6, 7, 3, 2, 2, 8, 1, 8, 4, 2, 5, 5 , 8, 8, 1, 3, 6, 6, 4, 7, 8, 7, 2, 6, 4, 2, 1, 7, 1, 3, 3]      

Por lo tanto, de acuerdo con nuestro algoritmo, el gráfico tiene 9 colores y los 9 colores calculados son:

Usando 9 colores:

Generación: 3744 Best_Fitness: 0 Individual: [8, 1, 6, 8, 5, 3, 1, 9, 8, 5, 9, 2, 2, 4, 3, 8, 3, 5, 3, 7, 1 , 6, 8, 5, 6, 7, 5, 6, 4, 4, 9, 2, 7, 3, 5, 5, 4, 4, 7, 2]  

5 Implementación de este problema en problemas de la vida real como Sudoku

Sudoku es un rompecabezas combinatorio de colocación de números basado en la lógica. El objetivo es llenar una cuadrícula N * N de modo que cada fila, columna y las subcuadrículas N (√N * √N) tengan todos los números del 1 al N. Por lo general, N = 9. También existen otras variantes del rompecabezas.

Una forma alternativa pero equivalente de presentar las reglas es: Rellenar la cuadrícula de modo que ninguna fila, columna o subcuadrícula tenga un número repetido. Esta definición deja en claro que resolver un Sudoku se reduce a un problema de coloreado de gráficos, donde tenemos un gráfico en N * N vértices. Imagina colocar un vértice en una cuadrícula N * N. Para cada vértice, agregue un borde que conecte el vértice con todos los demás vértices en su fila, columna y subcuadrícula. La siguiente imagen da una representación visual de N = 9.

Lo anterior es un gráfico de 81 vértices. Un 9 para colorear válido representará una forma de completar el Sudoku.

Para resolver las preguntas de Sudoku, necesitamos hacer algunos cambios. Todas las preguntas de Sudoku tienen valores especificados en ciertos lugares. Inicializaremos todos nuestros Individuos de modo que tengan el color (valor) correspondiente en sus respectivas posiciones. Además, cambiamos la función de mutación para garantizar que estos valores no se modifiquen. Luego encontramos una coloración de 9 del gráfico Sudoku2, es decir, asignamos las etiquetas ‘1’, ‘2’,…, ‘9’ a los Nodes del gráfico. El resultado final del código será un 9-coloreado válido. Además, las etiquetas especificadas en la entrada permanecen sin cambios. A continuación se muestra un ejemplo:

• Gráfico de entrada:

Al ejecutar el código, las últimas líneas de la salida son las siguientes:

Generación: 144100 Best_Fitness: 2 Individual: [1, 2, 3, 6, 5, 8, 7, 4, 9, 5, 8, 4, 7, 3, 9, 7, 2, 1, 9, 6, 7 , 2, 4, 1, 3, 8, 5, 3, 7, 1, 4, 9, 2, 5, 6, 8, 6, 5, 2, 1, 8, 3, 9, 7, 4, 4 , 9, 8, 5, 6, 7, 2, 1, 3, 8, 3, 6, 9, 2, 4, 1, 5, 7, 2, 1, 9, 8, 7, 5, 4, 3 , 6, 7, 4, 5, 3, 1, 6, 8, 9, 2]  

Generación: 144120 Best_Fitness: 2 Individual: [1, 2, 3, 6, 5, 8, 7, 4, 9, 5, 8, 4, 7, 3, 9, 7, 2, 1, 9, 6, 7 , 2, 4, 1, 3, 8, 5, 3, 7, 1, 4, 9, 2, 5, 6, 8, 6, 5, 2, 1, 8, 3, 9, 7, 4, 4 , 9, 8, 5, 6, 7, 2, 1, 3, 8, 3, 6, 9, 2, 4, 1, 5, 7, 2, 1, 9, 8, 7, 5, 4, 3 , 6, 7, 4, 5, 3, 1, 6, 8, 9, 2]  

Generación: 144128 Best_Fitness: 0 Individual: [1, 2, 3, 6, 7, 8, 9, 4, 5, 5, 8, 4, 2, 3, 9, 7, 6, 1, 9, 6, 7 , 1, 4, 5, 3, 2, 8, 3, 7, 2, 4, 6, 1, 5, 8, 9, 6, 9, 1, 5, 8, 3, 2, 7, 4, 4 , 5, 8, 7, 9, 2, 6, 1, 3, 8, 3, 6, 9, 2, 4, 1, 5, 7, 2, 1, 9, 8, 5, 7, 4, 3 , 6, 7, 4, 5, 3, 1, 6, 8, 9, 2]  

El Individuo con aptitud 0 es una solución al Sudoku dado. Cuando se ingresan los valores, se ve así:

• Valores de salida cuando se rellena en Sudoku:

6. Implementación:

from array import *
import random
import matplotlib.pyplot as plt
import numpy as np
Gen = np.array([])
Fit = np.array([])
  
'''Create Graph'''
n = 40
graph = []
for i in range(n):
    vertex = []
    for j in range(n):
        vertex.append(random.randint(0, 1))
    graph.append(vertex)
for i in range(n):
    for j in range(0, i):
        graph[i][j] = graph[j][i]
for i in range(n):
    graph[i][i] = 0
for v in graph:
    print(v)
  
'''Upper Bound for Coloring'''
max_num_colors = 1
for i in range(n):
    if sum(graph[i]) > max_num_colors:
        max_num_colors = sum(graph[i]) + 1
print(max_num_colors)
  
  
'''Create Individual using given # of colors'''
number_of_colors = max_num_colors
'''GA'''
condition = True
while(condition and number_of_colors > 0):
    def create_individual():
        individual = []
        for i in range(n):
            individual.append(random.randint(1, number_of_colors))
        return individual
    '''Create Population'''
    population_size = 200
    generation = 0
    population = []
    for i in range(population_size):
        individual = create_individual()
        population.append(individual)
  
    '''Fitness'''
    def fitness(graph, individual):
        fitness = 0
        for i in range(n):
            for j in range(i, n):
                if(individual[i] == individual[j] and graph[i][j] == 1):
                    fitness += 1
        return fitness
  
    '''Crossover'''
    def crossover(parent1, parent2):
        position = random.randint(2, n-2)
        child1 = []
        child2 = []
        for i in range(position+1):
            child1.append(parent1[i])
            child2.append(parent2[i])
        for i in range(position+1, n):
            child1.append(parent2[i])
            child2.append(parent1[i])
        return child1, child2
  
    def mutation1(individual):
        probability = 0.4
        check = random.uniform(0, 1)
        if(check <= probability):
            position = random.randint(0, n-1)
            individual[position] = random.randint(1, number_of_colors)
        return individual
  
    def mutation2(individual):
        probability = 0.2
        check = random.uniform(0, 1)
        if(check <= probability):
            position = random.randint(0, n-1)
            individual[position] = random.randint(1, number_of_colors)
        return individual
  
    '''Tournament Selection'''
    def tournament_selection(population):
        new_population = []
        for j in range(2):
            random.shuffle(population)
            for i in range(0, population_size-1, 2):
                if fitness(graph, population[i]) < fitness(graph, population[i+1]):
                    new_population.append(population[i])
                else:
                    new_population.append(population[i+1])
        return new_population
  
    '''Roulette Wheel Selection'''
    def roulette_wheel_selection(population):
        total_fitness = 0
        for individual in population:
            total_fitness += 1/(1+fitness(graph, individual))
        cumulative_fitness = []
        cumulative_fitness_sum = 0
        for i in range(len(population)):
            cumulative_fitness_sum += 1 / \
                (1+fitness(graph, population[i]))/total_fitness
            cumulative_fitness.append(cumulative_fitness_sum)
  
        new_population = []
        for i in range(len(population)):
            roulette = random.uniform(0, 1)
            for j in range(len(population)):
                if (roulette <= cumulative_fitness[j]):
                    new_population.append(population[j])
                    break
        return new_population
    best_fitness = fitness(graph, population[0])
    fittest_individual = population[0]
    gen = 0
    while(best_fitness != 0 and gen != 10000):
        gen += 1
        population = roulette_wheel_selection(population)
        new_population = []
        random.shuffle(population)
        for i in range(0, population_size-1, 2):
            child1, child2 = crossover(population[i], population[i+1])
            new_population.append(child1)
            new_population.append(child2)
        for individual in new_population:
            if(gen < 200):
                individual = mutation1(individual)
            else:
                individual = mutation2(individual)
        population = new_population
        best_fitness = fitness(graph, population[0])
        fittest_individual = population[0]
        for individual in population:
            if(fitness(graph, individual) < best_fitness):
                best_fitness = fitness(graph, individual)
                fittest_individual = individual
        if gen % 10 == 0:
            print("Generation: ", gen, "Best_Fitness: ",
                  best_fitness, "Individual: ", fittest_individual)
        Gen = np.append(Gen, gen)
        Fit = np.append(Fit, best_fitness)
    print("Using ", number_of_colors, " colors : ")
    print("Generation: ", gen, "Best_Fitness: ",
          best_fitness, "Individual: ", fittest_individual)
    print("\n\n")
    if(best_fitness != 0):
        condition = False
        print("Graph is ", number_of_colors+1, " colorable")
    else:
        Gen = np.append(Gen, gen)
        Fit = np.append(Fit, best_fitness)
        plt.plot(Gen, Fit)
        plt.xlabel("generation")
        plt.ylabel("best-fitness")
        plt.show()
        Gen = []
        Fit = []
        number_of_colors -= 1

Código para generar array de adyacencia de un Sudoku 9*9

board = []
for i in range(1, 74, 9):
    row = []
    for j in range(i, i+9):
        row.append(j)
    board.append(row)
for l in board:
    print(l)
squares = []
for i in range(1, 8, 3):
    for k in range(1, 8, 3):
        square = []
        for j in range(i, i+3):
            for l in range(k, k+3):
                square.append(board[j-1][l-1])
        squares.append(square)
for l in squares:
    print(l)
sudoku = []
for i in range(81):
    row = []
    for j in range(81):
        row.append(0)
    sudoku.append(row)
for l in sudoku:
    print(l)
Adj = []
for i in range(1, 82):
    row = (i-1)//9
    column = (i-1) % 9
    adj = []
    for j in range(9):
        adj.append(board[row][j])
    for j in range(9):
        adj.append(board[j][column])
    row_block = row//3
    column_block = column//3
    square_number = row_block*3 + column_block
    for j in squares[square_number]:
        adj.append(j)
    Adj.append(adj)
for l in Adj:
    print(l)
for i in range(81):
    for j in Adj[i]:
        print(i, j-1)
        sudoku[i][j-1] = 1
for i in range(81):
    sudoku[i][i] = 0
for l in sudoku:
    print(l)

7. Deficiencias y Posibles Soluciones:

• El algoritmo puede llevar mucho tiempo para gráficos más grandes (> 200 vértices). Además, el tiempo para llegar a una solución depende en gran medida de la población inicializada aleatoriamente.
• El criterio de parada para el algoritmo es un número dado de generaciones. Esta podría ser una mala estrategia, ya que el algoritmo podría no llegar al número de color real del gráfico, dado el criterio de parada. Esto puede conducir a soluciones deficientes en algunos casos.
• Para llegar a una coloración k válida, el algoritmo primero tiene que encontrar coloraciones válidas para k+1, k+2, …. . Establecer límites superiores más estrictos en el número cromático que el mencionado en la Sección 3.1 puede ayudar a ahorrar mucho tiempo de cálculo en los casos en que el número cromático está muy lejos del límite superior mencionado anteriormente.
• Como se señaló anteriormente, el algoritmo tiende a atascarse en un óptimo local, hasta que el operador de mutación lo perturba de la manera correcta para ayudarlo a acercarse a la solución. El uso de operadores de mutación avanzados podría ayudar a superar esto, lo que mejorará aún más el tiempo de ejecución.

8. Conclusión

Al implementar el algoritmo, realmente sentimos por qué estos algoritmos se conocen como algoritmos ‘genéticos’ y su parecido con la teoría de la evolución de Darwin. Los GA son esencialmente simulaciones por computadora de la naturaleza. Vimos cómo la aptitud de la población tiende a mejorar con las iteraciones. El paradigma de ‘supervivencia del más apto’ se refleja en el operador Selección. El cruce se asemeja a la reproducción, al igual que los padres que dan a luz a una descendencia que tiene información genética de ambos padres. La sublime simplicidad del algoritmo y los impresionantes resultados que produce muestran cuán poderosos son estos algoritmos.

Compañeros de equipo del proyecto: –

  1. Pranav Gupta  

  2. Duro Vardhan Goenka