Optimisation in a natural system: Argentine ants solve the Towers of Hanoi

Routing telephone calls through busy networks while minimising connection time, constructing complex machinery while keeping costs and build-time low, and finding the most efficient set-down and pick-up routes for delivery vehicles are all examples of combinatorial optimisation problems (Gonzalez and Sahni, 1976; Alon and Srinivasan, 1997; Bell and McMullen, 2004). These problems become increasingly difficult to solve as the size of the problem increases. In many cases, the difficulty of the problem increases exponentially with the number of components in the system. In the worst case these problems are ‘NP-hard’ (‘non-deterministic polynomial-time hard’), so that there is no known algorithm for solving general instances of the problem within a reasonable time frame. As a result, programmers must exploit ‘heuristic’ algorithms that find near-optimal solutions in a reasonable time.

Natural systems have proved to be a rich source of inspiration for computer scientists in designing optimisation algorithms (Bonabeau et al., 2000; Vassiliadis and Dounias, 2009). Many biological systems have been refined through millions of years of natural selection to efficiently exploit the ephemeral, often fiercely contested and spatially isolated resources of their environment. Such systems often hinge upon the construction of efficient transportation networks connecting the resources. Such networks have been studied at all levels of biological organisation: colonies of ants (Dussutour et al., 2004; Buhl et al., 2009) and termites (Perna et al., 2008), fungal mycelia (Bebber et al., 2007), acellular slime mould (Nakagaki et al., 2000; Nakagaki et al., 2001; Nakagaki et al., 2004; Latty and Beekman, 2009; Tero et al., 2010) and even the vasculature of plants and animals (Banavar et al., 1999; West et al., 1999). These complex systems are constructed in the absence of any central control by many individual autonomous components possessing only local information. It is this ‘swarm intelligence’ (Bonabeau et al., 1999) that has been widely used in a variety of computing techniques.

Probably the best-known nature-inspired algorithm used for NP-hard problems is Ant Colony Optimisation (ACO) (Dorigo and Stützle, 2004). ACO was inspired by the foraging behaviour of trail-laying ants (Dorigo et al., 1996). Many ant species construct foraging networks by laying pheromone trails towards food sources (Hölldobler and Wilson, 1990). Scouts deposit pheromones linking a newly discovered food source to the nest. The presence of the pheromone recruits nestmates to follow the trail, laying their own pheromone in turn and leading to a process of amplification. In addition, the trail pheromone is volatile and gradually evaporates, thus requiring constant reinforcement. As a result, longer trails are less competitive and eventually only shorter trails will be selected (Goss et al., 1989; Beckers et al., 1990). The ACO method for solving shortest path problems deploys virtual ‘ants’ to explore all possible routes, depositing pheromone on each edge they travel. The amount of pheromone is inversely proportional to the length of the tour, so that shorter tours receive the most pheromone. Evaporation of pheromone after each tour and many reiterations of the process means eventually only the shortest tour remains, or one close to it (Dorigo et al., 1996). The ant-based system has since been widely adopted for use in other combinatorial optimisation problems (Liang and Smith, 2004; Akay and Toksari, 2009; Zhang et al., 2009).

Although ACO and other nature-inspired algorithms often prove competitive in solving specific optimisation problems, apart from the original studies on binary choice shortest path problems there has been surprisingly little work on how real ants solve combinatorial optimisation problems. Notable exceptions are the studies of Vittori et al. (Vittori et al., 2006) and Garnier et al. (Garnier et al., 2009), which examined how ants used the branching angles in shortest-path mazes to decide which path to take. They showed that Argentine ants use the polarity of their trail network to determine whether the path leads towards or away from the nest. Unfed foragers have a high tendency to make a U-turn when they encounter an asymmetrical bifurcation, whereas fed foragers will tend to make a U-turn when they confront a symmetrical bifurcation (Gerbier et al., 2008).

