book

Optimization Algorithms

Name: Optimization Algorithms
Author: Alaa Khamis
ISBN: 9781633438835

by Alaa Khamis

October 2024

Intermediate to advanced

536 pages

20h 56m

English

Manning Publications

Audiobook available

Read now

Unlock full access

Optimization Algorithms
Copyright
dedication
contents
front matter
prefaceacknowledgmentsabout this bookWho should read this book?How this book is organized: A roadmapAbout the codeliveBook discussion forumabout the authorabout the cover illustration
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 world1.3 Basic ingredients of optimization problems1.3.1 Decision variables1.3.2 Objective functions1.3.3 Constraints1.4 Well-structured problems vs. ill-structured problems1.4.1 Well-structured problems1.4.2 Ill-structured problems1.4.3 WSP, but ISP in practice1.5 Search algorithms and the search dilemmaSummary
2 A deeper look at search and optimization
2.1 Classifying optimization problems2.1.1 Number and type of decision variables2.1.2 Landscape and number of objective functions2.1.3 Constraints2.1.4 Linearity of objective functions and constraints2.1.5 Expected quality and permissible time for the solution2.2 Classifying search and optimization algorithms2.3 Heuristics and metaheuristics2.4 Nature-inspired algorithmsSummary
3 Blind search algorithms
3.1 Introduction to graphs3.2 Graph search3.3 Graph traversal algorithms3.3.1 Breadth-first search3.3.2 Depth-first search3.4 Shortest path algorithms3.4.1 Dijkstra’s search3.4.2 Uniform-cost search (UCS)3.4.3 Bidirectional Dijkstra's search3.5 Applying blind search to the routing problemSummary
4 Informed search algorithms
4.1 Introducing informed search4.2 Minimum spanning tree algorithms4.3 Shortest path algorithms4.3.1 Hill climbing algorithm4.3.2 Beam search algorithm4.3.3 A* search algorithm4.3.4 Hierarchical approaches4.4 Applying informed search to a routing problem4.4.1 Hill climbing for routing4.4.2 Beam search for routing4.4.3 A* for routing4.4.4 Contraction hierarchies for routingSummary

