Tabu Search (Busca Tabu) e
Algoritmos Genéticos
Prof. Alexandre Monteiro
Recife
‹#›
Contatos

Prof. Guilherme Alexandre Monteiro Reinaldo

Apelido: Alexandre Cordel

E-mail/gtalk: [email protected]
[email protected]

Site: http://www.alexandrecordel.com.br/fbv

Celular: (81) 9801-1878
Tabu Search (Busca Tabu)
Meta - heurísticas
Tabu Search

Fred Glover e Pierre Hansen.

é um método de busca local


explorar o espaço de soluções movendo-se de uma solução
para outra que seja seu melhor vizinho.
uma estrutura de memória para armazenar as soluções
geradas
•Ou características destas
Algoritmo BT




Começando com uma solução inicial s0, a cada iteração,
Um subconjunto V da vizinhança N(s) da solução corrente s
é explorado
O membro s0 de V com melhor valor nesta região segundo a
função f(:) torna-se a nova solução corrente
mesmo que s0 seja pior que s.
Evitando Ciclos



existe uma lista tabu T, a qual é uma lista de
movimentos proibidos.
A lista tabu clássica contém os movimentos reversos
aos últimos |T| movimentos realizados
|T| funciona como uma fila de tamanho fixo,
• isto é, quando um novo movimento é adicionado à lista, o
mais antigo sai.

Assim, na exploração do subconjunto V da vizinhança
N(s) da solução corrente s, ficam excluídos da busca os
vizinhos s0 que são obtidos de s por movimentos m que
constam na lista tabu
Função de Aspiração

A lista tabu
•por um lado, reduz o risco de ciclagem
•por outro, também pode proibir movimentos
para soluções que ainda não foram visitadas

Função de aspiração é um mecanismo que retira, sob certas
circunstâncias,
•o status tabu de um movimento.
Aspiração por Objetivo




Mais precisamente, para cada possível valor v da
função objetivo existe um nível de aspiração A(v):
• uma solução s0 em V pode ser gerada se f(s0) <
A(f(s)), mesmo que o movimento m esteja na lista
tabu.
A função de aspiração A é tal que,
• para cada valor v da função objetivo, retorna outro
valor A(v) que representa o valor que o algoritmo
aspira ao chegar de v.
Um exemplo simples de aplicação desta idéia é
considerar A(f(s)) = f(s*) onde s* é a melhor solução
encontrada até então.
Neste caso, aceita-se um movimento tabu somente se
ele conduzir a um vizinho melhor que s*. Esta é a
chamada aspiração por objetivo.
Critério de Parada




Duas regras são normalmente utilizadas de forma a
interromper o procedimento.
Pela primeira, pára-se quando é atingido um certo
número máximo de iterações sem melhora no valor da
melhor solução.
Pela segunda, quando o valor da melhor solução chega
a um limite inferior conhecido (ou próximo dele).
Esse segundo critério evita a execução desnecessária
do algoritmo quando uma solução ótima é encontrada
ou quando uma solução é julgada suficientemente
boa.
Parâmetros Principais

a cardinalidade |T| da lista tabu,

a função de aspiração A,


a cardinalidade do conjunto V de soluções vizinhas testadas
em cada iteração e
BTmax, o número máximo de iterações sem melhora no
valor da melhor solução.
Estratégias de Intensificação


Uma estratégia típica é retornar à uma solução
já visitada para explorar sua vizinhança de
forma mais efetiva.
Outra estratégia consiste em incorporar
• atributos das melhores soluções já encontradas
• estimular componentes destas soluções a tornar
parte da solução corrente.

Um critério de término
• tal como um número fixo de iterações, é utilizado
para encerrar o período de intensificação.
Busca Tabu
Fred Glover (1986) & Pierre Hansen
(1986)
1ª Idéia: Utilizar heurística de
descida
1ª Idéia: Utilizar heurística de
descida
1ª Idéia: Utilizar heurística de
descida
Problema: Fica-se preso no primeiro ótimo local
2ª Idéia: Mover para o melhor
vizinho
O melhor vizinho pode ser de piora!
2ª Idéia: Mover para o melhor
vizinho
Problema: Ciclagem
3ª Idéia: Criar Lista Tabu
TABU
3ª Idéia: Criar Lista Tabu
Problemas com uma Lista Tabu de
soluções.

