Ola pessoal, tudo certo?No post de hoje temos um desafio interessante para um algoritmo evolucionario:dado uma determinada imagem e um numero fixo de poligonos semi-transparentes, sera que conseguimos aproximar a imagem de maneira satisfatoria, em um temporazoavel? Como voce deve ter adivinhado, a resposta e sim, podemos! Observe as imagens abaixo:Apos 2386 geracoes:Apos 17451 geracoes:Apos 121076 geracoes:Imagem original:Nas imagens acima vemos que mesmo com poucas geracoes, obtemos bons resultados. Por exemplo, a imagem do centro (linha 2, coluna 2) foi formada em 8094 geracoes, tomando poucomais de 5 minutos de execucao no meu MacBook Pro (2.4 GHz, 4 GB).Neste post vou mostrar como fazer isso da maneira mais simples possivel, entao maos a obra!Estrategia A minha primeira tentativa para resolver esse problema foi usar uma GA simples, e os resultados nao foram muito animadores: os poligonos demoravam muito para evoluir, e mesmo assim as imagens resultantes nao eram muito boas. Provavelmente o crossover atua deteriorando os melhores individuos, o que torna a evolucao muito lenta ou quase impossivel. Claro, bastou eliminar o crossover para obter resultados muito melhores. Como estrategia, vamos usar uma especie de 'Hill Climbing estocastico', de acordo com o pseudo-codigo abaixo: solucao := cria cromossomo randomico repete novaSolucao := mutaciona(criaCopia(solucao)) se novaSolucao.qualidade > solucao.qualidade solucao := novaSolucao ate atingir a qualidade desejada retorna solucao A qualidade de cada solucao e simplesmente uma comparacao pixel a pixel da imagem alvo e da solucao atual. Apesar de nao ser muito eficiente (depende do tamanho da imagem), essa foi a maneira mais simples que encontrei. Para facilitar o decoding dos cromossomos, fixamos um valor V para o numero de vertices de cada poligono. Quanto as cores, usaremos os 4 componentes RGBA e restringimos o valor de alpha numa determinada faixa [alphMin, alphaMax], o que nos permite 'cortar' um pouco o espaco de busca. Dessa forma, representamos um poligono de V vertices como poly(V) = [x1, y1, x2, y2, ..., xv, yv, red, green, blue, alpha]. Um cromossomo e apenas uma sequencia de poligonos: cromo(N, V) = [poly1(V), poly2(V), ..., polyN(V)]. Como de costume, usaremos uma string de 1's e 0's para codificar nosso problema. Vamos comecar criando uma classe que faca esse encoding/decoding, continue lendo!Classe BinaryIntChromosome O papel dessa classe e simples: codificar um vetor de inteiros em um vetor de booleans, e ter a capacidade de fazer a operacao reversa: decodificar o vetor de booleans em um vetor de inteiros. No construtor passamos os vetores minVals e maxVals, que representam respectivamente os valores minimos e maximos que as variaveis podem assumir, e opcionalmente passamos um objeto java.util.Random, que ira percorrer o cromossomo e setar os bits de maneira randomica. A 'qualidade' de cada cromossomo e representada pela variavel de instancia fitness, e obviamente e setada pelo cliente da classe.O metodo mutatepercorre o cromossomo e inverte cada bit com a probabilidade fornecida. Por fim, o metodo decodefaz o que realmente interessa: decodifica o cromossomo e seta a variavel de instancia fenotype, que representa as variaveis do problema em questao. Segue a classe:import java.util.Random;public class BinaryIntChromosome implements Comparable<BinaryIntChromosome>{ protected int[] minVals; protected int[]