Adaptive approach heuristics for the generalized assignment problem

The Generalized Assignment Problem consists in assigning a setof tasks to a set of agents with minimum cost. Each agent hasa limited amount of a single resource and each task must beassigned to one and only one agent, requiring a certain amountof the resource of the agent. We present new metaheuristics forthe generalized assignment problem based on hybrid approaches.One metaheuristic is a MAX-MIN Ant System (MMAS), an improvedversion of the Ant System, which was recently proposed byStutzle and Hoos to combinatorial optimization problems, and itcan be seen has an adaptive sampling algorithm that takes inconsideration the experience gathered in earlier iterations ofthe algorithm. Moreover, the latter heuristic is combined withlocal search and tabu search heuristics to improve the search.A greedy randomized adaptive search heuristic (GRASP) is alsoproposed. Several neighborhoods are studied, including one basedon ejection chains that produces good moves withoutincreasing the computational effort. We present computationalresults of the comparative performance, followed by concludingremarks and ideas on future research in generalized assignmentrelated problems.

A new species of the fungus-farming ant genus Mycetagroicus Brandão & Mayhé-Nunes (Hymenoptera, Formicidae, Attini)

The fungus-farming ant genus Mycetagroicus Brandão & Mayhé-Nunes was proposed based on three species from the Brazilian "Cerrado": M. cerradensis, M. triangularis and M. urbanus. Here we describe a new species of Attini ant of the genus Mycetagroicus, M. inflatus n. sp., based on two workers collected in eastern Pará State, Brazil. A new key for species identification, comments on differences among species and new geographical distribution data are furnished.

Nestmate recognition and the genetic relatedness of nests in the ant Formica pratensis

