ALGORITMOS GENÉTICOS

Ordinola Marcelo, Jean

Torres Requena, Erick

¿ALGORITMO GENÉTICO?

SE BASA EN LA GENETICA NATURAL DE LOS SERES VIVOS, EN LAS LEYES DE DARWIN: 1. LOS PADRES MAS ADAPTADOS. 2. EL # DE HIJOS TIENDE A SER MAYOR AL # DE PADRES.

EL PUNTO 1 TIENE QUE VER CON LA LEY DE DARWIN EN LA SELECCIÓN NATURAL ESTO PUEDE DARSE DE MANERA: DETERMINISTICA PROBABILISTICA

ALGORITMO GENÉTICO - DIVERSIDAD

LOS A.G. ESTAN BASADOS EN QUE LOS PADRES DEBEN SER ALTAMENTE DIVERSOS.

SI LA POBLACION ES ALTAMENTE DIVERSA, SE PUEDE ALCANZAR EL OPTIMO DEL SISTEMA.

LA DIVERSIDAD HACE POSIBLE LA SELECCIÓN DE LAS ESPECIES.

ALGORITMO GENÉTICO - DIVERSIDAD

AL TENER DIVERSIDAD EN LOS PADRES, SE GARANTIZA QUE LAS SIGUIENTES GENERACIONES DE LOS HIJOS SEAN MAS ADAPTADOS, A ESO SE LE LLAMA EVOLUCIÓN

ALGORITMO GENÉTICO

PARTES DE UN ALGORITMO GENETICO

GENOTIPO: GENES QUE SE HEREDAN DE LOS PADRES

FENOTIPO: CARACTERISTICAS QUE LOS DIFERENCIAS DE LOS DEMÁS

ALGORITMO GENÉTICO – GENOTIPO Y FENOTIPO

1 0 1 0 0 1GENOTIPO

FENOTIPO COSTO = 23

ALGORITMO GENÉTICO

1 0 1 0 0 1X1 X2 X3 X4 X5 X6 GENES

ALELO

CROMOSOMA

ALGORITMO GENÉTICO – OTRAS DEFINICIONES

FACTOR PROBLEMÁTICO => FUNCION OBJETIVO CICLO GENERACIONAL => ITERACION INDIVIDUO MEJOR ADAPTADO => INCUMBENTE MEDIO AMBIENTE => F.O. + RESTRICCIONES EVOLUCION => COMO SE DESPLAZA EL A.G DE PUNTOS

DE BAJA CALIDAD A PUNTOS DE BUENA CALIDAD

ALGORITMO GENÉTICO BÁSICO

CREADO POR HENRY HOLLAND, QUIEN AL MIRAR LA EVOLUCION DE LAS ESPECIES Y GENETICA, TRATO DE RECREAR ESO EN UN ALGORITMO MATEMATICO QUE OPTIMIZARA UN SISTEMA.

ALGORITMO GENÉTICO BÁSICO

CONSTA DE 2 PASOS: 1. CREAR UNA POBLACION INICIAL 2. APLICAR ITERATIVAMENTE LOS MECANISMOS

DE LOS ALGORIMOS GENETICOS: SELECCIÓN RECOMBINACION MUTACIÓN

ALGORITMO GENÉTICO

¿Cómo SE CREA UNA POBLACION INICIAL? ¿Cuántos INDIVIDUOS DEBE TENER MI POBLACION

INICIAL?

ESTAS PREGUNTAS SON COMPLICADAS Y PARA CADA PROBLEMA ES UN NUMERO DIFERENTE DE POBLACION, SEGÚN ESTUDIOS PARA PROBLEMAS GRANDES UNA POBLACION DE 80 INDIVIDUOS DARÍA MUY BUENOS RESULTADOS, ES LO MAS RECOMENDABLE.

ALGORITMO GENÉTICO

1 0 0 1 0 0

1 1 0 1 1 0

1 0 0 0 1 0

0 0 1 0 1 0

1 0 0 1 0 0

0 0 0 0 1 0

1 1 1 1 0 1

0 0 1 1 0 1

100% Población

10% - 15% Población Creada por Heurística

ALGORITMO GENÉTICO

1 0 0 1 0 0

1 1 0 1 1 0

1 0 0 0 1 0

0 0 1 0 1 0

1 0 0 1 0 0

0 0 0 0 1 0

1 1 1 1 0 1

0 0 1 1 0 1

Población InicialF.O. (Costo)

15

31

14

13

15

9

28

16

In factibilidad (Volumen)

0

3

0

2

0

0

7

0

Volumen

6

18

9

17

6

7

22

15

5 7 4 10 9 2

2 5 10 4 7 1

C =V =

B = 15

ALGORITMO GENÉTICO - SELECCIÓN

Consiste en determinar que individuos de la población tienen derecho a tener descendientes y cuantos tendrá.

Lo importante de la SELECCIÓN es garantizar la selectividad, eso quiere decir que los mejores padres deberían de tener mas hijos que los menos adaptados.

ALGORITMO GENÉTICO - SELECCIÓN

Se tiene que crear una función de adaptación, esta permite medir cuantos hijos se merece cada habitante de la población.

F.A. en nuestro problema:

ALGORITMO GENÉTICO - SELECCIÓN

Nro. Descendientes = = A.AA

Población Inicial FO In FAPromedio

1.38

# Des

3.43

8.21

1.05

ALGORITMO GENÉTICO – SELECCIÓNMÉTODO ESTOCÁSTICO DE LOS RESIDUOS

1.38

# Des

3.438.211.05

1

3

8

1

Hijos = 13 Población Inicial = 20

0.380.430.210.05

+ 3 hijos

+ 4 hijos

4

7

8

1

ALGORITMO GENÉTICO – RECOMBINACIÓN

EL proceso de recombinación hace que los padres transfieran su información (genes buenos) a los hijos.

El mecanismo que se usa es el punto de cruce.

1 0 0 0 1

1 1 0 0 0

Punto de Cruce (ramdon = 3)

1 0 0 0 0

1 1 0 0 1

Tasa de Recom.(90% – 100%)

ALGORITMO GENÉTICO – MUTACIÓN

1 0 1 0 0 1

0 1 1 0 0 1

ALGORITMO GENÉTICO – MUTACIÓN

Tasa de Mutación

0.1% - 5%

1 0 0 1 0 0

1 1 0 1 1 0

1 0 0 0 1 0

0 0 1 0 1 0

1 0 0 1 0 0

0 0 0 0 1 0

1 1 1 1 0 1

0 0 1 1 0 1

Aleat.

Random

APLICACIÓN EN MATLAB…

GRACIAS…!!!