Inteligência artificial. Algoritmo Genético e Suas Aplicações

„Não é o mais forte ou o mais inteligente que sobrevive, mas aquele que melhor se adapta às mudanças. “
Charles Darwin

“Mesmo se uma em cada mil leituras se interessar por esses algoritmos e decidir se aprofundar, isso é ótimo. “

Atenção, a pergunta: você se lembra das forças motrizes da evolução de acordo com Darwin? Esse conhecimento é necessário para entender como o algoritmo genético funciona, pois ele tenta imitar os processos que realmente ocorrem na natureza. Portanto, o principal pré-requisito para a evolução é a variabilidade hereditária e suas forças motrizes são a luta pela existência e a seleção natural. Usando um algoritmo genético, você essencialmente age como um criador e você mesmo estabelece as leis da evolução que permitem que você atinja a otimização da população. Idealmente, as qualidades necessárias para a sobrevivência e adaptação devem ser desenvolvidas, que será a solução desejada. Vamos ver como esses princípios são implementados no algoritmo genético.

⇡#O que é?

O algoritmo genético (AG) é um algoritmo de busca e otimização baseado no princípio biológico da seleção natural.

⇡#Como ele trabalha?

O primeiro passo é criar uma população. Nesse caso, uma população não é um conjunto de indivíduos biológicos, mas um conjunto de soluções possíveis para o problema existente, que constituem uma busca espacial.

A segunda etapa é calcular a função de aptidão. Esta função aceita uma solução potencial para o problema (solução candidata) na entrada e produz um valor que avalia sua adequação. No caso do algoritmo genético clássico, a função objetivo e a função de adequação são uma e a mesma. A seguir, vamos verificar se a condição para interromper o algoritmo foi satisfeita. O algoritmo interromperá a execução se o valor ideal esperado for alcançado, se o valor obtido não melhorar mais ou após o tempo / número de iterações especificado ter decorrido. Depois de parar, o cromossomo mais adaptado é selecionado (de acordo com o valor de função mais alto). Se a condição de parada não for atendida, de acordo com os resultados da seleção natural, a seleção de cromossomos será feita para a produção de descendentes.

O terceiro estágio é o cruzamento (em fontes russas – “cruzamento”, menos frequentemente “cruzamento”) e mutação.

Fluxograma do algoritmo genético

Cruzamento, mutação e seleção são operadores genéticos. Como na natureza, a probabilidade de cruzamento é várias ordens de magnitude maior do que a probabilidade de mutação. O cruzamento mantém uma diversidade infinita na população, é a redistribuição do material genético dos pais, graças ao qual novas combinações de genes aparecem na prole. Mas de que tipo de “genes” e “cromossomos” podemos falar fora do contexto da natureza viva? No algoritmo genético, “cromossomo” é um conjunto de parâmetros que determinam a possível solução proposta, e “gene” é uma das “letras” da string “cromossomo”, geralmente possuindo um valor binário. Como lembramos, como resultado da seleção, os cromossomos mais adaptados são selecionados – esses operadores genéticos são aplicados a eles. Provavelmente, você agora está pensando como o cruzamento desses “cromossomos” pode ocorrer. Vários cenários são possíveis,

Cruzamento de ponto único: há um par de cromossomos parentais com um conjunto de genes L, para eles o chamado ponto de cruzamento Px é selecionado aleatoriamente – esta é uma determinada posição do gene no cromossomo. K [1; Px] de um cromossomo parental junta-se [Px + 1; L] é diferente, e o primeiro filho é obtido. A segunda descendência também é obtida por cruzamento, mas “na direção oposta”.

Crossover de um ponto

Cruzamento de dois pontos: uma troca de material genético (ou seja, bits) ocorre em dois pontos de cruzamento.

Krgossingover de dois pontos

Crossover uniforme: O valor de cada bit no cromossomo da criança é determinado de acordo com uma máscara de crossover gerada aleatoriamente. Se a máscara contém 0 – o gene do primeiro pai é retirado, se 1 – do segundo.

Cruzamento uniforme

