This thesis presents a novel algorithm called ant colony optimization with dual pheromone tables (ACODPT) for improving the quality of ant colony optimization (ACO). The proposed algorithm works by adding a so-called ¡§negative¡¨ pheromone table to ACO to avoid the problem of ACO easily falling into local optima. By using the ¡§negative¡¨ pheromone table to eliminate the most impossible path to search for the new solution, the probability of selecting the remaining paths is increased, and so is the quality. To evaluate the performance of the proposed algorithm, ACODPT is compared with several state-of-the-art algorithms in solving the clustering problem. The experimental results show that the proposed algorithm can eventually prevent ACO from falling into local optima in the early iterations, thus providing a better result than the other algorithms in many cases.

Functional expression of a protein in life form is decided by its tertiary structure. In the past few decades, a significant number of studies have been made on this subject. However, the folding rules of a protein still stay unsolved. The challenge is to predict the three-dimensional tertiary structure of a protein from its primary amino acid sequence. We propose a hybrid method combining homology model and the folding approach to predict protein three-dimensional structure from amino acid sequence. The previous researches on folding problem mostly take the HP (Hydrophobic-Polar) model, which is not able to simulate the native structure of proteins. We use a more exquisite model, the sliced lattice model, to approximate the native forms. Another essential factor influencing protein structures is disulfide bonds, which are ignored in the HP model. We use the ant colony optimization algorithm to approximate the folding problem with the constrained disulfide bond on the sliced lattice HP model. We show that the prediction results are better than previous methods by the measurement of RMSD(Root Mean Square Deviation).

As estratégias de mapeamento utilizando múltiplos robôs móveis possuem uma série de vantagens quando comparadas àquelas estratégias baseadas em um único robô. As principais vantagens que podem ser elucidadas são: flexibilidade, ganho de informação e redução do tempo de construção do mapa do ambiente. No presente trabalho, um método de integração de mapas locais é proposto baseado em observações inter-robôs, considerando uma nova abordagem para a exploração do ambiente. Tal abordagem é conhecida como Sistema de Vigilância baseado na Modificação do Sistema Colônias de Formigas, ou IAS-SS. A estratégia IAS-SS é inspirada em mecanismos biológicos que definem a organização social de sistemas de enxames. Especificamente, esta estratégia é baseada em uma modificação do tradicional algoritmo de otimização por colônias de formiga. A principal contribuição do presente trabalho é a adaptação de um modelo de compartilhamento de informações utilizado em redes de sensores móveis, adaptando o mesmo para tarefas de mapeamento. Outra importante contribuição é a colaboração entre o método proposto de integração de mapas e a estratégia de coordenação de múltiplos robôs baseada na teoria de colônias de formigas. Tal colaboração permite o desenvolvimento de uma abordagem de exploração que emprega um mecanismo não físico para depósito e detecção de feromônios em ambientes reais por meio da elaboração do conceito de feromônios virtuais integrados. Resultados obtidos em simulação demonstram que o método de integração de mapas é eficiente, de modo que os ensaios experimentais foram realizados considerando-se um número variável de robôs móveis durante o processo de exploração de ambientes internos com diferentes formas e estruturas. Os resultados obtidos com os diversos experimentos realizados confirmam que o processo de integração é efetivo e adequado para executar o mapeamento do ambiente durante tarefas de exploração e vigilância do mesmo / The multiple robot map building strategies have several advantages when compared to strategies based on a single robot, in terms of flexibility, gain of information and reduction of map building time. In this work, a local map integration method is proposed based on the inter-robot observations, considering a recent approach for the environment exploration. This approach is based on the Inverse Ant System-Based Surveillance System strategy, called IASSS. The IAS-SS strategy is inspired on biological mechanisms that define the social organization of swarm systems. Specifically, it is based on a modified version of the known ant colony algorithm. The main contribution of this work is the fit of an information sharing model used in an mobile sensor network, adapting the method for mapping tasks. Another important contribution is the collaboration between the local map integration method and the multiple robot coordination strategy based on ant colony theory. Through this collaboration it is possible to develop an approach that uses a mechanism for controlling the access to pheromones in real environments. Such mechanism is based on the integrated virtual pheromones concept. Simulation results show that the map integration method is efficient, the trials are performed considering a variable number of robots and environments with different structures. Results obtained from several experiments confirm that the integration process is effective and suitable to execute mapping during the exploration task

