Heurísticas - ia

Páginas: 6 (1465 palavras) Publicado: 7 de novembro de 2012
UNIVERSIDADE NOVE DE JULHO – UNINOVE

DAISY MONTE MACHADO
RENATO SANTANA BRITO
RICARDO RAMOS DOS SANTOS

META-HEURÍSTICAS

SÃO PAULO
2012

DAISY MONTE MACHADO
RENATO SANTANA BRITO
RICARDO RAMOS DOS SANTOS

META-HEURÍSTICAS

Atividade de IA II

Linha de pesquisa: Meta-heurísticas
Professor: Adilson Pereira Marques

SÃO PAULO
2012

INDICE

1 BUSCA TABU...................................................................................................................................... 4
2 SIMULATED ANNEALING ................................................................................................................. 7
3 OTIMIZAÇÃO DE COLÔNIA DE FORMIGAS - OCF.......................................................................... 9
4 ALGORITMOSGENÉTICOS ............................................................................................................ 10
3 CONCLUSÃO .................................................................................................................................... 12

4

Busca Tabu

A meta heurística busca tabu, é utilizada quando o intuito é evitar percorrer o
caminho já visitado, criando umalista de estados já visitados.
O seu algoritmo evita retornar ao local já visitado previamente, com o intuito de
atingir um resultado ótimo ou próximo ao ótimo global.
A busca tabu é capaz de armazenar em suas memórias flexíveis os espaços já
percorridos. Para que o algoritmo seja capaz de encontrar “boas soluções”, são
utilizadas técnicas de memória adaptativa. Uma “boa solução” está próximodo ótimo
global. Assim como outras metas heurísticas, a busca tabu consome tempo de
processamento e de experiências percorrendo diversos caminhos, porem é
considerado um tempo de processamento aceitável.
A seguir é apresentado um exemplo:

Figura 1.1 – Solução inicial

5

Figura 1.2 – Ótimo local

Figura 1.3 – Elemento tabu

Figura 1.4 – Ótimo global

6

O ponto de partida seda à solução inicial (figura 1.1) que é determinada dentre
diversos critérios possíveis e que em nosso exemplo é utilizado os Correios. Com o
tempo (iteração) a busca (carteiro) vai caminhando para os vizinhos buscando a
melhor solução (figura 1.2), sendo que não é possível passar por um caminho já
visitado (figura 1.3). Este controle se da porque é criada uma lista tabu armazenando
todos oscaminhos percorridos anteriormente e permanece na memória por um
determinado tempo ou quantidade de iterações. Espera-se que seja encontrado um
ótimo global ou uma solução próxima (figura 1.4).
A busca tabu pode ser aplicada em diferentes áreas de atuação como:


Design



Scheduling



Produção, inventário e investimento



Telecomunicações



Roteamento



Lógica einteligência artificial



Otimização de grafos



General Combinational Optimization



Tecnologia



Location and Allocation

É possível aplicar a BT em quase qualquer problema de otimização para ter
resultados próximo do ótimo ou até mesmo uma solução ótima.

7

Simulated Annealing

A meta heurística simulated annealing, é usada para otimização de determinadasaplicações e para proporcionar custos baixos.
Essa meta heurística é baseada no processo da termodinâmica, onde é feita uma
analogia ao processo térmico, utilizado em metalurgias por exemplo, e onde aquecese um objeto sólido em uma temperatura alta e depois resfria-se o mesmo
lentamente, até atingir a estrutura desejada e estável.
Essa analogia consiste basicamente, numa busca local eprobabilística, onde se
busca atingir um determinado resultado e objetivo através da função com menor
custo.
Na aplicação escolhida temos um carteiro de uma determinada agência, que
necessita fazer todas as entregas necessárias através do mais curto, mais barato e
mais rápido percurso, sem ainda passar por um mesmo local duas vezes.
Nessa heurística o carteiro tem várias variantes opcionais,...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Heuristica
  • Heurísticas
  • Heurística
  • HEURISTICA
  • Heurística
  • Heuristica
  • Heuristica
  • Heurísticas

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!