Enrique J. Carmona: "O mundo dos Algoritmos Evolutivos goza de boa saúde, como así o testemumuña o gran volume de publicacións que aparecen cada ano"

16 de abril de 2021

O doutor Carmona Suárez Falou hoxe dos algoritmos evolutivos e as súas aplicacións. Este relatorio forma parte do Seminario de IA da UNED, e emítido desde o Centro de IA de Ourense, en cuxa páxina web poderá seguirse en diferido. Este seminario conta co apoio económico do Vicerreitorado de Investigación, Transferencia do Coñecemento e Divulgación Científica da UNED.

OURENSE, 16 de abril.-O 22 de marzo de 2006, a NASA enviaba por vez primeira ao espazo un hardware deseñado artificialmente. Tratábase dunha antena deseñada mediante técnicas evolutivas que operou con éxito durante todo o período da denominada misión Space Technology 5 (ST5). Aínda que pasaron uns anos desde aquel fito histórico, aínda segue estando vixente algunhas das conclusións realizadas polos propios desarrolladores da NASA daquela época e que están relacionadas coas vantaxes do deseño evolutivo fronte ao deseño convencional. En particular, a ausencia de rumbos de deseño tipicamente humanos que favorece a posibilidade de atopar deseños totalmente novos no campo e a necesidade de ciclos de deseño máis rápidos que implican custos de desenvolvemento menores. Posteriormente (2013-2014), unha nova misión, dedicada a obter información da atmosfera lunar, utilizaba tamén outras antenas obtidas evolutivamente.

O relator fixo un percorrido pola perspectiva histórica dos algoritmos evolutivos e así, xa en 1948, Turing propuxo o que denominou “procura xenética ou evolutiva” como un medio para dotar de intelixencia a unha máquina. Posteriormente, en 1962, Bremermann realizaba experimentos en “Optimización a partir de evolución e recombinación” implementados nunha computadora.

Con todo, é durante os anos 60 cando aparecen, en tres lugares diferentes, senllas implementacións do que hoxe en día coñecemos como Algoritmo Evolutivo:

Algoritmo Xenético: Holland (USA)
Programación Evolutiva: Fogel, Owens e Walsh (USA)
Estratexias Evolutivas: Rechenberg e Schwefel (Alemaña)

“Durante os 15 anos seguinte estas técnicas desenvolvéronse independentemente, pero desde principios dos 90 foron vistas como diferentes representacións (dialectos) dunha mesma disciplina que recibiu o nome de Computación Evolutiva (CE), actualmente, unha rama da intelixencia artificial que aborda problemas de optimización mediante inspiración biolóxica”, explica o doutor Carmona.

Finalmente, na década dos 90 emerxeron dúas novas variantes: en 1992, a denominada Programación Xenética, liderada por Koza (USA) e, algo máis tarde, en 1997, a denominada Evolución Diferencial, presentada por Storn e Price.

“A terminoloxía actual denota todos os algoritmos pertencentes á CE como algoritmos evolutivos (AE) e as cinco modalidades mencionadas anteriormente son consideradas como distintas variantes que se engloban baixo o paraugas da CE. Con todo, o mundo da CE non finaliza nestes cinco tipos de AEs. Existe un amplo repertorio de variantes de cada un deles e, ademais, abarca outras subramas como son o uso dos AES en problemas de optimización multiobxectivo ou en problemas de optimización con restricións, así como o estudo teórico da converxencia deste tipo de algoritmos, entre outras”, sinala o relator.

Enrique J. Carmona realizou unha introdución aos algoritmos evolutivos, englobándoos nun tipo de algoritmo máis amplos denominados metaheurísticas. Aínda que pode definirse unha heurística como un método de procura que fai uso da información do domino dun problema particular para utilizar “atallos” na procura da solución, unha metaheurística é un método de procura que é capaz de xeneralizar a operativa dunha heurística, facéndoa independente do dominio do problema e, por tanto, alcanzando a propiedade de poder ser usada nun repertorio moito máis amplo de problemas de optimización. É grande o repertorio de metaheurísticas que existe na actualidade, todas elas inspiradas en diferentes procesos naturais ou artificiais. Con todo, tamén é certo que actualmente hai un debate aberto sobre se as últimas metaheurísticas incorporadas á colección supoñen realmente novas achegas ao campo ou son diferentes metáforas nas que subxacen estratexias similares, pero expresadas cunha notación diferente.

En canto á comparación entre os AEs e os métodos clásicos, Carmona sinala que os primeiros son competitivos cando o uso destes últimos supón tempos de execución prohibitivos, debido a unha explosión combinatoria de posibles solucións no espazo de procura (imposible realizar unha procura exhaustiva); igualmente, naqueles casos en que os métodos clásicos son incapaces de dar unha solución, os AEs permiten obter unha solución que, aínda que non sexa a óptima, podería ser mellor que a obtida ata o momento para un problema dado ou que a que podería producir un humano.

