O que são Algoritmos Genéticos?

Nos últimos anos, tem havido um grande zumbido em torno da Inteligência Artificial (IA). Grandes empresas como Google, Apple, e Microsoft estão trabalhando ativamente no tema. Na verdade, a IA é um guarda-chuva que cobre muitos objetivos, abordagens, ferramentas e aplicações. Genetic Algorithms (GA) é apenas uma das ferramentas para busca inteligente através de muitas soluções possíveis.

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

GA mantém uma população de cromossomas – um conjunto de potenciais soluções para o problema. A idéia é que a “evolução” encontrará uma solução ótima para o problema após um número de gerações sucessivas – semelhante à seleção natural.

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

Similiar à seleção natural, o conceito central da seleção de AG é a adequação. Os cromossomas 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 cromossoma. Em essência, cada cromossoma 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 comercialização, cada cromossoma consistirá logicamente em dois elementos. Como os elementos são codificados dentro do cromossoma é um tópico diferente.

Durante a seleção, os cromossomas formam pares de pais para reprodução. Cada filho tira 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.

Porque cromossomas mais aptos produzem mais crianças, cada geração subsequente terá melhor condição física. Em algum momento, uma geração conterá um cromossomo que representará uma boa solução para o nosso problema.

GA é poderoso e amplamente aplicável para problemas complexos. Há uma grande classe de problemas de otimização que são bastante difíceis de resolver pelas técnicas convencionais de otimização. Algoritmos genéticos são algoritmos eficientes cuja solução é aproximadamente ótima. As aplicações bem conhecidas incluem programação, transporte, roteamento, tecnologias de grupo, design de layout, treinamento de redes neurais e muitas outras.

Putting Things into Practice

O exemplo que vamos ver pode ser considerado o “Hello World” da GA. Este exemplo foi dado inicialmente por J. Freeman em Simulação de Redes Neurais com o Mathematica. Eu o tirei dos Algoritmos Genéticos e do Projeto de Engenharia do Mitsuo Gen e Runwei Cheng.

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

