Introductory Chapter: Ant Colony Optimization

1. Introduction

Optimization challenges arise in a wide range of fields and sectors of human activity, where we must discover optimal or near-optimal solutions to specific problems while staying within certain constraints. Optimization issues are essential in both scientific and industrial fields. Timetable scheduling, traveling salesman problems, nurse time supply planning, railway programming, space planning, vehicle routing problems, Group-shop organizing problems, portfolio improvement, and so on are a number of real-world illustrations of optimization opportunities. For this reason, many optimization algorithms are created [1].

Optimization focuses on establishing efficient and reliable computational infrastructures that will be used, among other things, to improve the performance of meta-heuristic techniques dramatically. As a result, numerous heuristic algorithms for identifying speedier near-optimal solutions have been created. Moreover, heuristic algorithms can solve with acceptable quality in a short amount of time [2].

Scientists have devoted a great deal of work to understand the complex social habits of ants, and computer scientists are now learning that these patterns can be exploited to tackle complex combinatorial improvement challenges. Ant colony optimization (ACO), the most successful and generally recognized algorithmic technique based on ant behavior, results from an effort to design algorithms motivated by one element of ant behavior, the capability to locate what computer scientists would term shortest pathways. ACO is a population-based metaheuristic for resolving complex optimization challenges. This method is a probabilistic optimization procedure used to solve computational issues and discover the best path using graphs. Artificial ants in ACO seek software agents for possible answers to a particular improvement issue. The optimization challenge is the challenge of discovering the optimum path on a weighted diagram to use the ACO. The artificial ants (hence referred to as ants) then incrementally create solutions by traveling along the graph. Using the pheromone model, a set of parameters associated with graph components (nodes or edges) whose values are updated at runtime by the ants, the solution construction process is skewed in one direction [3].

ACO is a well-known bio-inspired combinatorial optimization approach. Marco Dorigo proposed ACO in his Ph.D. thesis in the early 1990s to solve the optimal path issue in a graph [4]. It was first used to resolve the well-known dilemma of the traveling salesman, and it has since become widely used. After that, it’s used to solve various complex optimization problems of several types. A great deal of time has been spent studying the complex social habits of ants, and computer scientists are now discovering that similar patterns can be exploited to solve complex combinatorial optimization problems, which represents a significant advance in the field. Each cycle begins with a departure from the nest, searching for a food source, and ends with a return to the nest. Each ant leaves a chemical known as pheromone on the path they walk during the journey. The pheromone concentration on each path is determined by the path’s length and the quality of the accessible food supply. Because the concentration of pheromones present on a path affects ant selection, the higher the pheromone concentration, the more likely it is that ants will select the path. Using pheromone concentration and some heuristic value, such as the objective function value, each ant chooses a path in a probabilistic manner based on their environment [5].

Consider the following illustration. Let us consider the following scenario: there are two options for obtaining food from the colony. At first, there is no pheromone to be found on the ground. Consequently, the probability of choosing either of these two paths is equal, or 50 percent. For example, consider two ants who decide two alternative routes to obtain food, each with a fifty-fifty chance of success (see Figure 1(a)).

Figure 1.

Ant Colony optimization – A simple schematic view (a to f) [6].

A significant amount of distance separates these two routes. Therefore, the ant who takes the shortest path to the food will be the first to reach it (see Figure 1(b)).

It returns to the colony after locating food and carrying some food with it. It leaves pheromone on the ground as it follows the returning path. The ant that takes the shortest route will arrive at the colony first (see Figure 1(c)).

As soon as the third ant decides to go out in search of food, it will choose the path that will take it the shortest distance, determined by the level of pheromones on the ground. A shorter road contains more pheromones than a longer path (see Figure 1(d)). The third ant will choose the shorter path because it is more convenient.

Upon returning to the colony, it was discovered that more ants had already traveled the path with higher pheromone levels than the ant who had taken the longer route. Therefore, when another ant tries to reach the colony’s goal (food), it will discover that each trail has the same level of pheromones as the previous one. As a result, it selects one at random from the list. Figure 1(e) depicts an example of the option described above.

After several repetitions of this process, the shorter path has a higher pheromone level than the others and is more likely to be followed by the animal. As a result, all ants will take the shorter route the next time (see Figure 1(f)).

An ACO is based on the technique known as Swarm Intelligence, which is a component of Artificial Intelligence (AI) methodologies for solving technical problems in the industrial sector [7].

2. Swarm intelligence