However, these studies did not provide the ants with a difficult optimisation problem. Moreover, little work has focused on how ants solve dynamic problems, that is, those that change over time. The problem of finding the shortest path to food in situations in which the food changes position or paths become blocked and reopened has been faced by ant colonies for millions of years. Understanding how the ants solve such dynamic problems could prove a fruitful source of new inspiration for ACO and other computing methods.

The current convention remains that many mass-recruiting ant species are unable to adapt to dynamic changes, such as exploiting a newly discovered superior food source when an inferior one is currently being used. The apparent inability of the ants to adapt to changing conditions is supported by laboratory experiments (Goss et al., 1989; Beckers et al., 1992; Traniello et al., 1995) and mathematical models (Goss et al., 1989; Nicolis and Deneubourg, 1999; Camazine et al., 2001). However, more recent studies also suggest that trail-laying ants are better able to adjust their foraging efforts than previously assumed (Dussutour et al., 2009a; Dussutour et al., 2009b). In particular, Dussutour et al. (Dussutour et al., 2009b) argue that allowing the ants to first explore an environment before food is placed within it improves their ability to react to changes in the position of the food.

Here, we use the ‘Towers of Hanoi’ to examine how ants construct a solution to a dynamic optimisation problem. In the Towers of Hanoi, N discs of different diameters are stacked upon one of three pegs in order of decreasing diameter from the base. The problem is solved optimally when the stack of discs is transferred to one of the remaining two pegs using the smallest number of possible moves while obeying the following rules: only one disc can be moved at a time; only the top disc in a stack can be moved; and a disc can never be stacked upon another of smaller diameter. The optimal solution to this version of the problem is a simple recursive algorithm requiring exactly 2^N-1 moves (Buneman and Levy, 1980). However, with the addition of extra discs and a single extra peg, the problem becomes NP-hard (Korf and Felner, 2007). We used the three-disc, three-rod version of the Towers of Hanoi problem to test the optimisation abilities of Argentine ants (Linepithema humile Mayr). We chose this version of the problem because the set of possible moves and configurations forms an undirected graph that can easily be transformed into a maze with a clear entry point (the nest) and goal (the food) when linked to its mirror image [see Fig. 1A, adapted from Romik (Romik, 2006), and 1B]. We could thus translate the Towers of Hanoi problem into a shortest-path problem. Our maze contains 32,768 possible paths from one end to the other without turning an ant back to directly face the origin of travel. The two shortest paths are along the outside edges of the maze (Fig. 1B). We tested the ants' ability to adapt to changing conditions by obstructing the most-used shortest path(s) once a solution had been constructed by the ants. As the presence of ‘exploration’ pheromone (pheromone deposited while the ants explore their environment in the absence of food) might help a colony to better forage dynamically (Dussutour et al., 2009b), we conducted trials both in the presence and absence of exploration pheromone. Lastly, we tested the effect of colony size, as the number of ants is known to affect the ability of a colony to form pheromone trails (Beekman et al., 2001).

We used Argentine ants collected from the grounds of the University of Sydney, New South Wales, Australia. We housed colonies in plastic boxes with sides coated with Fluon to prevent escape. Each box contained up to 20 cardboard-wrapped test tubes partially filled with water and a cotton wool plug. We fed the colonies with a vitamin-enriched diet (Bhatkar and Whitcomb, 1970) twice per week, supplemented with mealworms.

All experiments were performed in a temperature-controlled room with diffuse overhead lighting and with colonies of different ages. Experiments were run from May 2009 until March 2010. The mazes were uncovered to prevent pheromone saturation. At the end of each experiment, the mazes were sprayed with ethanol (90%) and washed in bleach (80%) to remove any trace of pheromone. The experimental setup was surrounded by white walls to avoid any disturbance and to prevent the ants from using visual cues to navigate.

