ECE 457A - Co-operative and Adaptive Algorithms

Midterm Info

• Date: Friday, February 27
• Time: 4:30 PM - 6:00 PM

Search Algorithms

• Properties of Search Algorithms
• Uninformed vs. Informed Search

Uninformed Search

• Breadth-First Search
• Depth-First Search
  • BFS vs DFS
• Depth-Limited Search
• Uniform Cost Search
• Iterative Deepening Search
• Comparing Search Strategies
• Avoiding Cycles and Repeated States

Informed Search

• Informed Search
• Heuristic
  • 8-Queens Heuristic Example
  • Admissible Heuristic Design
• Weak vs. Strong Methods
• Best-First Search
• Greedy Best-First Search
• Beam Search
• A Search
• A* Search
• Hill Climbing Search

Game Playing as Search

• Game Playing as Search
• Minimax
  • Minimax Tic-Tac-Toe Example
• Alpha-Beta Pruning

Metaheuristics

• Metaheuristics

Trajectory-based Metaheuristics

• Trajectory Search
  • Trajectory Search Method Comparison
• Greedy descent
• Simulated Annealing
  • Simulated Annealing Examples
  • Cooperative Simulated Annealing
• Tabu Search
  • Adaptive and Cooperative Tabu Search

Population-Based Metaheuristics

• Population-based Algorithms
• Information in Search Algorithms
• Evolutionary Algorithms

Genetic Algorithms

• Genetic Algorithms

• Premature Convergence and Deception for GA

• Simple Genetic Algorithm

• Generational Genetic Algorithm

• Steady-State Genetic Algorithm

• Representation in Binary Genetic Algorithms

• Variation Operators for Binary Genetic Algorithms

  • One-Point Crossover
  • N-Point Crossover
  • Uniform Crossover

• Selection in Genetic Algorithms

• Real-Valued Genetic Algorithms

• Variation Operators in Real-Valued Genetic Algorithms

  • Arithmetic Crossover
  • Blend Crossover
  • Simulated Binary Crossover

• Permutation Genetic Algorithms

• Variation Operators for Permutation Genetic Algorithms

  • Partially Matched Crossover
  • Order Crossover
  • Cycle Crossover
  • Edge Recombination Crossover

Assignments

• 457A Assignment 1