table of content

Part 1. Deterministic search algorithms

1 Introduction to search and optimization

1.1 Why care about search and optimization?

1.2 Going from toy problems to the real world

1.3 Basic ingredients of optimization problems

1.3.1 Decision variables

1.3.2 Objective functions

1.3.3 Constraints

1.4 Well-structured problems vs. ill-structured problems

1.4.1 Well-structured problems

1.4.2 Ill-structured problems

1.4.3 WSP, but ISP in practice

1.5 Search algorithms and the search dilemma

Summary

2 A deeper look at search and optimization

2.1 Classifying optimization problems

2.1.1 Number and type of decision variables

2.1.2 Landscape and number of objective functions

2.1.3 Constraints

2.1.4 Linearity of objective functions and constraints

2.1.5 Expected quality and permissible time for the solution

2.2 Classifying search and optimization algorithms

2.3 Heuristics and metaheuristics

2.4 Nature-inspired algorithms

Summary

3 Blind search algorithms

3.1 Introduction to graphs

3.2 Graph search

3.3 Graph traversal algorithms

3.3.1 Breadth-first search

3.3.2 Depth-first search

3.4 Shortest path algorithms

3.4.1 Dijkstra’s search

3.4.2 Uniform-cost search (UCS)

3.4.3 Bidirectional Dijkstra’s search

3.5 Applying blind search to the routing problem

Summary

4 Informed search algorithms

4.1 Introducing informed search

4.2 Minimum spanning tree algorithms

4.3 Shortest path algorithms

4.3.1 Hill climbing algorithm

4.3.2 Beam search algorithm

4.3.3 A* search algorithm

4.3.4 Hierarchical approaches

4.4 Applying informed search to a routing problem

4.4.1 Hill climbing for routing

4.4.2 Beam search for routing

4.4.3 A* for routing

4.4.4 Contraction hierarchies for routing

Summary

Part 2. Trajectory-based algorithms

5 Simulated annealing

5.1 Introducing trajectory-based optimization

5.2 The simulated annealing algorithm

5.2.1 Physical annealing

5.2.2 SA pseudocode

5.2.3 Acceptance probability

5.2.4 The annealing process

5.2.5 Adaptation in SA

5.3 Function optimization

5.4 Solving Sudoku

5.5 Solving TSP

5.6 Solving a delivery semi-truck routing problem

Summary

6 Tabu search

6.1 Local search

6.2 Tabu search algorithm

6.2.1 Memory structure

6.2.2 Aspiration criteria

6.2.3 Adaptation in TS

6.3 Solving constraint satisfaction problems

6.4 Solving continuous problems

6.5 Solving TSP and routing problems

6.6 Assembly line balancing problem

Summary

Part 3. Evolutionary computing algorithms

7 Genetic algorithms

7.1 Population-based metaheuristic algorithms

7.2 Introducing evolutionary computation

7.2.1 A brief recap of biology fundamentals

7.2.2 The theory of evolution

7.2.3 Evolutionary computation

7.3 Genetic algorithm building blocks

7.3.1 Fitness function

7.3.2 Representation schemes

7.3.3 Selection operators

7.3.4 Reproduction operators

7.3.5 Survivor selection

7.4 Implementing genetic algorithms in Python

Summary

8 Genetic algorithm variants

8.1 Gray-coded GA

8.2 Real-valued GA

8.2.1 Crossover methods

8.2.2 Mutation methods

8.3 Permutation-based GA

8.3.1 Crossover methods

8.3.2 Mutation methods

8.4 Multi-objective optimization

8.5 Adaptive GA

8.6 Solving the traveling salesman problem

8.7 PID tuning problem

8.8 Political districting problem

Summary

Part 4. Swarm intelligence algorithms

9 Particle swarm optimization

9.1 Introducing swarm intelligence

9.2 Continuous PSO

9.2.1 Motion equations

9.2.2 Fitness update

9.2.3 Initialization

9.2.4 Neighborhoods

9.3 Binary PSO

9.4 Permutation-based PSO

9.5 Adaptive PSO

9.5.1 Inertia weight

9.5.2 Cognitive and social components