As estratégias de mapeamento utilizando múltiplos robôs móveis possuem uma série de vantagens quando comparadas àquelas estratégias baseadas em um único robô. As principais vantagens que podem ser elucidadas são: flexibilidade, ganho de informação e redução do tempo de construção do mapa do ambiente. No presente trabalho, um método de integração de mapas locais é proposto baseado em observações inter-robôs, considerando uma nova abordagem para a exploração do ambiente. Tal abordagem é conhecida como Sistema de Vigilância baseado na Modificação do Sistema Colônias de Formigas, ou IAS-SS. A estratégia IAS-SS é inspirada em mecanismos biológicos que definem a organização social de sistemas de enxames. Especificamente, esta estratégia é baseada em uma modificação do tradicional algoritmo de otimização por colônias de formiga. A principal contribuição do presente trabalho é a adaptação de um modelo de compartilhamento de informações utilizado em redes de sensores móveis, adaptando o mesmo para tarefas de mapeamento. Outra importante contribuição é a colaboração entre o método proposto de integração de mapas e a estratégia de coordenação de múltiplos robôs baseada na teoria de colônias de formigas. Tal colaboração permite o desenvolvimento de uma abordagem de exploração que emprega um mecanismo não físico para depósito e detecção de feromônios em ambientes reais por meio da elaboração do conceito de feromônios virtuais integrados. Resultados obtidos em simulação demonstram que o método de integração de mapas é eficiente, de modo que os ensaios experimentais foram realizados considerando-se um número variável de robôs móveis durante o processo de exploração de ambientes internos com diferentes formas e estruturas. Os resultados obtidos com os diversos experimentos realizados confirmam que o processo de integração é efetivo e adequado para executar o mapeamento do ambiente durante tarefas de exploração e vigilância do mesmo / The multiple robot map building strategies have several advantages when compared to strategies based on a single robot, in terms of flexibility, gain of information and reduction of map building time. In this work, a local map integration method is proposed based on the inter-robot observations, considering a recent approach for the environment exploration. This approach is based on the Inverse Ant System-Based Surveillance System strategy, called IASSS. The IAS-SS strategy is inspired on biological mechanisms that define the social organization of swarm systems. Specifically, it is based on a modified version of the known ant colony algorithm. The main contribution of this work is the fit of an information sharing model used in an mobile sensor network, adapting the method for mapping tasks. Another important contribution is the collaboration between the local map integration method and the multiple robot coordination strategy based on ant colony theory. Through this collaboration it is possible to develop an approach that uses a mechanism for controlling the access to pheromones in real environments. Such mechanism is based on the integrated virtual pheromones concept. Simulation results show that the map integration method is efficient, the trials are performed considering a variable number of robots and environments with different structures. Results obtained from several experiments confirm that the integration process is effective and suitable to execute mapping during the exploration task

This thesis presents research focused on developing statistical methods with emphasis on techniques that can be used for the analysis of data in imaging studies and sparse estimations for applications in high-dimensional data. The first contribution addresses the pixel/voxel-labeling problem for spatial hidden Markov models in image analysis. We formulate a Gaussian spatial mixture model with Potts model used as a prior for mixture allocations for the latent states in the model. Jointly estimating the model parameters, the discrete state variables and the number of states (number of mixture components) is recognized as a difficult combinatorial optimization. To overcome drawbacks associated with local algorithms, we implement and make comparisons between iterated conditional modes (ICM), simulated annealing (SA) and hybrid ICM with ant colony system (ACS-ICM) optimization for pixel labelling, parameter estimation and mixture component estimation. In the second contribution, we develop ACS-ICM algorithm for spatiotemporal modeling of combined MEG/EEG data for computing estimates of the neural source activity. We consider a Bayesian finite spatial mixture model with a Potts model as a spatial prior and implement the ACS-ICM for simultaneous point estimation and model selection for the number of mixture components. Our approach is evaluated using simulation studies and an application examining the visual response to scrambled faces. In addition, we develop a nonparametric bootstrap for interval estimation to account for uncertainty in the point estimates. In the third contribution, we present sparse estimation strategies in linear mixed model (LMM) for longitudinal data. We address the problem of estimating the fixed effects parameters of the LMM when the model is sparse and predictors are correlated. We propose and derive the asymptotic properties of the pretest and shrinkage estimation strategies. Simulation studies is performed to compare the numerical performance of the Lasso and adaptive Lasso estimators with the pretest and shrinkage ridge estimators. The methodology is evaluated through an application of a high-dimensional data examining effective brain connectivity and genetics. In the fourth and final contribution, we conduct an imaging genetics study to explore how effective brain connectivity in the default mode network (DMN) may be related to genetics within the context of Alzheimer’s disease. We develop an analysis of longitudinal resting-state functional magnetic resonance imaging (rs-fMRI) and genetic data obtained from a sample of 111 subjects with a total of 319 rs-fMRI scans from the Alzheimer’s Disease Neuroimaging Initiative (ADNI) database. A Dynamic Causal Model (DCM) is fit to the rs-fMRI scans to estimate effective brain connectivity within the DMN and related to a set of single nucleotide polymorphisms (SNPs) contained in an empirical disease-constrained set. We relate longitudinal effective brain connectivity estimated using spectral DCM to SNPs using both linear mixed effect (LME) models as well as function-on-scalar regression (FSR). / Graduate

