Section 3 : Simulated annealing, local beam search, and genetic algorithms

Commentary

Section Goals

• To discuss a group of local search algorithms, and explain how they achieve their goals differently than classic search algorithms.
• To apply simulated annealing, local beam search, and genetic algorithms to solve optimization problems.

Learning Objectives

Learning Objective 1

• Explain the mechanism of local search.
• Define the following concepts or terms:
  • Local and global maximum
  • Optimization problems
  • Ridges and Plateaux
  • Stochastic hill climbing
  • Local beam search
  • Gradient descent
  • Simulated annealing
  • Mutation, crossover, and fitness function
  • Population in genetic algorithms
• Analyse and design the algorithm and mechanism of simulated annealing search.
• Describe mutation and crossover processes in genetic algorithms.
• Exemplify how schemas are affected during a Genetic-Algorithm.
• Describe the principles of local search in continuous spaces.

Objective Readings

Required Readings

Reading topics:

Local Search Algorithms, Optimization Problems, and Local Search in Continuous Spaces (see Sections 4.1 - 4.2 of AIMA3ed)

Atkinson-Abutridy, J., Mellish, C., and Aitken, S. (2004). Combining information extraction with genetic algorithms for text mining. IEEE Intelligent Systems, 19(3), 22-30. Digital Object Identifier 10.1109/MIS.2004.4

Hedberg, S. R. (2005). Evolutionary computing: The rise of electronic breeding. IEEE Intelligent Systems, 20(6), 12-15. Digital Object Identifier 10.1109/MIS.2005.104

Note: To speed up access to required papers, direct access information in the form of Digital Object Identifiers (DOI) may be provided along with the papers referenced in the Study Guide. If a link is provided for a paper (e.g., DOI:10.1109/MIS.2008.18), click on it and you will be redirected to the URL of the paper's publication webpage (e.g., https://ieeexplore.ieee.org/document/4475859). If you only have the DOI, simply add it to: https://dx.doi.org/ (e.g., https://dx.doi.org/10.1109/MIS.2008.18) and you will be directed to its publication webpage. To get the full text of the paper through the AU Library, you can first change "." in the URL's domain name part (the string between "//" and the first "/" character) into "-", and add a "0-" prefix and a ".aupac.lib.athabascau.ca" suffix to it as follows: https://0-ieeexplore-ieee-org.aupac.lib.athabascau.ca/document/4475859. When accessing this new link, you will be asked to provide your AU Library login information, and then you will be given full access to the paper.

Objective Questions

• What are the differences between local search and informed search?
• If the path from initial state to goal state is important in a problem, would you use local search to solve the problem?
• Why is hill-climbing also known as "greedy local search"?
• What are the main operators in genetic algorithms?
• What is the relationship between stochastic beam search and genetic algorithm?

Objective Activities

• Summarize the most recent papers on local search from IEEE Transactions on Neural Network, Neural Computing, IEEE Transaction on Evolutionary Computation, and Computational Intelligence, and report your findings through the online conference.
• Explore the following local search algorithms and programs from the textbook's website.
  • Hill-Climbing
  • Simulated-Annealing
  • Genetic-Algorithm
• Complete Exercise 4.1 of AIMA3ed.