CI2025 Lab 1: Metaheuristic Optimization Review

by SLV Team 48 views

Hey there, code wizards! Let's dive into some awesome insights and tweaks for your CI2025 Lab 1 on metaheuristic optimization. The goal here is to get you on track with a robust and effective search strategy. We will address the core issues that are holding back your algorithm from finding those optimal solutions, especially on larger, more complex problems. Buckle up; let's get started!

The "Reject" Strategy and Its Impact

Understanding the Problem

Your current code structure is built around a "reject" strategy. Here’s what I mean: in both baseHillClimbing and tabuSearchHillClimbing, your primary loops look like this:

  • new_solution = tweak(solution)
  • if not is_valid(new_solution): continue
  • if fitness(new_solution) >= fitness(solution): ...

You're starting with an empty (and therefore valid) solution, and your tweak function is designed to flip a single item. This setup is designed to move only between valid states. For problems 2 and 3, which involve massive knapsacks with numerous constraints, the odds of a single random flip leading to another valid solution are incredibly slim. Think of it like trying to hit a tiny target from miles away.

What Goes Wrong

This "reject" strategy leads to an almost immediate standstill. The algorithm might add a few items initially, but then every subsequent tweak will likely result in an invalid solution. The candidates list in your Tabu Search will remain empty most of the time, and the search will get stuck, unable to move and therefore, unable to find good solutions. This is like being trapped in a maze with only a few valid paths, and those paths are almost impossible to find by chance.

The Solution: Embracing Imperfection

The way to fix this is to embrace imperfection by allowing invalid solutions temporarily but penalizing them appropriately. Here’s how you can make the change:

  • Remove is_valid(new_solution) from your main loop entirely. This frees up your algorithm to explore a wider range of possibilities.
  • Create a function that calculates how invalid a solution is. This function quantifies the degree of constraint violation, such as the amount by which knapsack capacities are exceeded or items are duplicated.
  • Define a new score function that the algorithm will try to maximize. This function should combine the value of the solution (items included) with a penalty for any invalidity. For example, score = value - penalty * invalidity. This way, the algorithm aims to find solutions that maximize the value while minimizing the penalty.
  • Adjust your hill climber to use this score function. The goal is to maximize the score, which means finding solutions that are both valuable and valid, or at least have a low penalty if they are slightly invalid. This allows the algorithm to move more freely within the solution space, even if the moves initially lead to some invalid states. Over time, the algorithm should gravitate towards more valid and higher-value solutions.

Performance Bottlenecks: Optimizing is_valid

The Slowdown

Even if you sidestep the "Reject" issue, your is_valid function is a major performance bottleneck. You're running this function inside a loop MAX_STEPS times, which can be computationally expensive. For Problem 3, this means running the function: MAX_STEPS (10,000) x NUM_SAMPLES (10) x NUM_KNAPSACKS (100) x (Cost of sum). You're recalculating the total weight of every knapsack from scratch every single time, even after a tiny modification. This is like reassembling a car from individual parts after making the smallest adjustment.

The Optimization Strategy

The key to speeding things up is to avoid redundant calculations. Instead of just storing a solution, you should also maintain the current loads (a (K, D) sized array representing the load in each knapsack) and the current excess (how much each knapsack exceeds its capacity). Here's what you should do:

  • Maintain loads and excess alongside your solution. These variables store crucial intermediate results, avoiding recalculations.
  • When your tweak function flips an item i in knapsack k, don't recalculate everything. Just update loads[k] by adding or subtracting WEIGHTS[i]. This involves a simple addition or subtraction, which is much faster than recalculating the sum of all item weights.
  • From these updated loads, you can instantly re-calculate the new excess and the new score. This ensures that you can quickly evaluate the impact of a change.

Implementing the Optimization

  1. Initialize loads and excess: When you initialize your solution, also calculate the loads (the total weight in each knapsack) and excess (the amount by which each knapsack exceeds its capacity). This will be your starting point.
  2. Update loads in tweak: When tweak changes your solution (e.g., adds or removes an item from a knapsack), also update the corresponding loads and excess values. This is where you leverage the pre-calculated intermediate results.
  3. Recalculate excess: After updating loads, quickly recalculate excess based on the new loads and knapsack capacities.
  4. Recalculate score: Recalculate the score using the updated excess values, reflecting the new penalty if any constraints are violated.

The tweak Operators: Choosing the Right Tool

Comparing the Operators

You've got two different tweak operators: one that's a standard operator and another, more advanced, "move" operator. Let's break down each one:

  • Standard Operator: This operator flips an item's status (from False to True or vice versa). However, it has a significant drawback. If you flip sol[k1, i] from False to True but sol[k2, i] is already True, the item is now in two knapsacks. Your is_valid check sol.sum(axis=0) > 1 would catch this, but again, this will be rejected.
  • "Move" Operator: This "move" operator is much better. It ensures that the "item in at most one knapsack" rule is never violated. Instead of simply toggling an item, it moves the item from one knapsack to another. This is a much safer, more controlled operation.

Why the "Move" Operator Wins

Your comment says the move operator "RETURN WORST RESULTS." This is almost certainly because of the "Reject" strategy. The "move" tweak is more disruptive, so it probably landed in the "invalid" solutions even more often, and your hill climber just got stuck. The move operator is more disruptive because it makes a more significant change to the solution, which increases the likelihood of violating a constraint, particularly when your search space is heavily constrained. With the "Reject" strategy in place, such moves would be immediately discarded.

Recommended Approach

I would strongly recommend using the "move" operator (your commented-out one) in combination with the penalty function fix we discussed earlier. This combination offers several advantages:

  • The "move" operator ensures that the "item in at most one knapsack" rule is always respected, avoiding a common validity issue.
  • The penalty function allows the algorithm to explore a wider search space by temporarily accepting invalid solutions, thus increasing the chance of finding more effective moves. This is like allowing your algorithm to step outside the safe zone to explore what's beyond the fence.

Final Thoughts: Reframing Your Approach

You've got all the fundamental components you need. By switching your objective from "find the best valid move" to "find the move that best improves the score (value minus penalty)," your hill climber will be able to navigate the search space more effectively and find great solutions. This is like changing your mindset from finding the perfect answer immediately to finding the answer that is the least flawed. Focus on maximizing the score, balancing the solution's value with the associated penalties. This will allow your algorithm to move more freely, avoid getting stuck, and discover higher-quality solutions.

By implementing these changes, you'll transform your search strategy from a restricted, easily trapped approach into a dynamic, adaptive system capable of tackling complex optimization problems. Good luck, and keep up the great work!