Esta entrada es la primera de una serie que pretende ilustrar cómo el funcionamiento de los sistemas biológicos ha influido en el desarrollo de técnicas en el mundo de la informática. Para empezar, he escogido aquella que más me llama la atención, los llamados algoritmos genéticos, que imitan el proceso de selección natural para resolver problemas de optimización.
Pero, Puertas de Acero ¿qué demonios es un problema de optimización? En palabras llanas, optimizar es buscar la mejor manera de llevar a cabo una actividad. Cualquier actividad está, a no ser que ya se desempeñe de manera óptima, sujeta a ser optimizada. Poniendo un ejemplo concreto, un problema típico de optimización sería encontrar la ruta que pase por todas las ciudades de un país y retornase al lugar de origen, pero intentando minimizar la distancia recorrida. En este problema se dispone de una solución que es el orden en el que se recorrieron las ciudades y la calidad de ésta depende de la distancia recorrida, que es precisamente lo que se desea optimizar (en este caso minimizar).
Los algoritmos genéticos lo que proponen es una manera general de obtener una solución de gran calidad para un problema dado. Como hablar de manera abstracta de este tema puede ser algo lioso, veremos como un algoritmo genético es capaz de resolver un problema de juguete. La situación es la siguiente: imaginemos que deseamos realizar la compra en el supermercado y queremos llenar el carro con alimentos que posean la mayor cantidad de calorías, pero al menor precio. Para hacer más sencilla la explicación imaginemos que el carro que empleamos tiene una capacidad máxima de seis artículos. Como lo que deseamos optimizar es el precio (minimizar) y las calorias (maximizar) podemos también suponer que los artículos del supermercado disponen de esos dos atributos.
A continuación, puede verse una lista de seis artículos del supermercado. Cada uno de ellos posee un identificador numérico, un nombre, precio, calorías y "lo bueno" que es, lo cual viene dado el cociente o ratio entre las calorías y el precio. Precisamente lo que deseamos conseguir es un carro de la compra cuyos artículos maximicen la suma de este cociente para cada artículo.
| Identificador | Nombre | Precio | Calorías | f |
| 0 | Pescado | 7 | 500 | 71 |
| 1 | Arroz | 1 | 300 | 300 |
| 2 | Pan | 0.6 | 380 | 633 |
| 3 | Patatas | 1 | 500 | 500 |
| 4 | Aceite | 3 | 800 | 266 |
| 5 | Pollo | 5 | 665 | 133 |
| 6 | Agua | 2 | 0 | 0 |
Un algoritmo genético basa su comportamiento en la evolución de poblaciones. Una población es un conjunto de individuos que codifican una determinada solución. En nuestro caso, un individuo se compondría de un cromosoma con seis genes. Cada uno de los genes indica el artículo seleccionado de la lista de la compra. Por ejemplo, un carro de la compra que contuviese arroz, pan, patatas, aceite, pollo y agua se representaría de la siguiente manera:
El valor de idoneidad (F) de este individuo vendría dado por la suma de lo bueno que son cada uno de sus elementos, es decir, la suma de los f de cada uno de los artículos que lo componen. Reitero, F indica lo bueno que es el individuo y que f es lo bueno que es cada artículo.
Al comienzo del algoritmo, la primera generación de individuos está compuesta por N individuos creados de manera aleatoria. Cada uno de ellos, al igual que el ejemplo anterior dispone de un F, cuyo valor depende directamente de los artículos que contiene. Algunos contendrán artículos mejores y otros peores, pero la idea es que existe una manera objetiva de saber cómo de adaptados están a nuestros criterios.
Una vez se dispone de una población inicial, el algoritmo pasa por cuatro fases. En primer lugar se encuentra la fase de selección, en la que se escogen aquellos individuos que son mejores (en función de su F). Por lo general, aquellos que mejor adaptados se encuentren tendrán más posibilidades de ser seleccionados, pero siempre se deja la posibilidad de que algunos de los menos aptos tengan oportunidades de continuar.
Una vez concluida la selección de individuos se procede a su cruce. Esta fase puede realizarse de varias maneras, pero basta con decir que no todos los individuos tienen derecho a reproducirse (como la vida misma, oiga) y que los detalles no son en absoluto eróticos, sino que consiste en partir el cromosoma por la mitad e intercambiar las dos dos partes resultantes para producir dos individuos. Abajo puede verse como dos carros de la compra se cruzan para producir otros dos diferentes. La fase de cruce tiene como objetivo obtener una descendencia mejor que la de la generación actual, partiendo de la base de que los individuos seleccionados son ya buenos de por sí.
Una vez se dispone de una población inicial, el algoritmo pasa por cuatro fases. En primer lugar se encuentra la fase de selección, en la que se escogen aquellos individuos que son mejores (en función de su F). Por lo general, aquellos que mejor adaptados se encuentren tendrán más posibilidades de ser seleccionados, pero siempre se deja la posibilidad de que algunos de los menos aptos tengan oportunidades de continuar.
Una vez concluida la selección de individuos se procede a su cruce. Esta fase puede realizarse de varias maneras, pero basta con decir que no todos los individuos tienen derecho a reproducirse (como la vida misma, oiga) y que los detalles no son en absoluto eróticos, sino que consiste en partir el cromosoma por la mitad e intercambiar las dos dos partes resultantes para producir dos individuos. Abajo puede verse como dos carros de la compra se cruzan para producir otros dos diferentes. La fase de cruce tiene como objetivo obtener una descendencia mejor que la de la generación actual, partiendo de la base de que los individuos seleccionados son ya buenos de por sí.
| Se define un punto de corte y se intercambian las mitades. |
Después, se llega a la fase de mutación, que consiste en cambiar algunos de los genes (en este caso son artículos de la compra) aleatoriamente por otros. Como en la naturaleza, las mutaciones pueden ser perjudiciales (el individuo ve su F disminuida), neutras (F no cambia) o beneficiosas, en el caso en el que la idoneidad incremente. Es preciso mencionar que la mutación, al igual que el cruce viene determinado por una probabilidad, la cual debido al carácter totalmente aleatorio de la operación, es mucho más baja que en el cruce. Abajo puede verse como el agua (código 6) se ve transformado en pescado (código 0), lo cual hace que su valor de F incremente, ya que como veíamos anteriormente en la tabla, el agua tenía un f de cero, mientras que el pescado, si bien es baja, no es nula.
| Mejora producida por una mutación aleatoria. |
Finalmente, si el número de individuos seleccionados es menor que los N iniciales, lo cual suele suceder a menudo, se introducen nuevos generados aleatoriamente.
Cada secuencia de selección, cruce, mutación y reemplazo constituye una generación de la población. Algunos individuos se adaptarán mejor, mientras que otros serán reemplazados por nuevos individuos aleatorios, que pasaran a pelear para ser seleccionados y poder pasar a la siguiente generación. Lo importante es que el funcionamiento es siempre el mismo, mientras se pueda calcular el valor F de cada individuo. La técnica funciona perfectamente imitando de una manera más simple, el mismo proceso evolutivo que nos ha llevado a donde estamos.
Los algoritmos genéticos pueden emplearse para problemas de planificación de cualquier tipo (transportes, fábricas, etc), así como para el diseño de componentes electrónicos. Además pueden ser empleados para componer música. La idea principal es que la propia canción entera puede evaluarse según criterios de armonía, por lo que toda la maquinaria de selección, cruce, mutación y reemplazo es aplicable. Os dejo con este enlace en el que podéis escuchar algún temita.
Los algoritmos genéticos pueden emplearse para problemas de planificación de cualquier tipo (transportes, fábricas, etc), así como para el diseño de componentes electrónicos. Además pueden ser empleados para componer música. La idea principal es que la propia canción entera puede evaluarse según criterios de armonía, por lo que toda la maquinaria de selección, cruce, mutación y reemplazo es aplicable. Os dejo con este enlace en el que podéis escuchar algún temita.
No hay comentarios:
Publicar un comentario