Non-rigid shapes are generally known as objects whose three dimensional geometry may deform by internal and/or external forces. Deformable shapes are all around us, ranging from protein molecules, to natural objects such as the trees in the forest or the fruits in our gardens, and even human bodies. Two deformable shapes may be related by isometry, which means their intrinsic geometries are preserved, even though their extrinsic geometries are dissimilar. An important problem in the analysis of the deformable shapes is to identify the three-dimensional correspondence between two isometric shapes, given that the two shapes may be deviated from isometry by intrinsic distortions. A major challenge is that non-rigid shapes have large degrees of freedom on how to deform. Nevertheless, irrespective of how they are deformed, they may be aligned such that the geodesic distance between two arbitrary points on two shapes are nearly equal. Such alignment may be expressed by a permutation matrix (a matrix with binary entries) that corresponds to every paired geodesic distance in between the two shapes. The alignment involves searching the space over all possible mappings (that is all the permutations) to locate the one that minimizes the amount of deviation from isometry. A brute-force search to locate the correspondence is not computationally feasible. This thesis introduces a novel approach created to locate such correspondences, in spite of the large solution space that encompasses all possible mappings and the presence of intrinsic distortion. In order to find correspondences between two shapes, the first step is to create a suitable descriptor to accurately describe the deformable shapes. To this end, we developed deformation-invariant metric descriptors. A descriptor constitutes pair-wise geodesic distances among arbitrary number of discrete points that represent the topology of the non-rigid shape. Our descriptor provides isometric-invariant representation of the shape irrespective of its circumstantial deformation. Two isometric-invariant descriptors, representing two candidate deformable shapes, are the input parameters to our optimization algorithm. We then proceed to locate the permutation matrix that aligns the two descriptors, that minimizes the deviation from isometry. Once we have developed such a descriptor, we turn our attention to finding correspondences between non deformable shapes. In this study, we investigate the use of both classical and quantum particle swarm optimization (PSO) algorithms for this task. To explore the merits of variants of PSO, integer optimization involving test functions with large dimensions were performed, and the results and the analysis suggest that quantum PSO is more effective optimization method than its classical PSO counterpart. Further, a scheme is proposed to structure the solution space, composed of permutation matrices, in lexicographic ordering. The search in the solution space is accordingly simplified to integer optimization to find the integer rank of the targeted permutation matrix. Empirical results suggest that this scheme improves the scalability of quantum PSO across large solution spaces. Yet, quantum PSO's global search capability requires assistance in order to more effectively manoeuvre through the local extrema prevalent in the large solution spaces. A mutation based genetic algorithm (GA) is employed to augment the search diversity of quantum PSO when/if the swarm stagnates among the local extrema. The mutation based GA instantly disengages the optimization engine from the local extrema in order to reorient the optimization energy to the trajectories that steer to the global extrema, or the targeted permutation matrix. Our resultant optimization algorithm combines quantum Particle Swarm Optimization (PSO) and mutation based Genetic Algorithm (GA). Empirical results show that the optimization method presented is scalable and efficient on standard hardware across different solution space sizes. The performance of the optimization method, in simulations and on various near-isometric shapes, is discussed. In all cases investigated, the method could successfully identify the correspondence among the non-rigid deformable shapes that were related by isometry.

Recently, interest in the Graphics Processing Unit (GPU) for general purpose parallel applications development and research has grown. Much of the current research on the GPU focuses on the acceleration of regular problems, as irregular problems typically do not provide the same level of performance on the hardware. We explore the potential of the GPU by investigating four problems on the GPU with regular and/or irregular properties: lookback option pricing (regular), single-source shortest path (irregular), maximum flow (irregular), and the task matching problem using multi-swarm particle swarm optimization (regular with elements of irregularity). We investigate the design, implementation, optimization, and performance of these algorithms on the GPU, and compare the results. Our results show that the regular problem achieves greater performance and requires less development effort than the irregular problems. However, we find the GPU to still be capable of providing high levels of acceleration for irregular problems.

