Nous nous intéressons dans cette thèse à la résolution du problème de tournées sélectives (Team Orienteering Problem - TOP) et ses variantes. Ce problème est une extension du problème de tournées de véhicules en imposan tcertaines limitations de ressources. Nous proposons un algorithme de résolution exacte basé sur la programmation linéaire en nombres entiers (PLNE) en ajoutant plusieurs inégalités valides capables d’accélérer la résolution. D’autre part, en considérant des périodes de travail strictes pour chaque véhicule durant sa tournée, nous traitons une des variantes du TOP qui est le problème de tournées sélectives multipériodique (multiperiod TOP - mTOP) pour lequel nous développons une métaheuristique basée sur l’optimisation par essaim pour le résoudre. Un découpage optimal est proposé pour extraire la solution optimale de chaque particule en considérant les tournées saturées et pseudo saturées .Finalement, afin de prendre en considération la disponibilité des clients, une fenêtre de temps est associée à chacun d’entre eux, durant laquelle ils doivent être servis. La variante qui en résulte est le problème de tournées sélectives avec fenêtres de temps (TOP with Time Windows - TOPTW). Deux algorithmes exacts sont proposés pour résoudre ce problème. Le premier est basé sur la génération de colonnes et le deuxième sur la PLNE à laquelle nous ajoutons plusieurs coupes spécifiques à ce problème. / We focus in this thesis on developing new algorithms to solve the Team Orienteering Problem (TOP) and two of its variants. This problem derives from the well-known vehicle routing problem by imposing some resource limitations .We propose an exact method based on Mixed Integer Linear Programming (MILP) to solve this problem by adding valid inequalities to speed up its solution process. Then, by considering strict working periods for each vehicle during its route, we treat one of the variants of TOP, which is the multi-period TOP (mTOP) for which we develop a metaheuristic based on the particle swarm optimization approach to solve it. An optimal split procedure is proposed to extract the optimal solution from each particle by considering saturated and pseudo-saturated routes. Finally, in order to take into consideration the availability of customers, a time window is associated with each of them, during which they must be served. The resulting variant is the TOP with Time Windows (TOPTW). Two exact algorithms are proposed to solve this problem. The first algorithm is based on column generation approach and the second one on the MILP to which we add additional cuts specific for this problem. The comparison between our exact and heuristic methods with the existing one in the literature shows the effectiveness of our approaches.

Recently, continuous-valued optimization problems have received a great amount of focus, resulting in optimization algorithms which are very efficient within the continuous-valued space. Many optimization problems are, however, defined within the binary-valued problem space. These continuous-valued optimization algorithms can not operate directly on a binary-valued problem representation, without algorithm adaptations because the mathematics used within these algorithms generally fails within a binary problem space. Unfortunately, such adaptations may alter the behavior of the algorithm, potentially degrading the performance of the original continuous-valued optimization algorithm. Additionally, binary representations present complications with respect to increasing problem dimensionality, interdependencies between dimensions, and a loss of precision. This research investigates the possibility of applying continuous-valued optimization algorithms to solve binary-valued problems, without requiring algorithm adaptation. This is achieved through the application of a mapping technique, known as angle modulation. Angle modulation effectively addresses most of the problems associated with the use of a binary representation by abstracting a binary problem into a four-dimensional continuous-valued space, from which a binary solution is then obtained. The abstraction is obtained as a bit-generating function produced by a continuous-valued algorithm. A binary solution is then obtained by sampling the bit-generating function. This thesis proposes a number of population-based angle-modulated continuous-valued algorithms to solve binary-valued problems. These algorithms are then compared to binary algorithm counterparts, using a suite of benchmark functions. Empirical analysis will show that the angle-modulated continuous-valued algorithms are viable alternatives to binary optimization algorithms. Copyright 2012, University of Pretoria. All rights reserved. The copyright in this work vests in the University of Pretoria. No part of this work may be reproduced or transmitted in any form or by any means, without the prior written permission of the University of Pretoria. Please cite as follows: Pamparà, G 2012, Angle modulated population based algorithms to solve binary problems, MSc dissertation, University of Pretoria, Pretoria, viewed yymmdd < http://upetd.up.ac.za/thesis/available/etd-02242012-090312 / > C12/4/188/gm / Dissertation (MSc)--University of Pretoria, 2012. / Computer Science / unrestricted