9.6 Solving the traveling salesman problem

9.7 Neural network training using PSO

Summary

10 Other swarm intelligence algorithms to explore

10.1 Nature’s tiny problem-solvers

10.2 ACO metaheuristics

10.3 ACO variants

10.3.1 Simple ACO

10.3.2 Ant system

10.3.3 Ant colony system

10.3.4 Max�min ant system

10.3.5 Solving open TSP with ACO

10.4 From hive to optimization

10.5 Exploring the artificial bee colony algorithm

Summary

Part 5. Machine learning-based methods

11 Supervised and unsupervised learning

11.1 A day in the life of AI-empowered daily routines

11.2 Demystifying machine learning

11.3 Machine learning with graphs

11.3.1 Graph embedding

11.3.2 Attention mechanisms

11.3.3 Pointer networks

11.4 Self-organizing maps

11.5 Machine learning for optimization problems

11.6 Solving function optimization using supervised machine learning

11.7 Solving TSP using supervised graph machine learning

11.8 Solving TSP using unsupervised machine learning

11.9 Finding a convex hull

Summary

12 Reinforcement learning

12.1 Demystifying reinforcement learning

12.1.1 Markov decision process (MDP)

12.1.2 From MDP to reinforcement learning

12.1.3 Model-based vs. model-free RL

12.1.4 Actor-critic methods

12.1.5 Proximal policy optimization

12.1.6 Multi-armed bandit (MAB)

12.2 Optimization with reinforcement learning

12.3 Balancing CartPole using A2C and PPO

12.4 Autonomous coordination in mobile networks using PPO

12.5 Solving the truck selection problem using contextual bandits

12.6 Journey’s end: A final reflection

Summary

Appendixes

Appendix A: Search and optimization libraries in Python

A.1 Setting up the Python environment

A.1.1 Using a Python distribution

A.1.2 Installing Jupyter Notebook and JupyterLab

A.1.3 Cloning the book’s repository

A.2 Mathematical programming solvers

A.2.1 SciPy

A.2.2 PuLP

A.2.3 Other mathematical programming solvers

A.3 Graph and mapping libraries

A.3.1 NetworkX

A.3.2 OSMnx

A.3.3 GeoPandas

A.3.4 contextily

A.3.5 Folium

A.3.6 Other libraries and tools

A.4 Metaheuristics optimization libraries

A.4.1 PySwarms

A.4.2 Scikit-opt

A.4.3 NetworkX

A.4.4 Distributed evolutionary algorithms in Python (DEAP)

A.4.5 OR-Tools

A.4.6 Other libraries

A.5 Machine learning libraries

A.5.1 node2vec

A.5.2 DeepWalk

A.5.3 PyG

A.5.4 OpenAI Gym

A.5.5 Flow

A.5.6 Other libraries

A.6 Projects

Appendix B: Benchmarks and datasets

B.1 Optimization test functions

B.2 Combinatorial optimization benchmark datasets

B.3 Geospatial datasets

B.4 Machine learning datasets

B.5 Data folder

Appendix C: Exercises and solutions

C.1 Chapter 2: A deeper look at search and optimization

C.1.1 Exercises

C.1.2 Solutions

C.2 Chapter 3: Blind search algorithms

C.2.1 Exercises

C.2.2 Solutions

C.3 Chapter 4: Informed search algorithms

C.3.1 Exercises

C.3.2 Solutions

C.4 Chapter 5: Simulated annealing

C.4.1 Exercises

C.4.2 Solutions

C.5 Chapter 6: Tabu search

C.5.1 Exercises

C.5.2 Solutions

C.6 Chapter 7: Genetic algorithm

C.6.1 Exercises

C.6.2 Solutions

C.7 Chapter 8: Genetic algorithm variants

C.7.1 Exercises

C.7.2 Solutions

C.8 Chapter 9: Particle swarm optimization

C.8.1 Exercises

C.8.2 Solutions

C.9 Chapter 10: Other swarm intelligence algorithms to explore

C.9.1 Exercises

C.9.2 Solutions

C.10 Chapter 11: Supervised and unsupervised learning

