Algoritmo de Colônia de Formigas e Sistema Imunológico Artificial para Otimização em Espaços Discretos

Aplicação ao Problema de Designação Generalizada (“Generalized Assignment

Problem”)

Carlos Henrique Dias 010117Fábio Luiz Usberti 001667Hamilton Melo Ferreira 861101Joelma Cristina Costa 069618Tiago Agostinho de Almeida 025625

GAP: Generalized Assignment Problem

Enunciado:Suponha um conjunto de agentes e um conjunto de tarefas. Um agente pode ser designado a cumprir qualquer tarefa, cada qual implicando em um custo e em um consumo de recursos específicos para cada agente, que por sua vez possui uma quantidade limitada de recursos, ou seja, uma capacidade que não pode ser excedida. O objetivo consiste em encontrar um conjunto de designações no qual todas as tarefas sejam designadas aos agentes, minimizando o custo.

Representação em Grafos

agentes

15

16

14

17

capacidade

3

4

2

5

1

4

2

3

custos

6

8

9

7

8

7

6

8

recursos

trabalhos

Representação em Grafos

Representação em Grafos

Formulação Matemática

Variáveis:xij: 1 se o trabalho i foi designado ao agente j, 0 c.c.

Parâmetros:cij: custo associado à designação do agente j à tarefa iaij: recurso associado à designação do agente j à tarefa ibj: capacidade do agente jM: número de agentesN: número de tarefas

Formulação Matemática

∑∑= =

N

i

M

jijij xcMin

1 1Função Objetivo

Formulação Matemática

∑∑= =

N

i

M

jijij xcMin

1 1Função Objetivo

..as Restrições

Formulação Matemática

∑∑= =

N

i

M

jijij xcMin

1 1Função Objetivo

..as Restrições

Mjjbxa j

N

iijij ≤≤∀≤∑

=

11

Capacidade

Formulação Matemática

∑∑= =

N

i

M

jijij xcMin

1 1Função Objetivo

..as Restrições

Mjjbxa j

N

iijij ≤≤∀≤∑

=

11

Capacidade

NjixM

jij ≤≤∀=∑

=

111

Designação

Formulação Matemática

∑∑= =

N

i

M

jijij xcMin

1 1Função Objetivo

..as Restrições

Mjjbxa j

N

iijij ≤≤∀≤∑

=

11

Capacidade

{ }⎩⎨⎧

≤≤∀≤≤∀

∈MjjNii

xij 11

1,0

NjixM

jij ≤≤∀=∑

=

111

Designação

Binária

Formulação Matemática

∑∑= =

N

i

M

jijij xcMin

1 1Função Objetivo

..as Restrições

Mjjbxa j

N

iijij ≤≤∀≤∑

=

11

Capacidade

{ }⎩⎨⎧

≤≤∀≤≤∀

∈MjjNii

xij 11

1,0

NjixM

jij ≤≤∀=∑

=

111

Designação

Binária

Colônia de Formigas

τ: Feromônio

τ

Agentes (recurso limitado)

Tarefas

Custo

Recurso

ττ

(Marcus Randall - BondUniversity / Australia)

Executa N Iterações Para cada formiga

Escolha da Tarefa / AgenteAtualização do Feromônio

Se solução infactível:formiga morre / nasce

Se uma solução é encontrada:Busca LocalSE Melhor_SoluçãoAtualiza Feromônio (global)formiga morre / nasce

Escolha da Tarefa:1st: maior (Σ recurso agente)

Escolha do Agente:- Sorteia q- SE q < q’’ determinístico

max {τ / ηβ }-SENÃO probabilístico

- prob α {τ / ηβ }

-η: recurso ou custo

τ (1 - γ ) * τ

P/ melhor solução: τ τ + γ * 0,1 / custo_sol

τ (1 - ρ ) * τ + ρ * τ’’

Inicialização: τ’’ = 1 / custo

Medidas HeurísticasConstrução de soluções combina nível de feromônio e medida heurística

consideraçõescusto

Duas propostas:

Estática : probabilidade de escolha fixa. recursosEx: razão custo/recurso 0,1

Adaptativa : probabilidade adaptada automaticamente em cada iteração.Ex: Reforço de aprendizado, 0,02%

heurísticaferomônio

>−>−

