Computação Evolucionária: Algoritmos Genéticos

Olá pessoal,

Neste post vamos sair um pouco do foco no tema de redes neurais, e entrarmos em outra área muito estudada e cobiçada no ramo de inteligência artificial: Computação evolutiva ou evolucionária. Mas do que se trata esse campo ?

Computação Evolutiva de fato!

Computação evolucionária

A computação evolucionária (CE) é um ramo da ciência da computação que propõe um paradigma alternativo ao processamento de dados convencional. Este novo paradigma tenta resolver problemas a partir de mecanismos evolutivos encontrados na natureza, tais como a auto-organização e o comportamento adaptativo. Esses conceitos foram introduzidos e formalizados por Charles Darwin na sua teoria da evolução natural, segundo a qual, a vida na terra é resultado de um processo de seleção, pelo meioa ambiente, do mais aptos e adaptados, e por isto mesmo com mais chances de reproduzir-se. A diversidade da vida, associada ao fato de que todos os seres vivos compartilham uma bagagem genética comum, pelo menos em termos de seus componentes básicos, é um exemplo eloqüente das possibilidades do mecanismo de evolução natural.

Um dos clássicos modelos computacionais inspirados neste paradigma (CE) são os algoritmos genéticos, o tema a ser discutido nesse post. Mas antes de entrarmos a fundo neste poderoso modelo computacional, vamos entender um pouco a sua aplicação.

Aplicações

Problemas compostos de múltiplas variáveis e diversas soluções estão presentes em uma grande variedade de problemas de otimização. Esses problemas são caracterizados por circunstâncias em que se desejam maximizar ou minimizar uma função numérica de várias variáveis, em um contexto que podem existir restrição. Apesar da existência de diversas técnicas clássicas de otimização para a solução desses tipos de problema, a sua falta de robustez e alta complexidade em problemas de alta dimensionalidade impulsionaram a busca por novas alternativas.
A sofisticação dos recursos computacionais desenvolvidos nos últimos anos tem motivado um grande avanço nas técnicas de otimização. Com isso, uma forte tendência tem acompanhado esse avanço através de estudos de métodos heurísticos que permitem encontrar soluções ótimas em diferentes espaços de busca, inclusive vários com máximos e mínimos locais. Dentre essas heurísticas, os algoritmos evolucionários têm tido grande sucesso em solucionar problemas de otimização de múltiplas soluções. Um desses algoritmos é o algoritmo genético, visto como otimizador de funções, embora a quantidade de problemas para qual os AG's se aplicam seja bastante abrangente. Então podemos resumir que os algoritmos genéticos são eficientes otimizadores de problemas de múltiplas soluções. Vamos citar alguns exemplos:

-- Problemas de otimização complexos: problemas com muitas variáveis e espaços de soluções de dimensões elevadas. Ex: problema do caixeiro viajante, gerenciamento de carteiras de fundos de investimento.

-- Otimização de funções matemáticas.

--Gerenciamento de redes: supervisão do tráfego nos links e das filas nos "buffers" de roteadores para descobrir rotas ótimas e para reconfigurar as rotas existentes no caso de falha de algum link .

-- Roteamento de veículos, otimização de solução de jogos como quebra-cabeças, cubo mágicos, etc.

Como podemos ver a gama de problemas solucionáveis por algoritmos genéticos é muito abrangente. Neste post de teor introdutório, iremos descrever o algoritmo genético através de uma implementação simples na linguagem de programação Python a fim de encontrar o máximo/mínimo de uma função númerica contínua (Otimização de funções numéricas).

O problema consiste em achar o máximo da função:

f(x) = x * sen(10*pi*x) + 1.0 ,
restrita ao intervalo x em [-1.0,2.0]

Gráfico da função f(x) = x * sen(10*pi*x) + 1.0

Podemos observar que a função a ser otimizada é uma função multimodal com vários pontos de máximo e que para encontrarmos manualmente o máximo global é muito dispendioso em tempo e esforço. Como podemos solucionar essa busca ? Algoritmos genéticos!

Afinal ,o que são algoritmos genéticos ?

Os algoritmos genéticos são uma família de modelos computacionais inspirados na evolução, que incorporam uma solução potencial para um problema específico numa estrutura semelhante a de um cromossomo e aplicam operadores de seleção e "cross-over" a essas estruturas de forma a preservar informações críticas relativas à solução do problema.

