Algoritmos sociales jerárquicosuna metaheurística basada en la hibridación entre métodos constructivos y evolutivos

Résumé

EN ESTA TESIS DOCTORAL SE INTRODUCE UNA NUEVA METAHEURÍSTICA LLAMADA ALGORITMOS SOCIALES JERÁRQUICOS O ALGORITMOS HS, QUE SE INSPIRA EN LAS ESTRUCTURAS Y EN EL COMPORTAMIENTO JERÁRQUICO QUE SE OBSERVA EN DIVERSIDAD DE ORGANIZACIONES HUMANAS. LA IDEA FUNDAMENTAL DE LOS ALGORITMOS HS RESIDE EN LA OPTIMIZACIÓN SIMULTÁNEA DE UN CONJUNTO DINÁMICO DE SOLUCIONES FACTIBLES Y DISJUNTAS. EL PROBLEMA SE MODELA COMO UNA SOCIEDAD QUE SE DIVIDE JERÁRQUICAMENTE EN GRUPOS, DONDE CADA GRUPO DE LA SOCIEDAD REPRESENTA UNA SOLUCIÓN FACTIBLE. EN LA EMPLEMENTACIÓN MÁS SENCILLA, ESTOS GRUPOS SE DISTRIBUYEN INCIALMENTE DE FORMA ALEATORAI SOBRE EL ESPACIO DE SOLUCIONES. MEDIANTE LAS ESTRATEGIAS DE EVOLUCIÓN SOCIAL, CADA GRUPO COMPITE CON SUS GRUPOS VECINOS, ENCONTRANDO SOLUCIONES MEJORES. EN ESTA EVOLUCIÓN SOCIAL, LOS GRUPOS DE PEOR CALIDA TIENDEN A DESAPARECER, ENRIQUECIENDO A LOS GRUPOS DE MEJOR CALIDAD. AL FINAL DEL PROCESO SOCIAL SÓLO SOBRVIVE UN GRUPO QUE CONTIEN LA SOLUCIÓN AL PROBLEMA PLANTEADO. LOS ALGORITMOS HS SE HAN APLICADO CON ÉXITO A LA RESOLUCIÓN DE PROBLEMAS COMBINATORIOS QUE PERTENECEN TANTO A LA CLASE P COMO NP. EL PRIMER PROBLEMA QUE SE HA RESUELTO UTILIZANDO LA METAHEURÍSTICA PROPUESTA ES EL PROBLEMA DEL CIRCUITO CRÍTICO EN UN GRAFO DIRIGIDO EN CUALQUIERA DE SUS VERSIONES: MÁXIMO CICLO MEDIO, MÁXIMA RELACIÓN BENEFICIO TIEMPO Y SUS VERSIONES DUALES, MÍNIMO CICLO MEDIO Y MÍNIMA RELACIÓN COSTE TIEMPO. LA RESOLUCIÓN DE CUALQUIERA DE ESTAS CUATRO VARIANTES SE LLEVA A CABO A TRAVÉS DE UNA GENERALIZACIÓN Y REINTERPRETACIÓN DEL ALGORITMO DE HOWARD EN EL MARCO DE LOS ALGORITMOS HS. ADEMÁS, SE INTRODUCEN UNA SERIE DE OPERADORES SOCIALES QUE MEJORAN EL COMPORTAMIENTO DEL ALGORITMOS ORIGINAL. PARA CONOCER LA EFICIENCIA DE LA METAHEURÍSTICA PROPUESTA, ÉSTA SE HA COMPORTADO EXPERIMENTALMENTE CON LOS ALGORITMOS DE KARP, LAWLER + BELLMAN-FORD ADAPTATIVO Y HOWARD. EN SEGUNDO LUGAR, LOS ALGORITMOS HS SE HAN APLICADO A PROBLEMAS