Optimization Algorithms: AI techniques for design, planning, and control problems

Optimization Algorithms
Copyright
dedication
contents
front matter
   preface
   acknowledgments
   about this book
      Who should read this book?
      How this book is organized: A roadmap
      About the code
      liveBook discussion forum
   about the author
   about 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 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
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
references
index