Kit Ciência Y Arte: Algoritmo Genético (Vida Artificial): 6 Passos

2024 Autor: John Day | [email protected]. Última modificação: 2024-01-30 11:38

Los algoritmos genéticos filho provavelmente una de las cosas más interesantes de la computación (en mi opinión). Basicamente, se toma a ideia de evolução da biologia, e se aplica um algoritmo em um computador para resolver um problema.

O algoritmo genético é a parte de lá que se conoce como algoritmos evolutivos no mundo das ciências da computação. Acá hacemos un ejemplo sencillo, con el fin de aprender sobre el algoritmo. Usamos el Circuit Playground (CP) de Adafruit para hacer el ejercicio.

Imaginen el CP que es um ser vivo, y que se debe adaptar a las condiciones cambiantes de luz. El CP, debe buscar la forma más eficiente de prender sus leds, para obtener la mayor cantidad de luz possível según su sensor de luz. Para lograrlo además debe hacerlo encendiendo la menor cantidad de leds posibles. Entonces maximiza la luz, al mismo tiempo que minimiza la cantidad de leds. Acá trataremos de hacerlo com um algoritmo genético.

ADVERTENCIA: Este é um tema para estudiantes AVANZADOS

Etapa 1: materiais

Simples:

1. Circuit Playground (o cualquier Arduino com leds e sensor de luz)
2. Baterías
3. Cabo USB
4. Algo para generar luz e sombra para pruebas

Etapa 2: Búsqueda Al Azar

Imaginemos un mono, apretando letras en el teclado de una computadora, el mono simplemente presiona las letras al azar. Si hay unas 50 letras en el teclado, cada letra (si el mono presiona de manera independente cada vez), tiene una probabilidad de 1/50 = 0.02 de ser presionada.

Ahora bien, digamos que queremos que el mono escriba la palabra "banano", ¿Podrá el mono escribir la palabra? La respuesta corta es SI !!!

La respuesta larga es que si lo puede hacer pero tomará un tiempo largo para resolverlo. Vamos esto estadísticamente. La probabilidad de que el mono escriba "banano" es entonces la probabilidad conjunta, esto es:

(1/50) x (1/50) x (1/50) x (1/50) x (1/50) x (1/50) = (1/50) ^ 6

Esto es igual a 1 sobre 15 625 000 000, es decir la probabilidad de que el mono escriba "banano", es 1 en 15 millones… muy poco provável! Dicho de otro modo, es muy poco provável que un mono escriba la palabra "banano" escribiendo teclas al azar, ah, pero si tuviéramos 15 millones de monos escribiendo, é possível que uno de ellos escriba la palabra "banano". entonces poco provável, pero não imposível.

Formalicemos esta ideia un poco. SI (1/50) ^ 6 es la probabilidad de escribir "banano", entonces, 1- (1/50) ^ 6 es la probabilidad de NO escribirlo. Si un mono intenta n veces, entonces, la probabilidad P de no escribir la palabra "banano" en n intentos sería:

P = [1- (1/50) ^ 6] ^ n

Assim por ejemplo si intento una vez, P = 1, si intento un millón de veces, P = 0.999936, pero para 10 mil millones, P = 0.53, y mientras más grande se n, más me acerco a P = 0, es decir, con un numero infinito de intentos, puedo estar seguro de que el mono va a escribir la palabra "banano".

Lo que sí, no tenemos tiempo infinito, es decir se puede buscar una solução al azar, pero, el azar solo tardaría mucho tiempo. En pocas palabras, la fuerza bruta no es una forma efectiva de buscar una solución

Lo maravilloso es que la naturaleza busca al azar, pero de manera constructiva, es decir, busca de forma aleatoria pero manteniendo una buena solución y haciendo modificaciones a veces fuertes a veces pequeñas de ellas. Esa é a manera en que o algoritmo genético funciona, tomando ideias del como se genera la variabilidad genética en los seres vivos, e inventando um algoritmo para hacerlo en computadora, con el fin para solucionar um problema. Entonces aunque contém elementos de azar, también tiene memoria y hace que acad intento de buscar la solución, no sea independiente del intento anterior.

