The Human Genome Project completed in 2003 and the draft of human genome sequences were also yielded. It has been known that any two human gnomes are almost identical, and only very little difference makes human diversities. Single nucleotide polymorphism (SNP) means that a single-base nucleotide changes in DNA. A SNP sequence from one of a pair of chromosomes is called a haplotype. In this thesis, we study how to reconstruct a pair of chromosomes from a given set of fragments obtained by DNA sequencing in an individual. We define a new problem, the chromosome pair assembly problem, for the chromosome reconstruction. The goal of the problem is to find a pair of sequences such that the pair of output sequences have the minimum mismatch with the input fragments and their lengths are minimum. We first transform the problem instance into a directed multigraph. And then we propose an efficient algorithm to solve the problem. We apply the ACO algorithm to optimize the ordering of input fragments and use dynamic programming to determine SNP sites. After the chromosome pair is reconstructed, the two haplotypes can also be determined. We perform our algorithm on some artificial test data. The experiments show that our results are near the optimal solutions of the test data.

The k-LCS problem is to find the longest common subsequence (LCS) of k input sequences. It is difficult while the number of input sequences is large. In the past, researchers focused on finding the LCS of two sequences (2-LCS). However, there is no good algorithm for finding the optimal solution of k-LCS up to now. For solving the k-LCS problem, in this thesis, we first propose a mixed algorithm, which is a combination of a heuristic algorithm, genetic algorithm (GA) and ant colony optimization (ACO) algorithm. Then, we propose an enhanced ACO (EACO) algorithm, composed of the heuristic algorithm and matching pair algorithm (MPA). In our experiments, we compare our algorithms with expansion algorithm, best next for maximal available symbol algorithm, GA and ACO algorithm. The experimental results on several sets of DNA and protein sequences show that our EACO algorithm outperforms other algorithms in the lengths of solutions.

Havlík, M. Ant Colony Optimization: Implementation and testing of bio-inspired optimization method. Diploma thesis. Brno, 2015. This thesis deals with the implementation and testing of algorithm Ant Colony Optimization as a representative of the family of bio-inspired opti-mization methods. A given algorithm is described, analyzed and subsequently put into context with the problems which can be solved. Based on the collec-ted information is designed implementation that solves the Traveling sale-sman problem. Implementation contains graphical user interface to track the algorithm. Implementation is further optimized using parallel programming and other methods. Finally the implementation compared and summarized results.

Ant Colony Optimization (ACO) uses behaviour observed in real-life ant colonies in order to solve shortest path problems. Short paths are found with the use of pheromones, which allow ants to communicate indirectly. There are numerous pheromone distribution techniques for virtual ant systems and this thesis studies two of the most well known, Elitist and Max-Min. Implementations of Elitist and Max-Min ACO algorithms were tested using instances of the Traveling Salesman Problem (TSP). The performance of the different techniques are compared with respect to runtime, iterations and approximation quality when the optimal solution could not be found. It was found that the Elitist strategy performs better on small TSP instances where the number of possible paths are reduced. However, Max-Min proved to be more reliable and better performing when more paths could be chosen or size of the instances increased. When approximating solutions for large instances, Elitist was able to achieve high quality approximations faster than Max-Min. On the other hand, the overall quality of the approximations were better when Max-Min was studied after a slightly longer runtime, compared to Elitist. / Ant Colony Optimization (ACO) drar lärdom av beteende observerat hos riktiga myror för att lösa kortaste vägen problem. Korta vägar hittas med hjälp av feromoner, som tillåter myror att kommunicera indirekt. Det finns flera tekniker för att distribuera feromoner i virtuella myr-system och denna rapport kommer studera två av de mest kända, Elitist och Max-Min. Implementationer av Elitist och Max-Min ACO algoritmer testades med instanser av Handelsresandeproblemet (TSP). Prestandan hos de olika teknikerna jämförs med avseende på körtid, iterationer och approximeringskvalité när den optimala lösningen inte kunde hittas. Det konstaterades att Elitist strategin fungerar bättre på små TSP instanser där antalet möjliga stigar är begränsade. Däremot visade det sig Max-Min vara bättre och mer pålitlig när instansernas storlek ökades eller när fler stigar kunde väljas. När lösningar approximerades för stora instanser kunde Elitist uppnå approximationer med god kvalité snabbare än Max-Min. Däremot var den generella kvalitén hos approximationerna bättre när Max-Min studerades efter en lite längre körtid, jämfört med Elitist.

Traffic signal control is an effective way to improve the efficiency of traffic networks and reduce users’ delays. Ant Colony Optimization (ACO) is a metaheuristic based on the behavior of ant colonies searching for food. ACO has successfully been used to solve many NP-hard combinatorial optimization problems and its stochastic and decentralized nature fits well with traffic flow networks. This thesis investigates the application of ACO to minimize user delay at traffic intersections. Computer simulation results show that this new approach outperforms conventional fully actuated control under the condition of high traffic demand.

