EL ARTE EN LA CONSTRUCCIÓN DE LOS ALGORITMOS GENETICOS CASO: “LA MALDICIÓN DE LA PROGRAMACIÓN DINÁMICA”

III CONGRESO COLOMBIANO Y I CONFERENCIA ANDINA INTERNACIONAL DE INVESTIGACIÓN DE OPERACIONES

EL ARTE EN LA CONSTRUCCIÓN DE LOS ALGORITMOS GENETICOS CASO: “LA  MALDICIÓN DE LA PROGRAMACIÓN DINÁMICA”

THE ART IN THE CONSTRUCTION OF THE GENETIC ALGORITHMS CASE: THE  CURSE OF THE DYNAMIC PROGRAMMING

AUTOR

ING. MIGUEL JIMÉNEZ CARRIÓN M.Sc.

Profesor Principal a DE, adscrito al Departamento Académico de Investigación de Operaciones  de la Facultad de Ingeniería Industrial de la UNP Piura – Perú

mjimenezc@gmail.com 

mjimenezc@unp.edu.pe 

Resumen

El diseño y construcción de un Algoritmo Genético está influenciado por la experiencia del  diseñador y por el tipo de problema que se quiere resolver. La asignación multidimensional de  recursos generan un efecto combinatorio en la programación dinámica y ésta metodología se  vuelve inoperante. Este problema es conocido como: “la maldición de la programación  dinámica”.

Este trabajo se refiere al software ARCAG en el cual se ha implementado un algoritmo genético  para dar respuesta a este tipo de problemas. Los resultados muestran que el 93.55% de las  veces se encuentra la solución óptima y el restante 6.45%, soluciones 5% por debajo de éste  valor.

Palabras Claves: Algoritmo genético, asignación de recursos, programación dinámica, efecto  combinatorio.

Abstract

The design and construction of a Genetic Algorithm are influenced by the experience of the  designer and the kind of problem that wants to be solved. The multidimensional assignment of  resources generates a combinatorial effect in the dynamic programming and this methodology  becomes inoperative. This problem is known like: " the curse of the dynamic programming ". This paper refers to the ARCAG software in which a genetic algorithm has been implemented to  give response to this problems. The results show that 93.55 % of the times is the ideal solution  and the remaining 6.45 %, are near the ideal solution.

[pic 1]

Asignación de Recursos Con Algoritmos Genéticos

INTRODUCCIÓN

Los problemas de Dimensionalidad en programación dinámica, originan el problema de  infactibilidad de cómputo, especialmente en los cálculos tabulares en donde el número de  entradas de las tablas será demasiado grande para la mayoría de computadoras disponibles.  Además el tiempo de computación puede ser excesivamente largo.

En el presente estudio se revisa los algoritmos genéticos llegándose a comprender cómo es el  mecanismo de operación de estos algoritmos, con el propósito de resolver el modelo  matemático del problema de dimensionalidad que enfrentan la asignación de recursos con  retornos tabulados cuando el número de variables de estado al inicio de cada etapa del proceso  de programación dinámica es mayor a uno.

En este estudio se ha diseñado e implementado un Algoritmo Genético en la construcción del  software ARCAG que resuelve el problema de asignación de recursos con retornos tabulados  cuando el vector de estados es multidimensional.  

Las facilidades del software permiten al usuario ingresar datos de problemas de este tipo,  encontrar la mejor solución, observar gráficamente el comportamiento de la convergencia hacia  la solución, modificar datos de un problema, guardar o leer desde un medio magnético los datos  e imprimir resultados, entre otras.  

Los requerimientos mínimos de Hardware para correr este software son: una PC Pentium, 64Mb  de memoria RAM, monitor a color con resolución de 600 x 800 y velocidad del microprocesador  200Mhz.

EL PROBLEMA DE DIMENSIONALIDAD EN LA PROGRAMACIÓN DINÁMICA

El problema de dimensionalidad en programación dinámica es un problema derivado del  método de programación dinámica y se presenta cuando el número de variables de estado al  inicio de cada etapa del proceso es mayor a uno. En este caso se plantea que el vector de  estados es multidimensional en cada etapa para los cuales se tiene retornos tabulados  derivados de las diferentes asignaciones de los recursos, y lo que se busca es la asignación de  recursos de tal forma que el retorno total de todas las etapas involucradas sea la máxima.  

Matemáticamente se puede representar el problema como:

Ejemplo de Aplicación

Se tienen 3 proyectos de inversión los cuales tienen diferentes alternativas; cada alternativa requiere varios recursos y en diferentes cantidades con el consiguiente retorno. Sobre el  particular considere que para determinado retorno (R) en cualquier alternativa, éste no depende  solamente de cuánto capital se invierte (C) sino también de cuántas horas hombre (HH), se  destinan al proyecto y de cuántas horas de maquinaria y equipo (HM). La restricción a este  problema es que se tienen cantidades limitadas de cada recurso como: 5 unidades de (C), 4  unidades de (HH) y 6 unidades de (HM). La tabla que condensa la información es como se  muestra:

 Fábrica 1 Fábrica 2 Fábrica 3

Alter. C HH HM R C HH HM R C HH HM R

 1 0 0 0 0 0 0 0 0 0 0 0 0   2 1 3 2 5 2 3 4 8 1 3 2 3  3 2 4 3 6 3 2 6 9 - - - -  4 - - - - 4 3 5 12 - - - -

En consecuencia el vector de estados multidimensional estará representado por: Si = (C, HH, HM) = (5, 4, 6)

¿Cuál es la combinación óptima de los recursos que maximizan el retorno total?.

MATEMÁTICAMENTE SE PUEDE REPRESENTAR EL PROBLEMA COMO: Versión 1

Maximizar Z = f1(x1, y1, z1) + f2(x2, y2, z2) + f3(x3, y3, z3)

s.a

x1 + x2 + x3 ≤ 5

y1 + y2 + y3 ≤ 4

z1 + z2 + z3 ≤ 6

con todas las variables enteras y no negativas

en donde: f1(x1, y1, z1), f2(x2, y2, z2) y f3(x3, y3, z3), son funciones no lineales conocidas de tres  variables y representan la utilidad o contribución de la fábrica o proyecto 1, 2 ó 3 por asignar x1,  x2 x3; y1, y2, y3; z1, z2, z3; y 5, 4 y 6 representa la disponibilidad del recurso disponible “Capital”,  “Horas Hombre” y “Horas Máquina”.

Otra forma de representar el problema matemáticamente y de una forma general es la que se  ilustra a continuación:

...