We starved 30 colonies containing 500 workers and one queen, and 30 colonies containing 1000 workers and two queens for 3 days before each experiment. Each colony contained varied numbers of brood and males. To determine the effect of the presence of exploration pheromone on the ability of the ants to solve the Towers of Hanoi, half of the 500 and 1000 ant colonies (15 each) were given access to the experimental arena for at least two hours prior to the start of a trial. These were our pre-exposure trials.

We used a Perspex maze 1 m in length consisting of 64 identical hexagons aligned in a rhomboid array (Fig. 3). The underside of the maze and the stilts it was mounted upon were coated in Fluon to ensure the ants could only walk on the upper side of the maze. Each bifurcation within the maze was made symmetrical when coming from the nest, and asymmetrical when returning from the food source (Vittori et al., 2006; Gerbier et al., 2008; Garnier et al., 2009). To convert the maze into the undirected graph of the Towers of Hanoi problem, several paths were blocked off with a perpendicular wall of Fluon-coated plastic (Fig. 1B).

Ants were given access to the maze via a wooden skewer that was placed in the nest and rested against the inner side of the first bifurcation. We placed a food source (wax insect feeder containing 2 mol l^–1 sucrose solution) at the distal end of the maze at the beginning of each experiment and recorded the construction of trails as described below for 1 h. After 1 h, we blocked off the connecting bridge that was most used by the ants using Fluon-coated plastic walls. This configuration is hereafter referred to as ‘Towers of Hanoi’ and is presented in Fig. 2A. We again recorded the construction of trails for 1 h, this time to determine how capable the ants were of constructing an alternative solution after the maze had been changed. This was performed for all 30 trials.

We alternated the order in which we tested the different treatments (with and without pre-exposure, 500 and 1000 ants). We also alternated which side of the maze contained the nest and the food source.

To determine whether Argentine ants have an intrinsic bias when constructing solutions through a maze, we also performed experiments using an open 64-hexagon maze (referred to as ‘open maze’ hereafter, Fig. 3). Twelve colonies of 1000 workers and two queens were starved for 3 days without access to the maze. After 3 days, we placed food at the distal end of the maze and recorded the construction of trails for each of the 12 colonies for 1 h.

As ants in an open maze appeared to prefer constructing trails along the outside edges of the maze (which corresponds to the optimal solution to the Towers of Hanoi maze), we performed a variation on the Towers of Hanoi maze. As before, we allowed the ants to construct a solution for 1 h using the Towers of Hanoi maze. After 1 h, we blocked off the two connecting bridges and opened a new bridge (central bridge) in the middle of the maze. Thus, in this version of the maze, the ants needed to construct a solution that did not follow the outside edges. This version is hereafter referred to as ‘Modified Towers of Hanoi’ (Fig. 2B). We used 24 colonies of 1000 workers and two queens. All colonies were starved for 3 days prior to the experiments, with half of the colonies (12) having access to the maze to lay exploration pheromone. These were our pre-exposure trials.

Because we found an effect of exploration pheromone on the networks that the ants constructed, we next compared the behaviour of individual ants in the presence and absence of exploration pheromone. We starved approximately 100 ants for 3 days in a separate queenless colony. We then placed a single worker from this colony on either the proximal or distal end of an open maze using a wooden skewer. Because we needed a smaller field of view in order to perform our analyses of individual behaviour, we used a truncated maze; the area available to the ant did not exceed 42 cm along the outside edge of the maze. We collected data as described below for 8 min, after which time the ant was removed and another placed on the opposite end of the maze to ensure the pheromone laid by the first individual did not interfere with the behaviour of the second. This was repeated until 15 ants had been tested. The entire maze was washed with ethanol (90%) and bleach (80%) to remove any pheromone after the testing of each pair of ants. To obtain a maze coated in exploration pheromone, the maze was offered to a colony of 500 workers and one queen for at least 2 h over the starvation period, and just prior to testing. The same colony was used to mark the mazes in these pre-exposure trials. We then tested 15 ants as described above. In the treatment with exploration pheromone, we did not place consecutive ants on opposite ends of the maze, but used a new maze after every 3 ants tested. This was done to prevent excessive evaporation of the pheromone over repeated experiments, as the mean lifetime of L. humile pheromone has been shown to be approximately 30 min (Deneubourg et al., 1990).