Die Optimierung spielt in der Industrie und Technik eine entscheidende Rolle. Für einen Betrieb ist es beispielsweise äußerst wichtig, die zur Verfügung stehenden Ressourcen optimal zu nutzen und Betriebsabläufe effizient zu gestalten. Damit diese Vorhaben umgesetzt werden können, setzt man Methoden der Optimierung ein. Die Zielstellungen werden als eine abstrakte mathematische Aufgabe formuliert und anschließend wird versucht, dieses Problem mit einem Optimierungsverfahren zu lösen. Da die Komplexität der Problemstellungen in der Praxis ansteigt, sind exakte Verfahren in der Regel nicht mehr effizient anwendbar, sodass andere Methoden zum Lösen dieser Aufgaben entwickelt werden müssen, die in angemessener Zeit eine akzeptable Lösung finden. Solche Methoden werden als Approximationsalgorithmen bezeichnet. Im Gegensatz zu den exakten Verfahren ist der Verlauf der Optimierung bei dieser Verfahrensklasse vom Zufall abhängig. Dadurch lassen sich in der Regel keine Konvergenzaussagen beweisen. Dennoch hat sich gezeigt, dass Approximationsalgorithmen viel versprechende Ergebnisse für eine Vielzahl von unterschiedlichen Problemstellungen liefern. Zwei Approximationsalgorithmen werden in dieser Arbeit vorgestellt, untersucht und erweitert. Zum einen steht ein Verfahren im Vordergrund, welches aus Beobachtungen in der Natur entstanden ist. Es gibt Lebewesen, die durch verblüffend einfache Strategien in der Lage sind, komplexe Probleme zu lösen. Beispielsweise bilden Fische Schwärme, um sich vor Fressfeinden zu schützen. Der Fischschwarm kann dabei als selbstorganisierendes System verstanden werden, bei dem die Aktivitäten der einzelnen Fische hauptsächlich von den Bewegungen der Nachbarfische abhängig sind. An diesem erfolgreichen Schwarmverhalten ist der moderne Approximationsalgorithmus der Partikelschwarmoptimierung angelehnt. Weiterhin wird ein ersatzmodellgestütztes Verfahren präsentiert. Der Ausgangspunkt dieses Optimierungsverfahrens ist der Aufbau von Ersatzmodellen, um das Verhalten der Zielfunktionen anhand der bisherigen Auswertungen vorhersagen zu können. Damit so wenig wie möglich Funktionsauswertungen vorgenommen werden müssen, wird bei diesem Verfahren ein hoher Aufwand in die Wahl der Punkte investiert, welche auszuwerten sind. Die vorliegende Diplomarbeit gliedert sich wie folgt. Zunächst werden die mathematischen Grundlagen für das Verständnis der weiteren Ausführungen gelegt. Insbesondere werden multikriterielle Optimierungsaufgaben betrachtet und klassische Lösungsansätze aufgezeigt. Das dritte Kapitel beschäftigt sich mit der Partikelschwarmoptimierung. Dieser „naturanaloge Approximationsalgorithmus“ wird ausführlich dargelegt und analysiert. Dabei stehen die Funktionsweise und der Umgang mit mehreren Zielen und Restriktionen im Vordergrund der Ausarbeitung. Ein ersatzmodellgestütztes Optimierungsverfahren wird im Anschluss darauf vorgestellt und erweitert. Neben der Verfahrensanalyse, ist die Behebung der vorhandenen Schwachstellen ein vorrangiges Ziel dieser Untersuchung. Die eingeführten und implementierten Verfahren werden im fünften Kapitel an geeigneten analytischen und technischen Problemen verifiziert und mit anderen Approximationsalgorithmen verglichen. Anschließend werden Empfehlungen für die Verwendung der Verfahren gegeben. Die gewonnenen Kenntnisse werden im letzten Kapitel zusammengefasst und es wird ein Ausblick für zukünftige Forschungsthemen gegeben

