1 Evolución y optimización
Herramientas: selection-ga, accesible desde el portal. Es un capítulo de ideas: la mayoría de las actividades son ejercicios de papel y lápiz.
Al terminar el recorrido básico de este capítulo podrás:
- explicar los tres ingredientes de la selección natural de Darwin y en qué se diferencia de la explicación de Lamarck;
- reconocer los tres rasgos de un sistema evolutivo (diversidad, selección y replicación) en sistemas biológicos, económicos y culturales, y decir cuál falta cuando un sistema no es evolutivo;
- explicar por qué la selección reduce la diversidad y qué le pasa a un sistema si nada la renueva;
- explicar por qué la evolución puede verse como un método de búsqueda;
- definir un problema de optimización, su espacio de búsqueda y sus óptimos local y global, y estimar el tamaño de un espacio de búsqueda;
- relacionar la exploración y la explotación con las dos fuerzas de un sistema evolutivo;
- describir qué toma un algoritmo genético de la evolución natural.
1.1 La idea de Darwin BásicoB
En la naturaleza hay seres muy bien adaptados a su medio, y nadie los ha diseñado. ¿Cómo puede un proceso que nadie dirige producirlos?
En 1859, Charles Darwin publicó El origen de las especies (figura 1.1). Su respuesta cabe en un párrafo de la introducción (Darwin, 1859, p. 5, traducción propia):
Como nacen muchos más individuos de cada especie de los que pueden sobrevivir, y como, en consecuencia, la lucha por la existencia se repite con frecuencia, se sigue que cualquier ser que varíe, aunque sea ligeramente, de algún modo provechoso para él, en las condiciones complejas y a veces cambiantes de la vida, tendrá más probabilidades de sobrevivir y será así seleccionado de forma natural. Por el poderoso principio de la herencia, toda variedad seleccionada tenderá a propagar su forma nueva y modificada.
figuras/01-imagenes.md, en el repositorio del libro.
En el párrafo están los tres ingredientes del mecanismo:
- Variación. Los individuos de una especie no son iguales: varían, aunque sea poco.
- Selección. Nacen más individuos de los que pueden sobrevivir, y las variaciones deciden quién tiene más probabilidades de hacerlo y de reproducirse. Darwin llamó selección natural a «esta conservación de las variaciones favorables y el rechazo de las perjudiciales» (Darwin, 1859, p. 81, traducción propia).
- Herencia. Los descendientes se parecen a sus padres, así que las variaciones que ayudaron a sobrevivir pasan a la generación siguiente.
Ninguno de los tres persigue un objetivo. Para la teoría evolutiva actual, las variaciones genéticas aparecen al azar, no porque hagan falta (Mitchell, 1996/1998, apartado 3.1); la selección solo hace que unos se reproduzcan más que otros. Pero, repetido durante muchas generaciones, el proceso acumula los cambios favorables.
Darwin tardó más de veinte años en publicar su teoría. En 1837, en el primero de sus cuadernos sobre la transmutación de las especies, dibujó su primer árbol evolutivo (figura 1.2). Parte de un antepasado, marcado con un 1, y se ramifica: unas ramas llegan hasta el presente y otras se interrumpen. Las letras señalan especies actuales: según la nota de Darwin, entre A y B hay una distancia enorme, y entre B y C, la gradación más fina. Junto al árbol escribió que, para que cada generación tenga tantos seres vivos como ahora y haya muchas especies en un mismo género, hace falta la extinción. En el dibujo están los tres ingredientes: las ramas se separan porque los descendientes varían, unas se cortan porque no todas las variantes sobreviven, y cada rama sale de otra porque los rasgos se heredan.
figuras/01-imagenes.md, en el repositorio del libro.
Darwin no fue el primero en proponer que las especies cambian. Medio siglo antes, Jean-Baptiste Lamarck (figura 1.3) había defendido en su Filosofía zoológica dos leyes: los órganos que se usan mucho se fortalecen y los que no se usan se debilitan hasta desaparecer, y lo que un individuo adquiere o pierde de este modo lo conserva la reproducción en sus descendientes (Lamarck, 1809, capítulo «VII»). Es la herencia de los caracteres adquiridos. La diferencia con Darwin está en el origen de los cambios: para Lamarck, el propio individuo los produce durante su vida, y se heredan; para Darwin, la variación ya está ahí y la selección decide cuál se conserva. La biología acabó rechazando la herencia de los caracteres adquiridos (Mitchell, 1996/1998, apartado 3.1), aunque, como veremos en las ampliaciones, la epigenética ha matizado ese rechazo.
figuras/01-imagenes.md, en el repositorio del libro.
Un algoritmo genético toma la idea de Darwin: una población de soluciones que varían, una selección que favorece a las mejores y una herencia que pasa sus rasgos a la generación siguiente. Es el ciclo del capítulo 2.
¿Por qué tienen las jirafas el cuello tan largo? Explícalo como lo haría Lamarck y como lo haría Darwin. ¿En qué se diferencian las dos explicaciones?
Ver la solución
Lamarck. Los antepasados de las jirafas estiraban el cuello para alcanzar las hojas altas de los árboles. Con el uso, el cuello de cada uno se alargaba un poco durante su vida, y ese alargamiento lo heredaban sus crías. Generación tras generación, los cuellos se fueron alargando.
Darwin. En la población de antepasados había cuellos algo más largos y algo más cortos, por variación, no por esfuerzo. Cuando escaseaba el alimento, los de cuello más largo alcanzaban más hojas, sobrevivían más y dejaban más crías, que heredaban cuellos largos. Generación tras generación, el cuello medio se fue alargando.
La diferencia está en de dónde sale el cambio y qué se hereda. Para Lamarck, el cambio lo produce el uso durante la vida del individuo y se hereda. Para Darwin, la variación existe antes de la selección y no la provoca la necesidad; lo que se hereda es lo que el individuo traía al nacer, y la selección decide qué variantes abundan más.1.2 ¿Qué hace evolutivo a un sistema? BásicoB
Hablamos de la evolución de las especies, pero también de la evolución de la economía, de una lengua o de la tecnología. ¿Es solo una forma de hablar, o tienen algo en común?
Lewontin resumió la teoría de Darwin en tres principios: los individuos de una población son distintos entre sí (variación); los distintos tipos sobreviven y se reproducen a ritmos distintos (aptitud diferencial), y los descendientes se parecen a sus padres en lo que les hace más o menos aptos (la aptitud se hereda) (Lewontin, 1970). En esa lista no aparecen ni los genes ni el ADN. Por eso el esquema puede aplicarse a otras cosas. Campbell, por ejemplo, defendió que una variación ciega seguida de una retención selectiva explica también el pensamiento creativo y otros procesos de adquisición de conocimiento (Campbell, 1960).
Luis R. Izquierdo lo sintetiza en tres rasgos que comparten todos los sistemas evolutivos, aunque sus entidades sean de naturaleza muy distinta: moléculas, células, genes, animales, organizaciones, ideas o comportamientos (Izquierdo, 2008, pp. 22–23):
- Diversidad. Las entidades del sistema no son todas iguales, y sus diferencias afectan a su aptitud (fitness). La aptitud es un indicador medible que determina cómo evoluciona la población: las entidades con más aptitud tienden a extenderse relativamente más que las demás.
- Selección. Es una fuerza que discrimina: favorece a unas entidades frente a otras, según su aptitud. Al quedarse solo con algunas, reduce la heterogeneidad del sistema.
- Replicación, herencia o conservación. Las propiedades de las entidades, o las propias entidades, se conservan, se replican o se heredan, al menos en parte, de una generación a la siguiente. Puede ocurrir por transmisión genética, en los sistemas biológicos, o por aprendizaje social, como la imitación, en muchos sistemas socioeconómicos.
Son los tres ingredientes de Darwin, pero sin nada que sea exclusivo de la biología. No hacen falta ADN ni organismos que nazcan y mueran. Basta con entidades distintas entre sí, un criterio que favorezca a unas frente a otras y un mecanismo que conserve lo que se ha seleccionado. Por eso un algoritmo, que no tiene nada de vivo, puede ser un sistema evolutivo.
La economía. En 1950, Armen Alchian propuso mirar la competencia entre empresas como una selección. Si nadie sabe de antemano qué decisión dará el máximo beneficio, el mercado no premia a quien lo maximiza, sino a quien obtiene beneficios positivos: esos son los que sobreviven. Y los beneficios van a quienes son mejores que sus competidores reales: el éxito acompaña a la superioridad relativa (Alchian, 1950, p. 213). Alchian buscaba en la economía los equivalentes de la herencia, las mutaciones y la selección natural (Alchian, 1950, p. 220). Nelson y Winter (1982) desarrollaron esa idea en una teoría evolutiva del cambio económico. En ella, las rutinas de las empresas, sus formas habituales de hacer las cosas, hacen el papel de los genes: se conservan y se imitan; el mercado selecciona a las empresas, y la búsqueda de rutinas nuevas hace de mutación. Hoy se habla de darwinismo generalizado: para explicar la evolución de una economía hay que decir cómo se genera y se renueva la variedad, cómo se replican los hábitos, las costumbres, las normas y las rutinas, y por qué unas entidades duran o se multiplican más que otras (Aldrich et al., 2008).
La cultura. En la evolución cultural, lo que cambia son los comportamientos, las creencias, las técnicas o las palabras, que pasan de unas personas a otras por enseñanza e imitación. Cavalli-Sforza y Feldman (1981) y Boyd y Richerson (1985) empezaron a estudiar con modelos matemáticos cómo se transmite y cambia la cultura. Mesoudi et al. (2004) revisaron la evidencia a la luz de El origen de las especies y concluyeron que la cultura muestra variación, competencia, herencia y acumulación de modificaciones sucesivas; de ahí su propuesta de una ciencia unificada de la evolución cultural (Mesoudi et al., 2006).
Piensa en los restaurantes de una ciudad.
- ¿Qué entidades forman el sistema? ¿Qué las hace distintas entre sí, y de dónde salen las diferencias nuevas?
- ¿Qué hace de selección? ¿Qué sería la aptitud? ¿Es absoluta o relativa?
- ¿Qué conserva o replica lo que tiene éxito?
- ¿Es, entonces, un sistema evolutivo? ¿Qué diferencias ves con la evolución biológica?
Ver la solución
Las entidades pueden ser los restaurantes o, mejor aún, sus formas de hacer las cosas: la carta, los precios, el local, el servicio. La diversidad es evidente: no hay dos iguales. Las diferencias nuevas llegan con los restaurantes que abren con ideas nuevas (innovación), con los cambios que prueban los que ya existen y también con los errores: una receta mal copiada puede salir mejor que la original.
La selección la hacen los clientes y la competencia. Los restaurantes con pocos clientes cierran; los que funcionan crecen o abren otros locales. La aptitud podría medirse con el beneficio o con la cuota de mercado. Es relativa: un restaurante bueno puede cerrar si los de su calle son mejores, y uno mediocre puede sobrevivir si no tiene competencia.
Lo que tiene éxito se conserva porque el restaurante sigue abierto, y se replica porque otros lo imitan (un plato de moda acaba en muchas cartas), porque las cadenas y franquicias copian un negocio entero y porque los cocineros que cambian de trabajo se llevan lo que aprendieron.
Sí: tiene los tres rasgos. Pero con diferencias importantes. La variación no es ciega: un empresario innova a propósito, intentando anticipar lo que funcionará. Lo que un restaurante aprende durante su vida puede copiarse; se parece más a la herencia que imaginaba Lamarck que a la genética (sección 1.1). La replicación es por imitación, no genética, y no hay generaciones bien definidas. Además, lo que favorece la selección cambia con las modas: la aptitud no es fija.
Para cada sistema, di si tiene los tres rasgos de un sistema evolutivo. Si no, ¿cuál le falta?
- Las bacterias de un paciente que toma un antibiótico.
- Los cantos rodados de una playa. Las olas desgastan y rompen antes las piedras blandas, y con los años quedan sobre todo piedras duras.
- Las palabras de una lengua.
- Un termostato que enciende la calefacción cuando la temperatura baja de 20 °C.
- Una población de plantas idénticas que se reproducen por esquejes, sin mutaciones.
- Los chistes que circulan por los grupos de mensajería.
Ver la solución
Sí. Hay diversidad: por mutación, algunas bacterias resisten mejor el antibiótico. Hay selección: el antibiótico mata antes a las sensibles. Y hay replicación: las resistentes se dividen y sus descendientes heredan la resistencia.
No. Hay diversidad (piedras duras y blandas) y una especie de selección (las olas eliminan antes las blandas), pero no hay replicación: una piedra dura no hace copias de sí misma. La composición de la playa cambia, pero no se acumula nada nuevo, y cuando solo quedan piedras duras el proceso se detiene.
Sí. Aparecen palabras nuevas y variantes de las existentes (diversidad); unas se usan y se copian más que otras, y algunas caen en desuso (selección); y los hablantes las aprenden de otros hablantes (replicación por imitación). Es un ejemplo de evolución cultural.
No. El termostato reacciona a su entorno, pero no hay una población de entidades distintas, ni selección, ni replicación: siempre aplica la misma regla. Es un sistema que se ajusta al entorno, pero no evoluciona.
No, porque le falta diversidad. Si todas las plantas son iguales, la selección no tiene nada que elegir: pueden morir más o menos plantas, pero la población no cambia de composición. En cuanto aparece una mutación, aparece la diversidad.
Sí. Hay chistes nuevos y versiones que cambian al contarlos (diversidad); los más graciosos se reenvían más (selección); y cada reenvío es una copia (replicación). Richard Dawkins llamó memes a estas unidades culturales que se copian de una persona a otra (Dawkins, 1976/2006, capítulo «11») (véanse las ampliaciones).
1.3 Dos fuerzas que tiran en sentidos opuestos BásicoB
Si la selección favorece una y otra vez a las mismas entidades, ¿qué le pasa a la diversidad del sistema?
La selección necesita diferencias: si todas las entidades son iguales, no hay nada que elegir. Ronald Fisher lo expresó en su teorema fundamental de la selección natural: la velocidad a la que aumenta la aptitud en cada momento es igual a la varianza genética de la aptitud en ese momento (Fisher, 1930). Cuanto más varía la aptitud heredable entre los individuos, más deprisa mejora la población.
Pero la selección reduce la diversidad, porque favorece a unas entidades frente a otras. Si nada la renueva, el sistema acaba formado por copias de unas pocas entidades, o de una sola, y ya no puede cambiar más: queda bloqueado (lock-in). Por eso los sistemas evolutivos suelen tener procesos que crean y mantienen la diversidad. Actúan en sentido contrario a la selección, y son lo único que puede impedir que el sistema se bloquee (Izquierdo, 2008, p. 22). No es casualidad que la explicación de cómo se genera y se renueva la variedad sea el primer requisito del darwinismo generalizado (Aldrich et al., 2008).
En biología, la diversidad viene de las mutaciones y de la recombinación genética (Mitchell, 1996/1998, apartado 1.2). En los sistemas socioeconómicos, de las innovaciones, de la experimentación, de que la información no llega a todos por igual o, sencillamente, de los errores (Izquierdo, 2008, p. 22); Alchian (1950, pp. 218–219) ya veía en la imitación y la innovación las formas en que las empresas se adaptan. Por eso el proceso por el que aparecen entidades nuevas se llama mutación en biología y experimentación o innovación en economía.
La evolución como búsqueda. Repetidas durante millones de generaciones, estas dos fuerzas producen diseños asombrosos sin que nadie los dirija. No es casualidad que el guepardo, el animal terrestre más rápido, cace impalas, que también son muy rápidos. Cada especie forma parte del entorno de la otra. Los guepardos que corrían y aceleraban algo más cazaban más y dejaban más crías; los impalas que escapaban mejor sobrevivían más. Cada mejora de una especie aumentaba la presión selectiva sobre la otra: es una carrera de armamentos evolutiva (Wilson et al., 2018). Nadie diseñó la velocidad de ninguno de los dos: las variantes que ayudaban a cazar o a escapar se propagaron solas.
Mitchell lo plantea en general: la evolución es, en la práctica, un método para buscar «soluciones» entre un número enorme de posibilidades. En biología, las posibilidades son las secuencias genéticas, y las soluciones, organismos capaces de sobrevivir y reproducirse en su entorno. Y es una búsqueda en un terreno que cambia: la aptitud de un organismo depende también de los que le rodean, así que lo que conviene buscar cambia a medida que las especies evolucionan (Mitchell, 1996/1998, apartado 1.2). El guepardo y el impala son un buen ejemplo: cada uno forma parte del terreno en el que busca el otro.
Esa es la idea que aprovechó John Holland (1975/1992). Si la evolución encuentra buenas soluciones a los problemas de la supervivencia, un programa que imite sus mecanismos podría encontrarlas para otros problemas; Holland y su grupo se propusieron llevar los mecanismos de la adaptación natural a los sistemas artificiales (Goldberg, 1989, p. 1). Así nacieron los algoritmos genéticos. Un algoritmo genético mantiene una población de soluciones posibles de un problema, mide su aptitud, favorece a las más aptas y genera a partir de ellas soluciones nuevas, generación tras generación. Veremos su origen en la sección 1.6 y su ciclo completo en el capítulo 2.
En un algoritmo genético también actúan las dos fuerzas. La selección no crea individuos nuevos: elige, entre los que ya hay, cuáles se copian. Si se repite generación tras generación sin nada más, la población se queda sin diversidad.
- Baja hasta Varias generaciones solo con selección. La simulación parte de poblaciones de 50 individuos y encadena 40 generaciones sin cruce ni mutación: cada población es la de los padres elegidos en la anterior.
- En la gráfica Individuos distintos, sigue la curva del torneo. Empieza en 50. ¿Cuántos quedan en la generación 20? En la simulación que aparece al abrir la pantalla, la tabla de debajo da 4,5 de media en la generación 5 y 1,1 en la 20.
- Mira la gráfica Aptitud media. ¿Sigue subiendo cuando casi no quedan individuos distintos? ¿Por qué?
- Pulsa Simular de nuevo varias veces. ¿Cambia la conclusión?
La población queda bloqueada en pocas generaciones: es la versión artificial del lock-in. Lo estudiaremos con detalle en la sección 5.6. Para evitarlo, un algoritmo genético tiene operadores que generan diversidad: el cruce, que combina los genes de dos padres en individuos nuevos (capítulo 6), y la mutación, que introduce valores que no tiene nadie en la población (capítulo 7). Cuánta diversidad conviene generar es una de las preguntas centrales del diseño; volveremos a ella en la sección 1.5, después de precisar qué significa buscar.
1.4 Optimizar es buscar BásicoB
¿Qué significa, exactamente, buscar la mejor solución de un problema?
Un problema de optimización tiene dos partes: un conjunto S de soluciones factibles, el espacio de búsqueda, y una función objetivo f que asigna a cada solución un número que dice cuánto vale. Resolverlo es encontrar una solución con el mejor valor posible, un óptimo global (Talbi, 2009, p. 3). Según el problema, «mejor» será el menor valor (el coste de una ruta) o el mayor (el valor de lo que cabe en una mochila).
En la búsqueda de la evolución (sección 1.3), S serían las secuencias genéticas posibles, y la aptitud haría el papel de f, con una diferencia: en la naturaleza nadie la fija, y cambia a medida que cambian los demás seres vivos. En un algoritmo genético, S y f las da el problema.
¿Por qué no probarlas todas? Porque suelen ser demasiadas. Una proteína es una cadena de aminoácidos, y en cada posición puede haber uno de 20. Mitchell propone buscar una proteína con una forma determinada limitándose a las cadenas de 100 aminoácidos o menos (Mitchell, 1996/1998, apartado 1.4); solo las de 100 ya son 20^{100}, más de 10^{130} posibilidades. Para hacerse una idea de la escala: se suele decir que en el universo observable hay unos 10^{80} átomos; una estimación reciente da unos 2 \times 10^{80} protones y neutrones en toda su materia visible (Vopson, 2021). Hay muchísimas más proteínas posibles que átomos en el universo. Con muchos problemas, el número de soluciones crece de forma exponencial con el tamaño del problema, y revisarlas todas llevaría siglos o más (Talbi, 2009, pp. 10–11). Goldberg distingue tres familias de métodos clásicos y señala el punto débil de cada una (Goldberg, 1989, pp. 2–5):
- Los métodos basados en el cálculo suben por la pendiente de la función. Son locales, porque buscan lo mejor cerca del punto en el que están, y necesitan derivadas, que muchos problemas no tienen.
- Los métodos enumerativos revisan las soluciones una a una. Son sencillos, pero ineficientes cuando el espacio es grande.
- Las búsquedas al azar prueban soluciones al azar y se quedan con la mejor. A la larga, no lo hacen mejor que la enumeración.
Un algoritmo genético también usa el azar, pero para guiar la búsqueda, no para dar palos de ciego: una búsqueda con azar no tiene por qué ser una búsqueda sin rumbo (Goldberg, 1989, p. 5).
Óptimos locales. Muchos métodos se mueven de una solución a otra vecina, parecida a ella. Una solución es un óptimo local si no tiene ningún vecino mejor (Talbi, 2009, p. 91). Un método que pasa siempre al mejor vecino se para en el primer óptimo local que encuentra, que puede no ser el global (figura 1.4): si la función tiene varias cimas, ¿por cuál subir? (Goldberg, 1989, pp. 3–4). Lo veremos con más detalle en la sección 4.12.
figuras/01-evolucion.py, en el repositorio del libro.
Una solución o una población. Los métodos como la búsqueda local o el recocido simulado transforman una sola solución; los algoritmos evolutivos hacen evolucionar una población entera (Talbi, 2009, p. 25). Una población que empieza repartida por el espacio de búsqueda no depende de un único punto de partida.
Mejorar antes que alcanzar el óptimo. Goldberg recuerda que optimizar tiene dos partes: mejorar y acercarse a un óptimo. Para los sistemas complejos, lo más importante es mejorar: llegar pronto a una solución lo bastante buena. Alcanzar el óptimo importa mucho menos (Goldberg, 1989, pp. 6–7). El propio Holland, quince años después de su libro, escribió que pondría más énfasis en la mejora y menos en la optimización (Holland, 1975/1992, p. x). Con un algoritmo genético no solemos saber si hemos llegado al óptimo, pero sí si hemos mejorado.
Un repartidor sale de su almacén, tiene que pasar por 19 clientes y volver al almacén. Con 20 lugares, contando el almacén, hay 19!/2 rutas distintas (sección 10.2).
- ¿Cuántas rutas son, aproximadamente? Si un ordenador calcula la longitud de un millón de rutas por segundo, ¿cuánto tardaría en revisarlas todas?
- ¿Y con 25 lugares?
- En el universo observable hay unos 10^{80} átomos. ¿A partir de cuántos lugares hay más rutas que átomos? ¿Cuántos bits necesita un cromosoma binario para que haya más cromosomas distintos que átomos?
Ver la solución
19!/2 = 60\,822\,550\,204\,416\,000, unas 6{,}1 \times 10^{16} rutas. A un millón por segundo son 6{,}1 \times 10^{10} segundos. Un año tiene unos 3{,}16 \times 10^{7} segundos, así que harían falta unos 1 900 años.
Con 25 lugares, 24!/2 \approx 3{,}1 \times 10^{23} rutas: casi 10 000 millones de años. Cinco lugares más multiplican el tiempo por unos cinco millones. Por eso, salvo en problemas pequeños, no se puede revisar todo el espacio de búsqueda.
Con 60 lugares hay 59!/2 \approx 6{,}9 \times 10^{79} rutas, todavía menos que 10^{80}; con 61 lugares, 60!/2 \approx 4{,}2 \times 10^{81}, ya más. En binario, 2^{265} \approx 5{,}9 \times 10^{79} y 2^{266} \approx 1{,}2 \times 10^{80}: basta un cromosoma de 266 bits. Son tamaños modestos, y aun así no hay forma de revisar todas las opciones.
Las soluciones de un problema son las cadenas de 3 bits, y queremos maximizar f:
| Cadena | 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
|---|---|---|---|---|---|---|---|---|
| f | 3 | 1 | 2 | 5 | 4 | 0 | 6 | 2 |
Dos cadenas son vecinas si se diferencian en un solo bit: los vecinos de 000 son 100, 010 y 001.
- ¿Cuál es el óptimo global? ¿Hay algún otro óptimo local?
- Un método empieza en una cadena y pasa siempre al mejor de sus vecinos, mientras sea mejor que la cadena actual. ¿Dónde termina si empieza en 001? ¿Y si empieza en 010?
- ¿Qué ventaja tendría empezar con una población de cuatro cadenas al azar?
Ver la solución
El óptimo global es 110, con f = 6. También es óptimo local 011, con f = 5: sus vecinos, 111, 001 y 010, valen 2, 1 y 2. Las demás cadenas tienen algún vecino mejor.
Desde 001 (1), los vecinos son 101 (0), 011 (5) y 000 (3): pasa a 011, que no tiene ningún vecino mejor. Termina en 011, con 5, y no llega al óptimo. Desde 010 (2), los vecinos son 110 (6), 000 (3) y 011 (5): pasa a 110, el óptimo global. El resultado depende del punto de partida.
La figura 1.5 lo resume. Siguiendo las flechas, desde 001 se acaba en 011; desde 000, 010, 100, 101 y 111, en 110.
figuras/01-evolucion.py, en el repositorio del libro.
- Con varias cadenas repartidas por el espacio es más difícil que todas empiecen cerca del mismo óptimo local: es más probable que alguna esté cerca de 110. Y en un algoritmo genético, el cruce puede combinar partes de cadenas que están en zonas distintas.
1.5 Explorar y explotar BásicoB
Si la selección aprovecha lo que ya funciona y la variación prueba cosas nuevas, ¿cuánto conviene de cada una?
Explorar es probar posibilidades nuevas; explotar es aprovechar lo aprendido para mejorar las soluciones que ya conocemos. Una búsqueda necesita ambas cosas: descubrir alternativas y desarrollar las que parecen prometedoras.
Holland vio en la tensión entre la selección y la generación de diversidad (sección 1.3) un problema común a la evolución, la economía, el aprendizaje o el control. En todos ellos hay que mejorar sin conocer de antemano todas las opciones. Como encontrar la mejor puede llevar mucho tiempo, o no acabarse nunca, hay que explotar en cada paso la mejor de las opciones ya probadas; pero, a la vez, hay que reducir pronto la incertidumbre, es decir, conocer opciones nuevas (Holland, 1975/1992, p. 1).
James March llevó la misma tensión al aprendizaje de las organizaciones. Para él, explorar es buscar, variar, arriesgar, experimentar o innovar; explotar es refinar, elegir, producir, ser eficiente, seleccionar o ejecutar. Una organización que explora sin explotar acumula ideas nuevas que nunca desarrolla y no llega a ser buena en nada; una que explota sin explorar acaba atrapada en un equilibrio estable, pero peor de lo que podría ser (March, 1991, p. 71).
En el diseño de cualquier método de búsqueda aparecen los mismos dos criterios contradictorios: la exploración del espacio de búsqueda (diversificación) y la explotación de las mejores soluciones encontradas (intensificación). En un extremo está la búsqueda al azar, que solo explora; en el otro, la búsqueda local que pasa siempre al mejor vecino (sección 1.4), que solo explota (Talbi, 2009, pp. 24–25). Los métodos que transforman una sola solución tienden a explotar, intensificando la búsqueda en una zona; los que hacen evolucionar una población, a explorar, repartiéndola por todo el espacio (Talbi, 2009, p. 25).
En un sistema evolutivo, la selección explota lo que ya funciona y la generación de diversidad explora. Si domina la selección, el sistema se bloquea antes de encontrar algo bueno: en un algoritmo genético se llama convergencia prematura (sección 9.7). Si domina la variación, lo que se encuentra se pierde antes de aprovecharlo, y la búsqueda se parece a una búsqueda al azar. Buena parte de las decisiones de diseño de un algoritmo genético consisten en equilibrar estas dos fuerzas, como la presión selectiva del capítulo 5.
- Llevas un mes viviendo en una ciudad nueva y cada viernes cenas fuera. ¿Qué es explorar y qué es explotar? ¿Qué te pasa si solo haces una de las dos cosas?
- En un algoritmo genético, ¿qué esperas que pase si la mutación es tan fuerte que cada gen del hijo se sortea de nuevo, sin tener en cuenta el que heredó? ¿Y si no hay ni cruce ni mutación?
Ver la solución
Explotar es volver al mejor restaurante que conoces; explorar, probar uno nuevo. Si solo explotas, te quedas con el mejor de los pocos que probaste al principio y nunca sabrás si había otro mejor. Si solo exploras, cada viernes cenas en un sitio desconocido, a veces bueno y a veces malo, y nunca aprovechas lo que has aprendido. Lo razonable es explorar más al principio, cuando sabes poco, y explotar más cuando ya conoces bien las opciones.
Si cada gen se sortea de nuevo, los hijos no guardan ninguna relación con sus padres: lo que la selección había encontrado se pierde en cada generación, y el algoritmo se comporta como una búsqueda al azar. Es demasiada exploración. No es lo mismo que cambiar todos los genes: con cadenas de bits, invertirlos todos da la cadena contraria, que depende por completo del padre. El hijo deja de depender del padre cuando cada bit cambia con probabilidad 0,5 (sección 7.7). Si no hay ni cruce ni mutación, el algoritmo solo copia individuos que ya existen, y en pocas generaciones la población está formada por copias de uno solo, como en la caja «En la aplicación» de la sección 1.3. Es demasiada explotación: la población queda bloqueada.
1.6 De la evolución natural a la artificial BásicoB
¿Qué hay que tomar de la evolución para que un ordenador resuelva problemas?
Para trasladar este mecanismo a un ordenador, debemos decidir qué representa cada individuo y cómo evaluar su calidad. Si buscamos una ruta corta, cada individuo será una ruta posible y su longitud permitirá compararla con las demás. La selección favorecerá las mejores rutas, mientras que el cruce y la mutación producirán variantes. Es el problema del viajante, que resolveremos de principio a fin en el capítulo 10.
Holland lo planteó en general, a partir de la idea de adaptación: cualquier proceso por el que una estructura se modifica poco a poco para funcionar mejor en su entorno, ya sea una proteína, la pata de un caballo o un cerebro humano. Hay procesos adaptativos en la biología, la psicología, la economía o el control, y todos son, en el fondo, procesos de optimización (Holland, 1975/1992, p. xiii). En todos ellos hay unas estructuras que se modifican, unos operadores que las modifican y una medida del rendimiento; en genética, los cromosomas, la mutación y la recombinación, y la aptitud (Holland, 1975/1992, pp. 4–5). En el ejemplo de las rutas, las estructuras son las rutas; los operadores, el cruce y la mutación, y la medida del rendimiento, la longitud.
Holland presentó estas ideas en 1975, después de desarrollarlas en los años sesenta y setenta, en Adaptation in Natural and Artificial Systems (Mitchell, 1996/1998, apartado 1.1). Allí llamaba a sus algoritmos planes genéticos; fueron sus estudiantes de doctorado quienes empezaron a decir algoritmo genético (Holland, 1975/1992, p. x). Goldberg los define así (Goldberg, 1989, p. 1, traducción propia):
Los algoritmos genéticos son algoritmos de búsqueda basados en la mecánica de la selección natural y de la genética natural.
No fueron los únicos. En los años sesenta, Rechenberg propuso las estrategias evolutivas para optimizar parámetros reales, y Fogel, Owens y Walsh, la programación evolutiva. Junto con los algoritmos genéticos, forman la base de la computación evolutiva (Mitchell, 1996/1998, apartado 1.1); volveremos a ellas en la sección 2.11.
Las palabras de la biología (cromosoma, gen, alelo, aptitud) se usan en un algoritmo genético por analogía: lo que designan es mucho más sencillo que en un ser vivo (Mitchell, 1996/1998, apartado 1.3). Y hay diferencias de fondo. En la naturaleza nadie fija el objetivo; en un algoritmo genético, la aptitud la elige quien lo diseña, a partir de la función objetivo del problema (capítulo 4). Goldberg resume en cuatro rasgos lo que distingue a los algoritmos genéticos de los métodos de optimización tradicionales (Goldberg, 1989, p. 7):
- Trabajan con una codificación de las soluciones, no con las soluciones mismas (capítulo 3).
- Buscan desde una población de puntos, no desde uno solo.
- Solo usan el valor de la función objetivo, sin derivadas ni otro conocimiento auxiliar.
- Usan reglas de transición probabilísticas, no deterministas.
Completa la última columna de la tabla. Puedes ayudarte con el ciclo de la sección 2.2.
| Biología | Economía | Algoritmo genético | |
|---|---|---|---|
| Entidades | Organismos y sus genes | Empresas y sus formas de hacer las cosas | ? |
| Aptitud | Supervivencia y número de descendientes | Beneficio o cuota de mercado | ? |
| Diversidad | Mutación y recombinación genéticas | Innovación, experimentación y errores | ? |
| Selección | Selección natural | Competencia en el mercado | ? |
| Replicación | Herencia genética | Imitación, franquicias | ? |
Ver la solución
| Algoritmo genético | |
|---|---|
| Entidades | Los individuos de la población: cada uno es una solución del problema, escrita como un cromosoma (capítulo 3). |
| Aptitud | La función de aptitud, que se calcula a partir de la función objetivo del problema (capítulo 4). |
| Diversidad | La población inicial, generada al azar; el cruce, que crea combinaciones nuevas de genes, y la mutación, que crea valores nuevos (capítulos 6 y 7). |
| Selección | La selección de los padres, que favorece a los más aptos (capítulo 5), y el reemplazo, que decide quién pasa a la generación siguiente (capítulo 8). |
| Replicación | Los hijos heredan los genes de sus padres, copiados y recombinados por el cruce; con elitismo, los mejores pasan a la generación siguiente sin cambios. |
1.7 Ampliaciones Para saber más+
Lamarck, otra vez. A finales del siglo XX, la herencia de los caracteres adquiridos estaba rechazada por casi todos los biólogos, ante la abrumadora evidencia en contra; era difícil imaginar un mecanismo que llevara lo adquirido durante la vida al código genético (Mitchell, 1996/1998, apartado 3.1). La epigenética ha matizado esa conclusión. Las marcas epigenéticas, como la metilación del ADN, cambian qué genes se expresan sin cambiar la secuencia del ADN, y algunas pasan a la descendencia. Jablonka y Raz (2009) reunieron más de cien casos de herencia epigenética entre generaciones en bacterias, protistas, hongos, plantas y animales, y defienden un marco que reconoce los aspectos lamarckianos de la herencia. Heard y Martienssen (2014) concluyen que esta herencia existe, sobre todo en las plantas, pero que todavía no está claro hasta qué punto la provoca el entorno ni hasta qué punto ocurre en los seres humanos. En ratones, Takahashi et al. (2023) metilaron en el laboratorio la región reguladora de dos genes del metabolismo y comprobaron que ese cambio, y sus efectos en el metabolismo, pasaban a las generaciones siguientes por vía paterna y materna; el cambio no lo produjo el entorno, sino los investigadores. Y hay casos en los que lo adquirido sí llega a los genes: según Koonin y Wolf (2009), el sistema CRISPR-Cas, con el que bacterias y arqueas incorporan a su genoma fragmentos de los virus que las atacan y transmiten así la defensa a sus descendientes, funciona mediante un mecanismo lamarckiano genuino. Su conclusión es que las dos modalidades, la darwiniana y la lamarckiana, son importantes en la evolución. No se ha recuperado el mecanismo general de Lamarck, el uso y el desuso como motor de la adaptación, pero la regla de que nada de lo adquirido se hereda tiene excepciones: en algo, Lamarck tenía razón.
Algoritmos lamarckianos. En la evolución artificial, Lamarck no está prohibido. Muchos algoritmos genéticos se combinan con una búsqueda local que mejora a cada individuo. Si el individuo se sustituye por la solución mejorada, que sus hijos heredarán, el algoritmo es lamarckiano; si la solución mejorada solo sirve para calcular su aptitud y el cromosoma no cambia, se habla de modelo de Baldwin (Talbi, 2009, p. 390). Es la misma pregunta que aparece al reparar cromosomas infactibles (sección 3.13) y en los algoritmos meméticos (sección 10.9). El segundo nombre recuerda el efecto Baldwin: aunque lo aprendido no se herede, la capacidad de aprender puede guiar la evolución, porque los individuos que aprenden mejor sobreviven más. Hinton y Nowlan lo mostraron en 1987 con un modelo que usaba precisamente un algoritmo genético (Mitchell, 1996/1998, apartado 3.1).
El punto de vista del gen. Dawkins (1976/2006) propone mirar la evolución desde los genes, que son lo que se copia de una generación a otra, en lugar de desde los organismos que los llevan. Y extiende la idea más allá de la biología: llama memes a las unidades de transmisión cultural, como una melodía, una idea o una moda, que se replican pasando de un cerebro a otro por imitación (Dawkins, 1976/2006, capítulo «11»). Encaja con las ideas y los comportamientos de la lista de Izquierdo (sección 1.2) y con el ejercicio 1.3.
Teoría evolutiva de juegos. La teoría evolutiva de juegos nació en la biología. Maynard Smith y Price (1973) la usaron, junto con simulaciones por ordenador, para explicar por qué los combates entre animales de una misma especie suelen ser «guerras limitadas», que rara vez causan heridas graves, sin recurrir a un beneficio para la especie: combatir sin herir también favorece a cada individuo. En ese trabajo definieron la estrategia evolutivamente estable: una estrategia tal que, si la adopta la mayoría de la población, ninguna estrategia mutante obtendría más aptitud (Maynard Smith y Price, 1973, p. 15). Después la teoría pasó a la economía y a las ciencias sociales, para estudiar cómo cambian los comportamientos de agentes con racionalidad limitada que aprenden e imitan (Vega-Redondo, 1996). En la teoría evolutiva de juegos, las entidades que evolucionan son estrategias, que pueden verse como fenotipos de comportamiento, y la aptitud es el pago que obtiene cada una al jugar contra las demás (Izquierdo, 2008, pp. 23–24). A diferencia de lo que ocurre en un algoritmo genético con una función objetivo fija, la aptitud de una estrategia depende de las demás estrategias de la población; también en biología la aptitud de un organismo depende de los que le rodean (Mitchell, 1996/1998, apartado 1.4). Una de las conclusiones de la tesis de Izquierdo es que las estrategias que surgen y se mantienen en contextos evolutivos dependen mucho de supuestos que se solían considerar secundarios, como el número de jugadores, la tasa de mutación o la estructura de la población (Izquierdo, 2008, resumen). Es una advertencia que conviene recordar al elegir los parámetros de un algoritmo genético (capítulo 9).
Más lecturas. Mitchell (1996/1998, apartados 1.1–1.4) cuenta la historia de la computación evolutiva y por qué la evolución es una buena fuente de inspiración. Goldberg (1989, pp. 1–7) compara los algoritmos genéticos con los métodos de optimización tradicionales. Holland (1975/1992, capítulo «1») plantea el marco general de la adaptación en los sistemas naturales y artificiales. Izquierdo (2008, apartado 2.3) presenta los rasgos de los sistemas evolutivos y la teoría evolutiva de juegos, y Vega-Redondo (1996) la lleva de sus orígenes en la biología a las ciencias económicas y sociales. Para la evolución cultural, Mesoudi et al. (2006) es una buena puerta de entrada; para la economía, Aldrich et al. (2008) resumen qué significa aplicar los principios darwinianos a las empresas y las instituciones.
Resumen
- La selección natural de Darwin tiene tres ingredientes: variación entre los individuos, selección de los que sobreviven y se reproducen más, y herencia. Lamarck proponía, en cambio, que se heredan los cambios adquiridos durante la vida.
- Cualquier sistema con diversidad, selección y replicación es evolutivo, sea biológico, económico o cultural. La aptitud es relativa: importa ser mejor que los demás.
- La selección reduce la diversidad y, si nada la renueva, el sistema se bloquea. La generación de diversidad (mutación, innovación) actúa en sentido contrario. Con las dos fuerzas, la evolución busca, y encuentra, soluciones asombrosas, como la velocidad del guepardo y del impala; Holland aprovechó esa idea en los algoritmos genéticos.
- Optimizar es buscar en un espacio de soluciones que suele ser demasiado grande para revisarlo entero. Un método que pasa siempre al mejor vecino puede quedarse en un óptimo local; un algoritmo genético busca con una población.
- Equilibrar la selección y la generación de diversidad es equilibrar la explotación de lo que ya funciona y la exploración de lo nuevo. Con demasiada explotación, la población converge prematuramente; con demasiada exploración, la búsqueda se vuelve al azar.
- Holland propuso los algoritmos genéticos para estudiar la adaptación natural y llevar sus mecanismos a los sistemas artificiales. Un algoritmo genético es un sistema evolutivo cuyas entidades son soluciones de un problema.