La natura ha estat sempre una de les principals fonts d’inspiració per a pintors, poetes i filòsofs. Però també ho ha estat a l’hora de resoldre problemes complexos de matemàtiques. En concret, la genètica i la selecció natural han servit per provar de desxifrar un dels problemes més complexos de l’últim segle: el problema de la motxilla.

El problema de la motxilla

Imagina que te’n vas d’excursió i només pots portar 2 kg dins la motxilla. Pots escollir entre una bossa de menjar, una ampolla d’un litre d’aigua, una ampolla de 500 ml de crema solar, una navalla i un llibre. A cadascun d’aquests 5 articles li assignem un valor d’importància. Ara la qüestió és trobar la millor combinació possible d’aquests articles per aprofitar al màxim els 2 kg que pots portar a la motxilla.

1. Serieu capaços de trobar la combinació de més importància (més cors) sense sobrepassar el límit de 2 kg?

Tenint en compte el pes i el valor de cada element, la millor combinació és portar-ho tot excepte la crema solar. Realment aquest problema no és gaire difícil si tenim poques combinacions possibles. A l’ordinador de casa tampoc li costa gaire resoldre’l: per comprovar les 32 combinacions (25) diferents només tarda uns quants microsegons.

I si afegim més articles a la llista?

Ampliem la llista a 10 possibles articles per ficar a la motxilla:

2.

Ara ja no és tan fàcil trobar una solució perquè tenim 1024 (210) combinacions per comprovar. A l’ordinador també li costa més resoldre el problema: tarda 200 vegades més que en el problema anterior. Si tenim una llista de 20 possibles articles, amb més d’un milió de possibilitats, l’ordinador ja tarda més d’un segon per resoldre-ho. Per tant, a mesura que anem augmentant el nombre de possibilitats, el temps que triga l’ordinador a resoldre el problema augmenta exponencialment.

Això és un problema molt conegut anomenat el problema de la motxilla (o Knapsack problem en anglès) i es porta estudiant des de fa més d’un segle.

Però segur que hi ha una manera més efectiva de trobar la solució

Efectivament, no cal comprovar totes i cada una de les combinacions. Per evitar haver de fer-ho, l’any 1950 Alan Turing va proposar una màquina d’aprenentatge que s’inspirava en els principis de l’evolució. Durant les dècades posteriors, diversos grups de recerca van anar perfilant uns algoritmes inspirats en la teoria de l’evolució –en concret la selecció natural– que permetrien resoldre problemes altrament impossibles de resoldre, com el problema de la motxilla. Aquests algoritmes s’anomenen algoritmes genètics, ja que modelen el problema com si fossin genomes.

Els algoritmes genètics

Els algoritmes genètics utilitzen “poblacions” de possibles solucions. En el cas del problema de la motxilla, tindríem diverses combinacions d’articles per omplir-la, i, fent analogia, cada individu de la població té un genoma que codifica quins articles selecciona. Per exemple: en el cas dels 5 articles possibles, cada individu tindria un genoma de 5 gens, un per cada article de la llista. Cada gen codificaria si es porta (1) o no (0) l’article en qüestió.

3. Un individu podria tenir aquest genoma, per exemple, que codificaria la combinació de portar una bossa de menjar, una ampolla d’aigua i crema solar.

Si ajuntem diversos individus –o diverses combinacions possibles– aleshores tenim una generació.  La generació d’inici és simplement un conjunt de combinacions generades aleatòriament.

4. Aquí tindríem una generació de 5 individus amb els seus respectius genomes.

Comencem el procés de selecció natural

A partir de la generació d’inici, s’ha de determinar com serà el procés de selecció natural per determinar la supervivència dels individus més forts. Per establir quins individus sobreviuran, hem de decidir quina característica haurien de tenir per ser els millors. Per això, determinem una funció d’aptitud.

En el cas de la motxilla, la funció d’aptitud serà la suma dels valors dels articles que hi fiquem, sempre que no superin el límit de pes de 2 kg. Si el límit de pes se supera, el valor de la funció d’aptitud és 0.

5. Els individus de la generació que hem creat tenen cadascun un valor de la funció d’aptitud (en vermell) i un pes total.

Pares i fills

Un cop hem establert el valor de tots els individus de la generació, seleccionem aquells que es reproduiran: els pares. Estadísticament, els individus més forts tindran més possibilitats d’emparellar-se i tenir descendència.

Per simular la reproducció, escollim dos individus que faran de pares. Els seus genomes es divideixen en dues parts tallant-los en un punt aleatori. Seguidament, les dues parts finals dels genomes dels pares s’intercanvien generant dues noves solucions (o fills) per la propera generació. Aquest procés s’anomena encreuament i es repeteix tantes vegades com faci falta per generar el mateix nombre d’individus que tenia la generació anterior.

Com que els individus més forts tenen més probabilitats de reproduir-se i transmetre els seus gens “bons”, les generacions posteriors tenen millors individus. Tot i això, la selecció dels progenitors i el encreuament tenen un component aleatori. No podem assegurar-nos que tallant els genomes dels pares no destruïm les millors solucions, ni tampoc podem assegurar-nos que obtinguem la millor combinació possible. 

Elitisme

Si es vol evitar que es destrueixin les millors solucions, sempre podem dir-li a l’algoritme que transmeti íntegrament els millors individus de cada generació a la següent. És clar que això no té res a veure amb el procés natural, però en una simulació artificial es poden seguir les normes que es vulguin.

Mutació

El següent pas per fer que el nostre algoritme s’assembli més al procés natural seria incloure mutacions. Les mutacions permeten descobrir noves solucions impossibles d’obtenir només amb l’encreuament dels individus. Durant el procés de mutació de l’algoritme, determinem que, amb una certa probabilitat, es facin canvis aleatoris en el genoma dels individus.

Ara ja és qüestió de deixar passar el temps…

Amb tots aquests processos es pot generar un bucle que creï generació rere generació. El procés es pot aturar en el moment en què s’obté una solució prou bona o en el moment en què s’arriba a un màxim de generacions. Quan s’atura l’algoritme es treu el millor individu de l’última generació i es considera la solució final.

Ja per acabar…

Arribats en aquest punt, ja podríem intentar resoldre el problema de la motxilla amb molts més articles. És clar, tanmateix, que aquests algoritmes no només serveixen per resoldre el problema de la motxilla. També podrien fer-se servir, per exemple, per determinar la manera òptima d’evitar que dos avions xoquin o la forma d’una antena per tal que radiï de la millor forma possible.

A l’hora de la pràctica, hi ha moltes maneres diferents d’abordar els algoritmes genètics, però en general tots utilitzen els mateixos ingredients: una representació genètica de les solucions, una generació aleatòria dels primers individus, una funció d’aptitud, un criteri de selecció de progenitors, un criteri de encreuament per formar nous individus i una certa mutació.

Per saber-ne més

Xin-SheYang – Nature-inspired optimization algorithms

Towards data science – Introduction to Genetic Algorithms — Including Example Code

International Journal of Computer Sciences and Engineering – A Study on Genetic Algorithm and its Applications