Thesis
Optimización de funciones estocásticas con algoritmos genéticos
Fecha
2008-11-04Registro en:
Ramos Quintana, Guillermo. (2006). Optimización de funciones estocásticas con algoritmos genéticos. (Maestría en Ciencias de la Computación). Instituto Politécnico Nacional, Centro de Investigación en Computación, México.
Autor
Ramos Quintana, Guillermo
Institución
Resumen
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.