Approximations on minimum weight pseudo-triangulation problem using ant colony optimization

In this work, we consider the Minimum Weight Pseudo-Triangulation (MWPT) problem of a given set of n points in the plane. Globally optimal pseudo-triangulations with respect to the weight, as optimization criteria, are difficult to be found by deterministic methods, since no polynomial algorithm is known. We show how the Ant Colony Optimization (ACO) metaheuristic can be used to find high quality pseudo-triangulations of minimum weight. We present the experimental and statistical study based on our own set of instances since no reference to benchmarks for these problems were found in the literature. Throughout the experimental evaluation, we appraise the ACO metaheuristic performance for MWPT problem.

Decentralized multi-tasks distribution in heterogeneous robot teams by means of ant colony optimization and learning automata

This paper focuses on the general problem of coordinating multiple robots. More specifically, it addresses the self-election of heterogeneous specialized tasks by autonomous robots. In this paper we focus on a specifically distributed or decentralized approach as we are particularly interested on decentralized solution where the robots themselves autonomously and in an individual manner, are responsible of selecting a particular task so that all the existing tasks are optimally distributed and executed. In this regard, we have established an experimental scenario to solve the corresponding multi-tasks distribution problem and we propose a solution using two different approaches by applying Ant Colony Optimization-based deterministic algorithms as well as Learning Automata-based probabilistic algorithms. We have evaluated the robustness of the algorithm, perturbing the number of pending loads to simulate the robot’s error in estimating the real number of pending tasks and also the dynamic generation of loads through time. The paper ends with a critical discussion of experimental results.

Automatic design of Ant Colony Optimization for permutation problems

In this study, we present a framework based on ant colony optimization (ACO) for tackling combinatorial problems. ACO algorithms have been applied to many diferent problems, focusing on algorithmic variants that obtain high-quality solutions. Usually, the implementations are re-done for various problem even if they maintain the same details of the ACO algorithm. However, our goal is to generate a sustainable framework for applications on permutation problems. We concentrate on understanding the behavior of pheromone trails and specific methods that can be combined. Eventually, we will propose an automatic offline configuration tool to build an efective algorithm. ---RESUMEN---En este trabajo vamos a presentar un framework basado en la familia de algoritmos ant colony optimization (ACO), los cuales están dise~nados para enfrentarse a problemas combinacionales. Los algoritmos ACO han sido aplicados a diversos problemas, centrándose los investigadores en diversas variantes que obtienen buenas soluciones. Normalmente, las implementaciones se tienen que rehacer, inclusos si se mantienen los mismos detalles para los algoritmos ACO. Sin embargo, nuestro objetivo es generar un framework sostenible para aplicaciones sobre problemas de permutaciones. Nos centraremos en comprender el comportamiento de la sendas de feromonas y ciertos métodos con los que pueden ser combinados. Finalmente, propondremos una herramienta para la configuraron automática offline para construir algoritmos eficientes.

A Multi Ant Colony Optimization algorithm for a Mixed Car Assembly Line

This paper presents an ant colony optimization algorithm to sequence the mixed assembly lines considering the inventory and the replenishment of components. This is a NP-problem that cannot be solved to optimality by exact methods when the size of the problem growth. Groups of specialized ants are implemented to solve the different parts of the problem. This is intended to differentiate each part of the problem. Different types of pheromone structures are created to identify good car sequences, and good routes for the replenishment of components vehicle. The contribution of this paper is the collaborative approach of the ACO for the mixed assembly line and the replenishment of components and the jointly solution of the problem.

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.

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 Optimization for Requirement selection in Incremental Software development

This proposal shows that ACO systems can be applied to problems of requirements selection in software incremental development, with the idea of obtaining better results of those produced by expert judgment alone. The evaluation of the ACO systems should be done through a compared analysis with greedy and simulated annealing algorithms, performing experiments with some problems instances

Multi-objective ant colony optimization for requirements selection

The selection of a set of requirements between all the requirements previously defined by customers is an important process, repeated at the beginning of each development step when an incremental or agile software development approach is adopted. The set of selected requirements will be developed during the actual iteration. This selection problem can be reformulated as a search problem, allowing its treatment with metaheuristic optimization techniques. This paper studies how to apply Ant Colony Optimization algorithms to select requirements. First, we describe this problem formally extending an earlier version of the problem, and introduce a method based on Ant Colony System to find a variety of efficient solutions. The performance achieved by the Ant Colony System is compared with that of Greedy Randomized Adaptive Search Procedure and Non-dominated Sorting Genetic Algorithm, by means of computational experiments carried out on two instances of the problem constructed from data provided by the experts.

Flexible colony-founding strategies in a socially polymorphic ant

