Algoritmos Genéticos Aplicados a la Gestión de Inventarios de Artículos No Perecederos (página 4)

2. Resultados de la Prueba III

• Cantidad de generaciones utilizadas: 12
• Finalización del algoritmo por criterio de cantidad de generaciones
• Cantidad a Pedir Sugerida : 514
• Demora del proceso: 12 segundos

2. Prueba IV

• Se mantienen absolutamente todas las variables del escenario y marco de gestión planteado.
• Se incrementa el tamaño de la población planteado a 150.
• Se incrementa el tamaña de la cantidad de generaciones en 20
• Método de selección ranking
• Método reproducción monopunto

• Se supone una tasa de interés del %10

1. Resultados de la Prueba IV

• Cantidad de generaciones utilizadas: 13
• Finalización del algoritmo por criterio de identidad
• Cantidad a Pedir Sugerida : 401
• Demora del proceso: 15 segundos

1. Conclusiones acerca de las Pruebas efectuadas

En función a las pruebas efectuadas se ha podido llegar a conclusiones que surgen del comportamiento que denotó el algoritmo genético, aplicado al modelo matemático de gestión de inventarios con stock de protección.

Cabe aclarar que en todos los casos la salida que provee el algoritmo no es conocida, por lo tanto la conclusión se basa en la comparación de los resultados de las diferentes pruebas.

Lo que se descubre luego de efectuar distintos tipos de pruebas con diferentes valores de entrada, es que la "optima" solución, se alcanza cuando el algoritmo converge por criterio de identidad (ver sección 2.1.8).

Esto implica determinar un tamaño de la población inicial de al menos 100 cromosomas y un número de generaciones cuyo valor sea 15. Esto permitirá que el algoritmo encuentre la mejor solución en una población inicial, lo suficientemente "rica", en lo que se refiere a la diversidad de cromosomas.

Tal como se verifica en la prueba I, y la prueba II, los resultados obtenidos no son los mejores, debido a que el tamaño de la población inicial es pequeña, lo que genera que el algoritmo, "entienda", que la solución optima, es alcanzada en apenas unas 5 o 6 generaciones.

De aquí se desprende que el criterio de finalización por cantidad de generaciones con un tamaño pequeño de la población inicial, no son los mejores "aliados" a soluciones óptimas.

Por otro lado podemos verificar como en las pruebas III y IV encontramos soluciones de mejor calidad al incrementar el tamaño de la población. El algoritmo utiliza mayor cantidad de generaciones, evalúa muchas mas alternativas y llega a soluciones de mejor calidad, ya sea que finalice por criterio de identidad o por cantidad de generaciones. También cabe aclarar que queda demostrado que la aplicación de la mutación no es relevante cuando el tamaño y la cantidad de generaciones no son significativas, ya que la probabilidad de mutación es de 0.09.

En todas las pruebas se utilizó la generación de la población inicial en forma aleatoria, reproducción monopunto, mutación aleatoria y criterios de terminación del algoritmo, por criterio de identidad o cantidad de generaciones, según sea el caso.

2. Capitulo VI – Conclusión Final

Teniendo en cuenta lo planteado en la introducción de este trabajo en donde se pretendía verificar que "los algoritmos genéticos son aplicables a la gestión de inventarios y diseñar un sistema que permita, mediante la utilización de los algoritmos, la minimización de costos en función a cantidades y capacidades de almacenamiento variables", podemos afirmar que en base a las pruebas efectuadas en el capitulo 5 se demuestra que la tecnología de A.G. son una alternativa de optimización valiosa, al momento de proponer una solución optima en un contexto incierto y variable.

Esta incertidumbre y variablididad del contexto generan que el universo de soluciones posibles sea altamente elevado. Ha quedado demostrado que los algoritmos genéticos tienen una tendencia a la optimización y que los mismos permiten resolver una situación compleja.

Cabe aclarar que las pruebas no contemplaron todos los mecanismos de generación de población inicial, selección, reproducción y mutación, sino que solamente este trabajo acoto la demostración a lo desarrollado en el capitulo II.

Fuera del trabajo quedaron otros modelos para implementar reproducción, selección y mutación.

La solución demostrada tiene las siguientes ventajas:

• Se ha descubierto que los algoritmos genéticos son soluciones sencillas aplicables al problema de minimizar costos en función a cantidades y capacidades de almacenamiento variable dentro de un modelo de gestión de stock para artículos no perecederos.
• El tiempo de respuesta de la solución sugerida es altamente menor a la que tendría que usar si se realizara utilizando el trabajo humano.
• El software implementado puede ser utilizado en hardware de bajos recursos en lo que se refiere a velocidad de procesamiento y memoria.