abstract: Buildings (approximately half commercial and half residential) consume over 70% of the electricity among all the consumption units in the United States. Buildings are also responsible for approximately 40% of CO2 emissions, which is more than any other industry sectors. As a result, the initiative smart building which aims to not only manage electrical consumption in an efficient way but also reduce the damaging effect of greenhouse gases on the environment has been launched. Another important technology being promoted by government agencies is the smart grid which manages energy usage across a wide range of buildings in an effort to reduce cost and increase reliability and transparency. As a great amount of efforts have been devoted to these two initiatives by either exploring the smart grid designs or developing technologies for smart buildings, the research studying how the smart buildings and smart grid coordinate thus more efficiently use the energy is currently lacking. In this dissertation, a "system-of-system" approach is employed to develop an integrated building model which consists a number of buildings (building cluster) interacting with smart grid. The buildings can function as both energy consumption unit as well as energy generation/storage unit. Memetic Algorithm (MA) and Particle Swarm Optimization (PSO) based decision framework are developed for building operation decisions. In addition, Particle Filter (PF) is explored as a mean for fusing online sensor and meter data so adaptive decision could be made in responding to dynamic environment. The dissertation is divided into three inter-connected research components. First, an integrated building energy model including building consumption, storage, generation sub-systems for the building cluster is developed. Then a bi-level Memetic Algorithm (MA) based decentralized decision framework is developed to identify the Pareto optimal operation strategies for the building cluster. The Pareto solutions not only enable multiple dimensional tradeoff analysis, but also provide valuable insight for determining pricing mechanisms and power grid capacity. Secondly, a multi-objective PSO based decision framework is developed to reduce the computational effort of the MA based decision framework without scarifying accuracy. With the improved performance, the decision time scale could be refined to make it capable for hourly operation decisions. Finally, by integrating the multi-objective PSO based decision framework with PF, an adaptive framework is developed for adaptive operation decisions for smart building cluster. The adaptive framework not only enables me to develop a high fidelity decision model but also enables the building cluster to respond to the dynamics and uncertainties inherent in the system. / Dissertation/Thesis / Ph.D. Industrial Engineering 2012

O presente trabalho avalia a otimização de parâmetros concentrados de suspensão em veículos e considera a importância deste processo para minimizar a aceleração vertical rms transmitida para garantir conforto e segurança ao motorista. Dessa forma, o trabalho objetiva desenvolver uma modelagem capaz de representar o veículo completo para então otimizar os parâmetros de rigidez e amortecimento no domínio da frequência e identificar, em torno do ponto ótimo, quais desses parâmetros mais influenciam nessa minimização. Para atingir esses objetivos, dois modelos veiculares (com dois e oito graus de liberdade respectivamente) são propostos conforme as orientações das normas BS 6841 (1987), ISO 8608 (1995) e ISO 2631 (1997). Os modelos são analisados linearmente e otimizados por um algoritmo heurístico de enxame de partículas. Finalmente, os resultados de rigidez e amortecimento da suspensão são obtidos e reduzem em até 35,3% a aceleração vertical rms transmitida ao motorista. Por meio de uma análise de sensibilidade, as variáveis de projeto que mais contribuem para essa redução são identificadas. / The present work evaluates the optimization of lumped parameters of suspension on vehicles and considers the importance of this process to minimize the rms vertical acceleration transmitted to ensure comfort and safety to the driver. Thus, this work aims to develop a model able to represent the whole vehicle and, then, optimize the parameters of stiffness and damping in the frequency domain and identify, around the optimal point, those parameters which most influence in this minimization. To achieve these goals, two vehicle models (with two and eight degrees of freedom respectively) are proposed according to the guidelines of the standards BS 6841 (1987), ISO 8608 (1995) and ISO 2631 (1997). The models are linearly analyzed and optimized by a heuristic algorithm of particle swarm. Finally, the results of stiffness and damping of suspension are obtained and reduces up to 35,3% of rms vertical acceleration transmitted to the driver. Through a sensitivity analysis, the design variables that most contribute to this reduction are identified.

