Optimización de funciones estocásticas con algoritmos genéticos

Abstract

RESUMEN: La minimización del costo de los inventarios estocásticos (IE) es un problema difícil de modelar matemáticamente debido a la naturaleza aleatoria de componentes como: la demanda y el tiempo de reabastecimiento, presentes en los sistemas de inventarios reales. La investigación de operaciones (IO) propone modelos para tratar el problema imponiendo, generalmente, restricciones difíciles de asumir. Por su lado, los algoritmos de optimización estocástica (AOE), ampliamente usadas en funciones complejas, si bien permiten relajar las restricciones sobre las variables, también pueden llevar la convergencia hacia mínimos falsos, debido a la aleatoriedad presente en la función de desempeño. Los AOE, en general, enfrentan el problema de la aleatoriedad de dos formas: i) tratando previamente los datos para reducir la incertidumbre o ii) modificando la estrategia de búsqueda del propio algoritmo. Debido al alto costo computacional de la primera opción, la mayoría se dirige hacia la segunda. En este trabajo se muestra un algoritmo genético (AG) para el problema de los IE, que toma el promedio de la función de evaluación como una forma de evitar los mínimos falsos, combinando al mismo tiempo una modificación del operador de mutación y del incremento progresivo del tamaño de la población. El AG implementado hace una selección elitista completa y se basa en una función de contracción que asegura la convergencia hacia un mínimo. La función de evaluación, asociada a las variables de decisión, se simula usado el método de Monte Carlo, que permite, además de relajar las restricciones impuestas por otros métodos, representar la interrelación explicita entre estas variables y las variables aleatorias.

ABSTRACT: The cost minimization of the stochastic inventories (SI) is a problem difficult to model mathematically due to the random nature of components as: demand and time supply, present in the systems of real inventories. The operations research (OR) proposes models to treat the problem imposing, generally, restrictions difficult to assume. By their side, the stochastic optimization algorithms (SOA), broadly used in complex functions, although they allow to relax the restrictions on the variables, they can also take the convergence toward false minima, due to the present randomness in the evaluation function. The SOA, in general, faces the problem of the randomness in two ways: i) treating the data previously to reduce the uncertainty or ii) modifying the strategy of search of the own algorithm. Due to the high cost computacional of the first option, most goes toward second option. In this work a genetic algorithm (GA) is shown for the problem of the IE that takes the average of the evaluation function like a form of avoiding the false minima, combining a modification of the mutation operator at the same time and of the progressive increment of the population’s size. The AG implement a complete elitist selection and it is based on a contraction function that assures the convergence toward a minimum. The evaluation function, associated to the variables of decision, is simulated used the method of Mount Carlo that allows, besides relaxing the restrictions imposed by other methods, to represent the explicit interrelation between these variables and the random variables.