Modified continuous ant colony algorithm for function optimization

Many classical as well as modern optimization techniques exist. One such modern method belonging to the field of swarm intelligence is termed ant colony optimization. This relatively new concept in optimization involves the use of artificial ants and is based on real ant behavior inspired by the way ants search for food. In this thesis, a novel ant colony optimization technique for continuous domains was developed. The goal was to provide improvements in computing time and robustness when compared to other optimization algorithms. Optimization function spaces can have extreme topologies and are therefore difficult to optimize. The proposed method effectively searched the domain and solved difficult single-objective optimization problems. The developed algorithm was run for numerous classic test cases for both single and multi-objective problems. The results demonstrate that the method is robust, stable, and that the number of objective function evaluations is comparable to other optimization algorithms.

Ant colony search algorithm for the optimal power flow problem

To maintain a power system within operation limits, a level ahead planning it is necessary to apply competitive techniques to solve the optimal power flow (OPF). OPF is a non-linear and a large combinatorial problem. The Ant Colony Search (ACS) optimization algorithm is inspired by the organized natural movement of real ants and has been successfully applied to different large combinatorial optimization problems. This paper presents an implementation of Ant Colony optimization to solve the OPF in an economic dispatch context. The proposed methodology has been developed to be used for maintenance and repairing planning with 48 to 24 hours antecipation. The main advantage of this method is its low execution time that allows the use of OPF when a large set of scenarios has to be analyzed. The paper includes a case study using the IEEE 30 bus network. The results are compared with other well-known methodologies presented in the literature.

Sequenzierung mit Ant-Colony-Systemen am Beispiel Querverteil-Wagen

Dieser Beitrag zeigt die Anwendung des Ant-Colony-System (ACS) Algorithmus auf die Sequenzierung von Querverteil-Wagen in einem Lager. Wir erweitern den Basisalgorithmus der Ant-Colony-Optimierung (ACO) für die Minimierung der Bearbeitungszeit einer Menge von Fahraufträgen für die Querverteil-Wagen. Im Vergleich zu dem Greedy-Algorithmus ist der ACO-Algorithmus wettbewerbsfähig und schnell. In vielen Lagerverwaltungssystemen werden die Fahraufträge nach dem FIFO-Prinzip (First-in-First-out) ausgeführt. In diesem Beitrag wird der ACO-Algorithmus genutzt, um eine optimale Sequenz der Fahraufträge zu bilden.

Ant colony system based approach to single machine scheduling problems: weighted tardiness scheduling problem

The paper introduces an approach to solve the problem of generating a sequence of jobs that minimizes the total weighted tardiness for a set of jobs to be processed in a single machine. An Ant Colony System based algorithm is validated with benchmark problems available in the OR library. The obtained results were compared with the best available results and were found to be nearer to the optimal. The obtained computational results allowed concluding on their efficiency and effectiveness.

Ant colony for TSP

The aim of this work is to investigate Ant Colony Algorithm for the traveling salesman problem (TSP). Ants of the artificial colony are able to generate successively shorter feasible tours by using information accumulated in the form of a pheromone trail deposited on the edges of the TSP graph. This paper is based on the ideas of ant colony algorithm and analysis the main parameters of the ant colony algorithm. Experimental results for solving TSP problems with ant colony algorithm show great effectiveness.

Application of ontologies in peer-to-peer database with routing queries based on ant colony algorithm

A significant set of information stored in different databases around the world, can be shared through peer-topeer databases. With that, is obtained a large base of knowledge, without the need for large investments because they are used existing databases, as well as the infrastructure in place. However, the structural characteristics of peer-topeer, makes complex the process of finding such information. On the other side, these databases are often heterogeneous in their schemas, but semantically similar in their content. A good peer-to-peer databases systems should allow the user access information from databases scattered across the network and receive only the information really relate to your topic of interest. This paper proposes to use ontologies in peer-to-peer database queries to represent the semantics inherent to the data. The main contribution of this work is enable integration between heterogeneous databases, improve the performance of such queries and use the algorithm of optimization Ant Colony to solve the problem of locating information on peer-to-peer networks, which presents an improve of 18% in results. © 2011 IEEE.