ητ

)()(

recursoacustoc

==

ηη ?

Busca Local

1210

65

2

8 6

8

2 15

Change: o agente de uma tarefa é trocado por outro.

Busca Local

1210

65

2

8 6

8

2 15

Change: o agente de uma tarefa é trocado por outro.

Busca Local

1710

15

2

8 6

8

2 15

Change: o agente de uma tarefa é trocado por outro.

Busca Local

1210

65

2

8 6

8

2 15

Swap: dada duas tarefas e os agentes alocados são trocados

Busca Local

1210

65

2

8 6

8

2 15

Swap: dada duas tarefas e os agentes alocados são trocados

Busca Local

1110

75

2

8 6

8

2 15

Swap: dada duas tarefas e os agentes alocados são trocados

Sistema Imunológico Artificial

Modelagem (CLONALG)ExperimentosResultados

SIA – ModelagemRepresentação

1 2 3 1 3 3 2 1 2

1 2 3 4 5 6 7 8 9Clientes

Centros

SIA – ModelagemGeração de Anticorpos

AleatórioRoletaFactível

SIA – ModelagemRepertório de Anticorpos

Clientes

1 2 3 1 3 3 2 1 2

1 3 3 2 1 3 1 2 2

2 1 2 3 2 1 3 3 3

3 2 1 1 3 2 2 1 2

... ... ... ... ... ... ... ... ...

1 1 3 2 2 3 3 2 1

Tamanho

do

Repertório

SIA – ModelagemMedida de Afinidade

∑∈

=Jj

jsk kjcAfinidade

=ijc

=kjsOnde: Custo para designar o centro i ao cliente j.

Centro designado para o cliente j na solução k.

SIA – ModelagemMedida de Desafinidade

∑ ∑∈ =∈ ⎥

⎥⎦

⎤

⎢⎢⎣

⎡−⎟

⎟⎠

⎞⎜⎜⎝

⎛=

Iii

isJjijk brdeDesafinida

kj,,0max

=ijr

=ib

Onde: Recursos requeridos pelo centro i para realizar o trabalho do cliente j.

Recursos disponíveis do centro i (capacidade).

SIA – ModelagemClonagem

Somente anticorpos com Desafinidade= 0 são selecionados para clonagem

SE Desafinidade(anticorpoi) > 0 ENTÃO Gere n Anticorpos

SIA – ModelagemMaturação

Maturação inversamente proporcional à AfinidadeN bits do anticorpo são selecionados e substituídos por outros aleatoriamente

1 2 3 1 3 3 2 1 21 1 3 3 3 3 2 1 2

SIA – ModelagemBusca Local

Passo (a) – Melhorar a Factibilidade.Seja Tj o centro designado para o cliente j em uma determinada

solução. Então, para cada centro i , se o consumo excedeu a capacidade,

,,∑

=∈

>iTJj

iijj

br

escolhe-se aleatoriamente um cliente q com Tq = i e o aloca para o próximo centro ( na ordem de i + 1,..., m, 1,..., i - 1 ), verificando a

disponibilidade do próximo centro.

SIA – ModelagemBusca Local

Passo (b) – Melhorar o custo.

Para cada cliente j, achar ijcIi i,min ∈ que satisfaça:

iijiTJqiqjTij brrecc

q

j≤+⎟

⎟⎠

⎞⎜⎜⎝

⎛< ∑

=∈ ,

Se um determinado i pode ser localizado, designar o cliente j do centro Tj para o centro i.

SIA – ModelagemBusca Local

Exemplo (a)

Capacidade do centro 1 = 25.Capacidade do centro 2 = 20.

SIA – ModelagemBusca Local

Exemplo (a)

Cliente escolhido aleatoriamente j = 5.

SIA – ModelagemBusca Local

Exemplo (a)

Recursos utilizados do centro 1 = 22.Recursos utilizados do centro 2 = 16.

SIA – ModelagemBusca Local

Exemplo (b)

Recursos disponíveis no centro 1 = 3.Recursos disponíveis no centro 2 = 4.

SIA – ModelagemBusca Local

Exemplo (b)

Recursos disponíveis no centro 1 = 13.Recursos disponíveis no centro 2 = 0.

SIA – ModelagemSeleção

Regras de Prioridade:Menor DesafinidadeMaior Afinidade

SIA – ModelagemDiversidade

Métrica:Somente soluções exatamente iguais são levadas em conta para o cálculo da diversidade

Motivo:Qualidade da Solução é bastante sensível a representação

A alteração de único bit pode alterar drasticamente a qualidade de uma solução

Injeção de Diversidade:Quando a diversidade do Repertório ficar abaixo de um limiar:

1 – Mecanismo de Supressão2 – Completar o Repertório com novos anticorpos

SIA – ModelagemSupressão

Soluções exatamente idênticas são eliminadas do repertório, mantendo apenas um representanteObjetivo:

Eliminar soluções concentradas em um mesmo ponto do espaço de buscaProporcionar maior exploração com o aumento da diversidade

SIA – Experimentos e Resultados

Executamos 600 testes, sendo:10 testes por instância60 instâncias [OR-Library]

Solução ótima encontrada para 45 instânciasNo pior caso, a solução encontrada ficou a 0,2% do ótimoO SIA foi capaz de preservar e evoluir uma grande quantidade de boas soluções em um mesmo experimento

SIA – Experimentos e Resultados

Uma amostra (Maximização):Gap5-2: 24 clientes e 8 centrosA solução ótima = 558 foi encontrada nos 10 testes realizadosTamanho do Repertório = 100Número de Soluções Factíveis obtidas = 85Custo das 10 melhores soluções: [558 557 557 556 556 555 555 554 554 553]Custos das 10 piores soluções:[541 541 540 540 539 537 536 536 534 534]A pior solução está a 4,5% da ótimaMatriz de Distância entre as soluções mostra que elas são bem diversificadas. Para transformar uma solução em outra, em média, é necessário trocar 33% das arestas, ou seja, designar 33% dos clientes a outros centros

SIAGap – Pacote Gráfico

SIAGap – Pacote Gráfico

Dúvidas ???