Algoritmos Genéticos Aplicados a la Gestión de Inventarios de Artículos No Perecederos
- Objetivos y
alcances - Organización del
trabajo - ¿A quienes está
dirigida esta Tesis? - Gestión de
Inventarios - Algoritmos
Genéticos - Diseño
de la Solución - Especificación
de Requerimiento del Software - Laboratorio de
Prueba - Conclusión
Final - Anexo
- Referencias
La gestión de inventarios, como
problema de toma de decisiones, pretende suministrar el nivel de
existencias que permita minimizar los costes implicados en la
misma. La resolución tradicional se basa en hipótesis de partida restrictivas que
determinan su falta de aplicabilidad en la
práctica.
Constituyen una parte esencial en el buen comportamiento
económico de las empresas. Con
ella, se pretende satisfacer las necesidades de los clientes
incurriendo en los mínimos costes posibles.
Las decisiones más habituales que se adoptan con
relación a los inventarios son: que artículos
mantener en stock; si es más conveniente fabricarlos o
comprarlos; en que momento efectuar la compra; tamaño del
lote a comprar; nivel de servicio a
brindar a los clientes; nivel de existencias a mantener;
inventarios de seguridad a
mantener; sistema de
control a
utilizar.
Uno de los problemas que
encuentra la forma tradicional de gestionar los inventarios, es
que en un contexto de costos variables, el
mismo solo es resuelto aplicando las formulas para todas las
posibilidades, no pudiendo indicar cual es la mejor de todas las
opciones.
Los algoritmos
genéticos son una técnica del área de
Inteligencia
Artificial que constituye una abstracción del concepto
biológico de evolución natural y tiene numerosas
aplicaciones en problemas de optimización.
Su funcionamiento está basado en los mecanismos
de selección
natural, combinando la supervivencia del más apto con un
intercambio de información entre miembros de
una
población de posibles soluciones.
Los algoritmos genéticos son métodos
sistemáticos para la resolución de problemas de
búsqueda y optimización que aplican a estos los
mismos métodos de la evolución
biológica: selección basada en la población, reproducción y mutación.
Se estima que el uso de algoritmos genéticos
puede contribuir a acortar significativamente los tiempos de
resolución de un problema, ya que se caracterizan por su
capacidad de explorar el espacio de búsqueda de soluciones
amplia y eficientemente.
La programación mediante esta técnica
supone un nuevo enfoque que permite abarcar todas aquellas
áreas de aplicación donde no sepamos como resolver
un problema
En este contexto, el objetivo de
este trabajo es
analizar como pueden aplicarse los algoritmos genéticos,
que han demostrado ser útiles para ayudar a resolver
problemas de optimización, a solucionar el problema de
encontrar la mejor forma de gestionar los inventarios de
artículos no perecederos, entendiendo por ‘no
perecederos’ a aquellos productos que
pueden almacenarse para una venta a
futuro.
Se pretende demostrar que los algoritmos
genéticos son aplicables a la gestión de
inventarios y es posible diseñar un sistema que permita,
mediante la utilización de dicha técnica, la
minimización de costos en función a
cantidades y capacidades de almacenamiento
variables.
Para esto se contempla el estudio de los métodos
de análisis de stocks para identificar el
proceso y
definir las variables involucradas en la determinación de
costos, análisis a fondo de la técnica de
algoritmos genéticos y su modo de implementación
para evaluar su uso y de que manera sacarle un mayor provecho.
Una vez establecida la base teórica, se procederá a
diseñar y desarrollar un sistema que calcule los costos
mínimos de administración de stocks utilizando
algoritmos genéticos con el fin de realizar pruebas que
ayuden a confirmar o refutar la hipótesis
enunciada.
Queda fuera del alcance de este trabajo el
análisis correspondiente a la gestión de los
inventarios de stock para toda fase de producción.
El Capítulo 1 servirá de introducción a la gestión de stocks,
en donde podremos aprender acerca de modelos,
variables y costos para determinar de qué manera encarar
una solución al problema planteado. En el Capítulo
2 se analizará en profundidad el funcionamiento de los
algoritmos genéticos y las herramientas
con las que cuentan para realizar optimización y
búsqueda de soluciones. A partir de esta base
teórica, en el Capítulo 3 se plantea un posible
enfoque para el diseño
de una herramienta que nos permita demostrar la hipótesis
de este trabajo. En el Capítulo 4 se podrá
encontrar un diseño de dicho sistema (el cual fue
implementado y su código
fuente puede leerse en el Anexo A)". Este sistema fue el
utilizado para las pruebas descriptas en el Capítulo 5, en
donde pueden verse los resultados obtenidos y su análisis
correspondiente. Finalmente, en el Capítulo 6
podrán encontrarse las conclusiones finales, basadas en
las pruebas del Capítulo 5 y la base
teórica.
A quienes está dirigida esta Tesis
?
Esta investigación está dirigida a
profesionales informáticos, licenciados e ingenieros, y a
profesionales de administración comercial, con apoyo de
personal
informático.
La gestión de los inventarios, la podemos
definir, como la
administración de existencias de todo producto o
artículo que es utilizado dentro de una organización. Es un conjunto de políticas
y controles que gestionan los niveles de inventarios y determina
cuanto, cuando y de que manera se debe reponer. Es una de las
funciones de
mayor importancia en la administración de sistemas
empresariales o comerciales, fundamentalmente debido a que ellas
representan una considerable inversión de capital de
trabajo.
De alguna manera, la eficiente gestión de
inventarios de artículos no perecederos es una herramienta
capaz de mejorar la calidad de la
manipulación de costos y cantidades.
Se considera que un artículo es no perecedero
cuando no pose fecha de vencimiento, es decir que no caduca con
el transcurso del tiempo.
Sus aplicaciones más importantes son:
- Maximizar el servicio a los clientes.
Se pretende conseguir que los productos estén
disponibles cuando son demandados, sirviendo de medida de la
efectividad de la gestión de inventarios.
- Minimizar la inversión en
inventarios.
La tenencia de inventarios supone la
inmovilización de capitales que no pueden ser utilizados
para otras actividades de la empresa. En
un análisis de las posibles ventajas que puede conllevar
la tenencia de inventarios hay que tener en cuenta los costes
en los que se puede incurrir por el mantenimiento de existencias.
Citando una definición formal podríamos
decir que los inventarios son materiales y
suministros que una empresa o
institución posee, ya sea para vender o para abastecer al
proceso productivo. [Cuatrecasas – 2003]
Todas las empresas o instituciones
precisan de inventarios, constituyendo una parte
importante
del activo total de las mismas.
Podemos decir que el nivel de los stocks presentes es
una medida directa de la incompetencia del sistema y su dirección. Efectivamente, las existencias
suelen actuar como escudo protector ante las malas
gestiones.
Esto será expuesto en la incapacidad para
planificar los suministros, incapacidad para producir o
incapacidad para prever la demanda real y
sus variaciones.
En consecuencia el objetivo de una empresa, en
cuanto a su política de
inventarios, será lograr el balance justo entre los
beneficios derivados de mantenerlos y los costos que ellos
originan.
La demanda a la que estarán afectados los
artículos no perecederos es la llamada Demanda Continua o
Independiente.Es la que proviene directamente del mercado
y que por lo tanto no puede ser controlada ni determinada
por la empresa, sino solo prevista.- Tipo de Demanda para
Artículos no Perecederos. - Modelo de Stock para
Artículos no Perecederos.
El modelo de
stock más utilizado para el manejo de artículos no
perecederos es el de "Stock de Fluctuación con
protección", el cual tiene características bien
definidas e influye en gran parte a la forma en la que se
gestionan los inventarios en lo que se refiere a tiempos,
cantidades y diferentes costos. A continuación, se
describen las características del modelo.
Modelo de Stock de
Fluctuación con Protección.
La inseguridad o
desconocimiento del ritmo de entradas o salidas de
artículos en el almacén
son los motivos que dan lugar a este tipo de modelo, que nos
conduce a mantener un cierto nivel de "stock de seguridad"
por encima del que sería necesario para prevenir las
posibles rupturas.
El tratamiento económico de la
optimización de este stock se basa en enfrentar el coste
de mantenimiento con el coste de ruptura derivado de necesitar un
material para poder atender
a un pedido y no poder hacerlo por no disponer de él en
ese momento (coste de la posible perdida de un cliente,
beneficio que se deja de ganar, etc.). Dado que consideraremos la
demanda como una variable aleatoria regida por las
correspondientes leyes estadísticas (normal, poisson, etc.) este
modelo es no determinista.
Se debe tener en cuenta
- Variación de la demanda por desajustes en la
previsión de ventas. - Retrasos en los suministros por parte de los proveedores
y subcontratistas. - Fallos en la calidad del citado suministro, de forma
que puedan ser devueltos. - Problemas emanados de los proveedores: continuidad,
precios,
negociaciones. - Problemas de planificación y programación de
los lotes. - Fallos en las entregas
- Problemas derivados del personal (rendimiento,
formación, etc.)
En el Stock de Fluctuación encontramos dos formas
de enfocar la gestión de los mismos.
- Método de punto de pedido o del inventario
permanente
Consiste en lanzar la orden de pedido de una cantidad
siempre constante cada vez que el nivel de stock llegue a un
nivel determinado (punto de pedido). Requiere un control
constante de las existencias para saber el nivel exacto en cada
momento. Normalmente se aplica a artículos de
importancia estratégica para la empresa o
artículos de alta rotación.
- Método del inventario
cíclico.
Consiste en revisar el nivel de los stock
periódicamente y pedir cada vez la cantidad necesaria
para llegar a un nivel de stock determinado. Al contrario que
el anterior se aplica a artículos de poca
importancia.
Otros modelos aplicables a diferentes tipos de productos
son el modelo de Stock de partida y de anticipación que no
serán tratados en este
trabajo.
Los siguientes costes y variables son los
considerados tradicionalmente para la toma de
decisiones relacionadas con la Gestión de
Inventarios:Es el precio pagado por la adquisición
de un artículo comprado y se compone del coste
del material y cualquier otro coste directo que haya
sido necesario para conseguir que dicho material se
encuentre en la empresa. Puede incluir costes de
transporte, aduanas, seguros, etc., en cuyo caso recibe el
nombre de coste de adquisición. Si se tratara de
un producto fabricado en la empresa, los componentes
del coste de los productos serían las materias
primas, la mano de obra directa y los gastos generales de fabricación.
A este respecto, generalmente se suelen producir
descuentos en el importe de este concepto de coste ante
volúmenes grandes de
artículos.- Coste de Compra de los
Artículos - Costes de Posesión o de
Mantenimiento en Almacén
- Costes y Variables de los Inventarios a
Optimizar
Estos costes se refieren a los gastos en los que incurre
la empresa para mantener los artículos en sus almacenes y son
proporcionales al volumen de
inventarios. Así, a medida que los inventarios aumentan,
también lo hacen los costes de este tipo.
Pueden dividirse en tres categorías:
- Costes de Capital.
Debido a la existencia de inventarios el dinero
que lo constituye no está disponible para otros usos y
por lo tanto representa un coste de oportunidad.
- Coste de Almacenamiento.
El mantenimiento de inventarios requiere espacio,
trabajadores y equipos .
- Costes de Riesgo.
Los riesgos
inherentes al mantenimiento de artículos almacenados por
obsolescencia, deterioro, pérdidas o depreciación.
Los costes de lanzamiento de los pedidos están
relacionados con la empresa y con el suministrador. El coste de
emitir un pedido no depende únicamente de la cantidad
solicitada, sino que hay ciertos costes que son independientes de
dicha cantidad. De ahí que, el coste anual de lanzamiento
de los pedidos dependa del número de órdenes
emitidas al año, estando compuesto de la siguiente
manera:
- Costes de Puesta a Punto y
Parada.
Cada vez que una orden llega al almacén se
incurren en costes de preparación de los trabajadores y
equipos encargados de su recepción. Adicionalmente,
cuando se termina esta tarea, se incurren en unos costes de
finalización de la misma. Ambos son independientes del
volumen del pedido pero aumentan a medida que se incrementa el
número de los mismos.
- Costes de Capacidad
Perdida.
Cada vez que un pedido llega a la empresa se pierde
tiempo en la recepción del mismo que se podría
emplear en el proceso productivo.
- Costes Administrativos del
Pedido.
En el momento de realizar un pedido, se incurren en
unos costes necesarios para solicitarlo. Éstos incluyen
petición remitida al proveedor, seguimiento,
recepción, autorización del pago y
contabilización de la operación.
Si la demanda excede de lo previsto se
producirá una ruptura en el stock, es decir,
no habrá suficientes artículos para
satisfacer la demanda de los clientes o del proceso
productivo.Los costes que esta situación acarrea
pueden ser elevados en ciertas ocasiones, e
incluirán: costes de ventas no realizadas, de
devolución del pedido, de pérdidas de
clientes, etc. Las rupturas pueden evitarse manteniendo
niveles extra de inventarios para proteger a la empresa
contra situaciones en las que la demanda real sea mayor que
la previsión de la misma. Sin embargo, esta
práctica supone mayores costes de posesión de
los artículos almacenados.- Costes de Ruptura
Cuando los volúmenes de capacidad
varían por motivo de las necesidades se incurre en
costes de alquiler, entrenamiento, horas extra, paradas, etc.,
fuera de lo previsto. Este tipo de costes se puede evitar
obteniendo productos en épocas de demanda baja para
ser vendidos en períodos de aumento de la misma lo
que, por otro lado, producirá un incremento en los
costes de posesión. - Costes Asociados con la
CapacidadLos stocks mínimos tienden a evitar las
continuas rupturas de stocks. Son puntos de
protección; cuando las existencias llegan a ese
punto se deberá efectuar el
reaprovisionamiento. - Los Stocks
Mínimos. - La Proyección
de Ventas
La proyección de las ventas surgirá en
función del análisis de las ventas
históricas. De esto se desprende, que el solicitar la
reposición de las cantidades vendidas, se hace en
función a una cantidad conocida, que tiene que ver con el
promedio de ventas para un periodo determinado.
Existen diversos modelos matemáticos utilizados
para la gestión de inventarios. El presente trabajo
tomará como base el modelo conocido como Stock de
Protección por ser uno de los más usados en la
actualidad. Este modelo considera que existe una cantidad de
productos que se mantienen en existencia, a fin de absorber
variaciones de demanda o de plazo de entregas y situaciones
imprevistas.
Además maneja un parámetro que es el nivel
de protección, el cual se fija políticamente de
acuerdo a la empresa en donde se gestionen.
Parámetros:
D : Demanda del producto, referida a un periodo de
tiempo
b : Costo unitario de
adquisición.
c : Costo unitario de almacenamiento.
k : Costo de Una Orden
LT : "Lead Time" (plazo de entrega).
T : Parámetros de dimensionamiento que sirven
para referenciar todos los parámetros temporales a la
misma unidad de tiempo. Se toma siempre igual a 1 y su unidad es
"pedidos"
Variables
q : Tamaño del lote. Es una variable de
decisión.
t : Intervalo entre dos reaprovisionamientos
sucesivos.
CTE : Costo total esperado.
n : número de pedidos (órdenes) a emitir
en ese periodo de tiempo.
SR : Stock de reorden o punto de pedido
Calculo del Tamaño del lote
óptimo
El tamaño de lote óptimo, también
llamado cantidad económica a solicitar esta dado por la
formula.
q* = √(2.k.D/T.c)
Esta expresión se la conoce con el nombre de
fórmula de Wilson.
Cálculo del Costo Total
Esperado
CTE =
b.D+1/2.q*.c.T+k.D/q*+c.Sp.T
* Multiplicando esta expresión por el
número de ciclos n por períodos
Calculo del Stock de Reposición
SR = LT.d.Sp
Los algoritmos genéticos fueron
desarrollados por John Holland, junto a su equipo
de investigación, en la universidad de Michigan en la
década de 1970 [Holland, 1975] y conforman
una técnica informática dentro del área
de la Inteligencia Artificial para la
resolución de problemas.Éstos combinan las nociones de
supervivencia del más apto con un intercambio
estructurado y aleatorio de características entre
individuos de una población de posibles
soluciones, conformando un algoritmo de búsqueda que puede
aplicarse para resolver problemas de optimización
en diversos campos [Goldberg, 1989]. Imitando la
mecánica de la evolución
biológica en la naturaleza, los algoritmos
genéticos operan sobre una población
compuesta de posibles soluciones al problema.Cada elemento de la población se denomina
"cromosoma". Un cromosoma es el representante, dentro del
algoritmo genético, de una posible solución
al problema. La forma en que los cromosomas codifican a la solución
se denomina "Representación" (ver figura
2.1).
Fig. 2.1 – Cada cromosoma
codifica una posible solución al
problemaEl algoritmo genético va creando nuevas
"generaciones" de esta población, cuyos individuos
son cada vez mejores soluciones al problema. La
creación de una nueva generación de
individuos se produce aplicando a la generación
anterior operadores genéticos, adaptados de la
genética natural. La figura 2.2
representa el esquema de funcionamiento del algoritmo
genético. El proceso comienza seleccionando un
número de cromosomas para que conformen la
población inicial.A continuación se evalúa la
función de adaptación para estos
individuos. La función de adaptación da una
medida de la aptitud del cromosoma para sobrevivir en su
entorno. Debe estar definida de tal forma que los
cromosomas que representen mejores soluciones tengan
valores más altos de
adaptación. Los individuos más aptos se
seleccionan en parejas para reproducirse. La
reproducción genera nuevos cromosomas que combinan
características de ambos padres. Estos nuevos
cromosomas reemplazan a los individuos con menores
valores de adaptación.A continuación, algunos cromosomas son
seleccionados al azar para ser mutados. La
mutación consiste en aplicar un cambio
aleatorio en su estructura. Luego, los nuevos cromosomas
deben incorporarse a la población; estos
cromosomas deben reemplazar a cromosomas ya
existentes.El ciclo de selección,
reproducción y mutación se repite hasta que
se cumple el criterio de terminación del
algoritmo, momento en el cual el cromosoma mejor adaptado
se devuelve como solución (ver figura
2.2).
Fig. 2.2 – Esquema de
Funcionamiento del Algoritmo Genético.El esquema de representación es el
que define de qué forma se corresponden los
cromosomas con las soluciones al problema. Para
diseñar el esquema de representación,
se buscan los parámetros que identifican a las
soluciones, y luego se codifican estos
parámetros dentro del cromosoma.
La figura 2.3 muestra un posible esquema de
representación para un problema que tiene como
soluciones a los polígonos regulares. Los
parámetros que identifican a cada
solución son 2 (cantidad de lados y longitud
del lado), y estos se codifican en el cromosoma en
forma binaria.El cromosoma se compone de una cadena de 10
bits. A cada mínimo elemento que conforma el
cromosoma, en algoritmos genéticos, se lo
denomina Alelo. En esta representación
sería el bit.En los que los primeros 3 son la cantidad de
lados, y los siguientes 7 bits representan la
longitud de los lados en milímetros. El
esquema de representación debería ser
tal que exista al menos una posible codificación para cada una de
las soluciones posibles. Las soluciones que no
estén dentro del espacio de cromosomas no
serán exploradas por el algoritmo
genético.En el ejemplo de la figura 2.3 el algoritmo
genético no explorará soluciones que se
compongan por polígonos de más de 7
lados ni longitudes mayores a 127 milímetros,
ya que con 3 y 7 bits pueden codificarse solamente
números del 0 al 7, y del 0 al 127,
respectivamente. Por el mismo motivo (porque la
búsqueda se hace sobre el espacio de
cromosomas), es deseable que no haya redundancia en
la representación; que cada solución
sea representada por solamente un cromosoma. Si
existen k cromosomas por cada solución, el
espacio de búsqueda sobre el que opera el
algoritmo genético es k veces
más grande que el espacio de soluciones,
haciendo más lento el proceso de
evolución.La representación ejemplificada en la
figura 2.3 no tiene redundancia, cada polígono
es representado sólo por un cromosoma. Otro
problema que puede presentarse es que haya cromosomas
que no representan ninguna
solución.En el ejemplo de la figura 2.3, un cromosoma
que tenga todos 0 en los primeros 3 ó en los
últimos 7 bits no representan un
polígono válido. En caso de que la
representación lo permita, los operadores del
algoritmo genético deben adaptarse para tratar
con este tipo de cromosomas.La codificación ejemplificada en la
figura 2.3 se denomina "binaria", ya que cada
posición del cromosoma contiene un bit. Esta
es la representación clásica propuesta
por los primeros autores y que todavía es
utilizada ampliamente [Goldberg,1989; Cole, 1998;
Falkenauer, 1999]. Sin embargo, hay problemas
para los cuales esta representación no es la
más conveniente. El funcionamiento de los
algoritmos genéticos está basado en lo
que se denomina la "hipótesis de los
bloques constructores" [Goldberg,
1989].Esta hipótesis requiere que los
cromosomas se compongan por bloques significativos
que codifiquen las características de la
solución lo más independientemente
posible.El ejemplo de la figura 2.4 es un claro
ejemplo de una representación que no cumple
con esta premisa. Sería más apropiado
un esquema en el cual el cromosoma se componga por 2
números enteros, uno de los cuales codifique
el número de lados y el otro la longitud. La
figura 2.4 muestra esta
representación.
- Representación
La población inicial es la principal
fuente (luego se verá que el operador de
mutación también trabaja sobre este
punto) de material genético para el algoritmo.
La población inicial debe contener cromosomas
que estén bien dispersos por el espacio de
soluciones.La manera más simple de cumplir con
este objetivo es elegir cromosomas al azar. El uso de
una heurística, es decir, de una
técnica de indagación y descubrimiento,
puede ayudar a generar una población inicial
compuesta de soluciones de mediana calidad, ahorrando
tiempo al proceso de evolución, siempre y
cuando se garantice una dispersión suficiente
para la búsqueda. - Generación
de la Población InicialLa función de adaptación
cuantifica la aptitud de cada cromosoma como
solución al problema, y determina su probabilidad de ser seleccionado para
la fase de reproducción y poder pasar parte de
su material genético a la siguiente
generación.La función de adaptación
provee la presión que hace evolucionar la
población hacia cromosomas más aptos,
por lo que una buena definición de esta
función es fundamental para un correcto
funcionamiento del algoritmo. La función debe
asignar el valor más alto al cromosoma que
representa la solución óptima al
problema. Soluciones cercanas a la óptima
deben obtener valores altos, y la función debe
ir decreciendo a medida que los cromosomas
representan soluciones cada vez más alejadas
de la óptima.Como el proceso de evolución tiende a
retener el material genético de los cromosomas
con valores altos de aptitud, una elección
apropiada de la función de adaptación
resultará en mayor probabilidad de retener
características de soluciones cercanas a la
óptima. Otro punto a tener en cuenta en el
diseño de la función de
adaptación es la escala [Goldberg,
1989].Cuando la aptitud de los elementos de la
población es variada (por ejemplo, al inicio
del proceso de evolución), es común que
la población contenga unos pocos cromosomas
cercanos al óptimo, rodeados de cromosomas que
representan soluciones mediocres. Los cromosomas
más aptos obtendrán valores
exageradamente superiores al promedio para la
función de adaptación, y el algoritmo
genético elegirá solamente a estos
cromosomas para la reproducción.Esto puede ocasionar lo que se denomina
"convergencia prematura": el algoritmo
genético encontrará una solución
sin haber explorado suficientemente el espacio de
búsqueda.Sin embargo, a medida que la aptitud
promedio va subiendo, el problema será
diferente. La diferencia irá decreciendo, y
los cromosomas más aptos obtendrán
valores de adaptación similares a los de los
demás cromosomas, reduciendo la probabilidad
de que el algoritmo genético seleccione a los
mejores individuos para la reproducción. Los
dos problemas pueden corregirse aplicando una
función de escala a la función de
adaptación.La función de escala lineal calcula
la nueva función de adaptación
f’ a partir de la función de
adaptación f usando la
transformación lineal f’ =
a.f + b. Las constantes "a" y "b" se eligen de
forma tal que el promedio de las dos funciones sea el
mismo, y que el máximo para la función
f’ asegure la diferencia de
probabilidades deseada entre los elementos más
aptos y el promedio. - Función
de Adaptación - Selección
- Introducción
a los Algoritmos Genéticos
- Capitulo II – Algoritmos
Genéticos
La selección de los individuos que van a
reproducirse se realiza mediante un operador de selección.
El operador de selección hace la elección
basándose en los valores de
adaptación de los individuos. Existen distintos operadores
de selección que pueden utilizarse [Miller
et.al., 1995], de los cuales, a continuación,
se describen los más comunes.
- Selección Basada en el
Ranking
En el operador de selección basado en el
ranking, los cromosomas se ordenan de acuerdo a sus valores
para la función de adaptación. Luego, se
seleccionan para la reproducción a los primeros m
(la cantidad que sea necesaria) cromosomas. Como las
probabilidades de ser elegido de cada individuo
dependen solamente de su posición relativa respecto a
los demás y no del valor absoluto de aptitud, este
operador no requiere que se apliquen las técnicas
de escala de la función de adaptación.
- Selección por Ruleta
El operador de selección por ruleta es uno de los
más simples [Goldberg, 1989].
Los cromosomas se colocan en segmentos continuos sobre
una línea, de forma tal que el segmento para cada
individuo sea de tamaño proporcional a su valor de
aptitud, y que la suma de las longitudes de los segmentos sea
igual a 1.
Se genera un número al azar entre 0 y 1, y el
individuo cuyo segmento comprende el número generado es
seleccionado para la reproducción; el procedimiento
se repite hasta que se obtiene el número deseado de
individuos. Esta técnica es análoga a una rueda
de ruleta en la que a cada cromosoma le es asignada una parte
de tamaño proporcional a su valor de aptitud. La figura
2.5 ejemplifica el funcionamiento de este operador.
El tamaño del segmento asignado a cada
cromosoma (y por lo tanto su probabilidad de ser seleccionado
para reproducirse) es proporcional a su aptitud. El operador de
selección por ruleta puede requerir la aplicación
de una función de escala sobre la función de
adaptación, ya que los segmentos son dimensionados en
función del valor absoluto de aptitud de cada
individuo.
- Selección por Torneo
Los dos operadores de selección descriptos
anteriormente no permiten regular la presión selectiva.
El operador de selección basado en el ranking siempre
seleccionará a los mejores individuos de la
población. La selección por ruleta, si no se
aplica ninguna función de escala, aplica una
presión selectiva muy alta cuando las aptitudes de los
individuos son variadas, y muy baja cuando las aptitudes son
similares [Goldberg, 1989].
El operador de selección por torneo permite controlar
en forma efectiva la presión selectiva del algoritmo
genético, siendo a la vez de fácil
implementación. En este esquema, se toman T
individuos al azar de la población (donde T es el
tamaño del torneo, habitualmente 2 o 3 individuos), de
los cuales se selecciona para la fase de reproducción,
con probabilidad p (generalmente entre 0,7 y 0,8), aquel
que tenga el mayor valor de la función de
adaptación.
Los parámetros T y p permiten regular
la presión selectiva. Cuanto más grandes son los
valores de T y p, mayor es la presión
selectiva. En el caso extremo de que p sea igual a 1 y
T igual al tamaño de la población, el
algoritmo genético solamente seleccionará al
mejor individuo de la población.
En el otro extremo, si T es igual a 1, se logra la
presión selectiva más baja (los cromosomas se
seleccionan al azar). Manteniendo estos parámetros
constantes, se logra una presión selectiva que es
independiente de los valores absolutos de aptitud de la
población, y sin requerir la aplicación de
funciones de escala sobre la función de
adaptación.
La fase de reproducción se implementa por medio de un
operador de reproducción. El operador de
reproducción es el encargado de transferir el material
genético de una generación a la siguiente. Es este
operador el que confiere a la búsqueda de soluciones
mediante algoritmos genéticos su característica
más distintiva [Falkenauer, 1999].
A diferencia de otros métodos de optimización,
los algoritmos genéticos no solamente exploran el
vecindario de las buenas soluciones, sino que recombinan sus
partes para formar nuevas soluciones. Se ha hecho notar que el
descubrimiento de nuevas teorías
combinando nociones ya conocidas es un mecanismo que el hombre ha
utilizado constantemente a lo largo de la evolución de
la ciencia
[Goldberg, 1989].
El objetivo de los operadores de reproducción es,
partiendo de dos cromosomas padres, generar uno o más
cromosomas hijos que hereden características de ambos
padres, como se muestra en la figura 2.6.
Se dice que en el hijo se "recombinan" las
características de los padres. Si las
características se traspasan en bloques significativos, se
espera que un hijo que recombina características de buenas
soluciones sea una buena solución, tal vez mejor que
cualquiera de sus padres. Los operadores de reproducción
más típicos generan dos hijos a partir de dos
padres.
A continuación se describen los más
utilizados.
- Cruza Monopunto
Este operador consiste en separar a los padres en dos partes
para formar dos hijos intercambiando las partes de cada padre.
Si los cromosomas se componen de N bloques, se elige un
número al azar c, tal que 1 <= c < N, y
luego se asigna al primer hijo los primeros c bloques
del primer padre y los últimos N – c bloques del
segundo padre. Se procede en forma inversa para formar al
segundo hijo.
- Cruza Multipunto
Es evidente que en el operador de cruza monopunto, el primer
y último bloque de uno de los padres no pueden pasar
juntos al hijo en ningún caso. El operador de cruza
multipunto avanza un paso más, quitando esta
restricción. En la cruza multipunto, se eligen M
puntos de corte al azar, y las secciones de cada padre se pasan
a los hijos en forma alternada.
La figura 2.8 ejemplifica este procedimiento, para el caso en
que M es igual a 2 y 5.
- Cruza Uniforme
Si bien la cruza multipunto es más flexible que
la monopunto, tiene algunos inconvenientes. En primer lugar,
para valores impares de M impide que el primer y
último bloque de los padres pasen juntos a los hijos, y
para valores pares obliga a que sea así.
En segundo lugar, los bloques consecutivos tienen
más posibilidades de pasar juntos que los que se
encuentran más distanciados. Esto no es deseable (a
menos que la codificación elegida haga que los bloques
consecutivos representen características
relacionadas).
El operador de cruza uniforme permite el intercambio
de los bloques en una manera que es independiente del orden que
la codificación impuso a cada uno dentro del
cromosoma.
Para cada posición de los cromosomas hijos, se
elige al azar cuál de los dos bloques de los cromosomas
padres se copia en cada uno. Esta es una generalización
del esquema de cruza multipunto donde la cantidad de puntos de
corte M se elige al azar para cada
reproducción.
La mutación de cromosomas (junto con la
generación de la población inicial) es la
encargada de proveer al sistema de material
genético. La mutación se implementa mediante
un operador de mutación.El operador de cruza genera nuevas soluciones
intercambiando bloques de las soluciones existentes, pero
sin el operador de mutación, el algoritmo
genético no tendría forma de crear nuevos
bloques. Este operador es el que permite que la
exploración del espacio de búsqueda sea
amplia. El operador de mutación trabaja a nivel de
bloque dentro de los cromosomas, haciendo cambios
aleatorios de acuerdo a una probabilidad PM
(probabilidad de mutación). La naturaleza del cambio
depende de la composición de los bloques de los
cromosomas. Si cada bloque es un bit (en la
codificación binaria), el único cambio
posible es invertir su valor. Si los bloques son
números reales, la modificación podría
ser la suma o sustracción de un pequeño valor
aleatorio.- Mutación
- Inserción de
los Hijos en la Población
La reinserción de hijos consiste en incorporar
los nuevos cromosomas en la población. Los métodos
de reinserción son diferentes según la cantidad de
cromosomas generados sea menor, igual o mayor que la cantidad de
elementos existentes en la población.
- Se generan más cromosomas que elementos
en la población
Este esquema es similar al de reinserción pura.
Se eligen los mejores cromosomas entre los que se generaron, y
se eliminan los cromosomas sobrantes. Luego, se reemplaza la
población completa por la nueva
generación.
- Se generan menos cromosomas que elementos en la
población
Este esquema exige seleccionar entre los cromosomas de
la población aquellos que se eliminarán. A
continuación se describen los métodos más
utilizados para hacerlo.
- Inserción uniforme
Los cromosomas a ser reemplazados se eligen al azar
entre los miembros de la población. Se corre el riesgo
de eliminar buenas soluciones, ya que no se tiene en cuenta la
aptitud de los cromosomas.
- Inserción elitista
Se eligen los cromosomas menos aptos para ser
reemplazados. Este método
asegura que los mejores cromosomas pasarán siempre a la
siguiente generación, pero puede restringir la amplitud
de la búsqueda que realiza el algoritmo
genético.
- Inserción por torneo
invertido
Se utiliza en combinación con el método
de selección por torneo. Funciona exactamente igual que
el método de selección por torneo pero
seleccionando con probabilidad p al peor cromosoma del
torneo para ser reemplazado, y tiene las mismas propiedades que
éste, permitiendo regular la presión selectiva
sin el uso de funciones de escala.
El criterio de terminación del algoritmo
genético es el encargado de definir el momento en el cual
debe detenerse el ciclo de evolución y adoptar el
cromosoma más apto como la solución encontrada por
el algoritmo genético. A continuación se describen
los criterios más comúnmente utilizados.
- Criterio de Convergencia de
Identidad
Este criterio consiste en detener al algoritmo
genético cuando un determinado porcentaje de los
cromosomas de la población representa a la misma
solución. Los operadores del algoritmo genético
tienden a preservar y difundir el material genético de los
cromosomas más aptos, por lo que es de esperar que luego
de un gran número de generaciones, alguna solución
con gran valor de aptitud se imponga y domine la
población.
- Criterio de Convergencia de
Aptitud
Puede suceder que existan soluciones equivalentes o casi
equivalentes a un problema, que obtengan valores de aptitud
similares. En ese caso, es probable que no haya una
solución que se imponga en la población (y el
criterio de terminación por convergencia de identidad
nunca se cumpla).
Este criterio no espera a que la población se
componga mayoritariamente de una sola solución, sino que
finaliza la ejecución del algoritmo cuando los valores de
aptitud de un determinado porcentaje de las soluciones son
iguales, o difieren en un porcentaje. Por ejemplo, cuando el 90%
de las soluciones tenga valores de aptitud que no difieran en
más de un 1%.
- Criterio de Cantidad de
Generaciones
Los métodos anteriores apuntan a esperar a que la
evolución de la población llegue a su fin. Cuando
alguno de ellos se cumple, es probable que las soluciones no
sigan mejorando mucho más, no importa cuantas generaciones
más se ejecuten.
Sin embargo, los algoritmos genéticos pueden
necesitar un número de generaciones muy grande para llegar
a la convergencia, dependiendo de las tasas de
reproducción y mutación. Utilizando cualquiera de
los dos criterios anteriores no puede estimarse un número
máximo de generaciones, ya que esto dependerá no
solamente de los parámetros del algoritmo genético
sino también del azar.
Esto puede ser un problema, sobre todo si se quieren
comparar los tiempos de resolución de un problema mediante
algoritmos genéticos con otros métodos
[Estivill-Castro, 2000].
El criterio de terminación por cantidad de
generaciones consiste simplemente en finalizar la
ejecución una vez que ha transcurrido un número
determinado de generaciones. Este método permite
determinar con precisión los tiempos de ejecución
del algoritmo a costa de detener la evolución sin la
certeza de que las soluciones no seguirán
mejorando.
Página siguiente  |