Uma de suas vantagens é a simplificação que permite na formulação e solução de problemas otimização. Algoritmos genéticos normalmente com descrições de entradas formadas por cadeias de bits de tamanho fixo. Eles possuem um paralelismo implícito decorrente da avaliação independente de cada uma dessas cadeias de bits, ou seja, pode-se avaliar paralelamente a viabilidade de um conjunto de parâmetros para a solução do problema de otimização em questão.

Existem três tipos de representação possíveis para os cromossomos: binária, inteira ou real. A essa representação se dá o nome de alfabeto do Algoritmo Genético. De acordo com a classe de problema que se deseje resolver pode-se usar qualquer um dos três tipos.

Uma implementação de um algoritmo genético começa com uma população aleatória de cromossomos. Essas estruturas são, então, avaliadas e associadas a uma probabilidade de reprodução de tal forma que as maiores probabilidades são associadas aos cromossomos que representam uma melhor solução para o problema de otimização do que àqueles que representam uma solução pior. A aptidão da solução é tipicamente definida com relação à população corrente.

A função objetivo de um problema de otimização é construída a partir dos parâmetros envolvidos no problema. Ela fornece uma medida da proximidade da solução em relação a um conjunto de parâmteros. Os parâmetros podem ser conflitantes, ou seja, quando um aumenta o outro diminui. O objetivo é encontrar o ponto ótimo. A função objetivo permite o cálculo da aptidão bruta de cada indivíduo, que fornecerá o valor a ser usado para o cálculo de sua probabilidade de ser selecionado para reprodução.

Depois dessa explicação formal, é chegada a hora de botar a mão na massa. Vamos primeiramente resumir os principais conceitos apresentados acima e o que eles representam no mundo real. Vejam a tabela abaixo:

Tabela: Algoritmos Genéticos x Mundo Real

A idéia por trás do algoritmo genético consiste em gerar, através de regras específicas, um grande número de cromossomos (indivíduos), população, de forma a provmover uma varredura tão extensã quanto necessária do espaço de soluções. Vale salientar que cada cromossomo corresponde a um ponto no espaço de soluções do problema de otimização.

Como o código-fonte é extenso, explicarei por seções o algoritmo do algoritmo genético.

O Algoritmo dos algoritmos genéticos

A estrutura básica do algoritmo genético é mostrado na figura abaixo:

Fluxograma do Algoritmo Genético

Com referência ao fluxograma da figura acima, observa-se que cada iteração do algoritmo genético corresponde à aplicação de um conjunto de quatro operações básicas: cálculo de aptidão (fitness evaluation), seleção (selection), cruzamento (crossover) e mutação (mutation). Ao fim destas operações cria-se uma nova população, chamada de geração (generation) que, espera-se, representa uma melhor aproximação da solução (best solution) do problema de otimização que a população anterior. A população inicial é gerada atribuindo-se aleatoriamente valores aos genes (pense um gene como um repositório que armazena algo) de cada cromossomo. A aptidão bruta de um indivíduo da população é medida por uma função de erro, também chamada de função objetivo (fitness function) do problema de otimização.

A aptidão bruta é em seguida normalizada (aptidão normalizada), para permitir um melhor controle do processo de seleção. Como critérios de parada do algoritmo em geral são usados a aptidão do melhor indivíduo em conjunto com a limitação do número de gerações. Outros critérios podem envolver, por exemplo, um erro abaixo de um valor especificado pelo projetista para um determinado parâmetro do problema.

Vamos aos passos do algoritmo:

Inicialização (Generation of population)

Uma população de P individuos é gerada aleatoriamente. Cada um dos indivíduos da população representa uma possível solução para o problema, ou seja, um ponto no espaço de soluções.

"""
Represents a possible solution for the problem
"""
import random
import math

MAXIMIZE,MINIMIZE = (0,1)

STR_DELIMITER = ''

class Individual(object):

#The length of the chromosome
length = 22
#Values that the gene can be
alleles = (0,1)
#Function range
range = (-1.0,2.0)
#Optimization's type
optimization = MAXIMIZE