Para um mergulho mais profundo no tópico de algoritmos evolutivos, recomendamos estudar o artigo de F. Herrera, M. Losano, AMSanches Hybrid Crossover Operators for Real-Coded Genetic Algorithms: An Experimental Study.

Mutação é um operador genético que, com alguma probabilidade, altera um ou mais “genes” em posições aleatórias do “cromossomo”. Para que serve? Por que as mutações (mudanças no código genético) existem na natureza, elas podem contribuir para uma melhor sobrevivência da espécie? Este artigo não é sobre genética, mas não esqueçamos que foi ela quem serviu de inspiração para Holland, criador do algoritmo genético (1975). A prole que foi exposta a operadores genéticos forma uma nova população – e a próxima iteração de GA começa nela. A função de aptidão é calculada novamente, a seleção natural ocorre e então o algoritmo para se a condição dada for satisfeita ou novamente muda para a seleção. Se você quiser ver um aplicativo interessante, você pode ler a análise do problema do caixeiro viajante e do problema da mochila usando o GA. Ambos os problemas são problemas de otimização combinatória, ou seja, em um conjunto finito de objetos, estamos procurando o ótimo. Sem saber, resolvemos problemas semelhantes todos os dias. Agora vamos examinar as vantagens e desvantagens desse método.

Prós do GA

Este algoritmo tem pontos fortes únicos:

• Oferece várias soluções para escolher, não apenas uma;
• Explora vários pontos ao mesmo tempo, e não um após o outro, devido aos quais a função objetivo não se apóia em um extremo local;
• A otimização ocorre continuamente sob mudanças nas condições ambientais, e a população tem que se adaptar;
• Pode oferecer uma solução satisfatória para o problema NP-difícil;
• Permite computação paralela;
• Adequado para resolver problemas com uma grande variedade de parâmetros (o principal é definir uma função de fitness adequada).

Contras do GA

• «Apenas uma boa decisão ”- às vezes isso também é uma desvantagem;
• Muitos pontos no espaço de busca às vezes também são uma desvantagem;
• Nem sempre é conveniente representar o problema em termos de genes e cromossomos.

⇡#Para quais tarefas o GA é usado?

O GA é usado para resolver uma série de problemas: desde o desenvolvimento de antenas da NASA até programas de reconhecimento de estrutura de proteínas.

Em finanças, o GA é usado com sucesso para modelar agentes econômicos com comportamento racionalmente limitado: previsões financeiras, investimentos, etc. Uma das tarefas interessantes é a otimização de portfólio. Na teoria dos jogos, o AG é usado, por exemplo, para resolver o dilema do prisioneiro. Pode ser usado em jogos de dois jogadores para otimizar estratégias.

Na robótica, o GA é perfeitamente utilizado para controlar um robô humanoide, otimizar o planejamento de rotas (roteamento). Na aviação – para o sistema de controle de vôo. Por falar em aviação, cientistas da General Electric e do Rensselaer Polytechnic Institute usaram o GA para projetar a turbina de um motor a jato, que é usado em aviões modernos.

Você também pode usar o GA em situações mais próximas de nós, por exemplo, para planejar uma programação em uma instalação de produção ou em uma grande instituição de ensino. No primeiro caso, a função de adequação pode definir o número de peças produzidas em um determinado período de tempo e, no segundo, pode “penalizar” ramificações de cronograma conflitantes. As possibilidades de criatividade são simplesmente infinitas.

Qual é o próximo? O leitor que quiser saber mais pode consultar os materiais da conferência GECCO – esta é uma conferência que é dedicada à programação evolucionária, onde estão as notícias e atualizações mais quentes. O lado matemático é bem descrito aqui:

Https://loginom.ru/blog/ga-math

Mais sobre aplicativos GA em inglês:

Recentemente, um livro que chama a atenção foi lançado: Buontempo, Frances. Algoritmos genéticos e aprendizado de máquina para programadores: crie modelos de IA e desenvolva soluções. Pragmatic Bookshelf, 2019.

Materiais usados ​​para escrever este artigo:

• Diagrama de blocos: intuit.ru
• Diagramas de cruzamento: geeksforgeeks.org