Multi-Hop Routing Optimization Method Based on Improved Ant Algorithm for Vehicle to Roadside Network

This paper proposes a route optimization method to improve the performance of route selection in Vehicle Ad-hoc Network （VANET）. A novel bionic swarm intelligence algorithm, which is called ant colony algorithm, was introduced into a traditional ad-hoc route algorithm named AODV. Based on the analysis of movement characteristics of vehicles and according to the spatial relationship between the vehicles and the roadside units, the parameters in ant colony system were modified to enhance the performance of the route selection probability rules. When the vehicle moves into the range of several different roadsides, it could build the route by sending some route testing packets as ants, so that the route table can be built by the reply information of test ants, and then the node can establish the optimization path to send the application packets. The simulation results indicate that the proposed algorithm has better performance than the traditional AODV algorithm, especially when the vehicle is in higher speed or the number of nodes increases.     

Simulating the Folding Pathway of RNA Secondary Structure Using the Modified Ant Colony Algorithm

<正> A new method for simulating the folding pathway of RNA secondary structure using the modified ant colony algorithmis proposed.For a given RNA sequence,the set of all possible stems is obtained and the energy of each stem iscalculated and stored at the initial stage.Furthermore,a more realistic formula is used to compute the energy ofmulti-branch loop in the following iteration.Then a folding pathway is simulated,including such processes as constructionof the heuristic information,the rule of initializing the pheromone,the mechanism of choosing the initial andnext stem and the strategy of updating the pheromone between two different stems.Finally by testing RNA sequences withknown secondary structures from the public databases,we analyze the experimental data to select appropriate values forparameters.The measure indexes show that our procedure is more consistent with phylogenetically proven structures thansoftware RNAstructure sometimes and more effective than the standard Genetic Algorithm.     

Balancing organization and flexibility in foraging dynamics

Proper pattern organization and reorganization are central problems facing many biological networks which thrive in fluctuating environments. However, in many cases the mechanisms that organize system activity oppose those that support behavioral flexibility. Thus, a balance between pattern organization and pattern flexibility is critically important for overall biological fitness. We study this balance in the foraging strategies of ant colonies exploiting food in dynamic environments. We present discrete time and space simulations of colony activity that uses a pheromone-based recruitment strategy biasing foraging towards a food source. After food relocation, the pheromone must evaporate sufficiently before foraging can shift colony attention to a new food source. The amount of food consumed within the dynamic environment depends non-monotonically on the pheromone evaporation time constant—with maximal consumption occurring at a time constant which balances trail formation and trail flexibility. A deterministic, ‘mean field’ model of pheromone and foragers on trails mimics our colony simulations. This reduced framework captures the essence of the flexibility-organization balance, and relates optimal pheromone evaporation to the timescale of the dynamic environment. We expect that the principles exposed in our study will generalize and motivate novel analysis across a broad range systems biology.     

The Regulation of Ant Colony Foraging Activity without Spatial Information

Many dynamical networks, such as the ones that produce the collective behavior of social insects, operate without any central control, instead arising from local interactions among individuals. A well-studied example is the formation of recruitment trails in ant colonies, but many ant species do not use pheromone trails. We present a model of the regulation of foraging by harvester ant (Pogonomyrmex barbatus) colonies. This species forages for scattered seeds that one ant can retrieve on its own, so there is no need for spatial information such as pheromone trails that lead ants to specific locations. Previous work shows that colony foraging activity, the rate at which ants go out to search individually for seeds, is regulated in response to current food availability throughout the colony's foraging area. Ants use the rate of brief antennal contacts inside the nest between foragers returning with food and outgoing foragers available to leave the nest on the next foraging trip. Here we present a feedback-based algorithm that captures the main features of data from field experiments in which the rate of returning foragers was manipulated. The algorithm draws on our finding that the distribution of intervals between successive ants returning to the nest is a Poisson process. We fitted the parameter that estimates the effect of each returning forager on the rate at which outgoing foragers leave the nest. We found that correlations between observed rates of returning foragers and simulated rates of outgoing foragers, using our model, were similar to those in the data. Our simple stochastic model shows how the regulation of ant colony foraging can operate without spatial information, describing a process at the level of individual ants that predicts the overall foraging activity of the colony.     

基于蚁群遗传算法的DNA序列比对方法

蚁群遗传算法是在蚁群算法的基础上用遗传算法对其参数进行优化而产生的一种改进算法。把蚁群遗传算法应用于DNA序列比对上,结果表明这种新的序列比对算法是非常有效的。     

An agent-based model to investigate the roles of attractive and repellent pheromones in ant decision making during foraging

