Modelo de otimização binível e biobjetivo para a escolha e localização de sensores

Tese de mestrado em Investigação Operacional, apresentada à Universidade de Lisboa, através da Faculdade de Ciências, 2012Um grande número de estudos tem sido desenvolvido para a resolução de problemas com vários objetivos (problemas multiobjetivo) ou vários níveis de decisão (problemas multinível). No entanto, estudos sobre problemas que combinem estas duas características ainda são escassos. Este trabalho tem como objetivo propor uma resolução do problema, binível e biobjetivo, da escolha da configuração de uma rede de sensores e a sua respetiva localização num espaço bi-dimensional (nomeadamente num quadrado), de forma a minimizar os custos totais (aquisição e instalação) e maximizar a percentagem de área coberta (e consequentemente, reduzir o risco de não-deteção). Para resolver o problema foi desenvolvido um algoritmo evolutivo, que percorre o conjunto de soluções de Nível Superior (com o número de cada tipo de sensor a usar), explorando para cada uma dessas soluções, no Nível Inferior, as melhores localizações para os sensores. O algoritmo apresenta como output uma lista de soluções potencialmente não-dominadas. De forma a compreender para que conjuntos de parâmetros o algoritmo apresenta melhores resultados, foram executados diversos testes, com as várias fronteiras potencialmente de Pareto resultantes a serem comparadas através do indicador de qualidade, hipervolume. Este indicador permite comparar diferentes fronteiras potencialmente de Pareto, avaliando a dominância das soluções e a sua distribuição ao longo do Espaço dos Objetivos. Os resultados dos testes permitiram identificar oportunidades para tornar o algoritmo mais eficiente. Assim será conveniente integrar um método que permita uma pesquisa não-exaustiva e inteligente no Nível Superior, bem como um método que seja capaz de distribuir melhor os sensores no espaço admissível. Adicionalmente, este algoritmo deverá permitir resolver problemas com regiões admissíveis e avaliações de custo e risco mais realistas.A large number of studies have been developed to solve problems with multiple objectives (multi-objective optimization) or multiple decision levels (multi-level optimization). Nevertheless, studies about problems that combine these two characteristics are still rare. The objective of this dissertation is to offer a possible resolution to the bi-level and bi-objective problem, that is choosing a sensor network configuration and its distribution on a bidimensional space (namely, a square), in order to minimize the total costs (procurement, installation) and to maximize the percentage of covered area (and therefore, to reduce the risk of non-detection). In order to solve this problem, an evolutionary algorithm was developed that analyzes the solution set at the Upper Level (with the number of each type of sensor to be used), searching, in the Lower Level, the best locations for any of those sensors. The algorithm produces as output a list of potentially non-dominated solutions. In order to better understand the set of parameters to which the algorithm provides betters results, various tests were executed, with the potential Pareto frontiers given as an output, being compared by the quality indicator, hypervolume. This indicator allows us to compare different potential Pareto frontiers, by evaluating the dominance of their solutions and their distribution in the Objective Space