OTIMIZAÇÃO ALGORITMO DE COLONIA DE FORMIGA

...

e desaloção constante de memória.

A CPU simulou a situação dentro das expectativas, superando até mesmo a GPU no resultado final. Com isso podemos observar que os algoritmos de colonias de formiga podem serem aplicados em jogos para otimizar problemas.

2.2 - Otimização por colônia de formigas para o problema de sequenciamento de tarefas em uma única máquina com terceirização permitida.

O problema

O problema abordado neste artigo pode ser definido como:

Seja J um conjunto de n tarefas a serem sequenciadas para produção in-house ou terceirizadas, cada tarefa Ji é definida por:

a) um tempo de processamento pi;

b) um custo de terceirização oi;

c) um tempo de entrega de terceirização li.

Como mencionado anteriormente, estes problemas contêm um conjunto de tarefas. Cada tarefa pode ser sequenciada em uma máquina única ou terceirizada. O término de uma tarefa i é definido pela Equação1. O custo total de terceirização é definido pela Equação 2. em que:

O conjunto Oπ contém todas as tarefas terceirizadas;

O conjunto Sπ contém as tarefas a serem realizadas na máquina única;

O conjunto SPk contém todas as tarefas de Sπ sequenciadas antes da tarefa k.

A função objetivo do problema a ser estudado é mostrada na Equação 3

Como utilizou o algoritmo:

O método proposto neste trabalho, baseado na heurística ACO, é composto de dois estágios: o primeiro estágio ordena as tarefas usando a regra SPT (Shortest Processing Time - Menor Tempo de Processamento) buscando a redução do espaço de

busca. Com isso, esta fase tem como resultado uma representação do problema em forma de grafo que permite ao ACO escolher apenas se uma tarefa deve ou não ser terceirizada. No segundo estágio, uma variação do algoritmo ACO é proposta e aplicada, selecionando quais tarefas devem ser terceirizadas e quais não devem. Esse algoritmo incorpora ao ACO quatro características específicas do problema estudado, a saber:

i) uma representação em forma de grafo para problemas de scheduling que envolvam terceirização, resultado da aplicação do primeiro estágio do método;

ii) uma regra de pré-seleção, que garante a viabilidade da solução;

iii) uma nova regra de visibilidade, específica para o problema;

iv) uma estratégia de busca local.

Para apresentar o algoritmo, serão descritas a seguir as duas fases subsequentes do método proposto:

Fase 1:

O grafo é gerado por meio do pré-processamento do problema, conforme mostrado no Algoritmo 2;

Fase 2:

É proposto um algoritmo MMAS específico para a resolução do problema representado por este grafo.

Resultado

Dos dados gerados pelos experimentos, pode se verificar que as definições de visibilidade influenciaram positivamente o comportamento do Otimização por colônia de formigas para o problema de sequenciamento de tarefas... algoritmo implementado. Sem o uso da estratégia de busca local e com um ajuste adequado dos parâmetros do algoritmo (β={2,5;5,0}), os resultados encontrados foram melhores que aqueles encontrados por Lee e Sung (2008a) para problemas contendo 10e20 trabalhos. Para problemas contendo mais trabalhos, (n={30;40;50;60}), o algoritmo desenvolvido com a estratégia de busca local gerou melhores resultados. Para n=70, o gap médio encontrado pelo algoritmo proposto com busca local e os resultados encontrados por Lee e Sung (2008a) são muito semelhantes. Porém, o gapmáximo encontrado no algoritmo proposto mostra que, mesmo quando n={70}, o algoritmo ACO é

mais adequado para a resolução do problema do que o algoritmo proposto por Lee e Sung (2008a).

A estratégia de busca local proposta para o problema 1/Budget/δ.OC+(1–δ)ΣCj melhorou significativamente os resultados obtidos na resolução de problemas com 30, 40, 50 60 e 70 trabalhos. Percebeu-se que a busca local aumenta o tempo computacional necessário para a execução do algoritmo. Porém, mesmo quando são tratados alguns problemas contendo 70 trabalhos, o tempo computacional requerido é viável.

2.3- Algoritmo de Colônia de Formigas Aplicado ao Problema de Alocação de Equipamentos em Satélites

O problema

Problemas de otimização de layout s˜ao aqueles nos quais um conjunto de itens devem ser colocados num recipiente qualquer, sem sobreposic¸ ˜ao, de acordo com um conjunto de objetivos e restrições. Estes problemas podem ser vistos como um problema de Corte e Empacotamento (C&P) e são geralmente NP-difíceis [Dyckhoff 1990].

O problema de posicionamento de equipamentos no interior do módulo de satélites artificiais que visa otimizar um conjunto de objetivos, enquanto satisfaz restrições espaciais e/ou de desempenho, é denominado Problema de Projeto de Layout de Módulo de Satélites ou SMLDP, sigla em inglês para ”Satellite Module Layout Design Problem”[Wang et al. 2009].

Os problemas tradicionais de alocação de objetos, em geral, visam maximizar a

quantidade de objetos no interior do container e balancear a massa do conjunto. Outros

objetivos comuns para problemas de layout buscam minimizar o tamanho do container e

e mantê-lo balanceado (vide [Parreira et al. 2011]).

No trabalho, foi considerado o problema de alocação de equipamentos em um satélite tendo como objetivos minimizar o centro de massa em relação ao centro do conjunto e maximizar o momento de inércia, para permitir melhor controle nas manobras, Os equipamentos são caixas retangulares que devem ser dispostos em uma superfície também retangular. As condições de existência para alocar objetos consistem em não permitir sobreposições