This thesis deals with the implementation of the metaheuristic algorithms into the Drools Planner. The Drools Planner is an open source tool for solving optimization problems. This work describes design and implementation of Ant colony optimization metaheuristics in the Drools Planner. Evaluation of the algorithm results is done by Drools Planner benchmark with different kinds of optimization problems.

Opposition-based learning (OBL) was recently proposed to extend di erent machine learning algorithms. The main idea of OBL is to consider opposite estimates, actions or states as an attempt to increase the coverage of the solution space and to reduce exploration time. OBL has already been applied to reinforcement learning, neural networks and genetic algorithms. This thesis explores the application of OBL to ant algorithms. Ant algorithms are based on the trail laying and following behaviour of ants. They have been successfully applied to many complex optimization problems. However, like any other technique, they can benefit from performance improvements. Thus, this work was motivated by the idea of developing more complex pheromone and path selection behaviour for the algorithm using the concept of opposition. This work proposes opposition-based extensions to the construction and update phases of the ant algorithm. The modifications that focus on the solution construction include three direct and two indirect methods. The three direct methods work by pairing the ants and synchronizing their path selection. The two other approaches modify the decisions of the ants by using opposite-pheromone content. The extension of the update phase lead to an approach that performs additional pheromone updates using opposite decisions. Experimental validation was done using two versions of the ant algorithm: the Ant System and the Ant Colony System. The di erent OBL extensions were applied to the Travelling Salesman Problem (TSP) and to the Grid World Problem (GWP). Results demonstrate that the concept of opposition is not easily applied to the ant algorithm. One pheromone-based method showed performance improvements that were statistically significant for the TSP. The quality of the solutions increased and more optimal solutions were found. The extension to the update phase showed some improvements for the TSP and led to accuracy improvements and a significant speed-up for the GWP. The other extensions showed no clear improvement. The proposed methods for applying opposition to the ant algorithm have potential, but more investigations are required before ant colony optimization can fully benefit from opposition. Most importantly, fundamental theoretical work with graphs, specifically, clearly defining opposite paths or opposite path components, is needed. Overall, the results indicate that OBL ideas can be beneficial for ant algorithms.

Opposition-based learning (OBL) was recently proposed to extend di erent machine learning algorithms. The main idea of OBL is to consider opposite estimates, actions or states as an attempt to increase the coverage of the solution space and to reduce exploration time. OBL has already been applied to reinforcement learning, neural networks and genetic algorithms. This thesis explores the application of OBL to ant algorithms. Ant algorithms are based on the trail laying and following behaviour of ants. They have been successfully applied to many complex optimization problems. However, like any other technique, they can benefit from performance improvements. Thus, this work was motivated by the idea of developing more complex pheromone and path selection behaviour for the algorithm using the concept of opposition. This work proposes opposition-based extensions to the construction and update phases of the ant algorithm. The modifications that focus on the solution construction include three direct and two indirect methods. The three direct methods work by pairing the ants and synchronizing their path selection. The two other approaches modify the decisions of the ants by using opposite-pheromone content. The extension of the update phase lead to an approach that performs additional pheromone updates using opposite decisions. Experimental validation was done using two versions of the ant algorithm: the Ant System and the Ant Colony System. The di erent OBL extensions were applied to the Travelling Salesman Problem (TSP) and to the Grid World Problem (GWP). Results demonstrate that the concept of opposition is not easily applied to the ant algorithm. One pheromone-based method showed performance improvements that were statistically significant for the TSP. The quality of the solutions increased and more optimal solutions were found. The extension to the update phase showed some improvements for the TSP and led to accuracy improvements and a significant speed-up for the GWP. The other extensions showed no clear improvement. The proposed methods for applying opposition to the ant algorithm have potential, but more investigations are required before ant colony optimization can fully benefit from opposition. Most importantly, fundamental theoretical work with graphs, specifically, clearly defining opposite paths or opposite path components, is needed. Overall, the results indicate that OBL ideas can be beneficial for ant algorithms.

