Algoritmos Meta-Heurísticos para Aplicação a Localização baseada em Sistemas Acústicos

Tese no âmbito do Doutoramento em Engenharia Eletrotécnica e de Computadores, Ramo de Especialização em Telecomunicações, apresentada à Faculdade de Ciências e Tecnologia da Universidade de CoimbraA presente dissertação aborda o problema da localização no espaço de uma fonte acústica, com o recurso a algoritmos meta-heurísticos. Tradicionalmente, as metodologias adotadas neste contexto baseiam-se em aproximações de um estimador estatístico (não convexo), aplicando-se posteriormente métodos de procura heurísticos. Tais métodos implicam normalmente soluções eficientes à custa de elevado poder de computação, podendo no entanto, apenas fornecer soluções subótimas. Através do uso de métodos meta-heurísticos, nomeadamente, métodos baseados em enxames de partículas, o problema de localização é aqui abordado de forma direta (sem recurso a aproximações), recorrendo-se a uma metodologia de procura global. Embora conceptualmente estes algoritmos sejam desenvolvidos para problemas genéricos, sem explorar particularidades do problema em questão, o presente trabalho analisa, desenvolve e valida novos métodos, de modo a obter resultados ótimos e/ou subótimos com reduzido erro, mas sobretudo, acelerando consideravelmente a convergência dos mesmos. Inicialmente são estudados métodos de otimização global baseados em enxames de partículas, procurando-se ajustar os seus parâmetros de modo a serem obtidas soluções comparáveis ao estado da arte num largo espectro contextual, nomeadamente, ao nível do ruído das medições, do número de sensores e da posição da fonte no espaço. Os resultados obtidos certificam a utilização da metodologia, quer em termos do erro da solução final, quer em termos do tempo de computação. Estes são ainda validados com uma implementação em ambiente real, com medições de campo, obtendo-se resultados em concordância com as simulações computacionais. A segunda parte da dissertação, propõe novas técnicas para a inicialização da população normalmente considerada aleatória neste tipo de cenários. Para esse fim, dois métodos são desenvolvidos e propostos: (1) usando uma estimativa de distância obtida através das observações ruidosas do modelo, gerando pontos aleatórios em torno das interceções em relação aos sensores; (2) pela geração de Cadeias de Markov a partir do algoritmo de Metropolis-Hastings , tendo como ponto inicial o resultado obtido em (1). Em simultâneo, implementa-se uma procura local baseada no gradiente discreto do modelo. Além disso, através da aplicação de uma nova condição de paragem dos métodos que normalmente consideram um valor pré-definido de gerações de população, é demonstrado que as propostas no âmbito desta dissertação aceleram consideravelmente a convergência dos mesmos. Tal situação implica um cômputo bastante reduzido do número de gerações de população e, consequentemente, do tempo de processamento. Este trabalho introduz várias inovações importantes no campo de estudo: (1) incorporação de informações do modelo em estudo nos métodos de otimização baseados em enxames de partículas; (2) abordagens inovadoras para inicialização de populações para métodos baseados em enxames de partículas; (3) critérios de paragem mais eficientes de modo a interromper o processo iterativo, normalmente considerado com valores pré-determinados; (4) uma estratégia de procura local, sem a necessidade do cálculo analítico do gradiente do modelo. Tais inovações, resultam em novas metodologias com desempenho aprimorado da localização em termos de precisão, complexidade computacional e taxa de convergência. As inovações introduzidas no estado da arte para resolução do problema de localização de uma fonte acústica, abrem caminho para implementações "embedded" , em processadores de baixa complexidade, fator de forma e consumo. Deste modo, surgem novas possibilidades de investigação ao nível da computação de borda ou em nuvem (do inglês Edge ou Fog Computing ), assim como a implementação de métodos de localização distribuídos ou sequenciais, quer pela simplicidade de implementação, quer pela menor exigência do esforço computacional.The present dissertation addresses the problem of locatization of an acoustic source, using metaheuristic algorithms. Typically, the existing methodologies adopted for the considered localization problem are based on a sequence of approximations and/or relaxations of some proposed (non-convex) statistical estimator, whose solutions are possibly used later as the starting point for local search, applying heuristic search methods. Although solutions entailed from such methods are relatively accurate, they come at the expense of high computational cost, and are only sub-optimal. In this thesis, through the use of metaheuristic, namely swarm-based methods, the localization problem is tackled directly (without resorting to any approximations /relaxations), using a global optimization methodology. Although conceptually these algorithms are intended to address generic problems, without exploiting particularities of the problem at hand, the present work shows that they can be adopted for problem-specific applications. More specifically, the present work develops novel frameworks for metaheuristic algorithms which result in enhanced localization performance, both in terms of localization accuracy and algorithm convergence. In the first part of the dissertation, global optimization methods based on particle swarms are studied, aiming to adjust their parameters in order to match the localization accuracy of state-of-the-art solutions, in a wide range of settings of practical interest, namely in terms of power measurement noise, number of sensors and the position of the source in a search space. The simulation results obtained validate the use of the particle swarm methodology, both in terms of localization accuracy and execution time. These results are also validated through a real-world implementation using field measurements, achieving results in line with the computer simulations. The second part of the thesis proposes new techniques for population initialization, which is performed completely randomly in the traditional approach. To this end, two methods are developed: (1) we use distance estimates from noisy model observations to form circles with centers at the known reference locations and radii equal to the respective distance estimates to generate random points in the neighborhood of the intersections of the circles; (2) by generating Markov Chains and employing Metropolis-Hastings algorithm, taking as their starting point the result obtained in (1). Simultaneously, a local search based on a discrete gradient of the model is implemented. Moreover, by adopting a different stopping criterion in comparison with the traditional one (a predefined value a number of function evaluations), it is demonstrated that the proposed approaches in this thesis considerably accelerate the convergence of the method. This result implies a reduced number of population generations and, consequently, a reduced processing time. Therefore, this work introduces several important innovations in the field of study, namely: (1) incorporation of model problem particularity under study into global optimization methods; (2) new novel approaches for population initialization for swarm-based methods; (3) more efficient stopping criteria to interpose the iteration process, usually considered as a predetermined values; (4) a local search methodology without the need of analytic gradient calculations. Such innovations result in new methodologies, with enhanced localization performance in terms of localization accuracy, computational complexity, and convergence rate. The proposed state-of-the-art innovations introduced for solving the localization problem of an acoustic source paves the way for embedded implementations on low complexity processors, with small form factor, and consumption. This way, new research paths arise at the level of Edge or Cloud computing, as well as distributed implementation or sequential localization schemes. This is mainly due to the simplicity of implementation, which comes at a low computational effort