Prodef-Algorithm: Interfaz para el modelado de meta-heurísticas

Abstract

Si bien en la actualidad existe una gran cantidad de investigación respecto a algoritmos de optimización bioinspirados, estos todavía no gozan de un uso extendido fuera del mundo académico. Su complejidad intrínseca y la dificultad para implementarlos y adaptarlos al problema en cuestión dificultan su uso. Prodef es una herramienta que trata de cambiar eso, permitiendo al usuario definir un problema con una interfaz gráfica basada en bloques desarrollada mediante la librería Blockly. Cada problema está compuesto por cuatro elementos: una serie de parámetros, las variables que conforman una solución, los objetivos y las restricciones que existen para que una solución sea factible. Una vez se ha definido el problema se puede obtener una solución. Para ello se transforma la definición basada en bloques en una basada en ProdefLang, un lenguaje de dominio específico que ayuda en la especificación de objetivos y restricciones. Finalmente, un componente llamado resolutor es capaz de recibir esta definición y computar una solución para el problema. Actualmente, existen dos resolutores cada uno basado en un framework distinto: JMetal y METCO. Sin embargo, en un principio Prodef no permitía al usuario influir en la ejecución más allá de decidir con qué resolutor resolver el problema. En este trabajo se han implementado los cambios necesarios para que Prodef permita al usuario definir sus propios algoritmos de forma sencilla. Para añadir esta característica ha sido necesario hacer cambios a lo largo de toda la estructura de Prodef. En primer lugar, se ha añadido la capacidad de definir y guardar algoritmos desde la interfaz gráfica. También ha sido necesario crear un nuevo resolutor. Este resolutor es fundamentalmente distinto a aquellos que ya existían, ya que permite especificar qué algoritmo se quiere usar para resolver el problema en cuestión. Asimismo, para implementar este nuevo resolutor, ha sido necesario desarrollar un nuevo compilador de ProdefLang (el lenguaje de dominio específico que usa Prodef) para Rust, ya que este es el lenguaje que se ha elegido para la implementación del nuevo resolutor. Para permitir el modelado de algoritmos, este nuevo resolutor hace uso de una abstracción basada en componentes que se ha diseñado durante este trabajo. Asimismo, se han creado varios componentes para ilustrar el funcionamiento del sistema. Una característica de gran relevancia de este diseño es que los algoritmos que se definen son independientes de cualquier problema. Esto permite aplicar el mismo algoritmo a distintos problemas, si bien es necesario elegir ciertos parámetros y componentes específicos que sí son dependientes del problema. Estos cambios permiten a Prodef erigirse como una herramienta única. Los usuarios que no necesiten definir sus propios algoritmos podrán usar algoritmos predefinidos e, incluso, comparar distintos algoritmos para encontrar los de mayor rendimiento para su problema. Sin embargo, aquellos usuarios que quieran tener un mayor control sobre la ejecución pueden definir los suyos propios. Además, esto también permite a usuarios que quieran aprender sobre metaheurísticas una plataforma para dar sus primeros pasos. Estas ventajas son de interés para cualquier futuro usuario de la herramienta. Por tanto, este Trabajo de Fin de Grado acerca Prodef a su objetivo de facilitar a empresas e individuos el modelado y la resolución de problemas de optimización combinatoria, sin tener que conocer los detalles de implementación de los mismos.

While there is currently a large amount of research on bio-inspired optimisation algorithms, they are not yet widely used outside academia. Their intrinsic complexity and the difficulty of implementing and adapting them to the problem at hand hinder their use. Prodef is a tool that tries to change that, allowing the user to define a problem with a block-based graphical interface implemented using the Blockly library. Each problem is composed of four elements: a set of parameters, the variables that make up a solution, the objectives and the constraints that exist for a solution to be feasible. Once the problem has been defined, a solution can be obtained. This is done by transforming the block-based definition into one based on ProdefLang, a domain-specific language that helps in the specification of objectives and constraints. Finally, a component called solver is able to receive this definition and compute a solution for the problem. Currently, two solvers exist, each based on a different framework: JMetal and METCO. However, initially Prodef did not allow the user to influence the execution beyond deciding which solver to use to solve the problem. In this project , the necessary changes have been implemented to allow Prodef users to define their own algorithms in a simple way. To add this feature it has been necessary to make changes throughout the entire structure of Prodef. Firstly, the ability to define and save algorithms from the graphical interface has been added. It has also been necessary to create a new solver. This solver is fundamentally different from those that already exist as it allows the users to specify which algorithms they want to use to solve the problem in question. Likewise, to implement this new solver, it has been necessary to develop a new ProdefLang compiler (the domain-specific language used by Prodef) for Rust, as this is the language that has been chosen for the implementation of the new solver. To enable the modeling of algorithms, this new solver makes use of a component-based abstraction that has been designed during this work. In addition, several components have been created to illustrate the operation of the system. A major feature of this design is that the defined algorithms are independent of the problem. This allows the same algorithm to be applied to different problems, although it is necessary to choose specific parameters and components that depend on the problem. These changes allow Prodef to establish itself as a unique tool. Users who do not need to define their own algorithms will be able to use predefined algorithms and even compare different algorithms to find the best performing ones for their problem. However, users who want to have more control over the performance can define their own. In addition, this also provides users who want to learn about metaheuristics with a platform to take their first steps. These advantages contribute to solving a number of use cases that could be of interest to a future user of the tool. Therefore, this Final Degree Project brings Prodef closer to its goal of making it easier for companies and individuals to model and solve combinatorial optimisation problems, without having to know the implementation details.