• La teoría de algoritmos genéticos podría ser aplicable a otros modelos matemáticos de stock, con sólo cambiar las variables de entrada, y la función de adaptación. Estos modelos serían resueltos, con un mismo criterio de optimización.

Las desventajas encontradas son:

• Existe un grado de incertidumbre acerca de si la solución propuesta es verdaderamente la mejor de todas, más allá de que sea la óptima dentro del ámbito de búsqueda del algoritmo genético dado por sus condiciones de ejecución (tamaño de la población, operadores involucrados, cantidad de generaciones, etc.)

1. Futuras Líneas de Investigación

La aplicación del algoritmo seleccionado expresa una solución que calificaremos como optima, pero queda abierta a futuras investigaciones la utilización de otros métodos de selección, reproducción y mutación, para verificar si otras alternativas generan soluciones de mejor calidad que las obtenidas en este trabajo.

Otra posible línea es la verificación de la aplicabilidad de la solución propuesta a diferentes modelos matemáticos que estén asociados a la gestión de inventarios de otro tipo de productos, como por ejemplo los perecederos, o con una orientación a la producción.

Parece interesante además el estudio de la existencia de otras alternativas dentro de la Inteligencia Artificial, como redes neuronales o lógica difusa, para comparar criterios y calidad en el resultado de la optimización.

1. ANEXO A

Código Fuente de la Aplicación

DEFINE CLASS ag OF agenetico

PROCEDURE GeneracionPoblacion

LPARAMETERS pTOPE,pTamanoPoblacion

LOCAL I,nValor,nBinario

FOR I = 1 TO pTamanoPoblacion

nvalor = INT(1 + pTOPE* RAND())

cBinario = ALLTRIM(This.dectobin(nvalor))

cBinario = REPLICATE('0',11-LEN(cBinario))+ALLTRIM(cBinario)

INSERT INTO GENERACIONES(IDGEN,valor,binario) VALUES(1,nvalor ,cBinario)

ENDFOR

ENDPROC

PROCEDURE funcionadaptacion

LPARAMETERS pPromedio,pCTE

RETURN pPromedio / pCTE

ENDPROC

PROCEDURE seleccion

LPARAMETERS pIdgen

SELECT Generaciones

** Busco todos los Cromosomas cuya funcion d aptitud sea > 1.

** Solo esos son los que pasan.

SCAN ALL FOR pIdGen = Generaciones.IdGen

IF INT(Generaciones.FAdap) > 0

Replace Apto WITH .T.

ELSE

Replace Apto WITH .F.

ENDIF

ENDSCAN

ENDPROC

PROCEDURE postseleccion

LPARAMETERS pIdgen

LOCAL I,nIntervalo ,nReg

*- nIntervalo sirve para sacar un numero aleatorio entre 1 y nIntervalo

*- nReg sirve para recibir el numero aleatorio

*- I es la variable que controla los pares

I = 1

nPar= 0

* Entro a Armar las Parejas. Hasta que todos no estan con pareja no salgo

DO WHILE .T.

nPar = nPar +1

IF USED('aReproducirse')

USE IN aReproducirse

ENDIF

*- Armo una Temporal Con los Cromosomas que no tienen pareja -*

SELECT * FROM Generaciones G ;

WHERE G.apto = .T. AND G.idGen = pIdGen AND parcon=0 ;

INTO CURSOR aReproducirse

nIntervalo = RECCOUNT('aReproducirse')

SELECT aReproducirse

*- Verifico si me quedo uno solo sin pareja si es porque son impares o porque es el ultimo. -*

IF nIntervalo = 1

IF nPar = 1

UPDATE generaciones SET parcon = i

WHERE aReproducirse.id = generaciones.id

ELSE

UPDATE generaciones SET parcon = i

WHERE aReproducirse.id = generaciones.id

ENDIF

EXIT

ENDIF

* Busco de los registros que tengo un numero aleatorio

nReg = INT(1 + nIntervalo * RAND())

GO nReg

IF EMPTY(ParCon)

* Grabo en la Historica

UPDATE generaciones SET parcon = i

WHERE aReproducirse.id = generaciones.id

ENDIF

* Verifico si ya tengo una pareja armada. Si es asi, incremento el contador.

IF nPar = 2

i = i + 1

nPar = 0

ENDIF

ENDDO

ENDPROC

PROCEDURE reproduccion

LPARAMETERS pIdgen