#Creates a simple individual
#@param chromosome: Data Structure that codificates the solution of the problem.
def __init__(self,chromosome=None):
  #The Fitness score
  self.score = None
  #Collection of genes.
  self.chromosome = chromosome or self._makeChromosome()

#Creates a new chromosome made up of genes limited by its length.
def _makeChromosome(self):
 return [random.choice(self.alleles) for gene in xrange(self.length)]

#Evaluates the fitness score
#@param optimum: Optimization method
def evaluate(self,optimum=None):
  #Decodification of the chromosome
  coff = float(int(STR_DELIMITER.join(map(str,self.chromosome)),2)) / float(pow(2,self.length) - 1)
  x = self.range[0] + (self.range[1] - self.range[0]) * coff
  #Evaluation of the function
  y =  x * math.sin(10.0 * math.pi * x) + 1.0
  #Calculates the fitness score
  self.score = y

#combination of the parents to produce a new child
def crossover(self,mate):
  #Two-point crossover
  return self._twopoint(mate)

#Create a new individual replacing a gene allele with a random one.
#@param gene: The gene of chromosome
def mutate(self,gene):
  self._pick(gene)

##Invert the gene's allele to create a new individual.
#param gene: The gene that will be replaced.
def _pick(self,gene):
  self.chromosome[gene] = int(not self.chromosome[gene])

#Creates offspring via two-point crossover between mates."
#param mate: the other mate
def _twopoint(self,other):
  left,right = self._pickPivots()
  def mate(p0,p1):
      #Creates a new copy of p0.
      chromosome = p0.chromosome[:]
      #Two-point crossover
      chromosome[left:right] = p1.chromosome[left:right]
      child = p0.__class__(chromosome)
      child.repair(p0,p1)
      return child
  return mate(self,other), mate(other,self)

#Helper function to get the cutting point.
def _pickPivots(self):
  left = random.randrange(1,self.length-2)
  right = random.randrange(left,self.length-1)
  return left,right

#Crossover helper, if necessary, to fix duplicated genes
#@param parent1 : The mate 01
#@param parent2 : The mate 02
def repair(self,p0,p1):
  pass

#Returns string representation of itself
def __repr__(self):
  return '<%s chromosome="%s" score=%s>' % \
      (self.__class__.__name__,
       STR_DELIMITER.join(map(str,self.chromosome)),self.score)

#The comparison method with other individual
#@param other: The other individual that will be compared.
def __cmp__(self,other):
  if self.optimization == MINIMIZE:
          return cmp(self.score,other.score)
  else:
      #MAXIMIZE
      return cmp(other.score,self.score)

#Creates a replicate of itself.
def copy(self):
  clone = self.__class__(self.chromosome[:])
  clone.score = self.score
  return clone


"""
Enviroment necessary to run the Genetic Algorithm.
"""
class Environment(object):
#Initialize the enviroment parameters necessary to run the algorithm.
#@param population : The initial population of individuals.
#@param size: Size of the population.
#@param maxgenerations: The maximum generations.
#@param crossover_rate: Crossover rate.
#@param mutation_rate: Mutation rate.
#@param optimum :  Optimization type.
def __init__(self,population=None,size=100,maxgenerations=100,
           crossover_rate=0.90,mutation_rate=0.01,optimum=None):
  #Size of the population
  self.size = size
  #Optimization method
  self.optimum = optimum
  #Initialize the population
  self.population = population or self._makePopulation()
  #Start the evaluation of the population
  for individual in self.population:
      individual.evaluate(self.optimum)
  #Crossover rate
  self.crossover_rate = crossover_rate
  #Mutation rate
  self.mutation_rate = mutation_rate
  #Max number of generations
  self.maxGenerations = maxgenerations
  #Initialize the generation
  self.generation = 0
  #Report the algorithm running status
  self.report()

#Initialize the population (Generate the individuals)
def _makePopulation(self):
  return [Individual() for individual in xrange(self.size)]

(...)

Calculo da aptidão (Evaluation of fitness)

Geralmente a aptidão do indivíduo é determinada através do cálculo da função objetivo, que depende das especificações de projeto. Neste projeto, cada indivíduo é uma entrada para uma função de análise de desempenho (evaluate), cuja saída fornece medidas que permitem ao algoritmo genético o cálculo da aptidão do indivíduo. Ainda nesta fase os indivíduos são ordenados conforme a sua aptidão.

