Programación genética en Python: el problema de la bolsa

En este artículo, veremos el problema de la mochila, un clásico en informática. Explicaremos por qué es difícil de resolver usando métodos computacionales tradicionales y cómo la programación genética puede ayudar a encontrar una solución “suficientemente buena”. Más tarde, veremos una implementación de Python de tal solución para probarnos a nosotros mismos.

El problema de la mochila se puede utilizar para ilustrar la dificultad de resolver problemas computacionales complejos. En su forma más simple, se le entrega una bolsa de cierta capacidad, un conjunto de artículos con tamaños y precios, y se le pide maximizar el valor de los artículos colocados en la bolsa sin exceder su capacidad. El problema de la mochila se puede formular de muchas maneras, pero generalmente se considera un problema difícil de resolver utilizando algoritmos tradicionales.

La dificultad con el problema de la bolsa es que es un problema NP-completo, lo que significa que no existe una solución conocida que pueda proporcionar una solución óptima global. Por lo tanto, el problema es intratable y no puede resolverse rápidamente por métodos tradicionales. Los algoritmos más populares para resolver el problema de la bolsa utilizan métodos heurísticos o de búsqueda de fuerza bruta, que tienen tiempos de ejecución prolongados y no brindan soluciones óptimas.

Y la programación genética puede proporcionar un método alternativo para resolver el problema de la bolsa. La programación genética es una técnica que utiliza algoritmos evolutivos para encontrar soluciones a problemas complejos. Usando la programación genética, es posible encontrar rápidamente una solución que sea “suficientemente buena” para un problema dado. También se puede utilizar para optimizar y mejorar soluciones.

En la programación genética, se genera aleatoriamente un conjunto de posibles soluciones (o generación inicial) y luego se evalúa en función de un conjunto de criterios. Luego se seleccionan las soluciones que mejor se ajustan a los criterios y se aplican mutaciones genéticas para generar nuevas soluciones (o generaciones posteriores). Luego se evalúan estas opciones de próxima generación y se repite el proceso hasta encontrar una solución satisfactoria. El proceso se repite hasta que se encuentra la solución óptima o mejor “suficientemente buena”.

La ventaja de usar la programación genética para resolver el problema de la mochila es que se puede encontrar rápidamente una solución razonablemente buena sin tener que buscar exhaustivamente todas las soluciones posibles. Esto lo convierte en un enfoque más eficiente que los algoritmos tradicionales y permite una solución más rápida.

Ahora que tenemos una idea de qué es el problema de la mochila, qué es la programación genética y por qué usaríamos esta última para tratar de resolver la primera, veamos una implementación de Python de lo que describimos anteriormente.

Repasaremos las características importantes una por una y luego veremos la aplicación en general.

El programa se implementa en Python sin utilizar bibliotecas de terceros.

Crear una población aleatoria

Esta función genera una población aleatoria de un tamaño dado. Utiliza un bucle for para iterar sobre un tamaño determinado y crea un cromosoma para cada iteración. Este cromosoma es una lista de 0 y 1 generada usando la función random.choice(). Luego, el cromosoma se agrega a la lista de población. Finalmente, la función imprime un mensaje y devuelve una lista de la población. Esta función es útil para generar poblaciones de individuos para algoritmos genéticos.

def generate_population(size):
	population = []
	for _ in range(size):
		genes = [0, 1]
		chromosome = []
		for _ in range(len(items)):
			chromosome.append(random.choice(genes))
		population.append(chromosome)
	print("Generated a random population of size", size)
	return population

Calcular la compatibilidad cromosómica

Esta función se utiliza para calcular la compatibilidad de un cromosoma. Toma un cromosoma como argumento y lo itera. Si un cromosoma tiene un valor de 1 en un índice dado, agrega el peso y el valor del elemento correspondiente al peso total y al valor total, respectivamente. Si el peso total es mayor que el peso máximo, la condición física se establece en 0. De lo contrario, la coincidencia se establece en el valor común. Esta función se utiliza en algoritmos genéticos para determinar la aptitud de un cromosoma dado.

def calculate_fitness(chromosome):
	total_weight = 0
	total_value = 0
	for i in range(len(chromosome)):
		if chromosome[i] == 1:
			total_weight += items[i][0]
			total_value += items[i][1]
	if total_weight > max_weight:
		return 0
	else:
		return total_value

Selecciona los cromosomas

Esta función se utiliza para seleccionar dos cromosomas de la población para el cruce. Primero calcula los valores de aptitud de cada cromosoma en la población usando la función compute_fitness(). Luego normaliza los valores de coincidencia dividiendo cada valor por la suma de todos los valores de coincidencia. Finalmente, utiliza la función random.choices() para seleccionar aleatoriamente dos cromosomas de la población en función de sus valores de aptitud normalizados. Los dos cromosomas seleccionados luego se devuelven como cromosomas originales para el cruce.