In social insects the number of queens per nest varies greatly. One of the proximate causes of this variation may be that queens produced by multiple-queen colonies are generally smaller, and might thus be unable to found new colonies independently. We examined whether the social origin of queens and males influenced the colony-founding success of queens in the socially polymorphic ant Formica selysi. Queens originating from single-queen and multiple-queen colonies had similar survival rates and colony-founding success, be they alone or in two-queen associations. During the first 5 months, queens originating from single-queen colonies gave rise to more workers than queens originating from multiple-queen colonies. Pairs of queens were also more productive than single queens. However, these differences in productivity were transient, as all types of colonies had reached a similar size after 15 months. Mating between social forms was possible and did not decrease queen survival or colony productivity, compared to mating within social forms. Overall, these results indicate that queens from each social form are able to found colonies independently, at least under laboratory conditions. Moreover, gene flow between social forms is not restricted by mating or genetic incompatibilities. This flexibility in mating and colony founding helps to explain the maintenance of alternative social structures in sympatry and the absence of genetic differentiation between social forms.

Ant larval demand reduces aphid colony growth rates in an ant-aphid interaction

Ants often form mutualistic interactions with aphids, soliciting honeydew in return for protective services. Under certain circumstances, however, ants will prey upon aphids. In addition, in the presence of ants aphids may increase the quantity or quality of honeydew produced, which is costly. Through these mechanisms, ant attendance can reduce aphid colony growth rates. However, it is unknown whether demand from within the ant colony can affect the ant-aphid interaction. In a factorial experiment, we tested whether the presence of larvae in Lasius niger ant colonies affected the growth rate of Aphis fabae colonies. Other explanatory variables tested were the origin of ant colonies (two separate colonies were used) and previous diet (sugar only or sugar and protein). We found that the presence of larvae in the ant colony significantly reduced the growth rate of aphid colonies. Previous diet and colony origin did not affect aphid colony growth rates. Our results suggest that ant colonies balance the flow of two separate resources from aphid colonies- renewable sugars or a protein-rich meal, depending on demand from ant larvae within the nest. Aphid payoffs from the ant-aphid interaction may change on a seasonal basis, as the demand from larvae within the ant colony waxes and wanes.

Visual Navigation In The Neotropical Ant Odontomachus Hastatus (formicidae, Ponerinae), A Predominantly Nocturnal, Canopy-dwelling Predator Of The Atlantic Rainforest.

The arboreal ant Odontomachus hastatus nests among roots of epiphytic bromeliads in the sandy forest at Cardoso Island (Brazil). Crepuscular and nocturnal foragers travel up to 8m to search for arthropod prey in the canopy, where silhouettes of leaves and branches potentially provide directional information. We investigated the relevance of visual cues (canopy, horizon patterns) during navigation in O. hastatus. Laboratory experiments using a captive ant colony and a round foraging arena revealed that an artificial canopy pattern above the ants and horizon visual marks are effective orientation cues for homing O. hastatus. On the other hand, foragers that were only given a tridimensional landmark (cylinder) or chemical marks were unable to home correctly. Navigation by visual cues in O. hastatus is in accordance with other diurnal arboreal ants. Nocturnal luminosity (moon, stars) is apparently sufficient to produce contrasting silhouettes from the canopy and surrounding vegetation, thus providing orientation cues. Contrary to the plain floor of the round arena, chemical cues may be important for marking bifurcated arboreal routes. This experimental demonstration of the use of visual cues by a predominantly nocturnal arboreal ant provides important information for comparative studies on the evolution of spatial orientation behavior in ants. This article is part of a Special Issue entitled: Neotropical Behaviour.

Optimization of the Topology of Electric Energy Distribution Networks by Using Algorithm Inspired on Ant Behaviors

An algorithm inspired on ant behavior is developed in order to find out the topology of an electric energy distribution network with minimum power loss. The algorithm performance is investigated in hypothetical and actual circuits. When applied in an actual distribution system of a region of the State of Sao Paulo (Brazil), the solution found by the algorithm presents loss lower than the topology built by the concessionary company.

Arboreal thorn-dwelling ants use domatia morphology to partition nest sites on the savanna ant-plant, Vachellia erioloba

Nest site selection in arboreal, domatia-dwelling ants, particularly those coexisting on a single host plant, is little understood. To examine this phenomenon we studied the African savannah tree Vachellia erioloba, which hosts ants in swollen-thorn domatia. We found four ant species from different genera (Cataulacus intrudens, Tapinoma subtile, Tetraponera ambigua and an unidentified Crematogaster species). In contrast to other African ant plants, many V. erioloba trees (41 % in our survey) were simultaneously co-occupied by more than one ant species. Our study provides quantitative field data describing: (1) aspects of tree and domatia morphology relevant to supporting a community of mutualist ants, (2) how ant species occupancy varies with domatia morphology and (3) how ant colony size varies with domatia size and species. We found that Crematogaster sp. occupy the largest thorns, followed by C. intrudens, with T. subtile in the smallest thorns. Thorn age, as well as nest entrance hole size correlated closely with ant species occupant. These differing occupancy patterns may help to explain the unusual coexistence of three ant species on individual myrmecophytic trees. In all three common ant species, colony size, as measured by total number of ants, increased with domatia size. Additionally, domatia volume and species identity interact to predict ant numbers, suggesting differing responses between species to increased availability of nesting space. The proportion of total ants in nests that were immatures varied with thorn volume and species, highlighting the importance of domatia morphology in influencing colony structure.