Unit 7: Iterative Improvement Algorithms
In many problems, it is easy to propose some approximate solution to the problem. It may be inadequate or incorrect or correct but sub-optimal. In such cases, algorithms exist to improve a bad solution to arrive at a better solution. These are called iterative improvement algorithms and are very useful for certain problems. In this unit, we will introduce the concepts of iterative improvements and a range of algorithms that can be leveraged to solve problems in this category.
Completing this unit should take you approximately 4 hours.
Upon successful completion of this unit, you will be able to:
- explain the concept of iterative improvement of an incomplete or bad solution to arrive at better solutions;
- apply the principles of iterative improvement to solve constraint satisfaction problems;
- explain the basics of hill-climbing as an iterative improvement algorithm, along with its limitations;
- apply the concepts of simulated annealing to improve hill-climbing search; and
- explain the basics of genetic algorithms to iteratively improve outcomes.
7.1: Using Iterative Improvement to Solve Problems
Now, we will look at the details of the iterative improvement algorithm at a generic level. Constraint satisfaction problems are particularly well-suited to iterative improvement. We will review many sample CSPs and demonstrate the value of iterative improvement to arrive at optimal solutions.
7.2: Improving Algorithm Efficiency
The iterative improvement algorithm is the paradigm that lets agents explore better options to improve their state. This algorithm is called "greedy" because it always favors immediate payoff rather than deferring rewards to improve future outcomes. Many iterative improvement algorithms exist, including simulated annealing and genetic algorithms. We will look at several viable options to break out local optima using a greedy algorithm like iterative improvement.