Algoritmos Genéticos: Busca e Otimização por Seleção Natural

O que são algoritmos genéticos?

Nos últimos anos, houve um grande burburinho em torno da Inteligência Artificial (IA). Grandes empresas como Google, Apple e Microsoft estão trabalhando ativamente no assunto. Na verdade, a IA é um guarda-chuva que abrange muitos objetivos, abordagens, ferramentas e aplicativos. Algoritmos Genéticos (AG) é apenas uma das ferramentas para busca inteligente através de muitas soluções possíveis.

GA é uma técnica de busca e otimização metaheurística baseada em princípios presentes na evolução natural. Pertence a uma classe maior de algoritmos evolucionários.

O AG mantém uma população de cromossomos — um conjunto de soluções potenciais para o problema. A ideia é que a “evolução” encontre uma solução ótima para o problema após várias gerações sucessivas – semelhante à seleção natural.

O AG imita três processos evolutivos: seleção, cruzamento de genes e mutação.

Semelhante à seleção natural, o conceito central da seleção do AG é a adequação. Os cromossomos que são mais aptos têm uma melhor chance de sobrevivência. Fitness é uma função que mede a qualidade da solução representada pelo cromossomo. Em essência, cada cromossomo dentro da população representa os parâmetros de entrada. Por exemplo, se o seu problema contém dois parâmetros de entrada, como preço e volume na negociação, cada cromossomo consistirá logicamente em dois elementos. Como os elementos são codificados dentro do cromossomo é um tópico diferente.

Durante a seleção, os cromossomos formam pares de pais para reprodução . Cada criança recebe características de seus pais. Basicamente, a criança representa uma recombinação de características de seus pais: algumas das características são tiradas de um dos pais e outras de outro. Além da recombinação, algumas das características podem sofrer mutações .

Como os cromossomos mais aptos produzem mais filhos, cada geração subsequente terá melhor aptidão. Em algum momento, uma geração conterá um cromossomo que representará uma solução suficientemente boa para nosso problema.

GA é poderoso e amplamente aplicável para problemas complexos. Existe uma grande classe de problemas de otimização que são bastante difíceis de resolver por técnicas convencionais de otimização. Algoritmos genéticos são algoritmos eficientes cuja solução é aproximadamente ótima. As aplicações mais conhecidas incluem agendamento, transporte, roteamento, tecnologias de grupo, design de layout, treinamento de rede neural e muitos outros.

Colocando as coisas em prática

O exemplo que veremos pode ser considerado o “Hello World” do GA. Este exemplo foi dado inicialmente por J. Freeman em Simulating Neural Networks with Mathematica . Eu tirei isso de Algoritmos Genéticos e Design de Engenharia de Mitsuo Gen e Runwei Cheng.

O problema de correspondência de palavras tenta evoluir uma expressão com um algoritmo genético. Inicialmente, o algoritmo deve “adivinhar” a frase “ser ou não ser” a partir de listas de letras geradas aleatoriamente.

Como há 26 letras possíveis para cada uma das 13 localizações [excluindo os espaços em branco] na lista, a probabilidade de obtermos a frase correta de maneira puramente aleatória é (1/26)^13=4,03038×10-19, que é aproximadamente duas chances em um [quintilhões] (Gen & Chong, 1997).

Vamos definir o problema um pouco mais amplamente aqui, tornando a solução ainda mais difícil. Vamos supor que não estamos limitados ao idioma inglês ou a uma frase específica. Podemos acabar lidando com qualquer alfabeto, ou mesmo com qualquer conjunto de símbolos. Não temos conhecimento da língua. Nós nem sabemos se existe alguma linguagem.

Digamos que nosso oponente pensou em uma frase arbitrária, incluindo espaços em branco. Sabemos o comprimento da frase e a contagem de símbolos no alfabeto. Esse é o único conhecimento que temos. Após cada palpite, nosso oponente nos diz quantas letras estão no lugar.

Cada cromossomo é uma sequência de índices dos símbolos do alfabeto. Se estivermos falando sobre o alfabeto inglês, então 'a' será representado por 0, 'b' por 1, 'c' por 2 e assim por diante. Assim, por exemplo, a palavra “ser” será representada como [4, 1] .

Demonstraremos todas as etapas por meio de trechos de código Java, mas o conhecimento de Java não é necessário para entender cada etapa.

Núcleo do Algoritmo Genético