We collected still images of the entire maze every 10 s with a Logitech 9000 webcam mounted 1 m above the maze. Images were collected for 1 h after adding the food source. After blocking the connecting bridge used by the ants we collected another hour of data. If both connecting bridges were used, we blocked one.

In order to easily visualise the trail networks, we condensed the collected images into 10 min overlays (each consisting of 60 images). We defined a trail as any continuous (i.e. no break in the dark area exceeded six pixels) procession of dark pixelation between the nest and food source. Pilot studies showed that this criterion allows us to distinguish between established trails and individual ants displayed in successive images in the overlay.

At each time point of 10 min, we calculated the proportion of all colonies with definable trails (refer to the n values in Figs 4, 6) that had at least one minimal solution. We also determined the total length of the trail network for each period of 10 min by summing the lengths (cm) of all segments containing a trail between nest and food source. Dead-end branches of trails that connected the nest and food source were included in the analysis and the dead-end segments counted twice to reflect that ants must turn back to continue on to the nest/food source. The number of times the ants constructed trails along the minimal path(s) of each maze was also counted. The final analysis involved counting the number of ‘corrective moves’ employed in the trail network. These are any moves between nodes in a direction perpendicular to the long axis of the maze. For example, moving between the node ‘cbc’ and the node ‘abc’ in the bottom right of Fig. 1A involves one corrective move, moving between ‘aac‘ and ‘ccc’ involves three corrective moves, and so on. Further examples are given in Fig. 2B. Any sub-optimal solution to the problem will thus contain at least one corrective move, the number of which will scale directly with the divergence from the optimal solution. We calculated the mean total network length (cm), the mean number of minimal paths and the mean number of corrective moves across all replicates for each 10 min period. Each metric was graphed over the 12 time points of the experiments (six time points before one trail was blocked and six afterwards). The first and second hour of the experiments were treated separately in the analyses. We used the Shapiro–Wilk test for normality, which showed none of the data to be sufficiently normal. Hence, we applied a Poisson transformation to the data [x′=√(x+0.5)] and then performed three-way ANOVA with repeated measures. The factors were colony size (500/1000), pre-exposure (with/without), and time as the repeated measure. We also compared the partial eta squared (η²_p) values to compare the size of effect of each factor (colony size and pre-exposure).

For the Modified Towers of Hanoi, we performed two-way ANOVA on Poisson-transformed data with factors colony size (500/1000) and time as the repeated measure. In addition, in analysing the number of minimal path solutions, all observed combinations of minimal paths were scored. For example, where one minimal path linked the nest and the central bridge, and two minimal paths linked the central bridge and the food source, two minimal paths were scored, as this was the number of minimal paths available to any individual.

We recorded video at 10 frames per second with a Logitech 9000 webcam placed 30 cm above the section of the maze that the ant was allowed to explore. We omitted the first minute of data – just after the focal ant had been introduced to the maze – from the analysis. The remaining 7 min of video were analysed using the open source machine-vision program ‘Ctrax’ (Branson et al., 2009). For each frame, the body axis and movement direction of the ant was used to calculate its orientation, and to generate 4200 data points for velocity, acceleration and turning speed for each ant. We then determined an average of each measure for each ant, and calculated a mean for each treatment group of 15 replicates. These means were compared via one-way ANOVA.

All ant colonies tested succeeded in solving the Towers of Hanoi in the sense that they all constructed a trail between the nest and the food source. More importantly, 93.3% of the colonies with definable trails in all treatments succeeded in finding a shortest path solution by the end of the first hour, except for the 500, no pre-exposure treatment, of which only 43% found a minimal path (Fig. 4A). When one of the minimal paths was then blocked, 90 to 93.3% of the colonies with exposure were able to find the remaining minimal solution, whereas 73.3 to 78.6% of the colonies without pre-exposure achieved this.