NOTA: Busquen información sobre el teorema del mono infinito

Etapa 3: Evolución Y Definiciones

La evolución

Um algoritmo genético (AG) é um algoritmo que permite encontrar uma solução para problemas difíceis de resolver. El AG, se basa en tres principios principales de herencia Darwiniana:

• Herencia: Los hijo reciben las características de sus padres. En el AG significa que as novas soluções hereditárias para o alcanzado por soluções anteriores
• Variação: Crie um mecanismo para introduzir variados. en el AG, significa que se debe agregar variabilidad de alguna manera para encontrar novas soluções
• Selección: Hay un mecanismo en la cual se seleccionan los mejores. En el AG, hay una función de "fitness" que permite determinar a solução cual es mejor

Acá no me voy a meter en los detalles de como funciona a evolução de seres vivos, sino que quiero entrar de uma vez na explicação do Algoritmo Genético.

Definiciones

Para poder facilitar explicar el algoritmo, debemos definir algunas cosas antes. Estas definiciones son comunes en cualquier explicación de algoritmo genético que encuentren, y les facilitará entendre la literatura en las redes.

1. Uno de los primeros pasos es "codificar" o problema, esto quiere decir que debemos tener una representación de el problema para poder trabajarlo en el CP. Acá lo hacemos de manera sencilla. Como se muestra em uma foto, tenemos 10 LEDS que pueden estar encendidos "1" o apagados "0", entonces tenemos un arreglo con 10 elementos 0 y 1. Así entonces 101000000 significa que los leds 0 y 2 están encendidos, y el resto apagados. y 0010011010, que los leds 2, 5, 6 e 8 están encendidos
2. Una Población é um conjunto de posibles combinaciones de leds encendidos (ver la imagen de población), estas pueden ser iguaises o diferentes. Veja o nome de um cromossoma como um elemento na população. Ressalta um cromosoma, não mais que uma representação dos LEDS encendidos e apagados do CP
3. Una mutación, es cambiar al azar uno o varios LEDS, como se muestra en la foto, donde arbitrariamente la posición 5 cambia de apagado a encendido
4. La recombinación, consiste em tomas dos cromosomas, escoger un punto de cruzamiento, e intercambiar la información entre ambos (ver el diagrama)
5. Uma função de avaliação de aptidão, é um critério que permite avaliar que tan buenos son cada um de los cromosomas de la población para selecionar el mejor. Neste caso, viaje a trabalhar com a intensidade de luz e a cantidad de leds encendidos

Etapa 4: El Algoritmo

paso a paso

1. Crear una población de muchos cromosomas inicializados al azar
2. Avaliar cual es el mejor con la función de "fitness"
3. Copiar el mejor recombinando com o segundo mejor al resto de la población
4. Aplicar mutación a toda la población
5. Repertir a partir de 2

Ejemplo

Como explique en las definiciones, una tira (cromosoma) 1000101010, representa los leds encendidos "1" y apagados "0", en el circuit playground. Vamos a definir nuestra función de "fitness" como:

aptidão = (lectura de luz) x 0,5 - (número de leds) x 0,5

Noten como restamos el numero de leds en la formula, pues queremos la mejor luz con la cantidad menor de leds, entonces se uma solución es similar en luz pero con menos leds, selectemos esa.

Ahora entonces encendemos los leds correspondientes a cada cromosoma e avaliamos sua aptidão, como se muestra en la figura. Noten como en el ejemplo tenemos:

0011100000 aptidão = 98,5

1011100001 aptidão = 102,5

1010101011 aptidão = 102

Los de fitness más alto son 102.5 y 102, seleccionamos esos, y hacemos recombinación y mutación como se muestra en la imagen, lo que nos permite terminar con una nueva población, 1011100001

0011101011

1010100011

