ICS503 Final - Dr-Style Question Bank

Expected answer skeleton:

• BSF in minimization cannot increase. Any increasing CB curve cannot be BSF.
• Smooth monotone decrease = exploitation/local refinement/greedy acceptance.
• Stepwise decrease with exploitation periods = balanced behavior.
• Large irregular jumps = exploration or no elitism/current solution allowed to worsen.
• Fast drop then plateau = premature convergence or too much exploitation.
• Flat/high current with preserved best = elitism/bully risk.
• Tie to HW: HC/DE preserved-best behavior, PSO current oscillating above BSF, HCRR restart jumps, AS/ACS plateau/pheromone convergence.

• Very fast plateau: strong exploitation, high elitism/global-best/ACS greediness, low diversity.
• Oscillation around BSF: PSO current particles move while personal/global memory preserves BSF; SA/high exploration could also oscillate.
• Monotonic improvement: HC greedy acceptance, DE greedy replacement, GA with strong elitism if plotting preserved best.
• Late improvements: restart/perturbation/AS democratic exploration/TS escaping plateau.
• Fixes: reduce bully/global-best pressure, add mutation/noise/restarts, use local informants, adjust pheromone evaporation, preserve BSF but avoid excessive lock-in.

• HC: local exploitation; good with permutation encoding but can plateau.
• TS: adds memory/anti-cycling and best-neighbor movement; strongest pre-ACO non-population method.
• GA: population, crossover, mutation, elitism; diversity but crossover may disrupt global order.
• DE/PSO: stable population methods but random-key encoding is indirect for BPP.
• ACS/AS: constructive search plus pheromone co-location memory; ACS exploits, AS explores.
• Instance effect: easy/large-item instances do not differentiate; FFD-friendly instances reward greedy structure; Instance 3 rewards exploration/co-location learning.

• Do not simply average distances. Average hides goal coverage.
• External fitness measures actual progress/quality.
• Internal fitness is used for selection/breeding and should measure potential contribution.
• Fitness should be relative to other individuals targeting the same goal.
• Reward unique coverage of underrepresented goals; penalize redundancy when many individuals crowd the same goal.
• Purpose: maintain diversity and prevent the whole population from converging to one goal.

• Choose moderate interval.
• Long interval: wastes budget after local plateau.
• Short interval: does not allow enough exploitation within each basin.
• Moderate: each restart has time to improve, then budget samples another region.
• HW tie: HC runs reached local optima; different starts can end differently, so restart helps but must not be too frequent.

• T = 0: worse moves are not accepted; SA becomes HC-like; exploitation.
• T = infinity: worse moves are accepted almost freely; random-walk-like; exploration.
• Plot: low T gives monotone/plateau behavior; high T gives oscillating CB while BSF only improves when lucky.

• Mainly global best: swarm races to one leader; strong exploitation; bully/premature convergence risk.
• No global best: more distributed search; particles rely on their own memory and local informants; more exploration/diversity but slower convergence.
• CB/BSF: current best can oscillate, but BSF is preserved by memory.

• Too low evaporation: old pheromone persists; early paths dominate; lock-in.
• Too high evaporation: memory disappears; construction becomes closer to greedy/random heuristic.
• Best-only reward: elitist/exploitative; fast convergence but possible premature convergence.
• AS-style broader reward: more exploration; may discover unusual co-locations but can be less stable on greedy-friendly instances.

• Zero movement or identical population: no useful direction; stagnation.
• Small movement: local refinement; exploitation.
• Moderate movement: balance between exploiting the population structure and exploring nearby regions.
• Very large movement: big jumps; exploration but may overshoot or require repair/clamping.
• In BPP random-key encoding, even small key movement may cause no permutation change or sudden swaps.

• Define order: number of fixed positions.
• Define defining length: distance between first and last fixed positions.
• Crossover survival lower bound: 1 - pc * defining_length / (l - 1).
• Mutation survival: (1 - pm)^order.
• Short, low-order schemas survive more easily.

• Crossover combines partial structures from different individuals.
• Without crossover, individuals mostly self-breed through mutation.
• This reduces communication and makes the method closer to multiple parallel local searches/evolution strategy.
• Mutation adds exploration; selection and elitism add exploitation.

• Objective: minimize load imbalance, such as max load - min load or variance of column loads.
• Representation: assignment of each box to a column, or permutation decoded by a placement heuristic.
• Fitness: may include objective plus sensitivity term if many moves have same objective.
• Tweak: move one box to another column, swap boxes between columns, or perturb assignment.
• Locality: depends on tweak; moving one large box can cause large objective change, so locality may be weak.

• Many small tweaks do not change the number of bins, so the landscape has large plateaus.
• Fitness should be more sensitive to changes.
• Add empty-space distribution, fill variance, minimum slack, or penalty for bad packing patterns.
• External objective remains number of bins; internal fitness guides search/selection.

• Meta1 is more efficient early: good result with fewer resources.
• Meta2 is more effective if final quality is better.
• Meta1 likely exploits quickly; Meta2 may maintain exploration longer.
• Choice depends on time budget and required quality.
• Best answer: balanced method, effective and efficient for the constraint.

• Low variance means stable/reliable, but not necessarily effective.
• Higher variance can indicate useful exploration.
• If the goal is guaranteed acceptable quality, stable may be preferred.
• If the goal is best quality and multiple runs are possible, the exploratory method may be preferred.

• Storing complete solutions is expensive and very specific; may not prevent near-cycles.
• Storing moves/components is cheaper and can prevent immediate reversal.
• More restrictive tabu attributes increase exploration but may block useful moves.
• Less restrictive attributes preserve exploitation but may allow cycling.
• Aspiration can override tabu if a move gives a new best solution.

• Reactive tabu adjusts memory/tenure based on observed cycling or stagnation.
• If cycling occurs, increase restrictions/diversification.
• Noising perturbs the objective/fitness or evaluation to escape local traps.
• Both aim to avoid repeated exploitation of the same region.

• External fitness: absolute quality/progress measure, used to report the best solution.
• Internal fitness: used for selection/breeding; can be relative and context-sensitive.
• 8-tile: external may be distance to a goal; internal also considers which goal is covered by others.
• BPP: external may be number of bins; internal may include empty-space distribution to distinguish equal-bin solutions.

• It depends on relative coverage, but B may deserve high internal value.
• A is redundant if many individuals already cover Goal 1.
• B preserves diversity and goal coverage.
• The internal fitness should reward contribution to underrepresented goals, not just raw closeness.

• Average ignores which goal the individual is actually useful for.
• Average ignores whether many competitors already cover that same goal.
• It can eliminate unique individuals that are important for diversity.
• A better method is relative, goal-aware, and coverage-aware.

• Not necessarily. Multiple solutions alone are not enough.
• Population metaheuristics require interaction: communication, competition, shared memory, or collaboration.
• Independent restarts do not exchange information during the search.
• GA/PSO/ACO/co-evolution have interaction mechanisms.

• AS: proportional stochastic choice; democratic pheromone update; more exploration.
• ACS: greedier choice with best-focused update; more exploitation.
• AS can find unusual co-locations on hard/differentiating instances.
• ACS preserves strong greedy structure on FFD-friendly instances.

• Ants construct a solution component by component.
• In TSP, components are edges; in BPP, components can be item placements or item co-locations.
• Pheromone changes future construction probabilities.
• This differs from algorithms that modify a complete candidate solution after it already exists.