Algoritmos Genéticos Aplicados a la Gestión de Inventarios de Artículos No Perecederos
Enviado por Ignacio Luis Castillo
- 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 Capacidad
Los 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 problema
El 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 Inicial
La 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 |