Algoritmos genéticos

Algoritmos genéticos

SIS4307

"Aunque el ingenio humano puede lograr infinidad de inventos, nunca ideará ninguno mejor, más sencillo y directo que los que hace la naturaleza, ya que en sus inventos no falta nada y nada es superfluo".Leonardo Da Vinci

Índice

Características: salud, reproducción, mutación

Programación genética y algoritmos genéticos

El teorema de los esquemas

Creación y regeneración de poblaciones

Características: salud, reproducción, mutación

Las proteinas que producen los seres vivos determinan las caracteríticas que le permiten habitar en el medio de manera óptima.

Aminoácidos

Proteínas

+ info

"La naturaleza perpetúa aquello que resulta mejor".Johannes Goldschmidth

Características: salud, reproducción, mutación

En AG estos se mapean y se genera un código para establecer el dominio.

Aminoácidos

Proteínas

Algoritmo Genético Simple

Un algoritmo genético simple o básico, está compuesto de un mecanismo de selección de los genotipos o individuos, o soluciones potenciales más aptos que se utilizarán en la creación de los descendientes de la nueva generación y un conjunto de operadores genéticos. El algoritmo genético simple o básico, parte de n estructuras de cadenas de m bits, las cuales pueden ser generadas aleatoriamente. Cada estructura es evaluada y se le asigna una medida generalmente llamada fitness, o actitud. Las probabilidades de selección son calculadas para cada estructura basándose en su valor particular de fitness.

+ info

Algoritmo Genético Simple

La nueva generación de estructuras es creada seleccionando estructuras de acuerdo a las probabilidades asignadas en la presente generación, y con la aplicación a ésta de un conjunto de operadores genéticos. Estos operadores se aplican a cada pareja tomadas de la población presente por la selección hasta que n nuevas estructuras son creadas. La base de conocimientos de la nueva generación es entonces reemplazada por la generación presente. Las nuevas estructuras son evaluadas y este ciclo se repite hasta un número previamente definido de generaciones o si algún criterio de terminación es alcanzado. Como se ha mencionado, la selección determina qué individuos son los que cuentan con las condiciones más aptas para contribuir a la formación de nuevos descendientes. Los métodos de selección asignan a cada uno de los individuos de una población un número real que corresponde al valor de la función objetivo. Este valor indica el número esperado de descendientes a ser generados de ese individuo en particular en el tiempo t.

+ info

Métodos de selección

Algunos de los métodos de selección comúnmente usados son los siguientes.

Determinista

I. Reproducción proporcional

Estocástico

Con substitución

II. Torneo

Sin substitución

Métodos de selección

Reproducción proporcional, este método describe un grupo de esquemas de selección que eligen individuos de la población para que pasen a la siguiente generación y se crucen de acuerdo a sus valores de la función objetivo. Dentro de esta clasificación, tenemos a los métodos determinísticos y estocásticos. En estos esquemas, la probabilidad de selección pi de un individuo en la generación t, está dada por la siguiente ecuación:

Métodos de selección

II. Torneo

Con substitución

Sin substitución

Con Substitución, lo cual es una asignación a cada uno de los individuos de la población de su competidor de manera aleatoria tomado de la misma población, quedándose con el mejor. Sin substitución, generación de una permutación tamaño n, lo cual representa el tamaño de la población compitiendo con cada uno de los individuos de la población guardando nuevamente la mejor solución. En este método, se eligen individuos aleatoriamente de una población, se selecciona el mejor individuo de este grupo para el procesamiento y se repite hasta que la población está completa.

Los torneos se dan frecuentemente entre pares de individuos. Esto corresponde al torneo con substitución. Para el torneo sin substitución, se realiza una permutación tamaño n, tamaño de la población, que representa a los competidores de cada uno de los individuos.

Esquema

Algoritmos genéticos

Simulación

Codificación del dominio

Determina el espacio en el que se encuentran las posibles soliciones al problema planteado: Ejemplos: Problema de optimización de una función Dominio "Subconjunto de números reales" Una vez que se ha definido la manera de codificar los elementos del dominio del problema y se conoce la forma de pasar de un elemento a su código y vice- versa, es necesario fijar un punto de partida. En ella incluye la codificación de las estructuras utilizando el código binario 0 y 1. Un código de alguna estructura puede aparecer más de una vez.

+ info

Evaluación de la población

