[pt] Esta dissertação investiga o uso de Algoritmos Genéticos e
de Co-Evolução Cooperativa na otimização de problemas de
planejamento com restrições de precedência. Neste tipo de
problema algumas ou todas as tarefas têm restrições que
implicam na necessidade de planejá-las ou executá-las antes
ou depois de outras. Por esta razão, o uso de modelos
evolucionários convencionais como, por exemplo, os baseados
em ordem pode gerar soluções inválidas, não penalizáveis,
que precisam ser descartadas, comprometendo assim o
desempenho do algoritmo. O objetivo do trabalho foi,
portanto, estudar formas de representação de soluções para
este tipo de problema capazes de gerar somente soluções
válidas, bem como avaliar o desempenho dos modelos
propostos. O trabalho consistiu de 3 etapas principais: um
estudo sobre problemas de otimização de planejamento com
algoritmos genéticos; a definição de novos modelos usando
algoritmos genéticos e co-evolução cooperativa para
otimização de problemas de planejamento com restrições de
precedência e a implementação de uma ferramenta para estudo
de caso.
O estudo sobre os problemas de otimização de planejamentos
com algoritmos genéticos envolveu o levantamento de
representações, dificuldades e características deste tipo
de problema e, mais especificamente, de representações
baseadas em ordem.
A modelagem do algoritmo genético consistiu
fundamentalmente na definição de uma representação dos
cromossomas e da função da avaliação que levasse em conta a
existência de restrições de precedência (tarefas que devem
ser planejadas/executadas antes de outras).
A construção do modelo co-evolucionário por sua vez
consistiu em definir uma nova população, com uma outra
representação, que se responsabilizasse pela distribuição
dos recursos para execução das tarefas, responsabilidade
esta que, no modelo com algoritmos genéticos convencionais,
era tratada de forma simples por um conjunto de heurísticas.
Finalmente, desenvolveu-se uma ferramenta para implementar
estes modelos e tratar de um estudo de caso complexo que
oferecesse as características necessárias para testar a
qualidade das representações e avaliar os resultados. O
estudo de caso escolhido foi a otimização do planejamento
da descarga, armazenamento e embarque de minério de ferro
de modo a minimizar o tempo de estadia dos navios em um
porto fictício.
Foram realizados vários testes que demonstraram a
capacidade dos modelos desenvolvidos em gerar soluções
viáveis, sem a necessidade de heurísticas de correção, e os
resultados obtidos foram comparados com os de um processo
de busca aleatória. Em todos os casos, os resultados
obtidos pelos modelos foram sempre superiores aos obtidos
pela busca aleatória. No caso do modelo de representação
com uma única população obteve-se resultados até 41%
melhores do que com os obtidos por uma busca aleatória. No
caso do modelo de representação com co-evolução o resultado
ficou 33% melhor que a busca aleatória com tratamento de
solução idêntico ao da solução co-evolucionária. Os
resultados da co-evolução comparados com o algoritmo
genético com uma única espécie foram 29% melhores. / [en] This work investigates the use of Genetic Algorithms and
Cooperative Co-Evolution in optimization of scheduling
problems with precedence constraints. In this kind of
problem some or all tasks have constraints that imply
planning or executing them before or after others. For this
reason, the use of order-based conventional evolutionary
models may generate invalid solutions, which cannot
be penalized, needing to be discarded and therefore
compromising the algorithm performance. The main goal was
therefore to study models for this kind of problem that are
capable of generating only valid solutions. The work was
divided in 3 main steps: a survey on scheduling
optimization problems using genetic algorithms; definition
of two models based on genetic algorithms and cooperative
co-evolution for optimizing scheduling problems with
precedence constraints; and the implementation of a tool
for a case study.
The study on scheduling optimization problems with genetic
algorithms consisted in gathering information about
representations and characteristics of this kind of problem
and, more specifically, about order-based representations.
The genetic algorithm modeling consisted basically in
defining a chromosome representation and an evaluation
function that took into account the existence of precedence
constraints (tasks that must be scheduled or executed
before others).
The co-evolutionary model consisted in defining a new
population, with another representation scheme, which was
responsible for distributing resources for tasks execution.
On the conventional genetic algorithm model, this role was
played by a simple set of heuristics.
Finally, a tool was developed for implementing those models
and treating a complex case study which offered the needed
characteristics for testing representation performance and
evaluating results. The chosen case study was the
optimization of iron ore dumping, stocking and ship loading
on a fictitious harbor, targeting minimization of ships
waiting time.
Tests were done in order to demonstrate the ability of the
developed models in generating viable solutions without the
need of corrective heuristics and the results were compared
to the results obtained through exhaustive search. In all
cases, the models` results were better than the exhaustive
search ones. In the case where the representation used a
single population the results obtained were up to 41%
better than the ones with the exhaustive search. The co-
evolutionary results outperformed the co-evolutionary
search with the same solution representation by 33%.
Compared to the single specie genetic algorithm, the co-
evolutionary model outperformed it by 29%.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:3725 |
| Date | 17 July 2003 |
| Creators | ANDRE VARGAS ABS DA CRUZ |
| Contributors | MARLEY MARIA BERNARDES REBUZZI VELLASCO, MARCO AURÉLIO CAVALCANTI PACHECO |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0096 seconds