Dimencionalidad

IMPLEMENTACIÓN DE UN ALGORITMO GENÉTICO PARA RESOLVER EL PROBLEMA DE DIMENSIONALIDAD EN PROGRAMACIÓN DINÁMICA

Por: Ing. Miguel Jiménez Carrión. MsC

Profesor Asociado a DE, adscrito al

Departamento Académico de Investigación de Operaciones

de la Facultad de Ingeniería Industrial de la UNP

Piura – Perú

e-mail: jim_car_miguel@hotmail.com Teléfono:073 350155

mjimenezc@tallan.unp.edu.pe

Resumen

El problema de dimensionalidad en programación dinámica se deriva 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. Las combinaciones de las asignaciones de los recursos generan un efecto combinatorio y resulta que la metodología de la programación dinámica se vuelve inoperante.

En ARCAG, 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 resto 6.45%, soluciones cercanas al óptimo para los cuales los resultados son menos del 5% por debajo del valor óptimo.

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

Implementación del Algoritmo

Datos de Entrada

Relativos al problema

Número de Etapas o Fábricas.- Es un dato numérico de tipo entero y puede tener un rango de variación entre 1 y 1000.

Número de Alternativas en cada Etapa o Fábrica.- Es un dato numérico de tipo entero y puede variar de 1 a 1000. Esta entrada puede ser distinta para cada una de las fábricas.

Número de recursos.- Esta entrada es numérica de tipo entera y representa la cantidad máxima de recursos utilizados entre todas las etapas, lo que significa que pueden haber etapas que requieran menos número de recursos.

Cantidad disponible de cada tipo de recurso.- es un valor numérico de tipo continuo o discreto.

Inversiones permitidas.- de los recursos disponibles, en cada etapa o fábrica es un valor numérico de tipo continuo.

Retornos o utilidad.- en cada etapa o fábrica por cada alternativa por el uso de los recursos; es una cantidad numérica de tipo continuo.

Relativos al Algoritmo

Tamaño de la Población.- Es un número entero múltiplo de 2 y permite inicializar la población de posibles soluciones; puede variar entre 2 y 1000.

Número de Generaciones.- Número entero positivo que puede variar de 1 a 1000, permite encontrar la mejor solución dentro del intervalo.

Porcentaje de Mutación.- Operador Genético que es igual o menor al 10%

Porcentaje de Cruza.- Operador Genético que es igual o mayor a 80%.

Números de puntos de cruce.- Número entero positivo que puede variar desde uno hasta dos puntos de cruce los que pueden tomar los valores desde 1 hasta tamaño del cromosoma menos 1.

Datos de Salida

Los datos de salida están relacionados con el resultado de aplicar el algoritmo genético y está en términos de:

a) Cantidad del recurso i a invertir en la etapa o fábrica k.

b) La calidad o Fitness de la mejor solución

c) El retorno total máximo.

Resultados

Los resultados de 31 muestras cuando el algoritmo opera bajo las siguientes condiciones y conservando elitismo:

Mutación: 5%

Reproducción: 90%

Tamaño de la población: 100 individuos.

Número de Generaciones: 500.

Se implementa elitismo

Mostraron que el algoritmo genético implementado es Bueno trabajando con problemas de asignación de recursos con retornos tabulados cuando el tamaño del problema tiene hasta 6 fábricas, 5 recursos y 11 alternativas.

En este

...