Scheduling of aperiodic and independent tasks in hard real-time symmetric multiprocessing systems is an NP-complete problem that is often solved using heuristics like particle swarm optimization (PSO). The performance of these class of heuristics, known as evolutionary algorithms, are often evaluated based on the number of iterations it takes to find a solution. Such metrics provide limited information on how the algorithm reaches a solution and how the process could be accelerated. This thesis presents a methodology to analyze the trajectory formed by candidate solutions in order to analyze them in both the time and frequency domains at a single scale. The analysis entails (i) the impact of different parameters for the PSO algorithm, and (ii) the evolutionary processes in the swarm. The work reveals that particles have a directed movement towards a solution during a transient phase, and then enter a steady state where they perform an unguided local search. The scheduling algorithm presented in this thesis uses a variation of the minimum total tardiness with cumulative penalties cost function, that can be extended to suit different system needs. The experimental results show that the scheduler is able to distribute tasks to meet the real-time deadlines over 1, 2, and 4 processors and up to 30 tasks with overall system loads of up to 50\% in fewer than 1,000 iterations. When scheduling greater loads, the scheduler reaches local solutions with 1 to 2 missed deadlines, while larger tasks sets take longer to converge. The trajectories of the particles during the scheduling algorithm are examined as a means to emphasize the impact of the behaviour on the application performance and give insight into ways to improve the algorithm for both space and terrestrial applications.

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.

Filtering is a key step in digital image processing and analysis. It is mainly used for amplification or attenuation of some frequencies depending on the nature of the application. Filtering can either be performed in the spatial domain or in a transformed domain. The selection of the filtering method, filtering domain, and the filter parameters are often driven by the properties of the underlying image. This thesis presents three different kinds of biomedical image filtering applications, where the filter parameters are automatically determined from the underlying images. Filtering can be used for image enhancement. We present a robust image dependent filtering method for intensity inhomogeneity correction of biomedical images. In the presented filtering method, the filter parameters are automatically determined from the grey-weighted distance transform of the magnitude spectrum. An evaluation shows that the filter provides an accurate estimate of intensity inhomogeneity. Filtering can also be used for analysis. The thesis presents a filtering method for heart localization and robust signal detection from video recordings of rat embryos. It presents a strategy to decouple motion artifacts produced by the non-rigid embryonic boundary from the heart. The method also filters out noise and the trend term with the help of empirical mode decomposition. Again, all the filter parameters are determined automatically based on the underlying signal. Transforming the geometry of one image to fit that of another one, so called image registration, can be seen as a filtering operation of the image geometry. To assess the progression of eye disorder, registration between temporal images is often required to determine the movement and development of the blood vessels in the eye. We present a robust method for retinal image registration. The method is based on particle swarm optimization, where the swarm searches for optimal registration parameters based on the direction of its cognitive and social components. An evaluation of the proposed method shows that the method is less susceptible to becoming trapped in local minima than previous methods. With these thesis contributions, we have augmented the filter toolbox for image analysis with methods that adjust to the data at hand.

Scheduling of aperiodic and independent tasks in hard real-time symmetric multiprocessing systems is an NP-complete problem that is often solved using heuristics like particle swarm optimization (PSO). The performance of these class of heuristics, known as evolutionary algorithms, are often evaluated based on the number of iterations it takes to find a solution. Such metrics provide limited information on how the algorithm reaches a solution and how the process could be accelerated. This thesis presents a methodology to analyze the trajectory formed by candidate solutions in order to analyze them in both the time and frequency domains at a single scale. The analysis entails (i) the impact of different parameters for the PSO algorithm, and (ii) the evolutionary processes in the swarm. The work reveals that particles have a directed movement towards a solution during a transient phase, and then enter a steady state where they perform an unguided local search. The scheduling algorithm presented in this thesis uses a variation of the minimum total tardiness with cumulative penalties cost function, that can be extended to suit different system needs. The experimental results show that the scheduler is able to distribute tasks to meet the real-time deadlines over 1, 2, and 4 processors and up to 30 tasks with overall system loads of up to 50\% in fewer than 1,000 iterations. When scheduling greater loads, the scheduler reaches local solutions with 1 to 2 missed deadlines, while larger tasks sets take longer to converge. The trajectories of the particles during the scheduling algorithm are examined as a means to emphasize the impact of the behaviour on the application performance and give insight into ways to improve the algorithm for both space and terrestrial applications.

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.