Project II de Optimización · 4º curso, Grado en Ciencia de Datos · ETSINF, Universitat Politècnica de València
Carteras diversificadas con GRASP-ILS
Metaheurística híbrida para selección de activos con cardinalidad y retorno mínimo
Autores: Javier Elena Navarro · Luminița Ciobanu Borinschi · Pau Amores Giner · Rustam Suleimanov
1,33
ranking medio (1º entre 4)
+44%
mejora vs GA en n=1000, k=100
60 s
presupuesto por instancia
10¹³⁹
tamaño del espacio (n=1000, k=100)
Problema
Selección de cartera diversificada: hay que elegir exactamente k activos de un universo de n y asignarles pesos para maximizar la diversidad por pares (suma ponderada de la matriz de distancias dᵢⱼ). Sujeta a presupuesto total = 1, retorno esperado mínimo R y vínculo entre selección y peso. Es MIQP no convexo: para n=1000, k=100 hay ≈6,39 × 10¹³⁹ combinaciones, así que la enumeración exacta queda fuera de juego.
Diseño del algoritmo
Híbrido GRASP + ILS. El GRASP construye carteras por pasos con un score que mezcla retorno normalizado y diversidad acumulada, y elige aleatoriamente dentro de una Restricted Candidate List controlada por α. Después un operador explícito de restauración de factibilidad reasigna pesos para cumplir el retorno mínimo. La búsqueda local hace swaps de un activo dentro por uno fuera con estrategia first-improvement, que maximiza el número de iteraciones dentro del presupuesto temporal.
Tuning
Probamos tres niveles de codicia: α = 0,05 (greedy), 0,15 (balanceado) y 0,30 (random). El balanceado gana con ranking medio 1,2 y la menor varianza. Los extremos fallan: 0,05 converge prematuro en instancias grandes; 0,30 no explota las regiones buenas.
Resultados
Sobre 9 instancias de hasta n=1000, GRASP-ILS gana en 7 y empata en 2 (las pequeñas, donde todos llegan al óptimo). Ranking medio 1,33 frente a 2,56 (GA), 2,67 (Greedy) y 3,44 (Random). La diferencia se nota más a gran escala: en n=1000, k=100 mejora un 44% al GA.
Conclusiones
Separar selección de pesos, garantizar factibilidad por construcción y aceptar la primera mejora son las tres decisiones que hacen al algoritmo competitivo bajo presión temporal. Quedan abiertas extensiones interesantes: control adaptativo de α, pool elite con path relinking, evaluación paralela del vecindario y construcción guiada por ML.