El grupo de sistemas de optimización aplicada tiene como principal objetivo la aplicación de la tecnología y la ciencia en el entorno industrial y comercial. Para ello, hemos trabajado desde hace varios años en la creación de un framework llamado FACOP que está ideado para facilitar la implantación y el desarrollo de algoritmos de optimización.
Como ya comentamos en entradas anteriores, el grupo SOA ha creado también, herramientas que permiten el despliegue y utilización de FACOP.
En esta entrada del blog comentaremos algunas herramientas que hemos desarrollado para acelerar y mejorar el desarrollo de nuevos algoritmos y su inclusión en FACOP. Como así también otras herramientas centradas en la experimentación a gran escala.
Si bien el objetivo del grupo siempre ha sido la aplicación del conocimiento en organizaciones de todo tipo, como industrias, comercios e incluso el sector público, indudablemente la investigación, diseño y desarrollo de algoritmos de optimización debe tener una base.
Esta base debe partir de una parte teórica, claro está, como el estudio de literatura en diversos temas de optimización y también la publicación de artículos científicos. En el desarrollo de la base teórica se proponen nuevas formas para resolver problemas de optimización generales o específicos, si queremos centrarnos en un problema de optimización particular de alguna organización.
Para resolver un problema de optimización utilizando la computación como elemento central es necesario diseñar y desarrollar una representación digital de un problema de la vida real. Por ejemplo, si una empresa de transporte quiere encontrar la mejor ruta para llevar sus productos a una serie de usuarios o clientes, este problema de optimización se representa mediante un VRP (Vehicle Routing Problem). Esta representación teórica se puede plasmar en un algoritmo o en modelo matemático. En cualquier caso, la representación teórica se pasa a una representación digital, es decir se traduce de alguna forma a software.
Desarrollar software que sea capaz de representar (y resolver) un problema de optimización pasa por varias fases como diseño, desarrollo, prueba y comparación.
Volviendo al ejemplo del VRP, en la fase de diseño del algoritmo (también comúnmente llamado heurística o metaheurística) se considera la representación de la información real desde el punto de vista del software. Por ejemplo, la información necesaria acerca de los vehículos tal como velocidad y capacidad, la información de los puntos de entrega (por lo general coordenadas o dirección en un mapa) y el tiempo (o distancia) entre dos puntos de entrega diferentes. En la fase de desarrollo del algoritmo se toma esta representación teórica que se ha creado en la parte del diseño y se lleva a cabo la programación del algoritmo.
El algoritmo, entonces constituye una pieza de software basado en una representación teórica de un problema de optimización. Aun así, quedan algunas preguntas que responder: ¿Cómo sabemos si nuestro algoritmo funciona como corresponde? ¿Cómo sabemos que este algoritmo que acabamos de desarrollar obtiene buenos resultados o es mejor que otro algoritmo? ¿Cómo podemos determinar si los parámetros del algoritmo son los mejores para resolver cierto problema de optimización?
Para responder a estas preguntas necesitamos varias cosas como, por ejemplo, una forma de medir el resultado del algoritmo y una forma de estimar su comportamiento futuro.
Si un algoritmo es capaz de representar un problema de optimización, su resultado o solución representa a su vez un posible estado viable de este mismo problema. En el caso antes nombrado del VRP, el resultado del algoritmo, llamado comúnmente solución, es un conjunto ordenado de paradas que indica en que orden y en qué momento (horarios) el vehículo visitará cada parada donde debe realizar una entrega o descarga de mercancías.
Así, en el proceso de creación y prueba de algoritmo se deben realizar una serie de pasos repetitivos que requieren de una gran capacidad de cómputo. Estos procesos pueden llevarse a cabo de manera manual, lo cual es engorroso y consume mucho tiempo o podemos crear software que permitan a una persona automatizarlos parcial o totalmente.
El proyecto DIICEA (Desarrollo de Indicadores e Investigación en Cálculos Estadísticos Automatizados para optimización) está ideado para desarrollar ciertas herramientas necesarias para el diseño, desarrollo, comparación y ejecución de algoritmos de optimización.
Cuando se diseñan y desarrollan algoritmos capaces de resolver problemas de optimización existen una serie de tareas repetitivas y que requieren un gran esfuerzo, particularmente la ejecución de experimentos masivos para luego realizar comparaciones de resultados de diferentes algoritmos, o de un mismo algoritmo cuando se intenta determinar la mejor combinación de parámetros. La propia comparación de estos resultados requiere también de gran capacidad de cómputo.
El objetivo del proyecto DIICEA es proveer de algunas herramientas que faciliten estas tareas. Estas herramientas están pensadas para cubrir necesidades en tres pasos fundamentales de la creación, prueba y ejecución de algoritmos de optimización: la experimentación, la medición y la comparación estadística de resultados.
En primer lugar, llevaremos a cabo el desarrollo de una herramienta llamada Launcher. Esta herramienta consta de varias piezas de software que en conjunto permiten la ejecución de experimentos a pequeña o gran escala en un conjunto o clúster de ordenadores.
La herramienta Launcher permitirá a un usuario iniciar uno o varios experimentos a la vez, sin importar el tamaño y se encargará de la separación en partes pequeñas de cada experimento y su distribución en un conjunto de ordenadores o máquinas virtuales a lo que llamamos nodos. En cada nodo se realizará la ejecución de una parte de un experimento y sus resultados serán devueltos al finalizar. Con estas herramientas el usuario solo tendrá que realizar el trabajo de configuración inicial del experimento y esperar a que todos los resultados hayan sido devueltos.
El Launcher se compone de varios servicios que se encargan de diferentes tareas, como la administración de los experimentos, la comunicación entre ordenadores, la ejecución de cada parte de un experimento y el almacenamiento de todos los experimentos en curso y su estado. Cada servicio se podrá correr en diferentes máquinas virtuales lo que le da gran escalabilidad al sistema. Los nodos de ejecución pueden crearse y utilizarse de acuerdo con la capacidad de cómputo del clúster donde se ejecuta.
Este sistema provee de una interfaz de usuario amigable en un entorno web y es multiplataforma.
Un algoritmo, en su proceso de ejecución puede crear varias soluciones, para saber cuál de esas soluciones es mejor, es necesario asignarle a cada una un valor que sea representativo de su bondad. Este valor, que es por general un valor cuantitativo y numérico, es llamado objetivo de optimización o simplemente objetivo.
Cada solución obtenida por un algoritmo tendrá también un valor objetivo que las representa y que se puede utilizar para compararlas.
En el ejemplo del VRP ese valor puede ser la cantidad total de km recorridos por el vehículo, el tiempo total del recorrido o la cantidad de paradas que puede visitar en un día de trabajo. En los primeros dos casos una solución será mejor cuanto más pequeño sea el valor objetivo, mientras que en el tercero la mejor solución será la que obtenga un valor mayor de objetivo. En el primer caso se trata de un objetivo de minimización, y en el segundo se denomina objetivo de maximización.
El valor objetivo es una forma de medir una solución particular, generada en un momento por un algoritmo, para un conjunto de datos. Los datos que representan un problema de optimización con un estado particular se llaman instancia de problema.
Para poder llegar a una conclusión acerca de la capacidad de un algoritmo para resolver un problema de optimización en particular (como el caso del VRP) es necesario probar ese algoritmo contra diferentes situaciones (instancias) que representen al mismo problema de optimización. Por ejemplo, en el caso del VRP, se podría probar con diferentes cantidades de vehículos, diferentes capacidades de vehículos y distinta cantidad de paquetes para entregar, variando también la posición de cada parada.
Al comparar varios algoritmos, podremos decir que el mejor es el que obtiene las mejores soluciones al resolver la mayoría de las instancias de problema planteadas. Estas instancias se plantean de manera tal que representen situaciones muy diferentes del mismo problema de optimización. En particular, también interesan instancias que representen situaciones extremas, por ejemplo, cuando hay un solo vehículo y pocos paquetes que distribuir o cuando hay un solo vehículo y muchos paquetes que repartir. También situaciones donde las paradas están muy cerca y otras donde las paradas están muy alejadas entre sí.
Además de lo anterior, existe el caso particular de las metaheurísticas que, al tener un componente aleatorio, suelen obtener diferentes resultados al resolver la misma instancia. Por esta razón, lo normal en el caso de las metaheurísticas es que realicen varias ejecuciones contra cada conjunto de datos y se realice una media de los valores objetivos obtenidos.
Para determinar que un algoritmo funciona mejor que otro a nivel global se utilizan ciertos indicadores que miden, en vez del valor objetivos propiamente dicho, la distancia entre los valores obtenidos por un algoritmo y el mejor valor conocido para cada instancia. De esta manera, de forma global y aunque los valores de los objetivos varíen mucho entre diferentes conjuntos de datos de entrada el resultado será comparable.
Dentro del proyecto DIICEA y para ayudar en la comparación y prueba de algoritmos de optimización se desarrollará también una herramienta de software que facilite el cálculo de indicadores respecto de los resultados de algoritmos en experimentos. Este tipo de herramientas es sobre todo útil para experimentos grandes, donde se suelen obtener decenas de miles de resultados y es necesario calcular estos indicadores para cada uno de ellos.
Esta aplicación web incluirá la capacidad de calcular uno o varios indicadores dado un conjunto de resultados y tendrá la capacidad de ampliar los indicadores que se pueden calcular por si en un futuro es necesario ampliar su funcionalidad. Inicialmente incluirá los dos indicadores más utilizados en investigación: RPD (Relative Percent Deviation) y RDI (Relative Deviation Index). Ambos indicadores muestran la desviación de un resultado particular respecto al mejor valor conocido o a una estimación del posible mejor valor.
Con esta herramienta pretendemos acelerar el proceso de creación y prueba de algoritmos, como así también el proceso de prueba de algoritmos existentes para la resolución de nuevos problemas de optimización.
El cálculo estadístico sobre los resultados
El cálculo de indicadores permite obtener un valor comparable para todas las instancias probadas contra uno o varios algoritmos de optimización. Pero a la hora de realizar un análisis de los resultados de uno o varios algoritmos es necesario contar con herramientas que nos permitan convertir estas observaciones puntuales en estadísticos relevantes.
Una herramienta común utilizada en estadística es el análisis de varianza o ANOVA. Este tipo de estudio estadístico se utiliza para comparar las varianzas entre las medias de las mediciones. En el caso de algoritmos de optimización, se mide la varianza entre las medias de los indicadores obtenidos.
Al realizar un estudio ANOVA se puede determinar si un algoritmo es consistentemente mejor que otro algoritmo en un estudio completo (conjunto de instancias de prueba). Los indicadores nos dan un valor para cada instancia y algoritmo, mientras que el ANOVA nos da un valor global para cada algoritmo en comparación.
Como parte del proyecto DIICEA desarrollaremos una herramienta web que provea la capacidad para realizar el ANOVA a partir de un conjunto de indicadores calculado con los resultados de un experimento. Esta herramienta completa el proceso de creación, prueba y comparación de algoritmos.
El proyecto DIICEA está pensado para proveer estas herramientas indispensables en el proceso de diseño y desarrollo de algoritmos de optimización. Estas herramientas o piezas de software están claramente orientadas a la investigación y desarrollo de nuevos algoritmos. Pero también son indispensables para la prueba, diseño y desarrollo de algoritmos aplicados a un problema de la vida real.