Podemos começar com uma implementação geral do algoritmo genético:

 public void find() { // Initialization List<T> population = Stream.generate(supplier) .limit(populationSize) .collect(toList()); // Iteration while (!termination.test(population)) { // Selection population = selection(population); // Crossover crossover(population); // Mutation mutation(population); } }

Este é o conjunto simples de etapas que cada GA consiste mais ou menos. Na etapa de inicialização, geramos uma população inicial de frases. O tamanho da população é determinado por populationSize . A forma como a frase é gerada depende da implementação do supplier .

Dentro da etapa de iteração, evoluímos a população até que as condições de término sejam atendidas no teste do laço while . As condições de terminação podem incluir tanto o número de gerações quanto a correspondência exata de uma das frases na população. A termination encapsula uma implementação exata.

Dentro de cada iteração, realizamos as etapas típicas do GA:

1. Realize uma seleção sobre a população com base na aptidão cromossômica.
2. Produza uma nova “geração” através da operação de crossover.
3. Faça uma recombinação de algumas letras em algumas frases.

O núcleo do algoritmo é muito simples e independente de domínio. Será o mesmo para todos os problemas. O que você precisará ajustar é a implementação de operadores genéticos. A seguir, examinaremos de perto cada um dos operadores GA mencionados anteriormente.

Seleção

Como já sabemos, a seleção é um processo de encontrar sucessores para os cromossomos atuais – os cromossomos mais adequados ao nosso problema. Durante a seleção, precisamos garantir que os cromossomos com melhor aptidão tenham maior chance de sobrevivência.

 private List<T> selection(List<T> population) { final double[] fitnesses = population.stream() .mapToDouble(fitness) .toArray(); final double totalFitness = DoubleStream.of(fitnesses).sum(); double sum = 0; final double[] probabilities = new double[fitnesses.length]; for (int i = 0; i < fitnesses.length; i++) { sum += fitnesses[i] / totalFitness; probabilities[i] = sum; } probabilities[probabilities.length - 1] = 1; return range(0, probabilities.length).mapToObj(i -> { int index = binarySearch(probabilities, random()); if (index < 0) { index = -(index + 1); } return population.get(index); }).collect(toList()); }

A ideia por trás desta implementação é a seguinte: A população é representada como intervalos consequentes no eixo numérico. Toda a população está entre 0 e 1.

O pedaço do intervalo que um cromossomo leva é proporcional à sua aptidão. Isso resulta em um cromossomo mais apto recebendo um pedaço maior. Em seguida, espiamos aleatoriamente um número entre 0 e 1 e encontramos um intervalo que inclui o número. Obviamente, faixas maiores têm maiores chances de serem selecionadas e, portanto, cromossomos mais aptos têm uma chance melhor de sobrevivência.

Como não sabemos detalhes sobre a função de aptidão, precisamos normalizar os valores de aptidão. A função de aptidão é representada por fitness , que converte um cromossomo em um duplo arbitrário que representa a aptidão do cromossomo.

No código, encontramos taxas de aptidão para todos os cromossomos da população e também encontramos a aptidão total. Dentro do loop for , realizamos uma soma cumulativa sobre probabilidades reduzidas pela aptidão total. Matematicamente, isso deve resultar na variável final com o valor 1. Devido à imprecisão do ponto flutuante, não podemos garantir isso, então configuramos para 1 apenas para ter certeza.

Finalmente, para um número de vezes igual ao número de cromossomos de entrada, geramos um número aleatório, encontramos um intervalo que inclui o número e selecionamos o cromossomo correspondente. Como você pode notar, o mesmo cromossomo pode ser selecionado várias vezes.

Cruzamento

Agora precisamos dos cromossomos para “procriar”.

 private void crossover(List<T> population) { final int[] indexes = range(0, population.size()) .filter(i-> random() < crossoverProbability) .toArray(); shuffle(Arrays.asList(indexes)); for (int i = 0; i < indexes.length / 2; i++) { final int index1 = indexes[2 * i]; final int index2 = indexes[2 * i + 1]; final T value1 = population.get(index1); final T value2 = population.get(index2); population.set(index1, crossover.apply(value1, value2)); population.set(index2, crossover.apply(value2, value1)); } }

Com a probabilidade pré-definida crossoverProbability , selecionamos os pais para reprodução. Os pais selecionados são embaralhados, permitindo que qualquer combinação aconteça. Pegamos pares de pais e aplicamos o operador de crossover . Aplicamos o operador duas vezes para cada par porque precisamos manter o mesmo tamanho da população. Os filhos substituem os pais na população.

Mutação

Por fim, realizamos a recombinação das características.

 private void mutation(List<T> population) { for (int i = 0; i < population.size(); i++) { if (random() < mutationProbability) { population.set(i, mutation.apply(population.get(i))); } } }

Com probabilidade predefinida mutationProbability , realizamos “mutação” nos cromossomos. A mutação em si é definida por mutation .

Configuração do algoritmo específico do problema

Agora vamos dar uma olhada em que tipo de parâmetros específicos do problema precisamos fornecer para nossa implementação genérica.

 private BiFunction<T, T, T> crossover; private double crossoverProbability; private ToDoubleFunction<T> fitness; private Function<T, T> mutation; private double mutationProbability; private int populationSize = 100; private Supplier<T> supplier; private Predicate<Collection<T>> termination;

Os parâmetros, respectivamente, são:

1. Operador de cruzamento
2. Probabilidade de cruzamento
3. Função de condicionamento físico
4. Operador de mutação
5. Probabilidade de mutação
6. Tamanho da população
7. Fornecedor de cromossomos para a população inicial
8. Função de rescisão

Aqui está a configuração para o nosso problema:

 new GeneticAlgorithm<char[]>() .setCrossover(this::crossover) .setCrossoverProbability(0.25) .setFitness(this::fitness) .setMutation(this::mutation) .setMutationProbability(0.05) .setPopulationSize(100) .setSupplier(() -> supplier(expected.length)) .setTermination(this::termination) .find()

Operador de crossover e probabilidade

 private char[] crossover(char[] value1, char[] value2) { final int i = (int) round(random() * value1.length); final char[] result = new char(value1.length); System.arraycopy(value1, 0, result, 0, i); System.arraycopy(value2, i, result, i, value2.length - i); return result; }

A probabilidade de cruzamento é de 0,25, portanto, esperamos que, em média, 25% dos cromossomos sejam selecionados para cruzamento. Realizamos um procedimento simples para o cruzamento de um par de cromossomos. Geramos um número aleatório n do intervalo [0..length] , onde length é o comprimento de um cromossomo. Agora acasalamos o par selecionado pegando os primeiros n caracteres de um cromossomo e os caracteres restantes depois do segundo.

Função de condicionamento físico

 private double fitness(char[] value) { return range(0, value.length) .filter(i -> value[i] == expected[i]) .count(); }

A função de aptidão simplesmente conta o número de correspondências entre a frase alvo e o cromossomo dado.

Operador de mutação e probabilidade

 private char[] mutation(char[] value) { final char[] result = Arrays.copyOf(value, value.length); for (int i = 0; i < 2; i++) { int letter = (int) round(random() * (ALPHABET.length - 1)); int location = (int) round(random() * (value.length - 1)); result[location] = ALPHABET[letter]; } return result; }

A operação de mutação é realizada independentemente em cada cromossomo. A probabilidade de mutação é de 0,05, então esperamos que, em média, cinco por cento da população seja mutada. Mudamos escolhendo uma posição de letra aleatória e substituindo seu valor por uma letra aleatória do alfabeto. Fazemos isso duas vezes para cada cromossomo mutado.

Fornecedor

 private char[] supplier(int length) { final char[] result = new char(length); for (int i = 0; i < length; i++) { int letter = (int) round(random() * (ALPHABET.length - 1)); result[i] = ALPHABET[letter]; } return result; }

O fornecedor gera frases aleatórias pegando letras aleatórias do alfabeto. Cada frase tem um comprimento constante predefinido.

Função de Rescisão

 private boolean termination(Collection<char[]> chars) { count++; final Optional<char[]> result = chars.stream() .filter(value -> round(fitness(value)) == expected.length) .findAny(); if (result.isPresent()) { System.out.println("Count: " + count); System.out.println(result.get()); return true; } final boolean terminated = count == 3000; if (terminated) { chars.forEach(System.out::println); } return terminated; }

A função de terminação conta o número de chamadas e retorna true se houver uma correspondência exata ou se a contagem de geração atingir 3.000.

Execução

Agora estamos prontos para testar nosso algoritmo. Se você executá-lo várias vezes, notará que nem todas as execuções são bem-sucedidas. Cada vez, o número de iterações será diferente. Isso se deve à natureza probabilística do algoritmo. O algoritmo tem vários pontos onde pode ser melhorado. Você pode jogar com probabilidades de cruzamento e mutação.

Diminuir o número levará a uma solução estável, mas lenta. Um número menor de cromossomos será afetado por operadores genéticos e, portanto, mais iterações serão necessárias para a solução.

Aumentar os números acelerará o algoritmo, mas também tornará a solução instável. Os cromossomos aptos não serão apenas preservados, mas também serão afetados pelos operadores genéticos. Portanto, eles perderão seus genes “bons”.

É importante encontrar um bom equilíbrio. Aumentar o número de iterações dará ao algoritmo mais oportunidades de encontrar uma solução, mas, por outro lado, levará mais tempo. Você também pode aplicar diferentes métodos de cruzamento e mutação. Uma boa seleção desses operadores melhorará drasticamente a qualidade da solução.

Qual o proximo?

Nós cobrimos apenas a ponta do iceberg aqui. Pegamos um exemplo que tem apenas uma entrada, e a entrada pode ser facilmente apresentada como um cromossomo. Os operadores genéticos são claros e simples.

É muito interessante pegar um problema do mundo real e aplicar o algoritmo genético nele. Você descobrirá diferentes abordagens na codificação de dados de entrada reais, bem como diferentes implementações de cruzamento e mutação.

Se um problema pode ser expresso por meio de um conjunto de parâmetros que temos que adivinhar para otimizar uma métrica, podemos configurar rapidamente um GA que podemos usar para resolvê-lo.

Um dos problemas mais interessantes é o ensino de redes neurais artificiais. Podemos definir os parâmetros otimizáveis ​​como pontos fortes da sinapse e a métrica de aptidão como a porcentagem de entradas para as quais nossa rede neural deu a resposta certa. Depois disso, podemos sentar e deixar nossa rede neural evoluir para a solução ideal que desejamos. Ou pelo menos até conseguirmos algo bom o suficiente, porque a evolução leva tempo.