When exploration pheromone was present, definable trails were observed in the first 10 min (Fig. 4B). This was not the case when exploration pheromone was absent (Fig. 4B). Despite the network being longer during the first 10 to 20 min, the final network length after 60 min was shorter in the presence of exploration pheromone than in its absence (F_(1,56)=13.718, P<0.001, η²_p=0.197). Increasing colony size resulted in a longer total network length both in the presence and in the absence of exploration pheromone (F_(1,56)=28.484, P<0.001, η²_p=0.337). The larger η²_p value for colony size indicates that colony size had a greater effect on total network length than exploration pheromone.

During the first hour, the mean number of minimal paths used (Fig. 4C) was significantly lower in colonies of 500 ants with no pre-exposure than in all other treatments. The presence of exploration pheromone had a stronger effect on the number of minimal paths (F_(1,56)=29.060, P<0.001, η²_p=0.342) than did colony size (F_(56,1)=21.758, P<0.001, η²_p=0.280). Pre-exposure had an effect on the quality of the solution constructed, with pre-exposed treatments showing far fewer corrective moves than the others (F_(1,56)=28.965, P<0.001, η²_p=0.341) (Fig. 4D), whereas there was no significant effect of colony size (F_(1,56)=1.703, P=0.197, η²_p=0.030).

After blocking the trail at the connecting bridge (after 60 min), total network length initially either increased slightly or remained stable. This is because the high level of traffic at this stage enabled the ants to build new, definable trails to reconnect the nest and food source over this 10 min period. Ten to 20 minutes after this dynamic change, we saw a gradual pruning of the network (Fig. 4B). Pre-exposure had a larger effect on total network length in the second hour (F_(1,56)=26.674, P<0.001, η²_p=0.323) than did colony size (F_(1,56)=13.200, P=0.001, η²_p=0.191). At the end of the second hour, all treatments reached a plateau between a mean of 0.6 and 1 minimal path (Fig. 4C), with no significant difference between the presence and absence of exploration pheromone (F_(1,56)=1.524, P=0.222, η²_p=0.027) or between colony sizes (F_(1,56)=1.524, P=0.222, η²_p=0.027).

All treatments showed an increase in corrective moves after the blockage, followed by a rapid decrease to very near to the number of corrective moves made before the change (Fig. 4D). Pre-exposure reduced the number of corrective moves required (F_(1,56)=63.578, P<0.001, η²_p=0.532), as did colony size (F_(1,56)=8.219, P=0.006, η²_p=0.006), although this latter effect was far weaker than the former. Interestingly, colonies of 500 ants without pre-exposure required less corrective moves than did unexposed colonies of 1000 ants. This effect might be related to the trails of the 1000 ant colonies being less focused on minimal paths directly before the obstruction.

Ants showed a strong intrinsic bias for forming trails along the outer edges of the open maze. Mean edge proximity score remained close to maximal at all time points (Fig. 5). The ants thus preferentially built trails near or along the outside edges of the open maze.

As in the original Towers of Hanoi experiment, all colonies tested succeeded in producing at least one trail between nest and food source in the Modified Towers of Hanoi. At the end of the first hour, 100% of the pre-exposed and 83.3% of the no exposure colonies used at least one shortest path (Fig. 6A). They were also able to respond to the blockage at the end of the first hour. Over the first 10 min after both connecting bridges were blocked, 25% of the pre-exposure colonies began to use a minimal path, whereas this was seen for 8.3% of the no pre-exposure colonies. By the end of the second hour, 100% of the pre-exposure colonies and 85.7% of the no pre-exposure colonies were using a minimal path.