Social and temporal organization in an ant colony

Ant colonies are known for their complex and efficient social organization that com-pletely lacks hierarchical structure. However, due to methodological difficulties in follow¬ing all ants of a colony, it was until now impossible to investigate the social and temporal organization of colonies. We developed a tracking system that allows tracking the posi¬tions and orientations of several hundred individually labeled ants continuously, providing for the first time quantitative long term data on all individuals of a colony. These data permit reconstructing trajectories, activity patterns and social networks of all ants in a colony and enable us to investigate ant behavior quantitatively in previously unpreceded ways. By analyzing the spatial positions and social interactions of all ants in six colonies for 41 days we show that ant colonies are organized in groups of nurses, nest patrollers and foragers. Workers of each group were highly interconnected and occupied similar spa¬tial locations in the nest. Groups strongly segregated spatially, and were characterized by unique behavioral signatures. Nurses spent most of their time on the brood. Nest patrollers frequently visited the rubbish pile, and foragers frequently visited the forag¬ing arena. In addition nurses were on average younger than nest patrollers who were, in turn, younger than foragers. We further show that workers had a preferred behav¬ioral trajectory and moved from nursing to nest patrolling, and from nest patrolling to foraging. By analyzing the activity patterns of all ants we show that only a third of all workers in a colony exhibit circadian rhythms and that these rhythms shortened by on av¬erage 42 minutes in constant darkness, thereby demonstrating the presence of a functional endogenous clock. Most rhythmic workers were foragers suggesting that rhythmicity is tightly associated with task. Nurses and nest patrollers were arrhythmic which most likely reflects plasticity of the circadian clock, as isolated workers in many species exhibit circadian rhythmicity. Altogether our results emphasize that ant colonies, despite their chaotic appearance, repose on a strong underlying social and temporal organization. - Les colonies de fourmis sont connues pour leur organisation sociale complexe et effi-cace, charactérisée par un manque absolu de structure hiérarchique. Cependant, puisqu'il est techniquement très difficile de suivre toutes les fourmis d'une colonie, il a été jusqu'à maintenant impossible d'étudier l'organisation sociale et temporelle des colonies de four-mis. Nous avons développé un système qui permet d'extraire en temps réel à partir d'images vidéo les positions et orientations de plusieurs centaines de fourmis marquées individuellement. Nous avons pu ainsi générer pour la première fois des données quanti-tatives et longitudinales relatives à des fourmis appartenant à une colonie. Ces données nous ont permis de reconstruire la trajectoire et l'activité de chaque fourmi ainsi que ses réseaux sociaux. Ceci nous a permis d'étudier de manière exhaustive et objective le com-portement de tous les individus d'une colonie. En analysant les données spatiales et les interactions sociales de toutes les fourmis de six colonies qui ont été filmées pendant 41 jours, nous montrons que les fourmis d'une même colonie se répartissent en trois groupes: nourrices, patrouilleuses et approvisionneuses. Les fourmis d'un même groupe interagis-sent fréquemment et occupent le même espace à l'intérieur du nid. L'espace propre à un groupe se recoupe très peu avec celui des autres. Chaque groupe est caractérisé par un comportement typique. Les nourrices s'affairent surtout autour du couvain. Les pa-trouilleuses font de fréquents déplacements vers le tas d'ordures, et les approvisionneuses sortent souvent du nid. Les nourrices sont en moyenne plus jeunes que les patrouilleuses qui, à leur tour, sont plus jeunes que les approvisionneuses. De plus, nous montrons que les ouvrières changent de tâche au cours de leur vie, passant de nourrice à patrouilleuse puis à approvisionneuse. En analysant l'activité de chaque fourmi, nous montrons que seulement un tiers des ouvrières d'une colonie présente des rythmes circadiens et que ces rythmes diminuent en moyenne de 42 minutes lorsqu'il y a obscurité constante, ce qui démontre ainsi la présence d'une horloge endogène. De plus, la plupart des approvi¬sionneuses ont une activité rythmique alors que les nourrices et patrouilleuses présentent une activité arythmique, ce qui suggère que la rythmicité est étroitement associée à la tâche. L'arythmie des nourrices et patrouilleuses repose probablement sur une plasticité de l'horloge endogène car des ouvrières de nombreuses espèces font preuve d'une ryth¬micité circadienne lorsqu'elles sont isolées de la colonie. Dans l'ensemble nos résultats révèlent qu'une colonie de fourmis se fonde sur une solide organisation sociale et tem¬porelle malgré son apparence chaotique.