Esta nueva población avaliamos nuevamente su fitness y así continuamos. A medida que llega a una solução óptima, aunque sigue probando, se mantiene hasta que haya muda no ambiente.

Etapa 5: El Código

El código para pueden descargar en mi GitHub. Não voy a explicar os detalhes da biblioteca "cromosome.h", nada más o algoritmo genético, como é usado no código principal.

Código principal

O seguinte código cria uma combinação de 20 cromosomas:

# define N 20

população pop (N);

El objeto es população y lo hemos llamado pop. Esto inmediatamente ctrea una pobación de 20 cromosomas, inicializados con todos ceros. En el setup, agregamos la línea:

pop.mutateChromosomes (0,5, 0);

Para mudar aleatoriamente cada cromosoma com uma probabilidade de 0,5, iniciando desde o cromosoma 0. En el loop tenemos el algortimo, primero hacemos crossover:

pop.copyCrossover (2);

Luego aplicamos mutación con una probabilidad baja (0.05), e iniciando del cromosoma 1 para mantener el mejor que hemos obtenido en la población (el cromosoma 0 es el mejor)

pop.mutateChromosomes (0,05, 1);

Y avaliamos com a função de avaliação, que explico más abajo

Avalie();

Luego ordenamos los cromosomas de mayor a menor fitness (usando bubble sort), esto facilita o processo de recombinação, pop.sort ();

Allí está todo. Bem-vindo à função de avaliação que é importante

Função de avaliação

El codigo de Evalu () es:

void avaliar () {

para (int i = 0; i <pop.n; i ++) {setPixels (i); // dá tempo ao LED para ligar delay (100); aptidão (i); }}

Vean que simplemente prendemos los leds correspondientes al cromosoma (eso é lo que hace setPixels ()), y avaliamos su fitness, con la función, void fitness (int a) {

pop.fitness [a] = 0,5 * float (CircuitPlayground.lightSensor ()) - 0,5 * float (pop.countBits (a)); }

Almacenamos o valor de fitness de cada cromosoma en pop.fitness

Etapa 6: Funcionando Y Retos

Funcionando

En el video se ve como va adaptando de apoco a las diferentes condiciones de luz. Siempre encuentra una buena solución. Se lograste entendre este instructable, te felicito, los algoritmos genéticos filho de um tema dificil en computación, pero é lo que hace más emocionante.

De alguna marea al déjar funcionando el CP con el algoritmo, parece casi como um ser vivo explorando as condições e evolucionando para mejorar. En este caso está ocorrendo muchas iteraciones de eovlución en poco tiempo, para un organismo vivo son mucho más lentas

de cierto modo o algoritmo sirve para encontrar la mejor solução, dadas ciertas condiciones. Se pede correr os algoritmos para determinar o mejor em cada situação, e elimina as definições das definições no CP, pero en este ejemplo dejamos que o algoritmo siempre esté explorando.

Si se dejan muchas mutaciones, verán como el algoritmo es algo inestable y le va a costar llegar a una situación optima.

Comentário Final

O ejemplo utilizado é ilustrativo, e é para facilitar o uso da biblioteca. O reto plantado de mejorar la luz com o menor número de LEDS, es simple y hasta trivial, que provavelmente se pode solucionar de manera mais rápida con otros métodos. No embargo, se lo vemos from the punto de vista de seres vivos, la evolución organa, utiliza algo como um algoritmo genético para búsquedas no lineales, entonces, algo como optimizar la luz, é um problema que en la naturaliza tiene sentido (me disculpan si me puse espeso!)

Retos

• Buscar um problema de otimização más complicado com uma função de "aptidão" más compleja
• Mejorara el desempeño, cambiando probabilidad de mutación, re-combinación, aumentando la población, cambiando tiempos (esos delays por allí metidos)
• Aplicar a un robot, para que resuelva diferentes situaciones
• Estudar meiose, para aprender sobre mecanismos de evolução
• Estudiar a fondo los algoritmos genéticos (hay libros completos en el tema)