An official website of the United States government
Cloud computing is a concept introduced in the information technology era, with the main components being the grid, distributed, and valuable computing. The cloud is being developed continuously and, naturally, comes up with many challenges, one of which is scheduling. A schedule or timeline is a mechanism used to optimize the time for performing a duty or set of duties. A scheduling process is accountable for choosing the best resources for performing a duty. The main goal of a scheduling algorithm is to improve the efficiency and quality of the service while at the same time ensuring the acceptability and effectiveness of the targets. The task scheduling problem is one of the most important NP-hard issues in the cloud domain and, so far, many techniques have been proposed as solutions, including using genetic algorithms (GAs), particle swarm optimization, (PSO), and ant colony optimization (ACO). To address this problem, in this paper one of the collective intelligence algorithms, called the Salp Swarm Algorithm (SSA), has been expanded, improved, and applied. The performance of the proposed algorithm has been compared with that of GAs, PSO, continuous ACO, and the basic SSA. The results show that our algorithm has generally higher performance than the other algorithms. For example, compared to the basic SSA, the proposed method has an average reduction of approximately 21% in makespan.
more »
« less
A Geometry-Sensitive Quorum Sensing Algorithm for the Best-of-N Site Selection Problem
The house hunting behavior of the Temnothorax albipennis ant allows the colony to explore several nest choices and agree on the best one. Their behavior serves as the basis for many bio-inspired swarm models to solve the same problem. However, many of the existing site selection models in both insect colony and swarm literature test the model’s accuracy and decision time only on setups where all potential site choices are equidistant from the swarm’s starting location. These models do not account for the geographic challenges that result from site choices with different geometry. For example, although actual ant colonies are capable of consistently choosing a higher quality, further site instead of a lower quality, closer site, existing models are much less accurate in this scenario. Existing models are also more prone to committing to a low quality site if it is on the path between the agents’ starting site and a higher quality site. We present a new model for the site selection problem and verify via simulation that is able to better handle these geographic challenges. Our results provide insight into the types of challenges site selection models face when distance is taken into account. Our work will allow swarms to be robust to more realistic situations where sites could be distributed in the environment in many different ways.
more »
« less
- Award ID(s):
- 1810758
- PAR ID:
- 10432987
- Date Published:
- Journal Name:
- Thirteenth International Conference on Swarm Intelligence (ANTS 2022)
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract The study of social parasitism faces numerous challenges arising from the intricate and intranidal host–parasite interactions and the rarity of parasites compared to their free-living counterparts. As a result, our understanding of the ecology and evolution of most social parasites remains limited. Using whole-genome and reduced-representation sequence data, we conducted a study to fill knowledge gaps on host use, colony social structure, and population genetics of the facultative dulotic ant Formica aserva Forel. Our study reveals the remarkable ability of F. aserva to exploit at least 20 different host species across its wide geographic distribution. In some cases, one social parasite colony exploits multiple hosts simultaneously, suggesting a high degree of generalization even at a local spatial scale. Approximately 80% of the colonies were monogyne (with a single queen), with many exhibiting higher rates of polyandry compared to most Formica ants. Although we identified a supergene on chromosome 3, its association with colony structure remains uncertain due to the rarity of polygyny in our sample. Population genetic analyses reveal substantial geographic population structure, with the greatest divergence between California populations and those from the rest of the range. Mitochondrial population structure differs from structure inferred from the nuclear genome on a broad geographic scale, suggesting a possible role of adaptive introgression or genetic drift. This study provides valuable insights into the ecology and evolution of F. aserva, underscoring the need for further research to decipher the complexities of host interactions and the genetic mechanisms that regulate social structure.more » « less
-
Imperiale, Michael J. (Ed.)ABSTRACT Within social insect colonies, microbiomes often differ between castes due to their different functional roles and between colony locations. Trachymyrmex septentrionalis fungus-growing ants form colonies throughout the eastern United States and northern Mexico that include workers, female and male alates (unmated reproductive castes), larvae, and pupae. How T. septentrionalis microbiomes vary across this geographic range and between castes is unknown. Our sampling of individual ants from colonies across the eastern United States revealed a conserved T. septentrionalis worker ant microbiome and revealed that worker ant microbiomes are more conserved within colonies than between them. A deeper sampling of individual ants from two colonies that included all available castes (pupae, larvae, workers, and female and male alates), from both before and after adaptation to controlled laboratory conditions, revealed that ant microbiomes from each colony, caste, and rearing condition were typically conserved within but not between each sampling category. Tenericute bacterial symbionts were especially abundant in these ant microbiomes and varied widely in abundance between sampling categories. This study demonstrates how individual insect colonies primarily drive the composition of their microbiomes and shows that these microbiomes are further modified by developmental differences between insect castes and the different environmental conditions experienced by each colony. IMPORTANCE This study investigates microbiome assembly in the fungus-growing ant Trachymyrmex septentrionalis , showing how colony, caste, and lab adaptation influence the microbiome and revealing unique patterns of mollicute symbiont abundance. We find that ant microbiomes differ strongly between colonies but less so within colonies. Microbiomes of different castes and following lab adaptation also differ in a colony-specific manner. This study advances our understanding of the nature of individuality in social insect microbiomes and cautions against the common practice of only sampling a limited number of populations to understand microbiome diversity and function.more » « less
-
We study the problem of distributed task allocation in multi-agent systems e.g. the division of labor in an ant colony or robot swarm. Suppose there is a collection of agents, a collection of tasks, and a demand vector, which specifies the number of agents required to perform each task.The goal of the agents is to collectively allocate themselves to the tasks to satisfy the demand vector. We study the dynamic version of the problem where the demand vector changes overtime. Here, the goal is to minimize the switching cost, which is the number of agents that change tasks in response to a change in the demand vector. The switching cost is an important metric since changing tasks may incur significant overhead.We study a mathematical formalization of the above problem introduced by Su, Su, Dornhaus, and Lynch [21]. We prove the first non-trivial lower bounds for the switching cost.more » « less
-
We study the problem of house-hunting in ant colonies, where ants reach consensus on a new nest and relocate their colony to that nest, from a distributed computing perspective. We propose a house-hunting algorithm that is biologically inspired by Temnothorax ants. Each ant is modeled as a probabilistic agent with limited power, and there is no central control governing the ants. We show an O( log n) lower bound on the running time of our proposed house-hunting algorithm, where n is the number of ants. Furthermore, we show a matching upper bound of expected O( log n) rounds for environments with only one candidate nest for the ants to move to. Our work provides insights into the house-hunting process, giving a perspective on how environmental factors such as nest quality or a quorum rule can affect the emigration process.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1007/978-3-031-20176-9_1
