Metahuerísticas:

Algoritmos Genéticos

Sistemas de Informação/Ciências da Computação – UNISUL

Aran Bey Tcholakian Morales, Dr. Eng.

(Apostila 8)

Classificação de métodos heurísticos: os métodos heurísticos podem

ser classificados como: heurísticas específicas (métodos construtivos e

métodos de refinamento) e em meta-heurísticas (busca tabu, algoritmos

genéticos, entre outros métodos).

2

Meta-heurísticas

Características das meta-heurísticas:

– meta-heurísticas são estratégias que “guiam” o processo de busca;

– exploram o espaço de busca para encontrar soluções próximas ao ótimo;

– são algoritmos aproximados e geralmente não determinístico;

– incorporaram mecanismos para evitar ficarem presas em um

ótimo local;

– não são específicas para um determinado problema;

– podem fazer uso de conhecimento específico do problema por

meio de heurísticas;

– meta-heurísticas mais avançadas utilizam a experiência obtida durante a

busca (através de uma memória) para guiar a busca.

3

Meta-heurísticas

4

Algoritmos Genéticos

Algoritmos Genéticos: Definição

Os Algoritmos Genéticos são procedimentos adaptativos, para a busca

de soluções em espaços complexos, baseados na evolução biológica, com

padrões de operações, baseados no principio darwinista de seleção

natural e sobrevivência dos indivíduos que melhor se adaptarem ao

ambiente.

Darwin (1809 - 1882):

Como se processa a Evolução ?

Pela Adaptação

Fatores determinantes do processo adaptativo

Variações Hereditárias e Seleção Natural

“Quanto melhor um indivíduo se adaptar ao seu meio ambiente,

maior será sua chance de sobreviver e gerar descendentes”

6

As variações hereditárias que ocorrem em uma população podem

ser vantajosas ou não para os indivíduos que as experimentam.

A Seleção Natural age eliminando os portadores de variações que

dificultam ou impedem a sobrevivência e mantendo aqueles cujas

variações permitem melhor explorar o ambiente.

É desta maneira que age a seleção natural, atuando sobre as

variações hereditárias, eliminando os indivíduos portadores de

variações que dificultam ou impedem a sobrevivência, e mantendo

aqueles indivíduos cujas variações permitem melhor explorar o

ambiente.

Algoritmos Genéticos: Definição

7

Aqueles indivíduos mais aptos aos requerimentos ambientais

sobrevivem e se reproduzem deixando descendentes, e os menos

aptos acabam desaparecendo.

Com o passar das gerações, os indivíduos melhores dominam a

espécie.

Algoritmos Genéticos: Definição

Características dos AG As principais características dos A.G. são:

• Trabalham com uma população de indivíduos (cromossomos),

cada um representa uma solução do problema.

• Um cromossomo é uma estrutura de dados que representa uma

possível solução do problema.

• O conjunto de todas as configurações que o cromossomo pode

assumir forma o espaço de busca.

• O primeiro passo para resolver um problema com AG, é

representar os parâmetros do problema na forma de um cromossomo.

• O conjunto de parâmetros representados por um cromossomo

particular é o genótipo. Estes parâmetros (genes) são colocados em

um indivíduo (cromossomos), de forma codificada.

• Depois deve-se definir uma forma de avaliar os cromossomos

(aptidão ou fitness ).

• De uma geração a outra, os indivíduos competem por recursos,

aqueles mas aptos aos requerimentos ambientais, serão os que

poderão, com maior probabilidade, deixar descendentes. Assim uma

nova população é gerada, produzida por seleção dos melhores

indivíduos desde a geração corrente.

Características dos AG

Funcionamento dos A.G.

Começo

Inicialização;

Enquanto not ( Fim da Evolução )

t := t + 1; { próxima geração}

Operadores_Genéticos;

P(t) := P’(t); { próxima população }

Fim Enquanto

Fim

Inicialização

t:= 0; { tempo zero }

P(t) ; { Geração da População Inicial }

Avaliar P(t); { Avaliação da População }

Fim Inicialização

Operadores_Genéticos

Seleção de Indivíduos P’ (Para gerar descendentes )

Recombinar P’ (Recombinação dos genes dos pais )

Avaliar P’(t)

Fim Operadores_Genéticos

Funcionamento dos A.G.

12

Funcionamento dos A.G.

Funcionamento dos AG - Seleção

Seleção: inspirado no processo de seleção natural, o AG seleciona

os melhores cromossomos da população ( alta aptidão) para gerar

cromossomos filhos através de operadores genéticos.

Os cromossomos (os pais) são selecionados aleatoriamente,

utilizando um esquema de favorecer os melhores. Os pais são

selecionados com probabilidade proporcional a sua aptidão

( pi = fi / ( fi ) )

Selecionados os pais, os cromossomas são recombinados, utilizando

operadores genéticos, como o cruzamento (crossover) e a mutação.

18

