Heurística Computacional Ant Colony System – Relatório

Universidade Federal de Goiás – EMC

Heurística Computacional

Ant Colony System – Relatório

Uyara Ferreira Silva

 Prof. Leonardo Brito

Introdução        

        Este relatório contém o passo a passo do ACS, todos os cálculos necessários e o que são cada uma das variáveis e constantes envolvidas. Ao final mostra uma explicação detalhada do algoritmo desenvolvido no MATLAB, encontrado pronto. Este algoritmo resolve o problema do caixeiro viajante.  

1. Swarm – enxame

        Swarm intelligence é o estudo de sistemas computacionais inspirados na “inteligência coletiva”, que emerge através da cooperação de um grande número de agentes homogêneos no ambiente. Tal inteligencia é descentralizada, alto organizável e distribuída em todo um ambiente.

Na natureza, tais sistemas são usados para resolver problemas, tais como, busca eficaz de alimento, evasão da presa ou re-localização da colônia.

        As informações são normalmente armazenadas ao longo dos agentes homogêneos, ou são armazenadas ou comunicadas no próprio ambiente, como através do uso de feromônios em formigas, dança em abelhas e proximidade em peixes e aves.

        O paradigma é composto por dois sub-campos dominantes. 1) Otimização da colônia de formigas, que investiga algoritmos probabilísticos inspirados na estigmergia (mecanismo de coordenação indireta entre agentes ou ações) e no comportamento de forrageamento (busca e exploração de recursos alimentares) de formigas e 2)Otimização de partículas do enxame que investiga algoritmos probabilísticos inspirados na flocagem, escolaridade e pastoreio. Computação evolutiva e inteligencia coletiva são consideradas estratégias adaptativas e normalmente são aplicadas a busca e otimização de domínios.

2. Metáfora

        Formigas inicialmente vagam aleatoriamente em torno de seu meio ambiente. Uma vez que a comida é localizada a formiga vai começar a lançar feromônios no ambiente. Numerosas viagens entre a comida e o ninho são realizadas e se a mesta rota que leva a comida é seguida, então feromônios adicionais são lançados, feromônios também decaem no ambiente, de modo que os caminhos mais velhos são menos prováveis de serem seguidos. Outras formigas podem descobrir o mesmo caminho para a comida e por sua vez, pode segui-lo e também estabelecer feromônio. Um feedback positivo da rota lança mais e mais formigas para caminhos mais produtivos, que por sua vez são aperfeiçoados pelo uso.

3. Estratégias

        O objetivo da estratégia é explorar a informação histórica e heurística para a construção de soluções candidatas e dobrar as informações aprendidas a partir da construção de soluções para a história. Soluções são construídas passo a passo de uma forma probabilística. A probabilidade de seleção de um componente é determinado pela contribuição do componente de heurística para o custo global da solução e a qualidade das soluções.

O histórico é atualizado proporcionalmente à qualidade da melhor solução conhecida e é reduzido proporcionalmente para o uso de soluções discretas.

4. Procedimento

        A escolha da aresta a ser seguida pela formiga é feita da seguinte maneira:

. se q < q0,

        Prs  = 1, se s = arg max {τru . Ηruβ}

        Prs  = 0, caso contrário.

. se q > q0,

        Prs  =     ( τrs )α  . ( ηrs )β

                        -------------------------------------

                        Σkc ( τrs )α  . ( ηrs )β

        Prs  = 0, caso contrário.

        Atualização do feromônio ao fim da iteração para uma única formiga (que representa a melhor solução já obtida pelo algoritmo (S*)). Geral updating.

τrs = (1 – p) . τrs + p . Δ τrs

        Atualização do feromônio por cada formiga cada vez que passa por uma aresta. Local updating:

τrs = (1 – δ) . τrs + δ . τ0

Variáveis:

rs  → componente, distância de uma cidade a outra, só pode ser selecionado por uma formiga, se essa não tiver acabado de passar por ele (problema combinatório) e só pode ser selecionado se outro componente adjacente tiver sido selecionado antes, a não ser para a primeira seleção.

Prs → probabilidade de seleção para um componente/aresta, depende de várias outras variáveis. Pode variar de 0 a 1.

ηrs → contribuição para maximizar a pontuação geral de seleção do componente/aresta (pode ser 1/distânciars).

β → coeficiente de heurística (normalmente fixado em 1,0).

α → é o coeficiente de histórico.

c → conjunto de componentes utilizáveis a partir daquela cidade. O somatório que existe na fórmula de Prs varia de k=1 até c.

q → parâmetro entre (0,1].

q0 → número aleatório, também entre (0,1], o fator q0 é utilizado para influenciar quando a equação de Prs é utilizada e quando precisa selecionar o melhor componente possível.