Pharaoh's ants organise their foraging system using three types of trail pheromone. All previous foraging models based on specific ant foraging systems have assumed that only a single attractive pheromone is used. Here we present an agent-based model based on trail choice at a trail bifurcation within the foraging trail network of a Pharaoh's ant colony which includes both attractive (positive) and repellent (negative) trail pheromones. Experiments have previously shown that Pharaoh's ants use both types of pheromone. We investigate how the repellent pheromone affects trail choice and foraging success in our simulated foraging system. We find that both the repellent and attractive pheromones have a role in trail choice, and that the repellent pheromone prevents random fluctuations which could otherwise lead to a positive feedback loop causing the colony to concentrate its foraging on the unrewarding trail. An emergent feature of the model is a high level of variability in the level of repellent pheromone on the unrewarding branch. This is caused by the repellent pheromone exerting negative feedback on its own deposition. We also investigate the dynamic situation where the location of the food is changed after foraging trails are established. We find that the repellent pheromone has a key role in enabling the colony to refocus the foraging effort to the new location. Our results show that having a repellent pheromone is adaptive, as it increases the robustness and flexibility of the colony's overall foraging response.     

Behavioral responses to the alarm pheromone of the ant Camponotus obscuripes (Hymenoptera: Formicidae)

The alarm pheromone of the ant Camponotus obscuripes (Formicinae) was identified and quantified by gas chromatography (GC) and gas chromatography-mass spectrometry (GC-MS). Comparisons between alarm pheromone components and extracts from the major exocrine gland of this ant species revealed that the sources of its alarm pheromone are Dufour's gland and the poison gland. Most components of Dufour's gland were saturated hydrocarbons. n-Undecane comprised more than 90% of all components and in a single Dufour's gland amounted to 19 microg. n-Decane and n-pentadecane were also included in the Dufour's gland secretion. Only formic acid was detected in the poison gland, in amounts ranging from 0.049 to 0.91 microl. This ant species releases a mixture of these substances, each of which has a different volatility and function. When the ants sensed formic acid, they eluded the source of the odor; however, they aggressively approached odors of n-undecane and n-decane, which are highly volatile. In contrast, n-pentadecane, which has the lowest volatility among the identified compounds, was shown to calm the ants. The volatilities of the alarm pheromone components were closely related to their roles in alarm communication. Highly volatile components vaporized rapidly and spread widely, and induced drastic reactions among the ants. As these components became diluted, the less volatile components calmed the excited ants. How the worker ants utilize this alarm communication system for efficient deployment of their nestmates in colony defense is also discussed herein.     

The Model Identification for Small Unmanned Aerial Rotorcraft Based on Adaptive Ant Colony Algorithm

This paper proposes a model identification method to get high performance dynamic model of a small unmanned aerial rotorcraft.With the analysis of flight characteristics,a linear dynamic model is constructed by the small perturbation theory.Using the micro guidance navigation and control module,the system can record the control signals of servos,the state information of attitude and velocity information in sequence.After the data preprocessing,an adaptive ant colony algorithm is proposed to get optimal parameters of the dynamic model.With the adaptive adjustment of the pheromone in the selection process,the proposed model identification method can escape from local minima traps and get the optimal solution quickly.Performance analysis and experiments are conducted to validate the effectiveness of the identified dynamic model.Compared with real flight data,the identified model generated by the proposed method has a better performance than the model generated by the adaptive genetic algorithm.Based on the identified dynamic model,the small unmanned aerial rotorcraft can generate suitable control parameters to realize stable hovering,turning,and straight flight.     

Multiple pheromone types and other extensions to the Ant-Miner classification rule discovery algorithm

Ant-Miner is an ant-based algorithm for the discovery of classification rules. This paper proposes five extensions to Ant-Miner: (1) we utilize multiple types of pheromone, one for each permitted rule class, i.e. an ant first selects the rule class and then deposits the corresponding type of pheromone; (2) we use a quality contrast intensifier to magnify the reward of high-quality rules and to penalize low-quality rules in terms of pheromone update; (3) we allow the use of a logical negation operator in the antecedents of constructed rules; (4) we incorporate stubborn ants, an ACO variation in which an ant is allowed to take into consideration its own personal past history; (5) we use an ant colony behavior in which each ant is allowed to have its own values of the ?? and ?? parameters (in a sense, to have its own personality). Empirical results on 23 datasets show improvements in the algorithm??s performance in terms of predictive accuracy and simplicity of the generated rule set.     

An experimental analysis of design choices of multi-objective ant colony optimization algorithms

