Computer art - parte 1

Olá pessoal, tudo certo?
No post de hoje temos um desafio interessante para um algoritmo evolucionário: dado uma determinada imagem e um número fixo de polígonos semi-transparentes, será que conseguimos aproximar a imagem de maneira satisfatória, em um tempo razoável?
Como você deve ter adivinhado, a resposta é sim, podemos! Observe as imagens abaixo:

Após 2386 gerações:

Após 17451 gerações:

Após 121076 gerações:

Imagem original:

Nas imagens acima vemos que mesmo com poucas gerações, obtemos bons resultados. Por exemplo, a imagem do centro (linha 2, coluna 2) foi formada em 8094 gerações, tomando pouco mais de 5 minutos de execução no meu MacBook Pro (2.4 GHz, 4 GB). Neste post vou mostrar como fazer isso da maneira mais simples possível, então mãos a obra!

Estratégia

A minha primeira tentativa para resolver esse problema foi usar uma GA simples, e os resultados não foram muito animadores: os polígonos demoravam muito para evoluir, e mesmo assim as imagens resultantes não eram muito boas. Provavelmente o crossover atua deteriorando os melhores indivíduos, o que torna a evolução muito lenta ou quase impossível. Claro, bastou eliminar o crossover para obter resultados muito melhores.

Como estratégia, vamos usar uma espécie de 'Hill Climbing estocástico', de acordo com o pseudo-código abaixo:

 solucao := cria cromossomo randômico

 repete
    novaSolucao := mutaciona(criaCopia(solucao))
    se novaSolucao.qualidade > solucao.qualidade
       solucao := novaSolucao
 ate atingir a qualidade desejada

 retorna solucao

A qualidade de cada solucao é simplesmente uma comparação pixel a pixel da imagem alvo e da solução atual. Apesar de não 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 número de vértices de cada polígono. 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 espaço de busca. Dessa forma, representamos um polígono de V vértices como poly(V) = [x1, y1, x2, y2, ..., xv, yv, red, green, blue, alpha].

Um cromossomo é apenas uma sequência de polígonos: 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 começar criando uma classe que faça esse encoding/decoding, continue lendo!

Classe BinaryIntChromosome

O papel dessa classe é simples: codificar um vetor de inteiros em um vetor de booleans, e ter a capacidade de fazer a operação reversa: decodificar o vetor de booleans em um vetor de inteiros. No construtor passamos os vetores minVals e maxVals, que representam respectivamente os valores mínimos e máximos que as variáveis podem assumir, e opcionalmente passamos um objeto java.util.Random, que irá percorrer o cromossomo e setar os bits de maneira randômica.

A 'qualidade' de cada cromossomo é representada pela variável de instância fitness, e obviamente é setada pelo cliente da classe.O método mutatepercorre o cromossomo e inverte cada bit com a probabilidade fornecida. Por fim, o método decodefaz o que realmente interessa: decodifica o cromossomo e seta a variável de instância fenotype, que representa as variáveis do problema em questão. Segue a classe:

import java.util.Random;

public class BinaryIntChromosome implements Comparable<BinaryIntChromosome>
{
 protected int[] minVals;
 protected int[] maxVals;
 protected int[] bitsPerVar;
 protected boolean[] genotype;
 protected int[] fenotype;
 protected float fitness; 
 protected int totalBits;
 
 public BinaryIntChromosome(int[] minVals, int[] maxVals, Random random)
 {
  this.minVals = minVals;
  this.maxVals = maxVals;
  this.bitsPerVar = new int[minVals.length];
  
  for (int i = 0; i < minVals.length; i++)
  {
   int nBits = maxVals[i] - minVals[i] + 1;
   double bits = Math.log(nBits)/Math.log(2); 
   bitsPerVar[i] = (int) Math.ceil(bits); 
   this.totalBits += bitsPerVar[i];
  }
  
  this.genotype = new boolean[totalBits];
  this.fenotype = new int[minVals.length];
  
  if (random != null)
   this.randomizeGenotype(random);
 }
 
 protected void randomizeGenotype(Random random)
 { 
  for (int i = 0; i < totalBits; i++)        
   genotype[i] = random.nextBoolean();  
 }
 
 protected static int binToDec(boolean[] string, int startIndex, int endIndex)
 {
  int val = 0;
  int slot = 0;
  for (int i = startIndex; i <= endIndex; i++)
  {
   if (string[i])
    val += (int) Math.pow(2, slot);
   slot++;
  }
  return val;
 }
 
 protected void mutate(Random random, float mutationRate)
 {
  for (int i = 0; i < genotype.length; i++)
  {
   float f = random.nextFloat();
   if (f < mutationRate)
    genotype[i] = !genotype[i];
  }
 }
 
