Tratamiento de soluciones no factibles para el problema SMINK-1

Abstract

El problema inverso al resuelto por la suma de Minkowski se refiere a la descomposición de polígonos en suma de Minkowski. Este problema, que denominamos SMINK-1, puede resolverse con un algoritmo de complejidad exponencial. Debido a la complejidad inherente del mismo, propusimos en trabajos anteriores su resolución utilizando un algoritmo genético con el cual se obtuvieron resultados satisfactorios. Sin embargo, se presentaron ciertos problemas respecto a un considerable aumento en el tamaño del espacio de soluciones no factibles. En este trabajo presentamos una propuesta para tratar las soluciones no factibles utilizando una forma alternativa de descodificación, de manera que la mayoría de las soluciones no factibles sean evaluadas como factibles. La nueva propuesta de descodificación incluida en el algoritmo genético es validada a través de un conjunto de instancias de distinto tipo del problema SMINK-1

A solution for the opposite problem to the classical Minkowski Sum problem embodies the polygon decomposition in Minkowski sum. This problem (called SMINK-1) can be solved by algorithms of exponential complexity. Due to this fact, we proposed in earlier works a genetic algorithm from which satisfactory results were obtained. However, the representation used and the applied decoding process increased greatly the size of the infeasible search space. In this work, we propose an alternative approach for decoding the solutions which evaluates almost all infeasible solutions as feasible ones. The new decoding approach implemented in the genetic algorithm is validated by using a set of different instances of SMINK-1