Doutra banda, se comparamos os AEs con outras metaheurísticas, a principal vantaxe dos primeiros, comparados con aquelas metaheurísticas que fan uso dunha única solución, transformándoa en pasos sucesivos (metaheurísticas baseadas en traxectoria), é que a procura da solución nos AEs está baseada en poboación, o que diminúe a posibilidade destes queden atrapados nun óptimo local. Con todo, tamén existen outro tipo de metaheurísticas, como as baseadas en intelixencia de enxame, que fan uso deste tipo de procura. Pola contra, o inconveniente das metaheurísticas que fan uso de procura baseada en poboación é un maior custo computacional. Con todo, isto último pode paliarse paralelizando a execución do algoritmo. Adicionalmente, a existencia dunha gran variedade de AEs facilita o uso da variante máis adecuada en función das características do problema para resolver.

Existe un amplo repertorio de problemas onde os AEs poden ser competitivos:

problemas nos que se quere optimizar tanto os parámetros dun modelo como naqueloutros onde se require a optimización do propio modelo e os seus parámetros simultaneamente
problemas de optimización tanto en espazos discretos/continuos
problemas de optimización multiobjetivo
problemas de optimización con restricións

Carmona indica que dous mecanismos forman a base dos sistemas evolutivos:

Os operadores de variación (recombinación e mutación), que tenden a aumentar a variedade xenética da poboación e, por tanto, permiten crear a diversidade necesaria para poder alcanzar a solución a partir dunha poboación inicial obtida aleatoriamente. Dise que este tipo de operadores favorecen a EXPLORACIÓN do espazo de procura
O proceso de selección de sobreviventes, que tende a diminuír a variedade xenética, pero actúa como unha forza que empuxa a converxencia cara a unha solución.

Dise que este mecanismo favorece a EXPLOTACIÓN do espazo de procura.

Outra propiedade importante os AEs é a súa natureza estocástica, é dicir, non son deterministas. Isto implica que o subseguinte estado do sistema está determinado tanto polas accións predicibles do proceso como por mecanismos aleatorios. Esta aleatoriedade maniféstase principalmente na toma de decisións probabilista que subxace na operativa dos operadores de variación. A principal consecuencia desta propiedade tradúcese en que a execución dun mesmo AE, configurado cos mesmos valores de parámetros, non ten por que dar resultados idénticos.

Ao estudar a evolución da poboación nunha AE, ao comezo, os individuos están espallados aleatoriamente sobre todo o espazo de procura. Despois dunhas poucas xeracións, os individuos da poboación abandonan as rexións de alto valor de adaptación e empezan a “descender ós outeiros”, asumindo un problema de minimización. Durante as xeracións intermedias, o mecanismo de exploración do AE visitará diferentes rexións do espazo de procura, seleccionando aqueles vales máis prometedores. Próximos ao final do proceso de procura, toda a poboación estará concentrada ao redor de poucos vales. Entón, algún deles debería corresponder ao val do óptimo global, onde o mecanismo de explotación do AE acabará atopando finalmente a mellor solución. Con todo, é posible que a poboación non chegue a explorar o “val adecuado”, quedando así os individuos atrapados en óptimos locais. Normalmente, as causas de quedar atrapado nun óptimo local poden ser debidas a unha mala configuración do AE ou a unha mala elección do tipo de AE utilizado para resolver o problema.

O profesor Carmona sinala que, en todo problema de optimización abordado mediante un AE, hai dous puntos crave:

como representar as solucións potenciais (individuos) e como avaliar o grao de bondade de cada unha delas. No primeiro caso, tamén hai que establecer o procedemento que nos permita pasar da representación no espazo de procura (representación xenotípica) á representación pertencente ao dominio do problema (representación fenotípica). Con relación a como avaliar cada posible solución, hai que definir unha función matemática, denominada función de avaliación ou función fitness, que nos permita medir obxectivamente como de boa é unha solución e, adicionalmente, nos permita comparar o grao de adaptación das diferentes solucións contidas na poboación actual. Por exemplo, se se quixese atopar o máximo da función potencia ao cadrado nun intervalo dos números enteiros, poderiamos, por exemplo, representar cada individuo por unha cadea binaria (xenotipo); a forma de decodificar cada individuo podería consistir entón en transformar o número binario no seu correspondente número expresado en base 10 (fenotipo); e, finalmente, a forma de avaliar o devandito individuo podería ser a de calcular o cadrado do seu valor fenotípico. Por exemplo, o individuo representado pola cadea binaria 10010, se decodificaría como o enteiro,18 e o valor de adaptación do devandito individuo sería 18x18=324”.

A curva que mostra a evolución do mellor individuo da poboación ao longo do tempo ten unha forma característica: rápido progreso ao principio, un progreso moderado ao longo do que podería denominarse fase intermedia, e a tendencia a unha asíntota nas xeracións finais. Durante a primeira fase predomina a exploración do espazo de procura e, durante a última, a explotación das rexións máis prometedoras. O éxito da execución dependerá en gran medida do equilibrio entre exploración e explotación levado a cabo durante a fase intermedia.

Algoritmos anytime