É computacionalmente inviável armazenar todas as
soluções geradas!
• Idéia: Armazenar apenas as últimas |T| soluções geradas
• Observação: Uma lista com as |T| últimas soluções evita
ciclos de até |T| iterações
• Problema: Pode ser inviável armazenar |T| soluções e testar
se uma solução está ou não na Lista Tabu
• Idéia: Criar uma Lista Tabu de movimentos reversos

Problema: Uma Lista Tabu de movimentos pode ser
muito restritiva (impede o retorno a uma solução já gerada
anteriormente e também a outras soluções ainda não geradas).
Algoritmos Genéticos
Meta - heurísticas
Algoritmos Genéticos


São técnicas de busca e otimização.
É a metáfora da teoria da evolução das espécies iniciada pelo
Fisiologista e Naturalista inglês Charles Darwin.

Desenvolvido por John Holland (1975) e seus alunos.

Popularizado por David Goldberg (1989).

Princípio básico: Evolução natural

A evolução natural pode ser vista como um processo de
otimização no qual:
•
Indivíduos e populações competem entre si por
recursos
- Alimento
- Água
- Abrigo
Teoria da Evolução

1859 - Charles Darwin publica o livro “A
Origem das Espécies”:
.
Charles
Darwin
“As espécies evoluem pelo
princípio da seleção
natural e sobrevivência do
mais apto.”
Teoria da Evolução

1865- Gregor Mendel apresenta experimentos
do cruzamento genético de ervilhas.
•Pai da genética.
.
Gregor
Mendel

A Teoria da Evolução começou a partir da
conceituação integrada da seleção natural
com a Genética.
Introdução

Principal motivação para o estudo da computação evolutiva
através de algoritmos genéticos é:
•Otimização de processos complexo e que
possuem um grande número de variáveis

O que é otimizar?
26
Otimização

É a busca da melhor solução para um dado problema.
•Consiste em tentar várias soluções e usar a
informação obtida para conseguir soluções
cada vez melhores.

Exemplo de otimização:
•Telespectador através de ajuste na antena
da televisão otimiza a imagem buscando
várias soluções até alcançar uma boa
imagem.
Otimização

As técnicas de otimização, geralmente, apresentam:
Espaço de busca: onde estão todas as
possíveis soluções do problema;
• Função objetivo: utilizada para avaliar as
soluções produzidas, associando a cada
uma delas uma nota.
Introdução

Idéia principal da Computação Evolutiva é o seguinte:
• Indivíduos
mais bem sucedidos na sobrevivência e
atração de um parceiro terão, relativamente,
mais descendentes
-
Espalham seus genes
• Indivíduos
mal sucedidos geram poucos ou
nenhum descendente
-
Tendem a desaparecer
29
Computação Evolutiva

Sistemas utilizados para a resolução de
problemas
•Utilizam modelos computacionais baseados na
teoria da evolução natural

Pesquisas tiveram início na década de 50

Principal técnica:
•Algoritmos genéticos
30
Algoritmos Genéticos (AGs)


Métodos adaptativos que podem ser utilizados para resolver
problemas de busca e otimização
Os AGs são baseados nos processos genéticos de organismos
biológicos
•Populações de soluções evoluem, ao longo
das gerações
- De acordo com os princípios de seleção natural
31
Algoritmos Genéticos

Origem:
•Desenvolvido por John Holland e sua
equipe na década de 50
- Popularizado por David Goldberg

Objetivo:
• Desenvolver
sistemas artificiais baseados
nos mecanismos dos sistemas naturais
32
Algoritmos Genéticos

Podem encontrar soluções para problemas do mundo real,
dada as seguintes condições:
• Problemas
devem ser adequadamente
codificados
• Deve
haver uma forma de avaliar as
soluções apresentadas
33
Algoritmos Genéticos

Funcionamento:
População inicial
População final
Avaliação
População atual
Seleção
Reprodução
34
Algoritmos Genéticos

Utilizam uma população de soluções
candidatas (indivíduos)

Otimização ocorre em diversas gerações

A cada geração, acontece:
•Mecanismos de seleção selecionam os
indivíduos mais aptos
•Operadores de reprodução geram novos
indivíduos
35
Algoritmos Genéticos