def select_chromosomes(population):
	fitness_values = []
	for chromosome in population:
		fitness_values.append(calculate_fitness(chromosome))
	
	fitness_values = [float(i)/sum(fitness_values) for i in fitness_values]
	
	parent1 = random.choices(population, weights=fitness_values, k=1)[0]
	parent2 = random.choices(population, weights=fitness_values, k=1)[0]
	
	print("Selected two chromosomes for crossover")
	return parent1, parent2

Realiza un cruce

Esta función realiza el cruce entre dos cromosomas. Toma dos cromosomas madre como entrada y selecciona aleatoriamente un punto de cruce. Luego combina los dos cromosomas maternos en el punto de intersección para formar dos cromosomas hijos. El primer cromosoma hijo se crea tomando la primera parte del primer cromosoma materno y la segunda parte del segundo cromosoma materno. El segundo cromosoma hijo se crea tomando la primera parte del segundo cromosoma materno y la segunda parte del primer cromosoma materno. Finalmente, los dos cromosomas secundarios se devuelven como salida.

def crossover(parent1, parent2):
	crossover_point = random.randint(0, len(items)-1)
	child1 = parent1[0:crossover_point] + parent2[crossover_point:]
	child2 = parent2[0:crossover_point] + parent1[crossover_point:]
	
	print("Performed crossover between two chromosomes")
	return child1, child2

Realiza una mutación

Esta función lleva a cabo la mutación en el cromosoma. Toma un cromosoma como argumento y utiliza el módulo aleatorio para generar un número aleatorio entre 0 y la longitud del cromosoma. Si el valor en el punto de mutación es 0, se cambia a 1, si es 1, se cambia a 0. Luego, la función imprime un mensaje y devuelve el cromosoma mutado. Esta función se puede utilizar para simular mutaciones genéticas en una población de organismos.

def mutate(chromosome):
	mutation_point = random.randint(0, len(items)-1)
	if chromosome[mutation_point] == 0:
		chromosome[mutation_point] = 1
	else:
		chromosome[mutation_point] = 0
	print("Performed mutation on a chromosome")
	return chromosome

Consigue el mejor cromosoma

Esta función toma una población de cromosomas y devuelve el mejor cromosoma de la población. Lo hace generando primero una lista de valores de aptitud para cada cromosoma de la población. Luego encuentra el valor de fitness máximo y su índice correspondiente en la lista. Finalmente, devuelve el cromosoma en el índice del valor máximo de aptitud. Esta función es útil para encontrar el mejor cromosoma de una población de cromosomas y usarlo para operaciones posteriores.

def get_best(population):
	fitness_values = []
	for chromosome in population:
		fitness_values.append(calculate_fitness(chromosome))

	max_value = max(fitness_values)
	max_index = fitness_values.index(max_value)
	return population[max_index]

Bucle de control

Este código ejecuta un algoritmo evolutivo para evolucionar una población de cromosomas. Comienza ciclando a través de un número determinado de generaciones. Para cada generación, se seleccionan dos cromosomas de la población y luego se cruzan para producir dos nuevos cromosomas. Entonces los dos nuevos cromosomas están mutados con cierta probabilidad. Si la probabilidad de origen aleatorio está por encima de un umbral predeterminado, los nuevos cromosomas se someten individualmente a una mutación genética aleatoria. Finalmente, la población anterior se reemplaza por una nueva población que consta de dos cromosomas nuevos y los cromosomas restantes de la población anterior.

for _ in range(generations):
	# select two chromosomes for crossover
	parent1, parent2 = select_chromosomes(population)

	# perform crossover to generate two new chromosomes
	child1, child2 = crossover(parent1, parent2)

	# perform mutation on the two new chromosomes
	if random.uniform(0, 1) < mutation_probability:
		child1 = mutate(child1)
	if random.uniform(0, 1) < mutation_probability:
		child2 = mutate(child2)

	# replace the old population with the new population
	population = [child1, child2] + population[2:]

Si tomamos las funciones anteriores y el ciclo de control, agregamos una lista de elementos a la consola junto con algunos parámetros y algunos resultados, obtenemos la implementación completa de Python a continuación.

Tenga en cuenta que todos los parámetros están codificados por simplicidad; sin embargo, con cierta dificultad, puede aceptar argumentos de la línea de comandos o solicitar la entrada del usuario para cualquiera de ellos, incluidos el número, el valor y el peso de los elementos disponibles.

import random

# function to generate a random population
def generate_population(size):
	population = []
	for _ in range(size):
		genes = [0, 1]
		chromosome = []
		for _ in range(len(items)):
			chromosome.append(random.choice(genes))
		population.append(chromosome)
	print("Generated a random population of size", size)
	return population

# function to calculate the fitness of a chromosome
def calculate_fitness(chromosome):
	total_weight = 0
	total_value = 0
	for i in range(len(chromosome)):
		if chromosome[i] == 1:
			total_weight += items[i][0]
			total_value += items[i][1]
	if total_weight > max_weight:
		return 0
	else:
		return total_value

