ICS503 Final - Midterm-Style Mock Questions
Questions rewritten to match the doctor's midterm wording style: long scenario, fixed constraints, experiment reference, and rationale-based grading.
What Makes A Question Doctor-Style?
| Doctor-style feature | How it appears |
|---|---|
| Experiment reference | "Consider the set of runs you conducted..." or "based on your mini-project observations..." |
| Constraint | "Assume the same number of evaluations/time..." or "fitness can be executed only a limited number of times..." |
| Behavior, not formula only | "Discuss the impact on behavior" and "justify" are more important than naming the parameter. |
| Design components | Objective, representation, locality, operator, and why. |
| Answer must use rationale | He can accept different choices if the reasoning is consistent with exploration/exploitation and HW observations. |
Most Likely 10-Point First Questions
VERY LIKELY10 ptsMIDTERM STYLE Q1-A
Consider the set of plots you generated in the mini-projects for the Bin Packing problem. Assume that the plots provided below represent the Current Best (CB) behavior of different metaheuristic techniques applied under comparable evaluation budgets. For each plot, analyze the algorithm's behavior in terms of exploration and exploitation. Indicate whether similar behavior was observed in your mini-projects, and if so, specify which techniques exhibited this behavior. In your answer, also discuss which of the plots may indicate the use of elitism or a best-so-far memory, and which plot cannot represent a Best-So-Far plot for a minimization problem.
Hint: you need to base your answer on the behavior of CB and BSF across the runs, not on the final numerical result only.
Expected answer direction
- BSF cannot increase in minimization.
- Smooth decrease: exploitation/local refinement, HC/DE preserved-best style.
- Stepwise decrease: exploit a region, then move to a better one; balanced behavior.
- Irregular current-best movement: exploration/no strict elitism/current can worsen, e.g. PSO current or SA-like behavior.
- Fast drop then plateau: premature convergence/too much exploitation.
- Elitism/memory: GA elitism, DE greedy replacement, PSO global/personal best, ACS best-so-far pheromone.
VERY LIKELY10 ptsMIDTERM STYLE Q1-B
Consider the experiments you conducted using DE and PSO for the Bin Packing problem. Assume that in one set of runs the Current Best and Best-So-Far curves are almost identical, while in another set of runs the Current Best curve oscillates and stays above the Best-So-Far curve for many iterations. Explain which behavior is more expected from DE and which is more expected from PSO. Justify your answer based on the mechanisms of the two algorithms and the representation you used for the Bin Packing problem.
Hint: your answer should not focus on the exact parameter values. Focus on how the algorithm keeps or uses memory.
Expected answer direction
- DE: trial competes with parent; worse trial does not replace parent. This creates preserved-best behavior.
- PSO: particles move according to personal/informant/global memory; current positions can become worse than historical best.
- CB-BSF gap is normal in PSO because BSF is memory while CB is current state.
- Both used random-key encoding, so continuous movement is indirect for BPP permutations.
VERY LIKELY10 ptsMIDTERM STYLE Q1-C
Consider the set of runs you conducted using AS and ACS for the Bin Packing problem. Assume that ACS converges quickly and produces almost the same result in most runs, while AS shows more variation and sometimes reaches a better result on a difficult instance. Explain this observation in terms of exploration and exploitation. In your answer, discuss the role of pheromone update, greedy selection, and the effect of the instance characteristics.
Hint: do not answer by saying "ACS is always better" or "AS is always better." Your justification should depend on the problem instance.
Expected answer direction
- ACS: more exploitative, greedier transition, best-focused reinforcement, faster lock-in.
- AS: more democratic/stochastic, more exploration, can discover unusual item co-locations.
- ACS better when FFD-like greedy construction is already strong.
- AS can be better on a differentiating instance where exploration matters.
LIKELY10 ptsMIDTERM STYLE Q1-D
Consider a p-metaheuristic technique applied to the Bin Packing problem. Assume that the total number of fitness evaluations is fixed. You are allowed to choose either a small population with more generations or a large population with fewer generations. Discuss the impact of these two choices on the behavior of the metaheuristic technique. Relate your answer to the behavior you observed in GA, DE, PSO, or ACO experiments.
Hint: you are not asked for the best numerical value of the population size. Discuss exploration, exploitation, and the chance of premature convergence.
Expected answer direction
- Small population + more generations: more time to exploit/refine, but diversity may collapse.
- Large population + fewer generations: more initial diversity/exploration, but less depth of improvement.
- Best depends on landscape and representation.
- Population methods require communication/competition, not only many independent starts.
Likely 3-5 Point Short Questions
HIGH3 pts Q2-A
Give the name of the algorithm or behavior that would result in these cases; justify. Explain the impact on behavior.
- Simulated Annealing with temperature equal to zero at all times.
- Simulated Annealing with temperature equal to infinity at all times.
Expected answer direction
Zero temperature becomes HC-like exploitation. Infinite temperature becomes random-walk-like exploration.
HIGH5 pts Q2-B
Let us consider two quantitative criteria to evaluate the performance of metaheuristics: efficiency and effectiveness. Consider the Best-So-Far plots for two metaheuristics, Meta1 and Meta2. Meta1 reaches a reasonable solution very quickly but does not improve much after that. Meta2 improves slowly but reaches a better final solution. According to each criterion, which metaheuristic may be considered the best one? Propose and explain possible way(s) to use Meta1 and Meta2 together to complement each other for better overall performance.
Expected answer direction
- Meta1 more efficient early.
- Meta2 more effective if final quality is better.
- Hybrid idea: use Meta1 for fast good initialization, then Meta2 for deeper improvement; or adaptive switch after plateau.
HIGH5 pts Q2-C
Given a set of objects of different sizes, the objective is to distribute them into k groups such that the total sizes of the groups are as similar as possible. Propose an objective function that could be used to find the best distribution of objects. Specify whether it is a minimization or maximization problem. Propose a representation of solutions to tackle this problem using an s-metaheuristic. Comment on the locality of your representation. Propose and explain a tweaking operator.
This is similar to the Bin Packing problem, but instead of minimizing the number of bins, you are balancing the total sizes of groups.
Expected answer direction
- Objective: minimize max group load - min group load, or variance of group loads.
- Representation: assignment vector or permutation decoded by a constructive rule.
- Locality: moving one large item can strongly affect objective; locality may be weak.
- Tweak: move one object, swap two objects, or redistribute one group.
HIGH5 pts Q2-D
Consider a binary string of length 11 and consider the following schemata:
1*********1, 11*********, *****111***, and **1***1**0*.
- Under one-point crossover, calculate a lower limit on the probability of these schemata surviving crossover in one generation.
- Calculate the probability of surviving mutation in one generation if the probability of mutation at a single bit position is given.
- Explain which schema is most fragile and why.
Expected answer direction
- Crossover survival depends on defining length.
- Mutation survival depends on schema order.
- Short, low-order schemas survive more easily.
HIGH5 pts Q2-E
The 8-puzzle consists of a 3 by 3 board with eight numbered tiles and a blank space. A tile adjacent to the blank can move into the blank space. Assume there are multiple acceptable goal states. Using a coevolutionary algorithm, explain how you would assess the internal fitness of individuals in the population. Would you simply average the distance of each individual to all goal states? Justify your answer.
Hint: consider what happens if many individuals are close to the same goal state while another goal state is covered by only one individual.
Expected answer direction
- Do not simply average distances.
- Fitness should be goal-aware and relative to other individuals.
- Reward unique coverage of underrepresented goals.
- Internal fitness is for selection; external fitness is for actual progress/best solution.
MED5 pts Q2-F
Consider a Tabu Search technique applied to a permutation representation of the Bin Packing problem. Assume the algorithm keeps returning to very similar solutions. Discuss two possible tabu-list representations with different levels of restriction. Explain the expected impact of each representation on exploration, exploitation, and memory cost.
Expected answer direction
- Store complete solutions: high memory, very specific, may not prevent near-cycles.
- Store moves or reverse moves: cheaper, prevents immediate reversal.
- Store attributes/components: more restrictive, more diversification but may forbid useful moves.
- Aspiration can allow tabu move if it improves BSF.
MED4 pts Q2-G
Consider applying PSO to the Bin Packing problem using the representation you used in your mini-project. Explain why the Current Best curve may get worse while the Best-So-Far curve does not. In your answer, explain the role of personal best, neighborhood/informant best, and global best.
Expected answer direction
Particles move and can leave good current positions, so CB can worsen. Personal/global/informant memory preserves historical best guidance, so BSF does not worsen.
MED4 pts Q2-H
Consider the Bin Packing problem where the objective is to minimize the number of bins. Explain why the number of bins alone may not be a good internal fitness function for a metaheuristic. Propose an additional term that may be added to the fitness function and explain its purpose.
Expected answer direction
Number of bins is not sensitive to many tweaks. Add empty-space distribution, slack, fill variance, or penalty/reward to distinguish same-bin solutions and guide search.
Three Full Mock Finals In The Actual Style
- (10 pts) Consider the CB plots produced by different metaheuristic techniques in your mini-projects for Bin Packing. For each plot, analyze exploration and exploitation behavior. Indicate whether similar patterns were observed in HC, TS, GA, DE, PSO, AS, or ACS. Explain which plots may indicate elitism or best-so-far memory, and which plot cannot be a valid BSF plot for minimization.
- (3 pts) Give the name of the algorithm or behavior that would result from SA with temperature equal to zero and SA with temperature equal to infinity. Justify.
- (5 pts) Consider two metaheuristics Meta1 and Meta2 with different BSF plots. Meta1 is faster early, Meta2 is better late. Discuss efficiency, effectiveness, and how to combine them.
- (5 pts) Given boxes of different heights to be placed into k columns with similar total heights, propose objective, representation, locality, and tweak operator.
- (7 pts) Consider the 8-puzzle with multiple goal states. Explain how internal fitness should be assessed in 1-population competitive coevolution. Explain why simple average distance to all goals may be misleading.
- (10 pts) Consider the set of runs you conducted using DE and PSO for the Bin Packing problem. Assume both are limited by the same number of evaluations. One algorithm shows CB almost equal to BSF, while the other shows CB oscillating above BSF. Explain the behavior and relate it to the algorithm memory and representation.
- (4 pts) Consider PSO where particles are guided mainly by the global best. Discuss the impact on exploration and exploitation. What would happen if global-best influence is removed?
- (5 pts) Consider a p-metaheuristic with fixed fitness-evaluation budget. Discuss small population with more generations versus large population with fewer generations.
- (5 pts) Compare AS and ACS in terms of transition rule, pheromone update, and the expected behavior on easy versus difficult Bin Packing instances.
- (6 pts) Consider a binary string and a set of schemata. Compute survival under crossover and mutation, and explain which schema is most likely to survive.
- (10 pts) Consider the observations you reported in HW5 and HW6 for DE, PSO, AS, and ACS. Discuss how each algorithm navigates the Bin Packing problem. Your answer should explain why some algorithms are stable but not best, why ACO may improve on a difficult instance, and how item-size distribution affects the behavior.
- (5 pts) Consider applying Tabu Search to a permutation representation. Propose two tabu-list designs and discuss their impact on behavior.
- (5 pts) Consider two bin-packing solutions with the same number of bins but different empty-space distributions. Are they equal for selection/breeding? Explain using internal and external fitness.
- (5 pts) Consider GA for the 8-puzzle. Propose representation and objective. Discuss whether crossover should be used and justify your mutation choice.
- (5 pts) Consider HC with random restart under the same total budget as your original HC experiment. Would you choose a short, moderate, or long restart interval? Justify from experiment behavior.
Answer Style To Practice
Write like this:
"I would choose a moderate restart interval. A long interval wastes evaluations after HC has already reached a plateau, while a very short interval does not give each restart enough time to exploit its region. In our runs, HC behavior showed local-optimum behavior: improvement early, then little change. Therefore, under the same budget, a moderate interval balances exploitation inside each basin with exploration through new starting points."
Do not write like this: "Moderate because it is balanced." That is too thin.
This file is designed to imitate question wording, not only topic coverage. Use it after the broader question bank.