user_mobilelogo

Generación automática de algoritmos. 

Existe una gran variedad de problemas de optimización de alto interés práctico  para los cuales la obtención de la solución óptima es una tarea computacionalmente impracticable. Tales problemas surgen en los más diversas áreas de la ingeniería como por ejemplo en: la distribución óptima de turbinas eólicas,  el ruteamiento de vehículos del transporte público con minimización de pérdida de CO2 al ambiente, la sintonización de parámetros de los algoritmos heurísticos, la programación de las tareas que se deben realizar en la fundición de concentrado de cobre, la definición de turnos laborales, la determinación de dietas apropiadas para evitar la obesidad de niños, etc. La incesante búsqueda de buenos algoritmos para determinar la solución óptima de este tipo de problemas ha generado -mediante la investigación científica- variados métodos heurísticos que permiten determinar soluciones cercanas a la óptima para cada uno de estos problemas. Tales métodos se implementan mediante un algoritmo, que es lo que finalmente se programa en el computador.  Al detenerse en el tiempo y observar todo lo que ha ocurrido durante los últimos 30 años se constata que  la mayoría de los algoritmos contienen prácticamente los mismos componentes elementales. Se trata de algoritmos que buscan la solución óptima a través de un proceso iterativo que inspecciona el espacio delimitado por las restricciones del propio problema de optimización. El diseño de estos algoritmos -tarea propia de la ingeniería informática- requiere de alto nivel de conocimiento en el campo de la optimización, de práctica y al final, resulta siendo un proceso prácticamente artesanal. En esta línea de investigación hemos planteado que tales algoritmos pueden ser obtenido por un computador. Son identificados los componentes principales presentes en los algoritmos heurísticos y a partir de ellos, se construye paso a paso el algoritmo más apropiado para cada problema. De este modo la generación automática de algoritmos ocurre resolviendo un problema que también es de optimización y que consiste en determinar el mejor algoritmo en el espacio de posibilidades que a su vez tenga el mejor desempeño computacional para resolver un problema dado. Varios problemas han sido estudiados con este enfoque y nuevos, novedosos y eficientes algoritmos han sido encontrados para cada problema: el problema del vendedor viajero, el problema del árbol de cobertura de costo mínimo generalizado, etc.