Cada indivíduo representa uma possível solução para um dado
problema
A cada indivíduo é associado um valor de aptidão
•Mede o quão boa é a solução que ele representa

Indivíduos mais aptos têm mais oportunidades de serem
reproduzidos
36
Princípios básicos dos AGs

Indivíduo

Codificação

Função de aptidão

Reprodução
37
Indivíduo

Possível solução para um dado problema
• Também
chamado de cromossomo ou string
 Codificado
como vetor de características
 População
• Conjunto
de indivíduos
38
Codificação

Cada indivíduo é codificado por um conjunto
de parâmetros (genes)
•Genes podem assumir valores:
-

Binários (0; 1)
Inteiros (-2; -1; 0 ; 1; 2; 3...)
Reais (-2,33; 0; 3,45; 2,5 x 1024)
Parâmetros são combinados para formar
strings ou vetores (cromossomos)
•Exemplo:
Xi = [ 2 1 8 0 -2 -4 1 ]
39
Codificação

Genótipo
•

Conjunto de parâmetros representado por um
cromossomo (hereditário, genoma)
Fenótipo
•
Produto da interação de todos os genes (o homem é
produto do meio)
40
Função de aptidão

Mede o grau de aptidão de um indivíduo
• Aptidão = probabilidade do indivíduo sobreviver para a
próxima geração

Depende do objetivo da aplicação que se deseja
resolver
Uma mesma tarefa pode ter diferentes objetivos
• Ex. projeto de ponte
•
- Menor Custo
- Menor tempo de construção
- Maior capacidade de carga
41
Função de aptidão

É aplicada ao fenótipo do indivíduo
•O genótipo precisa ser decodificado,
recuperando o fenótipo associado

Cada aplicação tem sua própria função de
aptidão
42
Reprodução

Permite obtenção de novos indivíduos

Utiliza operadores genéticos
•Transformam a população
- Crossover (cruzamento ou recombinação)
- Mutação
43
Crossover

Recombinação de características dos pais durante a reprodução
•Permite que as próximas gerações herdem essas
características

Funcionamento
• Escolhe
dois indivíduos e troca trechos dos
cromossomos entre eles

Exploração rápida do espaço de busca
44
Crossover

Diversas variações
•Um ponto
- Mais comum
•Dois pontos
•Multi-pontos
•Uniforme
45
Crossover 1 ponto
Ponto de crossover
Pai 1
0 1 0 0 0 1 1 Pais
Filho A
0 1 0 0 1 0 1 Filhos
Pai 2
0 0 1 0 1 0 1
Filho B
0 0 1 0 0 1 1
46
Crossover de 2 pontos
Pai 1
0 1 0 0 0 1 1 Pais
Filho A
0 1 0 0 1 1 1 Filhos
Pai 2
0 0 1 0 1 0 1
Filho B
0 0 1 0 0 0 1
47
Crossover uniforme
• Gerar uma máscara de bits aleatórios e combinar os
bits dos pais de acordo com a máscara gerada
• 1 => Pai 1 e 0 => Pai 2
Mascara: 0 1 0 1 0 0 0
Pai 1
0 1 0 0 0 1 1 Pais
Filho A
0 1 1 0 1 0 1 Filhos
Pai 2
0 0 1 0 1 0 1
Filho B
0 0 0 0 0 1 1
48
Problema
Máximo global
f(x) = x sen(10 px) + 1
3,0
Máximo local
2,0
1,0
0,0
-1,0
-1,0
Máximo global:
x = 1,85055
f(x) = 2,85027
-0,5
0,0
0,5
x
1,0
1,5
2,0
As Gerações do Problema
f(x) = x seno(10px) + 1.0
3,0
População Inicial
2,5
2,0
1,5
1,0
0,5
0,0
-0,5
-1,0
-1,0
-0,5
0,0
0,5
1,0
x
População gerada aleatóriamente
1,5
2,0
As Gerações do Problema
3,0
Primeira Geração
f(x) = x sen(10px) + 1.0
2,5
2,0
1,5
1,0
0,5
0,0
-0,5
-1,0
-1,0
-0,5
0,0
0,5
x
Pouca melhoria
1,0
1,5
2,0
As Gerações do Problema
3,0
f(x) = x sen(10px) + 1.0
2,5
Geração 25
2,0
1,5
1,0
0,5
0,0
-0,5
-1,0
-1,0
-0,5
0,0
0,5
x
1,0
1,5
2,0
A maioria dos indivíduos encontraram o máximo global
As Gerações do Problema 2
Função objetivo
3,0
Média
Melhor
2,5
2,0
1,5
1,0
0,5
0
5
10
15
20
25
Geração
Na geração 15 o AG já encontrou o ponto máximo
Mutação