Funcionamento dos AG - Seleção

Probabilidade de Seleção

0.18; 0.16; 0.15; 0.13; 0.11; 0.09; 0.07; 0.06; 0.03; 0.02

Números Randômicos

0.81; 0.32; 0.96; 0.01; 0.65; 0.42.

Funcionamento dos AG - Cruzamento

Cruzamento: Dado 2 indivíduos, eles são “cortados” aleatoriamente

em uma posição física, produzindo 2 segmentos.

A escolha randômica utilizada para saber onde os cromossomos são

cortados, depende de uma probabilidade.

Se o cruzamento não é aplicado, os filhos, são idênticos aos pais.

20

Exemplo:

Ind1 0 1 1 1 0 0 1 1 0 1 0

Ind2 1 0 1 0 1 1 0 0 1 0 1

A posição de corte escolhida é 5

Des1 0 1 1 1 0 1 0 0 1 0 1

Des2 1 0 1 0 1 0 1 1 0 1 1

Funcionamento dos AG - Cruzamento

Mutação: É aplicado a cada indivíduo, em cada posição do gene (locus).

A aplicação deste operador depende também de uma probabilidade.

0 1 1 0 0 1 1 0 1 0

0 1 1 0 0 1 1 0 1 0

Funcionamento dos AG - Mutação

1

0

Operadores Secundários:

Nicho e Espécies

Diplodismo

Outros Operadores.

Diferenciação dos AG

As Principais Características dos A.G. que o fazem diferentes das

outras técnicas de busca, são:

• São independentes do domínio do problema;

• Trabalham com string de caracteres, geralmente em código binário,

para representar um conjunto de parâmetros;

• São relativamente imunes à alta dimensionalidade, mínimos locais e

a ruídos;

• São um método indutivo, e não dedutivo, porque procuram

soluções através da justaposição de hipóteses;

• Usam regras probabilísticas para guiar a busca, e não regras

deterministas.

• Só necessitam informação concernente à qualidade da solução

produzida por cada conjunto de parâmetros (informação da função

objetivo). Não como os métodos de otimização, que requerem

informação derivada, ou completo conhecimento dos parâmetros e da

estrutura do problema.

• Consideram uma população de pontos, e não um só.

Aqui, encontra-se implícito o paralelismo dos algoritmos genéticos, já

que esses pontos vão evoluir juntos, compartir e disputar recursos, e

aqueles que melhor de adaptem aos requerimentos ambientais gerarão

descendentes.

Diferenciação dos AG

24

Exploitation significa exploração no sentido de tirar informações das

soluções encontradas e exploration diz respeito à exploração no

sentido de visitar pontos desconhecidos no espaço de busca na procura

de novas soluções.

Cruzamento e mutação, levam a exploration

Seleção dirige a busca na direção dos melhores pontos do espaço,

exploitation.

Diferenciação dos AG

25

Conceitos Biológicos

População, grupo de indivíduos os quais podem interagir, para por

exemplo produzir descendentes. Indivíduo, membro de uma

população.

Cada indivíduo contém um cromossomo, o qual representa uma

possível solução do problema a ser resolvido, isto é um ponto do

espaço de busca.

Cromossomo, biologicamente, um cromossomo é uma cadeia de

DNA, encontrada nas células. Os cromossomos contém genes, cada

um codificado como uma subseção de uma cadeia de DNA.

Os genes determinam as características de um indivíduo.

26

Gene, a unidade de herança fundamental, contendo um segmento de

DNA que codifica uma ou varias funções relativas e ocupa uma

posição fixa ( locus ) de um cromossomo.

O gene é a unidade de hereditariedade que é transmitida pelo

cromossomo e que controla as características do organismo.

Locus, posição física dos genes. Cada gene é capaz de ocupar só uma

posição particular no cromossomo.

Alelo, representa os valores que o gene pode assumir.

Genoma, é o conjunto completo de genes de um organismo.

Conceitos Biológicos

27

Crossover, é um operador genético, o qual forma um novo indivíduo.

Mutação, é um operador genético, o qual forma um novo indivíduo.

Evolução, é um processo de mudanças dado em uma população de

indivíduos.

Fitness ou aptidão , é um valor atribuído cada indivíduo, o qual

representa como esse indivíduo resolve as tarefas colocadas pelo

ambiente.

Uma função fitness é utilizada para mapear um indivíduo em um

valor.

Conceitos Biológicos

28

Geração, de uma geração a outra, os indivíduos competem por

recursos ambientais, aqueles mas aptos aos requerimentos

ambientais, serão os que poderão, com maior probabilidade, deixar

descendentes.

Genótipo, a composição genética contida no genoma. Na computação

evolutiva, representa a informação contida no cromossoma.

Fenótipo, características físicas de um indivíduo.

Na computação evolutiva, representa o objeto, estrutura ou organismo

construído a partir das informações do genótipo.

Conceitos Biológicos