AN ABSTRACT OF THE THESIS OF Mohamed A. Abuella, for the Master of Science degree in Electrical and Computer Engineering, presented on May 10, 2012, at Southern Illinois University Carbondale. TITLE:STUDY OF PARTICLE SWARM FOR OPTIMAL POWER FLOW IN IEEE BENCHMARK SYSTEMS INCLUDING WIND POWER GENERATORS MAJOR PROFESSOR: Dr. C. Hatziadoniu, The aim of this thesis is the optimal economic dispatch of real power in systems that include wind power. The economic dispatch of wind power units is quite different of conventional thermal units. In addition, the consideration should take the intermittency nature of wind speed and operating constraints as well. Therefore, this thesis uses a model that considers the aforementioned considerations in addition to whether the utility owns wind turbines or not. The optimal power flow (OPF) is solved by using one of the modern optimization algorithms: the particle swarm optimization algorithm (PSO). IEEE 30-bus test system has been adapted to study the implementation PSO algorithm in OPF of conventional-thermal generators. A small and simple 6-bus system has been used to study OPF of a system that includes wind-powered generators besides to thermal generators. The analysis of investigations on power systems is presented in tabulated and illustrative methods to lead to clear conclusions.

Population-based global optimization algorithms including Particle Swarm Optimization (PSO) have become popular for solving multi-optima problems much more efficiently than the traditional mathematical techniques. In this research, we present and evaluate a new parallel PSO algorithm that provides a significant performance improvement as compared to the serial PSO algorithm. Instead of merely assigning parts of the task of serial version to several processors, the new algorithm places multiple swarms on the available nodes in which operate independently, while collaborating on the same task. With the reduction of the communication bottleneck as well the ability to manipulate the individual swarms independently, the proposed approach outperforms the original PSO algorithm and still maintains the simplicity and ease of implementation.

Submitted by Maykon Nascimento (maykon.albani@hotmail.com) on 2015-08-03T18:48:30Z No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Um algoritmo PSO híbrido para planejamento de caminhos em navegação de veículos utilizando A.pdf: 2604695 bytes, checksum: ed8f69e49eaefe272bccd6025290c381 (MD5) / Approved for entry into archive by Elizabete Silva (elizabete.silva@ufes.br) on 2015-08-13T21:44:43Z (GMT) No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Um algoritmo PSO híbrido para planejamento de caminhos em navegação de veículos utilizando A.pdf: 2604695 bytes, checksum: ed8f69e49eaefe272bccd6025290c381 (MD5) / Made available in DSpace on 2015-08-13T21:44:43Z (GMT). No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Um algoritmo PSO híbrido para planejamento de caminhos em navegação de veículos utilizando A.pdf: 2604695 bytes, checksum: ed8f69e49eaefe272bccd6025290c381 (MD5) Previous issue date: 2015 / Utilizar robôs autônomos capazes de planejar o seu caminho é um desafio que atrai vários pesquisadores na área de navegação de robôs. Neste contexto, este trabalho tem como objetivo implementar um algoritmo PSO híbrido para o planejamento de caminhos em ambientes estáticos para veículos holonômicos e não holonômicos. O algoritmo proposto possui duas fases: a primeira utiliza o algoritmo A* para encontrar uma trajetória inicial viável que o algoritmo PSO otimiza na segunda fase. Por fim, uma fase de pós planejamento pode ser aplicada no caminho a fim de adaptá-lo às restrições cinemáticas do veículo não holonômico. O modelo Ackerman foi considerado para os experimentos. O ambiente de simulação de robótica CARMEN (Carnegie Mellon Robot Navigation Toolkit) foi utilizado para realização de todos os experimentos computacionais considerando cinco instâncias de mapas geradas artificialmente com obstáculos. O desempenho do algoritmo desenvolvido, A*PSO, foi comparado com os algoritmos A*, PSO convencional e A* Estado Híbrido. A análise dos resultados indicou que o algoritmo A*PSO híbrido desenvolvido superou em qualidade de solução o PSO convencional. Apesar de ter encontrado melhores soluções em 40% das instâncias quando comparado com o A*, o A*PSO apresentou trajetórias com menos pontos de guinada. Investigando os resultados obtidos para o modelo não holonômico, o A*PSO obteve caminhos maiores entretanto mais suaves e seguros. / Autonomous robots with the ability of planning their own way is a challenge that attracts many researchers in the area of robot navigation. In this context, this work aims to implement a hybrid PSO algorithm for planning paths in static environments for holonomic and non-holonomic vehicles. The proposed algorithm has two phases: the first uses A* algorithm to generates an initial and feasible trajectory which is optimized by the PSO algorithm in the second stage. Finally a post path planning phase can be applied in order to adapt it to non-holonomic vehicle kinematic constraints. The Ackerman model has been considered for the experiments. The Carnegie Mellon Robot Navigation Toolkit (CARMEN) was used to perform the computational experiments considering five instances of maps artificially generated with obstacles. The performance of the A*PSO algorithm was compared with A*, PSO and A*-Hybrid State. The results of the dynamic instances were not compared with other algorithms. The computational results indicates that the algorithm A*PSO outperformes the PSO algorithm. With respect to the algorithm A*, the A*PSO achieved better solutions for 40% of the tested instances, but all of them, with less waypoints. For non-holonomic instances, the A*PSO obtained longer paths, however smoother and safer.