SELECT Distinct parcon FROM Generaciones ;

WHERE pIdgen = Generaciones.idGen AND Apto = .T.;

INTO ARRAY aNroPares

FOR I=1 TO ALEN(aNroPares)

SELECT ALLTRIM(Binario) FROM generaciones WHERE aNroPares (i,1)

= parcon Into array aCromosomas

nMonopunto = INT(1 + 11* RAND())

IF ALEN(aCromosomas) > 1

cPapa = aCromosomas (1,1)

cMama = aCromosomas (2,1)

cHijoA = LEFT(cPapa,nmonopunto)+RIGHT(cmama,

11-nmonopunto)

cHijoB = LEFT(cMama,nmonopunto)+RIGHT(cPapa,

11-nmonopunto)

ENDIF

nValorA = This.bintodec(cHijoA)

nValorB = This.bintodec(cHijoB)

* Inserto los hijos de la proxima generacion

INSERT INTO Generaciones (idgen, valor, binario, cte, fadap, apto)

VALUES(pIdgen+1,nValorA ,cHijoA,0,0,.F.)

INSERT INTO Generaciones (idgen, valor, binario, cte, fadap, apto) VALUES(pIdgen+1,nValorB ,cHijoB,0,0,.F.)

ENDFOR

ENDPROC

PROCEDURE bintodec

LPARAMETERS cBinario

LOCAL lnFinal, lnDecimal, lnI

cBinario = ALLTRIM(cBinario)

lnFinal = LEN(cBinario)

lnDecimal = 0

FOR lnI = lnFinal TO 1 STEP -1

lnDecimal = lnDecimal + ;

VAL(SUBS(cBinario,lnI,1)) * 2^(lnFinal – lnI)

ENDFOR

RETURN lnDecimal

ENDPROC

PROCEDURE insertarhijos

LPARAMETERS pIdgen

IF USED('cProxGeneracion')

USE IN cProxGeneracion

ENDIF

SELECT * FROM Generaciones WHERE idgen = pIdgen AND apto = .T. INTO CURSOR cProxGeneracion

SELECT cProxGeneracion

GO TOP

SCAN ALL

nCantHijos = INT(cProxGeneracion.FAdap)

FOR I = 1 TO nCantHijos

INSERT INTO Generaciones (idgen, valor, binario, cte, fadap, apto) ;

VALUES (pIdgen+1,cProxGeneracion.valor,cProxGeneracion.Binario,0,0,.F.)

ENDFOR

ENDSCAN

ENDPROC

PROCEDURE mutacion

LPARAMETERS pIdgen

LOCAL cCromosoma, nAlelo

IF USED('cProxGeneracion')

USE IN cProxGeneracion

ENDIF

SELECT Generaciones

GO TOP

SCAN ALL FOR pIdgen = Generaciones.idGen

cCromosoma = ALLTRIM(Generaciones.Binario)

nCantAlelos = LEN(ALLTRIM(Generaciones.Binario))

FOR nAlelo = 1 TO nCantAlelos

nProbabilidad = (0 + 1.0* RAND())

IF nProbabilidad < 0.001

IF SUBSTR(cCromosoma,nAlelo,1) == '0' THEN

cCromosoma = LEFT(cCromosoma,(nAlelo-1))+'1'+SUBSTR(cCromosoma,nAlelo+1,nCantAlelos)

ELSE

cCromosoma = LEFT(cCromosoma,(nAlelo-1))+'0'+SUBSTR(cCromosoma,nAlelo+1,nCantAlelos)

ENDIF

Replace binario WITH cCromosoma

Replace Valor WITH This.bintodec(binario)

Replace Muto WITH .T.

ENDIF

ENDFOR

ENDSCAN

ENDPROC

ENDCLASS ag OF agenetico

DEFINE CLASS Calculo OF agenetico

PROCEDURE calculocte

LPARAMETERS pCostoUni, pDemanda,pCostoAlmacenamiento, pCostoPreparacion, pValor

RETURN ((pCostoUni*pDemanda)+(0.5*pCostoAlmacenamiento*pValor)+(pCostoPreparacion*pDemanda/pValor))

ENDPROC

PROCEDURE calculopreliminarcostos

LPARAMETERS pEmision,pRecepcion

LOCAL nCostoPreparacion

nCostoPreparacion = pEmision +pEmision

RETURN nCostoPreparacion

ENDPROC

PROCEDURE costoalmacenamiento

LPARAMETERS pValor,pSeguro,pCalefaccion,pInteres,pVolumen,pCosto,pAlquiler

