Heurísticas de optimización combinatoria para la clasificación de datos

En el presente proyecto de investigación se realizó la implementación de las heurísticas de algoritmo genético, enjambre de partículas (EP) y búsqueda tabú (BT) para el estudio del problema de clasificación por particiones con datos cuantitativos. En total se implementaron cuatro algoritmos, dado que en el caso de búsqueda tabú se diseñaron dos variantes. Una de ellas constituyó en la generación de vecindarios mediante transferencias de individuos de una clase a otra; mientras que la otra consistió en la construcción de los vecinos mediante el movimiento de los centros de gravedad de las clases (BTCG).

Los algoritmos fueron aplicados a veinte tablas de datos tomadas de la literatura. Además, se diseñaron ocho tablas adicionales de mayor tamaño y complejidad, para verificar el rendimiento de los algoritmos. Se realizó, además, un análisis de la variabilidad de los resultados, en función de los parámetros de las diferentes heurísticas. Esto permitió determinar, para cada una de ellas, la combinación de parámetros que generó el mejor rendimiento posible en cada heurística. Además, se realizó una comparación de la eficiencia de las heurísticas implementadas, lo cual permitió generar una jerarquización de ellas como función del rendimiento, siendo BTCG y EP las que mostraron mejores resultados.

Resultados

1. Se logró la implementación de tres heurísticas de optimización combinatoria para estudiar el problema de particionamiento de individuos en presencia de datos cuantitativos (algoritmo genético, enjambre de partículas y búsqueda tabú). Con la característica adicional que la heurística de búsqueda tabú fue implementada siguiendo dos estrategias diferentes para la generación de vecinos. Esto potenció el haber culminado con cuatro algoritmos heurísticos para el estudio del problema en cuestión (PRIMER OBJETIVO ESPECIFÍCO).  
2. Del proceso de investigación se derivaron un conjunto de estrategias que potencializaron el rendimiento de las heurísticas. Como ejemplos particulares se pueden citar: la mejora de k−medias en todas las heurísticas, el método de paro en todas las heurísticas, la mejora de reinicio en las heurísticas de búsqueda tabú y la definición del operador de cruce y el operador de selección en el algoritmo genético. 
3. Se realizó un análisis de los parámetros en cada uno de los algoritmos, del cual se desprendieron los valores que deben asignarse a los diferentes parámetros de las heurísticas para potenciar su rendimiento (SEGUNDO OBJETIVO ESPECÍFICO).  
4. Se realizó una comparación del rendimiento, con respecto a los porcentajes de atracción y tiempos de ejecución, de las tres heurísticas implementadas en la investigación. Esto permitió jerarquizar a las heurísticas de búsqueda tabú mediante movimiento de centros gravedad (BT-CG) y enjambre de partículas en su versión EP-1, como las heurísticas de mejor rendimiento. Aportando evidencia que al aumentar significativamente la cantidad de individuos que conforman la tabla de datos, es la heurística BT-CG la que experimenta menos aumento en los tiempos de ejecución (TERCER OBJETIVO ESPECÍFICO).  
5. Se diseñó una heurística híbrida entre las dos mejores heurísticas, a saber, entre enjambre de partículas y búsqueda tabú (CUARTO OBJETIVO ESPECÍFICO). Se advierte que a pesar de las diferentes aristas exploradas y que el algoritmo híbrido generó buenos porcentajes de atracción, no cumplió con la expectativa de mejorar las heurísticas previamente implementadas. Los altos tiempos de ejecución fue un punto que en cierta medida hace concluir que el proceso de hibridación no fue del todo exitoso.