Connecting Waterpeople
ACCIONA

Algoritmos genéticos

500
  • Algoritmos genéticos

Sobre el blog

Alejandro Beivide
Director del departamento de Automatización y Control de Acciona. PDD-E-2018 IESE Business School. Ingeniero en Automática y Electrónica Industrial. Master en Energías Alternativas y Eficiencia Energética
· 500

He de confesar que poder escribir este post ha sido un placer. No sólo porque la metodología de programación y resolución de problemas complejos por medio de esta técnica me apasiona, sino porque el hecho de intentar desarrollar una explicación sencilla, entendible y entretenida ha hecho que me documente en abundancia y refresque conceptos que tenía un poco oxidados. En el proceso he encontrado información interesante y celebridades relevantes que enmarcan y sitúan el concepto a lo largo de la historia, lo que creo que en este caso es tremendamente enriquecedor para dar una visión amplia de lo que es una técnica de computación avanzada y muy utilizada en nuestros días.

Remontándonos muy atrás podríamos decir que todo empieza con Charles R. Darwin y su teoría de la evolución. En su obra “El origen de las especies” publicada en 1859 basa la teoría de la evolución en el proceso de selección natural. Básicamente la teoría de la evolución biológica viene a decir que las especies cambian con el tiempo y van evolucionando para adaptarse al entorno que las rodea. Es una adaptación evolutiva basada en 3 principios fundamentales: Número de individuos limitado, la naturaleza evoluciona individuos de iguales propiedades y los individuos mas fuertes suelen prevalecer. La deficiencia de la teoría de Darwin es que no explicaba las razones intrínsecas de esta evolución. Años más tarde un monje Checoslovaco daría la clave que le faltaba a la teoría evolutiva, la transmisión cromosómica.

Gregor Mendel fue el padre de las leyes de la genética moderna y en 1886 publicó su artículo “Estudios sobre la hibridación de plantas”, dónde tras más de 28.000 ensayos con plantas de guisantes formuló tres leyes para demostrar las normas que regían la transferencia genética de “padres” a “hijos” y teorizó sobre la existencia de genes dominantes y recesivos. En la transmisión genética radicaba la clave de la selección y evolución natural que Darwin había descrito años antes.

Con el conocimiento de la teoría de la evolución y las normas sobre la transferencia evolutiva, en 1970 John Holland definió una estrategia de cálculo de búsqueda de soluciones óptimas basadas en las mismas normas en las que se basaba la selección natural. Con esta estrategia se desarrolló la técnica de cálculo evolutiva denominada como “Algoritmos genéticos”, donde una población inicial irá evolucionando con cálculos y variaciones que surgirán de cruces de los más aptos y mutaciones aleatorias. Todo esto orientado para la búsqueda de una solución que cumpla con el óptimo de un problema o con una solución dada por “aceptable”. 

Los algoritmos genéticos son una técnica muy rápida y robusta de encontrar soluciones óptimas o aceptables a un problema o función. Si bien puede que no encuentre siempre la solución óptima lo que está claro es que por su rapidez en los cálculos es una tipología de algoritmo muy extendida en los problemas que se resuelven por sistemas de cálculo combinatorio.

Los pasos básicos para la aplicación y cálculo mediante un algoritmo genético son los siguientes: Se parte de una población inicial de soluciones al problema, se seleccionan los mejores “individuos” (cálculos intermedios de mayor calidad), se recombinan para mejorar las posibles soluciones, a continuación, se introducen “mutaciones aleatorias” (reconfiguración numérica para mejorar o empeorar el resultado de manera más rápida) y los resultados se transmitirán a la siguiente generación. Estos pasos se repetirán hasta un número de iteraciones fijado o hasta que no haya un valor óptimo calculado mejor durante un número concreto de repeticiones y evoluciones.

La metodología de cálculo de los algoritmos genéticos utiliza lo que se denomina conceptualmente como los “operadores genéticos”: Selección, reproducción, cruce y mutación.

El concepto de selección es la generación aleatoria de una población inicial que puede representar una muestra aceptable de las posibles soluciones al problema de optimización buscado. Se intentará que la población inicial tenga una suficiente diversidad. Se aplicará una primera “evaluación” que dará los primeros valores o resultados de aptitud para saber la “bondad” inicial de los resultados que pueden evolucionar hasta encontrar el óptimo buscado.

Una vez elegidos estos elementos mejor posicionados en aptitud se aplicará el operador “reproducción” donde estos elementos se combinan imitando la descendencia directa y transmitiendo el valor a la siguiente generación. Es similar a la clonación de un individuo o a la transmisión cromosómica de padres a hijos.

La fase de cruce es donde se combinan o mezclan los individuos seleccionados en la fase anterior. No podría explicar en detalle esta fase sin complicar la explicación así resumiré que la etapa de cruce combina valores de diferentes padres de una manera que puedan dar lugar a unos hijos mejorados cualitativamente. Existen varias metodologías de cálculo para el cruce y se basan fundamentalmente en cómo realizar los cálculos de combinación de los “cromosomas” (unidades de las posibles soluciones).

Llegados a este punto se introduce una modificación aleatoria en el “cromosoma”, que es lo que se conoce como “mutación” para intentar alcanzar posibles soluciones del espectro de posibilidades que podrían no estar cubiertas en la selección de la población actual.

Cuando hemos cumplido con las fases de los operadores genéticos se seleccionan los mejores “individuos” (“soluciones del problema de optimización”) y se plantea la selección de la población de la siguiente generación.

Estos pasos se repetirán hasta que los criterios de convergencia o paro definidos por el usuario se cumplan.

Esta técnica es una de las herramientas de cálculo que se identifican dentro del “espectro” de las herramientas de la “inteligencia artificial”.

Como innumerables ejemplos más que nos rodean, a veces las mejores metodologías para resolver problemas complejos se basan en “imitar” a la madre naturaleza así que quizás debiéramos estar más atentos a los pequeños detalles de todo lo que está a nuestro alrededor. ¡Abramos los ojos!

Comentarios