 protected BinaryIntChromosome duplicate()
 {
  int[] lb = new int[minVals.length];
  int[] ub = new int[maxVals.length];
  
  for (int i = 0; i  < minVals.length; i++)
  {
   lb[i] = minVals[i];
   ub[i] = maxVals[i];
  }
  
  BinaryIntChromosome theCopy = new BinaryIntChromosome(lb, ub, null);  
  for (int i = 0; i < this.genotype.length; i++)
   theCopy.genotype[i] = this.genotype[i];
   
  for (int i = 0; i < this.fenotype.length; i++)
   theCopy.fenotype[i] = this.fenotype[i];
   
  return theCopy;
 }
 
 protected void decode()
 {
  int bitIndex = 0;
  for (int var = 0; var < bitsPerVar.length; var++)
  {
   int bitsToRead = bitsPerVar[var];
   int startIndex = bitIndex;
   int endIndex = startIndex + bitsToRead - 1; 
   int decVal = BinaryIntChromosome.binToDec(this.genotype, startIndex, endIndex);   
   int n = (int)(Math.pow(2, bitsToRead) - 1);      
   int range = maxVals[var] - minVals[var];
   this.fenotype[var] = this.minVals[var] + (range * decVal) / n;               
   bitIndex += bitsToRead;   
  }
 }
 
 public int compareTo(BinaryIntChromosome other)
 {      
  if (this.fitness > other.fitness)
    return 1;
  else if (this.fitness < other.fitness)
   return -1;
   
  return 0;
 }
 
} 

Interface FitnessDelegate

Essa interface define o método getFitness, onde a qualidade do indivíduo será determinada passando-se o fenótipo como argumento:

public interface FitnessDelegate
{
 float getFitness(int[] fenotype);
}

Classe HillClimb

Agora que já sabemos como codificar/decodificar nossas variáveis, é uma boa hora para implementar o HC. O construtor da classe recebe os vetores de mínimo e máximo e também a taxa de mutação que será aplicada ao cromossomo. O objeto passado em delegate implementa a interface FitnessDelegate, sendo responsável pelo cálculo de fitness.

O método evolve simplesmente avança uma geração, podendo ser executado em uma Thread separada e notificar outras Threads, caso necessário. Por fim, getBest nos retorna a melhor solução obtida até então, que no caso do HC é sempre igual a solução atual, já que se trata de um algoritmo 'greedy'. Segue a classe:

import java.util.Random;
import java.util.concurrent.CountDownLatch;

public class HillClimb implements Runnable
{ 
 protected BinaryIntChromosome current;
 protected BinaryIntChromosome best;
 protected float mutationRate;
 protected FitnessDelegate delegate; 
 protected Random random = new Random();
 protected CountDownLatch signal;
 
 public HillClimb(int[] lower, int[] upper, FitnessDelegate delegate, float mutationRate,  CountDownLatch signal, boolean randomizeStart)
 {
  this.delegate = delegate;
  this.mutationRate = mutationRate;
  this.signal = signal;
  
  current = new BinaryIntChromosome(lower, upper, randomizeStart ? random : null);
  current.decode();
  current.fitness = delegate.getFitness(this.current.fenotype);
  best = current;
 }
 
 public void run()
 {
  evolve();
  if (signal != null)
   signal.countDown();
 }
 
 public void evolve()
 {
  BinaryIntChromosome copyIndiv = current.duplicate();
  copyIndiv.mutate(random, mutationRate);
  copyIndiv.decode();
  copyIndiv.fitness = delegate.getFitness(copyIndiv.fenotype);
  
  if (copyIndiv.fitness > current.fitness)
  {
   current = copyIndiv;
   best = copyIndiv;
  }
 }
 
 public BinaryIntChromosome getBest()
 {
  return best;
 }
}

Testando

Para finalizar este post, vamos testar as duas classes escritas e maximizar a função y = (x5 * x4 * x3) / (x2 * x1 * x0), cujo domínio está entre xmin = [1, 2, 3, 4, 5, 6] e xmax = [10, 20, 30, 40, 50, 60]. Como você deve ter notado, a solução é trivial: S = [1, 2, 3, 40, 50, 60], porém o computador não sabe disso!

public class TestHC
{
 public static void main (String[] args)
 {
  int[] min = new int[]{1, 2, 3, 4, 5, 6};
  int[] max = new int[]{10, 20, 30, 40, 50, 60};
  float mutationRate = 0.05f;
  int generations = 600;
  
  FitnessDelegate delegate = new FitnessDelegate()
  {   
   public float getFitness(int[] fenotype)
   {
    return (1.0f * fenotype[5] * fenotype[4] * fenotype[3]) / (fenotype[2] * fenotype[1] * fenotype[0]);
   }
  };
    
  HillClimb hc = new HillClimb(min, max, delegate, mutationRate, null, true);
  for (int i = 0; i < generations; i++)
   hc.evolve();
   
  BinaryIntChromosome best = hc.getBest();
  
  System.out.println("Best solution: ");  
  for (int i = 0; i < best.fenotype.length; i++)
   System.out.println("x[" + i + "] : " + best.fenotype[i]);
 }
}

Na próximo post colocaremos os polígonos a prova, até mais!