There have been several proposals on how to apply the ant colony optimization (ACO) metaheuristic to multi-objective combinatorial optimization problems (MOCOPs). This paper proposes a new formulation of these multi-objective ant colony optimization (MOACO) algorithms. This formulation is based on adding specific algorithm components for tackling multiple objectives to the basic ACO metaheuristic. Examples of these components are how to represent multiple objectives using pheromone and heuristic information, how to select the best solutions for updating the pheromone information, and how to define and use weights to aggregate the different objectives. This formulation reveals more similarities than previously thought in the design choices made in existing MOACO algorithms. The main contribution of this paper is an experimental analysis of how particular design choices affect the quality and the shape of the Pareto front approximations generated by each MOACO algorithm. This study provides general guidelines to understand how MOACO algorithms work, and how to improve their design.     

Protein folding in hydrophobic-polar lattice model: a flexible ant-colony optimization approach

This paper proposes a flexible ant colony (FAC) algorithm for solving protein folding problems based on the hydrophobic-polar square lattice model. Collaborations of novel pheromone and heuristic strategies in the proposed algorithm make it more effective in predicting structures of proteins compared with other state-of-the-art algorithms.     

基于改进投影寻踪的海洋生态环境综合评价

为了克服现有的海洋环境评价中存在的主观性强、不易处理高维数据的缺陷,提出了基于改进投影寻踪模型的海洋环境评价新方法.该方法利用改进蚁群算法实现了投影寻踪技术,将方案的多维评价指标值投影为一维投影数据,并据投影值大小对样本进行综合评价.工程应用实例表明,该模型易于决策,具有很强的客观性、适用性和可操作性,为海洋生态环境评价提供了新的技术工具.     

Reconstruction of phylogenetic trees using the ant colony optimization paradigm

We developed a new approach for the reconstruction of phylogenetic trees using ant colony optimization metaheuristics. A tree is constructed using a fully connected graph and the problem is approached similarly to the well-known traveling salesman problem. This methodology was used to develop an algorithm for constructing a phylogenetic tree using a pheromone matrix. Two data sets were tested with the algorithm: complete mitochondrial genomes from mammals and DNA sequences of the p53 gene from several eutherians. This new methodology was found to be superior to other well-known softwares, at least for this data set. These results are very promising and suggest more efforts for further developments.     

Long-term field trial to control the invasive Argentine ant (Hymenoptera: Formicidae) with synthetic trail pheromone

Previous short-term experiments showed that trail following behavior of the Argentine ant, Linepithema humile (Mayr) (Hymenoptera: Formicidae), can be disrupted by a high concentration of synthetic trail pheromone component (Z)-9-hexadecenal. In this study, a long-term field trial was conducted in 100-m2 plots of house gardens in an urban area of Japan to see whether the control effect on Argentine ants can be obtained by permeating synthetic trail pheromone from dispensers. The dispensers were placed in the experimental plots during the ant's active season (April-November) for 2 yr with monthly renewal. To estimate Argentine ant population density, foraging activity of Argentine ants in the study plots was monitored by monthly bait surveys. Throughout the study period, Argentine ant foraging activity was suppressed in the presence of the dispensers, presumably via trail forming inhibition. In contrast, the level of foraging activity was not different between treatment and no-treatment plots when the dispensers were temporarily removed, suggesting that treatment with pheromone dispensers did not suppress Argentine ant density in the treatment plots. Population decline may be expected with larger-scale treatment that covers a significant portion of the ant colony or with improvement in the potency of the disruptant.     

An ambiguous function of an alarm pheromone in the collective displays of the Australian meat ant,Iridomyrmex purpureus

Alarm pheromones, which have been documented in many species of ants, are thought to elicit responses related to aggressive or defensive behaviour. The volatile odour 6-methyl-5-hepten-2-one is described as an alarm pheromone in several species of ants, including the Australian meat ant, Iridomyrmex purpureus. The alarm pheromone is released by displaying workers that aggregate in the characteristic collective display grounds, located mid-way between colonies or near contested food trees. Workers are typically more aggressive at the latter location, and the alarm pheromone may regulate the collective level of aggression. We investigated this possibility by exposing displaying workers to synthesised alarm pheromone 6-methyl-5-hepten-2-one in a field experiment, and measuring their aggressive behaviour. We found no evidence that exposure to synthesised alarm pheromone caused changes in the aggressive level of workers. Subsequent field experiments revealed that the pheromone functions as an attractant, thereby increasing the density of displaying workers. More densely populated workers also display more aggressively, indicating that the interaction rate of displaying workers may determine the level of aggression in collective displays. This underlying mechanism can explain why displaying ants are more aggressive at the more densely populated food-tree locations than those displaying at locations midway between two neighbouring colony nest sites.     

