Kit Ciencia Y Arte: Algoritmo Genético (Vida Artificial): 6 Steps

2024 Autora: John Day | [email protected]. Última modificació: 2024-01-30 08:15

Els algoritmos genètics son probablement una de les coses més interessants de la computació (en la meva opinió). Bàsicament es pren la idea d’evolució de la biologia, i s’aplica a un algoritme en una computadora per resoldre un problema.

El algoritmo genético es parte de lo que se conoce como algoritmos evolutivos en el mundo de las ciencias de la computación. Acá hacemos un ejemplo sencillo, con el fin de aprender sobre el algoritmo. Utilitzem el Circuit Playground (CP) d’Adafruit per fer l’exercici.

Imaginen el CP que és un ser viu, i que s’ha d’adaptar a les condicions canviants de llum. El CP, ha de buscar la forma més eficient de rendir els seus leds, per obtenir la major quantitat de llum possible segons el seu sensor de llum. Per lograrlo a més ha de fer-ho acollint la menor quantitat de leds possibles. Entonces maximiza la luz, al mateix temps que minimitza la quantitat de leds. Aconseguirem fer-ho amb un algoritme genètic.

ADVERTENCIA: Aquest és un tema per a estudiants AVANZADOS

Pas 1: materials

Senzill:

1. Circuit Playground (o qualsevol Arduino amb leds i sensor de llum)
2. Bateries
3. Cable USB
4. Algo para generar luz y sombra para pruebas

Pas 2: cerqueu Al Azar

Imaginem un mono, aprenent lletres en el teclat d’una computadora, el mono simplement presiona les lletres a l’azar. Si hi ha unes 50 lletres en el teclat, cada lletra (si el mono presiona de manera independent cada vegada), té una probabilitat de 1/50 = 0,02 de ser presionada.

Ahora bé, digamos que queremos que el mono escribe la palabra "banano", ¿Podrá el mono escribir la palabra? La resposta corta és SI !!!

La resposta llarga és que si el que pot fer però tomarà un temps llarg per resoldre. Vamos esto estadísticament. La probabilitat de que el mono escrivia "banano" és llavors la probabilitat conjunta, això és:

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

Això és igual a 1 sobre 15 625 000 000, és dir la probabilitat de que el mono escrigui "banano", és 1 en 15 milions … molt poc probable! Dicho de otro modo, es muy poco probable que un mono escriba la palabra "banano" escribiendo teclas al azar, ah, pero si tuviéramos 15 millones de monos escribiendo, es posible que uno de ellos escriba la palabra "banano". llavors poc probable, però no és impossible.

Formalitzem aquesta idea poc. SI (1/50) ^ 6 és la probabilitat d'escriure "banano", llavors, 1- (1/50) ^ 6 és la probabilitat de NO escriure. Si un mono intenta n vegades, llavors, la probabilitat P de no escriure la paraula "banano" en n intentos seria:

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

Així per exemple si tinc una vegada, P = 1, si tinc un milió de vegades, P = 0.999936, però per a 10 milions de milions, P = 0,53, i mentre més gran es troba a mi, més m'acerco a P = 0, és dir, amb un número infinit d'intencions, pot estar segur de que el mono va a escriure la paraula "banano".

Lo que sí, no tenim temps infinit, es pot dir que es pot buscar una solució a l’azar, però, l’azar només tardaria molt de temps. En poques paraules, la força bruta no és una forma efectiva de buscar una solució

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 es la manera en que l’algoritmo genètic funciona, prenent idees del com es genera la variabilitat genètica en els seris vius, i inventant un algoritme per fer-ho en computadora, amb el fi de solucionar un problema. Entonces aunque contiene 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ó sobre el teorema del mono infinit

Pas 3: Evolució i definicions

La evolució

Un algoritmo genético (AG) és un algoritmo que permet trobar una solució a problemes difícils de resolució. El AG, es basa en tres principis principals d’herència Darwiniana:

• Herència: Los hijo reciben las características de sus padres. En el AG significa que les noves solucions heredan el assolit per solucions anteriors
• Variació: Debe haber un mecanismo para introducir variada. en el AG, significa que s’ha d’agregar variabilitat d’alguna manera per trobar noves solucions
• Selecció: Hi ha un mecanisme en el que selecciona els millors. En el AG, hi ha una funció de "fitness" que permet determinar quina solució és millor

Acá no me voy a meter en los detalles de como funciona la evolución de seres vivos, sino que quiero entrar de una vez a la explicación de Algoritmo Genético.

Definicions

Per poder facilitar explicar l’algoritme, debem definir algunes coses abans. Estas definicions son comunes en qualsevol explicació d'algoritmo genètic que es troben, i facilitaran entendre la literatura en les redes.

