Influence of the Alternative Objective Functions in the Optimization of the Cyclic Cutwidth Minimization Problem

Resumen

The quality of the solutions to a combinatorial optimization problem is usually measured using a mathematical function, named objective function. This function is also used to guide heuristic procedures through the solution space, helping to detect promising search directions (i.e., it helps to compare the quality of different solutions). However, this task becomes very hard when many solutions are evaluated with the same value by the objective function. This fact commonly occurs in either max-min/min-max optimization problems. In those situations, a key strategy relies on the introduction of an alternative objective function. This function helps to determine which solution is more promising when the compared ones achieve the same value of the original objective function. In this paper we study the Cyclic Cutwidth Minimization Problem (CCMP), which is an example of a min-max optimization problem. Particularly, we analyze the influence in the search of using alternative objective functions within local search procedures. Also, we propose two alternative objective functions for the CCMP and compare its performance against a previously introduced one. Finally, we explored the combination of more than one alternative function.

Sergio Cavero

Estudiante de Doctorado en Inteligencia Artificial

Sergio Cavero nació en Madrid (España) el 24 de septiembre de 1997. Se graduó en Ingeniería del Software por la Universidad Politécnica de Madrid en 2019. Durante sus estudios de grado realizó una estancia en la Universidad de Bradford (Reino Unido). Además, fue galardonado en dos ocasiones con la Beca de Excelencia de la Comunidad de Madrid, así como con el premio al Mejor Proyecto Fin de Carrera. Posteriormente, realizó un Máster en Inteligencia Artificial en la misma universidad (UPM) obteniendo los premios al Mejor Expediente Académico (‘Premio José Cuena’) y al Mejor Trabajo Fin de Máster. Sus resultados académicos le permitieron ser beneficiario de una de las ‘Ayudas para la Formación de Profesorado Universitario (FPU)’, financiadas por el Gobierno español. Actualmente realiza su tesis doctoral en la Universidad Rey Juan Carlos, dirigida por los profesores Abraham Duarte y Eduardo G. Pardo. Sus principales intereses de investigación se centran en la interfaz entre las Ciencias de la Computación, la Inteligencia Artificial y la Investigación Operativa. La mayoría de sus publicaciones tratan sobre el desarrollo de procedimientos metaheurísticos para problemas de optimización modelados por grafos.

Eduardo García Pardo

Profesor Titular de Universidad

Miembro fundador del grupo de investigación GRAFO, cuya línea de investigación principal es el desarrollo de algoritmos para abordar problemas de optimización, temática sobre la que versa la Tesis Doctoral del investigador y en la que se enmarcan sus publicaciones más destacadas.

Abraham Duarte

Catedrático de Universidad

Mi carrera investigadora se ha centrado en el desarrollo de nuevos algoritmos y técnicas de Inteligencia Computacional (metaheurísticas) y su aplicación a diferentes problemas en Ciencia e Ingeniería desde que me incorporé a la Universidad Rey Juan Carlos (URJC) en el octubre del año 2000.