Amorphous computing comprises a large number of interconnected computers with low processing power, memory, and intercommunication modules. Amorphous computing is also referred to as distributed computing. Swarms are the collective name for these collections of electronic devices. When the individual agents interact locally, the computer’s desired coherent global behavior results from the computer’s local interactions. Although there are only a small number of misbehaving agents, and the environment is noisy and threatening, the global behavior of these enormous numbers of faulty agents is long-lasting. Therefore, randomness, repulsion, and unpredictability among agents can be used to derive Swarm Intelligence (SI), which can then be used to generate multiple solutions for a single problem. On the other hand, there are no established criteria for evaluating the performance of SIs [8].

On the other hand, SI is based on simple principles that allow it to solve complex problems with only a few simple agents. An SI feature causes coherent functional global patterns to emerge from the collective behaviors of (unsophisticated) agents interacting with their environment on a local level. SI provides a foundation for investigating collaborative (or dispersed) problem-solving approaches that do not rely on centralized control or an overarching model. SI refers to the natural or artificial behavior of decentralized, self-organized collective systems that operate on their initiative. The concept is commonly used in AI research and development. Since the early 1990s, a significant amount of effort has been expended on the solution of ‘toy’ and real-world problems using algorithms inspired by social insects [9].

Despite the fact that many studies on SI have been presented, there are no standard criteria for evaluating the performance of a SI system. As indexes, fault tolerance and local superiority are proposed. They used simulation to compare two SI systems in terms of these two indexes. There is a pressing need for additional analytical research.

According to the researchers, “continuum models” for swarm behavior should be based on nonlocal interactions found in biology. First, they discovered that when the density dependency of the repulsion term is greater than the density dependency of the attraction term, the swarm has a constant inner density with sharp edges, similar to what is observed in biological examples. Following that, they looked for linear stability at the swarm’s borders [10].

2.1 Swarm intelligence: the fundamental principles

The following are the fundamental principles of swarm intelligence [11]:

1. Self-Organization is based on

   • positive feedback;

   • negative feedback;

   • amplification of fluctuations; and

   • multiple interactions.

2. Stigmergy- Indirect interaction through communication with the environment.

The purpose of this engagement is to provide a comprehensive review of the current state of the art in Swarm Intelligence, with a particular emphasis on the role of stigmergy in distributed problem-solving. The scope of this engagement is broad and includes a variety of topics. However, to proceed, it is necessary to provide working definitions and the essential properties of swarm-capable systems, such as the fact that problem-solving is an emergent property of a system of primary agents. The stigmergy concept states that simple agents can interact with one another over a common channel without a centralized control system. As a result of applying this concept, they are querying individual agents reveals little or nothing about the system’s emergent characteristics [12].

Consequently, simulation is frequently used to understand better the emergent dynamics of stigmergic systems and their interactions. Individual acts in stigmergic systems are frequently selected from a restricted behavioral repertoire in a probabilistic manner. It is the activities of the various agents that cause changes in the environment, for example, the deposit of a volatile chemical known as a pheromone. Other agents are alerted to the presence of this chemical signal, which results in a shift in the probabilistic selection of future actions.

The advantages of a system like this are self-evident. Generally speaking, the activity of a single agent is less important in a system where the actions of several agents are required for a solution to emerge. Stigmaria systems are resilient to the failure of individual agents while also responding exceptionally well to dynamically changing contexts, as demonstrated in the following example. When developing algorithms, they are making the most efficient use of available resources is usually a significant consideration. One other type of stigmaria system, the raid army ant model, uses pheromone-based signaling to forage for food and survive efficiently. Agents in an army ant system establish a forage front covering a large area, resulting in extraordinarily successful food discovery. This model has military value because it could be used to develop a system for searching for land mines, which is a problem that is all too common in some parts of the world and that this model could help solve. This model of military interest is the third stigmaria model of military interest, characterized by flocking or aggregation. Many simple agents can be programmed to travel across an environment filled with obstacles (and potentially dangerous threats) without the need for centralized control or supervision. The agents’ positions and velocities serve as cues to the environment they are operating.

2.2 Swarm intelligence advantages and disadvantages

There are several advantages of swarm Intelligence. In the following, some of them have been mentioned (Table 1) [13].

• Agents are simple, having little memory and behavior.

• Agents are not goal-oriented; rather than planning exhaustively, they respond.

• There is no central repository of information in the system, and control is dispersed.

• Agents are capable of reacting to rapidly changing settings.

• Individual agent failure is permitted, and emergent behavior is resilient to individual failure.

• It is not necessary to communicate with the agents directly.

Adaptable	The colony reacts to both internal and exterior disturbances.
Strong	Even though some individuals fail, tasks get completed.
Scalable	From a handful of individuals to tens of thousands of people
Distributed	In the colony, there is no such thing as a central controller.
Self-Organized	Paths to solutions are emergent rather than predefined

Table 1.

Advantages of swarm intelligence [13].

Swarm intelligence does have some drawbacks. They are as follows (Table 2) [14].

