- Modelagem Matemática e Computacional / CEFET-MG
Transcrição
- Modelagem Matemática e Computacional / CEFET-MG
CENTRO FEDERAL DE EDUCAÇÃO TECNOLÓGICA DE MINAS GERAIS Diretoria de Pesquisa e Pós-Graduação Programa de Pós-Graduação em Modelagem Matemática e Computacional Otimização de Layouts Industriais Utilizando Heurística SDPI no treinamento de Redes Neurais MLP Dissertação de Mestrado, submetida ao Programa de Pós-Graduação em Modelagem Matemática e Computacional, como parte dos requisitos exigidos para a obtenção do título de Mestre em Modelagem Matemática e Computacional. Aluno: Ricardo Soares (Engenheiro Mecânico – UFMG) Orientadora: Profa. Dra. Maria das Graças de Almeida (CEFET-MG) Co-Orientador: Prof. Dr. Sérgio Ricardo de Souza (CEFET-MG) Belo Horizonte, 31 de agosto de 2006. Agradecimentos Primeiramente, a Deus. Aos meus pais, Walter e Odina. À minha esposa Cláudia e aos meus filhos Guilherme e Eduardo pela compreensão das ausências em alguns momentos. Aos colegas e amigos, Alessandra, Marcelo, e Marcos pelo compartilhamento nas horas difíceis. À minha orientadora Profa.Dra. Maria das Graças de Almeida . Ao meu co-orientador e amigo Prof.Dr. Sérgio Ricardo de Souza. Este trabalho teve o apoio da CAPES. ii Dedicatória Para Cláudia, Guilherme, Eduardo e principalmente aos meus pais. iii Sem sonhos, a vida não tem brilho. Sem metas, os sonhos não têm alicerces. Sem prioridades, os sonhos não se tornam reais. Sonhe, trace metas, estabeleça prioridades e corra riscos para executar seus sonhos. Melhor é errar por tentar do que errar por omitir!. Não tenha medo dos tropeços da jornada. Não se esqueça de que você, ainda que incompleto, foi o maior aventureiro da história. Augusto Cury iv Resumo O arranjo físico de equipamentos em uma instalação industrial tem sido objeto de estudos por vários pesquisadores na busca do arranjo ótimo. Sendo assim, diversas metodologias têm sido desenvolvidas ao longo do tempo. Em 1957, Koopmans e Beckmann utilizaram o problema quadrático de alocação como modelo matemático nas soluções de problemas na área econômica. Em 1963, Armour e Buffa modelaram atividades relacionadas com otimização de layouts, tendo, como base, o Problema Quadrático de Alocação. Diversos tipos de formulações têm sido apresentadas para este problema com base nas permutações das matrizes de entrada; fundamentadas na programação inteira e booleana; na teoria dos grafos; programação semidefinida, dentre outras. Este trabalho aborda uma solução computacional para o problema de arranjo físico industrial com base em redes neurais multilayer perceptron para uma situação realista de vinte e dois departamentos. A heurística Steepest Descent Pairwise Interchange servirá de suporte à rede neural, fornecendo os dados necessários para o seu treinamento, validação e teste. De acordo com o número de departamentos, comparações são realizadas com métodos exatos enumerativos e com o algoritmo Branch and Bound. Como resultado, o arranjo físico final para o caso em estudo foi satisfatório, permitindo redução considerável no custo total. Palavras-Chave: Problema quadrático de alocação, Algoritmo Branch and Bound, Redes neurais Multilayer Perceptron. v Abstract The facility layout problem have been object of studies for several researchers in order to find optimal arrangement. A lot of Quadratic Assignment Problem (QAP) formulation have been developed along the time, such as: Koopmans and Beckmann (1957) used the quadratic assignment problem as mathematical model in the economical area; Armour and Buffa (1963) modeled activities related with layouts optimization based in QAP. According to mathematical resources, some QAP formulations has been made: based in matrix permutations ; integer and boolean linear programming; graph theory; semidefined programming, among others. This document presents a computacional solution for the facility layout problem. Neural Network Multilayer Perceptron will be used for a realistic situation with twenty-two departments. Heuristics Steepest Descent Pairwise Interchange will serve as support to the neural network supplying it for the data training, validation and test. Depending on departments numbers, comparisons will be made with enumerated exact methods as well as Branch and Bound algorithm. As result, the final layout for the case in study was satisfactory, allowing considerable reduction in the total cost. Keywords: Quadratic assignment problem, Branch and Bound Algorithm, Multilayer Perceptron Neural Networks. vi Conteúdo 1 Introdução 6 1.1 Preliminares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2 Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3 Caracterização do Problema . . . . . . . . . . . . . . . . . . . . . . . . 9 1.4 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.5 Proposta de Desenvolvimento . . . . . . . . . . . . . . . . . . . . . . . 10 1.6 Organização do Trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2 Problemas de Arranjo Físico 11 2.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2 Característica do Problema . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3 Formulações por Programação Booleana . . . . . . . . . . . . . . . . . 13 2.4 Formulações por Recobrimento de Conjunto . . . . . . . . . . . . . . . 14 2.5 Formulações por Programação Inteira . . . . . . . . . . . . . . . . . . . 16 2.6 Formulações por Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.7 Formulações por Permutações . . . . . . . . . . . . . . . . . . . . . . . 17 2.8 Formulações Traço . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.9 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3 Uma Revisão de Métodos Exatos e Heurísticos para a Solução do Problema de Arranjo Físico 20 3.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.2 Algoritmo Branch and Bound . . . . . . . . . . . . . . . . . . . . . . . 21 3.3 Steepest Descent Pairwise Interchange(SDPI) . . . . . . . . . . . . . . 28 3.4 Redes Neurais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 vii viii 3.5 Redes Neurais MLP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 Algoritmo de Levenberg-Marquardt . . . . . . . . . . . . . . . . 41 3.6 Colônia de Formigas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.7 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.5.1 4 Aplicação de Redes Neurais MLP à Solução do Problema de Arranjo Físico 44 4.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 4.2 Desenvolvimento do Modelo de Projeto . . . . . . . . . . . . . . . . . . 45 4.2.1 Variáveis de Interesse . . . . . . . . . . . . . . . . . . . . . . . . 46 4.2.2 Formulação Matemática Proposta . . . . . . . . . . . . . . . . . 47 4.3 Aplicação do Algoritmo Branch and Bound . . . . . . . . . . . . . . . . 49 4.4 Aplicação da Rede Neural MLP . . . . . . . . . . . . . . . . . . . . . . 52 4.4.1 Preparação dos dados . . . . . . . . . . . . . . . . . . . . . . . . 52 4.4.2 Criação da Rede Neural . . . . . . . . . . . . . . . . . . . . . . 54 4.4.3 Treinamento da Rede Neural MLP . . . . . . . . . . . . . . . . 55 4.4.4 Simulação da Rede Neural MLP . . . . . . . . . . . . . . . . . . 56 Análise dos resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.5.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.5.2 Experimento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.5.3 Resultados Obtidos e Limitações . . . . . . . . . . . . . . . . . 59 4.6 Análise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.7 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.5 5 Conclusão Geral e Trabalhos Futuros 63 A Implementações MaTlab 65 A.1 Código para algoritmo Branch and Bound . . . . . . . . . . . . . . . . 65 A.2 Gerador de Matrizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 A.3 SDPI(Steepest Descent Pairwise Interchange) . . . . . . . . . . . . . . 68 A.4 Colônia de Formigas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 A.5 Algoritmo Exato . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 ix Bibliografia 79 Lista de Tabelas 4.1 Áreas de conhecimento para projeto de arranjos físicos . . . . . . . . . 45 4.2 Relação dos Departamentos do Projeto. . . . . . . . . . . . . . . . . . . 47 4.3 Permutações possíveis . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.4 Resultado Branch and Bound . . . . . . . . . . . . . . . . . . . . . . . 52 4.5 Matriz de Entrada: Fluxo e Distância . . . . . . . . . . . . . . . . . . . 58 4.6 Comparação dos Resultados . . . . . . . . . . . . . . . . . . . . . . . . 61 x Lista de Figuras 2.1 Distância Euclidiana . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.1 Breadth Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.2 Depth Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.3 Best Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.4 Árvore Branch and Bound . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.5 Árvore Branch and Bound (caminho mais curto) . . . . . . . . . . . . . 27 3.6 Fluxograma SDPI [36] . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.7 Matriz Distância . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.8 Matriz Fluxo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.9 Pares Permutados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.10 Célula.[51]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.11 Modelo de Neurônio [51]. . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.12 Arquiteturas Redes Neurais. [1] . . . . . . . . . . . . . . . . . . . . . . 35 3.13 Modelo Aprendizado Supervisionado [1] . . . . . . . . . . . . . . . . . 36 . . . . . . . . . . . . . . . . . . . . . . . . 36 3.15 Mínimos locais e platôs em uma superfície de erro[1] . . . . . . . . . . . 38 3.16 Fluxo processamento do Algoritmo Backpropagation.[1] . . . . . . . . . 39 4.1 Distribuição espacial das localidades . . . . . . . . . . . . . . . . . . . 46 4.2 Arranjos para 4 departamentos . . . . . . . . . . . . . . . . . . . . . . 51 4.3 Preparação dos Dados. . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.4 Estrutura Rede Neural . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.5 Código para o Treinamento Rede MLP . . . . . . . . . . . . . . . . . . 56 4.6 Treinamento (Normalizado) Rede Neural . . . . . . . . . . . . . . . . . 57 3.14 Aprendizado do Perceptron xi xii 4.7 Código para Simulação da Rede Neural MLP . . . . . . . . . . . . . . 57 4.8 Arranjo obtido com a Rede Neural MLP . . . . . . . . . . . . . . . . . 58 4.9 Vetor Saída Rede Neural . . . . . . . . . . . . . . . . . . . . . . . . . . 60 Lista de Siglas ALDEP - Automated Layout Design Program. COFAD - Computerize facilities Design. CORELAP - Computerized Relationship Layout Planning. CRAFT -Computerized Relative Allocation of facilities Technique. FIFO - First-in-First-out M.I.P - Mixed Integer Program. M.L.P - Multilayer Perceptron. N.P - Não Polinomial. P.L.I - Programação Linear Inteira P.Q.A - Problema Quadrático de Alocação. P.Q.C - Problema Quadrático Cobertura de |Conjunto. PLANET - plant Layout Analysis and Evoluation Technique. Q.A.P - Quadratic Assignment Problem. RNAs - Redes Neurais Artificiais. S.D.P.I - Steepest Descent Pairwise Interchange. xiii Capítulo 1 Introdução 1.1 Preliminares O arranjo físico de máquinas e equipamentos, em um espaço conhecido, tem sido estudado em diferentes áreas, como o planejamento em áreas urbanas, a disposição de teclas em máquinas, projeto de placas em circuito impresso, arranjo físico de células de produção. A preocupação em minimizar o custo está presente em todas estas atividades. Este custo está intimamente ligado à relação de importância existente entre os pares de instalações (por exemplo, o fluxo de materias) e a distância entre elas, informações que são tipicamente fornecidas pelo engenheiro de produção. Originalmente tratado por Koopmans e Heragu [28], o problema de arranjo físico tem sido alvo das mais diferentes propostas, na tentativa de buscar metodologias eficazes para otimizar a disposição física de funcionários e máquinas dentro das instalações industriais. Diversos métodos de resolução deste problema encontram-se na literatura, a saber: Armour e Buffa [4], Nugent et al [43], Vollmann e Buffa [63], Kuriak e Heragu [31] e Meller e Gau [40], dentre outros. Em todos, o principal objetivo é encontrar a melhor posição relativa entre os departamentos. Formulado como um Problema Quadrático de Alocação (PQA) é, em geral, de difícil solução, já que, para problemas de grande porte, não existem algoritmos capazes de resolvê-lo em tempo polinomial. Pode-se entender o PQA supondo m departamentos e n locais, de modo que 6 1.1 Preliminares 7 cada departamento i deverá ser posicionado em um único local j, e cada local j deverá receber somente um departamento i. Esta correspondência biunívoca é essencial para a resolução do problema. Além disto, cada par de departamentos possui pesos, referentes ao grau de importância dentro das atividades da indústria. O objetivo é obter uma permutação entre os departamentos, de tal maneira que a soma dos produtos peso e distância seja a menor possível. Várias propostas têm sido utilizadas para modelar este problema. Dentre as principais, pode-se destacar: teoria dos grafos (Foulds e Robinson [15]), o MIP (Mixed Integer Program) (Montreuil [41]; Montreuil et al.[42]; Heragu e Kusiak [22]) e a abordagem que utiliza estrutura de árvore binária, apresentada por Tam e Li [54] e, mais tarde, empregada por Furtado e Lorena [17] e Azadivar e Wang [5]. Dependendo do tipo de atividades desenvolvidas na indústria e da área disponível, o arranjo físico sofre uma série de restrições: (a) a estrutura das áreas de circulação (corredores, passagens, desníveis e outros); (b) o sistema de movimentação de materiais; (c) a escolha da localização dos departamentos dentro da fábrica; e (d) a localização dos pontos de entrada/saída. Os layouts podem ser construídos a partir de dados básicos (algoritmos construtivos), ou melhorados, quando já existem (algoritmos de melhoramento) [19]. Dentre os algoritmos utilizados para a solução do PQA, destacam-se PLANET (Apple e Deisenroth [3]) CORELAP (Lee e Moore [33]) e ALDEP (Seehof e Evans [48]). Baseia-se em heurística construtiva, na qual cada departamento é alocado, um de cada vez, na área disponível, até que se obtenha a solução ótima ou próxima dela. Também são utilizados algoritmos de melhoramentos, nos quais, partindo-se de uma solução inicial, procura-se a solução ótima ou ideal. Nesse último caso, pode-se citar, dentre outros, os algoritmos: CRAFT (Armour e Buffa [4]), COFAD (Tompkins e Reed Jr. [56]). Estima-se que entre 20% a 50% do total de ações gastas na manufatura são provenientes da movimentação de materiais. O gasto desta movimentação depende do posicionamento entre os departamentos. A disposição lógica dos departamentos e 1.2 Motivação 8 das máquinas, quando oferece adequado arranjo físico, é capaz de reduzir os custos de mão-de-obra entre 10% e 30% , potencializando a produtividade e conseguindo eliminar fatores que não agregam valor ao produto (Savsar, M. [47]). Os métodos utilizados nos últimos 20 anos ainda esbarram nas restrições comuns encontradas no chão de fábrica, e os ajustes manuais ainda são necessários. Isto se deve ao grande número de variáveis inerentes a cada tipo de problema. Em função dos equipamentos utilizados, dos produtos a serem fabricados, dos estoques necessários para a produção, dos materiais envolvidos e de qual cliente a ser atendido, é possível dividir os arranjos físicos em três grandes grupos (Hassan, M. M. D.[24]): • Layout por produto: destinado às linhas de montagem; • Layout por processo: para produção por lotes ou encomendas; e • Layout por posição fixa: para a produção de projetos. 1.2 Motivação A complexidade inerente a este tipo de problema e os desafios apresentados são os principais motivos da atenção dedicada ao Problema de Arranjo Físico ótimo por pesquisadores de todo o mundo. Isto porque é um dos mais difíceis problemas de otimização combinatória. Mesmo quando as matrizes de distância e fluxo são simétricas. Esta dificuldade se torna maior quão maior seja o número de elementos envolvidos. Por exemplo, para n > 15, este tipo de problema não pode ser resolvido, em geral, em tempo computacional aceitável. Esta limitação serve para situações de procura de mínimos globais usando algorítmos deterministas. Um problema combinatorial, pertencente à classe NP-difícil, não possui algoritmo capaz de resolvê-lo em tempo polinomial (M. Gondran, M. Minoux [20]). O PQA é um exemplo de um problema pertencente a essa classe. A quantidade das possíveis configurações aumenta fatorialmente com o número de instalações. O universo de possibilidades possui elementos discretos, que dificulta o uso de ferramentas que têm como base conjuntos contínuos e compromete a busca da solução no sentido de se obter o ótimo global. Todos estes fatores contribuem para que os pesquisadores e estudiosos 1.4 Problemas de Arranjo Físico 9 o vejam como desafio nas implementações de novos algoritmos ou combinação deles. A indústria, por outro lado, requer arranjos físicos otimizados, para aumentar o valor agregado de seu produto. 1.3 Caracterização do Problema Considere o problema de se designar objetos a locais, de modo que cada objeto seja atribuído a um único local e, reciprocamente, cada local a um objeto, considerandose conhecidas as distâncias entre os pares de locais, os fluxos de algum tipo de demanda entre os pares de objetos e, nos casos mais gerais, os custos fixos de cada atribuição “objeto versus local”. O Problema Quadrático de Alocação (PQA) (Quadratic Assignment Problem - QAP, na literatura internacional) consiste em encontrar uma alocação de custo mínimo dos objetos aos locais, sendo os custos obtidos pela soma dos produtos distância-fluxo (Eliane Maria Loiola et al [37]). É importante notar a diferença entre o problema de alocação linear e o problema quadrático de alocação. O primeiro leva em consideração somente o custo de se alocar um departamento em um local específico. O segundo, além desta última consideração, verifica o fluxo de materiais entre os pares de departamentos resultante de algum tipo de demanda entre eles (Chu, L.K. [36]). 1.4 Objetivos Este trabalho tem como objetivo geral o estudo da solução do problema de ar- ranjo físico industrial. Para isso, é objetivo a implementação de uma solução computacional para o mesmo, tendo como base algoritmo exato, heurística e redes neurais. Especificamente, será estudado o treinamento de uma rede neural MLP, com base na heurística SDPI, em instâncias nas quais algoritmos exatos não são aplicáveis. Com isto, pretende-se obter ferramentas adequadas para aplicação nas diferentes instâncias do problema. Além disso, é objeto de interesse a verificação da qualidade dos resultados fornecidos pela rede neural, já que a base de dados para o seu treinamento terá origem na heurística SDPI, uma vez que a quantidade de dados exatos disponíveis na literatura 1.6 Problemas de Arranjo Físico 10 são insuficientes para o treinamento, validação e teste da rede. 1.5 Proposta de Desenvolvimento O problema de arranjo físico industrial é modelado como um problema de progra- mação linear inteira. A técnica de solução se baseia na adoção de algoritmos enumerativos, nos quais a relaxação do problema principal é utilizada. Nesta fase, algumas restrições são ignoradas, com o objetivo de facilitar a solução do problema. Eliminandose as restrições de integralidade das variáveis, o problema inteiro se transforma em um problema linear padrão, que poderia ser resolvido pelo método simplex. Mas outros algoritmos deverão ser usados face ao grande número de combinações possíveis. De acordo com os valores de n, ou seja, quantidade de departamentos a serem alocados, diferentes algoritmos serão utilizados: considerando a enumeração total, não considerando enumeração total(Branch and Bound) e rede neural MLP, treinada com base em dados gerados pela heurística SDPI. Ferramentas que se mostram adaptadas em relação às restrições apresentadas, oferecendo maior flexibilidade na entrada dos dados e futuras modificações nos arranjos físicos. 1.6 Organização do Trabalho Este trabalho está organizado da seguinte maneira: as principais formulações e a revisão bibliográfica a respeito de otimização de arranjos físicos industriais são apresentadas no capítulo 2. No capítulo 3, serão apresentadas as revisões de métodos exatos e heurísticos adotados para a solução do Problema de Arranjo Físico. Para cada um destes métodos, os princípios matemáticos e principais teoremas que os sustentam são discutidos. A abordagem da otimização do arranjo físico proposta é detalhada no capítulo 4, onde as considerações dos dados de entrada são evidenciadas, bem como são apresentados análises dos resultados alcançados quando da aplicação dos métodos apresentados. Finalmente, a conclusão e perspectivas de futuros trabalhos são tratadas no capítulo 5. Capítulo 2 Problemas de Arranjo Físico 2.1 Introdução As expressões facilities layout (arranjo físico de instalações), facilities location (lo- calização de instalações), facilities design (projeto de instalações) e facilities planning (planejamento de instalações) são termos usados principalmente na área industrial, que designam problemas de planejamento de instalações de diversos tipos. Uma ordem de classificação desses problemas foi proposta por Tompkins e White [57], que subdividiu o planejamento de instalações em dois grupos principais: • localização de instalações; e • projeto de instalações. O primeiro grupo faz referência à posição relativa da instalação com o mercado, recurso, ambientes, clientes, etc. O segundo leva em consideração o grau de importância desta instalação, dentro dos objetivos traçados pela instituição. É a este último conceito que o projeto de arranjo físico pertence, consistindo no planejamento da produção ou das áreas de trabalho, almoxarifado, estoque, pessoal, transporte de máquinas, matéria prima, etc. Considere n o número de setores a permutar. Assim, a quantidade de disposições possíveis é n!. Se, além disso, for considerado os espaços para circulação, manutenção e para novas instalações, o grau de complexidade aumenta e as possibilidades passam 11 2.2 Característica do Problema 12 a ser dadas por P = n!A An sendo A a área do departamento e An a área total ocupada por todos os departamentos. Trata-se, portanto, de um problema combinatorial, discreto, da classe de problemas NP-difícil. 2.2 Característica do Problema Os objetivos qualitativos e os quantitativos têm sido considerados para otimização de arranjos físicos de instalações. O primeiro trata da minimização de medidas de avaliação da posição relativa entre os departamentos; o segundo, relaciona-se com o manuseio de materiais. Na prática, ambos são usados isoladamente (Savsar, M. [47]). A literatura apresenta os problemas de projeto em dois grandes grupos: projeto de arranjo físico de instalações e projeto de arranjo físico de máquinas (Hassan, M. M. D. [24]). Este último é dividido em projetos de máquinas em linha simples, em linha múltipla e em malha. A principal diferença entre estes dois grandes grupos é no que tange às áreas ocupadas. No projeto relacionado às máquinas, as dimensões são relativamente pequenas e podem ser consideradas iguais ou mesmo desprezadas, não prejudicando a qualidade do projeto. Já com referência ao projeto de arranjo físico de instalações, as áreas ocupadas são as variáveis mais importantes a serem consideradas no projeto. Em todo projeto de arranjo físico, o objetivo principal é oferecer condições adequadas de mobilidade na área de trabalho, tanto para pessoas quanto para equipamentos e produtos. Três situações devem ser analisadas na decisão de se fazer um projeto de arranjo físico: (a) a capacidade da instalação e a produtividade sofrerem alterações; (b) implicações em despesas adicionais para realizar as mudanças necessárias; (c) prováveis custos extras para futuras reversões. Contudo, o responsável pelo projeto não deverá permitir a inflexibilidade do arranjo final e deve-se criar condições para mudanças, tão necessárias para o desenvolvi- 2.4 Formulações por Programação Booleana 13 mento. 2.3 Formulações por Programação Booleana A formulação booleana foi proposta inicialmente por Koopmans e Beckman [28], sendo utilizada mais tarde por Steinberg [53], Lawer [32], Gavett e Plyter [18], Elshafei [13], Bazaraa e Kirca [7], Christofides e Benavent [9], Bos [8], Mans et al. [38], Jünger e Kaibel [25, 26, 27] e, mais recentemente, por Liang [35], Torki et al. [58], Tsuchiya et al. [60, 61] Siu e Chang [50], Fedjki e Duffuaa [14] e Yu e Sarker [64]. A variável de decisão xij recebe valores um ou zero, dependendo se o departamento i está ou não na posição j. O modelo matemático é dado por Koopmans, T.C and Beckman, M.J [28]: min suj. a n X i,j=1 n X n X fij dkp xij xkp (2.1a) k,p=1 xij = 1, 1 ≤ j ≤ n (2.1b) xij = 1, 1 ≤ i ≤ n (2.1c) xij ∈ {0.1} , 1 ≤ i, j ≤ n. (2.1d) i=1 n X j=1 sendo: n = número de departamentos; fij = fluxo de material entre os departamentos i e j; dkp = distância entre as localizações k e p ; 1, se o departamento i está na posição j; xij = 0, para os outros casos. As matrizes F = {fij }ni,j=1 e D = {dkp }nk,p=1 possuem dimensões n × n tais que fij e dkp pertencem ao intervalo de números inteiros positivos {1, 2, 3, . . . , n}. O produto xij xkp das variáveis de decisão em tela compõe todas as permutações possíveis pertencentes ao espaço de soluções S. 2.4 2.4 Formulações por Recobrimento de Conjunto 14 Formulações por Recobrimento de Conjunto O modelo quadrático de recobrimento de conjunto para o problema geral de otimização de layouts foi apresentado por Bazaraa [6]. Neste modelo, a área total ocupada por todos os departamentos é dividida pelo número de blocos. As variáveis foram definidas como: q = número de blocos nos quais a área total ocupada por todos os departamentos é dividida; I(i) = número de locais possíveis para o departamento i; aij = o custo fixo para alocar o departamento i na posição j; Ji (j) = conjunto de blocos ocupados pelo departamento i alocada na posição j; d(ji , lk ) = distância entre centróides da posição j e l, quando o departamento i é alocada na posição j e o departamento k é alocada na posição l; 1, se o departamento i está na posição j; xij = 0, para os outros casos; pijt 1, se o bloco t ∈ J (j) ; i = 0, para os outros casos. O problema quadrático de cobertura de conjuntos (PQC) é : min I(i) n X X i=1 suj. a I(i) X j=1 aij xij − I(i) n I(k) n X X XX fik d(ji , lk )xij xkl (2.2a) i=1 j=1 k=1 l=1 xij = 1, i = 1, 2, . . . , n (2.2b) j−1 I(i) n X X pijt xij ≤ 1, t = 1, 2, . . . , q (2.2c) i=1 j=1 xij ∈ {0, 1} , i = 1, 2, . . . , n; j = 1, 2, . . . , I(i) (2.2d) As restrições (2.2b) garantem que cada departamento seja alocado em um único local e as restrições (2.2c) obrigam cada local a ser ocupado por apenas um departamento. As distâncias são medidas em relação aos centróides de cada localização. 2.5 Formulações por Recobrimento de Conjunto 15 Bazaraa [6] mostra uma maneira de medir estas distâncias por intermédio dos fluxos entre as instalações, fazendo: d0ik = fik Si Sk sendo Si o número de locais ocupados pelo departamento i e d0jl a distância entre os locais j e l. Usando este artifício, tem-se: min q n X X i=1 q suj. a X aij xij + q q n X n X X X fik d0jl xij xkl i=1 j=1 k=1 l=1 j=1 Si Sk xij = Si , i = 1, 2, . . . , n j=1 n X n X xij ≤ 1, j = 1, 2, . . . , q (2.3a) (2.3b) (2.3c) i=1 i=1 xij ∈ {0, 1} , i = 1, 2, . . . , n; j = 1, 2, . . . , q (2.3d) A desvantagem desta formulação surge quando a área total ocupada por todos os departamentos é dividida em pequenos blocos (Bazaraa, [6]). As distâncias mencionadas anteriormente são as distâncias euclidianas definidas pela fórmula: dkp = q (xp − xk )2 + (yp − yk )2 sendo x e y as coordenadas dos centróides das localizações K e P . Y P y(p) Distância K y(k) x(k) x(p) X Figura 2.1: Distância Euclidiana (2.4) 2.6 2.5 Formulações por Programação Inteira 16 Formulações por Programação Inteira Esta proposta, feita por Lawer [32], envolve coeficientes de custo que não corres- pondem necessariamente ao produto distância e fluxo. Seja a variável yijkl = xij xkl (2.5) O modelo é dado por: min suj. a n n X n X n X X i=1 j=1 k=1 l=1 n n X n X n X X bijkl yijkl (2.6a) yijkl = n2 (2.6b) i=1 j=1 k=1 l=1 yijkl ≥ 0, i, j, k, l = 1, 2, . . . , n (2.6c) yijkl ∈ {0, 1} , i, j, k, l = 1, 2, . . . , n (2.6d) Essa formulação permite a linearização do modelo apresentado em (2.1), através de um artíficio matemático. A matriz B ∈ <n×n representa o custo formado pelo produto das matrizes de fluxo F e de distância D. Observe que n é o número de departamentos em questão. Segundo Kaku e Thompson [30], a desvantagem desta formulação é o número de restrições que possui. O PQA tem n2 variáveis xij e 2n restrições, enquanto o problema apresentado em (2.6) possui n2 variáveis xij , n4 variáveis yijkl e n4 +2n+1 restrições. As restrições são necessárias para o estabelecimento da correspondência biunívoca entre os departamentos e os locais a serem associados. O acréscimo das restrições se deve à linearização do problema, já que várias substituições deverão ser efetuadas nas expressões por conta do artifício matemático utilizado: yijkl = xij xkl . 2.7 Formulações por Grafos 2.6 17 Formulações por Grafos Nos modelos que utilizam a teoria de grafos [15], os locais de cada par de depar- tamentos adjacentes devem ser conhecidos. O modelo é apresentado a seguir: min XX wij xij (2.7) i∈E j∈E suj. a xij = 1, para (i, j) ∈ N (2.8) xij = 0, para (i, j) ∈ F (2.9) sendo: G = (V, E) um grafo, no qual V é o conjunto de vértices, não-vazio, e E é o conjunto de ligações disjuntas de V; V: conjunto de departamentos; N : conjunto de pares de departamentos adjacentes; F: conjunto de pares de departamentos que não devem ser adjacentes; wij : razão de proximidade ao departamento j; (V, E 0 ∪ N ): grafo planar, para E 0 = {(i, j) : xij = 1, (i, j) ∈ E} Evans et al.(1987) [48] divide o problema de arranjo físico em duas categorias, sendo que uma utiliza modelos quadráticos de atribuição e a outra utiliza grafos com base nos fluxos do processo. As restrições mencionadas acima garantem a unicidade dos departamentos aos locais e que cada local tenha somente um departamento. 2.7 Formulações por Permutações Sabendo-se que o custo de alocar um par de departamentos a um par de localiza- ções é proporcional ao fluxo e à distância entre eles, chega-se ao conceito de permutação, apresentado por Hiller e Michael [23], Pierce e Crowston [44] e Cung et al.[10], dentre vários outros. 2.8 Formulações Traço 18 Definindo S n como o conjunto de todas as permutações entre n departamentos, fij como o fluxo entre os departamentos i e j e dπ(i) π(j) como a distância entre as localizações π(i) e π(j) , dada pela permutação π ∈ sn , este modelo pode ser representado, para cada permutação π, como sendo: n X min π∈S n suj. fij dπ(i)π(j) (2.10) i,j=1 1, se π = j; (i) a xij = 0, se π 6= j. (i) (2.11) Os modelos apresentados anteriormente e este são equivalentes, dado que as restrições envolvidas definem matrizes de permutação X = [xij ], que fazem parte do espaço S n . 2.8 Formulações Traço Com base na teoria espectral de matrizes, este tipo de modelagem leva em conta a soma dos elementos da diagonal principal da matriz, dado pela função traço, para que seja determinado o limite inferior da solução ótima do problema. O valor deste limite irá definir o quão ótima será a solução alcançada. Proposta por Edwards [12], esta formulação considera Π como sendo o conjunto das permutações possíveis, e é dada na forma: min Tr (F XDX t ) suj. a X∈Π (2.12a) (2.12b) Nessa expressão, F é a matriz de fluxo, representando o grau de importância entre os departamentos, e D é a matriz de distância entre as localidades. Ambas as matrizes possuem dimensão n × n. O conjunto Π representa o conjunto formado pelas permutações das matrizes X. Também como base nesta formulação, Karisch [29], Zhao [65], e Wolkowisz [62], define relaxação do PQA tendo como suporte o dual do dual Lagrangeano. Assim, sejam dados: 2.9 Conclusão 19 • e: vetor com todos os seus coeficientes iguais a unidade; • X: matriz de permutação; • B: matriz de custo fixo. pode-se escrever: min suj. a Tr (F XD − 2B) X t (2.13a) Xe = e (2.13b) X te = e (2.13c) xij ∈ {0, 1} , ∀ i, j (2.13d) Nesta expressão, tem-se que F ∈ <n×n é matriz de fluxo e D ∈ <n×n é a matriz de distâncias. Estas restrições garantem que cada departamento esteja alocado em um único local e cada local tenha um e somente um departamento. Outra relaxação do PQA utilizando Programação Semidefinida(PSD), com base na formulação traço, segundo Zhao [65], pode ser escrita como: min trF.X.D.X t − 2BX t s.a XX t = X t X = 1, (2.14) Xe = X t e = e, Xij2 − Xij = 0 2.9 ∀i, j. Conclusão Neste capítulo, foram apresentadas várias formulações matemáticas para repre- sentação do problema quadrático de alocação, desde aquelas com base em programação booleana até as fundamentadas na teoria espectral de matrizes. Todas elas têm, como suporte, as permutações das matrizes envolvidas, mesmo aquelas em que a linearização do problema é proposta, aumentando consideravelmente o número de restrições. Capítulo 3 Uma Revisão de Métodos Exatos e Heurísticos para a Solução do Problema de Arranjo Físico 3.1 Introdução Neste capítulo, serão revisados o algoritmo Branch and Bound (divisão e con- quista) e conceitos de Redes Neurais que serão utilizados no desenvolvimento deste trabalho. Especial atenção será dedicada às redes neurais multilayer perceptron(MLP). Será também revisada a heurística Steepest Descent Pairwise Interchange (SDPI). Esta revisão tem como foco a solução de problemas de otimização de arranjo físico até a dimensão compatível com o método utilizado, ou seja, em função do número de departamentos a ser considerado. Na seção 3.2, é apresentada uma aplicação do algoritmo Branch and Bound e as relaxações necessárias, evitando assim a enumeração completa do problema. Mostra o caminho percorrido na árvore de Branch (ramificações) e as alterações ocorridas em função do método de busca utilizado. A seção 3.3 apresenta a heurística do gradiente descendente com trocas de pares (SDPI). Por fim, na seção 3.4, a base teórica e o algoritmo de treinamento da rede neural MLP são apresentados. 20 3.2 3.2 Algoritmo Branch and Bound 21 Algoritmo Branch and Bound Com base na estratégia de divisão e conquista, Land e Doig [52] propuseram o método Branch and Bound para a solução de problemas de programação inteira. Este algoritmo divide o espaço de soluções factíveis em subespaços, evitando, desta maneira, verificar todas as soluções possíveis, permitindo ao método maior velocidade e eficiência. É um algoritmo enumerativo, cuja estrutura de resolução baseia-se na construção de uma árvore de busca, na qual os nós representam os problemas candidatos e os ramos representam as novas restrições que devem ser consideradas. Por intermédio dessa árvore, todas as soluções inteiras da região viável do problema são enumeradas, de modo implícito ou explícito, o que garante que todas as soluções ótimas serão encontradas. O seu princípio básico é o uso de estimativas no valor da solução ótima de um subproblema, para evitar a inspeção de partes de seu conjunto de soluções. Esta seção está fortemente fundamentada em Haffner[49]. Considere P um problema de programação linear inteira e S o seu conjunto de soluções. Seja Pr o problema relaxado de P e S̄ o conjunto de soluções deste problema relaxado, definido por: S̄ = x ∈ <n+ : Ax ≥ b (3.1) A operação de Branching (ramificação) consiste na definição de k poliedros S̄1,...,k , todos contidos em S̄, de tal modo que k [ i=1 S̄ i ∩ Zn+ = S̄ Isso implica que o problema P no poliedro original pode ser resolvido através da resolução de k subproblemas inteiros em poliedros menores. A operação de bounding (limitação) consiste em encontrar a melhor solução contida em cada subespaço, ou seja, em cada poliedro S̄ determinado através da operação de branching. Aquela operação fornece um modo de se calcular uma estimativa inferior para o valor de qualquer solução factível para o problema P em S̄ i , uma vez que, para todo S̄ i ⊂ S̄, tem-se: min f (x) = cx : x ∈ S̄ i ≤ min f (x) = cx : x ∈ S̄ ∩ S̄ i (3.2) O algoritmo Branch and Bound trabalha com iterações, mantendo uma coleção L de subconjuntos de S̄, a melhor solução factível conhecida x∗ ∈ S e o seu valor z ∗ = 3.2 Algoritmo Branch and Bound 22 f (x∗ ) = cx∗ . Inicialmente, L = S̄ e z ∗ = ∞ . Assim, terminando o algoritmo e sendo factível, x∗ será uma solução ótima. Em uma dada iteração do algoritmo, um poliedro S̄ i é extraído de L e a relaxação a seguir é resolvida: z̄i = min f (x) = cx : x ∈ S̄ i (3.3) Se o problema da equação anterior é infactível, ou se z̄i ≤ z ∗ , então não existe nenhuma solução factível x ∈ S ∩ S̄ i , cujo valor de f (x) seja menor do que o da melhor solução encontrada. O próximo passo é analisar a iteração i + 1. Caso contrário, se o problema de (3.3) for factível e z̄i ≤ z ∗ , então x∗ = xi e z ∗ = z̄i . Esse procedimento garante que os subconjuntos S̄ j ∈ L tais que z̄i ≥ z ∗ sejam retirados de L. Se a solução ótima x̄i não for solução factível de P , um branching é executado no conjunto S̄ i e os subconjuntos resultantes desta ramificação são inseridos em L e a iteração i = i + 1 é realizada. Quando não existir nenhum subconjunto no conjunto L, o algoritmo termina. O problema P é infactível se z ∗ = ∞; caso contrário z ∗ é a solução ótima. Com relação aos limites inferiores utilizados, heurísticas poderão ser empregadas para melhorá-los, ou seja, fazê-los o mais próximo possível da solução ótima. Com isto, a árvore de branch ficaria menor e o tempo para se encontrar a solução ótima diminuiria. A forma de escolha do subconjunto S̄ i ∈ L a cada iteração i pode depender da estrutura do problema apresentado, e o modo como a árvore de enumeração é percorrida também é fator importante, sendo vários critérios utilizados para este fim. As estratégias mais comuns para seleção do próximo problema são: Best First, Breadth First e Depth First. Busca em largura (Breadth First) é um método de busca que expande e examina sistematicamente todos os nós de uma árvore, em busca de uma solução. Este algoritmo realiza uma busca exaustiva numa árvore inteira, sem considerar o seu alvo de busca, até que o encontre. Todos os nós filhos obtidos pela expansão de um nó são adicionados a uma fila (primeiro que entra é o primeiro que sai - FIFO). Em implementações típicas, nós que ainda não foram examinados por seus vizinhos são colocados num container (como, por exemplo, uma fila) que é chamado de “aberto”. Uma vez examinados, são colocados num container “fechado”. 3.2 Algoritmo Branch and Bound 23 Figura 3.1: Breadth Search Busca em profundidade (Depth First) é um algoritmo utilizado para se fazer uma busca em uma árvore de busca, iniciando em um nó raiz (normalmente aquele que estiver no topo), explorando o máximo possível os seus ramos. Este tipo de algoritmo de busca progride através da expansão do primeiro nó filho, aprofundando-se cada vez mais até que o alvo da busca seja encontrado ou até que ele se depare com um nó que não possua filhos (nó folha). Então, a busca retrocede (backtrack ) e recomeça no próximo nó. Numa implementação não-recursiva, todos os nós expandidos recentemente são adicionados a uma pilha, para realizar a expansão. Figura 3.2: Depth Search Best-First consiste de uma busca em largura usando funções de avaliação. É uma combinação dos algoritmos Breadth First e Depth First já mencionados. A estrutura geral do algoritmo Branch and Bound apresenta três etapas princi- 3.2 Algoritmo Branch and Bound 24 Figura 3.3: Best Search pais: separação, relaxação e sondagem. Na etapa de separação (branching), o problema original P é separado em subproblemas, sujeitos às seguintes condições: • toda a solução viável do problema principal é uma solução de somente um dos subproblemas; • uma solução viável de qualquer um dos subproblemas também é uma solução viável do problema principal. A forma habitual de separação de um problema de programação inteira é através de restrições conflitantes em uma única variável inteira (variável de separação ou de ramificação). A medida que se percorre a árvore de busca, a região viável dos nós filhos gerados vai ficando cada vez mais limitada. A relaxação consiste em, provisoriamente, ignorar algumas restrições do problema principal, visando torná-lo mais fácil de resolver. A condição que deve ser satisfeita é que o conjunto de soluções viáveis do problema original esteja contido no conjunto de soluções viáveis do problema relaxado Pr . Se o problema relaxado não tem solução viável, então o mesmo é verdadeiro para o problema principal. O valor mínimo encontrado para o problema principal é menor que o valor máximo do problema relaxado. Se uma solução ótima de Pr é viável em P , então ela é uma solução ótima de P . Na sondagem, os problemas candidatos são analisados para se determinar quais são os promissores e quais deverão ser rejeitados. O problema candidato é rejeitado se: 3.2 Algoritmo Branch and Bound 25 • o problema candidato relaxado Pcr não tem solução viável. Isto significa que o problema candidato Pc também não tem solução viável. • a solução ótima do problema candidato relaxado Pcr é pior (bounding) do que a melhor solução atualmente conhecida para P (solução incumbente). Deve-se observar que a solução ótima do problema candidato relaxado é sempre melhor ou igual à solução do problema candidato e de seus descendentes. Uma solução ótima do problema candidato relaxado também é viável em Pc . Neste caso, ela é ótima em Pc e ela é também factível em P . Caso seja melhor que a incumbente atual, a solução deste problema candidato passa a ser a nova incumbente. Para melhor entedimento deste algoritmo, as seguintes ações devem ser observadas: Inicialização. > Fazer i = 0 > Definir a incumbente inicial > Iniciar a lista dos sub-problemas candidatos Teste de Convergência. > Se lista de candidatos é vazia ⇒ Fim. A solucão ótima é a incumbente atual > Caso contrário, verificar próximo passo. Seleção do Candidato. > Escolher qual o próximo subproblema a ser examinado dentre os candidatos.(Utilizar teste de Sondagem). > Resolver o PL relativo ao Pcrk (problema candidato relaxado). k > Definir como limite inferior para os seus descendentes a solução ótima encontrada.(vinf = vP∗ k ). cr Testes de Sondagem. > A sondagem poderá ser realizada no subproblema candidato se: 3.2 Algoritmo Branch and Bound 26 . Pcrk não possuir solução factível. k . vinf > v ∗ sendo v ∗ o valor da incumbente atual. . Pcrk possuir solução ótima inteira factível também no subproblema candidato, e ainda se esta solução for menor do que a incumbente. > Se o subproblema candidato foi sondado, retornar ao item 2. Separação. > Com relação ao subproblema Pck , a variável de separação escolhida deverá ser inteira dentre aquelas que apresentam valores contínuos. > Sendo nj a variável escolhida, com valor atual n∗j , gera-se dois novos subproblemas descendentes acrescentando ao problema candidato as restrições abaixo: (Pci+1 ) : nj ≤ [n∗j ] (Pci+2 ) : nj ≥ [n∗j ] + 1 sendo [n∗j ] o maior inteiro de n∗j . > i = i + 2, voltar para o item 3. Exemplo 3.1 Seja o problema de programação inteira apresentada em (3.4) e sua versão relaxada mostrada em (3.5): min v = 5n12 + 2n13 + 2n23 + β suj. a 350n12 + 400n13 + β ≥ 400 350n12 + 210n23 + β ≥ 200 P β≥0 nij ≥ 0, ∀ i, j n12 , n13 , n23 inteiros min v = 5n12 + 2n13 + 2n23 + β suj. a 350n12 + 400n13 + β ≥ 400 Pr 350n12 + 210n23 + β ≥ 200 β≥0 nij ≥ 0 ∀i, j (3.4) (3.5) 3.2 Algoritmo Branch and Bound 27 Figura 3.4: Árvore Branch and Bound Figura 3.5: Árvore Branch and Bound (caminho mais curto) Com relação ao problema relaxado Pr , a solução apresenta duas variáveis não inteiras: n12 = 4/7 e n13 = 0, 5. Assim, a separação deste problema se dá com a 3.3 SDPI (Steepest Descent Pairwise Interchange) 28 escolha de uma das variáveis anteriores, por exemplo, n12 . As restrições verificadas n12 ≤ 0 (nó 1) e n12 ≥ 1 (nó 2) resultam em dois problemas de PL a serem resolvidos. Supondo que se escolha o nó 2, o resultado do problema relaxado apresenta ainda resultado não inteiro para a variável n13 = 0, 125. Sendo assim, o nó 2 deverá ser separado, dando origem aos nós 3 e 4. Escolhendo este último a ser examinado, encontra-se a primeira solução inteira para o problema 4 original v ∗ = vinf = 7. Como o valor da incumbente foi alterado, os nós 1 e 3 deverão ser avaliados. Escolhendo o nó 3, uma separação em torno da variável n12 se faz necessária. Com esta última separação, os descendentes 5 e 6 também apresentam soluções inteiras, mas são descartadas por possuírem soluções piores que a incumbente atual. Verifica-se a lista de candidatos e seleciona-se o único nó disponível (nó 1). Efetua-se a separação em torno da variável n13 , gerando seus descendentes 7 e 8. 8 Optando-se por este último, encontra-se a solução inteira v ∗ = vinf = 4, que é atualizada como incumbente, pois é melhor do que a anterior. 7 O nó 7 é descartado, já que a sua solução vinf = 201 > v ∗ é pior do que a incumbente atual. Os nós 9 e 10 são mostrados somente para completar a árvore. Da maneira como se percorreu a árvore, foi necessário resolver nove problemas lineares até se obter a solução final. Isto mostra que os métodos de busca, explicados anteriormente, combinados com heurísticas para determinação de bons limites inferiores, são fatores decisivos no tempo e eficiência nas resoluções dos problemas. Optando pelo caminho de melhor busca, a árvore mostrada na figura 3.4 poderia ser substituída pela apresentada na figura 3.5. Deste modo, a solução ótima é conseguida com apenas cinco Pls contra nove Pls mostrados anteriormente. 3.3 Steepest Descent Pairwise Interchange(SDPI) Heurística que realiza trocas entre pares de locais, comparando os custos atuais com os anteriores, em função das permutações encontradas. Foi primeiramente proposta por G.C. Armour e E.S. Buffa em [4]. Os custos são calculados levando-se em consideração apenas aquelas alterações provenientes da troca, ou seja, aqueles componentes que não são afetados pela troca não entram no cálculo do custo, diminuindo 3.3 SDPI (Steepest Descent Pairwise Interchange) 29 sensivelmente o esforço computacional. Observe que, para n = 4, para cada rodada de iterações (tomando com base uma permutação qualquer), tem-se C24 = 6 possibilidades de mudanças de pares. A diferença no valor do custo é computada e comparada com a anterior. Considera-se, então, uma nova permutação, e o processo continua. Esta Figura 3.6: Fluxograma SDPI [36] seção é fortemente baseada em [36]. Para desenvolvimento de uma rotina para implementação, a expressão que rege a diferença entre os custos atuais e anteriores deve ser considerada, sendo dada por: 3.3 SDPI (Steepest Descent Pairwise Interchange) DCTuv (a) = CT (a) − CT (a0 ) 30 (3.6) sendo DCT a diferença dos custos totais e a0 a nova permutação, proveniente da troca de pares u e v. A soma de todos os termos envolvendo u e v em CT (a) é dada por: n X wiu d (a(i), a(u)) + i=1,i6=v n X wiv d (a(i), a(v)) + wuv d (a(u), a(v)) (3.7) i=1,i6=u Com a troca de pares u e v, a nova soma passa a ser: n X wiu d (a(i), a(v)) + i=1,i6=v n X wiv d (a(i), a(u)) + wuv d(a(v), a(u)) (3.8) i=1,i6=u A equação (3.7) pode também ser escrita, adicionando-se: 0 = wvu d(a(v), a(u)) + wvu d(a(u), a(v)) − wvu d(a(v), a(u)) − wvu d(a(u), a(v)) (3.9) como: n X wiu d(a(i), a(u)) + i=1 n X wiv d(a(i), a(v)) − wuv d(a(u), a(v)) (3.10) i=1 Usando o mesmo artíficio, a equação (3.8) pode ser escrita : n X wiu d(a(i), a(v)) + i=1 n X wiv d(a(i), a(u)) + wuv d(a(v), a(u)) (3.11) i=1 O fluxograma para esse procedimento, conforme Chu, L.K., [36], é apresentado na figura 3.6. A mudança no custo em razão da troca de u e v é dada pela diferença (3.10) e (3.11): DCTuv (a) = n X (wiu − wiv )[d(a(i), a(u)) − d(a(i), a(v))] − 2wuv d(a(u), a(v)) (3.12) i=1 Observe que a condição: DCTuv (a∗ ) > 0 (3.13) induz à realização de troca de pares, pois garante que a nova permutação leva a um custo menor que a permutação atual. Com o exemplo abaixo para n = 6 podemos esclarecer o processo. 3.4 SDPI (Steepest Descent Pairwise Interchange) 31 Consideremos as matrizes abaixo e a permutação inicial (2, 4, 5, 3, 1, 6). Os pares trocados (2, 6) e (4, 5) nos dá a maior redução para o custo total, considerando a permutação inicial dada. Executando outros ciclos de iterações encontramos o custo mínimo valendo 92, Chu, L.K. [36]. Figura 3.7: Matriz Distância Figura 3.8: Matriz Fluxo Figura 3.9: Pares Permutados 3.4 3.4 Redes Neurais 32 Redes Neurais Modo de computação não algorítmica que busca emular a estrutura de funciona- mento de neurônios humanos. As Redes Neurais Artificiais (RNAs) são compostas por nós, ou seja, unidades de processamento simples capazes de calcular funções matemáticas. Estes são ligados entre si, formando várias conexões que poderão ser relacionadas a pesos, com a capacidade de deter conhecimentos apresentados no modelo. Apesar de existirem muitas diferenças entre as redes biológicas e as artificiais, as características comuns, ou seja, computação paralela e distribuída comunicando por intermédio de conexões sinápticas; a detecção de características; a redundância (com grande relevância no aprendizado) e modularização das conexões, permitem que as RNAs exerçam várias atividades só vistas nos seres humanos. Esta seção é baseada em S. Haykin [1]. O primeiro modelo proposto por McCulloch e Pitts [39] é uma imitação simplificada do neurônio biológico. Seu modelo matemático consiste em N terminais de entrada x1 , x2 , . . . , xn , que emulam os dendritos do cérebro humano. Estes dispositivos têm, como função, receber as informações, ou impulsos nervosos, provenientes de outros neurônios e levados até o corpo celular. Apenas um terminal de saída y foi proposto no modelo, representando os axônios do cérebro. O ponto de contato entre a terminação axônica de um neurônio e o dendrito de outro neurônio é chamado de sinapse. Estas, trabalhando com se fossem capacitores, regulam as informações transmitidas entre os nós da rede neural. A imitação do comportamento das sinapses nas RNAs acontece atribuindo pesos, w1 , w2 , ..., wn aos terminais de entrada. Os valores destes pesos poderão ser positivos ou negativos, dependendo se as sinapses são excitatórias ou inibitórias. A ponderação xi wi é o efeito de uma determinada sinapse no neurônio. Logo, os pesos wi determinam em que momento os neurônios devem considerá-las naquela conexão. Os sinais recebidos dos neurônios pré-sinápticos são passados para o corpo dos neurônios pós-sinápticos, onde são comparados com os outros sinais recebidos pelo mesmo. O disparo de um neurônio biológico acontece quando a soma dos impulsos recebidos é maior do que o seu limite de excitação (threshold ). No neurônio artificial, este comportamento é imitado por um sistema que realiza a soma ponderada xi wi , compara este somatório com o 3.4 Redes Neurais 33 Figura 3.10: Célula.[51]. limite de excitação e decide se o neurônio deve ou não disparar. Neste modelo, a ativação do neurônio é regida por uma “função de ativação”, que realiza ou não a saída, dependendo do valor da soma ponderada das entradas. Chamando de θ o limiar (threshold ) do neurônio, o nó da rede neural em questão terá a sua saída ativa quando: n X x i wi ≥ θ (3.14) i=1 sendo n o número de entradas e wi o peso relacionado à entrada xi . De acordo com a figura 3.11, para valores de entradas x1 , x2 , . . . , xm , com valores 0 (zero) ou 1 (um), a saída yk assumirá valores 0 ou 1, de acordo com a comparação entre a soma ponderada dos pesos e o limiar θ. Algumas limitações deste modelo devem ser consideradas. Dentre estas, destacamse, principalmente, a referente à possibilidade de implementação de somente funções linearmente separáveis, tendo pesos constantes, sem a possibilidade de qualquer tipo de ajuste. A solução de problemas não linearmente separáveis é obtida com o uso de redes com uma ou mais camadas intermediárias, ou escondidas. O uso de duas camadas intermediárias permite a aproximação de qualquer função. A preocupação que se deve ter na implementação deste tipo de rede é quanto ao número de nós utilizados nas camadas intermediárias, pois ele irá definir a precisão e a definição da função objetivo. 3.4 Redes Neurais 34 Figura 3.11: Modelo de Neurônio [51]. As redes de múltiplas camadas precisam utilizar funções de ativação que sejam não lineares e diferenciáveis, para que o gradiente possa ser calculado, direcionando o ajuste dos pesos. A função sigmoidal logística, mostrada abaixo, é a mais indicada, conforme aponta A.P.Braga [1]: y= 1 1 + e−x/T (3.15) O parâmetro T determina a suavidade da curva. Dependendo do tipo de problema que deverá ser tratado, na arquitetura da rede neural são parâmetros importantes: número de camadas da rede; número de nós em cada camada; tipo de conexão entre os nós; e topologia da rede. A figura 3.12 mostra diferenciações diversas quanto à estrutura de rede. Assim, as redes neurais podem ser classificadas:[1] (a) Quanto ao número de camadas: (i) Redes de camada única (figura 3.12 (a) e (e)); (ii) Redes de múltiplas camadas (figura 3.12 (b), (c), (d)). (b) Quanto às formas de conexões dos nós: (i) Feedforward ou acíclica (figura 3.12 (a), (b), (c)); 3.4 Redes Neurais 35 a b c d e Figura 3.12: Arquiteturas Redes Neurais. [1] (ii) Feedback, ou cíclica (figura 3.12 (d), (e)). (c) Quanto à conectividade: (i) Rede fracamente ou parcialmente conectada (figura 3.12 (b), (c), (d)); (ii) Rede completamente conectada: (figura 3.12 (a), (e)). O uso de redes neurais na resolução de problemas deve passar, em primeiro lugar, pela fase de aprendizagem, na qual a rede extrai padrões importantes do problema, criando o seu próprio modelo. É um processo iterativo, pelo qual os parâmetros da rede são ajustados, coletando-se informações do ambiente no qual está operando. O método de aprendizado mais comum é o supervisionado, pelo fato das entradas e saídas desejadas serem fornecidas por um supervisor. A figura 3.13 apresenta o modelo básico desse método. O que se espera encontrar é um padrão entre a entrada e a saída. A diferença entre a saída calculada pela rede e a diferença da saída desejada tende a diminuir à medida que o processo continua. Isto se deve aos ajustes realizados nos pesos das conexões, com o objetivo de minimizar esta diferença a cada passo. O desempenho da rede poderá ser medido, verificando-se a soma dos erros quadráticos de todas as saídas. A forma geral para alteração dos pesos por correção de erros, segundo D.E.Rumelhart 3.4 Redes Neurais 36 Saída Professor RNA Entrada Erro Figura 3.13: Modelo Aprendizado Supervisionado [1] Figura 3.14: Aprendizado do Perceptron 3.5 Redes Neurais MLP 37 et al [46], é dada pela seguinte equação : wi (t + 1) = wi (t) + ηe(t)xi (t) (3.16) sendo η a taxa de aprendizado e xi (t) a entrada para o neurônio i no tempo t. O termo e(t) do erro equivale a: e(t) = d(t) − y(t) para d(t) a saída desejada e y(t) a resposta calculada no instante t. Assim, a minimização da soma dos erros quadráticos das saídas poderá ser dada, segundo D.E.Rumelhart [46], pela expressão : k F (w) = 1X (di − yi (w))2 2 i=0 (3.17) na qual k é o número de nós da saída da rede. Na determinação da condição de erro mínimo, duas situações podem ocorrer: • a superfície do erro, dada pela expressão (3.17), possui um único mínimo, quando a rede é formada inteiramente por unidades de processamento lineares; ou • a superfície do erro possuir, além do mínimo global, um ou mais mínimos locais, quando a rede é formada por unidades de processamento não-lineares. Neste último caso, nem sempre o mínimo global é atingido, já que as superfícies de erro são irregulares, podendo levar à um mínimo local indesejado. O interesse na utilização de redes neurais é resolver problemas não-linearmente separáveis. Isto leva ao uso de redes neurais com uma ou mais camadas intermediárias ou escondidas, de modo que seja possível a aproximação de qualquer função. Uma das soluções para este problema seria subdividi-lo e aplicar, em cada um deles, uma rede simples. Mas isto muita das vezes é impossível ou muito complicado. 3.5 Redes Neurais MLP Nas redes Multilayer perceptrons (MLP), o processamento em cada nó é baseado nos processamentos dos nós anteriores conectados a ele. As camadas intermediárias geram uma codificação interna das camadas de entrada, servindo de definição da saída 3.5 Redes Neurais MLP 38 Figura 3.15: Mínimos locais e platôs em uma superfície de erro[1] da rede. Não se pode deduzir que quanto maior for o número de camadas intermediarias da rede, melhor será o resultado. Cada vez que o erro é medido durante o treinamento, ele se torna menos preciso. A camada final recebe somente uma estimativa do erro. A penúltima camada recebe a estimativa da estimativa do erro. Existem, na literatura, vários algoritmos para treinamento das redes MLP. O mais utilizado é o algoritmo back-propagation, que utiliza os pares entrada e saída da rede para ajuste dos pesos. Duas fases são utilizadas neste mecanismo: na primeira, denominada forward, a rede é percorrida no sentido entrada/saída, na qual, em função dos dados de entrada, se define a saída; a segunda, chamada backward, sentido saída/entrada, os pesos são atualizados nas conexões, utilizando as saídas desejada e fornecida pela rede, procurando diminuir a diferença entre elas (G.Cybenko, [11]). A técnica de backpropagation está representada na figura 3.16. A regra delta, proposta por Widrow e Hoff [1], serve de suporte para o algoritmo backpropagation. A base deste algoritmo se prende nos ajustes dos pesos nos nós, de modo a definir os erros das camadas intermediárias. Os ajustes destes pesos são calculados utilizando o método do gradiente, ou seja, para uma condição inicial qualquer w(0) = wi , deseja-se obter a direção do ajuste a ser aplicado no vetor de pesos, de forma a caminhar em direção à solução ótima. Este é o motivo pelo qual as funções de ativação das redes MLP precisam ser diferenciáveis. O algoritmo backpropagation é baseado nesta regra delta e por isso também é chamado de regra delta generalizada 3.5 Redes Neurais MLP 39 Figura 3.16: Fluxo processamento do Algoritmo Backpropagation.[1] (A.P.Braga et al, [1]). A medida do erro total é dada pela equação: p k 1 XX p (d − yip )2 E= 2 1 i=1 i (3.18) sendo p o número de padrões, k o número de unidades de saída, di é a i-ésima saída desejada e yi é a i-ésima saída calculada pela rede. Como visto acima, é a soma dos erros dos nós de saída que deverá ser minimizada. Sem risco de perda de generalidade, a minimização do erro para cada padrão levará à minimização do erro total. Assim, tem-se (o desenvolvimento a seguir tem como referência A.P.Braga et al,[1]) k 1X (di − yi )2 E= 2 i=0 (3.19) A variação do peso para um dado padrão (gradiente descendente do erro) é dado por: ∆wji = −k sendo k uma constante. ∂E ∂wji (3.20) 3.5 Redes Neurais MLP 40 O ajuste de cada peso em cada nó da rede em busca do erro mínimo: ∂E ∂netj ∂E = ∂wji ∂netj ∂wji Sendo netij = n P (3.21) xi wji , tem-se i=1 ∂netj = wji n P ∂ xl wjl l=1 (3.22) = xi wji O lado direito da equação (3.21) mede o erro no nó j e geralmente é chamado de δj : δE ∂netj (3.23) ∂E ∂yj δE = ∂netj ∂yj ∂netj (3.24) δj = Aplicando a regra da cadeia temos: δj = contudo, ∂yj ∂f (netj ) = = f 0 (netj ) ∂netj ∂netj (3.25) Com relação ao erro no nó da última camada: ∂E = ∂yi ∂( 21 k P (di − yi )2 ) i=1 (3.26) ∂yj que é a fórmula da regra delta . Com referência à equação 3.24, substituindo os dois termos do lado direito, temos: δj = (dj − yj )f 0 (netj ) (3.27) Se o nó de saída não for o nó j e utilizando a regra da cadeia: M M X ∂E ∂netl X ∂E ∂E = = ∂yj ∂net ∂netl l ∂yj l=1 l=1 ∂ n P wil yi i=1 ∂yj = M X ∂E wjl ∂net l l=1 (3.28) sendo, M M X X ∂E wjl = δl wjl ∂net l l=1 l=1 (3.29) 3.5 Redes Neurais MLP 41 Com referência à equação (3.24), substituindo, mais uma vez, os dois termos do lado direito, tem-se para a camada intermediária: δj = f 0 (netj ) X ∂l wlj (3.30) l Logo, a generalização da fórmula de ajuste de pesos é dada por: ∆wji = ηδj xi (3.31) wji (t + 1) = wji (t) + ηδj (t)xi (t) (3.32) que é o mesmo de: Então, para o nó de saída, o erro δj será definido pela equação 3.27; caso contrário, pela equação 3.30. 3.5.1 Algoritmo de Levenberg-Marquardt Visando minimizar a equação (3.19), alguns algoritmos trabalham em conjunto com o backpropagation. Dentre eles, destaca-se o algoritmo Levenberg-Marquardt, que calcula as derivadas de segunda ordem do erro quadrático em relação aos pesos, o que vale dizer o mesmo que derivar o algoritmo backpropagation tradicional. Esta ação faz com que o treinamento seja mais rápido. Este algoritmo utiliza-se da matriz jacobiana para o cálculo da matriz hessiana, nos mesmos moldes do método Quasi-Newton. Logo, conforme [2]: H= ∂ 2 ER (W ) ∂W 2 (3.33) ∂e(W ) ∂W (3.34) J= sendo e(W ) definido como: e(W ) = n X (yi − yd ) (3.35) i=1 yi representa a saída calculada e yd a saída desejada. Como já se sabe, o treinamento da rede neural depende da soma dos erros quadráticos, sendo assim, a matriz hessiana é calculada usando a matriz jacobiana como artifício, já que esta última é de cálculo mais simples: 3.6 Colônia de Formigas 42 H = J T (W )J(W ) (3.36) Os pesos são atualizados como é feito no método de Newton: W (k + 1) = W (k) − H −1 gk (3.37) gk = 2J T (W )e(W ) (3.38) A parcela gk vale: Combinando as equações anteriores, o algoritmo de Levenberg-Marquardt, atualiza os seus pesos: W (k + 1) = W (k) − [J T (W )J(W ) + µk I]−1 J T (W )e(W ) (3.39) Sendo I a matriz identidade e µk a constante do algoritmo em questão (Anderson Henrique Barbosa et al,[2]) 3.6 Colônia de Formigas Com base na interação de vários agentes autônomos, a colônia de formigas tra- balha de forma cooperativa a procura de alimentos. Nesta ação de procura, com o objetivo de preservação da espécie, as formigas depositam no solo uma substância química (feromônio), que serve como meio de comunicação entre elas. Na interação dos diversos agentes autônomos, na procura por alimento, a concentração do feromônio se torna mais acentuada no caminho mais curto. Isto porque, a cada momento, mais formigas utilizam este caminho, depositando cada vez mais feromônio. Esta meta-heurística de inteligência coletiva possui as seguintes características (Leandro dos Santos Coelho et al [34]): • algoritmo não determinista, já que não garante um ótimo global. • algoritmo paralelo e adaptativo, pois os diversos agentes agem de forma simultânea e independente. 3.7 Conclusão 43 • algoritmo cooperativo, visto que o caminho escolhido por cada agente tem como referência as informações depositadas por outros agentes, quando da procura por alimentos. No problema quadrático de alocação, no caso de arranjos físicos, considere-se uma população de m formigas, sendo k uma formiga qualquer. A probabilidade de que a k-ésima formiga atribua o departamento j à localização i é dada por(Leandro dos Santos Coelho et al [34]): pkij (t) = [τ (t)]α [ηij ]β P ij [[τij (t)]α [ηij ]β (3.40) Nesta equação, α e β são ajustados heuristicamente, sendo α a ponderação do feromônio (0 ≤ α ≤ 1); β a ponderação da informação heurística (0 ≤ β ≤ 1); ηij = 1 dij é a visibilidade entre as variáveis j e i e vice-versa; dij é distância euclidiana entre as localizações; τij é a intensidade da trilha no caminho. 3.7 Conclusão Limitações de cada método de resolução ficam evidentes. O método Branch and Bound é melhor aplicado para problemas discretos, no qual se utilizam relaxações da condição de integralidade para solucão dos problemas, necessitando de grande esforço computacional à medida que o problema possui maior número de variáveis envolvidas. As redes neurais MLP e o algoritmo SDPI, metaheurísticas que necessitam de ajustes para fugir de mínimos locais, não garantem solução ótima e, no caso das redes neurais, precisam de um banco de dados para o seu treinamento. Capítulo 4 Aplicação de Redes Neurais MLP à Solução do Problema de Arranjo Físico 4.1 Introdução Neste capítulo, é apresentado um estudo em uma fábrica de embalagem metálica, no qual todos foram abordados todos os processos de fabricação e algumas necessidades administrativas. Áreas de conhecimento inerentes a este processo são avaliadas, construindo uma base de informação essencial para a coleta de dados. O tipo de produto que é fabricado nesta unidade industrial permite considerar cada módulo de fabricação (departamento) como se fosse um equipamento específico. Esta consideração faz com que as áreas das localizações dos módulos sejam iguais, predefinindo os corredores de circulação, as distâncias entre as localizações, área total necessária para implantação do projeto e as áreas individuais requeridas. A tabela 4.1 apresenta os fatores do projeto e as áreas de conhecimento envolvidas (Torres, Isaías [59]). As atividades envolvidas para fabricação do produto final requerem movimentação de pessoas e equipamentos, trocando informações e materiais entre os departamentos. Estas trocas representam as necessidades de comunicação entre os pares. No problema tratado, as áreas responsáveis pelas operações de corte e repuxo do corpo, tampa e fundo da embalagem metálica a ser produzida, devem estar próximas do es- 44 4.2 Desenvolvimento do Modelo de Projeto 45 Tabela 4.1: Áreas de conhecimento para projeto de arranjos físicos Fatores de Projeto Áreas e sub-áreas de conhecimentos envolvidas Equipamento. Eng. de Processos, Ergonomia, Organização Operação (Transformação e Eng. de Processos, Eng. de Materiais, Eng. de Máquinas, Montagem). Logística,Ergonomia, Eng. de Segurança, PCP. Materiais. Eng. de Materiais, Logística, Eng. de Segurança, Ergonomia. Manutenção. Eng. de Manutenção, Eng. de Máquinas, PCP. Segurança e Saúde. Eng. de Segurança, Eng. de Processos, Saúde Ocupacional, do trabalho, Eng. de Máquinas, Eng. de Segurança. Administração, Organização do Trabalho. Almoxarifado/Estoque. Logística, PCP. Serviços auxiliares de Fábrica. Eng. de Processos, Eng. de Máquinas, PCP. Edificação Arquitetura, Eng. Civil, Eng. Segurança, Ergonomia, PCP Sistemas de Movimentação PCP, Logística, Ergonomia, Eng. de Segurança. Utilidades (Gás, Energia) Eng. de Processos, Eng. de Máquinas, Eng. de Materiais. Fluxo de Materias, PCP, Logística, Eng. Econômica, Eng. de Segurança, Pessoas e Informações. Organização do Trabalho. Espaço Ergonomia, Eng. de Segurança, Eng. de Processos, PCP, Arquitetura. Serviços de Pessoal Organização do Trabalho, Eng. de Segurança, Arquitetura, Administração. toque de matéria prima. Entre o setor de secagem e os aplicadores de vedante, existe um alto grau de dependência, obrigando estas duas operações a ficarem próximas. Sendo assim, a disposição física destes módulos deve oferecer, obedecendo às restrições, o menor caminho para o maior fluxo entre os pares. 4.2 Desenvolvimento do Modelo de Projeto Otimizar o arranjo físico de uma planta industrial significa decidir de que maneira as áreas de trabalho serão dispostas nesta instalação. Entende-se como área de trabalho a ocupação de espaço físico por parte de, por exemplo, máquinas, pessoas, departamentos, área para estoques, oficinas, dispositivos de segurança, etc. O objetivo principal é tornar lógicos os movimentos inerentes ao processo de produção, sejam movimentos de pessoas, máquinas ou materiais. Quando se trata de designar objetos a locais de tal maneira que cada local tenha somente um objeto, conhecidas as distâncias entre os locais e os fluxos entre os de- 4.2 Desenvolvimento do Modelo de Projeto 46 partamentos, o modelo baseado no problema quadrático de alocação permite encontrar uma disposição de custo mínimo dos departamentos aos locais, sendo o custo dado pelo produto distância e fluxo. 4.2.1 Variáveis de Interesse A minimização do custo total de interconexão deverá ser regida pelas seguintes variáveis: • distância entre as localidades; • fluxo entre os departamentos, que representa o grau de ligação entre eles, evidenciando a importância entre os pares no processo de fabricação; • número de departamentos; • número de localidades. Figura 4.1: Distribuição espacial das localidades A figura 4.1 mostra a distribuição espacial das localidades e as distâncias, em metros, entre elas. Observe que o projeto possui vinte e dois departamentos e vinte e duas 4.2 Desenvolvimento do Modelo de Projeto 47 Tabela 4.2: Relação dos Departamentos do Projeto. Item Departamento Item Departamento Item Departamento 1 Administração 9 Repuxo Tampa 17 Repuxo Fundo 2 Cont. de Qualidade 10 Vedante Tampa 18 Vedante Fundo 3 Est. Mat. Prima 11 Secagem Tampa 19 Estoque Fundo 4 Contabilidade 12 Estoque Tampa 20 Recravação 5 Expedição 13 Corte Corpo 21 Est. Prod. Acabado 6 Rec. de Materiais 14 Repuxo Corpo 22 Oficina Mecânica 7 Refeitórios 15 Estoque Corpo 8 Corte Tampa 16 Corte Fundo localizações a serem associados, tendo a denominação dada na tabela 4.2. 4.2.2 Formulação Matemática Proposta O problema a ser resolvido, ou seja, permutar departamentos em locais previamente conhecidos, de tal modo que o custo de transporte entre um departamento e outro seja o mínimo possível, é inteiro e binário. Inteiro, porque os departamentos e os locais não podem ser subdivididos. Binário, porque um dado departamento está ou não está em um determinado local. Sendo assim, o modelo apresentado atende às necessidades do projeto. Seja fij o fluxo entre os departamentos i e j e dkp a distância entre as localizações k e p. A função objetivo é definida por: min n n X X fij dkp xij xkp (4.1) i,j=1 k,p=1 sendo o produto cijkp = fij dkp o custo de transporte a considerar. Esta função está sujeita às restrições: n X xij = 1, 1 ≤ j ≤ n, (4.2) n X xij = 1, 1 ≤ i ≤ n, (4.3) xij ∈ {0, 1} , 1 ≤ i, j ≤ n (4.4) i=1 j=1 4.2 Desenvolvimento do Modelo de Projeto 48 As restrições indicam a relação bijetora entre departamentos e localidades, ou seja, cada departamento em um local e cada local somente com um departamento. Observe que (4.1) é uma fun ção não-linear, visto a existência de produto entre as variáveis xij e xkp . Uma técnica de resolução deste tipo de modelo não-linear é linearizálo, através de algum procedimento matemático, e resolvê-lo como um problema de otimização linear. Uma forma de realizar esse intento é como segue. O produto fij dkp é chamado custo de transporte cijkp entre os departamentos. O termo cijkp xij xkp da função objetivo contém a não linearidade. Uma vez que as variáveis xij xkp são binárias, possuindo os valores 0 ou 1, o custo somente terá valor diferente de zero quando estas duas variáveis valerem 1. Assim, pode-se substituí-las por somente uma variável yijkp = xij xkp , de modo que: yijkp 1, se x = 1 e x = 1 ij kp = 0, caso contrário. (4.5) Com este artifício de linearização, o algoritmo Branch and Bound pode ser aplicado até o limite de número de departamentos suportado pela plataforma utilizada. O problema em análise consiste na alocação de 22 (vinte e dois) departamentos, relacionados na tabela 4.2, em 22 (vinte e dois) locais, com as distâncias entre os locais conhecidas. Estes departamentos guardam entre si graus de interconexão, que podem ser medidos pelo fluxo de transporte existente entre eles. Os valores destes fluxos variam para cada tipo de atividade industrial, representando as necessidades de ligação entre os pares. Os valores de fluxo dependem, principalmente, do tipo de produto e da quantidade a ser fabricada, diferenciando os departamentos em razão de sua importância dentro da fábrica. Para se resolver o problema com base no modelo proposto, o entendimento do que a variável yijkp representa é essencial. Sabendo-se que se trata de um problema inteiro binário, cada elemento representado por esta variável é um departamento a ser alocado. O valor de yijkp será igual a 1 (um) se o departamento i estiver posicionado em um determinado local e terá valor zero se não estiver. Considere y como sendo um vetor. Para o primeiro departamento, este vetor varia das posições y1 até y22 ; para o segundo departamento, serão atribuídas as posições de y23 até y44 e assim sucessivamente. Portanto, o vetor y terá 484 posições no problema abordado, já que deve-se posicionar vinte e dois departamentos para vinte e dois locais. 4.3 Aplicação do Algoritmo Branch and Bound 49 A matriz formada por estes vetores terá dimensão 22 × 22 e será construída com base nas matrizes fluxo e distância, já definidas. Em relação às restrições, cada departamento ocupará somente um local, ou seja, a soma dos valores de y para este departamento deverá ser igual a unidade. Por exemplo, 66 P xi = 1. Ao mesmo tempo, cada local deverá ter um para o terceiro departamento, e somente um departamento. 4.3 i=45 Aplicação do Algoritmo Branch and Bound No caso específico da fábrica de embalagem, o número de departamentos con- siderado (n = 22) é elevado para aplicação do algoritmo Branch and Bound, face ao crescimento exponencial das variáveis e restrições envolvidas. Este problema será devidamente tratado com a utilização de redes neurais MLP. Sendo assim, será desenvolvida a lógica do algoritmo Branch and Bound para n = 4 departamentos, oferencendo suporte para instâncias maiores (n ≤ 15). Considere as matrizes aleatórias de fluxo (F ) e distância (D) entre os departamentos. 0 2 10 8 2 0 4 12 F = 10 4 0 6 8 12 6 0 0 1 9 7 1 0 3 11 D= 9 3 0 5 7 11 5 0 (4.6) (4.7) 4.3 Aplicação do Algoritmo Branch and Bound 50 Tabela 4.3: Permutações possíveis n No. de Diagonais Ordem Matriz Custo Arranjos Possíveis 4 2 6 4!=24 5 5 10 5!=120 6 .. . 9 .. . 15 .. . 6!=720 .. . 12 54 66 12!=479.001.600 de modo que a matriz de custo resultante seja: 2 18 14 6 22 10 10 90 70 30 110 50 8 72 56 24 88 40 C= 4 36 28 12 44 20 12 108 84 36 132 60 6 54 42 18 66 30 (4.8) Como pode ser visto, a dimensão da matriz de custo é 6×6. Isto se deve às diagonais existentes no polígono formado pelos departamentos. Logo, para n departamentos, o número de ligações será dado por: n(n − 3) +n 2 (4.9) A ordem da matriz-custo a considerar será igual ao número total de interconexões. A tabela 4.3 mostra o número de permutações possíveis em problemas crescentes em número de departamentos (n). No exemplo em questão, o número de arranjos possíveis é mostrado na figura 4.2. O resultado da aplicação do algoritmo Branch and Bound a esse exemplo particular é mostrado na tabela 4.4. Como pode ser verificado no código do programa e na tabela 4.4, os arranjos 11 e 14 têm custo mínimo de 198, sendo portanto adequados para localização dos quatro departamentos. Verificando os arranjos possíveis para n = 4 , os pares de arestas (1, 2), (3, 4) e (1, 4), (2, 3) não poderão ser adjacentes. O código para sua obtenção está apresentado no apêndice A.1 e utiliza explicitamente as restrições apresentadas no problema. A tabela 4.4 mostra a saída do exemplo mostrado, quando aplicado ao código desenvolvido. 4.4 Aplicação do Algoritmo Branch and Bound 51 Figura 4.2: Arranjos para 4 departamentos De acordo com a tabela 4.4, pode-se verificar o comportamento decrescente do gap relativo entre os limites (GREL). Calculado em relação ao melhor limite inferior (MLI) e o melhor ponto inteiro (MPI), esta medida demonstra o quão rápido o algoritmo alcança o ótimo global. É calculado de acordo com a expressão: GREL = para o nó sete, por exemplo, tem-se: GREL = 210−198 210 M P I−M LI MP I , ∼ = 8, 5% Observando a primeira coluna, verifica-se que foi necessário explorar nove nós da árvore de branch para alcançar a resposta desejada. Este valor está intimamente ligado à estratégia utilizada para o "corte" (branching) desta árvore e o modo como a percorremos. Para este caso exemplo, foi adotada a estratégia de corte mininfeas (minimum integer infeasibility), ou seja, o corte é feito em relação à variável que possui valores próximos a zero ou um, mas não igual a zero ou um. Quanto ao método de procura, o best search foi aplicado. A alteração destas estratégias pode mudar sensivelmente a quantidade de nós explorados. A segunda coluna da tabela 4.4 exibe as relaxações que foram realizadas em torno das variáveis inteiras para que se fosse possível utilizar o algoritmo Branch and Bound. 4.4 Aplicação da Rede Neural MLP 52 Tabela 4.4: Resultado Branch and Bound Relaxação Melhor ponto Nós não Melhor limite Nós Gap relativo Explorados Linear Inteiro explorados inferior entre os limites(%) 1 186 - 2 186 - 2 222 222 1 186 16 3 186 222 2 186 16 4 222 222 1 186 16 5 192 222 2 186 16 6 210 210 1 192 8,5 7 196 210 2 192 8,5 8 198 198 1 196 1 9 220 198 0 196 1 4.4 Aplicação da Rede Neural MLP O objetivo principal desta seção é mostrar a aplicação do algoritmo backpropaga- tion em conjunto com o algoritmo Levenberg-Marquardt para treinamento de uma rede neural MLP. Quatro etapas foram consideradas, a saber: • Preparação dos dados; • Criação da rede neural; • Treinamento da rede; e • Simulação da rede para o problema apresentado. 4.4.1 Preparação dos dados Como já dito anteriormente, para valores n > 15, não é aplicável a utilização de algoritmos enumerativos para a solução de problemas combinatoriais deste porte. O uso de heurísticas se torna necessário para solução adequada do problema. Como acontece no aprendizado dos seres humanos, as redes neurais também necessitam de treinamento suficiente para aprender. Este treinamento depende diretamente da quantidade de informações disponíveis, formando uma base de dados 4.4 Aplicação da Rede Neural MLP 53 confiável. Mas, neste caso, a quantidade de dados à disposição não é suficiente para treinamento da rede neural face a necessidade de validação da rede e a complexidade da solução inerente a estes problemas. Logo, uma heurística foi utilizada para formar um banco de dados capaz de treinar a rede neural adequadamente. Gradiente Descendente com Trocas de Pares e um gerador de matrizes de entrada (22 × 22) construíram a base de dados para treinamento da rede, ou seja, as matrizes fluxo e distância, bem com os vetores permutação, que guardam valores da função objetivo tão próximo do mínimo quanto possível. É importante ressaltar que o uso desta heurística, tem como objetivo, apresentar à rede as características inerentes aos dados de entrada relacionados com os dados de saída, não se preocupando especificamente com o valor exato da resposta. Devemos “ensinar” a rede neural a descobrir a lógica utilizada pela heurística. Para cada departamento, existem fluxos relacionados com os demais departamentos, o mesmo acontecendo para as distâncias em relação aos locais. Com a vetorização das matrizes fluxo e distância, necessária para configurar a rede neural, o número de entradas teria a dimensão 968 × 1. Mas como estas matrizes são simétricas podem-se eliminar as diagonais (valores iguais à zero) como também os elementos das matrizes triangular superior(ou inferior), já que possuem os mesmos valores. Com este artifício, diminui-se sensivelmente a quantidade de dados de entrada, descartando aqueles que não contribuem para o treinamento. O objetivo é construir uma rede neural capaz de determinar a melhor disposição dos departamentos nos locais, apresentando a esta rede as matrizes fluxo e distância, de tal maneira que o custo seja o mínimo possível. Tem-se um total de 100 pares de vetores de entrada, com 2 × 231 elementos cada par (matriz fluxo e matriz distância), e 100 vetores de saída com 22 posições, indicando quais as localizações dos departamentos. Neste ponto, é interessante verificar se existe alguma redundância entre os dados de entrada, devido à possível correlação existente entre eles. Para isto, aplica-se a análise de componentes principais, que consiste, basicamente, em eliminar aqueles componentes que pouco contribuem para a variação dos dados. Em seguida, normaliza-se os dados de entrada [pn,meanp,stdp] = prestd(p), de modo que a média dos valores seja zero e a variância um. Após o treinamento, a conversão dos dados normalizados para os dados originais é feita, com o auxílio da matriz ptrans, [ptrans,transMat] = prepca(pn,0.01), sendo que o parâmetro 0,01 indica que 4.4 Aplicação da Rede Neural MLP 54 são eliminados aqueles elementos que contribuem com até 1% do total de variação do conjunto. Sendo Q o conjunto dos 100 pares de vetores de entrada mencionados anteriormente, dividiu-se este conjunto em quatro partes iguais, conforme figura 4.3. Reservouse um quarto para a validação , um quarto para o teste e dois quartos para o treinamento da rede neural, garantindo, assim, que os dados sejam escolhidos de maneira uniforme através dos dados originais. Figura 4.3: Preparação dos Dados. Agora pode-se criar a rede neural para o treinamento Neural (Network Toolbox User’s Guide, [55]). 4.4.2 Criação da Rede Neural Em primeiro lugar, definiu-se o número de camadas escondidas da rede. A escolha para duas camadas se deve ao fato desta configuração conseguir mapear quaisquer dados de quaisquer função, linear ou não-linear apresentada à rede. A utilização de muitas camadas escondidas não é aconselhável, pois poderia comprometer as correções dos erros, tão necessárias na retropropagação. O que se procura definir é um número pequeno de camadas com número adequado de neurônios. Normalmente, o uso de uma camada escondida é suficiente, mas para este caso do PQA, duas camadas escondidas foram necessárias e a quantidade de neurônios por camadas foi determinada em função da dimensão do problema. Este procedimento é empírico. Mesmo assim, existem 4.4 Aplicação da Rede Neural MLP 55 propostas para determinação do número de neurônios: calcula-se a média aritmética ou mesmo a média geométrica entre as dimensões da entrada e saída da rede e atribui este valor ao número de neurônios na camada escondida. Ou, de posse da quantidade de exemplos disponíveis para o treinamento, utiliza-se um número de sinapses dez vezes menor que este número. Se o número de exemplos for muito maior que o número de sinapses, overfitting é improvável, no entanto pode ocorrer underfitting (a rede não converge durante o seu treinamento). Para este caso, a arquitetura da rede neural foi baseada em duas camadas intermediárias com função de transferência tan sigmoid [55] e uma camada de saída com função de transferência linear. Foram usados cinco neurônios nas camadas escondidas e esta rede deverá ter vinte e dois neurônios na camada de saída já que tem-se vinte e dois objetivos a serem alcançados (vetor posição de cada departamento). Figura 4.4: Estrutura Rede Neural O esquema mostrado na figura 4.4 mostra a estrutura da rede com duas camadas intermediárias trabalhando com cinco neurônios cada uma. 4.4.3 Treinamento da Rede Neural MLP Grande cuidado deve ser tomado na escolha dos parâmetros para treinamento do algoritmo backpropagation na configuração de uma rede neural MLP. Pequenas diferenças na escolha destes parâmetros podem levar às grandes diferenças no tempo de treinamento e comprometer a generalização desejada. Não existe um método para estas escolhas, somente a experiência e dados históricos ou gerados servem como base. 4.4 Aplicação da Rede Neural MLP 56 O meio termo entre um modelo muito rígido e um extremamente fléxivel seria o ideal, a ponto de não modelar fielmente os dados ou modelar também o ruído. Não se deseja que a rede responda aos valores exatos dos dados de entrada, e sim, às características inerentes à eles. As sinapses dos neurônios de cada camada armazenam as informações do procedimento a ser aprendido pela rede, e as saídas de cada camada alimentam as entradas da camada seguinte durante a fase de treinamento. Para que este treinamento seja bem efetuado, o parâmetro taxa de aprendizado foi bem definido. Este valor variou entre 0, 1 e 1 e que não permita um aprendizado muito lento e oscilações no treinamento, prejudicando a convergência do processo. Um dos objetivos foi escapar de mínimos locais, conseguindo um treinamento rápido e seguro. O algoritmo Levenberg-Marquardt (trainlm) foi utilizado em conjunto com o backpropagation. Figura 4.5: Código para o Treinamento Rede MLP 4.4.4 Simulação da Rede Neural MLP Feitas as etapas anteriores, a função ”Sim”(figura 4.7) simula a rede neural, atribuindo à entrada os valores das matrizes distância e fluxo devidamente vetorizadas, ou seja, dimensão [231 × 1] para cada uma delas, totalizando 462 elementos. Matriz triangular superior equivale às distâncias e matriz triangular inferior aos fluxos entre os departamentos.(ver tabela 4.5) O vetor permutação gerado pela rede neural deverá ser ajustado para representar as posições dos departamentos nos locais. Os valores deste vetor apresentam variações em torno dos números inteiros pertecentes ao intervalo [1, 22], já que a convergência da rede não é absoluta. Deve-se aproximá-los para o inteiro mais próximo. O primeiro 4.4 Aplicação da Rede Neural MLP Figura 4.6: Treinamento (Normalizado) Rede Neural Figura 4.7: Código para Simulação da Rede Neural MLP 57 4.4 Aplicação da Rede Neural MLP 58 Tabela 4.5: Matriz de Entrada: Fluxo e Distância . 20 45 68 88 25 36 65 85 112 48 62 71 87 117 127 68 92 95 115 118 148 8 . 26 48 69 35 32 47 68 96 52 58 58 79 105 114 71 95 90 115 111 138 9 1 . 22 43 58 46 33 54 81 71 66 55 80 99 105 86 109 96 125 110 135 6 7 8 . 21 78 63 31 46 71 88 77 58 83 96 98 101 121 102 133 111 130 6 7 7 1 . 96 78 38 42 60 103 87 63 86 91 90 112 131 107 139 110 124 4 1 1 1 1 . 24 60 81 105 23 44 60 71 103 115 44 67 74 91 100 131 1 6 1 1 1 1 . 43 58 82 25 29 37 51 82 93 41 64 59 83 82 112 1 5 1 1 1 1 7 . 21 49 67 49 27 52 67 72 75 93 72 103 80 101 1 6 1 1 1 1 3 7 . 28 78 54 27 46 50 52 81 95 67 99 68 84 1 5 1 1 1 1 3 5 8 . 99 72 46 52 36 30 96 105 72 101 60 65 1 2 3 6 1 1 3 4 1 1 . 28 53 55 89 102 21 45 54 69 82 114 1 6 1 1 1 1 1 1 1 1 1 . 28 28 61 74 27 44 33 59 57 88 1 5 1 1 1 1 1 1 1 1 1 7 . 25 45 57 54 69 45 76 55 80 1 6 1 6 1 1 1 1 1 1 1 1 1 . 34 47 46 52 21 53 32 61 1 6 1 1 1 1 1 1 1 2 1 1 1 1 . 15 79 80 45 70 25 34 1 6 1 1 1 1 1 1 1 2 1 1 1 1 7 . 94 95 60 84 38 35 1 6 1 1 1 1 1 1 1 7 1 1 1 1 6 7 . 24 37 48 66 99 1 5 3 6 1 1 1 1 1 1 1 1 1 1 4 4 2 . 35 27 61 91 1 5 1 1 1 1 3 1 7 1 7 6 6 5 1 1 1 1 . 32 29 61 1 2 4 7 1 1 2 2 4 1 3 2 2 3 3 2 1 1 1 . 46 72 1 1 1 1 1 1 2 3 2 1 2 2 2 1 2 1 1 1 1 1 . 32 3 4 3 1 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 . valor deste vetor indica que o departamento 14 (quatorze) está na posição 1 (um), o segundo valor indica que o departamento 16 (dezesseis) está na posição 2 (dois)e assim sucessivamente até a posição 22 (vinte e dois).Ver figura 4.9. Figura 4.8: Arranjo obtido com a Rede Neural MLP 4.5 Análise dos resultados 4.5 59 Análise dos resultados 4.5.1 Introdução Para fins de comparação de resultados, foram desenvolvidos um algoritmo exato baseado em matrizes de permutação, rede neural MLP e algoritmo Branch and Bound. As heurísticas SDPI e Colônia de Formigas foram extraídas de bibliografia sobre o assunto. Os testes realizados tiveram como objetivo obter resultados comparativos nas instâncias apresentadas. 4.5.2 Experimento Para treinamento da rede neural MLP, várias simulações foram realizadas, alterando, em cada uma delas, o número de camadas intermediárias, a quantidade de neurônios destas camadas e o algoritmo de treinamento. A configuração final resultante, 2 camadas intermediárias, 5 neurônios, e algoritmo Levenberg Marquardt para treinamento, responderam adequadamente às expectativas. As dimensões das matrizes de entrada foram reduzidadas eliminando valores repetidos face à simetria dos seus dados. Com isto, evitou-se a redundância desnecessária, tão prejudicial ao treinamento da rede neural. Este procedimento foi responsável pelo decréscimo no tempo de treinamento e estabilidade na convergência. O conjunto de dados formados pelas matrizes de entrada deve ser suficiente para treinamento da rede neural. Com isto, foi necessário formar um banco de dados para esta finalidade, já que o volume de dados na literatura é insuficiente. Com base em um gerador randômico de matrizes, para n = 22 , a heurística SDPI construiu 100 (cem) vetores de saída para a rede neural . Sendo assim, dividiu-se este conjunto em quatro partes iguais, cabendo duas delas para o treinamento da rede e as duas restantes para teste e validação, respectivamente. 4.5.3 Resultados Obtidos e Limitações Para as instâncias até n = 9, os algoritmos exatos e Branch and Bound demonstraram-se eficientes no resultado da função objetivo, garantindo, em tempo aceitável, 4.6 Análise 60 o ótimo local. Mas, para instâncias maiores do que 15, estes dois algoritmos não apresentaram desempenho viável: tempo de processamento muito alto com a plataforma utilizada. Para o caso específico em estudo, n = 22 , os algoritmos exatos não foram capazes de resolver. A rede neural, treinada com base na Heurística SDPI, forneceu vetor de saída (22 × 1) com valores não inteiros pertencentes ao intervalo [1, 22] 4.6 Análise O vetor de saída desejado, em comparação com o vetor de saída real, apresentou diferenças em relação aos valores absolutos deste último. Isto se deve a não convergência absoluta da rede. A interpretação da resposta dada pela rede foi fator importante no resultado final. Os valores esperados são inteiros e pertencem ao intervalo [1, 22], logo foi preciso ajustar a saída da rede com base nestes valores (ver figura 4.9). Figura 4.9: Vetor Saída Rede Neural Com relação ao PQA exato, foram testadas todas as possibildades de disposição dos departamentos. Este algoritmo somente obteve respostas para instâncias até n = 9, com tempo de processamento 314 minutos, sendo este tempo alterado a cada simulação 4.7 Análise 61 Tabela 4.6: Comparação dos Resultados Número de Departamentos (n) Rna MLP Branch and Bound Colônia de Formigas QAP Exato SDPI 4 7 9 15 22 VFO 208393 194230 379782 4203 32040 ITER 7 10 12 11 11 TEMPO(s) 2,35 2,29 3,16 2,76 3,27 VFO 203711 189152 357163 - - ITER 9 1210 5230 - - TEMPO(s) 0,34 0,63 111,05 - - VFO 234015 192312 359276 4198 31215 ITER 1000 1000 10000 10000 100000 TEMPO(s) 0,87 1,02 1,01 67,58 197,34 VFO 203711 189152 357163 - - ITER 24 5040 362880 - - TEMPO(s) 1,38 2,41 1864,68 - - VFO 237615 198030 357163 4219 50030 ITER 86 70 64 110 120 TEMPO(s) 0,52 0,41 0,43 3,71 12,71 em virtude da aleatoriedade das matrizes de entrada usadas. Para valores maiores do que nove, não se consegue obter qualquer resposta, face à capacidade de processamento da plataforma utilizada. O algoritmo Branch and Bound, com auxílio da função Bintprog do MatLab, resolveu instância até n = 13 em 22, 7 minutos. Não foi possível resolver para instâncias maiores, mesmo alterando o limite inferior para valores próximos àqueles encontrados pela rede neural. Com o uso do algoritmo baseado em colônia de formigas, o valor da função objetivo de 31215 atendeu às necessidades do projeto obtendo redução no custo de transporte em comparação com o arranjo físico inicial. Tempo de processamento de 6, 3 minutos foi aceitável em comparação com os outros algoritmos. 4.7 Análise 4.7 62 Conclusão Neste capítulo foi apresentado o modelo matemático para o problema proposto com base no PQA. As variáveis de interesse foram definidas de acordo com o estudo de caso proposto, ou seja, arranjo físico em uma fábrica de embalagem com vinte e dois departamentos. Foi desenvolvido um exemplo para n = 4 departamentos para esclarecer a lógica utilizada pelo algoritmo Branch and Bound, utilizando a toolbox do Software MaTlab especificamente a função Bintprog. Algoritmo exato foi desenvolvido produzindo resultados exatos até para n = 9 departamentos, a partir deste valor não foi possível obter resultados com a plataforma utilizada. (Pentium IV, 2.8 GHz, 512 Mb memória RAM). O uso de Rede Neural MLP, teve como banco de dados para o seu treinamento, validação e teste, dados gerados pela heurística SDPI. Esta heurística forneceu à rede neural cem matrizes 22 × 22 (matrizes de distâncias e fluxo), bem como os vetores resposta desejados que serviram de suporte ao algoritmo Backpropagation e LevenbergMarquardt. Capítulo 5 Conclusão Geral e Trabalhos Futuros Para se resolver problemas combinatoriais, em primeiro lugar deve-se verificar a dimensão do espaço solução, para se definir a melhor ferramenta para resolusão do problema. No caso de otimização de arranjo físico, o número de departamentos (n) a serem alocados serve de parâmetro para escolha do algoritmo adequado. Para valores de n <10 , algoritmos com base na enumeração completa do espaço solução poderá ser utilizado em tempo aceitável. Para valores de n menores do que 15(quinze), o algoritmo Branch and Bound é aplicável, retornando solução ótima para o problema. Mas, no estudo realizado, com n =22 departamentos, o uso de heurística é o aconselhável, já que o número de possibilidades de solução torna desaconselhável o uso de algoritmos exatos. A solução procurada é um ótimo local, que atenda às necessidades do projeto. Redes Neurais apresentam-se como ferramentas promissoras para situações que envolvem a indústria, onde se encontra o mesmo problema que deverá ser resolvido várias vezes, alterando apenas algumas situações de contorno. A escolha de uma rede neural MLP esbarrou na limitação de dados históricos que servissem de suporte para treinamento da rede, já que deve-se ensiná-la com base em exemplos. Apesar do treinamento ter como base um banco de dados gerado pela heurística SDPI, o resultado foi satisfatório, garantindo melhor custo em relação ao arranjo físico inicial. Isto demonstra que o treinamento da rede neural não se preocupou com os valores absolutos dos dados apresentados a ela e, sim, com as características destes dados. 63 5.0 Conclusão 64 A arquitetura da rede neural é tão importante quanto a base de dados que ela utiliza para treinamento e ainda de como esta base de dados é apresentada para a rede. A simplificação deste conjunto de dados, normalizando-os e aproveitando a simetria das matrizes, foi fator importante no tempo e na qualidade do treinamento. A comparação, em um mesmo gráfico, do treinamento, da validação e do teste permitiu acompanhar o progresso do treinamento. Com base neste gráfico, pode-se concluir que o resultado é aceitável, já que os erros do teste e da validação têm comportamentos similares e não existe nenhum sinal de overfitting. O importante a ser ressaltado é a resposta obtida pela rede neural em comparação com os outros algoritmos, mesmo sendo treinada com dados não exatos, conseguiu-se bons resultados. Também foi verificado que a implementação de camadas intermediárias, com o objetivo de diminuir o tempo de treinamento e aumentar o aprendizado da rede, obteve sucesso, já que o arranjo físico resultante atendeu às necessidades da unidade de negócio, oferecendo diminuição nos custos operacionais e agregando valor ao produto final. Já o desempenho dos algoritmos exatos, enumerativos ou não, ficam comprometidos, à medida que o valor de n cresce. Para desenvolvimento de trabalhos futuros, novas arquiteturas de redes neurais poderão ser aplicadas, combinando com algoritmos evolutivos, para se tentar melhorar, ainda mais, a qualidade do arranjo físico final. Apêndice A Implementações MaTlab A.1 Código para algoritmo Branch and Bound Matrizcusto = c = Matrizcusto(:); 2 18 14 6 22 10 70 30 110 50 8 72 56 24 88 40 4 36 28 12 44 20 12 108 84 36 132 60 6 54 42 18 66 30 10 90 (A.1) A primeira restrição do problema obriga cada departamento ocupar somente um lugar. A soma dos valores dos vetores xi correspondente à um departamento deverá ser um. numLocais = 6; numDep = 6; numDim = numLocais * numDep; onesvector = ones(1,numLocais); Aeq = blkdiag(onesvector,onesvector,onesvector,onesvector, onesvector,onesvector); beq = ones(numDep,1); A segundo grupo de restrições obriga cada local ter um e somente um departamento. e = eye(1,numLocais); 65 A.1 Apêndice: Implementações MaTlab 66 A = repmat(e,numLocais,numDep); for i = 2:6 A(i,:) = circshift(A(i-1,:),[0,1]); end b = ones(numLocais,1); O terceiro grupo de restricões faz referência às arestas não adjcentes mencionadas anteriormente. Em primeiro lugar a matriz de pesos D é criada tomando como base a posição relativa entre os locais. Aqueles próximos atribui-se a unidade, e aqueles que não estão próximos, valores maiores que a unidade. D = zeros(numLocais); D(1,2:end) = [1 5 5 5 5 ]; D(2,3:end) = [1 5 1 5 ]; D(3,4:end) = [1 5 1 ]; D(4,5:end) = [5 5]; D(5,end) =1; D = triu(D)’ + D; Com esta rotina impomos que as arestas não adjacentes não poderão ser vizinhas. [localA,localB]= find(D < 2); numPares = length(localA) numlinhas = 2*numPares + numLocais; A((numLocais+1):numlinhas, 1:numDim) = zeros(2*numPares,numDim); for i = 1:numPares A23 = 2; A14 = 4; A23NolocalA = sub2ind([numLocais numDep],localA(i),A23); A14NolocalB = sub2ind([numLocais numDep],localB(i),A14); A(i+numPares+numLocais, [A23NolocalA, A14NolocalB]) = 1; A12 = 1; A34 = 3; A12NolocalA = sub2ind([numLocais numDep],localA(i),A12); A34NolocalB = sub2ind([numLocais numDep],localB(i),A34); A(i+numPares+numLocais, [A12NolocalA, A34NolocalB]) = 1; A24 = 6; A13 = 5; A.2 Apêndice: Implementações MaTlab 67 A24NolocalA = sub2ind([numLocais numDep],localA(i),A24); A13NolocalB = sub2ind([numLocais numDep],localB(i),A13); A(i+numLocais, [A24NolocalA, A13NolocalB]) = 1; end b(numLocais+1:numLocais+2*numPares) = ones(2*numPares,1); x0 =[]; Utilização da Toolbox BINTPROG, Matlab, para determinação do custo mínimo. f = c; options = optimset(’Display’,’iter’,’NodeDisplayInterval’,1); [x,fval,exitflag,output] = bintprog(f,A,b,Aeq,beq,x0,options); fval exitflag output ; options = optimset(options,’BranchStrategy’,’mininfeas’); [x,fval,exitflag,output] = bintprog(f,A,b,Aeq,beq,x0,options); fval exitflag output; options = optimset(options,’NodeSearchStrategy’,’df’); [x,fval,exitflag,output] = bintprog(f,A,b,Aeq,beq,x0,options); fval exitflag output; A.2 Gerador de Matrizes %-------------------------------------------------------%Gerador das Matrizes de Entrada para heurística SDPI %-------------------------------------------------------%Gera 100 vetores de entrada for zz=i:100 %Número de Departamentos n=22 %Matriz Fluxo Assimétrica mrf=randint(n,n,[0,100]); %Matriz Distância Assimétrica A.3 Apêndice: Implementações MaTlab 68 mrd=randint(n,n,[1,100]); %Preparação das Matrizes Simétricas. t=mrf+mrf’; u=mrd+mrd’; v=tril(t,-1); x=triu(t,1); %Matriz Fluxo W=v+x; g=tril(u,-1); h=triu(u,1); %Matriz Distância D=g+h; end A.3 SDPI(Steepest Descent Pairwise Interchange) %*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*. %Com base nas matrizes fluxo e distância, esta rotina calcula o vetor %saída de posição dos departamentos. %*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*. function [TCout,aout] = sdpi(W,D) %SDPI Steepest Descent Pairwise Interchange para QAP. % [TC,a] = sdpi(W,D) % m = número de localizações % W = m x m matriz fluxo % D = m x m mmatriz distância % a = vetor permutação randômico inicial %********************************************************************* %Verificação de erros error(nargchk(2,5,nargin)); if nargin < 3 || isempty(a0), a0 = 1; end if nargin < 4, C = []; end if nargin < 5, XY = []; end A.3 Apêndice: Implementações MaTlab 69 [m,cW] = size(W); [rD,cD] = size(D); if length(a0(:)) == 1, nruns = a0; a0 = []; else nruns = 1; end if m ~= cW error(’W deve ser matriz quadrada’) elseif rD ~= cD error(’D deve ser matriz quadrada’) elseif m ~= rD error(’W e D devem ter a mesma dimensão’) elseif ~isempty(a0) && (length(a0(:)) ~= m || any(sort(a0) ~= 1:m)) error(’a0 não é um vetor permutação factível’) elseif ~isempty(C) && any(size(C) ~= [m m]) error(’C deve ter dimensão m x m’) elseif ~isempty(XY) && any(size(XY) ~= [m 2]) error(’XY deve ter dimensão m x 2’) end %************************************************************************ TC = Inf; if ~isempty(XY) sdpiplot(XY), title(’’), pauseplot(Inf) defpause = 1; end if nargout == 0 && nruns > 1, disp(’ ’), end for k = 1:nruns TC0 = Inf; A.3 Apêndice: Implementações MaTlab 70 if isempty(a0), ak = randperm(m); else ak = a0; end TCk = sum(sum(W(ak,ak).*D)); %TC Inicial if (nargout == 0 || ~isempty(XY)) && nruns == 1 if isint(TCk), s = ’d’; else s = ’f’; end str1 = sprintf([’TC inicial = %’ s],TCk); str2 = [’ a =’ sprintf(’ %d’,ak)]; if nargout == 0, fprintf(’\n%s\n%s\n’,str1,str2), end if ~isempty(XY) sdpiplot(XY,W,ak), title(str1), pauseplot(defpause) end end while TCk < TC0 TC0 = TCk; a0k = ak; for i = 1:m-1 for j = i+1:m aij = a0k; aij([j i]) = aij([i j]); if isempty(C) TCij = sum(sum(W(aij,aij).*D)); else D = D + diag(diag(ones(m))); TCij = sum(sum((W(aij,aij) + diag(diag(C(aij,:)))) .* D)); end if TCij < TCk TCk = TCij; ak = aij; ik = i; jk = j; end A.3 Apêndice: Implementações MaTlab 71 end end if ~isequal(a0k,ak) if (nargout == 0 || ~isempty(XY)) && nruns == 1 if isint(TCk), s = ’d’; else s = ’f’; end str1 = sprintf([’Troca %d and %d: TC = %’ s],jk,ik,TCk); str2 = [’ a =’ sprintf(’ %d’,ak)]; if nargout == 0, fprintf(’%s\n%s\n’,str1,str2), end if ~isempty(XY) sdpiplot(XY,W,ak), title(str1), pauseplot(defpause) end end if TCk < TC && nruns > 1 && ~isempty(XY) sdpiplot(XY,W,ak) title([’Min TC = ’,num2str(TCk)]) pauseplot(defpause) end end end if nargout == 0 if isint(TCk), s = ’d’; else s = ’f’; end if nruns == 1 disp([sprintf([’ TC Final = %’ s ’\n a =’],TCk) ... sprintf(’ %d’,ak)]) disp(’ ’) else disp([sprintf([’Run %d: Min TC = %’ s ’\n k,TCk) sprintf(’ %d’,ak)]) TCsave(k) = TCk; a = ’],... A.4 Apêndice: Implementações MaTlab 72 end end if TCk < TC TC = TCk a = ak; end end if nargout == 0 && nruns > 1 nTC = sum(TCsave == TC); TCpercent = round(100*(nTC/nruns)); if isint(TC), s = ’d’; else s = ’f’; end disp([sprintf([’\nMin TC = %’ s ... ’ (Found in %d of %d runs (%d%%))\n a =’], ... TC,nTC,nruns,TCpercent) sprintf(’ %d’,a)]), disp(’ ’) end if nargout > 0 TCout = TC; aout = a; end A.4 Colônia de Formigas % Ant Algorithm for the Quadratic Assignment Problem % By Kyriakos Tsourapas % You may contact me through the Mathworks site % University of Essex 2002 clc; clear; disp(’Please wait...’); disp(’ ’); ENTRA COM AS MATRIZES FLUXO E DISTÂNCIA. A.4 Apêndice: Implementações MaTlab pr_size = size(DF, 1); ants = 5; % NUMBER OF ANTS max_assigns = 10000; % NUMBER OF ASSIGNMENTS (WHEN TO STOP) optimal = 107; % OPTIMAL SOLUTION a = 1; % WEIGHT OF PHEROMONE b = 5; % WEIGHT OF HEURISTIC INFO lamda = 0.8; % EVAPORATION PARAMETER Q = 10; % CONSTANT FOR PHEROMONE UPDATING AM = ones(ants,pr_size); % ASSIGNMENTS OF EACH ANT min_cost = -1; % HEURISTIC INFO - SUM OF DISTANCES BETWEEN SITES for i=1:pr_size D(i) = sum( DF(1:i-1,i) ) + sum( DF(i,i+1:pr_size) ); end % START THE ALGORITHM assign = 1; while (assign <= max_assigns) & ( (min_cost > optimal) | (min_cost == -1) ) % =============== FIND PHEROMONE =============== % AT FIRST LOOP, INITIALIZE PHEROMONE if assign==1 % SET 1 AS INITIAL PHEROMONE pher = ones(22); % IN THE REST OF LOOPS, COMPUTE PHEROMONE else for i=1:pr_size for j=1:pr_size 73 A.4 Apêndice: Implementações MaTlab tmp = zeros(ants,pr_size); tmp( find(AM==j)) = 1; tmp = tmp(:,i); tmp = tmp .* costs’; tmp( find(tmp==0) ) = []; tmp = Q ./ tmp; delta(i,j) = sum(tmp); end end pher = lamda * pher + delta; end % ============ ASSIGN DEPTS TO SITES ============ % EACH ANT MAKES ASSIGNMENTS for ant=1:ants % GET RANDOM DEPT ORDER depts = rand(pr_size, 2); for i=1:pr_size depts(i,1) = i; end depts = sortrows(depts,2); % KEEP AVAILABLE SITES IN A VECTOR for i=1:pr_size free_sites(i) = i; end pref = ones(pr_size,1); % PREFERENCE FOR EACH SITE prob = ones(pr_size,1); % PROBABILITIES FOR EACH DEPT for dept_index=1:pr_size % GET SUM OF THE PREFERENCES 74 A.4 Apêndice: Implementações MaTlab 75 % AND THE PREFERENCE FOR EACH SITE pref_sum = 0; for site_index=1:size(free_sites,2) tmp_pher = pher(depts(dept_index), free_sites(site_index)); pref(site_index) = tmp_pher^a * ( 1/D(free_sites(site_index)) )^b; pref_sum = pref_sum + pref(site_index); end % GET PROBABILITIES OF ASSIGNING THE DEPT % TO EACH FREE SITE prob = free_sites’; prob(:,2) = pref / pref_sum; % GET THE SITE WHERE THE DEPT WILL BE ASSIGNED prob = sortrows(prob,2); AM(ant,dept_index) = prob(1); % ELIMINATE THE SELECTED SITE FROM THE FREE SITES index = find(free_sites==prob(1)); prob(1,:) = []; free_sites(index) = []; pref(index) = []; end % GET THE COST OF THE ANT’S ASSIGNMENT costs(ant) = 0; for i=1:pr_size for j=1:i-1 dept_flow = DF(i,j); site1 = AM(ant,i); site2 = AM(ant,j); if site1 < site2 A.5 Apêndice: Implementações MaTlab sites_distance = DF(site1, site2); else sites_distance = DF(site2, site1); end costs(ant) = costs(ant) + dept_flow * sites_distance; end end if (costs(ant) < min_cost) | (min_cost == -1) min_cost = costs(ant); ch_assign = AM(ant,:); end if mod(assign,100) == 0 end assign = assign + 1; end end clc; disp( sprintf(’Cheapest Cost : %d’, min_cost)); disp( sprintf(’Assignments : %d’, assign-1)); disp(’ ’); disp(’Assignment’); disp(’----------’); ant_index = find(costs==min(costs)); for i=1:pr_size disp( sprintf(’Dept %d to Site %d’, i, ch_assign(i))); end A.5 Algoritmo Exato tic n=9%Número de Departamentos mrf=randint(n,n,[0,100]);%Matriz Fluxo Assimétrica 76 A.5 Apêndice: Implementações MaTlab mrd=randint(n,n,[1,100]);%Matriz Distância Assimétrica %Preparação das Matrizes Simétricas. t=mrf+mrf’; u=mrd+mrd’; v=tril(t,-1); x=triu(t,1); W=v+x; g=tril(u,-1); h=triu(u,1); D=g+h; for c=1:10 mf=W; md=D; end custoi=inf; perm=perms(1:n); for p=1:factorial(n) b=perm(p,:); mfp=mf([b],[b]); mcp=mfp.*md; custo(p)=sum(mcp(:))/2; if custo(p)<custoi custoi=custo(p); end end vfo=custoi; ind=find(custo==custoi); vr=perm(ind,:); [l,z]=size(vr); for r=1:l s=vr(r,:); mfp=mf([s],[s]); vr; mf; md; mfp; end q=0; i=0; j=0; for j=1:n for i=1:n if i>j q=q+1; f(q,1)=mf(i,j); d(q,1)=md(i,j); fp(q,1)=mfp(i,j); end end end 77 A.5 Apêndice: Implementações MaTlab mc=f*d’ mctp=fp*d’ mru=zeros(n); z=0; for z=1:n mru(vr(z),z)=1; end; mru vr vfo toc 78 Bibliografia [1] A.P.Braga, André P.L.F de Carvalho, Tereza Bernada Ludermir Redes Neurais Artificiais. Teoria e Aplicações (2000) [2] Anderson Henrique Barbosa; Marcílio Sousa da Rocha Freitas; Francisco de Assis das Neves, Confiabilidade estrutural utilizando o método de Monte Carlo e redes neurais Revista Escola de Minas Print ISSN 0370-4467,(2005) [3] APPLE, J. M.; DEISENROTH, M. P A computerized plant layout Analysis and evaluation technique (PLANET). Proceedings of the 23rd Annual Conference and Convention, AIIE. California, p. 121-127,(1972) [4] Armour, G.C. e Buffa, E.S. Heuristic algorithm and simulation approach to relative location of facilities. Management Science, 9(2), 294-309.(1963) [5] AZADIVAR, F.; WANG, J. Facility layout optimization using simulation and genetic algorithms. International Journal of Production Research, v. 38, n. 17, p. 4369-4383(2000) [6] BAZARAA, M. S Computerized layout design: a branch and bound approach. AIIE Transactions, v. 7, n. 4, p. 432-437(1975) [7] Bazaraa, M.S. & Kirca, O. A branch-and-bound based heuristic for solving the quadratic assignment problem Naval Research Logistics Quarterly, 30, 287304.,(1983) [8] Bos, J. A quadratic assignment problem solved by simulated annealing.Journal of Environmental Management, 37(2), 127-145.,(1993) [9] Christofides, N. & Benavent, E. An exact algorithm for the quadratic assignment problem Operation Research, 37(5), 760-768.,(1989) 79 Bibliografia 80 [10] Cung,V.D A scatter search based approach for the quadratic assignment problem IEEE international Conference on Evolutionary Computation,165-169.(1997) [11] G.Cybenko. Aproximation by superpositions of a sigmoidal function.Mathematics of Control, Signal and Systems,2:303-314.(1989) [12] Edwards,C.S The derivationof a greedy aproximator for a Koopmans Beckman quadratic assignment problemProceedings of 77-th Combinatorial Programming Conference(CP77),55-86.(1977) [13] Elshafei, A.N. Hospital layout as a quadratic assignment problem. Operations Research Quarterly, 28(1), 167-179.,(1977) [14] Fedjki, C.A. & Duffuaa, S.O. An extreme point algorithm for a local minimum solution to the quadratic assignment problem. Operational Research, 156(3), 566-578.,(2004) [15] Robinson, D.F and Foulds, L Comparison of phylogenetics treesMathematical Biosciences, 53:131-147,(1981) [16] Gidas, B., Ni, W. M. e Nirenberg, L., Symmetry and related properties via the maximum principle, Comm. Math. Phys., 68, 209-243 (1979). [17] João Carlos Furtado e Luiz Antônio Nogueira Lorena OTIMIZAÇÃO EM PROBLEMAS DE LEIAUTE LAC/INPE - Instituto Nacional de Pesquisas Espaciais (1997) [18] Gavett, J.W. & Plyter, N.V. The optimal assignment of facilities to locations by branch-and-bound. Operations Research, 14, 210-232.(1966) [19] Valdair Candido MartinsI; Leandro dos Santos CoelhoII; Marco Antonio Barbosa CândidoII; Ricardo Ferrari Pacheco Otimização de layouts industriais com base em busca tabu doi: 10.1590/S0104-530X2003000100006,(2003) [20] M. Gondran, M. Minoux. Graphes et Algorithmes. Collection des Études et Recherches d´Électricité de France, Eds. Eyrolles, 1995. [21] Hartman, P., “Ordinary Differential Equations”, Baltimore 369-402. [22] Kusiak, A. and SS Heragu The Facility Layout Problem European Journal of ... 91-76, Faculty of Management, Laval University, Québec, Canada(1991) Bibliografia 81 [23] Hiller, F.S and Michael, M.C Quadratic Assignment Problem algorithms and location of indivisible facilities. Manegement Science,13,44-57,(1966) [24] Hassan, M. M. D. Machine Layout Problem in Modern Manufacturing Facilities Int. J. of Production Research, Vol. 32, no. 11, pp2559-2584,(nov 1994) [25] Jünger, M. & Kaibel, V On the qap polytope. Technical Report 96.241, Angerwandte Mathematik und Informatik, Universität zu Köln.(1996a) [26] Jünger, M. & Kaibel, V A basic study of the QAP polytope. Technical Report 96.215, Angerwandte Mathematik und Informatik, Universität zu Köln.(1996b) [27] Jünger, M. & Kaibel, V The qap-polytope and the star transformation. Discrete Applied Mathematics, 111(3), 283-306.(2001) [28] Koopmans, T.C and Beckman, M.J Assignment problens and the location of economic activities Econometrica, 25,53-76. [29] Karisch,S.E Trust regions and relaxations for the quadratic assignment problem Series in Discrete Mathematics and Theoretical Computer Science, 16,199-219, AMS,Rhode Island.(1994) [30] Kaku, B.K. & Thompson, G.L. An exact algorithm for the general quadratic assignment problem. European Journal of Operational Research, 2, 382390.(1986) [31] Andrew KUSIAK and Sunderesh S. HERAGU The facility layout problem Department of Mechanical and Industrial Engineering, University of Manitoba, Winnipeg, Manitoba, Canada R3T2N2,(1987) [32] Lawer, E.L The quadratic assignment problem Management Science, 9, 586599.(1963) [33] LEE, R. C.; MOORE, J. M. computerized relationship layout planning Industrial Engineering, v. 18, p. 195-200,(1967) [34] Leandro dos Santos Coelho & Roberto Fernandes Tavares Neto Colônia de Formigas: Uma Abordagem Promissora para Aplicações de Atribuição Quadrática e Projeto de Layout XXIV ENEGEP Florianópolis, SC, Brasil, 03 a 05 de novembro de 2004 Bibliografia 82 [35] Liang, Y. Combinatorial optimization by Hopfield networks using adjusting neurons. Information Sciences, 94(1-4), 261-276.,(1996) [36] Chu, L.K., Facilities Design Layout Analysis, The University of Hong Kong, Department of Industrial and Manufacturing Systems Engineering,September, (2005), em http://http://www.imse.hku.hk/lkchu/IEIM- download/BEng-MFA.pdf. [37] Eliane Maria Loiola, Nair Maria Maia de Abreu, Paulo Oswaldo Boaventura Netto it Uma revisão comentada das abordagens do problema quadrático de alocação Pesquisa Operacional Print ISSN 0101-7438,(2004) [38] Mans, B.; Mautor, T. & Roucairol, C. A parallel depth first search branch and bound algorithm for the quadratic assignment problem. European Journal of Operational Research, 81, 617-628.,(1995) [39] W.S.McCulloch and W.Pitts. A Logical Clculus of the ideas immanent in nervous activity. Bulletin of Mathematical Biophysics, 5:115-133.(1943) [40] RD Meller and K.-Y. Gau. The facility layout problem: Recent trends and perspectives, J. of Manufacturing Systems, vol. 15, no. 5, pp. 351–366 (1996) [41] MONTREUIL, B. A modeling framework for integrating layout design and flow network design. Proceeding of the Material Handling Research Colloquium, Hebron, KY, p. 43-58(1990) [42] MONTREUIL, B.; VENKATADRI, U.; RATLIFF, H. D. Generating a layout from a design skeleton. IIE Transactions, v. 25, n. 1, p. 3-15(1993) [43] Nugent, C.E.; Vollmann, T.E. e Ruml, J.. An experimental comparison of techniques for the assignment of facilities to locations. Operations Research, 16, 150-173.(1968) [44] Pierce,J.F and Crowston, W.B Tree-search algorithms for quadratic assignment problem naval Reseach Logistics Quarterly,18,136.(1971) [45] Rangel,M.C e Abreu,N.M.M Ordenações parciais nos conjuntosdas soluções dos problemas de alocação linear e quadrático. Pesquisa Operacional,23(2),265-284 (2003). Bibliografia 83 [46] D.E.Rumelhart, G.E Hinton, andR.J.Willians. Learning represetation by backpropagation erros. Nature,323:533-536.(1986) [47] Savsar, M. , Effects of Random Material Flow Volumes on Layout Flexibility ,International Journal of Industrial Engineering ,Vol.12 ,pp.234-243 ,June ,(2005). [48] SEEHOF, J. M.; EVANS, W. O.Automated layout design program. Industrial Engineering , v. 18, p. 690-695,(1967) [49] Sérgio Haffner Técnicas de Otimização (94430-03) Introdução à Otimização em Engenharia. [50] Siu, F. & Chang, R.K.C Effectiveness of optimal node assignments in wavelength division multiplexing networks with fixed regular virtual topologies. Computer Networks, 38(1), 61-74.,(2002) [51] S. Haykin, Neural Networks, 2nd ed ., Prentice Hall, Upper Saddle River, New Jersey, (1999). [52] A. H. Land e A. G. Doig, An automated method for solving discrete programming problems, Econometrica, 28, 497-520, 1960. [53] Steinberg, L.The backboard wiring problem: A placement algorithm. SIAM Review, 3, 37-50.(1961) [54] KY Tam and SG Li A hierarchical approach to the facility layout problem Int. J. of Production Research, vol. 29, no. 1, pp. 165–184(1991) [55] Neural Network Toolbox User’s Guide Ó COPYRIGHT 1992 - 2000 by The MathWorks, Inc. [56] TOMPIKINS, J. A.; REED Jr., R. An applied model for the facilities design problem International Journal of Production Research, v. 14, n. 5, p. 583595(1976). [57] John A.White Facilities Planning ISBN:0471032999 (1984). [58] Torki, A.; Yajima,Y. & Enkawa,T. A low-rank bilinear programming approach for sub-optimal solution of the quadratic assignment problem. European Journal of Operational Research, 94(2), 384-391.,(1996). Bibliografia 84 [59] Torres, Isaías Integração de ferramentas computacionais aplicadas ao projeto e desenvolvimento de arranjo físico de instalações industriais. São Carlos: UFSCar, 154p, 2001. [60] Tsuchiya, K.; Bharitkar, S. & Takefuji, Y. A neural network approach to facility layout problems. European Journal of Operational Research, 89(3), 556563.,(1996) [61] Tsuchiya, K.; Nishiyama, T. & Tsujita, K. A deterministic annealing algorithm for a combinatorial optimization problem using replicator equations. Physica D: Nonlinear Phenomena, 149(3), 161-173,(2001) [62] Wolkowisz,H. Semidefinite programming aproaches to the quadratic assignment problem Nonlinear Assignment Problem:Algorithms and Aplicationsedited by P.M Pardalos and L.Pitsoulis, Combinatorial optimization Series,7,143-174, Kluwer Academic Publishers,(2000b) [63] Vollmann, T.E. Buffa, E.S. The Facilities Layout Problem in Perspective [64] Yu, J. & Sarker, B.R. Directional decomposition heuristic for a linear machinecell location problem European Journal of Operational Research, 149(1), 142184.,(2003). [65] Zhao,Q. Semidefinite programming relaxations for the quadratic assignment problem Journal Combinatorial Optimization,2,71-109.(1998)