Due: Friday before class (submit on Moodle + be ready to demo)
Overview
In this assignment, you will improve the wall-design algorithm using hill climbing.
You will:
- build on your greedy algorithm,
- implement hill climbing to improve wall layouts,
- experiment with different improvement strategies,
- and evaluate your results using the visualizer.
For students who want to go further, you may extend your work using simulated annealing.
Part 1: Hill Climbing (Required)
Objective
Take a wall produced by your greedy algorithm and improve it using hill climbing.
Hill climbing means:
- start with an existing wall,
- repeatedly make small changes,
- keep only changes that improve the score,
- stop when no improvement is possible.
What You Must Do
For at least 2 different walls:
- Generate an initial wall (using your greedy algorithm).
- Apply hill climbing:
- make small changes to the wall,
- evaluate using the scoring function,
- accept only improvements.
- Repeat until no further improvement is possible.
Required Improvements
You must implement at least 3 different types of hill-climbing moves, such as:
- swap two artworks
- remove an artwork
- replace an artwork with another candidate
- add an artwork (if space allows)
- reposition artworks along the wall
You should experiment with different combinations of these moves.
What to Show in Class
Be ready to demonstrate:
- your starting (greedy) wall
- your improved (hill-climbed) wall
- the difference in score and/or visual quality
- a brief explanation of what changes helped
Part 2: Writeup (Required)
Submit a short writeup (1–2 pages) including:
1. Hill Climbing Approach
- How does your hill climbing work?
- What kinds of moves did you implement?
2. Results
- What improvements did you observe?
- Which moves were most effective?
3. Limitations
- Where does hill climbing get stuck?
- What kinds of walls are still difficult?
Part 3: Extension — Simulated Annealing (Optional, for full credit)
To go beyond hill climbing, implement simulated annealing.
This allows your algorithm to:
- occasionally accept worse moves,
- escape local optima,
- explore more of the solution space.
If you implement annealing, include:
- description of your temperature schedule
- how you modified hill climbing to allow worse moves
- comparison with your hill climbing results
Grading Rubric (100 points total)
Hill Climbing Implementation (40 points)
- 20 pts: Basic hill climbing implemented correctly
- 30 pts: Multiple meaningful move types used
- 40 pts: Strong hill climbing with effective improvements
Exploration and Experimentation (20 points)
- 10 pts: Minimal experimentation
- 15 pts: Tried multiple move types
- 20 pts: Thorough exploration with comparisons
Results and Demonstration (20 points)
- 10 pts: Some visible improvement
- 15 pts: Clear improvement over greedy
- 20 pts: Strong and consistent improvements
Writeup Quality (20 points)
- 10 pts: Basic explanation
- 15 pts: Clear explanation and results
- 20 pts: Insightful analysis and reflection
Simulated Annealing Bonus (up to +20 points)
- +10 pts: Basic annealing implemented
- +15 pts: Effective annealing with good comparison
- +20 pts: Strong implementation with clear improvement over hill climbing
Important Note on Grading
- The maximum score achievable using hill climbing alone is 80%.
- To earn a score above 80%, you must implement simulated annealing or an equivalent advanced strategy.
Summary
- Build a greedy wall
- Improve it using hill climbing
- Try multiple move strategies
- Analyze results
- (Optional) Extend using simulated annealing
Key Idea
Greedy builds.
Hill climbing improves.
Annealing explores.
This assignment is about learning how to move between those ideas.