Unlike in the original Towers of Hanoi experiment, in the initial 10 min of the Modified Towers of Hanoi experiments definable trails were observed for the no exposure treatment. These differences are probably accounted for by the differences in activity levels due to colony age and time of year at which the experiments were conducted. Otherwise the first hour of the Modified Towers of Hanoi experiments showed a similar relationship between the total length of the network and exposure (Fig. 6B). Total network length was lowest in the pre-exposed treatment (F_(1,22)=7.363, P=0.013). We found no significant differences in the second hour between the pre-exposure and no pre-exposure treatments (F_(1,22)=1.478, P=0.237). By the end of the experiment, both treatments converged to a point at or near the minimal network length.

Both the pre-exposure and no pre-exposure treatments showed the same pattern in terms of number of minimal paths used (Fig. 6C), with no significant difference between treatments in either the first (F_(1,22)=3.449, P=0.077) or second (F_(1,22)=1.066, P=0.313) hour. On average, more than one minimal path was used over the first hour, and directly following the dynamic change this number dropped to near zero owing to the blocking of these paths. Over the second hour, both treatments converged to use a mean of just one of the four possible minimal paths.

No significant difference was found between treatments in the mean number of corrective moves (Fig. 6D) for either the first (F_(1,22)=1.219, P=0.281) or second (F_(1,22)=0.945, P=0.342) hour. The number of corrective moves remained constant and low over the first hour, and then increased immediately following the dynamic change. The mean number of corrective moves returned to the original low levels by the end of the experiment.

Ants introduced onto a maze containing exploration pheromone moved significantly faster (Fig. 7A) than did those on a clean maze (10.61 mm s^–1 compared with 8.61 mm s^–1, respectively; F_(1,28)=6.899, P=0.014). Similarly, in the presence of exploration pheromone, acceleration (42.48 mm s^–2 compared with 33.9 mm s^–2; F_(1,28)=9.829, P=0.004; Fig. 7B) and turning speed (1.57 rad s^–1 compared with 1.37 rad s^–1; F_(1,28)=7.643, P=0.010; Fig. 7C) were significantly higher than for ants exploring a clean maze.

Our results show that Argentine ants can find the optimal solution to dynamic shortest path problems. Moreover, the ants had little problem finding an efficient alternative solution when their main trail was obstructed. The open maze experiments showed that the ants displayed a strong bias towards the outside edges. This bias is consistent with ants attempting to explore the full 360 deg radius of the environment. The intrinsic edge bias raised the question of whether the ants really recognise the shortest path, or whether the trail simply converges to the edge of the maze. The Modified Towers of Hanoi was designed to test this, by blocking both connecting bridges and opening a new path through the centre of the maze, thus forcing the ants to overcome their edge preference. Clearly, when the shortest path does not follow the edge, the ants are still able to construct the optimal solution.

Although increasing colony size generally increased the total length of the network, it was exploration pheromone that had the most striking effect on solution efficiency. In almost all cases, the presence of exploration pheromone led to smaller, less convoluted networks, the use of closer to just one minimal path, and fewer corrective moves. Increased solution efficiency can be at least partly attributed to the significantly greater velocity, acceleration and turning speed of individual ants when exploration pheromone was present. A similar effect has been found previously in Lasius niger (Beckers et al., 1992), but never before in L. humile. Strong behavioural evidence for such an exploration pheromone has been found for a similar mass-recruiting ant species, the Big-headed ant Pheidole megacephala (Fabricius). The two-pheromone model built on this experimental evidence suggests that a short-lived foraging pheromone, coupled with a longer-lasting exploration pheromone allows the ants to quickly redistribute their foragers to exploit new resources, even in the presence of a strong foraging trail to where a food source has just been removed (Dussutour et al., 2009b). Gerbier et al. (Gerbier et al., 2008) also found that when exploration pheromone was present ants tended to move more directly towards the food source when unfed, and towards the nest when fed, by continuing to follow their initial direction of travel. Hence, in the presence of exploration pheromone ants appear to use a more direct path both to and from the food source.