Desde que existem 26 letras possíveis para cada um dos 13 locais da lista, a probabilidade de obtermos a frase correcta de uma forma puramente aleatória é (1/26)^13=4.03038×10-19, que é cerca de duas chances fora de um (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 à língua inglesa ou a uma frase específica. Podemos acabar lidando com qualquer alfabeto, ou mesmo com qualquer conjunto de símbolos. Não temos nenhum conhecimento da língua. Nem sequer sabemos se existe alguma língua.

Vamos dizer que o nosso adversário pensou numa frase arbitrária, incluindo o espaço em branco. Sabemos o comprimento da frase e a contagem dos símbolos no alfabeto. Esse é o único conhecimento que temos. Após cada palpite, o nosso adversário diz-nos quantas letras estão no lugar.

Cada cromossoma é uma sequência de índices dos símbolos do alfabeto. Se estamos a falar do 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 “be” será representada como .

Demonstraremos todos os passos através de trechos de código Java, mas o conhecimento de Java não é necessário para entender cada passo.

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 passos em que cada AG mais ou menos consiste. Na etapa de inicialização, nós geramos uma população inicial de frases. O tamanho da população é determinado por populationSize. Como a frase é gerada depende da implementação do supplier.

No passo de iteração, nós evoluímos a população até que as condições de terminação sejam satisfeitas dentro do teste de while loop. As condições de terminação podem incluir tanto o número de gerações como a correspondência exata de uma das frases na população. O termination encapsula uma implementação exata.

Em cada iteração, nós executamos os passos típicos da AG:

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

O núcleo do algoritmo é muito simples e agnóstico de domínio. Ele será o mesmo para todos os problemas. O que você precisará afinar é a implementação de operadores genéticos. A seguir, vamos dar uma olhada de perto em cada um dos operadores de AG anteriormente mencionados.

Seleção

Como já sabemos, a seleção é um processo de encontrar sucessores para os cromossomos atuais – os cromossomos que são mais adequados para o nosso problema. Durante a seleção, precisamos garantir que os cromossomos com melhor condição física tenham mais chances 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; for (int i = 0; i < fitnesses.length; i++) { sum += fitnesses / totalFitness; probabilities = sum; } probabilities = 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 idéia por trás desta implementação é a seguinte: A população é representada como faixas conseqüentes no eixo numérico. Toda a população está entre 0 e 1,

>

A parte da faixa que um cromossomo leva é proporcional à sua aptidão física. Isto resulta em um cromossomo mais apto a receber um pedaço maior. Então nós olhamos aleatoriamente para um número entre 0 e 1 e encontramos um intervalo que inclui o número. Obviamente, intervalos maiores têm maiores chances de serem selecionados e, portanto, cromossomos mais aptos têm melhores chances de sobrevivência.

Por não sabermos detalhes sobre a função de condicionamento físico, precisamos normalizar os valores de condicionamento físico. A função fitness é representada por fitness, que converte um cromossoma num duplo arbitrário que representa a fitness do cromossoma.

No código, encontramos as taxas de fitness para todos os cromossomas da população, e também encontramos a fitness total. Dentro do laço for, realizamos uma soma cumulativa sobre probabilidades escalonadas para baixo pela aptidão total. Matematicamente, isto deve resultar em que a variável final tenha o valor 1. Devido à imprecisão do ponto flutuante, não podemos garantir isso, então definimos para 1 apenas para ter certeza.

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

Crossover

Agora precisamos dos cromossomas 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; final int index2 = indexes; 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 predefinida crossoverProbability, selecionamos os pais para procriar. Os pais selecionados são embaralhados, permitindo que qualquer combinação aconteça. Pegamos os pares de pais e aplicamos o operador crossover. Aplicamos o operador duas vezes para cada par porque precisamos manter o tamanho da população igual. Os filhos substituem seus pais na população.

Mutação

Finalmente, 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 pré-definida mutationProbability, realizamos a “mutação” nos cromossomos. A mutação em si é definida por mutation.

Configuração de Algoritmos específicos do problema

Agora vamos dar uma olhada em que tipo de parâmetros específicos do problema precisamos fornecer para a 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 crossover
2. Probabilidade de crossover
3. Função de adequação
4. Operador de mutação
5. Probabilidade de mutação
6. Tamanho da população
7. Fornecedor de cromossomas para a população inicial
8. Função de terminaçã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()

Clossover Operador 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 crossover é 0.25, então esperamos que em média 25% dos cromossomas sejam selecionados para o crossover. Nós realizamos um procedimento simples para o crossover de um par de cromossomas. Geramos um número aleatório n a partir do intervalo , onde length é o comprimento de um cromossoma. Agora acasalamos o par selecionado pegando o primeiro n caracteres de um cromossomo e os caracteres restantes após o segundo.

Fitness Function

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

A função fitness conta simplesmente o número de combinações entre a frase alvo e o cromossomo dado.

Operador da 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 = ALPHABET; } return result;}

A operação de mutação é realizada independentemente em cada cromossomo. A probabilidade de mutação é de 0,05, por isso esperamos que, em média, cinco por cento da população sofra mutação. Nós mutamos 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 cromossoma 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 = ALPHABET; } return result;}

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

Função de terminaçã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 o nosso algoritmo. Se você executá-lo várias vezes, você vai notar que nem todas as execuções são bem sucedidas. Cada vez, o número de iterações será diferente. Isso é devido à natureza probabilística do algoritmo. O algoritmo tem vários pontos onde pode ser melhorado. Você pode jogar com probabilidades de crossover e mutação.

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

Aumentar os números irá acelerar o algoritmo, mas também irá tornar a solução instável. Cromossomos aptos não só serão preservados, como 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 para 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 selecção destes operadores irá melhorar drasticamente a qualidade da solução.

Cobrimos aqui apenas a ponta do iceberg. Tomamos um exemplo que tem apenas um input, e o input pode ser facilmente apresentado como um cromossoma. Os operadores genéticos são simples e simples.

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

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

Um dos problemas mais interessantes é o ensino de redes neurais artificiais. Podemos definir os parâmetros otimizáveis para serem forças de sinapse, e a métrica de adequação para ser a porcentagem de entradas para as quais a 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 suficientemente bom, porque a evolução leva tempo.