# function to select two chromosomes for crossover
def select_chromosomes(population):
	fitness_values = []
	for chromosome in population:
		fitness_values.append(calculate_fitness(chromosome))
	
	fitness_values = [float(i)/sum(fitness_values) for i in fitness_values]
	
	parent1 = random.choices(population, weights=fitness_values, k=1)[0]
	parent2 = random.choices(population, weights=fitness_values, k=1)[0]
	
	print("Selected two chromosomes for crossover")
	return parent1, parent2

# function to perform crossover between two chromosomes
def crossover(parent1, parent2):
	crossover_point = random.randint(0, len(items)-1)
	child1 = parent1[0:crossover_point] + parent2[crossover_point:]
	child2 = parent2[0:crossover_point] + parent1[crossover_point:]
	
	print("Performed crossover between two chromosomes")
	return child1, child2

# function to perform mutation on a chromosome
def mutate(chromosome):
	mutation_point = random.randint(0, len(items)-1)
	if chromosome[mutation_point] == 0:
		chromosome[mutation_point] = 1
	else:
		chromosome[mutation_point] = 0
	print("Performed mutation on a chromosome")
	return chromosome

# function to get the best chromosome from the population
def get_best(population):
	fitness_values = []
	for chromosome in population:
		fitness_values.append(calculate_fitness(chromosome))

	max_value = max(fitness_values)
	max_index = fitness_values.index(max_value)
	return population[max_index]


# items that can be put in the knapsack
items = [
		[1, 2],
		[2, 4],
		[3, 4],
		[4, 5],
		[5, 7],
		[6, 9]
	]

# print available items
print("Available items:\n", items)

# parameters for genetic algorithm
max_weight = 10
population_size = 10
mutation_probability = 0.2
generations = 10

print("\nGenetic algorithm parameters:")
print("Max weight:", max_weight)
print("Population:", population_size)
print("Mutation probability:", mutation_probability)
print("Generations:", generations, "\n")
print("Performing genetic evolution:")

# generate a random population
population = generate_population(population_size)

# evolve the population for specified number of generations
for _ in range(generations):
	# select two chromosomes for crossover
	parent1, parent2 = select_chromosomes(population)

	# perform crossover to generate two new chromosomes
	child1, child2 = crossover(parent1, parent2)

	# perform mutation on the two new chromosomes
	if random.uniform(0, 1) < mutation_probability:
		child1 = mutate(child1)
	if random.uniform(0, 1) < mutation_probability:
		child2 = mutate(child2)

	# replace the old population with the new population
	population = [child1, child2] + population[2:]

# get the best chromosome from the population
best = get_best(population)

# get the weight and value of the best solution
total_weight = 0
total_value = 0
for i in range(len(best)):
	if best[i] == 1:
		total_weight += items[i][0]
		total_value += items[i][1]

# print the best solution
print("\nThe best solution:")
print("Weight:", total_weight)
print("Value:", total_value)

Guarde el código anterior en un archivo knapsack_ga.pyy luego ejecutarlo escribiendo python knapsack_ga.py.

El resultado de ejemplo es el siguiente:

Available items:
[[1, 2], [2, 4], [3, 4], [4, 5], [5, 7], [6, 9]]

Genetic algorithm parameters:
Max weight: 10
Population: 10
Mutation probability: 0.2
Generations: 10 

Performing genetic evolution:
Generated a random population of size 10
Selected two chromosomes for crossover
Performed crossover between two chromosomes
Performed mutation on a chromosome
Selected two chromosomes for crossover
Performed crossover between two chromosomes
Performed mutation on a chromosome
Selected two chromosomes for crossover
Performed crossover between two chromosomes
Selected two chromosomes for crossover
Performed crossover between two chromosomes
Selected two chromosomes for crossover
Performed crossover between two chromosomes
Selected two chromosomes for crossover
Performed crossover between two chromosomes
Selected two chromosomes for crossover
Performed crossover between two chromosomes
Selected two chromosomes for crossover
Performed crossover between two chromosomes
Performed mutation on a chromosome
Selected two chromosomes for crossover
Performed crossover between two chromosomes
Selected two chromosomes for crossover
Performed crossover between two chromosomes
Performed mutation on a chromosome

The best solution:
Weight: 10
Value: 14

Y te fuiste Ahora sabes cómo usar la programación genética para resolver el problema de la bolsa. Con un poco de ingenio, el script anterior se puede modificar para resolver todo tipo de problemas computacionalmente complejos para obtener las mejores soluciones "suficientemente buenas".

¡Gracias por leer!

Partes de este artículo fueron diseñadas y/o escritas con la ayuda de GPT-3.

Mateo Mayo (@mattmayo13) es científico de datos y editor en jefe de KDnuggets, el principal recurso en línea de ciencia de datos y aprendizaje automático. Sus intereses incluyen el procesamiento del lenguaje natural, el diseño y la optimización de algoritmos, el aprendizaje no supervisado, las redes neuronales y los enfoques automatizados para el aprendizaje automático. Matthew tiene una Maestría en Ciencias de la Computación y una Maestría en Procesamiento de Datos. Se le puede contactar en kdnuggets en editor1[dot]com.