Tamén a curva de progreso dun AE revela unha característica interesante: a de permitir obter unha solución durante calquera instante do proceso de execución (algoritmos anytime). Este comportamento é oposto ao doutro tipo de algoritmos que necesitan a realización dun número de pasos fixos antes de poder proporcionar unha solución. O nome “anytime” vén da propiedade de que a procura pode ser parada en calquera momento e o algoritmo sempre producirá algunha solución, aínda que sexa subóptima. Con todo, esta propiedade pode ser interesante naqueles casos en que se dispoña de pouco tempo para poder obter unha solución, de tal maneira que, aínda que a solución proporcionada non sexa óptima, pode ser mellor á obtida por calquera outro método ou polo propio humano.

O relator estableceu algunhas pautas para determinar como elixir un tipo de AE en función das características do problema abordado. Igualmente, para exemplificar a mecánica deste tipo de algoritmos, presentou un exemplo de uso do paradigma baseado en programación xenética aplicado ao problema da regresión simbólica.

Outro punto curioso presentado polo doutor Carmona é a competición que todos os anos, desde 2004, celébrase anualmente na Conferencia sobre Computación Xenética e Evolutiva (GECCO polo seu acrónimo en inglés). Trátase dun certame de premios pagos en efectivo, denominados "Humies", que se conceden a aqueles resultados que foron producidos por calquera forma de computación evolutiva e que resultan ser competitivos cos que puidese producir un humano. En particular, o concepto de "competitividade humana" foi definido por John Koza, o pai da programación xenética, quen estableceu que un resultado creado automaticamente considérase "competitivo humano" se satisfai polo menos un dos oito criterios existentes.

A última parte da presentación estivo dedicada a algunhas das aplicacións dos AEs levadas a cabo en diferentes traballos e proxectos de investigación realizados no Departamento de Intelixencia Artificial da UNED e, máis concretamente, no seo do grupo SIMDA. Os dominios de aplicación abarcan campos tan diversos como as Matemáticas, a Electrónica, a Medicina e a Industria. O relator resumiu así os diferentes pasos a seguir para abordar un problema mediante computación evolutiva:

Definir o problema orixinal
Transformar o problema orixinal nun problema de optimización
Establecer como codificar e decodificar as solucións
Definir como avaliar as solucións (función fitness)
Seleccionar o tipo de AE e sintonizar adecuadamente a súa configuración

Concretamente, no caso das Matemáticas, mostrouse como abordar o problema da resolución de ecuacións diferenciais, incluíndo tanto ecuacións diferenciais lineais como non lineais, sistemas de ecuacións diferenciais e ecuacións diferenciais en derivadas parciais. En Electrónica, exemplificouse o uso dos AEs para abordar o problema do deseño automático de circuítos electrónicos analóxicos. En Medicina, os AEs foron utilizados para a detección de estruturas anatómicas en imaxes de fondo de ollo. E, finalmente, no caso da Industria, para aplicacións tales como a optimización da eficiencia enerxética dunha turbina de gas aeronáutica ou para a optimización de diagramas de fluxo de instalacións de canteiras.

Para finalizar, Enrique J. Carmona explica que, a pesar de que os algoritmos son os AEs máis coñecidos, hai vida máis aló deste tipo concreto de algoritmos, dado o amplo repertorio de AEs existentes. Adicionalmente, hai que ter en conta que non todos os problemas de optimización resólvense mediante AEs. Así, nalgúns casos, poden existir métodos clásicos que resolvan o problema de maneira óptima. En caso contrario, os AEs si deberían ser tidos en conta naqueles problemas de optimización onde a dimensionalidade e o número de óptimos locais é alto, o número de obxectivos a optimizar é maior de dous (problemas multiobxectivo) e cando o problema de optimización está suxeito a un número elevado de restricións. Estes últimos problemas mencionados forman parte do mundo real e aparecen frecuentemente no ámbito da enxeñería.

Con todo, o uso de AEs para problemas reais representa un elevado custo computacional (tanto na execución do AE como no proceso de configuración dos seus parámetros). Con todo, “co incremento da potencia de cómputo, isto debería ser hoxe en día un problema cada vez menor, máxime se, ademais, pola súa propia natureza, os AEs son facilmente paralelizables”. No caso do deseño industrial, o uso deste tipo de algoritmos adoita requirir de potentes simuladores para poder avaliar automaticamente as diferentes solucións propostas ao longo do proceso evolutivo. Adicionalmente, nalgúns casos, requírese a necesidade de poder explicar o deseño obtido evolutivamente, imprescindible para ser aceptado e usado industrialmente, tal e como podería requirir, por exemplo, coa proposta dun novo circuíto electrónico obtido evolutivamente.

En calquera caso, a pesar dos seus inconvenientes e grazas ás súas vantaxes, o mundo dos AEs, en particular, e o das metaheurísticas, en xeral, gozan de moi boa saúde, tal e como así a testemuña o gran volume de publicacións que cada ano aparecen ao redor deste tipo de algoritmos.

Podes ver o relatorio aquí.