O presente trabalho avalia a otimização de parâmetros concentrados de suspensão em veículos e considera a importância deste processo para minimizar a aceleração vertical rms transmitida para garantir conforto e segurança ao motorista. Dessa forma, o trabalho objetiva desenvolver uma modelagem capaz de representar o veículo completo para então otimizar os parâmetros de rigidez e amortecimento no domínio da frequência e identificar, em torno do ponto ótimo, quais desses parâmetros mais influenciam nessa minimização. Para atingir esses objetivos, dois modelos veiculares (com dois e oito graus de liberdade respectivamente) são propostos conforme as orientações das normas BS 6841 (1987), ISO 8608 (1995) e ISO 2631 (1997). Os modelos são analisados linearmente e otimizados por um algoritmo heurístico de enxame de partículas. Finalmente, os resultados de rigidez e amortecimento da suspensão são obtidos e reduzem em até 35,3% a aceleração vertical rms transmitida ao motorista. Por meio de uma análise de sensibilidade, as variáveis de projeto que mais contribuem para essa redução são identificadas. / The present work evaluates the optimization of lumped parameters of suspension on vehicles and considers the importance of this process to minimize the rms vertical acceleration transmitted to ensure comfort and safety to the driver. Thus, this work aims to develop a model able to represent the whole vehicle and, then, optimize the parameters of stiffness and damping in the frequency domain and identify, around the optimal point, those parameters which most influence in this minimization. To achieve these goals, two vehicle models (with two and eight degrees of freedom respectively) are proposed according to the guidelines of the standards BS 6841 (1987), ISO 8608 (1995) and ISO 2631 (1997). The models are linearly analyzed and optimized by a heuristic algorithm of particle swarm. Finally, the results of stiffness and damping of suspension are obtained and reduces up to 35,3% of rms vertical acceleration transmitted to the driver. Through a sensitivity analysis, the design variables that most contribute to this reduction are identified.