#Evaluates the fitness score
#@param optimum: Optimization method
def evaluate(self,optimum=None):

   #Decodification of the chromosome
   coff = float(int(STR_DELIMITER.join(map(str,self.chromosome)),2)) / float(pow(2,self.length) - 1)
   x = self.range[0] + (self.range[1] - self.range[0]) * coff
   #Evaluation of the function
   y =  x * math.sin(10.0 * math.pi * x) + 1.0
   #Calculates the fitness score
   self.score = y

Seleção (Selection)

Nesta fase os indivíduos mais aptos da geração atual são selecionados. Esses indivíduos são utilizados para gerar uma nova população por cruzamento. São selecionados os n melhores indivíduos daquela geração e depois faz uma espécie de torneio. Neste método, denominado "amostragem universal estocática", cada indivíduo tem uma probabilidade de ser selecionado proporcional à sua aptidão. Para visualizar este método considere um círculo dividido em n regiões (tamanho da população), onde a área de cada região é proporcional à aptidão do indivíduo.Coloca-se sobre este círculo uma "roleta" com n cursores, igualmente espaçados. Após um giro da roleta a posição dos cursores indica os indivíduos selecionados. Isto significa que quanto melhores são os cromossomos, mais chances de serem selecionados. O lado de cada secção da roleta é proporcional ao valor de adequação (aptidão) de cada cromossomo: quanto maio valor, mais larga a secção. Veja a imagem a seguir para um exemplo:

Método de seleção de cromossomos por Roleta

Evidentemente, tais condições são mensuradas por valores, que quando elevados, o melhor indivíduo da população terá maior probabilidade de ser selecionado várias vezes. Como consequência, a seleção de indivíduos pode conter várias cópias de um mesmo indivíduo enquanto outros podem desaparecer.

class Environment(object):
 (...)

  #The step-by-step running algorithm
  def run(self):
      while not self._goal():
          self.step()

  #The conditions to stop the algorithm.
  def _goal(self):
      return (self.generation > self.maxGenerations) or (self.best.score == self.optimum)

  #The step done by the genetic algorithm
  def step(self):
      #Sort the individuals of the population based on their score
      self.population.sort()
      #Make the crossover
      self._crossover()
      #Increments the generation
      self.generation+=1
      #Report the current status
      self.report()

  (...)
    
  #Selection method of the individuals for crossover
  def _select(self):
      return self._tournament()

  (...)

  #sample selection method
  def _tournament(self):
      competitors = []
      total_score = sum([math.ceil(self.population[i].score) for i in xrange(self.size)])
      for index in xrange(self.size):
          temp = [index] * int((math.ceil(self.population[index].score /total_score) * 100))
          competitors.extend(temp)
        
      return self.population[random.choice(competitors)]

  (...)

Cruzamento (Crossover)

Os indivíduos selecionados na etapa anterior são cruzados. A forma como se realiza este cruzamento é ilustrada na figura abaixo. Os cromossomos de cada par de indivíduos a serem cruzados são particionados em um ponto, chamado ponto de corte, sorteado aleatoriamente. Um novo cromossomo é gerado permutando-se a metade inicial de um cromossomo coma metade final do outro. Deve-se notar que se o cromossomo for representado por uma cadeia de bits, como na figura figura 3, o ponto de corte pode incidir em qualquer posição (bit) no interior de um gene, não importando os limites do gene. No caso de genes representados por números reais, a menor unidade do cromossomo que pode ser permutada é o gene.

Exemplo de crossover com genes (bits)

class Environment(object):
   (...)
    
    #Crossover proccess
    def _crossover(self):
        #Elistism proccess (best individual is copied to the next generation)
        next_population = [self.best.copy()]
        while len(next_population) < self.size:
            mate1 = self._select()
            if random.random() < self.crossover_rate:
                mate2 = self._select()
                offspring = mate1.crossover(mate2)
            else:
                #make a copy of individual
                offspring = [mate1.copy()]
            for individual in offspring:
                self._mutate(individual)
                individual.evaluate(self.optimum)
                next_population.append(individual)
        self.population = next_population[:self.size]
    
 (...)  