The initial response of the ants to blocking their trail was to construct a new trail along the zig-zagging path perpendicular to the long axis of the maze. This can be seen in Fig. 8B, which was taken 30 min after the blockage. This perpendicular path constitutes a large number of corrective moves. In the Towers of Hanoi configuration, the perpendicular path is the shortest path between the blocked area and the open connecting bridge, and hence efficiently redirects traffic. Ultimately, as traffic increases on the remaining minimal path at the expense of the longer, perpendicular path, evaporation of the trail pheromone leads to the extinction of the longer path (Fig. 8C).

The response to the blockage violates a hypothesis of ‘simple’ trail-following behaviour in mass-recruiting ant species. On encountering the blockage, an individual ant is forced to complete a 180 deg turn to continue travel. At this point, both the asymmetry of the bifurcation (Gerbier et al., 2008; Garnier et al., 2009) and the strong, established pheromone trail (Goss et al., 1989; Beckers et al., 1990; Traniello et al., 1995; Nicolis and Deneubourg, 1999; Camazine et al., 2001) might be thought to impel her to retrace her steps directly back along the edge she has just travelled. This was not what we observed. Instead, the ants searched their local area around the now blocked path for a way around the blockage, despite the violation of up to seven bifurcation symmetry ‘preferences’ before the open connecting bridge was reached. This indicates that information provided by the bifurcation asymmetry is ignored by the ants in favour of information from some internal compass (Gerbier et al., 2008) that might provide the ants with a sense of directional intention. For individual foragers to return on a direct path to the nest, despite a tortuous outbound path, would require a compass, as well as an intrinsic odometer (Wittlinger et al., 2006). This ability has yet to be shown in a mass-recruiting species.

The bifurcation asymmetry, suggested by Garnier et al. (Garnier et al., 2009), could play a role in the creation of efficient paths in the modified Towers of Hanoi experiment. Unlike the standard Towers of Hanoi, the modified version does not have an established trail leading away from the new central bridge. Rather trails build up along the perpendicular paths on both sides of the blockage (Fig. 9B). However, rather than being attracted to these new pheromone trails and thus along the path perpendicular to their goals, the ants produce a new minimal path (Fig. 9C). This solution is consistent with the ants ignoring pheromone in favour of continuing in an established direction (i.e. bifurcation asymmetry).

Our study gives us an opportunity to think again what computer scientists and biologists can learn from one another. In many ways the field of Ant Colony Optimisation has moved away from its biological roots, because when applied to real problems the simple pheromone following ants do not solve difficult combinatorial problems (Dorigo and Stützle, 2004). Instead, various pieces of heuristic information are added to the ACO solution scheme in order to better match the solution to the problem in hand. We would raise three important points with respect to better linking experiment and algorithm development. Firstly, we have found that ants are capable of solving dynamic optimisation problems and suggest that it is such problems, rather than static NP-hard problems, that should be the focus of algorithm development. Secondly, our and several previous studies have identified exploration pheromone, laid out in advance of starting the problem-solving exercise, as an important component in reaching good solutions. Finally, as in the addition of heuristic information to ACO schemes, our results suggest that Argentine ants might have more advanced navigational abilities than they are often credited with (Aron et al., 1993). Although in general the link between experiments on ants and ACO is still rather weak, these types of observations show that experiments can continue to provide new inspiration for novel optimisation algorithms and that algorithms can inspire our investigation of biology.

Our experiment was inspired by a suggestion by Dave Broomhead and this article is dedicated to him on the occasion of his 60th birthday. We thank members of the Behaviour and Genetics of Social Insects lab (Sydney) for constructive comments on an earlier version of this manuscript and the anonymous referees for helpful comments and criticisms.

 
• ACO

  ant colony optimisation

 
• NP-hard

  non-deterministic polynomial-time hard

 
• η²_p

  partial eta squared