Geração de Configurações de Sistemas Industriais com o Recurso à Tecnologia das Restrições e Computação Evolucionária
Generation of Industrial Systems Configurations by Using the Constraint Technology and Evolutionary Computation
Tese submetida à Universidade do Minho para obtenção do grau de Doutor em Informática, elaborada sob a orientação do Professor Doutor José Carlos Ferreira Maia Neves (UM) e do Professor Doutor Carlos Fernando Silva Ramos (ISEP/IPP)
José António dos Reis Tavares
Dezembro, 2000
O objectivo
fundamental do trabalho apresentado neste documento relaciona‑se com a
exploração do paradigma da programação em lógica por restrições (PLR), em
combinação com os algoritmos genéticos, na resolução do problema da geração
de configurações de sistemas industriais, ou mais especificamente, na geração
de layout de plantas industriais, que
é reconhecidamente um problema complexo, caracterizado por possuir um conjunto
muito variado de condicionantes. A PLR evoluiu ao longo das duas últimas décadas,
assumindo-se inicialmente como um complemento à programação em lógica, sendo
presentemente uma poderosa ferramenta que conhece uma crescente aplicação na
resolução de problemas complexos.
O trabalho
realizado passou pelo desenvolvimento de um sistema para a geração de layout
de plantas industriais que tira partido, por um lado, da facilidade e
naturalidade proporcionada pelo paradigma da programação em lógica por restrições
para a especificação de um problema e, por outro lado, da capacidade que a
computação evolucionária possui na obtenção de boas soluções por combinação
de outras, principalmente quando não existem métodos específicos capazes de
solucionarem o problema de forma adequada.
As principais contribuições do trabalho aqui apresentadas são dadas a seguir. Em primeiro lugar, o sistema concebido tem em linha de conta a PLR. Contrariamente ao que é usual, são propostas restrições que modelam especificidades e requisitos de cada instância particular do problema, assim como se considera a existência de várias instalações, com diferentes desempenhos, na realização da mesma operação. Em segundo lugar, na resolução dos problemas é usada uma heurística original, que recorrendo a restrições, obriga a que determinados pares de instalações, cuja interacção é superior à das restantes, sejam colocadas próximas. Por último, para resolução destes problemas, foi desenvolvida uma abordagem que combina a utilização de algoritmos genéticos com a tecnologia da PLR, em que os operadores genéticos são baseados no paradigma da programação em lógica por restrições, com domínios finitos, usando conhecimento específico ligado ao universo de discurso que sustenta o problema em consideração.
Abstract
The main objective of the work presented in this document is related with the exploitation of the constraint logic programming (CLP) paradigm in combination with genetic algorithms, to solve the facilities layout problem of industrial plants. This problem is recognised to be complex and characterized to be subjected by a large set of restrictions, well suited to the CLP paradigm (CLP). Indeed CLP evolved in the last two decades, from a basic research concept into a powerful technique that found an increasing success when applied to solve hard problems.
The accomplish work went through the development of a system to generate facilities layouts for industrial plants. The system benefits, on one hand, from the easiness and naturalness of the CLP paradigm to express problems whose formulation is based on constraints, and on the other hand, from the ability that evolutionary computation has in attaining good solutions to a particular problem, manly when specific and efficient methods to solve the problem suitable way do not exist.
The main contributions of the work presented here are the following. Firstly, the conceived system to solve industrial facilities layout problems takes into account the potential of CLP. In contrast with what it is usual, are proposed constraints to model specific requirements for each particular instance of the problem and also are considered the existence of some facilities that are able to perform the same operations, possibly with different performances. Secondly, in order to solve these problems, an original heuristic was used, which is based on the use of constraints imposing that some facilities should be placed next to each other. Finally, to solve these problems, a hybrid approach was developed that combines the use of genetic algorithms with constraint logic programming. The genetic operators are based on the CLP paradigm, with finite domains, using specific knowledge linked to the of discourse that sustains the problem under consideration.
Índice
1.1 Enquadramento
1.2 Motivação e Objectivos
1.3 Contribuições Originais
1.4 Terminologia
1.5 Organização da Tese
2 Projecto do Layout de Instalações Industriais
2.1 Planeamento e Projecto de Instalações
2.2 Recolha de Informação para o Layout de Instalações Industriais
2.3 Parâmetros para a Avaliação da Qualidade de Layouts
2.4 Modelos Matemáticos para o Projecto de Layout
2.5 Algoritmos para a Resolução do Problema do Layout
2.6 O Layout e as Tendências dos Sistemas Industriais
3 Programação Lógica por Restrições na Resolução de Problemas
3.1 Conceitos Gerais Sobre Restrições
3.2 Problemas de Satisfação de Restrições
3.3 Programação Lógica por Restrições com Domínios Finitos
3.4. PLR(DF) na Resolução de Problemas
3.5 Limitações e Áreas de Aplicação
4 Modelo para Resolução de Problemas de Layout de Instalações com a Tecnologia das Restrições
4.1 Requisitos de Informação para Resolução de PPLI
4.2 Resolução de PPLI Recorrendo à PLR(DF)
5 Optimização de Problemas de Layout de Instalações com Programação Lógica por Restrições
5.1 Algumas Características do LaRLo
5.2 Descrição da Informação Necessária à Resolução de PPLI
5.3 Pesquisa e Optimização
6 Técnicas Algorítmicas Baseadas na Evolução Natural e a Tecnologia das Restrições
6.1 Algoritmos Genéticos: Técnica Baseada em Princípios Biológicos
6.2 Paradigmas da Computação Evolucionária
6.3 Algoritmos Genéticos
6.4 Os Algoritmos Genéticos e a Programação Lógica por Restrições
7 Metodologia GeRL na Optimização de Problemas de Layouts de Instalações
7.1 A Computação Evolucionária na Resolução de Problemas de Layout
7.2 A Metodologia GeRL na Resolução de PPLI
7.3 LayGeRL na Resolução dos Casos de Teste
8.1 Revisão dos Objectivos, Contribuições e Resultados
8.2 Problemas Relacionados com o Layout de Instalações
8.3 Limitações e Perspectivas de Trabalho Futuro