• Individual agent behavior cannot be used to infer collective behavior. This means that watching solitary agents will not always lead to the selection of swarm-defeating behavior. (From an aggressive standpoint, this can be seen as a benefit.)

• Because action selection is stochastic, individual behavior appears to be noise.

• Swarm-based systems are challenging to design. For design, there are essentially no analytical mechanisms.

• Various factors influence the formation (or non-formation) of collective behavior differently.

Behavior	Individual rules are challenging to predict collective behavior.
Knowledge	Interrogate one of the participants; it will not reveal anything about the group’s function.
Sensitivity	Minor modifications in the rules result in a shift in group behavior.
Action	Individual action appears to be random: how can you spot threats?

Table 2.

Disadvantages of swarm intelligence [14].

3. Why is ants’ behavior used for optimization?

What makes ants so fascinating?

• Ants use simple local methods to complete complex jobs.

• Ant’s production exceeds the sum of their actions.

• Ants are experts at finding and exploiting resources.

Which ant mechanism is superior?

• Cooperation and division of labor are two terms that come to mind when discussing cooperation and labor.

• Adaptive job assignment.

• Cultivation stimulates work.

• Pheromones.

4. Applications of ACO

An increasing number of complex combinatorial optimization problems, such as quadratic assignment, fold protein folding, and vehicle routing, have been successfully solved with the aid of ACO algorithms in the past. Dynamic problems with real-world variables, stochastic problems, multiple targets, and parallel implementations have all been addressed by derived methods in various settings. It has also been employed to search for near-optimal solutions to the traveling salesman’s problem. It is advantageous to use the ant colony algorithm when the graph changes dynamically because it can be performed continuously and adapt to real-time changes instead of simulated annealing and genetic algorithm techniques. This is relevant in network routing and urban transportation systems, among other areas.

Using ant colony optimization techniques, for example, it has been possible to find nearly optimal solutions to the traveling salesman problem. The Ant system, the world’s first ACO algorithm, was created to solve the traveling salesman problem, which entails finding out which route is the most efficient between a set of locations. Essentially, the method is built around ants, who each embark on one of the numerous roundtrips while also visiting the various towns and cities. The ant decides how to travel from one city to another based on a set of guidelines that are followed at each stage [15]:

• Each city must be visited exactly once.

• A faraway city has a lower likelihood of being chosen (the visibility).

• The more intensive the pheromone trail laid out on the boundary between two cities, the more likely that edge will be chosen.

• If the travel is brief, the ant leaves more pheromones on all of the edges it passes through.

• Pheromone trails dissipate with each iteration.

In terms of applications, one of the hottest topics right now is the use of ACO to solve dynamic, stochastic, multi-objective, uninterrupted, and mixed-variable optimization problems and the development of parallel implementations that can make use of the latest similar technology.

ACO can be used to identify the best solution to various optimization challenges. Here are a few examples:

• Capacitated vehicle routing problem

• Permutation flow shop problem

• The issue of stochastic vehicle routing

• There is a problem with the vehicle routing for both pick-up and delivery

• Group-shop scheduling problem

• Traveling salesman problem

• The scheduling of nursing time is a complex problem

• Frequency assignment challenge

• Redundancy allocation problem

The application of ACO in different industries is growing very fast. In the near future, many newly developed ACP-based applications will be used in industries to improve the operational process.

5. Future of ACO

From this overview, it should be evident that the ACO metaheuristic is a robust foundation for tackling complicated combinatorial issues. Traveling Salesman Problem (TSP), Dynamic Traveling Salesman Problem (DTSP), Quadratic Assignment Problem (QAP), and other optimization challenges are particularly well suited to Ant Systems (AS). Compared to different powerful approaches, their superiority is undeniable, and the time savings (produced tours) paired with a high level of optimality cannot be overlooked in this context.

Ant System has a competitive advantage over highly communicative multi-agent systems thanks to reinforcement learning and greedy searching concepts. Simultaneously, the capacity to self-train fast enables light and agile installations. Finally, by separating individual swarm agents from one another, AS can process massive data volumes with far less waste than competing algorithms.

ACO is a new area that combines straightforward functions with profound conceptualizations. There’s not much doubt that further research will yield exciting results that could provide answers to currently unsolvable combinatorial problems in the future. Alternatively, AS and ACO have been shown to be effective in various TSP permutations.

New research can provide better solutions by increasing effectiveness while decreasing restrictions by studying the ACO and PSO to make future improvements. More options for dynamically determining the optimal destination can be developed through ACO. For example, a plan to equip PSO with fitness sharing technology is being tested to see if it can help improve performance. In the future, rather than relying solely on the current iteration, each individual’s velocity will be updated by combining the best elements from all previous iterations.