C.10.1 Exercises

C.10.2 Solutions

C.11 Chapter 12: Reinforcement learning

C.11.1 Exercises

C.11.2 Solutions

Overview

10 Other Swarm Intelligence Algorithms to Explore

This chapter introduces two nature-inspired, swarm intelligence metaheuristics—Ant Colony Optimization (ACO) and Artificial Bee Colony (ABC)—and shows how they harness simple local rules and collective behavior to solve complex optimization problems. It emphasizes the exploration–exploitation balance that underpins these methods, outlines where they shine and where they struggle, and demonstrates how to adapt and tune them for both discrete and continuous search spaces. The discussion is anchored by practical, code-oriented treatments and examples that connect the biological metaphors to implementable optimization strategies.

For ACO, the chapter builds from ant foraging and stigmergic communication: pheromone trails act as a shared memory, evaporation curbs overcommitment, and positive feedback steers the colony toward good paths. The algorithm’s core involves probabilistic transitions driven by pheromone intensity and problem heuristics, plus two complementary pheromone update schemes (online step-by-step and delayed ant-cycle). It then surveys key variants and their purposes: SACO as a baseline; Ant System (AS) with tabu memory; Ant Colony System (ACS) using an elitist, pseudo-random proportional rule that can speed convergence but risks premature focus; and Max–Min Ant System (MMAS), which bounds pheromones, favors iteration-best updates, and uses resets to avoid stagnation. Practical notes address parameter sensitivities (e.g., evaporation extremes), inherent randomness across runs, and applications such as routing, scheduling, and assignment, illustrated with a TSP-style shortest-path example implemented in Python and via an ACO library.

For ABC, the chapter models the roles of employed, onlooker, and scout bees to divide labor between local intensification and global diversification. Recruitment is fitness-proportionate, information sharing emulates the waggle dance, neighborhood moves are generated with a randomized perturbation, and an abandonment limit triggers exploration via scouts. The method is applied to continuous optimization by minimizing the Rosenbrock function, first through a concise Python implementation and then with a ready-to-use library, showing that careful parameter tuning yields near-optimal solutions. Together, ACO and ABC illustrate how adaptive, decentralized search can effectively tackle design, planning, and control problems, while setting the stage for newer machine learning approaches to optimization introduced later in the book.

Ant foregoing process. A forager ant deposits pheromone trails along the path it takes in its way back to the nest. Other ants will likely follow the path with stronger pheromone trail to reach the discovered food source.

a) Binary Bridge Experiment, b) Bridges with Non-equal Length Experiment

Equation 10.1

ACO simulation

Equation 10.2

Effect of evaporation rate during food foraging process. In the simulation, the ants initiate their search for food from the central nest, which is surrounded by three food sources shown as blobs. Pheromone is shown as white trails. Upon discovering a food item, an ant transports it back to the nest while leaving behind a chemical trail. This trail is then followed by other ants that pick up the scent, thereby directing them towards the food source. As more ants continue to retrieve food, they strengthen the chemical trail.

Pheromone update methods

Equation 10.3

Equation 10.4

Equation 10.5

Examples of ACO variants

Shortest path problem

Equation 10.6

First ant at source node 1 with neighbors 2 and 3. There are two numbers on each edge separated by a colon. The first number represents the length of the edge and the second number represents the current pheromone concentration on the edge.

Equation 10.7

Equation 10.8

The path constructed by the first ant. Each of the other 4 ants will construct a path.

Equation 10.9

Updated pheromone concentration.

Equation 10.10

Equation 10.11

Ant at node 4 selects next node (2 or 5) following ACS elitist strategy

Shortest path obtained by ACO

Shortest path obtained by ACOpy

Honey bee’s foraging behavior

Equation 10.12

Equation 10.13

3d surface of Rosenbrock function

Equation 10.14

Equation 10.15

Equation 10.16

Equation 10.17

Rosenbrock function contour and solutions using ABC and ACO algorithms

Summary

