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
2 Projecto do Layout de Instalações Industriais
3 Programação Lógica por Restrições na Resolução de Problemas
4 Modelo para Resolução de Problemas de Layout de Instalações com a Tecnologia das Restrições
5 Optimização de Problemas de Layout de Instalações com Programação Lógica por Restrições
6 Técnicas Algorítmicas Baseadas na Evolução Natural e a Tecnologia das Restrições
7 Metodologia GeRL na Optimização de Problemas de Layouts de Instalações
|