Problemas de Optimización Decepcionantes Dinámicos, experimentación con Metaheurísticas

• Jenny Fajardo Calderín ^[1] ; Claudia Cañedo Espino ^[1] ; Alejandro Rosete Suárez ^[1] ; Antonio Masegosa Arredondo ^[2] ; David A. Pelta ^[2]
  1. [1] Instituto Superior Politécnico José Antonio Echeverría
  2. [2] Grupo de Investigación en Modelos de Decisión y Optimización DECSAI
• Localización: Revista Cubana de Ciencias Informáticas, ISSN-e 2227-1899, Vol. 9, Nº. 0, 2015
• Idioma: español
• Títulos paralelos:
  • Deceptive Dynamic Optimization Problems, experimentation with Metaheuristics
• Enlaces
  • Texto completo
• Resumen
  • español

    Dentro del campo de la optimización existen una serie de problemas llamados NP, que son aquellos que pueden ser resueltos por un algoritmo no determinístico en un tiempo polinomial de resolución. Debido a que el mundo real no es estático, sino dinámico, se crea la necesidad de acercar dichos problemas de prueba a la realidad, de ahí que surgieran los problemas de optimización dinámicos (PODs). Uno de los problemas clásicos de optimización que existen, son los problemas decepcionantes o engañosos, que son problemas de prueba de generación binaria a partir de XOR. Son llamados engañosos porque a los algoritmos les cuesta mucho obtener mejoras, ya que cuando se mejora la solución con una heurística se empeora la evaluación en la función objetivo. En los últimos años ha habido un creciente interés por la modelación de los problemas dinámicos de optimización y su solución con los algoritmos metaheurísticos. Por ello, el objetivo de esta investigación es analizar el comportamiento de las metaheurísticas clásicas frente a los problemas decepcionantes dinámicos, específicamente con cinco funciones decepcionantes y evaluando el rendimiento de los algoritmos aplicando test estadísticos no paramétricos. Además se realiza una comparación de los resultados del mejor algoritmo con dos algoritmos del estado de arte para resolver problemas de optimización dinámicos: Adaptive Hill Climbing Memetic Algorithm y Self Organized Random Immigrants Genetic Algorithm.

  • English

    In the optimization field there are a number of problems called NP, which are those that can be solved by a nondeterministic polynomial time algorithm for a resolution. Because the real world is not static, but dynamic, the need to bring these problems to test reality is created, hence arise dynamic optimization problems (PODs). One of the classic optimization problems that exist, are disappointing or deceptive problems, which are problems of test generation from binary XOR. They are called deceptive because the algorithms have a hard time getting improvements, because when solution is improved heuristic evaluation worsens the objective function. In recent years there has been an increasing interest in the modeling of dynamic optimization problems and their solution with metaheuristic algorithms. Therefore, the objective of this research is to analyze the behavior of the classical metaheuristics disappointing compared to dynamic problems, specifically with five disappointing functions and evaluating the performance of algorithms using non-parametric statistical test. Furthermore a comparison of the results of the best algorithm with two the state of art algorithms are usually done to solve dynamic optimization: Adaptive Hill Climbing Memetic Algorithm y Self Organized Random Immigrants Genetic Algorithm.

• Referencias bibliográficas
  • BERSON, A,SMITH, S. J. (1997). Data Warehousing, Data Mining, and OLAP, McGraw-Hill, Inc.
  • BOUMAN, R,VAN DONGEN, J. (2009). Pentaho Solutions: Business Intelligence and Data Warehousing with Pentaho and MySQL. Wiley Publishing. Indianapolis^eIndiana...
  • CASTELLANOS, M,SIMITSIS, A,WILKINSON, K,DAYAL, U. (2009). Automating the Loading of Business Process Data Warehouses. ACM.
  • CASTERS, M,BOUMAN, R,VAN DONGEN, J. (2010). Pentaho Kettle Solutions: Building Open Source ETL Solutions with Pentaho Data Integration. Wiley...
  • DÍAZ, L,LÓPEZ, B,LÓPEZ, D. (2013). Integración de Datos. “Universidad Central “Marta Abreu” de las Villas”.
  • ECCLES, M. J. (2013). Pragmatic Development of Service Based Real-Time Change Data Capture. Aston University.
  • EL-SAPPAGH, S. H. A,HENDAWI, A. M. A,EL BASTAWISSY, A. H. (2011). A proposed model for data warehouse ETL processes. 23. 91-104
  • GARCÍA, J. L. (2014). Automatización de los procesos de carga en el mercado de datos Recursos Humanos de la UCLV. Universidad Central “Marta...
  • JÖRG, T,DESSLOCH, S. (2008). Towards generating ETL processes for incremental loading. ACM. Coimbra.
  • JÖRG, T,DESSLOCH, S. (2009). Formalizing ETL Jobs for Incremental Loading of Data Warehouses.
  • JÖRG, T,DESSLOCH, S. (2010). Real-Time Data Warehousing Using State-of-the-Art ETL Tools.. Springer-Verlag. Heidelberg.
  • KIMBALL, R,CASERTA, J. (2004). The Data Warehouse ETL Toolkit. Wiley Publishing. Indianapolis^eIndiana Indiana.
  • KIMBALL, R,REEVES, L. (1998). The Data Warehouse Lifecycle Toolkit: Expert Methods for Designing, Developing, and Deploying Data Warehouses....
  • KIMBALL, R,ROSS, M. (2002). The Data Warehouse Toolkit: The Complete Guide to Dimensional Modeling. John Wiley and Sons. New York.
  • KIMBALL, R,ROSS, M. (2008). The Data Warehouse Lifecycle Toolkit. John Wiley & Sons.
  • LABIO, W. J,GARCÍA-MOLINA, H. (1995). Comparing very large database snapshots. Stanford University.
  • LABIO, W. J,GARCÍA-MOLINA, H. (1996). Efficient Snapshot Differential Algorithms for Data Warehousing. Proceedings of VLDB ’96.
  • MASÓ, A,CASTELLÓN, Y. (2013). Mercado de datos en apoyo a la toma de decisiones sobre el personal docente e investigativo en el departamento...
  • MUNDY, J. (2008). Design Tip #99 Staging Areas and ETL Tools.
  • RAM, P,DO, L. (2000). Extracting Delta for Incremental Data Warehouse Maintenance. IEEE.
  • ROSS, M. (2013). Design Tip #152 Slowly Changing Dimension Types 0, 4, 5, 6 and 7.
  • TELLEZ, Y,MEDINA, D,TORRES, R. E. (2012). Propuesta para la Implementación de las Dimensiones Lentamente Cambiantes con Pentaho Data Integration....
  • VASSILIADIS, P. (2009). A survey of Extract-transform-Load technology. 5.
  • VILLARREAL, R. X. (2013). Estudio de metodologías de Data Warehouse para la implementación de repositorios de información para la toma de...
  • YUAN, G,LI, B,XIAO, T. (2011). Improvement of Snapshot Differential Algorithm Based on Hadoop Platform. IEEE.