Ant Colony Optimization (ACO) is a population-based algorithm inspired by the foraging behavior of ants. Simple ACO (SACO), Ant System (AS), Ant Colony System (ACS) and Max-Min Ant System (MMAS) are examples of ACO meta-heuristics algorithms.
During foraging, ants discover good solutions, which influence the decisions of other ants. Over time, the pheromone trails intensify along the paths of better solutions, attracting more ants to explore those paths. This behavior is called autocatalytic behavior.
Pheromone update includes two phases: evaporation and deposit. During evaporation phase, the pheromone concentration is decreased. Ants can deposit pheromone during the construction of a solution, using the online step-by-step pheromone update method, or after the solution has been built, by revisiting all the states visited during the construction process, using the online delayed pheromone update method. In some cases, both methods can be used together.
Ant System (AS) improves on simple ACO by adding a memory capability by the inclusion of a tabu list.
Ant Colony System (ACS) Algorithm is an extension of the Ant System (AS) Algorithm with a modified transition rule that utilizes an Elitist strategy.
Max-Min Ant System (MMAS) addresses the limitations of Ant System (AS) and Ant Colony System (ACS) by using the iteration-best path for pheromone updates, encouraging exploration, and constraining pheromone values between minimum and maximum values. This approach reduces the risk of premature stagnation and improves performance by balancing exploration and exploitation.
The Artificial Bee Colony (ABC) algorithm is a population-based search algorithm inspired by the foraging behavior of honey bees. ABC algorithm manages the balance between exploration and exploitation through its three types of bees (employed bees, onlooker bees and scout bees), each of which perform different complementary roles.
The inherent randomness in stochastic optimization algorithms due to initial conditions and/or probabilistic decision making process, is not necessarily a bad thing. It can help the algorithm avoid getting stuck in local optima—solutions that are the best in their immediate vicinity but are not the best overall. By occasionally taking less promising paths, the algorithm can explore more of the solution space and has a better chance of finding the global optimum—the best possible solution.

FAQ

What is Ant Colony Optimization (ACO) and how does it work?

ACO is a metaheuristic inspired by real ants’ foraging. A colony of “artificial ants” builds solutions by moving over a problem graph. Each edge has a pheromone value (τ) and a heuristic desirability (η, often 1/distance). Ants choose next steps with probability proportional to τ^α · η^β. After tours are built, pheromones evaporate (rate ρ) and are deposited (amount linked to solution quality), creating positive feedback on good components. Evaporation prevents unlimited reinforcement, maintaining exploration. Over time, the colony converges to high-quality paths (e.g., short routes).

How do pheromone evaporation and deposition affect ACO’s exploration–exploitation balance?

Evaporation (ρ) reduces all trails each iteration, weakening outdated information and encouraging exploration. If ρ = 0, trails never fade, and ants risk getting stuck in early, suboptimal paths. If ρ = 1, trails vanish immediately, forcing pure random exploration and slowing convergence. Deposition reinforces edges used in good solutions, driving exploitation. Tuning ρ and the deposit magnitude Q balances searching new areas and intensifying around promising regions.

What’s the difference between online step-by-step and online delayed pheromone updates?

- Online step-by-step: an ant deposits pheromone while traversing each edge (e.g., ant-density uses a constant Q; ant-quantity uses Q/d_ij to favor shorter edges locally). This biases construction in real time but may amplify early noise. - Online delayed (ant-cycle): after completing a full tour, an ant deposits amount proportional to its tour quality (e.g., Q/L^k) on all edges it used. This leverages global solution quality and reduces premature bias from partial paths. Hybrids are possible.

How do α and β in ACO’s transition rule influence performance?

In the transition rule p(i→j) ∝ τ_ij^α · η_ij^β: - α controls pheromone influence. Larger α accelerates exploitation (but too large risks early convergence to suboptimal routes driven by initial random τ). - β controls heuristic influence (e.g., distance). Larger β favors greedier choices (short edges), helpful early on but can reduce diversity if too high. Typical practice is to start with moderate values and tune empirically for the problem scale.

How does Ant Colony System (ACS) improve on Ant System (AS)?

