Search

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 Coimbra A 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. more...

Submitted by Boris Flegr (boris@uerj.br) on 2021-01-07T14:40:10Z No. of bitstreams: 1 Tese_AneElidaNogueiraFrauchesAlmoaia.pdf: 1556726 bytes, checksum: 91e25f58a04963a86df1424073178a4f (MD5) Made available in DSpace on 2021-01-07T14:40:10Z (GMT). No. of bitstreams: 1 Tese_AneElidaNogueiraFrauchesAlmoaia.pdf: 1556726 bytes, checksum: 91e25f58a04963a86df1424073178a4f (MD5) Previous issue date: 2018-11-14 When dealing with optimization problems, researches find a major dilemma regarding to the algorithm efficiency for solving a problem. On the other hand, statistics provide tools to compare efficiency in algorithms. The goal of this thesis is to perform five metaheuristcs methods (differential evolution, firefly, firefly with predation, Hooke-Jeeves particle collision, and cross-section particle collision) to solve a set of fourteen benchmark problems then compare its success rates using non-parametric statistics tools, such as Friendman and Wilcoxon. The benckmark problems were divided into two groups. The first one deals with function problems like Branin, Easom, Goldstein-Price, Rosenbrock, Zakharov, Shuberts, Hartmann, and Shekel. Those functions are commonly used for testing optimization problems performance. The second group has nonlinear algebraic equations including parameter estimation problems. Ten-variable chemical equilibrium, chemical equilibrium, pig liver problem, fertilizer experiment parameter estimation, exponential fit 4-parameters are the problems on the second group. After all the executions, the two best methods and two new methods were applied to solve an optimal control problem known as continuous stirred tank reactor in order to find the more effective method. The new methods bring the topographical heuristic combined with the differential evolution algorithm and a new population version of the particle collision algorithm. Ao lidar com problemas que envolvem otimização, os pesquisadores enfrentam um grande dilema no que diz respeito à eficiência e eficácia do algoritmo escolhido para aquela determinada situação. Por outro lado, a estatística fornece ferramentas capazes de comparar algoritmos. Pensando nisso, esta dissertação foi desenvolvida com o objetivo de executar cinco métodos metaheurísticos (evolução diferencial, vagalumes, vagalumes com predação, colisão de partíclas com Hooke-Jeeves e colisão de partículas através de seção de choque) em um conjunto de quatorze problemas encontrados na literatura e compará-los utilizando a estatística não-paramétrica a partir dos testes de Friedman e Wilcoxon. Os problemas foram divididos em duas categorias. A primeira categoria conta com os problemas Branin, Easom, Goldstein-Price, Rosenbrock, Zakharov, Shubert, Hartmann e Shekel por serem funções amplamente utilizadas em teste de desempenho de algoritmos de otimização. A segunda categoria constitui de sistemas algébricos não lineares incluindo problemas de estimação de parâmetros, são eles: equilíbrio químico com dez variáveis, equilíbrio químico, problema do fígado de porco, estimação de parâmetros de um experimento fertilizante e ajuste exponencial com quatro parâmetros. Por fim, os dois melhores métodos foram aplicados ao problema do reator tanque agitado contínuo, sendo este um caso de controle ótimo, em conjunto com os dois novos métodos que serão apresentados neste trabalho com o objetivo de encontrar o algoritmo que seja mais eficaz em diversos tipos de problemas que precisam da otimização para serem solucionados. Os novos métodos trarão a heurística topográfica atuando em conjunto com o algoritmo de evolução diferencial e com uma versão populacional do algoritmo de colisão de partículas. more...

Parameter adjustment of shape descriptors is a challenging task in computer vision and image processing. Rather than manual schemes, which are time consuming and tedious, there is a trend towards applying metaheuristic optimization to fully support parameter settings of shape descriptors. Nevertheless, the problem of cost function selection, which plays an important role in the optimization process, has not yet been fully addressed. This work investigates the influence of the cost function on the performance of an optimized multiscale shape descriptor using three distinct clustering validation indices: the Silhouette, Davies-Bouldin and Calinski- Harabasz indices. Here, we optimize the scale parameters of the normalized multiscale bending energy descriptor using the simulated annealing metaheuristic; both classification and retrieval experiments are conducted using a synthetic shape dataset (Kimia 99), two plant leaf datasets (ShapeCN and Swedish) and the National Library of Medicine (NLM) pill image dataset (NLM Pills). The performance evaluation, in terms of the Bulls-eye and Accuracy measures, showed that optimized descriptor with the Calinski-Harabasz cost function underperformed the other functions in datasets where there is high level of dissimilarity between classes. Particularly for the NLM Pills, where each class has a well-defined pattern and furthermore the differences within pill classes are quite small. Thus, the Normalized Multiscale Bending Energy descriptor did not benefit from the optimization methodology. O ajuste de parâmetros de descritores de formas é uma tarefa desafiadora em visão computacional e processamento de imagens. Ao contrário de esquemas manuais, que são custosos e tediosos, há uma tendência de aplicação de otimização meta-heurística para a configuração dos parâmetros desses descritores. No entanto, a escolha da função custo, a qual desempenha um importante papel no processo de otimização, ainda é um problema em aberto. Este trabalho investiga a influência da função custo no desempenho de um descritor multiescala de formas, o qual foi otimizado usando três índices de validação de agrupamentos: a Silhouette, o índice de Davies- Bouldin e o índice de Calinski-Harabasz. Para a otimização dos parâmetros de escala do descritor denominado energia de dobramento multiescala normalizada, utilizou-se a meta-heurística de recozimento simulado, realizando experimentos de classificação e recuperação com uma base de formas sintéticas (Kimia 99), duas bases de folhas de plantas (ShapeCN e Swedish) e uma base de pílulas da United States National Library of Medicine (base NLM Pills). Na avaliação de desempenho dos experimentos de recuperação e classificação, utilizou-se a medida Bulls-eye e a Acurácia da classificação, respectivamente. Os resultados mostraram que o descritor otimizado com o índice de Calinski-Harabasz no papel de função custo apresentou desempenho inferior aos resultados obtidos com as outras funções nas bases com maior dissimilaridade intraclasse. Particularmente para base NLM Pills, onde cada classe tem um padrão bem característico e portanto não há muitas diferenças entre os elementos de uma mesma classe, o descritor de energia de dobramento multiescala normalizada não se beneficiou da metodologia de otimização. more...