Introdução e manutenção da diversidade
genética
• Aplicado a cada indivíduo após crossover
Altera aleatoriamente um ou mais genes no
cromossomo
Assegura que a probabilidade de atingir
qualquer ponto do espaço de busca nunca será
zero
Taxa de mutação pequena Pm @ 0.001
54
Mutação
Antes da mutação
0 1 0 0 0 1 1
Após a mutação
0 1 1 0 0 1 1
55
Seleção

Escolhe preferencialmente, embora não exclusivamente,
indivíduos com maiores notas de aptidão
• Procura

manter a diversidade da população
Indivíduos mais aptos têm mais oportunidades de serem
reproduzidos
56
Seleção pela roleta
Método da Roleta baseado em Aptidão Relativa
Indivíduo Aptidão Aptidão
Si
f(Si)
Relativa
S1 10110
2.23
0.14
S2 11000
7.27
0.47
S3 11110
1.05
0.07
S4 01001
3.35
0.21
S5 00110
1.69
0.11
S1
S5
S4
S2
S3
57
Elitismo


Indivíduo de maior desempenho é automaticamente
selecionado
Evita modificações deste indivíduo pelos operadores genéticos
•Utilizado para que os melhores indivíduos não
desapareçam da população pela manipulação
dos operadores genéticos
58
Critério de parada

Tempo de execução

Número de gerações

Valor de aptidão mínimo e/ou médio

Convergência
•Nas últimas k iterações não houve melhora
nas aptidões
59
Escolha de parâmetros

Escolhidos de acordo com o problema
• Quantos
cromossomos em uma população
- Poucos  efeito pequeno do crossover
- Muitos  aumenta tempo de computação
• Taxa
de mutação
- Baixa  mudanças lentas
- Alta  traços desejados não são mantidos (caos)
60
Escolha de parâmetros

Outros parâmetros
• Quantos
indivíduos selecionados para
reprodução?
• Quantos pontos de crossover?
• Critério para medir aptidão?

Manter limites no tamanho da população e complexidade
da análise
• Algoritmo
pode se tornar ineficiente
61
Aplicações

Otimização de função numérica

Otimização combinatória
•

Projetos
•

Determinação de Árvores Filogenéticas
Projeto de pontes
Aprendizado de Máquina
• Determinação dos parâmetros de Redes Neurais
Artificiais em problemas de Bioinformática
62
Aplicações de AGs

O desenvolvimento de um AG inclui os seguintes passos:
•Especificar o problema, limites e critério
ótimo
•Representar o domínio do problema como
um cromossomo
•Definir a função de avaliação
•Construir os operadores genéticos
•Rodar o AG
63
Algoritmos Genéticos
Caixeiro Viajante
O Problema

Dado um número de cidades, encontrar o
caminho mais curto passando por todas as
cidades uma única vez
• Função Objetivo = Distância Total Percorrida
Representação
Crossover

Crossover baseado em posição


São selecionadas n cidades.
Cada filho mantém a posição das cidades selecionadas de um pai
Crossover

Crossover baseado em ordem


São selecionadas n cidades.
Cada filho herda a ordem das cidades selecionadas de um pai
Mutação

Mutação baseada na troca de posição de uma cidade

Mutação baseada na troca da ordem de duas cidades
Algoritmos Genéticos –
Referência Básica da Aula

Estefane Lacerda – Introdução aos Algoritmos Genéticos. Em
Sistemas Inteligentes – Aplicações a Recursos Hídricos e Ciências
Ambientais, 1999
• http://www.dca.ufrn.br/~estefane/metaheuristicas/index.html

Stuart Russell and Peter Norvig, Artificial Intelligence - A Modern
Approach. Prentice Hall, 1995.