Mutação (Mutation)

A operação de mutação é utilizada para garantir uma maior varredura do espaço de estados e evitar que o algoritmo genético convirja muito cedo para mínimos locais. A mutação é efetuada alterando-se o valor de um gene de um indivíduo sorteado aleatoriamente com uma determinada probabilidade, denominada probabilidade de mutação, ou seja, vários indivíduos da nova população podem ter um de seus genes alterado aleatoriamente.

class Environment(object):
   (...)
   
    #Mutation method.
    #@param individual: Individual to be mutated.
    def _mutate(self,individual):
        for gene in xrange(individual.length):
            if random.random() < self.mutation_rate:
                individual.mutate(gene)
    
    #Get the individual with best fitness score in population.
    def best():
        def fget(self):
            return self.population[0]
        return locals()
    best = property(**best())
    
    #Shows the results report
    def report(self):
        print "="*70
        print "generation: " , self.generation
        print "best:       " , self.best

Para executarmos o código demonstrado acima, instanciamos a classe Enviroment passando como parâmetros o tamanho da população, número máximo de gerações, o ótimo global (pode er usado também como condição de parada) e as taxas de crossover e mutação respectivamente,de acordo com o tipo de problema em questão. Neste pequeno exemplo, tentamos solucionar um problema de maximização, onde a solução ótima se encontra no valor x = 1,85055 f(x) = 2,85027.

#########################################################################
"""
   Main loop
"""
if __name__ == "__main__":
   env = Environment(maxgenerations=50, optimum=2.85026911722)
   env.run()

Executando o código acima, temos o seguinte resultado no console. (A partir da geração 26 já se tem o valor máximo da função a ser buscada):

generation:  25
best:        Individual chromosome="1111001100101010101110" score=2.84947534214
======================================================================
generation:  26
best:        Individual chromosome="1111001100101111011110" score=2.84980345657
======================================================================
generation:  27
best:        Individual chromosome="1111001100111111011110" score=2.85027356577
======================================================================
generation:  28
best:        Individual chromosome="1111001100111111011110" score=2.85027356577
======================================================================
generation:  29
best:        Individual chromosome="1111001100111111011110" score=2.85027356577
======================================================================
generation:  30
best:        Individual chromosome="1111001100111111011110" score=2.85027356577
======================================================================
generation:  31
best:        Individual chromosome="1111001100111111011100" score=2.85027360267

Como se pode observar, algoritmos genéticos prova-se ser bastante eficiente na solução de problemas de otimização, garantido convergir à solução ótima. É claro, que há casos de problemas mais complexos, com diversas regiões de mínimos locais, que exigem do projetista uma análise mais refinada na forma de como o cromossomo é codificado, (representação da solução no algoritmo genético) e além de vários parâmetros do algoritmo que podem ser escolhidos para melhorar o seu desempenho, adaptando-o às características particulares de determinadas classes de problemas. Entre eles os mais importantes são: o tamanho da população, o número de gerações, a probabilidade de cross-over e a probabilidade de mutação.

A influência de cada parâmetro no desempenho do algoritmo depende da classe de problemas que se está tratando. Assim, a determinação de um conjunto de valores otimizado para estes parâmetros dependerá da realização de um grande número de experimentos e testes. Na maioria da literatura os valores encontrados estão na faixa de 60 a 65% para a probabilidade de cross-over e entre 0,1 e 5% para a probabilidade de mutação. O tamanho da população e o número de gerações dependem da complexidade do problema de otimização e devem ser determinados experimentalmente. No entanto, deve ser observado que o tamanho da população e o número de gerações definem diretamente o tamanho do espaço de busca a ser coberto. Existem estudos que utilizam um AG como método de otimização para a escolha dos parâmetros de outro AG, devido à importância da escolha correta destes parâmetros.


É isso pessoal, recomendo a leitura deste artigo do autor Márcio Nunes de Miranda (UFRJ) utilizado como referência principal para a construção deste tutorial. O download do código acima está disponível neste link. Espero que tenha sido útil!

No próximo post, irei trazer um problema mais "realista" de otimização para ser solucionado pela técnica evolucionária dos algoritmos genéticos.

Até a próxima!

Marcel P. Caraciolo