Algoritmos Geneticos

Equipo

1527268 Victor Emanuel Ríos Martínez

1483821 Juan Carlos Guzmán Pinales

1511137 Eduardo Alberto Briones Hernández
1522790 Ricardo Alberto Morales Ramos

Introducción

Para este algoritmo utilizaremos el problema de la mochila, que se trata de un un ladrón que intenta robar cierta cantidad de objetos que se ven limitados por la capacidad de transporte de la mochila, el debe escoger que tipo de objetos pueden ser los mas valiosos y ademas de eso poder transportar la mayor cantidad de ellos.

El problema de la mochila es una de las cosas que vivimos día a día aun sin darnos cuenta e ahí su importancia. Este tipo de problemas se presentan en la vida real para mi forma de verlo por ejemplo cuando vas de paseo y necesitas llevarte cosas tienes un limite de objetos que puedes llevar o también al momento de comprar comida tienes cierta cantidad de dinero y cada platillo cuesta tanto porcentaje de el.

El dilema del problema de la mochila se ve reflejado mas que nada en que la mayoría de nosotros somos tan codiciosos o aborasados que nos vamos siempre por lo mas factible o el el así mero.

Marco teorico

EL problema de la mochila está en una categoría de NP completo ya que es difícil por que es relevante y cuenta con demasiadas instancias.
Una instancia de este problema consiste en darle diferentes valores a los a las variables involucradas ósea parámetros dentro del problema, por ejemplo:

Objeto O1 O2 O3 O4 O5 O6 O7

Ganancia 8 16 45 2 11 22 7
Peso 5 7 15 8 24 20 18

Capacidad total = 95
El algoritmo genético es una técnica que busca una solución de algún problema influenciado por la evolución humana. Estos algoritmos genéticos fueron inventados por John Henry Holland, este tipo se basó en la evolución biológica usando términos como genes, cromosomas y mutaciones.
Esta información se representa de la siguiente manera:
La población es el conjunto de cromosomas que hay dentro del problema estos cromosomas se representan por medio de una cadena binaria y cada elemento de la cadena se le llama gen.
¿Cuál es el proceso (general) que se sigue con un AG simple? Puedes incluir un diagrama de flujo o pseudocódigo para explicar este punto.
Se trabaja con una población de individuos donde cada uno representa una solución al problema.  Cada 1 tiene un valor o puntación, relacionada con la solución al problema. Entre más se adapte un individuo al problema más probabilidad tendrá a reproducirse y este cruce creara nuevos individuos que se adaptaran mejor al problema.
Si el algoritmo genético fue bien diseñado cada vez se harán mejores individuos con mejores características para encontrar la solución.
Entonces resumiendo el AG simple es:

> Se genera una población inicial
> Se evalúa cada individuo
> Se seleccionan 2 de los mejores individuos para una cruza.
> Se cruzan y mutan
> Se evalúa su función de los descendientes mutados
> Estos se agregan a una nueva generación

BEGIN AG
{
Iniciar población
EVALUAR adap
{
SELECCIONAR padres
CRUZA entre los padres
{
MUTACION de los hijos
}
EVALUAR hijos
If adap hijos < padres
{
“Está mal implementado el AG”
Else
{
AGREGAR hijos ngeneracion
END
END AG
*ngeneracion = nueva generación de hijos

¿Qué son los operadores genéticos y para qué sirven? Explica cada uno de ellos y la implementación específica que estás utilizando (ej. rueda de ruleta, punto de cruce,...).
Son métodos para crear nuevos mejores individuos que los anteriores, sirven para crear una mejor población.
Existen los algoritmos de selección, se eligen cuales individuos se van a reproducir y cuáles no.

  - Punto de cruce
Si se tienen dos individuos digamos:
1010 y
0101

Entonces para hacer un cruce y crear un nuevo individuo supuestamente más apto se toma las primeras dos partes del primer individuo osèase: 10 y en el segundo se toman sus últimas dos partes osèase: 01
Y ya con esto tenemos un nuevo individuo que sería chan chan chaan!:

1001

  -Mutación
   Los genes de un individuo variaran su valor a una forma aleatoria. Si se tiene un cruce con éxito el individuo muta con algo de probabilidad.
Si anteriormente se obtuvo al individuo:
1001 al mutar este seria
0110

- Selección por torneo
En esta selección se realizan comparaciones directas entre individuos como si pelearan entre sí. Existen dos versiones de hacer esto
- Deterministica: Aquí dentro de la población se seleccionan un número de individuos y se selecciona el más adaptable.
- Probabilística: Se genera un numero aleatorio y si es mayor  que un parámetro se escoge al individuo más alto y en caso contrario al menos alto.
¿Cuáles son los parámetros involucrados en un AG?
El tamaño de la población, probabilidad de cruce, probabilidad de mutacion.

Cálculos y resultados de experimentos

Calculo de optimo por fuerza bruta

Instancia 1:




















instancia 2:

Parámetro	Valor
Poblaciones	8	8	8	8
P. mutación	0.2	0.3	0.4	0.3

Código generador de instancias
Conclusiones

Resolver los problemas que se nos presentan cuando estos tiene un número muy alto de combinaciones por fuerza bruta  toma demasiado tiempo, en cambio el algoritmo genético simple es más rápido en su arrojamiento de resultado. El algoritmo genético tiene como base las mutaciones entre cromosomas y por cada iteración se va escogiendo el más óptimo y de esa forma al mismo tiempo se acerca al óptimo de toda la generación.

El algoritmo genético sirve para encontrar soluciones óptimas dentro de una población de n individuos. Una de las ventajas es que se puede encontrar una solución en un tiempo más corto que por fuerza bruta y una de las desventajas puede ser que se no siempre se llega a la más óptima y se tiene que dar mas iteraciones.