Genetic relatedness of the mound-building ant Formica pratensis was determined by means of microsatellite DNA polymorphism, and its impact on nestmate recognition was tested in a population in Southern Sweden (Oeland). Recognition between nests was measured by testing aggression levels between single pairs of workers. The genetic distances of nests (Nei's genetic distance) and the spatial distance of nests were correlated and both showed a strong relation to the aggression behavior. Multiple regression analysis revealed a stronger impact of genetic relatedness rather than spatial distances on aggression behavior. Neighbouring nests were more closely related than distant nests, which may reflect budding as a possible spreading mechanism. The genetic distance data showed that nestmate recognition was strongly genetically influenced in F. pratensis.

Dynamics and genetic structure of Argentine ant supercolonies in their native range.

Some introduced ant populations have an extraordinary social organization, called unicoloniality, whereby individuals mix freely within large supercolonies. We investigated whether this mode of social organization also exists in native populations of the Argentine ant Linepithema humile. Behavioral analyses revealed the presence of 11 supercolonies (width 1 to 515 m) over a 3-km transect. As in the introduced range, there was always strong aggression between but never within supercolonies. The genetic data were in perfect agreement with the behavioral tests, all nests being assigned to identical supercolonies with the different methods. There was strong genetic differentiation between supercolonies but no genetic differentiation among nests within supercolonies. We never found more than a single mitochondrial haplotype per supercolony, further supporting the view that supercolonies are closed breeding units. Genetic and chemical distances between supercolonies were positively correlated, but there were no other significant associations between geographic, genetic, chemical, and behavioral distances. A comparison of supercolonies sampled in 1999 and 2005 revealed a very high turnover, with about one-third of the supercolonies being replaced yearly. This dynamic is likely to involve strong competition between supercolonies and thus act as a potent selective force maintaining unicoloniality over evolutionary time.

Rediscovery of the putatively extinct ant species Simopelta minima (Brandão) (Hymenoptera, Formicidae), with a discussion on rarity and conservation status of ant species

Simopelta minima (Brandão, 1989) was originally described based on four workers collected in soil samples from a small cocoa plantation in Ilhéus, state of Bahia, northeastern Brazil. In the subsequent years after the description, this cocoa plantation was eliminated and the species was then considered extinct by the Brazilian environmental institutions. The recent rediscovery of S. minima workers in subterranean pitfall trap samples from Viçosa, state of Minas Gerais, southeastern Brazil, over 1.000 km distant from type locality, suggests that the rarity and vulnerability status of some ant species may be explained by insufficient sampling of adequate microhabitats, in time and space.

On the efficiency and sensitivity of a pyramidal classification algorithm

In this paper we propose a Pyramidal Classification Algorithm,which together with an appropriate aggregation index producesan indexed pseudo-hierarchy (in the strict sense) withoutinversions nor crossings. The computer implementation of thealgorithm makes it possible to carry out some simulation testsby Monte Carlo methods in order to study the efficiency andsensitivity of the pyramidal methods of the Maximum, Minimumand UPGMA. The results shown in this paper may help to choosebetween the three classification methods proposed, in order toobtain the classification that best fits the original structureof the population, provided we have an a priori informationconcerning this structure.

The genome of the fire ant Solenopsis invicta.

Ants have evolved very complex societies and are key ecosystem members. Some ants, such as the fire ant Solenopsis invicta, are also major pests. Here, we present a draft genome of S. invicta, assembled from Roche 454 and Illumina sequencing reads obtained from a focal haploid male and his brothers. We used comparative genomic methods to obtain insight into the unique features of the S. invicta genome. For example, we found that this genome harbors four adjacent copies of vitellogenin. A phylogenetic analysis revealed that an ancestral vitellogenin gene first underwent a duplication that was followed by possibly independent duplications of each of the daughter vitellogenins. The vitellogenin genes have undergone subfunctionalization with queen- and worker-specific expression, possibly reflecting differential selection acting on the queen and worker castes. Additionally, we identified more than 400 putative olfactory receptors of which at least 297 are intact. This represents the largest repertoire reported so far in insects. S. invicta also harbors an expansion of a specific family of lipid-processing genes, two putative orthologs to the transformer/feminizer sex differentiation gene, a functional DNA methylation system, and a single putative telomerase ortholog. EST data indicate that this S. invicta telomerase ortholog has at least four spliceforms that differ in their use of two sets of mutually exclusive exons. Some of these and other unique aspects of the fire ant genome are likely linked to the complex social behavior of this species.

A simple randomized algorithm for consistent sequential prediction of ergodic time series

We present a simple randomized procedure for the prediction of a binary sequence. The algorithm uses ideas from recent developments of the theory of the prediction of individual sequences. We show that if thesequence is a realization of a stationary and ergodic random process then the average number of mistakes converges, almost surely, to that of the optimum, given by the Bayes predictor.

Nest structure and occurrence of three species of Azteca (Hymenoptera, Formicidae) in Cecropia pachystachya (Urticaceae) in non-floodable and floodable pantanal areas

Thirty Cecropia pachystachya trees were examined in non-floodable and floodable areas to investigate the association between C. pachystachya and Azteca ants in the Pantanal of Mato Grosso do Sul, Brazil. The species Azteca ovaticeps, Azteca isthmica, and Azteca alfari were found nesting inside domatia of C. pachystachya. A. ovaticeps was the most frequent species in the trees in the floodable area, while A. isthmica and A. alfari, in the non-floodable area. A. ovaticeps and A. isthmica maintained more entrance/exit holes in comparison to A. alfari. All Azteca species maintained entrance/exit holes in the closest domatia to the apical area of the branch, due to proximity to Müllerian and pearl bodies, suggesting that these species of Azteca were influenced by their environment during evolution and became specialized. All internodal septa of each examined branch were perforated by ants, indicating the branches were inhabited by a single colony.

Ant fauna (Hymenoptera, Formicidae) associated to arboreal nests of Nasutitermes spp: (Isoptera, Termitidae) in a cacao plantation in southeastern Bahia, Brazil

Ants are among the most common arthropods that colonize termite nests. The aim of this study was to identify the ant fauna associated to termite nests found in a cacao plantation in the county of Ilhéus, Bahia, Brazil, with emphasis on the fauna that uses the nests as foraging and/or nesting environment. For this purpose, 34 active, decadent and abandoned nests of Nasutitermes corniger, N. ephratae and Nasutitermes sp., with different volumes and degrees of activity, were dissected. A total of 54 ant species, belonging to 23 genera and five subfamilies, was found in the constructions. The active, decadent and abandoned termite nests presented, respectively, six, eight and 48 ant species. Crematogaster acuta and Ectatomma tuberculatum were the most frequent species in the active and decadent nests, respectively, while the most frequent species in the abandoned nests were Solenopsis pollux, Thaumatomyrmex contumax and Thaumatomyrmex sp. Twenty-six ant species had true colonies within the termitaria. The Formicidae species richness in the nests was inversely related to the degree of termite activity in the nests. The occurrence of living, decadent or abandoned termitaria of Nasutitermes spp. in cacao plantations foments the heterogeneity of habitats available in the plantations and favors the maintenance of high diversity of organisms that use obligatory or opportunistically this substrate.

Epigean ant communities in Atlantic Forest remnants of São Paulo: a comparative study using the guild concept

Epigean ant communities in Atlantic Forest remnants of São Paulo: a comparative study using the guild concept. The guilds constitute a valuable ecological tool, because they allow conducting comparisons among environments under different conditions. The ants can be used as ecological indicators, mainly for the monitoring of degraded forest areas. The aim of this research was to study guild organization among the epigeous Formicidae living in Atlantic forest remnants of the State of São Paulo, Brazil. Ant collections were performed in three distinct Atlantic forest biome areas: arboreal littoral vegetation ("restinga") (Cananéia), semideciduous seasonal forest (Piracicaba) and dense ombrophylousforest (Pariquera-Açu). After identification, the ants were grouped into guilds, based on the ecological attributes of behavior and habit, according to the literature. Nine guilds were found; the semideciduous seasonal forest ecosystem presented eight of them, followed by the arboreal sandbank (7) and dense ombrophylous forest (6). The guilds found were: litter omnivorous and scavengers, granivorous species, specialist predators living in litter and soil, litter generalist predators, subterranean mealybug-dependent species, army ants, dominant or subdominants arboreal, that occasionally forage on the ground, soil or litter dominant and fungus-growers, using feces and insect body fragments. The guilds found can be used in the monitoring of the mirmecofauna in the Atlantic Forest biome, supplying insights for further ecological studies.

Colony cycle of the social wasp Mischocyttarus consimilis Zikán (Hymenoptera, Vespidae)

Colony cycle of the social wasp Mischocyttarus consimilis Zikán (Hymenoptera, Vespidae). This study describes some aspects of the colony cycle of the Neotropical social wasp Mischocyttarus consimilis, from data obtained under field conditions. Our results showed that the colony cycle in M. consimilis is annual and asynchronous in relation to the months of the year. The colonies remained active for approximately eight months. Most of the abandonments were associated with natural causes, and were most frequent in the pre-emergence stage. The nests were constructed preferentially in man-made structures, especially in sites protected from direct sunlight and rain. Colony foundation was either by haplometrosis or pleometrosis, being the first form predominant.

Tracking individuals shows spatial fidelity is a key regulator of ant social organization.

Ants live in organized societies with a marked division of labor among workers, but little is known about how this division of labor is generated. We used a tracking system to continuously monitor individually tagged workers in six colonies of the ant Camponotus fellah over 41 days. Network analyses of more than 9 million interactions revealed three distinct groups that differ in behavioral repertoires. Each group represents a functional behavioral unit with workers moving from one group to the next as they age. The rate of interactions was much higher within groups than between groups. The precise information on spatial and temporal distribution of all individuals allowed us to calculate the expected rates of within- and between-group interactions. These values suggest that the network of interaction within colonies is primarily mediated by age-induced changes in the spatial location of workers.

Updated list of ant species (Hymenoptera, Formicidae) recorded in Santa Catarina State, southern Brazil, with a discussion of research advances and priorities

Updated list of ant species (Hymenoptera, Formicidae) recorded in Santa Catarina State, southern Brazil, with a discussion of research advances and priorities. A first working list of ant species registered in Santa Catarina State, southern Brazil was published recently. Since then, many studies with ants have been conducted in the state. With data compiled from published studies and collections in various regions of the state, we present here an updated list of 366 species (and 17 subspecies) in 70 ant genera in Santa Catarina, along with their geographical distribution in the seven state mesoregions. Two hundred and seven species are recorded in the Oeste mesoregion, followed by Vale do Itajaí (175), Grande Florianópolis (150), Norte (60), Sul (41), Meio Oeste (23) and Planalto Serrano (12). The increase in the number of records since 1999 results from the use of recently adopted sampling methods and techniques in regions and ecosystems poorly known before, and from the availability of new tools for the identification of ants. Our study highlights the Meio Oeste, Planalto Serrano, Sul and Norte mesoregions, as well as the deciduous forest, mangrove, grassland and coastal sand dune ecosystems as priority study areas in order to attain a more complete knowledge of the ant fauna in Santa Catarina State.

The genome of the leaf-cutting ant Acromyrmex echinatior suggests key adaptations to advanced social life and fungus farming.

We present a high-quality (>100× depth) Illumina genome sequence of the leaf-cutting ant Acromyrmex echinatior, a model species for symbiosis and reproductive conflict studies. We compare this genome with three previously sequenced genomes of ants from different subfamilies and focus our analyses on aspects of the genome likely to be associated with known evolutionary changes. The first is the specialized fungal diet of A. echinatior, where we find gene loss in the ant's arginine synthesis pathway, loss of detoxification genes, and expansion of a group of peptidase proteins. One of these is a unique ant-derived contribution to the fecal fluid, which otherwise consists of "garden manuring" fungal enzymes that are unaffected by ant digestion. The second is multiple mating of queens and ejaculate competition, which may be associated with a greatly expanded nardilysin-like peptidase gene family. The third is sex determination, where we could identify only a single homolog of the feminizer gene. As other ants and the honeybee have duplications of this gene, we hypothesize that this may partly explain the frequent production of diploid male larvae in A. echinatior. The fourth is the evolution of eusociality, where we find a highly conserved ant-specific profile of neuropeptide genes that may be related to caste determination. These first analyses of the A. echinatior genome indicate that considerable genetic changes are likely to have accompanied the transition from hunter-gathering to agricultural food production 50 million years ago, and the transition from single to multiple queen mating 10 million years ago.