ICS503 Final - Midterm-Style Model Solutions

Q1-A10 pts CB/BSF Plot Interpretation

Model answer: For a minimization problem such as bin packing, the Best-So-Far curve must either decrease or stay flat. It cannot increase, because BSF is the best objective value observed up to that point. If a curve goes up, it can only be a Current Best/current solution curve, not BSF.

A smooth decreasing curve suggests exploitation: the algorithm is making local improvements without large jumps. This resembles HC with greedy acceptance, or DE if we plot the preserved population best because worse trials do not replace parents. A stepwise decreasing curve with plateaus means the algorithm exploits a region for some time, then finds a better region. This is closer to balanced behavior and can appear in TS, GA with elitism, or ACO when pheromone reinforcement discovers a better construction.

A curve with irregular ups and downs suggests current search movement without strict preservation of the current best. This can happen with SA, PSO current positions, comma-style replacement, or random restart current curves. A fast drop followed by a long plateau suggests premature convergence: the method exploited too quickly and then lost useful diversity. If the plot shows a good solution being preserved while the current population is not improving, this may suggest elitism or a "bully" effect: the best is kept, but not effectively exploited or diversified around.

HW tie: HC and DE give more monotone preserved-best behavior. HCRR can show jumps at restart points. PSO can show a gap between CB and BSF because particles move away while memory keeps the historical best. ACS can converge quickly and plateau because pheromone and greedy choice reinforce the same construction.

Q1-B10 pts DE vs PSO Curves

Model answer: The run where Current Best and Best-So-Far are almost identical is more expected from DE. In DE, each trial solution competes directly with its parent. If the trial is worse, it is rejected, so the parent remains. This greedy replacement makes each individual non-worsening over time, and the best individual in the population is naturally preserved. Therefore, DE often looks like a preserved-best curve.

The run where Current Best oscillates above Best-So-Far is more expected from PSO. In PSO, particles keep moving according to personal best, informant best, and global best. A particle can move away from a good position, so the current swarm best may become worse than the best historical position. However, the best-so-far memory is still kept, so BSF does not worsen.

For bin packing, both DE and PSO were applied through random-key encoding. This means continuous positions are decoded into permutations. The encoding lets us use continuous optimizers, but it is indirect: small key changes may not change the permutation, or may suddenly swap item order. That is why DE/PSO can be stable but still not always better than direct permutation methods such as TS or GA.

Q1-C10 pts AS vs ACS Runs

Model answer: ACS converging quickly with very similar results across runs indicates stronger exploitation. ACS uses a greedier transition rule and a more best-focused pheromone update, so once a good construction pattern appears, the ants repeatedly reinforce it. This can be very effective when the instance is FFD-friendly or when the largest-first/size heuristic already gives a strong solution.

AS showing more variation means it is more explorative. In AS, pheromone is updated more democratically, so more ants influence future construction. This can keep more alternatives alive and may find item co-locations that ACS locks out too early. Therefore, AS may beat ACS on a difficult differentiating instance, especially if the best solution requires unusual pairings rather than simply following the greedy structure.

The correct conclusion is not "AS is better" or "ACS is better." ACS is better when strong exploitation of a good construction pattern is enough. AS is better when the instance requires broader exploration before deciding which components deserve reinforcement.

Q1-D10 pts Small Population vs Large Population

Model answer: Under a fixed number of fitness evaluations, a small population with more generations gives more depth. The algorithm has more opportunities to refine, select, recombine, and improve the same lineages. This increases exploitation. The drawback is that a small population may lose diversity early and converge prematurely.

A large population with fewer generations gives more breadth. The algorithm samples more regions initially, so it has better exploration and lower dependence on one unlucky initialization. The drawback is that each individual or region receives less improvement time, so the search may not exploit promising solutions deeply.

In GA, this is a selection between population diversity and generational improvement. In PSO, more particles may cover more regions, but fewer iterations gives less time for personal/global/informant memory to guide the swarm. In ACO, more ants can sample more constructions per iteration, but fewer iterations gives less time for pheromone learning. The best choice depends on whether the problem is suffering from premature convergence or from insufficient local refinement.

Q1-E10 pts HC Random Restart Interval

Model answer: I would choose a moderate restart interval. A long interval is not suitable because after HC reaches a local optimum or plateau, additional iterations are mostly wasted exploiting the same region. A very short interval is also not suitable because the search restarts before it has enough time to improve and exploit the current basin.

A moderate interval balances both behaviors. Each restart gets enough time to perform local exploitation and reach a reasonable local optimum, but the algorithm still reserves budget to explore other starting regions. This matches the behavior observed in the HC experiments: runs improved early and then plateaued, and different random starts could lead to different local optima. Therefore, moderate restart length is the best answer under a fixed budget.

Q2-A3 pts SA Temperature Extremes

Temperature = 0: SA becomes Hill Climbing-like. Since worse moves have no chance of being accepted, the algorithm only accepts improving or non-worsening moves. This is exploitation.

Temperature = infinity: SA becomes random-walk-like. Worse moves are accepted with very high probability, so the algorithm loses greedy pressure and explores randomly. This is exploration.