• Habilidad para sobrevivir.
• Se determina una calificación de acuerdo a su grado de adaptación (fitness)
• Fitness, es un número real no negativo.
• Entre más grande, mejor la solución propuesta por dicho individuo.
• El objetivo, es distinguir las buenas propuestas de las que no lo son.
• La función de adaptación asigna sólo una calificación por indivduo.
• Crear el fitness consume mayor tiempo de ejecución en un AG.

+ info

Selección

• De los individuos mejor calificados (mayor fitness)
• Función del AG en esta etapa:
• Elegir la mayor cantidad de individuos buenos.
• Explotación de su conocimiento.
• Exploración de los mejores individuos.
• Convergencia prematura: Un individuo bueno, puede ser el mejor podible.
• Si sólo se hace selección forzando que sea más probable elegir al mejor individuo de la población pero sin asegurarlo, es posible que este indi viduo se pierda y no forme parte de la siguiente generación.
• Elitismo: selección de los mejores n individuos de la generación para pasar intactos a la siguiente.

+ info

Cruzamiento

• Meiosis
• Combinación de los gametos de los padres para producir un índividuo híbrido.
• En AG se denomina mezcla.
• El mecanismo más común se llama Cruzamiento de punto.
• punto de corte / quiasma
• La cruza de los códigos genéticos de individuos exitosos favorece nuevos individuos con las características deseables de sus ancestros.

+ info

Mutación

• Algunas veces, muy pocas de hecho, la ADN-polimerasa (la enzima encargada de replicar el código genético), se equivoca y produce una mutación, una alteración accidental en el código genético de los seres vivos.
• Ocasionalmente algunos elementos del código de ciertos individuos de un al goritmo genético se alteran a propósito. Éstos se seleccionan aleatoriamente en lo que constituye el símil de una mutación.
• Objetivo
• Generar nuevos indivi- duos, que exploren regiones del dominio del problema que probablemente no se han visitado aún.

+ info

AGS

Algoritmo genético simple por John Henry Holland

+ info

AGS

La selección es proporcional utilizando la Ruleta(Roulette wheel selection)

+ info

AGS

La condición de terminación, se puede dar por establecer un número fijo de generaciones

+ info

AGS

Quiasma = Cruzamiento de puntos. 1-point crossover

+ info

AGS

• Tamaño de población fijo en todas las generaciones.
• Selección proporcional (de ruleta).
• Cruzamiento de un punto. La probabilidad de cruza se mantiene fija para todas las generaciones y todas las parejas.
• Mutación uniforme (todas las posiciones de las cadenas genéticas tienen la misma probabilidad de ser cambiadas). La probabilidad de mutación permanece fija para todas las generaciones y todas las posiciones de los individuos.
• Selección no elitista. Esto es, no se copian individuos de una generación a otra sin pasar por el proceso de selección aleatoria (en este caso, proporcional).

Se caracteriza por tener:

+ info

Ejemplo

• Codificar el dominio de la función [0, 0.875]
• Generar de forma aleatoria un conjunto de posibles soluciones
• Seleccionar a los individuos
• Cruzamiento, validar si es posible el cruzamiento entre los individuos seleccionados.
• Mutación.

• Tamaño de población fijo en todas las generaciones.
• Selección proporcional (de ruleta).
• Cruzamiento de un punto. La probabilidad de cruza se mantiene fija para todas las generaciones y todas las parejas.
• Mutación uniforme (todas las posiciones de las cadenas genéticas tienen la misma probabilidad de ser cambiadas). La probabilidad de mutación permanece fija para todas las generaciones y todas las posiciones de los individuos.
• Selección no elitista. Esto es, no se copian individuos de una generación a otra sin pasar por el proceso de selección aleatoria (en este caso, proporcional).

Reporte de lectura (p.14 a 18)

https://anahuac.primo.exlibrisgroup.com/permalink/52ANAHUAC_INST/129oqcn/alma993889096505016

Tarea

+ info

+ info

Tarea

+ info

+ info

Tarea

+ info

+ info

¡Gracias!

Muestreo determinístico

El muestreo determinístico es un esquema en el cual las probabilidades de selección son calculadas como se muestra en la ecuación anterior. Posteriormente, se realizan tantos giros como individuos se desean seleccionar, y se van tomando de acuerdo al individuo al cual apunta en cada giro.

Método estocástico

Por otra parte, el método estocástico inicia de una manera idéntica al muestreo determinístico, sin embargo, aquí se realiza un solo giro de la ruleta, pero se tienen tantos apuntadores como individuos se desean seleccionar ubicados a la misma distancia.