No campo da inteligência artificial, um algoritmo evolucionário (EA) é um subconjunto de cálculos populacionais totais baseados em otimização metaheurística. A EA usa mecanismos inspirados no desenvolvimento biológico, como reprodução, mutação, recombinação e seleção. A solução candidata no problema de algoritmos de otimização evolutiva desempenha o papel de indivíduos na população. E também a função fitness determina a qualidade das respostas.
Algoritmos evolucionários geralmente aproximam bem as soluções para todos os tipos de problemas. Porque, idealmente, eles não fazem suposições sobre o cenário de condicionamento físico subjacente. Os métodos utilizados para modelagem evolutiva e algoritmos genéticos são geralmente limitados a estudos de processos microevolutivos e modelos de planejamento baseados em estágios celulares. Na maioria das aplicações reais de EA, a complexidade computacional é um fator proibitivo.
Na verdadeesse problema está relacionado à estimativa da função de aptidão. A aproximação da aptidão é uma solução para superar essa dificuldade. No entanto, um EA aparentemente simples pode resolver problemas muitas vezes complexos. Portanto, não pode haver relação direta entre a complexidade da sequência e o problema. Mais detalhes podem ser encontrados nos livros "Algoritmos Evolucionários".
Implementação
O primeiro passo é criar uma população inicial de indivíduos aleatoriamente.
O segundo passo é avaliar a adequação de cada indivíduo neste grupo (limite de tempo, preparação suficiente, etc.).
Etapa três - repita as seguintes etapas de regeneração até a conclusão:
- Selecione as pessoas mais adequadas para reprodução (pais).
- Traga novos indivíduos que passaram pelo algoritmo evolutivo usando cruzamento e mutação para gerar descendentes.
- Avalie a aptidão individual de novas pessoas.
- Substitua a população menos apta por eles.
Tipos
Algoritmo Genético é uma sequência evolutiva, o tipo mais popular de Expert Advisor. Procura-se uma solução para o problema na forma de cadeias de números (tradicionalmente binários, embora as melhores representações sejam geralmente aquelas que refletem mais no problema a ser resolvido) aplicando operadores como recombinação e mutação (às vezes um, em alguns casos ambos). Este tipo de Expert Advisor é frequentemente usado em problemas de otimização. Outro nome para isso é fetura (do latim para "nascimento"):
- Programação genética. Apresenta soluções como códigos de computador, e sua adequação é determinada por sua capacidade de realizar tarefas computacionais.
- Programação evolutiva. Semelhante ao algoritmo genético evolutivo, mas a estrutura é fixa e seus parâmetros numéricos podem mudar.
- Programação da expressão gênica. Desenvolve aplicativos de computador, mas explora o sistema genótipo-fenótipo, onde projetos de diferentes tamanhos são codificados em cromossomos lineares de comprimento fixo.
- Estratégia. Trabalha com vetores de números reais como representações de soluções. Geralmente usa algoritmos de taxa de mutação evolutiva autoadaptáveis.
- Desenvolvimento diferencial. Baseado em diferenças vetoriais e, portanto, principalmente adequado para problemas de otimização numérica.
- Neuroevolução. Semelhante à programação evolutiva e algoritmos genéticos. Mas as últimas são redes neurais artificiais, que descrevem a estrutura e o peso das conexões. A codificação do genoma pode ser direta ou indireta.
Comparação com processos biológicos
Uma possível limitação de muitos algoritmos evolutivos é a f alta de uma distinção clara entre genótipo e fenótipo. Na natureza, um óvulo fertilizado passa por um processo complexo conhecido como embriogênese para se tornar maduro. Acredita-se que essa codificação indireta torne as pesquisas genéticas mais confiáveis (ou seja, menos propensas a causar mutações fatais) e também pode melhorar a capacidade de desenvolvimento do organismo. Tais indiretas (em outras palavras,codificações generativas ou de desenvolvimento) também permitem que a evolução explore a regularidade no ambiente.
Trabalhos recentes em embriogênese artificial ou sistemas de desenvolvimento procuram abordar essas questões. Ao programar a expressão gênica, a região genótipo-fenótipo é explorada com sucesso, onde a primeira consiste em cromossomos multigênicos lineares de comprimento fixo, e a segunda de muitas árvores de expressão ou programas de computador de vários tamanhos e formas.
Técnicas relacionadas
Algoritmos incluem:
- Otimização de colônias de formigas. Baseia-se na ideia de que os insetos procuram comida conectando-se com feromônios para formar caminhos. Principalmente adequado para otimização combinatória e problemas de grafos.
- Algoritmo do controle deslizante raiz. O criador se inspirou na função das raízes das plantas na natureza.
- Algoritmo para colônias artificiais de abelhas. Baseado no comportamento das abelhas. É proposto principalmente para otimização numérica e estendido para resolver problemas combinatórios, limitados e multiobjetivos. O algoritmo das abelhas é baseado no comportamento de forrageamento dos insetos. Ele tem sido aplicado em muitas aplicações, como roteamento e agendamento.
- Otimização de enxame de partículas - com base em ideias de comportamento de rebanho de animais. E também principalmente adequado para tarefas de processo numérico.
Outros métodos metaheurísticos populares
- Busca de caça. Um método baseado na captura em grupo de determinados animais, como lobos, por exemplo, quedistribuir seus deveres para cercar a presa. Cada um dos membros do algoritmo evolucionário se relaciona com os outros de alguma forma. Isto é especialmente verdadeiro para o líder. Este é um método de otimização contínua adaptado como um método de processo combinatório.
- Pesquisa por medidas. Ao contrário dos métodos metaheurísticos baseados na natureza, o algoritmo de processo adaptativo não usa a metáfora como seu princípio principal. Em vez disso, ele usa um método simples orientado ao desempenho com base na atualização do parâmetro de proporção de dimensão de pesquisa em cada iteração. O algoritmo Firefly é inspirado em como os vaga-lumes se atraem com sua luz intermitente. Isso é especialmente útil para otimização multimodal.
- Busca pela harmonia. Baseado nas ideias do comportamento dos músicos. Nesse caso, os algoritmos evolucionários são o caminho para a otimização combinatória.
- Adaptação gaussiana. Baseado na teoria da informação. Usado para maximizar o desempenho e a disponibilidade média. Um exemplo de algoritmos evolutivos nesta situação: entropia em termodinâmica e teoria da informação.
Memética
Um método híbrido baseado na ideia de meme de Richard Dawkins. Geralmente assume a forma de um algoritmo baseado em população combinado com procedimentos de aprendizado individual capazes de realizar refinamentos locais. Enfatiza o uso de conhecimento específico do problema e tenta organizar pesquisas globais e refinadas de maneira sinérgica.
Evolutivoalgoritmos são uma abordagem heurística para problemas que não podem ser facilmente resolvidos em tempo polinomial, como problemas classicamente NP-difíceis e qualquer outra coisa que levaria muito tempo para processar exaustivamente. Quando usados de forma independente, geralmente são usados para problemas combinatórios. No entanto, os algoritmos genéticos são frequentemente usados em conjunto com outros métodos, agindo como uma maneira rápida de encontrar vários pontos de partida ideais para trabalhar.
A premissa do algoritmo evolutivo (conhecido como conselheiro) é bastante simples, já que você está familiarizado com o processo de seleção natural. Ele contém quatro etapas principais:
- inicialização;
- escolha;
- operadores genéticos;
- fim.
Cada uma dessas etapas corresponde aproximadamente a um certo aspecto da seleção natural e fornece maneiras fáceis de modularizar essa categoria de algoritmos. Simplificando, na EA, os membros mais aptos sobreviverão e se reproduzirão, enquanto os membros menos aptos morrerão e não contribuirão para o pool genético da próxima geração.
Inicialização
Para iniciar o algoritmo, você deve primeiro criar um conjunto de soluções. A população conterá um número arbitrário de possíveis declarações de problemas, geralmente chamadas de membros. Eles geralmente são gerados aleatoriamente (dentro das restrições da tarefa) ou, se algum conhecimento prévio for conhecido, centrados provisoriamente em torno do que é considerado ideal. É importante que a população abranja uma vasta gama de soluções,porque é essencialmente um pool genético. Portanto, se alguém quiser explorar muitas possibilidades diferentes dentro de um algoritmo, deve se esforçar para ter muitos genes diferentes.
Escolha
Uma vez criada a população, seus membros devem agora ser avaliados de acordo com a função de aptidão. A função de aptidão pega as características de um membro e fornece uma representação numérica de quão adequado é o membro. Criando-os muitas vezes pode ser muito difícil. É importante encontrar um bom sistema que represente com precisão os dados. Isso é muito específico para o problema. Agora é necessário calcular a adequação de todos os participantes e selecionar alguns dos melhores membros.
Funções de objetivo múltiplo
EAs também podem ser estendidos para usar esses sistemas. Isso complica um pouco o processo, pois ao invés de identificar um ponto ótimo, obtém-se um conjunto ao utilizá-los. O conjunto de soluções é chamado de fronteira de Pareto e contém elementos que são igualmente adequados no sentido de que nenhuma delas domina a outra.
Operadores genéticos
Esta etapa inclui duas subetapas: cruzamento e mutação. Depois de selecionar os melhores termos (geralmente os 2 primeiros, mas esse número pode variar), eles agora são usados para criar a próxima geração no algoritmo. Ao aplicar as características dos pais escolhidos, são criados novos filhos que são uma mistura de qualidades. Isso muitas vezes pode ser difícil dependendo do tipo de dados, mas geralmente em problemas combinatóriosé bem possível misturar e produzir combinações válidas.
Agora é preciso introduzir novo material genético na geração. Se esse passo importante não for dado, o cientista ficará rapidamente preso em extremos locais e não obterá os melhores resultados. Este passo é uma mutação, e é feito de forma bastante simples, alterando uma pequena parte dos filhos de tal forma que eles não refletem predominantemente subconjuntos dos genes dos pais. A mutação geralmente ocorre de forma probabilística, uma vez que a probabilidade de uma criança obtê-la, bem como sua gravidade, é determinada pela distribuição.
Rescisão
No final, o algoritmo deve terminar. Isso geralmente acontece em dois casos: ou atingiu algum tempo máximo de execução ou atingiu um limite de desempenho. Neste ponto, a solução final é selecionada e retornada.
Exemplo de algoritmos evolutivos
Agora, para ilustrar o resultado desse processo, você precisa ver o conselheiro em ação. Para isso, podemos relembrar como várias gerações de dinossauros aprenderam a andar (aos poucos dominando a terra), otimizando a estrutura de seu corpo e aplicando força muscular. Mesmo que os répteis da primeira geração não pudessem andar, o conselheiro foi capaz de evoluí-los ao longo do tempo através de mutação e cruzamento para uma forma que pudesse andar.
Esses algoritmos estão se tornando cada vez mais relevantes no mundo moderno, pois as soluções baseadas neles são cada vez mais utilizadas em setores como marketing digital, finanças esaúde.
Onde os EAs são usados?
Mais amplamente, os algoritmos evolucionários são usados em uma ampla variedade de aplicações, como processamento de imagens, roteamento de veículos, otimização de comunicações móveis, desenvolvimento de software e até mesmo treinamento de redes neurais artificiais. Essas ferramentas estão no centro de muitos dos aplicativos e sites que as pessoas usam diariamente, incluindo o Google Maps e até jogos como The Sims. Além disso, a área médica usa a EA para ajudar a tomar decisões clínicas em relação ao tratamento do câncer. Na verdade, os algoritmos evolucionários são tão robustos que podem ser usados para resolver praticamente qualquer problema de otimização.
Lei de Moore
A crescente prevalência de EO é impulsionada por dois fatores principais: poder de computação disponível e acúmulo de grandes conjuntos de dados. A primeira pode ser descrita pela Lei de Moore, que essencialmente afirma que a quantidade de poder computacional em um computador dobra aproximadamente a cada dois anos. Essa previsão se manteve por décadas. O segundo fator está relacionado à crescente dependência da tecnologia, que permite que as instituições coletem uma quantidade incrivelmente grande de dados, o que lhes permite analisar tendências e otimizar produtos.
Como os algoritmos evolutivos podem ajudar os profissionais de marketing?
As condições de mercado estão mudando rapidamente e muito competitivas. Isso forçou os gerentes de marketing a competir por uma melhor tomada de decisão. Aumento na disponibilidadeo poder da computação levou os trabalhadores a usar o EA para resolver problemas.
Otimização de conversão
Um dos principais objetivos é aumentar a taxa de visitantes do site. Esse problema se resume a otimizar o número de usuários que fazem o que o profissional de marketing deseja. Por exemplo, se uma empresa vende notebooks, o ideal é aumentar o número de visitantes do site que acabam comprando o produto. Essa é a essência da otimização da taxa de conversão.
Um dos aspectos surpreendentemente importantes é a escolha da interface do usuário. Se o web design não for muito amigável, há quem acabe não comprando o produto por um motivo ou outro. O objetivo então é reduzir o número de usuários que acabam não convertendo, o que aumenta o lucro geral.