Using ant colonies for solve the multiprocessor task graph scheduling

The problem of scheduling a parallel program presented by a weighted directed acyclic graph (DAG) to the set of homogeneous processors for minimizing the completion time of the program has been extensively studied as academic optimization problem which occurs in optimizing the execution time of parallel algorithm with parallel computer.In this paper, we propose an application of the Ant Colony Optimization (ACO) to a multiprocessor scheduling problem (MPSP). In the MPSP, no preemption is allowed and each operation demands a setup time on the machines. The problem seeks to compose a schedule that minimizes the total completion time.We therefore rely on heuristics to find solutions since solution methods are not feasible for most problems as such. This novel heuristic searching approach to the multiprocessor based on the ACO algorithm a collection of agents cooperate to effectively explore the search space.A computational experiment is conducted on a suit of benchmark application. By comparing our algorithm result obtained to that of previous heuristic algorithm, it is evince that the ACO algorithm exhibits competitive performance with small error ratio.

Task assignment optimization in SAP Extended WarehouseManagement

Nowadays in the world of mass consumption there is big demand for distributioncenters of bigger size. Managing such a center is a very complex and difficult taskregarding to the different processes and factors in a usual warehouse when we want tominimize the labor costs. Most of the workers’ working time is spent with travelingbetween source and destination points which cause deadheading. Even if a worker knowsthe structure of a warehouse well and because of that he or she can find the shortest pathbetween two points, it is still not guaranteed that there won’t be long traveling timebetween the locations of two consecutive tasks. We need optimal assignments betweentasks and workers.In the scientific literature Generalized Assignment Problem (GAP) is a wellknownproblem which deals with the assignment of m workers to n tasks consideringseveral constraints. The primary purpose of my thesis project was to choose a heuristics(genetic algorithm, tabu search or ant colony optimization) to be implemented into SAPExtended Warehouse Management (SAP EWM) by with task assignment will be moreeffective between tasks and resources.After system analysis I had to realize that due different constraints and businessdemands only 1:1 assingments are allowed in SAP EWM. Because of that I had to use adifferent and simpler approach – instead of the introduced heuristics – which could gainbetter assignments during the test phase in several cases. In the thesis I described indetails what ware the most important questions and problems which emerged during theplanning of my optimized assignment method.

Classification of petroleum well drilling operations with a hybrid particle swarm/ant colony algorithm

This paper describes an investigation of the hybrid PSO/ACO algorithm to classify automatically the well drilling operation stages. The method feasibility is demonstrated by its application to real mud-logging dataset. The results are compared with bio-inspired methods, and rule induction and decision tree algorithms for data mining. © 2009 Springer Berlin Heidelberg.

Architecture for peer-to-peer databases with routing queries using ant colony algorithm and semantic support

