Integrantes
Francisco David Garcia Bernal-1482065
Luis Ivan Gomez Garcia-1481249
Francisco Mendez Juarez-1488241
Francisco Javier Martinez-1455954
Miguel Angel de la Fuente Hererra-1513642
Introducción
ejemplo del problema de la mochila
El problema de la mochila fue inventado por richard karp a mitades de los años 70`s, inspirado en el modelo de la evoluciona biológica , fue creado para la utilización del principio de selección natural para resolver problemas de optimizacion "complicados".
El algoritmo de la mochila es mejor conocido abreviado como KP o por sus iniciales en ingles Knapsack problem,
este problema es de optimizacion combinatoria y trata de llenar la mochila con lo mas indispensable pero eso tiene su costo , aparte la mochila solamente tiene un peso limite que no puede ser excedido por los objetos que se echaran a la mochila, cada objeto tiene un peso y un valor , El peso no puede exceder a lo que permite la mochila y tenemos que escoger el que sea mas optimo ya que los objetos tienen un cierto precio (valor) y el de menos valor sin exceder el peso seria la combinación mas optima.
El problema de la mochila lo venimos aplicando durante casi toda la vida, cuando tratamos de interactuar con grupos pequeños, y suele ser importante para poder obtener una optima respuesta sobre un problema que se nos presenten en la vida cotidiana.
Este problema no es difícil ,solo en algunos casos cuando en este problema se presentan muchos datos o es demasiado grande, esto podría tomar tiempo en solucionarlo.
Algoritmo Genético (resumido)
Un algoritmo genético es una serie de pasos organizados que se usan para llegar a un problema en especifico.Son llamados así porque se inspiran en la evolución biológica y su base genético-molecular. Estos algoritmos hacen evolucionar una población de individuos sometiéndola a acciones aleatorias semejantes a las que actúan en la evolución biológica.en función del cual se decide cuáles son los individuos más adaptados, que sobreviven, y cuáles los menos aptos, que son descartados.
que incluyen también las estrategias evolutivas, la programación evolutiva y la programación genética.
Marco Teórico
Recombinación o Cruzamiento. Es el principal operador
genético, representa la reproducción sexual, opera sobre dos cromosomas a la
vez para generar dos descendientes donde se combinan las características de
ambos cromosomas padres.
El problema de la mochila es un problema NP-Completo y
consiste a grandes rasgos en querer llenar una “mochila” con objetos de forma
que se maximice el beneficio pero sin sobrepasar el límite de peso que soporta
la “mochila”.
Se consideran n tipos
de objetos, cada objeto i tiene su
valor que se determina por vi y un
peso wi. Y el peso máximo que se
puede llevar es C.
Como por ejemplo:
Echar la mayor cantidad de proteínas en una mochila de
110 litros, sin importar el precio, sabor, ni calorías.
Como datos seria:
Proteínas de cada uno de los n productos (Pi)
Volumen de cada uno de los n productos (Vi)
Producto
|
1
|
2
|
3
|
Proteínas
|
1000
|
660
|
120
|
Volumen
|
30
|
22
|
10
|
Algoritmo
genético
El algoritmo genético es una técnica
de búsqueda basada en la teoría de la evolución de Darwin.
Es un algoritmo matemático altamente paralelo
que transforma un conjunto de objetos matemáticos individuales con respecto al
tiempo usando operaciones modeladas de acuerdo al principio Darwiniano de
reproducción y supervivencia del más apto, y tras haberse presentado de forma
natural una serie de operaciones genéticas de entre las que destaca la
recombinación sexual. Cada uno de estos objetos matemáticos suele ser una
cadena de caracteres (letras o números) de longitud fija que se ajusta al
modelo de las cadenas de cromosomas, y se les asocia con una cierta función
matemática que refleja su aptitud.
Un investigador de la Universidad de Michigan llamado
John Holland era consciente de la importancia de la selección natural, y a
fines de los 60s desarrolló una técnica que permitió incorporarla a un
programa. Su objetivo era lograr que las computadoras aprendieran por sí
mismas.
Pseudocodigo de un AG
Lo que dice básicamente
este Pseudocodigo es:
Inicialización: Se genera aleatoria-mente la
población inicial, que está constituida por un conjunto de cromosomas los
cuales representan las posibles soluciones del problema. En caso de no hacerlo
aleatoriamente, es importante garantizar que dentro de la población inicial, se
tenga la diversidad estructural de estas soluciones para tener una
representación de la mayor parte de la población posible o al menos evitar
la convergencia prematura.
Evaluación: A cada uno de los cromosomas de
esta población se aplicará la función de aptitud para saber cómo de
"buena" es la solución que se está codificando.
Condición de término El AG se deberá detener
cuando se alcance la solución óptima, pero ésta generalmente se desconoce, por
lo que se deben utilizar otros criterios de detención. Normalmente se usan dos
criterios: correr el AG un número máximo de iteraciones (generaciones) o
detenerlo cuando no haya cambios en la población. Mientras no se cumpla la
condición de término se hace lo siguiente:
Selección. Después de saber la aptitud de cada cromosoma
se procede a elegir los cromosomas que serán cruzados en la siguiente
generación. Los cromosomas con mejor aptitud tienen mayor probabilidad de ser
seleccionados.
Recombinación o Cruzamiento. Es el principal operador
genético, representa la reproducción sexual, opera sobre dos cromosomas a la
vez para generar dos descendientes donde se combinan las características de
ambos cromosomas padres.
Mutación. Modifica al azar parte del cromosoma de los
individuos, y permite alcanzar zonas del espacio de búsqueda que no estaban
cubiertas por los individuos de la población actual.
Reemplazo. Una vez aplicados los operadores genéticos,
se seleccionan los mejores individuos para conformar la población de
la generación siguiente.
Operadores Genéticos
Para el paso de una generación a la siguiente
se aplican una serie de operadores genéticos. Los más empleados son los
operadores de selección, cruce, copia y mutación.
Selección.
Los algoritmos de selección serán los encargados de escoger qué
individuos van a disponer de oportunidades de reproducirse y cuáles no.
Cruce. Una vez seleccionados los
individuos, éstos son recombinados para producir la descendencia que se
insertará en la siguiente generación. Tal y como se ha indicado anteriormente
el cruce es una estrategia de reproducción sexual.
Copia. La copia es la otra
estrategia reproductiva para la obtención de una nueva generación a partir de
la anterior. A diferencia del cruce, se trata de una estrategia de reproducción
asexual. Consiste simplemente en la copia de un individuo en la nueva
generación.
Mutación. La mutación de un
individuo provoca que alguno de sus genes, generalmente uno sólo, varíe su
valor de forma aleatoria. La
probabilidad de mutación es muy baja, generalmente menor al 1%. Esto se debe
sobre todo a que los individuos suelen tener un ajuste menor después de
mutados.
Experimentos y resultados
Tabla de valores de los parámetros AG
DESCARGAR :)
Gráficas de resultados
Instancia 1
CÓDIGO
PANTALLAS
Las gráficas las sacamos de excel
CÓDIGO
PANTALLAS
Las gráficas las sacamos de excel
Generación 1 (00111)
Generación 2 (01110) OPTIMA
Generación 3 (10110)
Generación 4 (11011)
Generación 5 (11101)
Instancia 2
CÓDIGO
PANTALLAS
Las gráficas las sacamos de excel
Generación 2 (0001110001)
Generación 3 (0001111000)
Generación 4 (0001101010)
Generación 5 (0001110010) OPTIMA
CÓDIGO
PANTALLAS
Las gráficas las sacamos de excel
Generación 1 (0001110000)
Generación 2 (0001110001)
Generación 3 (0001111000)
Generación 4 (0001101010)
Generación 5 (0001110010) OPTIMA
Conclusiones
Someten accione aleatorias semejantes a las que actúan en las evoluciones.
Cuando resolvemos un problema como el que se nos presento de la fuerza bruta ,
es algo mas complicado,
tardado y poco eficiente . y en los algoritmos genéticos, pueden también ser algo lento dependiendo de las iteraciones o generaciones que se presenten en el problema o de la complejidad , pero también son muchos mas rápidos que los de fuerza bruta y seria mas recomendable usar un algoritmo genético
Cuando queremos resolver problemas de fuerza bruta con iteraciones de 10 , 20 o 30 , seria algo muy tardado y algo extenso e incluso fastidioso, seria mas fácil poder usar el problema de algoritmos genéticos.
Los AG nos sirven para usarlos en una serie de procesos organizados que se deben se seguir , para optimizar o solucionar un problema en especifico.
Someten accione aleatorias semejantes a las que actúan en las evoluciones.
En pocas palabras esto seria un método de búsqueda para sacar una probabilidad bajo a una condición .y los cromosomas evolucionan a través de las iteraciones.
algunas ventajas de AG, que no ocupamos un conocimiento especifico para llevar acabo estos problemas.
Cuando usamos problemas de maximizan , estos resultados suelen estar menos afectados .
una de las ventajas de un AG es que operan de forma simultanea son varias soluciones, es comúnmente que los utilizan en problemas para optimizar una función y es sumamente fácil ejecutarlos
las limitaciones o desventajas que tienen es que aveces puede que no encuentra la solución mas optima del problema.
Referencias
- http://sabia.tic.udc.es/mgestal/cv/aaggtutorial/tutorialalgoritmosgeneticos.pdf
- http://es.wikibooks.org/wiki/Programaci%C3%B3n_din%C3%A1mica/Problema_de_la_mochila_con_programaci%C3%B3n_din%C3%A1mica
- http://eddyalfaro.galeon.com/geneticos.html
- http://www.it.uc3m.es/jvillena/irc/practicas/06-07/05.pdf
- Vijay V. Vazirani. Approximation Algorithms. Springer-Verlag GmbH,Berlin, Germany, 2001.