Pattern recognition has as its objective to classify objects into different categories and classes. It is a fundamental component of artificial intelligence and computer vision. This thesis investigates the application of an efficient optimization method, known as Particle Swarm Optimization (PSO), to the field of pattern recognition and image processing. First a clustering method that is based on PSO is proposed. The application of the proposed clustering algorithm to the problem of unsupervised classification and segmentation of images is investigated. A new automatic image generation tool tailored specifically for the verification and comparison of various unsupervised image classification algorithms is then developed. A dynamic clustering algorithm which automatically determines the "optimum" number of clusters and simultaneously clusters the data set with minimal user interference is then developed. Finally, PSO-based approaches are proposed to tackle the color image quantization and spectral unmixing problems. In all the proposed approaches, the influence of PSO parameters on the performance of the proposed algorithms is evaluated. / Thesis (PhD)--University of Pretoria, 2006. / Computer Science / unrestricted

This thesis contains three main sections. In the first section, we examine methodologies to discriminate Type II protein kinase inhibitors from the Type I inhibitors. We have studied the structure of 55 Type II kinase inhibitors and have notice specific descriptive geometric features. Using this information we have developed a pharmacophore and a shape based screening approach. We have found that these methods did not effectively discriminate between the two inhibitor types used independently, but when combined in a consecutive way – pharmacophore search first, then shape based screening, we have found a method that successfully filtered out all Type I molecules. The effect of protonation states and using different conformer generators were studied as well. This method was then tested on a freely available database of decoy molecules and again shown to be discriminative. In the second section of the thesis, we implement and assess swarm-based docking methods. We implement a repulsive particle swarm optimization (RPSO) based conformational search approach into Autodock 3.05. The performance of this approach with different parameters was then tested on a set of 51 protein ligand complexes. The effect of using different factoring for the cognitive, social and repulsive terms and the importance of the inertia weight were explored. We found that the RPSO method gives similar performance to the particle swarm optimization method. Compared to the genetic algorithm approach used in Autodock 3.05, our RPSO method gives better results in terms of finding lower energy conformations. In the final, third section we have implemented a Monte Carlo (MC) based conformer searching approach into Gaussian03. This enables high level quantum mechanics/molecular mechanics (QM/MM) potentials to be used in docking molecules in a protein active site. This program was tested on two Zn2+ ion-containing complexes, carbonic anhydrase II and cytidine deaminase. The effects of different QM region definitions were explored in both systems. A consecutive and a parallel docking approach were used to study the volume of the active site explored by the MC search algorithm. In case of the carbonic anhydrase II complex, we have used 1,2-difluorobenzene as a ligand to explore the favourable interactions within the binding site. With the cytidine deaminase complex, we have evaluated the ability of the approach to discriminate the native pose from other higher energy conformations during the exploration of the active site of the protein. We find from our initial calculations, that our program is able to perform a conformational search in both cases, and the effect of QM region definition is noticeable, especially in the description of the hydrophobic interactions within the carbonic anhydrase II system. Our approach is also able to find poses of the cytidine deaminase ligand within 1 Å of the native pose.