Q2-B5 pts Meta1 vs Meta2

Model answer: Meta1 is more efficient because it reaches a useful solution quickly with fewer resources. However, Meta2 is more effective if it eventually reaches the better final solution. If the time budget is very small, Meta1 may be preferred. If final quality matters more and we have enough time, Meta2 may be preferred.

A good hybrid is to use Meta1 first to quickly generate a good initial solution, then switch to Meta2 for deeper improvement. Another option is adaptive switching: run Meta1 until its BSF plot plateaus, then use Meta2 to escape or refine. This combines Meta1's efficiency with Meta2's effectiveness.

Q2-C5 pts Boxes / Columns Balancing

Objective: Minimize imbalance between columns. Possible objective functions are:

or

Representation: An assignment vector where position i indicates which column box i belongs to. Example: [1, 3, 2, 2, 1] means box 1 in column 1, box 2 in column 3, etc. Another option is a permutation decoded by a placement heuristic.

Locality: Locality may be weak if one moved box has a large height, because a small representation change can cause a large load difference. It is stronger when item sizes are similar.

Tweak: Move one box from one column to another, or swap two boxes between columns. Move is simple and explorative if the box is large; swap may preserve total number of boxes per column and can be more controlled.

Q2-D5 pts Schema Survival

Model method: For one-point crossover, the lower bound survival probability is:

where delta(H) is the defining length and l is chromosome length.

For mutation, the survival probability is:

where o(H) is schema order, the number of fixed bits.

Interpretation: A schema with large defining length is more fragile under crossover. A schema with many fixed positions is more fragile under mutation. Therefore, short, low-order schemas are most likely to survive. This is the building-block intuition.

Q2-E5 pts 8-Puzzle Coevolution Internal Fitness

Model answer: I would not simply average the distance of an individual to all goal states. Average distance ignores which goals are already covered by other individuals. In 1-population competitive coevolution, internal fitness should be relative to the population.

If many individuals are already close to Goal 1, another individual close to Goal 1 is less valuable because it is redundant. If one individual is moderately close to Goal 2 and nobody else is covering Goal 2, that individual has important internal value because it preserves diversity and goal coverage.

External fitness measures actual progress or final quality. Internal fitness is used for selection and should reward contribution, potential, and coverage. A good internal fitness should consider closeness to each goal relative to the best/current individuals for that goal, and penalize overcrowding around the same goal.

Q2-F5 pts Tabu List Design

Model answer: One tabu-list design is to store complete solutions. This is expensive in memory and very specific. It prevents returning to exactly the same solution, but it may not prevent returning to a very similar solution.

A second design is to store the recent move or reverse move, such as "do not swap these two positions back." This is cheaper and prevents immediate cycling. A stronger version is to store attributes, such as "item A cannot return to bin B for several iterations." This increases exploration because it forces the search away from recent structures, but if it is too restrictive it may block useful moves and hurt exploitation.

Aspiration can be used to override tabu status if the move produces a new best-so-far solution.

Q2-G4 pts PSO CB Worse Than BSF

Model answer: In PSO, current particles can move away from good positions. Therefore, the current best particle in this iteration may be worse than a solution discovered earlier. This is why CB can worsen or oscillate.

However, PSO stores memory: each particle has a personal best, informants or neighborhood best can guide it, and the swarm may keep a global best. Because of this memory, the Best-So-Far curve does not worsen. A gap between CB and BSF is normal and indicates that current movement is exploring while historical memory preserves the best solution found.

Q2-H4 pts Objective vs Fitness In BPP

Model answer: The number of bins is the external objective, but it may be weak as an internal fitness function because many small moves do not change the bin count. This creates plateaus: two different configurations may both use the same number of bins even though one has more potential for future improvement.

To guide the search, we can add a sensitivity term such as empty-space distribution, variance of bin loads, minimum slack, or a penalty for badly filled bins. The purpose is not to change the real objective, but to help selection and local search distinguish between solutions that look equal externally.

Mock Final A - Outline

1. Use Q1-A plot solution.
2. Use Q2-A SA extremes.
3. Use Q2-B Meta1 vs Meta2.
4. Use Q2-C boxes/columns formulation.
5. Use Q2-E coevolution internal fitness.

Mock Final B - Outline

1. Use Q1-B DE vs PSO curves.
2. PSO global best: strong global-best influence creates exploitation and premature convergence risk. Removing it increases diversity but slows convergence.
3. Use Q1-D population size vs generations.
4. Use Q1-C AS vs ACS.
5. Use Q2-D schema method.

Mock Final C - Outline

1. DE/PSO: stable but random-key indirect. AS/ACS: constructive pheromone memory; AS explores, ACS exploits. Instance size distribution controls winner.
2. Use Q2-F tabu list design.
3. Use Q2-H objective vs fitness and internal/external distinction.
4. GA for 8-puzzle: representation can be sequence of moves; objective minimizes distance to goal plus invalid/redundant move penalty. Mutation can change a move; crossover is risky unless repaired because move sequences can become invalid or meaningless.
5. Use Q1-E HC random restart interval.