Introducción
La optimización combinatoria es una rama de la optimización matemática que se centra en problemas donde el objetivo es encontrar el mejor objeto de un conjunto finito de objetos. Estos problemas son comunes en diversas áreas como la logística, la planificación, las redes y la bioinformática. En este tema, exploraremos varias técnicas y algoritmos utilizados para resolver problemas de optimización combinatoria.
Conceptos Clave
- Problema de Optimización Combinatoria: Un problema donde se busca encontrar el mejor objeto (solución) de un conjunto finito de objetos.
- Espacio de Soluciones: El conjunto de todas las posibles soluciones de un problema.
- Función Objetivo: Una función que asigna un valor a cada solución en el espacio de soluciones, indicando su calidad.
- Restricciones: Condiciones que deben cumplir las soluciones válidas.
Algoritmos Clásicos
- Algoritmo de Fuerza Bruta
El algoritmo de fuerza bruta evalúa todas las posibles soluciones y selecciona la mejor. Aunque es simple y garantiza encontrar la solución óptima, es ineficiente para problemas grandes debido a su complejidad exponencial.
Ejemplo: Problema del Viajante (TSP)
from itertools import permutations
def calculate_distance(path, distance_matrix):
return sum(distance_matrix[path[i]][path[i + 1]] for i in range(len(path) - 1))
def tsp_brute_force(distance_matrix):
n = len(distance_matrix)
all_permutations = permutations(range(n))
min_distance = float('inf')
best_path = None
for perm in all_permutations:
current_distance = calculate_distance(perm + (perm[0],), distance_matrix)
if current_distance < min_distance:
min_distance = current_distance
best_path = perm
return best_path, min_distance
# Ejemplo de uso
distance_matrix = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]
best_path, min_distance = tsp_brute_force(distance_matrix)
print(f"Mejor ruta: {best_path}, Distancia mínima: {min_distance}")
- Algoritmo de Ramificación y Poda (Branch and Bound)
Este algoritmo explora el espacio de soluciones de manera más eficiente que la fuerza bruta, utilizando una estructura de árbol y podando ramas que no pueden contener la solución óptima.
Ejemplo: Problema de la Mochila (Knapsack)
def knapsack_branch_and_bound(weights, values, capacity):
n = len(weights)
max_value = 0
best_combination = []
def bound(i, current_weight, current_value):
if current_weight >= capacity:
return 0
upper_bound = current_value
total_weight = current_weight
for j in range(i, n):
if total_weight + weights[j] <= capacity:
total_weight += weights[j]
upper_bound += values[j]
else:
upper_bound += (capacity - total_weight) * values[j] / weights[j]
break
return upper_bound
def branch_and_bound(i, current_weight, current_value, current_combination):
nonlocal max_value, best_combination
if i == n:
if current_value > max_value:
max_value = current_value
best_combination = current_combination[:]
return
if current_weight + weights[i] <= capacity:
current_combination.append(i)
branch_and_bound(i + 1, current_weight + weights[i], current_value + values[i], current_combination)
current_combination.pop()
if bound(i + 1, current_weight, current_value) > max_value:
branch_and_bound(i + 1, current_weight, current_value, current_combination)
branch_and_bound(0, 0, 0, [])
return best_combination, max_value
# Ejemplo de uso
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5
best_combination, max_value = knapsack_branch_and_bound(weights, values, capacity)
print(f"Mejor combinación: {best_combination}, Valor máximo: {max_value}")
- Algoritmo de Recocido Simulado (Simulated Annealing)
Este algoritmo es una técnica probabilística para aproximar la solución óptima de un problema. Se basa en el proceso de recocido en metalurgia, donde un material se calienta y luego se enfría lentamente para eliminar defectos.
Ejemplo: Problema del Viajante (TSP)
import random
import math
def tsp_simulated_annealing(distance_matrix, initial_temp, cooling_rate):
def calculate_distance(path):
return sum(distance_matrix[path[i]][path[i + 1]] for i in range(len(path) - 1))
def get_neighbour(path):
a, b = random.sample(range(len(path)), 2)
path[a], path[b] = path[b], path[a]
return path
n = len(distance_matrix)
current_path = list(range(n))
random.shuffle(current_path)
current_distance = calculate_distance(current_path + [current_path[0]])
best_path = current_path[:]
best_distance = current_distance
temp = initial_temp
while temp > 1:
new_path = get_neighbour(current_path[:])
new_distance = calculate_distance(new_path + [new_path[0]])
if new_distance < current_distance or math.exp((current_distance - new_distance) / temp) > random.random():
current_path = new_path
current_distance = new_distance
if new_distance < best_distance:
best_path = new_path
best_distance = new_distance
temp *= cooling_rate
return best_path, best_distance
# Ejemplo de uso
distance_matrix = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]
initial_temp = 1000
cooling_rate = 0.99
best_path, best_distance = tsp_simulated_annealing(distance_matrix, initial_temp, cooling_rate)
print(f"Mejor ruta: {best_path}, Distancia mínima: {best_distance}")Ejercicios Prácticos
Ejercicio 1: Problema del Viajante (TSP) con Fuerza Bruta
Descripción: Implementa el algoritmo de fuerza bruta para resolver el problema del viajante con una matriz de distancias diferente.
Matriz de distancias:
Solución:
from itertools import permutations
def calculate_distance(path, distance_matrix):
return sum(distance_matrix[path[i]][path[i + 1]] for i in range(len(path) - 1))
def tsp_brute_force(distance_matrix):
n = len(distance_matrix)
all_permutations = permutations(range(n))
min_distance = float('inf')
best_path = None
for perm in all_permutations:
current_distance = calculate_distance(perm + (perm[0],), distance_matrix)
if current_distance < min_distance:
min_distance = current_distance
best_path = perm
return best_path, min_distance
# Ejemplo de uso
distance_matrix = [
[0, 29, 20, 21],
[29, 0, 15, 17],
[20, 15, 0, 28],
[21, 17, 28, 0]
]
best_path, min_distance = tsp_brute_force(distance_matrix)
print(f"Mejor ruta: {best_path}, Distancia mínima: {min_distance}")Ejercicio 2: Problema de la Mochila con Ramificación y Poda
Descripción: Implementa el algoritmo de ramificación y poda para resolver el problema de la mochila con diferentes pesos y valores.
Pesos: [1, 2, 3, 8]
Valores: [20, 5, 10, 40]
Capacidad: 10
Solución:
def knapsack_branch_and_bound(weights, values, capacity):
n = len(weights)
max_value = 0
best_combination = []
def bound(i, current_weight, current_value):
if current_weight >= capacity:
return 0
upper_bound = current_value
total_weight = current_weight
for j in range(i, n):
if total_weight + weights[j] <= capacity:
total_weight += weights[j]
upper_bound += values[j]
else:
upper_bound += (capacity - total_weight) * values[j] / weights[j]
break
return upper_bound
def branch_and_bound(i, current_weight, current_value, current_combination):
nonlocal max_value, best_combination
if i == n:
if current_value > max_value:
max_value = current_value
best_combination = current_combination[:]
return
if current_weight + weights[i] <= capacity:
current_combination.append(i)
branch_and_bound(i + 1, current_weight + weights[i], current_value + values[i], current_combination)
current_combination.pop()
if bound(i + 1, current_weight, current_value) > max_value:
branch_and_bound(i + 1, current_weight, current_value, current_combination)
branch_and_bound(0, 0, 0, [])
return best_combination, max_value
# Ejemplo de uso
weights = [1, 2, 3, 8]
values = [20, 5, 10, 40]
capacity = 10
best_combination, max_value = knapsack_branch_and_bound(weights, values, capacity)
print(f"Mejor combinación: {best_combination}, Valor máximo: {max_value}")Conclusión
En esta sección, hemos explorado varios algoritmos de optimización combinatoria, incluyendo fuerza bruta, ramificación y poda, y recocido simulado. Cada uno de estos algoritmos tiene sus propias ventajas y desventajas, y la elección del algoritmo adecuado depende de la naturaleza del problema y las restricciones de tiempo y recursos. En los ejercicios prácticos, hemos aplicado estos algoritmos a problemas clásicos como el problema del viajante y el problema de la mochila, proporcionando una comprensión más profunda de cómo funcionan en la práctica.
En el siguiente módulo, profundizaremos en los algoritmos de optimización combinatoria más avanzados, como los algoritmos genéticos y la optimización de colonia de hormigas.
Algoritmos Avanzados
Módulo 1: Introducción a los Algoritmos Avanzados
Módulo 2: Algoritmos de Optimización
- Programación Lineal
- Algoritmos de Optimización Combinatoria
- Algoritmos Genéticos
- Optimización de Colonia de Hormigas
Módulo 3: Algoritmos en Grafos
- Representación de Grafos
- Búsqueda en Grafos: BFS y DFS
- Algoritmos de Caminos Mínimos
- Algoritmos de Flujo Máximo
- Algoritmos de Emparejamiento en Grafos
Módulo 4: Algoritmos de Búsqueda y Ordenación
Módulo 5: Algoritmos de Aprendizaje Automático
- Introducción al Aprendizaje Automático
- Algoritmos de Clasificación
- Algoritmos de Regresión
- Redes Neuronales y Deep Learning
- Algoritmos de Clustering
Módulo 6: Casos de Estudio y Aplicaciones
- Optimización en la Industria
- Aplicaciones de Grafos en Redes Sociales
- Búsqueda y Ordenación en Grandes Volúmenes de Datos
- Aplicaciones de Aprendizaje Automático en la Vida Real