L’objectif de ce travail est d’exploiter les potentialités offertes par la conduite coopérative afin de fluidifier le trafic au niveau des intersections isolées. Pour ce faire, nous avons proposé un nouveau système de régulation au sein des intersections en s’inspirant du principe de l’intersection autonome. Nous avons appelé notre système : SVAC (système du véhicule-actionneur coopératif). Il repose sur la possibilité des échanges d’information entre le véhicule et son environnement de conduite.Le SVAC permet une régulation plus précise du trafic puisqu’il se base sur les requêtes de droit de passage envoyées par les véhicules réellement présents dans l’intersection. En outre, grâce à la signalisation à bord, la régulation consiste à définir les séquences de passage des véhicules, ce qui permet de personnaliser la signalisation. Le gain de précision soulève plusieurs obstacles. D’une part, nous nous heurtons systématiquement à l’absence de modèles mathématiques permettant d’aborder le problème. D’autre part, la simple énumération des séquences implique une explosion combinatoire, ce qui ne convient pas à l’application temps-réelle de la régulation des intersections. Pour s’affranchir des deux problématiques nous avons utilisé les réseaux de Petri P-temporisés. Le modèle nous a permis de décrire sous la forme d’équations mathématiques les compteurs des différents évènements observés par les véhicules. Deux objectifs de régulation ont été dégagés après avoir déduit le temps moyen d’attente basé sur la formule de Little. Le premier consiste à vider les intersections au plus tôt. Nous avons proposé un algorithme de programmation dynamique et deux heuristiques. La première heuristique est directement issue de l’analyse des propriétés du problème posé. La deuxième est basée sur l’algorithme de colonies de fourmis. En effet, le problème défini est un cas particulier du problème du voyageur de commerce. Le deuxième objectif de régulation consiste à minimiser instantanément la longueur de la file d’attente. Dans ce cadre, nous avons supposé le fonctionnement à vitesse maximale du réseau de Petri. L’utilisation des contraintes sur les ressources nous a permis de définir des règles simples de régulation en utilisant le mapping.Dans ce mémoire, nous avons utilisé la simulation microscopique basée sur les lois de poursuite pour s’approcher du comportement de conduite. La simulation a servi pour la comparaison des différentes approches proposées dans ce mémoire avec les régulateurs adaptatifs et les intersections autonomes. Dans tous les cas notre approche se distingue par un gain de capacité, ce qui nous a encouragé de reproduire le SVAC à travers un prototype de robots. Cette maquette montre la faisabilité du système au moins pour des applications industrielles. / The aim of this work is to benefit from the potential of the cooperative driving in order to optimize the traffic throughput at isolated intersections. To achieve this objective, we have proposed a new traffic control system for isolated intersections: Cooperative Vehicle-Actuation Signalization (CVAS). The concept of this new system is based on the assumption of the ability of exchanging information between each vehicle and the surrounding vehicles or the nearby infrastructure.The system allows more precise control of the traffic since it determines the right-of-way of each vehicle according to its corresponding data sent by the embedded wireless device. The right-of-way is displayed to the driver by means of the onboard signalization. The control system determines the sequence of the vehicles to be directed through the intersection. For the sake of benefiting the improvement brought by the new system, we face several challenges. On the one hand, we are confronted with the absence of a mathematical model to address the control problem. On the other hand, despite the fact that the optimal passing sequence of vehicles can be found by the simple enumeration of all feasible sequences, the exhaustive search does not fulfill the requirements of the real-time application. To overcome these two problems, we seek help from the P-timed Petri nets. This mathematical modeling tool is able to describe the events observed by the position markers in the form of mathematical equations. Two different objectives of the control have been derived from the Little's formula. The first one aims to minimize the maximum exit time of vehicles present in the intersection. An algorithm of dynamic programming and two heuristics have been proposed to achieve this objective. The first heuristic is based on the analysis of the properties of the control problem. The second heuristic is based on the analogy between the dealt problem and the problem of Traveling Salesman Problem, which can be solved successfully by the algorithm of ant colony system. The second objective of the control is to instantly minimize the queue length. A protocol of relaying the right of way has been determined from the assumption of a Petri net that operates at its maximum speed. This simple protocol of control can be extended to all possible layouts of the isolated intersections by using the technique of “mapping”.In this work, a microscopic model (car-following model) is used to simulate the driving behavior. The simulations show that the CVAS system outperforms the other systems which are popularly used at present. It is even better than some innovative systems based on the technology of the cooperative driving. The good results encouraged us to replicate the system under real conditions through a prototype of NXT robots. The tests of this prototype prove the feasibility of the system at least for industrial applications.

This diploma thesis deals with ant colony optimization for shortest path problems. In the theoretical part it describes Ant Colony Optimization. In the practical part ant colony optimization algorithms are selected for the design and implementation of shortest path problems in the Java.