ACS introduces a pseudo-random proportional rule with a threshold r0: - If r ≤ r0, the ant deterministically picks the best τ·η edge (exploitation). - Otherwise, it samples probabilistically (exploration). ACS also emphasizes reinforcing the global-best solution, which speeds convergence. The trade-off is potential over-exploitation; r0 should be tuned to keep sufficient exploration.

What problem does Max-Min Ant System (MMAS) address, and how?

MMAS combats stagnation (all ants following the same path too early). It: - Updates pheromone using the iteration-best path (often more exploratory) and optionally mixes in global-best occasionally. - Bounds pheromones within [τ_min, τ_max] to prevent any edge from becoming too dominant or too neglected. - Resets all trails to τ_max if stagnation is detected to re-ignite exploration.

How is ACO applied to shortest path/TSP-like problems in practice?

Typical steps: 1) Initialize τ_ij (often equally) and set α, β, ρ, Q, and number of ants. 2) For each iteration, each ant constructs a tour using p(i→j) ∝ τ_ij^α·η_ij^β with tabu memory (visited nodes). 3) Evaporate pheromones, then deposit based on tour quality (e.g., Q/L). 4) Track best-so-far and/or iteration-best tour. Python support: while ACO has fewer mature packages than GA/PSO, ACOpy can solve graph problems, and custom NumPy implementations are common for TSP/shortest path.

What is the Artificial Bee Colony (ABC) algorithm and the roles of employed, onlooker, and scout bees?

ABC models honeybee foraging with three roles: - Employed bees: exploit their current “food source” (solution), doing local search via neighbor generation v = x + φ·(x − x_k) with φ ∈ [−1, 1]. - Onlooker bees: observe employed bees and select sources proportionally to fitness (better sources get more attention), reinforcing exploitation. - Scout bees: replace stagnated sources (no improvement for a “limit” of trials) with random ones, ensuring exploration and avoiding local traps.

How do you use ABC to minimize the Rosenbrock function?

Workflow: 1) Initialize a population of candidate points in the bounded domain. 2) Employed phase: each bee perturbs one dimension using a partner solution; accept if fitness improves; otherwise increase a no-improvement counter. 3) Onlooker phase: select sources with probability ∝ fitness and perform neighborhood search; accept improvements. 4) Scout phase: any source exceeding the trial “limit” is replaced with a random point. 5) Memorize the best-so-far. In practice, solutions approach (1, 1) with near-zero fitness. Libraries: MEALPY provides an OriginalABC implementation.

When should I choose ACO vs ABC, and what are common applications and tips?

- ACO: excels in discrete/combinatorial tasks with graph structure (routing, scheduling, assignment, shortest path/TSP). Use tabu lists, careful ρ/α/β/Q tuning, and MMAS/ACS to mitigate stagnation. - ABC: well-suited for continuous optimization (engineering design, parameter tuning), but can be adapted to discrete forms. Tune colony size, neighbor strength φ, and the limit to balance intensification/diversification. General tips: run multiple trials (stochastic), tune parameters empirically, and consider hybridizing (e.g., iteration-best with occasional global-best) for robustness.

pro $24.99 per month

access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
choose one free eBook per month to keep
exclusive 50% discount on all purchases
renews monthly, pause or cancel renewal anytime

lite $19.99 per month

access to all Manning books, including MEAPs!

team

5, 10 or 20 seats+ for your team - learn more

eBook

pdf, ePub, online

$74.99 $37.49

you save $37.50 (50%)

include audio $24.99 $12.49

pro $24.99 per month

access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
choose one free eBook per month to keep
exclusive 50% discount on all purchases
renews monthly, pause or cancel renewal anytime

lite $19.99 per month

access to all Manning books, including MEAPs!

team

5, 10 or 20 seats+ for your team - learn more

eBook

$74.99 $37.49

you save $37.50 (50%)

include audio $24.99 $12.49

eBook

pdf, ePub, online

$74.99 $37.49

you save $37.50 (50%)

include audio $24.99 $12.49

pro $24.99 per month

access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
choose one free eBook per month to keep
exclusive 50% discount on all purchases
renews monthly, pause or cancel renewal anytime

lite $19.99 per month

access to all Manning books, including MEAPs!

team

5, 10 or 20 seats+ for your team - learn more