Algoritmos

Algoritmos genéticos

Concepto
Algoritmo de búsqueda basado en la mecánica de la genética y la selección natural.Un algoritmo genético puede resolver problemas que aún no están completamente
caracterizados o son demasiado complejos para permitir
una completa caracterización. Es decir, problemas para
los cuales no necesariamente conocemos cómo llegar a
una buena solución, pero si podemosevaluar por alguna
medida cuantificable el valor relativo de una solución (o
al menos el valor relativo de una solución potencial en
comparación con otra).
El concepto básico de un algoritmo genético es la codificación de una solución potencial de un problema como
una serie de parámetros.

Un conjunto de valores de parámetros es tratado como el
genoma o material genético de una soluciónindividual. Se
crea una gran población de soluciones candidatas (inicialmente con valores de parámetros al azar). Estas soluciones son esencialmente apareadas unas con otras por varias generaciones simuladas bajo el principio de supervivencia del más apto.
El apareamiento tiene lugar haciendo uso de operadores
tales como el entrecruzamiento, y la mutación (esencialmente la introducción de ruido).El tercer operador básico
es la reproducción.
AG explota eficientemente la información histórica para
especular sobre nuevos puntos de búsqueda con la esperanza de un mejor rendimiento.

Robustez
La robustez, balance entre eficiencia y eficacia necesario
para sobrevivir en muchos ambientes diferentes, es el tema central de investigación en algoritmos genéticos.
Los AGs, teórica yprácticamente han probado que proveen una búsqueda robusta en espacios complejos. Son
simples computacionalmente y no están limitados por suposiciones restrictivas acerca del espacio de búsqueda
(suposiciones acerca de continuidad, existencia de derivadas, unimodalidad y/u otras cuestiones).

Métodos basados en cálculo
Son locales, en área de influencia. Además dependen de la
existencia dederivadas. Pero...
El mundo real de búsqueda está
lleno de discontinuidades, multimodalidad y espacios de búsqueda con ruídos.
Métodos enumerativos
Buscan valores de la función objetivo en cada punto en el espacio, uno por vez. Su principal falla es la falta de eficiencia.

Eficiencia

Robustez de métodos tradicionales de búsqueda

Esquema
robusto
Esquema
especializado

Enumeración
óbúsq.al azar

combinat. unimodal multimodal

Tipo de problema

Diferencias entre AGs y los métodos
tradicionales de búsqueda
1.- Trabajan con la codificación del conjunto de parámetros, no con los parámetros.
2.- Buscan a partir de una población de puntos, no un
punto único.
3.- Usan información de una función objetivo (o más), no
derivadas u otro conocimiento adicional.
4.- Usan reglas detransición probabilísticas, no reglas
determinísticas.

Problema
Usar un algoritmo genético para maximizar la función
f(x) = x2 en el rango x ={0, ..., 31}. (Supongamos que x
es entero). La función se muestra a continuación:

Generación de la población inicial
Para usar un algoritmo genético
primero debemos codificar las variables de decisión de nuestro problema en un conjunto decadenas
de longitud finita. Hacemos esto
codificando la variable ‘x’ en un
conjunto de 5 bits.
Generación de la población inicial
al azar: definimos cada bit en cuatro conjuntos de bits con probabilidad 0.5, por ej. lanzando una
moneda 20 veces y asociando cara
con ‘1’ y cruz con ‘0’

CADENA
NUMERO

POBLACION
INICIAL
(GENERADA
AL AZAR)

01101
11000
01000
10011

VALOR
DE XCálculo de f(x)

CADENA
NUMERO

POBLACION
INICIAL
(GENERADA
AL AZAR)

VALOR
DE X

f(x)=x2

1

01101

13

169

2

11000

24

576

3

01000

8

64

4

10011

19

361
VALORES DE
APTITUD O
ADAPTACION

SUMA =

1170

Cálculo del valor de ajuste
Luego debemos maximizar f(x).
Definimos: valor de aptitud = f(x) = x2
El valor de aptitud, también...