Dissertação (mestrado)—Universidade de Brasília, Faculdade de Tecnologia, Departamento de Engenharia Elétrica, 2014. / Submitted by Ana Cristina Barbosa da Silva (annabds@hotmail.com) on 2014-11-25T17:23:31Z No. of bitstreams: 1 2014_RafaelCortesdePaiva.pdf: 7660330 bytes, checksum: eaad53db8e1c76edec638a3e30ee5f3e (MD5) / Approved for entry into archive by Raquel Viana(raquelviana@bce.unb.br) on 2014-11-25T17:58:53Z (GMT) No. of bitstreams: 1 2014_RafaelCortesdePaiva.pdf: 7660330 bytes, checksum: eaad53db8e1c76edec638a3e30ee5f3e (MD5) / Made available in DSpace on 2014-11-25T17:58:54Z (GMT). No. of bitstreams: 1 2014_RafaelCortesdePaiva.pdf: 7660330 bytes, checksum: eaad53db8e1c76edec638a3e30ee5f3e (MD5) / Nesse trabalho foi realizado o estudo de técnicas bio-inspiradas para gerar a marcha de um robô bípede. Foi utilizado o conceito de CPG, Central Pattern Generator (CPG), que é uma rede neural capaz de produzir respostas rítmicas. Elas foram modeladas como osciladores acoplados chamados de osciladores neurais. Para tanto foram utilizados alguns modelos de osciladores, o modelo de Matsuoka, o modelo de Kuramoto e o modelo de Kuramoto com acoplamento entre a dinâmica do oscilador e a dinâmica da marcha. Foram usados dois modelos de robôs, o Bioloid e o NAO. Para otimizar os parâmetros dos osciladores foram utilizados o Algoritmo Genético (AG), o Particle Swarm Optimization (PSO) e o Nondominated sorting Genetic Algorithm II (NSGA-II). Foi utilizada uma função de custo que através de determinadas condições tem como objetivo obter uma marcha eficiente. No NSGA-II, além dessa função de custo, foi utilizada outra função de custo que considera o trabalho realizado pelo robô. Além disso, também foi utilizada a aprendizagem por reforço para treinar um controlador que corrige a postura do robô durante a marcha. Foi possível propor um framework para obter os parâmetros dos osciladores e através dele obter uma marcha estável em ambas as plataformas. Também foi possível propor um framework utilizando aprendizagem por reforço para treinar um controlador para corrigir a postura do robô com a marcha sendo gerado pelo oscilador de Kuramoto com acoplamento. O objetivo do algoritmo foi minimizar a velocidade do ângulo de arfagem do corpo do robô, dessa forma, a variação do ângulo de arfagem também foi minimizada consequentemente. Além disso, o robô andou mais “cautelosamente” para poder manter a postura e dessa forma percorreu uma distância menor do que se estivesse sem o controlador. ______________________________________________________________________________ ABSTRACT / This document describes computational optimized bipedal robot gait generators. Thegaits are applied by a neural oscillator, composed of coupled central pattern generators(CPG), which are neural networks capable of producing rhythmic output. The models ofthe oscillators used were the Matsuoka model, Kuramoto model and Kura moto model withcoupling between the dynamics of the oscillator and dynamics of the gait. Two bipedalrobots, a NAO and a Bioloid, were used. The neural oscillators were optimized with threealgorithms, a Genetic Algorithm (GA), Particle Swarm Optimization (PSO) and Nondominatedsorting Genetic Algorithm II (NSGA-II). It was used a fitness function that has theobjective to obtain an efficient gait through some conditions. In NSGA-II, besides this fitnessfunction, another one was used that has the objective to minimize the work done by therobot. Additionally, reinforcement learning techniques were used to train a controller thatcorrects the robots gait posture. It was proposed a framework to obtain the parameters of theoscillators used and obtain efficient gaits in both robots. Also, it was proposed a frameworkusing reinforcement learning to train a controller to correct the robots gait posture. The objective of the algorithm was to minimize the pitch angular velocity, consequently the pitchangle standard deviation was minimized. Additionally, the robot moved with more “caution” and walked less compared with the walk without the posture controller.