In this thesis, we propose to use relevant potential invariants in a simulation-based swarmintelligence-based test generation technique to generate relevant test vectors for design validation at the Register Transfer Level (RTL). Providing useful guidance to the test generator for such techniques is critical. In our approach, we provide guidance by exploiting potential invariants in the design. These potential invariants are obtained using random stimuli such that they are true under these stimuli. Since these potential invariants are only likely to be true, we try to generate stimuli that can falsify them. Any such vectors would help reach some corners of the design. However, the space of potential invariants can be extremely large. To reduce execution time, we also implement a two-layer filter to remove the irrelevant potential invariants that may not contribute in reaching difficult states. With the filter, the vectors generated thus help to reduce the overall test length while still reach the same coverage as considering all unfiltered potential invariants. Experimental results show that with only the filtered potential invariants, we were able to reach equal or better branch coverage than that reported by BEACON in the ITC99 benchmarks, with considerable reduction in vector lengths, at reduced execution time. / Master of Science / Over the recent years, size and complexity of hardware designs are increasing at an enormous rate. Due to this, verification of these designs is of utmost importance and demands much more resources and time than designing of these hardware. To project the information of the designs, developers use Hardware Descriptive Languages (HDL), that includes the important decision points of the system, also called branches of the circuit. There are several methodologies proposed to check how many branches of the design can be traversed by set of inputs. This practice is important to confirm correct functionality of the design as we can catch all the faults in the design at these decision points. Some of these methodologies include checking with random inputs, exhaustively checking for every possible input, investing many hours of labor to verify with appropriate inputs, or simply automating the process of generating inputs. In this thesis, we focus on one such automated process called BEACON or Branch-oriented Evolutionary Ant Colony OptimizatioN. We propose a modification to improve this method by using standard properties of the design. These properties, also known as invariants, help to cover those branches that require extra effort in terms of both inputs and time, and are thus, hard to cover. When we add these significant invariants to the design, modified BEACON is able to cover almost all accessible branches in the system with significantly less amount of time and lesser number of vectors than original BEACON itself, which helps save a lot of resources.

L'amélioration des systèmes énergétiques est considérée comme un levier technologique pour répondre aux défis liés à la croissance de la demande d’électricité et des émissions des gaz à effet de serre. Les futures centrales devraient présenter une intégration thermique plus flexible et des sources de chaleur mixtes possibles. Une des solutions fiables consiste à utiliser un cycle de Brayton au CO2 supercritique (CO2-SC), un tel cycle à haut rendement est théoriquement prometteur pour les applications nucléaires, fossiles et solaires thermiques. Un des principaux obstacles au déploiement du cycle de Brayton au CO2-SC est de justifier sa faisabilité, sa viabilité et son potentiel à l’échelle industrielle. Dans ce contexte deux axes de recherche ont été identifiées : • Une sélection rigoureuse de l’équation d’état qui permet de représenter les propriétés d’intérêt du CO2-SC. • Une nouvelle méthodologie pour l’optimisation des centrales électriques, permettant de sélectionner automatiquement le procédé optimal parmi une grande quantité de configurations possibles (dénomme superstructure). Les résultats de la première partie de cette thèse mettent en lumière que l’équation de SW est pertinente pour limiter l’impact de l’imprécision de l’équation d’état sur le dimensionnement du procédé. Dans cette thèse, un simulateur de procédé commercial, ProSimPlus a été combiné avec un solveur type évolutionnaire (MIDACO) afin d’effectuer des optimisations superstructure. Premièrement, le critère d’optimisation est de maximiser le rendement énergétique du procédé. Dans un deuxième temps, on cherche simultanément à minimiser les coûts du procédé. Pour ce faire, des fonctions de coût internes à EDF ont été utilisées afin de permettre l’estimation des coûts d'investissement (CAPEX), des dépenses opérationnelles (OPEX) et du coût actualisé de l'électricité (LCOE) / Efficiency enhancement in power plant can be seen as a key lever in front of increasing energy demand. Nowadays, both the attention and the emphasis are directed to reliable alternatives, i.e., enhancing the energy conversion systems. The supercritical CO2 (SC-CO2) Brayton cycle has recently emerged as a promising solution for high efficiency power production in nuclear, fossil-thermal and solar-thermal applications. Currently, studies on such a thermodynamic power cycle are directed towards the demonstration of its reliability and viability before the possible building of an industrial-scale unit. The objectives of this PhD can be divided in two main parts: • A rigorous selection procedure of an equation of state (EoS) for SC-CO2 which permits to assess influences of thermodynamic model on the performance and design of a SC-CO2 Brayton cycle. • A framework of optimization-based synthesis of energy systems which enables optimizing both system structure and the process parameters. The performed investigations demonstrate that the Span-Wagner EoS is recommended for evaluating the performances of a SC-CO2 Brayton cycle in order to avoid inaccurate predictions in terms of equipment sizing and optimization. By combining a commercial process simulator and an evolutionary algorithm (MIDACO), this dissertation has identified a global feasible optimum design –or at least competitive solutions– for a given process superstructure under different industrial constraints. The carried out optimization firstly base on cycle energy aspects, but the decision making for practical systems necessitates techno-economic optimizations. The establishment of associated techno-economic cost functions in the last part of this dissertation enables to assess the levelized cost of electricity (LCOE). The carried out multi-objective optimization reflects the trade-off between economic and energy criteria, but also reveal the potential of this technology in economic performance.