RETURN (pSeguro+(pAlquiler*pVolumen)+(pCalefaccion*pVolumen)+(pCosto*pInteres))

ENDPROC

PROCEDURE calculocte

LPARAMETERS pCostoUni,pDemanda,pCostoAlmacenamiento,pCostoPreparacion, pValor

RETURN ((pCostoUni*pDemanda)+(0.5*pCostoAlmacenamiento*pValor)+(pCostoPreparacion*pDemanda/pValor))

ENDPROC

PROCEDURE calculopreliminarcostos

LPARAMETERS pEmision,pRecepcion

LOCAL nCostoPreparacion

nCostoPreparacion = pEmision +pRecepcion

RETURN nCostoPreparacion

ENDPROC

PROCEDURE costoalmacenamiento

LPARAMETERS pValor,pSeguro,pCalefaccion,pInteres,pVolumen,pCosto,pAlquiler

RETURN (pSeguro+(pAlquiler*pVolumen)+(pCalefaccion*pVolumen)+(pCosto*pInteres))

ENDPROC

ENDCLASS

Referencias

Bibliografía

Beasley, David; Bull, David R. & Martin, Ralph R (1993).An Overview of Genetic Algorithms : Part 1, Fundamentals, University Computing, pages 58-69.

Cuatrecasas L. (2003). Gestión de Competitiva de Stocks y Procesos de Producción

Ed. Gestión 2000, pagina 33

Estivill-Castro, V. (2000). "Hybrid Genetic Algorithms Are Better for Spatial Clustering".

Pacific Rim International Conference on Artificial Intelligence, pages 424-434.

Falkenauer, Emanuel. (1999). Evolutionary Algorithms: Applying Genetic Algorithms to Real-World Problems. Springer, New York

Goldberg, David E. (1989). Genetic Algorithms – in Search, Optimization

Learning. Addison-Wesley Publishing Company, Inc.

García – Servente – Pasquini (2003). Sistemas Inteligentes

Ed. Nueva librería, paginas 150-207

López E. – Mendaña C. – Rodríguez M.A (2000). Algoritmos Genéticos y la Gestión.

Paper publicado. León – España

Miranda M. (1998). Sistemas de Optimización de Stocks

Editorial EDUCA, paginas 36-46

Yolis E. (2003). Algoritmos genéticos Aplicado a la Categorización de Documentos

Trabajo de Investigación. Universidad de Buenos Aires, paginas 40-70

Imágenes

Fig. 2.1 a 2.8 Tomadas de Yolis E. Algoritmos genéticos Aplicado a la Categorización de Documentos. Trabajo de Investigación. Universidad de Buenos Aires, paginas 40-70

Fig. 3.1 Tomada de Miranda M. (1998). Sistemas de Optimización de Stocks

Editorial EDUCA, pagina 36.

A mi mamá Eleonora,

la cual, ante cada tropiezo, ante cada momento difícil,

siempre me dio gesto de amor y contención.

Ella siempre me apoyo para que estudie y me supere,

y me enseño que con esfuerzo todo se puede alcanzar.

Para vos mami.

A toda mi familia.

A vos papa que siempre me esperaste a altas horas de la noche,

simplemente para cenar juntos

y a mis hermanos Grisi, Ana, Lucas, Virgi y Luci.

A mis amigos. Ustedes fueron muy importantes.

En primer lugar quería expresar mi agradecimiento a mi amigo/hermano del alma; al Lic.Jorge Luis Insfran.

Jorge gracias por sacrificar tiempo con tu familia para sentarte conmigo y ayudarme a llevar esta investigación adelante. Sin tu ayuda no lo hubiera logrado.

Gracias a mis amigos que me ayudaron de alguna manera u otra en mis 6 años de Universidad

Leo, Gaby, Jorge, Cali, Sandra, Alejo, Maria Luisa, Miriam, Pablo Felipe y Checho.

A toda esa gente que en estos seis años me brindo su ayuda, con su tiempo, con sus ganas, con un apunte o con un gesto

Gracias a todos mis jefes y compañeros de trabajo que me cedieron horas y tiempo, para estudiar.

Al terciario Nuestra Señora de Lujan del Buen Viaje, mi primer escuela. Autoridades, alumnos y ex alumnos.

A mi director de tesis, que desinteresadamente, me acompaño hasta poder terminar con esta investigación.

Por último gracias, muchísimas gracias a Dios.

Autor

Ignacio Luis Castillo

Director de la Tesis

Ing. Christian Caminos

Universidad de Morón – Año 2004