O framework NP-Opt e suas aplicações a problemas de otimização

Resumo: Uma das maiores dificuldades em se trabalhar com otimização combinatória éque os metodos utilizados requerem procedimentos específicos para cada pro¬blema tratado. Mesmo metodos de uso geral, como os algoritmos evolutivos, precisam de operadores desenvolvidos especificamente para os problemas. Su¬ponha, por exemplo, que alguem tenha desenvolvido um código que resolva problemas de Sequenciamento em Máquina Simples. Caso essa pessoa queira agora mudar e resolver um problema de Flowshop, tera que reformular grande parte de seu coídigo, perdendo assim um tempo precioso devido a uma baixa reutilizacão das partes de seu programa. Para reduzir esse problema, desen¬volvemos um ambiente de otimizacão, batizado de NP-Opt, que permite um alto grau de reutilizacao do codigo, facilitando a migracão de um tipo de pro¬blema para outro. No centro desse ambiente, estao dois algoritmos evolutivos: um Genético eum Memetico.Nesta tese examinaremos de forma detalhada os aspectos principais do framework e ainda serão apresentados resultados de desempenho para qua¬tro tipos de problemas NP que fazem parte do NP-Opt: Sequenciamento em Máquina Simples, Flowshop Permutacional com Famílias de Tarefas, Gate Ma¬trix Layout e Ordenamento de Genes.Ha ainda um problema nao incorporado ao framework devido a necessidade de comunicacao constante com pacotes ex¬ternos, mas cuja implementacão utilizou classes do NP-Opt: Localizacao de Capacitores em Redes de Energia Elétrica. Este problema esta descrito como uma aplicacao externa ao NP-Opt.Abstract: One of the greatest difficulties in working with combinatorial optimization is that the methods require specific procedures for each problem. Even general purpose methods, like Evolutionary Algorithms, require operators developed specifically for the problems. Suppose, for example, that someone has de¬veloped a code to solve Single Machine Scheduling problems. If such person decides to change and address a Flowshop problem, most of this code will have to be changed, wasting precious time due to a low reutilization of the software components. In order to overcome this problem, we developed an optimization framework, named Np-Opt, which allows a high degree of code reutilization, facilitating the migration from any type of problem to another. The core of this framework is composed of two evolutionary algorithms:aGenetic and a Memetic. In this thesis we will examine thoroughly all the main characteristics of the framework and present results for four different NP problems that are incor¬porated to the NP-Opt: Single Machine Scheduling, Permutational Flowshop with families of jobs, Gate Matrix Layout and Gene Ordering. A fifth problem, which was not included in the framework due to the need of accessing external packages, but whose implementation uses NP-Opt classes is also commented. It is named Capacitor Allocation in Distribution Networks, and is described as an external application of the NP-Opt