En el mundo real existen problemas donde uno o más objetivos deben ser optimizados, y los algoritmos meméticos son una de las técnicas más utilizadas para resolverlos. Dichos algoritmos combinan un algoritmo evolutivo con técnicas de búsqueda local. Desafortunadamente, un problema con los algoritmos meméticos, es que en ciertas ocasiones la búsqueda local de los mismos requiere que se proporcione información del gradiente del problema. Como una alternativa para lidiar con esta limitante presentamos en esta tesis tres diferentes técnicas de búsqueda local que no requieren que dicha información sea dada: la Búsqueda Dirigida Discreta (DDS), la Aproximación del Subespacio del Gradiente (GSA) y la Mutación Polinomial de Subespacios (SPM). El método llamado Búsqueda Dirigida Discreta (DDS), es un método que puede dirigir la búsqueda en cualquier dirección d 2 Rk dada en el espacio de los objetivos.
El método DDS surge como una extensión sin gradiente del método de Búsqueda Dirigida (DS), aunque, en lugar de construir una dirección utilizando la Jacobiana de la función, el metodo DDS usa la informacion del vecindario. Tal información ya se encuentra calculada en la población actual del algoritmo evolutivo. Utilizando al DDS como método de búsqueda local se propuso un nuevo algoritmo memético, con el cual, se realizaron diversas comparaciones con funciones de prueba del estado del arte. Los resultados obtenidos muestran que el algoritmo memético basado en el método DDS presenta mejores resultados cuando es comparado con el algoritmo evolutivo usado como base; a su vez, presenta resultados similares en comparación con el método DS. El segundo método presentado en este trabajo es la Aproximación del Subespacio del Gradiente (GSA). Dicho método posee dos diferentes versiones y cada una de ellas depende del número de objetivos del problema que se este resolviendo. La primera versión del GSA se desarrollo para resolver problemas con un solo objetivo que posean restricciones. En particular, utilizando dicha versión se implemento un algoritmo memético que utiliza a la Evolución Diferencial (DE, por sus siglas en inglés) y se realizaron experimentos utilizando este algoritmo. Los resultados arrojados por los experimentos muestran que el algoritmo DE/GSA es capaz de ahorrar un monto considerable de recursos (medidos en evaluaciones de las funciones objetivo) en contraparte a los algoritmos con los que se realizo la comparación. La segunda versión del GSA se desarrollo como una extension del mismo para trabajar en el contexto de problemas multi-objetivo. Dos híbridos se desarrollaron con esta versión: el MOEA/D/GSA y el IG-NSGA-II/GSA. De igual manera, se desarrollaron diversos experimentos, en los cuales, los valores de los indicadores obtenidos muestran una mejora considerable en comparacion con el algoritmo base usado para los algoritmos meméticos utilizados.
Finalmente, el último método desarrollado fue la Mutación Polinomial de Subespacios (SPM). Dicho método es capaz de manejar problemas multi-objetivo con restricciones de desigualdad. En particular, la idea principal del operador SPM es el moverse a lo largo de las restricciones activas del problema para generar nuevas soluciones a lo largo de las mismas. Los experimentos realizados con el operador SPM, muestran que una mejora signi cativa (medida utilizando indicadores multi-objetivo tales como el hipervolumen y 2) puede ser alcanzada cuando se realiza este tipo de movimiento.
Abstract
In the real world there exist problems where one or more objectives have to be optimized. Memetic algorithms are currently one of the most widely used techniques to solve such problems. Such kind of algorithms hybridize evolutionary algorithms with local search procedures. One drawback of such algorithms is that some of the local search procedures currently available require that explicit gradient information is given. As an alternative to tackle such a problem we present three local search techniques that do not require that explicit gradient information is given: the Discrete Directed Search, the Gradient Subspace Approximation and the Subspace Polynomial Mutation.
The Discrete Directed Search (DDS) is a method that steers the search in any given direction d 2 Rk provided in objective space. The DDS method is a gradientfree realization of the Directed Search (DS) method. Instead of computing a direction using the Jacobian, it utilizes the given information from neighboring solutions of the current population. A new memetic algorithm using the DDS method as a local search was proposed. Such a method was compared using several state-of-the-art test functions. The results of such an experiments demonstrated that the memetic algorithm based on the DDS local search have obtained competitive results in comparison with the standalone algorithm and similar results in comparison to the original DS algorithm. The second method presented in this work is the Gradient Subspace Approximation (GSA). Two di erent versions of the GSA are proposed in this work according to the number of objectives of the problem. The rst version of the GSA is a method to solve constrained single-objective problems. In particular, to nd a solution of a given optimization problem, a memetic algorithm using Di erential Evolution was proposed. The experiments of the DE/GSA showed that such an algorithm is capable of saving a considerable amount of resources (measured in function calls) than the algorithm with respect to which it is compared. A natural extension of the GSA is the increment in the number of objective functions. In particular, a second approach using the GSA method in the multi-objective context was proposed. Two di erent memetic algorithms are hybridized using the GSA: the MOEA/D/GSA and the IGNSGA- II/GSA. The indicator values on such an algorithm showed a considerable improvement in comparison with the standalone version of the algorithms.
Finally, the Subspace Polynomial Mutation (SPM) was proposed as a mechanism to handle inequality constrained multi-objective problems. Considering a problem where the Pareto Front is de ned by one or more constraints, the SPM operator is capable of computing a new candidate solution steering the search along the active inequality constraints. In particular, the experiments showed that an improvement was archieved in terms of multi-objective indicators (Hypervolume and 2) when such kind of movement is performed.