Part 2. Trajectory-based algorithms
5 Simulated annealing
5.1 Introducing trajectory-based optimization5.2 The simulated annealing algorithm5.2.1 Physical annealing5.2.2 SA pseudocode5.2.3 Acceptance probability5.2.4 The annealing process5.2.5 Adaptation in SA5.3 Function optimization5.4 Solving Sudoku5.5 Solving TSP5.6 Solving a delivery semi-truck routing problemSummary
6 Tabu search
6.1 Local search6.2 Tabu search algorithm6.2.1 Memory structure6.2.2 Aspiration criteria6.2.3 Adaptation in TS6.3 Solving constraint satisfaction problems6.4 Solving continuous problems6.5 Solving TSP and routing problems6.6 Assembly line balancing problemSummary
Part 3. Evolutionary computing algorithms
7 Genetic algorithms
7.1 Population-based metaheuristic algorithms7.2 Introducing evolutionary computation7.2.1 A brief recap of biology fundamentals7.2.2 The theory of evolution7.2.3 Evolutionary computation7.3 Genetic algorithm building blocks7.3.1 Fitness function7.3.2 Representation schemes7.3.3 Selection operators7.3.4 Reproduction operators7.3.5 Survivor selection7.4 Implementing genetic algorithms in PythonSummary
8 Genetic algorithm variants
8.1 Gray-coded GA8.2 Real-valued GA8.2.1 Crossover methods8.2.2 Mutation methods8.3 Permutation-based GA8.3.1 Crossover methods8.3.2 Mutation methods8.4 Multi-objective optimization8.5 Adaptive GA8.6 Solving the traveling salesman problem8.7 PID tuning problem8.8 Political districting problemSummary
Part 4. Swarm intelligence algorithms
9 Particle swarm optimization
9.1 Introducing swarm intelligence9.2 Continuous PSO9.2.1 Motion equations9.2.2 Fitness update9.2.3 Initialization9.2.4 Neighborhoods9.3 Binary PSO9.4 Permutation-based PSO9.5 Adaptive PSO9.5.1 Inertia weight9.5.2 Cognitive and social components9.6 Solving the traveling salesman problem9.7 Neural network training using PSOSummary
10 Other swarm intelligence algorithms to explore
10.1 Nature’s tiny problem-solvers10.2 ACO metaheuristics10.3 ACO variants10.3.1 Simple ACO10.3.2 Ant system10.3.3 Ant colony system10.3.4 Max–min ant system10.3.5 Solving open TSP with ACO10.4 From hive to optimization10.5 Exploring the artificial bee colony algorithmSummary
Part 5. Machine learning-based methods
11 Supervised and unsupervised learning
11.1 A day in the life of AI-empowered daily routines11.2 Demystifying machine learning11.3 Machine learning with graphs11.3.1 Graph embedding11.3.2 Attention mechanisms11.3.3 Pointer networks11.4 Self-organizing maps11.5 Machine learning for optimization problems11.6 Solving function optimization using supervised machine learning11.7 Solving TSP using supervised graph machine learning11.8 Solving TSP using unsupervised machine learning11.9 Finding a convex hullSummary
12 Reinforcement learning
12.1 Demystifying reinforcement learning12.1.1 Markov decision process (MDP)12.1.2 From MDP to reinforcement learning12.1.3 Model-based vs. model-free RL12.1.4 Actor-critic methods12.1.5 Proximal policy optimization12.1.6 Multi-armed bandit (MAB)12.2 Optimization with reinforcement learning12.3 Balancing CartPole using A2C and PPO12.4 Autonomous coordination in mobile networks using PPO12.5 Solving the truck selection problem using contextual bandits12.6 Journey’s end: A final reflectionSummary
Appendix A. Search and optimization libraries in Python
A.1 Setting up the Python environmentA.1.1 Using a Python distributionA.1.2 Installing Jupyter Notebook and JupyterLabA.1.3 Cloning the book’s repositoryA.2 Mathematical programming solversA.2.1 SciPyA.2.2 PuLPA.2.3 Other mathematical programming solversA.3 Graph and mapping librariesA.3.1 NetworkXA.3.2 OSMnxA.3.3 GeoPandasA.3.4 contextilyA.3.5 FoliumA.3.6 Other libraries and toolsA.4 Metaheuristics optimization librariesA.4.1 PySwarmsA.4.2 Scikit-optA.4.3 NetworkXA.4.4 Distributed evolutionary algorithms in Python (DEAP)A.4.5 OR-ToolsA.4.6 Other librariesA.5 Machine learning librariesA.5.1 node2vecA.5.2 DeepWalkA.5.3 PyGA.5.4 OpenAI GymA.5.5 FlowA.5.6 Other librariesA.6 Projects
Appendix B. Benchmarks and datasets
B.1 Optimization test functionsB.2 Combinatorial optimization benchmark datasetsB.3 Geospatial datasetsB.4 Machine learning datasetsB.5 Data folder
Appendix C. Exercises and solutions
C.1 Chapter 2: A deeper look at search and optimizationC.1.1 ExercisesC.1.2 SolutionsC.2 Chapter 3: Blind search algorithmsC.2.1 ExercisesC.2.2 SolutionsC.3 Chapter 4: Informed search algorithmsC.3.1 ExercisesC.3.2 SolutionsC.4 Chapter 5: Simulated annealingC.4.1 ExercisesC.4.2 SolutionsC.5 Chapter 6: Tabu searchC.5.1 ExercisesC.5.2 SolutionsC.6 Chapter 7: Genetic algorithm
C.6.1 Exercises
C.6.2 SolutionsC.7 Chapter 8: Genetic algorithm variantsC.7.1 ExercisesC.7.2 SolutionsC.8 Chapter 9: Particle swarm optimizationC.8.1 ExercisesC.8.2 SolutionsC.9 Chapter 10: Other swarm intelligence algorithms to explore
C.9.1 Exercises
C.9.2 SolutionsC.10 Chapter 11: Supervised and unsupervised learningC.10.1 ExercisesC.10.2 SolutionsC.11 Chapter 12: Reinforcement learningC.11.1 ExercisesC.11.2 Solutions
references
index

Content preview from Optimization Algorithms

6 Tabu search

This chapter covers

Understanding local search
Understanding how tabu search extends local search
Solving constraint-satisfaction problems
Solving continuous problems
Solving routing problems
Solving assembly line balancing problems

In the previous chapter, you were introduced to trajectory-based metaheuristics, and you learned about simulated annealing (SA) as an example of these metaheuristic algorithms. The actual first use of a metaheuristic is probably Fred Glover’s tabu search (TS) in 1986, although his seminal article on tabu search was published later, in 1997 [1]. The word “tabu” (also spelled “taboo”) originated from the Polynesian languages of the South Pacific. It is a term used to describe something that is prohibited, ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Publisher Resources

ISBN: 9781633438835Publisher Support Publisher Website Errata Page

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Optimization Algorithms

by Alaa Khamis

6 Tabu search

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.