INTRODUCCIÓN
El problema de la mochila es un problema en el que se busca que las personas desarrollen más su lógica al deber buscar la forma de obtener la mayor ganancia con los objetos que debemos llevar sin pasar el límite de peso de nuestra mochila (o cualquier “contenedor” que tengamos).
El problema de la mochila es importante porque nos permite pensar en las diferentes formas de hacer lago en las cueles podemos obtener diferentes resultados tanto buenos como malos y al saberlos podemos desarrollar o planificar la mejor de ellas.
El problema de la mochila es importante porque nos permite pensar en las diferentes formas de hacer lago en las cueles podemos obtener diferentes resultados tanto buenos como malos y al saberlos podemos desarrollar o planificar la mejor de ellas.
El problema no es la mochila no es muy difícil de analizar, pero es muy laborioso de llevar a cabo pues entre más objetos se tenga, son más combinaciones las que deben analizarse. Este problema se puede ver en el área de la de la industria, pues cuando mueven objetos deben reconocer que las máquinas tienen un límite y reconocer cuales son los objetos más importantes.
Un algoritmo genético es un método que se usa para problemas de optimización y búsqueda que consiste en que nuestros resultados “mejoran” (o deberían de) en cada nueva iteración, esto con la finalidad de encontrar el más óptimo.
Esta práctica está desarrollada en la presente introducción, un marco teórico acerca de los algoritmos genéticos y dos experimento del problema del viajero resuelto por algoritmo genético.
MARCO TEÓRICO
El problema de la mochila es un problema curioso desde el punto de vista de las ciencias de la computación, pues se considera que el problema de decisión es considerado NP-Completo, pero el problema de optimización es NP-Difícil.
Una instancia del problema de la mochila consiste en tener una mochila (contenedor) al cual hay que llenar de varios objetos que tienen un valor y un peso, pero esta mochila tiene un límite de peso que no debe ser excedido.
(Una instancia -gráfica- del problema)
Así, una instancia de este problema sería tener cuatro objetos con sus respectivos valores de ganancia y peso, como A con una ganancia de 5 y un peso de 2, B con una ganancia de 3 y un peso de 4, C con una ganancia de 8 y un peso de 9, y D con una ganancia de 3 y un peso de 6, contando con una mochila que admite máximo 16 unidades de peso. El objetivo del problema es encontrar la combinación de objetos más óptima sin que rebase el límite de peso que puede soportar la mochila.
Un algoritmo genético es un algoritmo heurístico de búsqueda que se basa en las ideas de la evolución y la selección natural. Su principal pionero fue John Holland en los años 60. Como se basa en las ideas de evolución, sus principales funciones hacen referencia a esto: selección, cruza, evaluación del más óptimo.
Un algoritmo genético sigue la siguiente estructura:
Aunque la imagen anterior es muy básica y no lo demuestra, dos de las funciones más importantes del algoritmo genético son la selección de los mejores cromosomas y el cruce de dichos cromosomas. Estas funciones dentro del algoritmo genético se llaman operadores genéticos.
Operadores genéticos de selección
Estos algoritmos son los encargados de escoger qué individuos se van a reproducir y cuales no. Existen diferentes algoritmos de selección, por ejemplo:
- Selección por ruleta: consiste en que cada a individuo se le asigna una parte proporcional a una ruleta, de tal forma que la suma de todos los porcentajes represente a la ruleta. En teoría, los mejores individuos deben recibir la porción más grande de la ruleta.
- Selección por torneo: consiste en realizar la selección en base a comparaciones directas entre individuos. Existen dos variaciones de este algoritmo: determinística y probabilística.
- Selección por torneo determinística: se selecciona al azar un número p de individuos (por lo general p = 2), y de entre los individios seleccionados se escoge el más apto para pasarlo a la siguiente generación.
- Selección por torneo probabilística: es parecido al anterior, pero para elegir al ganador se genera un número aleatorio del intervalo, si es mayor que un parámetro p se escoge el individuo más apto y en caso contrario el menos apto.
Operadores genéticos de cruce
Una vez que se selecciona a los individuos, estos se recombinan para producir una descendencia que aparecerá en la siguiente generación.
- Cruce de 1 punto: es la más sencilla de esta técnica, consiste en dos individuos que se cortan sus cromosomas por un punto seleccionado, lo que genera dos segmentos diferenciados. Para crear a los hijos simplemente se combinan la información de ambos segmentos para los dos padres, lo que genera dos nuevos cromosomas.
- Cruce de 2 puntos: es parecido al anterior, pero en vz de cortar por un único punto se realizan dos cortes. Se recomiendo que dichos puntos se realicen en el segmento central de los padres (generando tres segmentos), lo que hace que los hijos tengan información de los dos padres.
- Cruce uniforme: es una técnica que consiste en utilizar una máscara de cruces con valores binarios, lo que permite a que los genes de los descendientes tengan las mismas probabilidades de pertenecer a uno u otro padre.
Operador genético de copia y mutación.
- Copia: consiste en copiar un individuo a la nueva generación.
- Mutación: consiste en que los genes de un individuo cambien su valor de manera aleatoria.Se utiliza para promover la variación de genes.
En base a lo anterior, en un algoritmo genético los parámetros más importantes que pueden influir en los resultados del algoritmo son los siguientes:
- la población inicial
- la elección de los operadores genéticos a utilizar
- así como el número de generaciones a realizar
EXPERIMENTOS Y RESULTADOS
Para probar un algoritmo genético se realizó dos instancias del problema de la mochila, las cuales se probarán, al menos, cuatro veces para probar si el algoritmo llega al óptimo.
Para la instancia 1 se realizó cuatro iteraciones del algoritmo con los siguientes parámetros.
Para probar un algoritmo genético se realizó dos instancias del problema de la mochila, las cuales se probarán, al menos, cuatro veces para probar si el algoritmo llega al óptimo.
Para la instancia 1 se realizó cuatro iteraciones del algoritmo con los siguientes parámetros.
Para cada iteración se encontró los mejores individuos por generación, así como el mejor individuo encontrado.
De acuerdo a los resultados obtenidos, en tres de las cuatro iteraciones se encontró el óptimo de la instancia 1, el cual es 75. Probablemente se deba a que es una instancia pequeña, pero se observa que el algoritmo encontró muy rápido el óptimo en poblaciones grandes, y que, para poblaciones pequeñas, tuvo más dificultades o definitivamente no lo encontró (aunque también pudo influir la probabilidad de mutación)
Para la instancia 2 también se realizó cuatro iteraciones, también cambiando los parámetros y generando las siguientes gráficas.
Se observa que ninguna iteración llegó al más óptimo, que es 291, pero se acercaron bastante aun a pesar de las distintas configuraciones. Dado a que las iteraciones 2 y 4 son las que llegan al óptimo, se puede deducir que tener una población relativamente grande ayuda a que se mejoren los individuos con el paso del tiempo.
No obstante, la probabilidad de mutación también influye muchísimo, porque a pesar de que en la iteración 4 tiene una población muy grande, también es notable que tiene una probabilidad muy pequeña, y en cambio, la iteración 2 está "un poco más balanceado" y sin embargo también encuentra una respuesta óptima aceptable (y en un tiempo mucho menor)
CONCLUSIONES
En base a lo observado en las gráficas, tener una probabilidad de mutación no muy alta ayuda a encontrar el óptimo, así como definir una población ni muy pequeña ni muy grande. Esto permite que el algoritmo genético genere soluciones factibles y que se acercan al óptimo en un rango aceptable, aunque sería interesante definir una instancia del problema de la mochila, muy, pero muy grande, para saber que tan eficiente es el algoritmo genético en estos casos.
Aun así, es obvio que implementar un algoritmo como éste es mucho mejor que realizar el cálculo a fuerza bruta, pues con una instancia de 11 de objetos el problema llegaría a ser de 2048 combinaciones; de 20, 1048576 combinaciones; de 30, 1073741824... Es decir, sería una locura definir todas las combinaciones para una posible instancia muy grande sólo por fuerza bruta, aunque para encontrar soluciones factibles "óptimas" un algoritmo genético puede ayudar bastante. El inconveniente a esto es que, en caso de sólo guiarnos al algoritmo genético, nunca sabremos cuál es el resultado óptimo, al menos que hagamos muchas iteraciones y se compare dichos resultados.
Otra de las desventajas que encontramos de los algoritmos genéticos es que tiene muchos parámetros que se pueden configurar, los cuales pueden afectar a que se encuentra el óptimo con más o menos tiempo en un rango aceptable. En ocasiones tener una probabilidad muy alta ayuda a que los cromosomas cambien, pero en ocasiones hacen que "se alejen" mucho del óptimo o de una región factible y que ya no regresen tan facilmente a dichos valores.
REFERENCIAS
No hay comentarios:
Publicar un comentario