A swarm intelligence system is a type of multiagent system with the following distinctive characteristics: (i) it is composed of a large number of agents, (ii) the agents that comprise the system are simple with respect to the complexity of the task the system is required to perform, (iii) its control relies on principles of decentralization and self-organization, and (iv) its constituent agents interact locally with one another and with their environment. <p><p>Interactions among agents, either direct or indirect through the environment in which they act, are fundamental for swarm intelligence to exist; however, there is a class of interactions, referred to as "interference", that actually blocks or hinders the agents' goal-seeking behavior. For example, competition for space may reduce the mobility of robots in a swarm robotics system, or misleading information may spread through the system in a particle swarm optimization algorithm. One of the most visible effects of interference in a swarm intelligence system is the reduction of its efficiency. In other words, interference increases the time required by the system to reach a desired state. Thus, interference is a fundamental problem which negatively affects the viability of the swarm intelligence approach for solving important, practical problems.<p><p>We propose a framework called "incremental social learning" (ISL) as a solution to the aforementioned problem. It consists of two elements: (i) a growing population of agents, and (ii) a social learning mechanism. Initially, a system under the control of ISL consists of a small population of agents. These agents interact with one another and with their environment for some time before new agents are added to the system according to a predefined schedule. When a new agent is about to be added, it learns socially from a subset of the agents that have been part of the system for some time, and that, as a consequence, may have gathered useful information. The implementation of the social learning mechanism is application-dependent, but the goal is to transfer knowledge from a set of experienced agents that are already in the environment to the newly added agent. The process continues until one of the following criteria is met: (i) the maximum number of agents is reached, (ii) the assigned task is finished, or (iii) the system performs as desired. Starting with a small number of agents reduces interference because it reduces the number of interactions within the system, and thus, fast progress toward the desired state may be achieved. By learning socially, newly added agents acquire knowledge about their environment without incurring the costs of acquiring that knowledge individually. As a result, ISL can make a swarm intelligence system reach a desired state more rapidly. <p><p>We have successfully applied ISL to two very different swarm intelligence systems. We applied ISL to particle swarm optimization algorithms. The results of this study demonstrate that ISL substantially improves the performance of these kinds of algorithms. In fact, two of the resulting algorithms are competitive with state-of-the-art algorithms in the field. The second system to which we applied ISL exploits a collective decision-making mechanism based on an opinion formation model. This mechanism is also one of the original contributions presented in this dissertation. A swarm robotics system under the control of the proposed mechanism allows robots to choose from a set of two actions the action that is fastest to execute. In this case, when only a small proportion of the swarm is able to concurrently execute the alternative actions, ISL substantially improves the system's performance. / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

Pour faire face à la concurrence, les entreprises cherchent à améliorer leurs performances industrielles. L’une des solutions à ce défi réside dans la détermination de la meilleure configuration des ateliers de production. Ce type de problème est connu en anglais par Facility Layout Problem « FLP». Dans ce contexte, notre travail propose une méthodologie pour la définition de la configuration d’atelier à travers une approche réaliste. Plus précisément, notre objectif est de prendre en compte les distances réelles parcourues par les pièces dans l’atelier et des contraintes liées au système qui n’ont pas encore été intégrées aux modèles proposés dans la littérature. Pour ce faire, notre première contribution scientifique consiste à développer une nouvelle méthodologie qui utilise l’algorithme A* pour identifier les distances les plus courtes entre les postes de travail de manière réaliste. La méthodologie proposée combine l’Algorithme Génétique (AG) et l’algorithme A* afin d’explorer des espaces de solutions. Pour se rapprocher de plus en plus des cas réels, notre deuxième contribution consiste à présenter une nouvelle formulation généralisée du FLP initialement étudié, en tenant compte de différentes formes et de dimensions des équipements ainsi que de l’atelier. Les résultats obtenus prouvent l’applicabilité et la faisabilité de cette approche dans diverses situations. Une étude comparative de l’approche proposée avec les essaims particulaires intégrés avec A* a prouvé la qualité de la première approche en terme de coût de transport. Finalement, notre troisième contribution consiste à traiter le FLP dans un espace 3D où des contraintes spatiales sont intégrées dans la phase de modélisation. La résolution est une extension de la méthodologie proposée pour le problème 2D, qui intègre donc l'algorithme A* et l’AG afin de générer diverses configurations dans l’espace 3D. Pour chacune de ces contributions, une analyse de sensibilité des différents paramètres d’AG utilisés a été faite à l’aide de simulations de Monte Carlo. / To face the competition, companies seek to improve their industrial performance. One of the solutions to this challenge lies in determining the best configuration of the production workshops. This type of problem is known in English by Facility Layout Problem "FLP". In this context, our work proposes a methodology for the definition of the workshop configuration through a realistic approach. More precisely, our goal is to take into account the actual distances traveled by the parts in the workshop and system-related constraints that have not yet been incorporated into the models proposed in the literature. To do this, our first scientific contribution is to develop a new methodology that uses the A* algorithm to identify the shortest distances between workstations in a realistic way. The proposed methodology combines the Genetic Algorithm (GA) and the algorithm A* to explore solution spaces. To get closer to real cases, our second contribution is to present a new generalized formulation of FLP initially studied, taking into account different shapes and dimensions of the equipment and the workshop. The results obtained prove the applicability and the feasibility of this approach in various situations. A comparative study of the proposed approach with particle swarms integrated with A * proved the quality of the first approach in terms of transport cost. Finally, our third contribution is to treat the FLP in a 3D space where spatial constraints are integrated into the modeling phase. The resolution is an extension of the proposed methodology for the 2D problem, which therefore integrates the A * algorithm and the AG to generate various configurations in the 3D space. For each of these contributions, a sensitivity analysis of the different AG parameters used was made using Monte Carlo simulations.