1. Un dels primers passos és "codificar" el problema, això vol dir que tinguem una representació del problema per poder treballar en el CP. Acá lo hacemos de manera sencilla. Com es mostren en una foto, tenim 10 LEDS que poden estar inclosos "1" o apagats "0", llavors tenim un arregle amb 10 elements 0 i 1. Així doncs 101000000 significa que els leds 0 i 2 estan inclosos, i el restant apagados. y 0010011010, que els leds 2, 5, 6 y 8 están encendidos
2. Una Població és un conjunt de possibles combinacions de leds encendits (ver la imagen de población), poden ser iguals o diferents. Se le llama un Cromosoma a un element en la població. Entonces un cromosoma, no és més que una representació dels LEDS encendidos y apagados del CP
3. Una mutació, es canvia a l’atzar un o diversos LEDS, com es mostra a la foto, on arbitràriament la posició 5 canvia d’apagat a encendit
4. La recombinació, consisteix en tomas dos cromosomas, escoger un punt de creuament, i intercambiar la informació entre ambdós (veure el diagrama)
5. Una funció d'avaluació o fitness, és un criteri que permet avaluar que tan bons son cada un dels cromosomes de la població per seleccionar el millor. En aquest cas, voy a treballar amb la intensitat de llum i la quantitat de leds encendits

Pas 4: El Algoritmo

pas a pas

1. Crear una població de molts cromosomes inicialitzats a l’azar
2. Avaluar quin és el millor amb la funció de "fitness"
3. Copiar el millor recombinant amb el segon millor al resto de la població
4. Aplicar mutació a tota la població
5. Repertir a partir de 2

Exemple

Como expliqué en las definiciones, una tira (cromosoma) 1000101010, representa els leds encendits "1" y apagados "0", en el circuit playground. Vam definir la nostra funció de "fitness" com:

fitness = (lectura de luz) x 0,5 - (número de leds) x 0,5

Noten com restem el número de leds en la fórmula, volem que la millor llum amb la quantitat menor de leds, llavors si una solució és similar en llum però amb menys leds, seleccionem aquesta.

Ahora llavors encendem els leds corresponents a cada cromosoma i avaluem el seu fitness, com es mostra en la figura. Noten com en l'exemple tenim:

0011100000 fitness = 98,5

1011100001 fitness = 102,5

1010101011 fitness = 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

Aquesta nova població nou avaluem el seu estat físic i així continuem. A medida que llega a una solución óptima, aunque sigue probando, se mantiene hasta que haya cambios en el ambiente.

Pas 5: El Codi

El codi es poden descarregar en mi GitHub. No voy a explicar els detalls de la llibreria "cromosome.h", sinó res més de l'algoritme genètic, com s'utilitza en el codi principal.

Codi principal

El següent codi crea una població de 20 cromosomes:

#define N 20

població pop (N);

L’objecte és població i hem anomenat pop. Esto inmediatamente ctrea una pobación de 20 cromosomas, inicialitzats amb tots els ceros. A la configuració, agregem la línia:

pop.mutateChromosomes (0,5, 0);

Per canviar aleatòriament cada cromosoma amb una probabilitat de 0,5, iniciando des del cromosoma 0. En el bucle tenim l'algorit, primer fem 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 és el millor)

pop.mutateChromosomes (0,05, 1);

I avaluem amb la funció d'avaluació, que explico més a baix

avaluar ();

Luego va ordenar els cromosomes de major a menor fitness (utilitzant bubble sort), això facilita el procés de recombinació, pop.sort ();

Allí està tot. Ahora veu la funció d'avaluació que és important

Funció d'avaluació

El codigo de evaluate () es:

void evaluate () {

for (int i = 0; i <pop.n; i ++) {setPixels (i); // dóna temps al LED per activar el retard (100); condició física (i); }}

Vean que simplement prenem els leds corresponents al cromosoma (això és el que fa setPixels ()), i avaluem el seu fitness, amb la funció, estat físic nul (int a) {

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

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

Pas 6: Funcionant i retos

Funcionant

En el vídeo es veu com va adaptant-se a les diferents condicions de llum. Sempre troba una bona solució. Si lograste entendre aquest instructable, te felicito, los algoritmos genéticos son un tema difícil en computación, pero eso es lo que lo hace más emocionante.

De alguna marea al dejar funcionant el CP amb l’algoritme, sembla casi com un ser viu explorant les condicions i evolucionant per millorar. En aquest cas estan ocurriendo moltes iteracions d’eovlució en poc temps, per a un organisme viu son molt més lent

de cierto modo el algoritmo sirve para encontrar la mejor solución, dadas ciertas condiciones. Es pot corregir els algoritmes per determinar el millor en cada situació, i després deixar-los definits en el CP, però en aquest exemple deixem que l’algoritme sempre estigui explorant.

Si es deixen moltes mutacions, veran com l’algoritme és alguna cosa inestable i li va a arribar a una situació òptima.

Comentari Final

Un exemple utilitzat és il·lustratiu, i és per facilitar l’ús de la biblioteca. El reto plantat de millorar la llum amb el menor nombre de LEDS, és senzill i fins trivial, que probablement pot solucionar de manera més ràpida amb altres mètodes. Sin embargo, si lo vemos desde el punto de vista de seres vivos, la evolució organitza, utilitza alguna cosa com un algoritme genètic per a cerques sense línies, llavors, alguna cosa com optimitzar la llum, és un problema que en la naturalització té sentit (me disculpan si me puse espeso!)

Retos

• Buscar un problema d’optimització més complicat amb una funció de "fitness" més complexa
• Millorar el desempeño, canviant probabilitat de mutació, re-combinació, augmentant la població, canviant temps (esos retards per tots metits)
• Aplicar un robot, per resoldre diferents situacions
• Estudiar la meiosi, per aprendre sobre mecanismes d’evolució
• Estudiar al fons els algoritmes genètics (hi ha llibres complets en el tema)