Estimation-based ant colony optimization and local search for the probabilistic traveling salesman problem

The use of ant colony optimization for solving stochastic optimization problems has received a significant amount of attention in recent years. In this paper, we present a study of enhanced ant colony optimization algorithms for tackling a stochastic optimization problem, the probabilistic traveling salesman problem. In particular, we propose an empirical estimation approach to evaluate the cost of the solutions constructed by the ants. Moreover, we use a recent estimation-based iterative improvement algorithm as a local search. Experimental results on a large number of problem instances show that the proposed ant colony optimization algorithms outperform the current best algorithm tailored to solve the given problem, which also happened to be an ant colony optimization algorithm. As a consequence, we have obtained a new state-of-the-art ant colony optimization algorithm for the probabilistic traveling salesman problem.     

Trail formation in ants. A generalized Polya urn process

Faced with a choice of paths, an ant chooses a path with a higher concentration of pheromone. Subsequently, it drops pheromone on the path chosen. The reinforcement of the pheromone-following behavior favors the selection of an initially discovered path as the preferred path. This may cause a long path to emerge as the preferred path, were it discovered earlier than a shorter path. However, the shortness of the shorter path offsets some of the pheromone accumulated on the initially discovered longer path. In this paper, we model the trail formation behavior as a generalized Polya urn process. For k equal length paths, we give the distribution of pheromone at any time and highlight its sole dependence on the initial pheromone concentrations on paths. Additionally, we propose a method to incorporate the lengths of paths in the urn process and derive how the pheromone distribution alters on its inclusion. Analytically, we show that it is possible, under certain conditions, to reverse the initial bias that may be present in favor of paths that were discovered prior to the discovery of more efficient (shorter) paths. This addresses the Plasticity–Stability dilemma for ants, by laying out the conditions under which the system will remain stable or become plastic and change the path. Finally, we validate our analysis and results using simulations.     

蚂蚁群落优化算法在蛋白质折叠二维亲-疏水格点模型中的应用

氨基酸的亲疏水格点模型是研究蛋白质折叠的一种重要的简化模型,其优化问题是一个非确定型的多项式问题。采用蚂蚁群落优化算法对这一问题进行了研究,对测试数据的计算结果表明,在一定规模下,此算法能够有效地获得亲-疏水格点模型的最优解,其效率优于传统的Monte Carlo仿真等方法。     

Ants find the shortest path: a mathematical proof

In the most basic application of Ant Colony Optimization (ACO), a set of artificial ants find the shortest path between a source and a destination. Ants deposit pheromone on paths they take, preferring paths that have more pheromone on them. Since shorter paths are traversed faster, more pheromone accumulates on them in a given time, attracting more ants and leading to reinforcement of the pheromone trail on shorter paths. This is a positive feedback process that can also cause trails to persist on longer paths, even when a shorter path becomes available. To counteract this persistence on a longer path, ACO algorithms employ remedial measures, such as using negative feedback in the form of uniform evaporation on all paths. Obtaining high performance in ACO algorithms typically requires fine tuning several parameters that govern pheromone deposition and removal. This paper proposes a new ACO algorithm, called EigenAnt, for finding the shortest path between a source and a destination, based on selective pheromone removal that occurs only on the path that is actually chosen for each trip. We prove that the shortest path is the only stable equilibrium for EigenAnt, which means that it is maintained for arbitrary initial pheromone concentrations on paths, and even when path lengths change with time. The EigenAnt algorithm uses only two parameters and does not require them to be finely tuned. Simulations that illustrate these properties are provided.     

Identification of an ant queen pheromone regulating worker sterility

The selective forces that shape and maintain eusocial societies are an enduring puzzle in evolutionary biology. Ordinarily sterile workers can usually reproduce given the right conditions, so the factors regulating reproductive division of labour may provide insight into why eusociality has persisted over evolutionary time. Queen-produced pheromones that affect worker reproduction have been implicated in diverse taxa, including ants, termites, wasps and possibly mole rats, but to date have only been definitively identified in the honeybee. Using the black garden ant Lasius niger, we isolate the first sterility-regulating ant queen pheromone. The pheromone is a cuticular hydrocarbon that comprises the majority of the chemical profile of queens and their eggs, and also affects worker behaviour, by reducing aggression towards objects bearing the pheromone. We further show that the pheromone elicits a strong response in worker antennae and that its production by queens is selectively reduced following an immune challenge. These results suggest that the pheromone has a central role in colony organization and support the hypothesis that worker sterility represents altruistic self-restraint in response to an honest quality signal.