Computação Evolucionaria

Abstract - Agmon

This work aims to give a brief introduction to the vast field of Evolutionary Computation. Highlighting especially its main algorithms such as Genetic Algorithms, Evolution Strategies and Evolutionary Programming. Besides exemplify a simple Evolutionary Algorithm, which was modeled using the framework Paradiseo [4].

Resumo - Agmon

Este trabalho tem como objetivo fazer uma breve introdução ao imenso campo da Computação Evolucionária. Com destaque especialmente aos seus principais algoritmos, como Algoritmos Genéticos, Estratégias Evolutivas, e Programação Evolucionária. Além de exemplificar um simples Algoritmo Evolucionário, que foi modelado utilizando o framework Paradiseo[4].

Introdução - Agmon

A Computação Evolucionária é um campo de pesquisa que faz uso de simulações computacionais para analisar problemas de alta complexidade. Tais problemas são muito mais complexos que aqueles analisados matematicamente, pois não possuem linearidade, ou algum comportamento padronizado. Logo, não existem fórmulas matemáticas que possam representá-los, ou fazer uma previsão de seus comportamentos ao longo do tempo.

        Dentro da Computação Evolucionária, os Sistemas Evolucionários são instâncias bem específicas de uma classe geral dos Algoritmos Evolucionários. Resumidamente, um Sistema Evolucionário é uma estrutura que se altera ao longo do tempo. Dentro da Biologia, este conceito é utilizado com uma conotação diferente, se referindo ao Sistema Evolucionário Darwiniano. No qual, a Computação Evolucionária abstrai alguns conceitos, como competição, mutação e herança genética, por exemplo.

Algoritmos Evolucionários - Luciano

História:

Os primeiros trabalhos envolvendo AEs são datados da década de 1930, quando sistemas evolutivos naturais passaram a ser investigados como algoritmos de exploração de múltiplos picos de uma função objetivo. Porém, apenas com o maior acesso a computadores, a partir da

década de 1960, é que se intensificaram os desenvolvimentos de AEs (De Jong, 2006), com a realização de diversos estudos teóricos e empíricos.

Descrição:

        Algoritmos evolucionários são métodos de busca e otimização baseados nos mecanismo de evolução das espécies. Baseado no darwinismo e/ou neodarwinismo (se contarmos com a base genética) temos que quando mais adaptado o indivíduo no seu ambiente, maior a chance de sobreviver e produzir descendentes.

        Um Algoritmo Evolucionário é geralmente composto por cinco componentes:

        * Representação genética das potenciais soluções.

        * Uma formula para criar a população inicial.

* Uma função de avaliação para medir a adaptação da solução ao                   problema.

        * Operadores genéticos que auxiliam a gerar descendentes.

        * Parâmetros específicos de cada algoritmo.

        Diferentes de outras técnicas de busca e otimização, que constroem apenas uma solução iterativa, os AEs trabalham com conjuntos de soluções, que reduz em muitos casos o número de iterações para a obtenção das soluções, pois reduz o tempo de convergência. Trabalhos mais recentes (1990) desenvolveram AEs específicos para as áreas de Aprendizado de Máquina (AM) e construção de modelos probabilísticos. Assim, o desempenho dos AEs tem aumentado significativamente com o estudo de Algoritmos de Estimação de Distribuição (AEDs).

Ramos distintos de pesquisas desenvolveram técnicas computacionais que construíram os AEs. A Programação Evolutiva (PE), Estratégias Evolutivas (EE) e Algoritmos Genéticos (AG) foram fundamentais para a área e foram chamados de AE’s Canônicos.        

Algoritmos Genéticos

Historia

Os Algoritmos Genéticos (AGs) são algoritmos probabilísticos e foram inicialmente propostos pelo Professor John Holland da Universidade de Michigan em meados da decada de 70, com o ideal inicial de tentar imitar etapas do processo evolutivo natural das especies adicionando essas etapas a um algoritmo computacional, mas, somente a partir dos anos 80, é que realmente começaram a se popularizar.[1]

Descrição

O  algoritmo tem a seguinte característica: a partir de um conjunto de soluções, que são representadas por cromossomas, chamandos de população, então, com as soluções obtidas a partir da população são reutilizadas para obter uma nova população. Essa soluções são escolhidas a partir da adequação dos cromossomas que formam a população, assim, cromossomas que melhor se adaptam então serão escolhidos para pertencer a nova população. Portanto essa nova geração vai ter apenas os melhores cromossomas que tendem ter melhor chance de reprodução.

Esse processo é repetitivo sendo concluído quando a condição é satisfeita (por exemplo o número de populações ou o aperfeiçoamento da melhor solução).

Esta particular descrição to algoritmo genético é intencionalmente abstrata por que de certa forma, o termo algoritmo genético tem dois significados. Numa interpretação formal, o algoritmo genético refere-se ao modelo introduzido e estudado por John Holland  e seus estudantes (e.g., DeJong). Ainda hoje a maior parte da teoria existente sobre algoritmos genéticos aplica-se totalmente ou primariamente ao modelo introduzido por Holland, assim como variações do que é referido em seu paper como algoritmo genético canônico. Avanços recentes na teoria da modelagem do algoritmo genético também aplicam-se primariamente ao algoritmo genético canônico (Vose, 1993).[2]

Numa utilização mais abrangente do termo, um algoritmo genético é qualquer modelo baseado em população que utiliza operadores de seleção e re-combinação para gerar novos pontos amostrais em um espaço de busca. Muitos algoritmos genéticos foram introduzidos por pesquisadores de uma perspectiva experimental. A maior parte deles tem interesse no algoritmo genético como ferramenta de otimização.[2]

Esboço Básico do Algoritmo Genético[3]

1. [Início] Gere uma população aleatória de n cromossomas (soluções adequadas para o problema)
2. [Adequação] Avalie a adequação f(x) de cada cromossoma x da população
3. [Nova população] Crie uma nova população repetindo os passos seguintes até que a nova população esteja completa

1. [Seleção] Selecione de acordo com sua adequação (melhor adequação, mais chances de ser selecionado) dois cromossomas para serem os pais
2. [Cruzamento] Com a probabilidade de cruzamento cruze os pais para formar a nova geração. Se não realizar cruzamento, a nova geração será uma cópia exata dos pais.
3. [Mutação] Com a probabilidade de mutação, altere os cromossomas da nova geração nos locus (posição nos cromossomas).
4. [Aceitação] Coloque a nova descendência na nova população

1. [Substitua] Utilize a nova população gerada para a próxima rodada do algoritmo
2. [Teste] Se a condição final foi atingida, pare, e retorne a melhor solução da população atual
3. [Repita] Vá para o passo 2

Bibliografia: [1]http://www.sbmac.org.br/bol/bol-2/artigos/satoru/satoru.html

...