{This thesis deals with optimization by means of metaheuristics, which are used for complicated engineering problems that cannot be solved by classical methods of mathematical programming. At the beginning, choosed metaheuristics are described: simulated annealing, particle swarm optimization and genetic algorithm; and then they are compared with use of test functions. These algorithms are implemented in Python programming language with use of package called DEAP, which is also described in this thesis. Algorithms are then applied for optimization of design parameters of the heat storage unit.

This Master's thesis describes the design and implementation of an experimental sample for automatic calibration of a robotic tool using machine vision methods under the auspices of the company SANEZOO EUROPE s.r.o. It deals with the analysis of all used methods of performing TCP calibration, on the basis of which it is implemented. The application is based on the Point-counterpoint method, where the robot is guided against the calibration point from three different directions, all perpendicular to each other. The calibration point is set using the ArUco marker. In order to detect the endpoint are used images from two cameras that are at the right angles to each other. Using conventional computer vision methods and an HSV filter, the endpoint of the instrument is found in the images and is guided to the calibration point. From the obtained coordinates, the searched endpoint of the robotic tool in the robot coordinates is found using the optimization method Particle Swarm Optimization. This application, therefore, performs TCP calibration in a fast time, thus reducing production downtime almost without human intervention.

Methods used for correction and modeling of frequency response of sound devices are discussed in this paper. Besides classic methods of digital filter design, more advanced and complex numerial methods are reviewed, Prony and Steiglitz-McBride in particular. This paper focuses on structure utilizing parallel sections of second-order IIR filters. Methods for calculating coefficients of this structure are presented and later implemented. For selected method, utilizing dual frequency warping, an interative algorithm for automatic calculation of parameters necessary to filter design is implemented - so called Particle Swarm Optimization. Six ways of evaluation filter design precision are presented and the results are compared. Functions realizing filter design are implemented in C++, MATLAB and Python. A VST module simulating the filter in real time is also provided.

Metoda koneÄnch prvk implementovan v programu COMSOL Multiphysics je vyu­vna k analze tzv. free-standing kmitoÄtovÄ selektivn­ch povrch ve 3D. Tyto modely jsou nslednÄ doplnÄny o periodick© okrajov© podm­nky. Dle jsou free-standing povrchy doplnÄny o vrstvy dielektrika a je zkoumn jejich vliv na modul Äinitele odrazu. V analytick© Ästi jsou vyhodnoceny vlivy poÄtu element diskretizaÄn­ m­ky na pesnost vsledku a d©lku vpoÄt. Vsledky jsou srovnvny vzhledem k vsledkm uvedenm v literatue [5]. V zvÄreÄn© Ästi prce je vysvÄtlen postup pi generovn­ m-file pro obd©ln­kov element a pouit­ globln­ho optimalizaÄn­ho algoritmu PSO, kter automaticky upravuje rozmÄry vodiv©ho motivu tak, aby bylo dosaeno prbÄhu modulu Äinitele odrazu podle poadovan©ho prbÄhu.