In a peer-to-peer network, the nodes interact with each other by sharing resources, services and information. Many applications have been developed using such networks, being a class of such applications are peer-to-peer databases. The peer-to-peer databases systems allow the sharing of unstructured data, being able to integrate data from several sources, without the need of large investments, because they are used existing repositories. However, the high flexibility and dynamicity of networks the network, as well as the absence of a centralized management of information, becomes complex the process of locating information among various participants in the network. In this context, this paper presents original contributions by a proposed architecture for a routing system that uses the Ant Colony algorithm to optimize the search for desired information supported by ontologies to add semantics to shared data, enabling integration among heterogeneous databases and the while seeking to reduce the message traffic on the network without causing losses in the amount of responses, confirmed by the improve of 22.5% in this amount. © 2011 IEEE.

Algoritmos de alinhamento múltiplo e técnicas de otimização para esses algoritmos utilizando Ant Colony

Pós-graduação em Ciência da Computação - IBILCE

An evolutionary approach to the design of experiments for combinatorial optimization with an application to enzyme engineering

In a large number of problems the high dimensionality of the search space, the vast number of variables and the economical constrains limit the ability of classical techniques to reach the optimum of a function, known or unknown. In this thesis we investigate the possibility to combine approaches from advanced statistics and optimization algorithms in such a way to better explore the combinatorial search space and to increase the performance of the approaches. To this purpose we propose two methods: (i) Model Based Ant Colony Design and (ii) Naïve Bayes Ant Colony Optimization. We test the performance of the two proposed solutions on a simulation study and we apply the novel techniques on an appplication in the field of Enzyme Engineering and Design.

An Ant Colony System adaptation to deal with accessibility issues after a disaster

One of the main problems relief teams face after a natural or man-made disaster is how to plan rural road repair work tasks to take maximum advantage of the limited available financial and human resources. Previous research focused on speeding up repair work or on selecting the location of health centers to minimize transport times for injured citizens. In spite of the good results, this research does not take into account another key factor: survivor accessibility to resources. In this paper we account for the accessibility issue, that is, we maximize the number of survivors that reach the nearest regional center (cities where economic and social activity is concentrated) in a minimum time by planning which rural roads should be repaired given the available financial and human resources. This is a combinatorial problem since the number of connections between cities and regional centers grows exponentially with the problem size, and exact methods are no good for achieving an optimum solution. In order to solve the problem we propose using an Ant Colony System adaptation, which is based on ants? foraging behavior. Ants stochastically build minimal paths to regional centers and decide if damaged roads are repaired on the basis of pheromone levels, accessibility heuristic information and the available budget. The proposed algorithm is illustrated by means of an example regarding the 2010 Haiti earthquake, and its performance is compared with another metaheuristic, GRASP.

Exploring ant-based algorithms for gene expression data analysis

Objective: Recently, much research has been proposed using nature inspired algorithms to perform complex machine learning tasks. Ant colony optimization (ACO) is one such algorithm based on swarm intelligence and is derived from a model inspired by the collective foraging behavior of ants. Taking advantage of the ACO in traits such as self-organization and robustness, this paper investigates ant-based algorithms for gene expression data clustering and associative classification. Methods and material: An ant-based clustering (Ant-C) and an ant-based association rule mining (Ant-ARM) algorithms are proposed for gene expression data analysis. The proposed algorithms make use of the natural behavior of ants such as cooperation and adaptation to allow for a flexible robust search for a good candidate solution. Results: Ant-C has been tested on the three datasets selected from the Stanford Genomic Resource Database and achieved relatively high accuracy compared to other classical clustering methods. Ant-ARM has been tested on the acute lymphoblastic leukemia (ALL)/acute myeloid leukemia (AML) dataset and generated about 30 classification rules with high accuracy. Conclusions: Ant-C can generate optimal number of clusters without incorporating any other algorithms such as K-means or agglomerative hierarchical clustering. For associative classification, while a few of the well-known algorithms such as Apriori, FP-growth and Magnum Opus are unable to mine any association rules from the ALL/AML dataset within a reasonable period of time, Ant-ARM is able to extract associative classification rules.