Apresentação Group Search Optimizer

Apresentação

Slide 1 - Group Search Optimizer

A Otimização por Busca em Grupo (Group Search Optimization, ou GSO) é uma meta-heurística de inteligência de exames baseado no comportamento de busca de animais sociais e da teoria da vida em grupo. O GSO segue o modelo Producer-Scrounger (PS), proposto para a análise comportamental das estratégias de busca por recursos (ex.: fontes de alimento) empregadas por animais que vivem em grupos. No modelo PS, existem dois tipos principais de indivíduos: os producers, que fazem buscas por recursos em seu ambiente; os scroungers, que fazem uso de reservas descobertas por outros membros. De acordo com esse modelo, cada indivíduo do grupo adotará exclusivamente um tipo de comportamento dentre os dois possíveis.

Slide 2 - Group Search Optimizer

• Mecanismo de Busca: Visão.

A busca desempenhada por cada membro no GSO leva em consideração o campo de varredura visual do mesmo (visual scanning field).

• Estratégia:

• Produtor: Pesquisar (produzir) alimentos, recursos;
• Scroungers: Juntar (arrecadar) recursos descoberto por outros.

• Cada indivíduo possui uma posição, altura máxima que ele pode ir, ângulo máximo que sua cabeça pode girar para procurar recursos e distância máxima que pode atingir.

• Inspirado no peixe branco
• Esta varredura é executada através da movimentação da cabeça de cada membro por um ângulo específico e que varia a cada iteração do algoritmo.

Slide 3 - Mecanismo de Busca de Membros

Em um problema definido por um espaço de busca n-dimensional, o i-ésimo membro na t-ésima iteração da busca terá uma posição atual definida pelo vetor Xki ∈ Rn e um ângulo de cabeça φki = (φki 1 ,..., φki (n−1)) ∈ Rn−1. Este ângulo de cabeça limita o até onde o indivíduo pode girar seu ângulo de busca. A direção da busca do i-ésimo membro, que é um vetor Dk i(φki) = (dki1 ,..., dkin) ∈ Rn, pode ser calculada por φki através de uma transformação polar para coordenadas cartesianas dada por:

[pic 1]

Slide 4 - Classificação de Membros

No GSO, a população G de S indivíduos é chamada de grupo, enquanto os indivíduos da população (soluções candidatas ao problema abordado) são chamados de membros.

Um grupo no GSO consiste de três tipos de membros: producers (produtores), scroungers (dependentes) e membros dispersos (dispersed members, ou rangers), sendo os rangers uma modificação ao modelo PS original proposta pelo GSO. Existe apenas um produtor em cada busca do GSO e os demais membros são dependentes ou membros dispersos. Todos os dependentes irão juntar o recurso encontrado pelo produtor. Durante cada geração do GSO (iteração da busca), o membro do grupo que encontrou a melhor reserva de recursos, ou seja, o melhor valor para a função de adequação (fitness), é escolhido como producer (COUZIN et al., 2005).

Slide 5 a 6

Na t-ésima geração de uma execução do GSO, o produtor Xp se comporta como se segue:

Passo 1 - O producer executará uma estratégia de varredura baseada em seu campo de visão. Essa estratégia recebe o nome de producing. Na t-ésima geração de uma execução do GSO, o producer Xpk varrerá o espaço de busca do problema através da observação de três pontos aleatórios em seu campo visual: um ponto a zero grau (2), um ponto no hipercubo à sua direita (4), e um ponto no hipercubo à sua esquerda (3).

[pic 2]

onde r1 ∈ R1 é um número aleatório normalmente distribuído com média 0 e desvio padrão 1, r2 ∈ Rn−1 é uma seqüência aleatória uniformemente distribuída no intervalo (0, 1), θmax ∈ R1 é o ângulo de busca máxima, e lmax ∈ R1 é a distância máxima de busca.

Passo 2 - Se o producer for capaz de encontrar uma reserva de recursos melhor que a de sua posição atual (melhor valor de fitness), ele se dirigirá para esse ponto; caso contrário, se nenhuma posição mais promissora for encontrada, o producer permanecerá em sua posição atual, movimentando sua cabeça para uma posição definida por um novo ângulo, de acordo com

φk+1 = φk + r2 αmax                                  (5)

onde αmax ∈ R1 é o ângulo máximo de retorno.

Passo 3 - Se o producer não for capaz de encontrar uma posição melhor que sua posição atual, ele retornará sua cabeça para a posição de ângulo zero

φk+α = φk                                                  (6)

onde a ∈ R1 é uma constante.

Slide 7 - Scroungers

Todos os scroungers tentarão alcançar as reservas já encontradas pelo producer, sendo essa estratégia denominada scrounging. O operador de scrounging no GSO é executado de acordo com