Algoritmos Genéticos Aplicados a la Gestión de Inventarios de Artículos No Perecederos (página 4)
idgen | cte |
1 | 61147,20 |
2 | 58944,62 |
3 | 58026,36 |
4 | 57372,35 |
5 | 57186,37 |
6 | 57069,74 |
7 | 56963,00 |
8 | 56940,58 |
9 | 56914,57 |
10 | 56886,29 |
11 | 56864,45 |
12 | 56851,22 |
- 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
- 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
Rango Unidades | Costo directo por Ítem | Costos Adicional Alquiler |
0-400 | $ 40,00 | $ 15 m3 |
401-800 | $ 32,00 | $ 30 m3 |
801-1200 | $ 28,00 | $ 45 m3 |
1200 o 1600 | $ 26,00 | $ 60 m3 |
Parámetros | $ |
Costo de preparación de | 50 |
| 1000 |
| 3000 |
12.000 U /Año | |
Costo de Almacenamiento para un | |
Costo de alquiler | $15 m3/Mes |
Costo mensual de Calefacción | $0,5 m3 |
Stock de Seguridad | 5 días de demanda |
Costo mensual de seguros | 10 Unidad |
Lead Time | 2 días |
Disponibilidad por | 2 m3 |
- Se supone una tasa de
interés del %10
Variables AG | Valor |
Cantidad de Generaciones | 20 |
Tamaño de la Población | 150 |
Mutación | Si |
idgen | Cte |
1 | 64040,09 |
2 | 59848,39 |
3 | 58883,24 |
4 | 58160,68 |
5 | 57487,88 |
6 | 57401,18 |
7 | 57350,80 |
8 | 57201,62 |
9 | 56930,73 |
10 | 56889,25 |
11 | 56875,12 |
12 | 56861,86 |
13 | 56852,97 |
- Cantidad de generaciones utilizadas: 13
- Finalización del algoritmo por criterio de
identidad - Cantidad a Pedir Sugerida : 401
- Demora del proceso: 15 segundos
- 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.
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.)
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.
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
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
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
Página anterior | Volver al principio del trabajo | Página siguiente |