ITC/USA 2010 Conference Proceedings / The Forty-Sixth Annual International Telemetering Conference and Technical Exhibition / October 25-28, 2010 / Town and Country Resort & Convention Center, San Diego, California / Telemetry receivers must typically be located so that obstacles do not block the signal path. This can be challenging in geometrically complex indoor environments, such as factories, health care facilities, or offices. An accurate method for estimating the paths followed by typical telemetry transmitters in these environments can assist in system planning. It may be acceptable to provide marginal coverage to areas which are rarely visited, or areas which transmitters quickly transit. This paper discusses the use of the ant colony optimization and its application to the telemetry system planning problem.

This thesis proposes different approaches to address routing and security of MANETs using swarm technology. The mobility and infrastructure-less of MANET as well as nodes misbehavior compose great challenges to routing and security protocols of such a network. The first approach addresses the problem of channel assignment in multichannel ad hoc networks with limited number of interfaces, where stable route are more preferred to be selected. The channel selection is based on link quality between the nodes. Geographical information is used with mapping algorithm in order to estimate and predict the links’ quality and routes life time, which is combined with Ant Colony Optimization (ACO) algorithm to find most stable route with high data rate. As a result, a better utilization of the channels is performed where the throughput increased up to 74% over ASAR protocol. A new smart data packet routing protocol is developed based on the River Formation Dynamics (RFD) algorithm. The RFD algorithm is a subset of swarm intelligence which mimics how rivers are created in nature. The protocol is a distributed swarm learning approach where data packets are smart enough to guide themselves through best available route in the network. The learning information is distributed throughout the nodes of the network. This information can be used and updated by successive data packets in order to maintain and find better routes. Data packets act like swarm agents (drops) where they carry their path information and update routing information without the need for backward agents. These data packets modify the routing information based on different network metrics. As a result, data packet can guide themselves through better routes. In the second approach, a hybrid ACO and RFD smart data packet routing protocol is developed where the protocol tries to find shortest path that is less congested to the destination. Simulation results show throughput improvement by 30% over AODV protocol and 13% over AntHocNet. Both delay and jitter have been improved more than 96% over AODV protocol. In order to overcome the problem of source routing introduced due to the use of the ACO algorithm, a solely RFD based distance vector protocol has been developed as a third approach. Moreover, the protocol separates reactive learned information from proactive learned information to add more reliability to data routing. To minimize the power consumption introduced due to the hybrid nature of the RFD routing protocol, a forth approach has been developed. This protocol tackles the problem of power consumption and adds packets delivery power minimization to the protocol based on RFD algorithm. Finally, a security model based on reputation and trust is added to the smart data packet protocol in order to detect misbehaving nodes. A trust system has been built based on the privilege offered by the RFD algorithm, where drops are always moving from higher altitude to lower one. Moreover, the distributed and undefined nature of the ad hoc network forces the nodes to obligate to cooperative behaviour in order not to be exposed. This system can easily and quickly detect misbehaving nodes according to altitude difference between active intermediate nodes.

In this work, we present a way to extend Ant Colony Optimization (ACO), so that it can be applied to both continuous and mixed-variable optimization problems. We demonstrate, first, how ACO may be extended to continuous domains. We describe the algorithm proposed, discuss the different design decisions made, and we position it among other metaheuristics. Following this, we present the results of numerous simulations and testing. We compare the results obtained by the proposed algorithm on typical benchmark problems with those obtained by other methods used for tackling continuous optimization problems in the literature. Finally, we investigate how our algorithm performs on a real-world problem coming from the medical field—we use our algorithm for training neural network used for pattern classification in disease recognition. Following an extensive analysis of the performance of ACO extended to continuous domains, we present how it may be further adapted to handle both continuous and discrete variables simultaneously. We thus introduce the first native mixed-variable version of an ACO algorithm. Then, we analyze and compare the performance of both continuous and mixed-variable ACO algorithms on different benchmark problems from the literature. Through the research performed, we gain some insight into the relationship between the formulation of mixed-variable problems, and the best methods to tackle them. Furthermore, we demonstrate that the performance of ACO on various real-world mixed-variable optimization problems coming from the mechanical engineering field is comparable to the state of the art.