Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

APLICAÇÃO DO ALGORITMO “COLÔNIA DE FORMIGAS”

No description
by

RAQUEL MONTEIRO

on 27 November 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of APLICAÇÃO DO ALGORITMO “COLÔNIA DE FORMIGAS”

Faculdade Escritor Osman Lins
Artificial
Intelligence
Professor: Rodrigo Lira
Equipe:
Mario Antônio
Raquel Monteiro
Data 27/11/2015
As Formigas habitam no planeta Terra a mais de 100 bilhões de anos.

Existem diversas espécies espalhadas pelo mundo e grande partes das espécies são cegas.

Desde a antiguidade muitos pesquisadores são atraidos por suas características.
Percorrem Longas distâncias
Carregam 100 vezes o seu próprio peso
Consome muita comida
Busca e coleta de alimento
De início elas saem aleatoriamente em busca de alimento
Quando elas encontram alimento retornam a Colônia e depositam Feromônio proporcional a quantidade de alimento encontrado
Ao encontrarem o rastro de feromônio elas começa a seguir, sendo assim elas não andam mais aletoriamente e sim seguem uma mesma trilha, sendo que os melhores e menores caminhos são reforçados.
A trilha de feromônio é reforçada a medida que outras formigam transitam na trilha (uma vez que mais feromônio é depositado). Quanto mais formigas passarem por um caminho predeterminado, mais tempo será necessário para o feromônio da trilha evaporar, porém ao reduzir a fonte de alimento , logo o feromônio começa a evapoar.
OBRIGADO!
O feromônio evapora com o tempo, dessa forma, os caminhos menos visitados perdem feromônio, levando as formigas a outros caminhos escolhidos pelas demais. Caso o feromônio não evaporasse a trilha tornaria-se altamente atrativa para as formigas e a exploração do espaço iria delimitar fortemente a fonte de alimento, por conta da quantidade de feromônio.
Neste contexto usando o comportamento das formigas reais para solucionar problemas reais foram criadas as formigas artificias para coordenar sociedade de agentes artificiais, elas são heurísticas construtivas, elas constroem soluções de forma probabilística utilizando a trilha de feromônio (artificial) que muda dinamicamente durante a execução do programa de modo a refletir a experiência já adquirida durante a busca.
Existem diversos algoritmos baseado no comportamentos das formigas, o objetivo é a otmização e a busca por soluções, onde as formigas reais são substituidas por formigas artifíciais e o feromônio por feromônio artifícial. As formigas são Heurísticas e Probabilísticas, constroem informações de duas formas: trilha de feromônio e informações Heurísticas
É um método ou processo criado com o objetivo de encontrar soluções para um problema.
Cidades são os vértices
As estradas definem as arestas
O problema do caixeiro-viajante consiste na procura de um circuito que possua a menor distância, começando numa qualquer cidade,entre várias, visitando cada cidade precisamente uma vez e regressando à cidade inicial.
Pseudo-Código Ant System
Ant Algorithm Simulator
Heurísticas:
Probabilísticas:
É um Tipo de amostragem, onde os elementos da amostra são selecionados aleatoriamente e todos eles possuem probabilidade conhecida de serem escolhidos.
Baseado no problema do caixeiro viajante
conj. dos locais ainda não visitados pelas formigas
Também associado a aresta (Tij) esta a heurística n que é a probabilidade da formiga visitar o local I depois do local j
O Algoritmo
O Algoritmo
Passos para a implementação de um algoritimo para um problema de otimização são os seguintes:
Passo 1:
Inicialização do Sistema onde se calcula a probabilidade de cada nó e define a quantidade de feromônio para cada interação e distribui as formigas de um modo aleatório entre os nós.
Passo 2:
Para cada interação definida cada formiga percorre todos os nós do grafo calculando em cada nó sua probabilidade de movimento.
Passo 3:
Verificar qual formiga obteve a melhor volta.
Passo 4:
Atualização do Feromônio onde é incrementado a quantidade de feromônio na melhor volta reduzindo a quantidade de feromônio nas demais voltas.
Ant System


O Ant System é o primeiro algoritmo que surgiu inspirado em Colônia de formigas. Desenvolvido por Marco Dorigo, Vitorio Maniezzo e Alberto Colorni em 1996.Tem como características a otimização e busca por soluções. A parti dele, foram desenvolvidas soluções de otimizações em Roteamento de Redes, Coloração de Mapas, Mineração de Dados, Sistema de Roteameneto de Veículos, busca por soluções em grafos dinâmicos como por exemplo usado no problema do caixeiro viajante.

O Feromônio
O Algoritmo
APLICAÇÃO DO ALGORITMO
“COLÔNIA DE FORMIGAS”
Seminário Artificial Intelligence
Problema do Caixeiro Viajante
Problema do Caixeiro Viajante
Problema do Caixeiro Viajante
A e B São parâmetros
A cada interação o feremônio depositado sofre uma evaporação seu valor é reduzido por uma contante de evaporação FE
Onde FE >=0 < 1
t : iteração atual
da heurística AS
(Ant System)
Sk : caminho completo
que interliga todas as cidades uma única vez, descoberta pela formiga k.

Lk : distância associada ao caminho completo Sk descoberto pela formiga k
O Caminho será igual ao caminho descoberto pela formiga.

A Distância será igual a distancia associada descoberta pela formiga
Se distancia associada ao
caminho completo Sk for menor que a distancia, então
Full transcript