Coevolution: Exam Concepts

Focused on Dr. Moataz Ahmed's final-exam style: explain behavior, classify the scheme, design internal/external fitness, and reason about exploration/diversity.

Final exam priority: Coevolution has no HW report, so expect conceptual questions from slides/transcripts. Most likely: define context-sensitive fitness, internal vs external fitness, classify a scenario into one of the four schemes, and explain why diversity/niching prevents premature convergence.

1. The One-Line Model

Coevolution = fitness depends on other individuals, not only on the solution itself.

Before coevolution, fitness was mostly absolute: a BPP packing uses 10 bins, a TSP tour has length 120, a GA chromosome has a fixed score. In coevolution, an individual's score can change depending on who else is present.

The broad transcript idea is that multiple individuals, populations, techniques, or metaheuristics can compete or cooperate. The slide examples make this precise using populations and context-sensitive fitness.

The slide definition is the key exam sentence: a system is coevolutionary if whether A is better than B depends on the presence or absence of another individual C.

Exam answer: Coevolution is a population-based framework where fitness is context-sensitive. The quality of an individual depends on its interaction with other individuals or populations. Therefore, the ranking of solutions can change when the population changes.

2. Context-Sensitive Fitness

Tic-Tac-Toe / Rock-Paper-Scissors Intuition

Assume three game-playing individuals:

Match	Winner	What It Means
`A` vs `B`	`A`	If only A and B exist, A looks better.
`B` vs `C`	`B`	If only B and C exist, B looks better.
`C` vs `A`	`C`	If C appears, A no longer looks best.

There is no fixed global ranking like A > B > C. The answer depends on who is being tested against whom.

Doctor-style wording: The fitness is not only a property of the individual. It is a property of the individual in a context. This is why coevolution can be tricky: the population itself changes the fitness landscape.

3. Internal vs External Fitness

This is probably the most testable concept in coevolution.

Internal fitness = what the algorithm uses to choose parents/survivors. External fitness = what you report as the real solution quality.

	Internal Fitness	External Fitness
Purpose	Used inside the algorithm for selection, breeding, survival, or assigning credit.	Used to judge real progress and track the best solution.
Nature	Can be relative, context-sensitive, penalized, or shaped.	Should be as absolute and problem-facing as possible.
BPP analogy	Bins plus empty-space signal, variance, or penalty to distinguish two 10-bin solutions.	Actual number of bins used.
Coevolution example	How well a firewall rule set performs against the current adversarial scenarios.	How well the final firewall performs on a fixed real test set.

Exam answer: Internal fitness is for the optimizer. It decides which individuals should survive or reproduce, and it may be relative to the current population. External fitness is for reporting progress. It should measure the actual quality of the solution independently of the temporary population context.

Example 1: Bin Packing

External fitness: the real objective, usually the number of bins.

External = number of bins

If two solutions both use 10 bins, externally they look equal. But internally one may have more potential.

Solution	External	Internal Signal
A	`10` bins	Lots of half-empty bins; weaker potential.
B	`10` bins	Tighter packing; better potential.

Internal fitness may add empty-space variance or fill-quality so the algorithm can choose between equal-bin solutions.

Example 2: Game Players

Internal fitness: wins against the current population.

External fitness: performance against a fixed benchmark player or fixed test panel.

Match	Winner	Meaning
`A` vs `B`	`A`	A looks strong if B is common.
`C` vs `A`	`C`	A looks weak if C is common.

Internal fitness changes with the population. External fitness is more stable because the benchmark does not keep changing.

Example 3: Firewall Coevolution

Population P is firewall rule sets. Population Q is attack/test scenarios.

Fitness Type	Question
Internal fitness for `P`	How many current `Q` scenarios did this rule set block correctly?
External fitness for `P`	How well does this rule set perform on a fixed real-world test set?

Internal is useful for breeding because Q is the current challenge. External is needed because Q changes every generation.

Example 4: Multi-Goal 8-Puzzle

Suppose the algorithm wants to solve G1, G2, and G3.

Individual	Goal	Raw Distance	Internal Meaning
`A`	`G1`	`2`	Good, but many others also chase `G1`.
`D`	`G2`	`5`	Worse raw distance, but uniquely covers `G2`.
`E`	`G3`	`2`	Good and uniquely covers `G3`.

Internal fitness may prefer D over another G1 individual because D preserves coverage. External fitness reports actual progress toward solved goals.

Simple memory hook: External asks, "How good is this solution really?" Internal asks, "How useful is this individual for the algorithm's next selection decision?"

4. The Four Coevolution Schemes

Transcript clarification: The doctor first motivates coevolution broadly as "can techniques compete or cooperate?" and mentions that two metaheuristics can help each other. But the exam-level lecture then focuses on populations of individuals: candidate solutions, rules, scenarios, strategies, or subsolutions. Do not assume every individual is an algorithm.

Scheme	Setup	Main Question	Example	Exam Keyword
1-Pop Competitive	One population. Individuals compete with others in the same population.	How does this individual perform against its peers?	Game players, multi-goal 8-puzzle, rules competing for the same input.	Same-population competition
2-Pop Competitive	Two populations. One tries to solve; the other tries to challenge or break it.	Can P survive what Q throws at it?	GAN-like setup, firewall rules vs attack scenarios.	Adversarial test cases
N-Pop Cooperative	Problem is split into subproblems, each handled by a dedicated population.	Does this partial solution cooperate well in a complete team?	Robot soccer roles, project roles, decomposed high-dimensional optimization.	Subpopulations cooperate
Diversity / Niching	One population, but similar individuals are penalized or separated into niches.	How do we avoid everyone collapsing to the same region?	Fitness sharing, crowding, random restarts, noisy tweaks.	Prevent premature convergence

Does Each Individual Represent an Algorithm?

The doctor did say multiple algorithms/techniques can be used together. In the coevolution intro, he frames the idea broadly: techniques may compete or cooperate, and one metaheuristic can help another. This is a valid coevolution idea.

But in the detailed slide examples, an individual is usually not an algorithm. An individual represents whatever candidate object the population is evolving: a complete solution, a partial solution, a rule, a test scenario, or a strategy. It only represents an algorithm if you deliberately design the population that way.

Transcript anchors: ICS503-23_otter_ai.txt lines 372-381 say techniques/metaheuristics can cooperate or compete. Lines 397-409 then narrow the formal definition to fitness affected by other individuals. ICS503-24_otter_ai.txt lines 478-529 discuss rule individuals, scenario individuals, and N-pop role strategies.

Transcript Context	Population	What One Individual Represents
1-pop competitive game / 8-puzzle	One population `P`	A candidate player or a sequence of moves trying to reach one of several goals.
2-pop firewall, Pittsburgh design	`P`: firewall side	A whole firewall rule set. This is a complete candidate solution.
2-pop firewall, Michigan design	`P`: firewall side	One rule. The final firewall is formed by many rule individuals working together.
2-pop firewall attack side	`Q`: scenario side	One attack/test scenario sent to the firewall population.
N-pop cooperative soccer/team	Several subpopulations	One role strategy or partial solution, such as goalkeeper strategy or backend component.
Broad metaheuristic coevolution view	Multiple optimizers or techniques	One metaheuristic/algorithm can help, challenge, or complement another. This matches the doctor's intro wording.

Safe exam wording: Coevolution can be viewed broadly as multiple algorithms or populations helping/challenging each other. In the slide-level schemes, the individual is problem-dependent: it may be a full solution, a rule, a test case, or a partial solution. The key is that fitness depends on interaction with other individuals, subpopulations, or populations.

Is Niching Used With the Other Three Schemes?

Yes, it can be used with them, but it is listed as a fourth theme. The slide lists four main themes: 1-pop competitive, 2-pop competitive, N-pop cooperative, and diversity maintenance/niching. The first three describe the coevolution structure. Niching is the diversity tool that can be added when individuals collapse into the same role, same goal, or same niche.

Transcript anchor: ICS503-24_otter_ai.txt lines 653-719. He asks what happens under premature convergence, says all individuals get pulled by one good solution, then lists diversification, noise, less-fit survival, fitness sharing, crowding, and similarity types.

Where Niching Appears	Why It Is Needed	Example
Inside 1-pop competitive	Too many individuals chase the same opponent/goal.	Multi-goal 8-puzzle: penalize the crowd near `G1` so `G2` and `G3` survive.
Inside 2-pop competitive	Many rules or scenarios cover the same weakness.	Firewall Michigan design: many good rules trigger on the same input, so rules need internal competition/niching.
Inside N-pop cooperative	One subpopulation may collapse to one role strategy.	All goalkeeper strategies become similar, so the team loses alternative coordination patterns.
As its own diversity theme	The main problem is premature convergence, regardless of competition/cooperation.	Penalize similarity, use crowding, inject noise, random restarts, or keep less-fit individuals sometimes.

Exam answer: Niching is formally the fourth coevolution theme in the slides, but practically it can be used inside the other schemes whenever the population loses diversity. It is the answer to "everyone is being pulled to the same good solution; how do we force spread?"

5. 1-Pop Competitive Example

Multi-Goal 8-Puzzle

The doctor spent time on this kind of issue: one population, multiple goal states. If everyone chases the easiest goal, the population ignores the other goals.

Why not solve three separate problems? You can, but the transcript point is that it wastes computation. A sequence of moves that helps one goal may also be useful for another goal. Solving them together can reuse search effort. The catch is that the fitness function becomes harder.

No-free-lunch trap: Solving the goals together saves repeated search, but now fitness cannot be a simple "distance to nearest goal." It must also ask whether too many individuals are already chasing that same goal.

Individual	Closest Goal	Distance	Naive Fitness	Problem
`A`	`G1`	`2`	`-2`	Good, but G1 is crowded.
`B`	`G1`	`2`	`-2`	Another G1 seeker.
`C`	`G1`	`3`	`-3`	Another G1 seeker.
`D`	`G2`	`5`	`-5`	Farther, but only one going to G2.
`E`	`G3`	`2`	`-2`	Good and unique.

If selection only uses naive fitness, it may pick A, B, and E, leaving G2 abandoned. A context-sensitive internal fitness should penalize crowding around G1 and preserve progress on G2.

One possible internal score: internal = closeness_to_goal / number_of_individuals_chasing_that_goal

Individual	Goal Crowd	Internal Meaning
`A`, `B`, `C`	3 individuals chasing `G1`	Share credit. Do not let one goal bully the population.
`D`	Only one chasing `G2`	Keep it alive even if its raw distance is worse.
`E`	Only one chasing `G3`	High value because it covers a separate goal.

What the Internal Fitness Must Consider

Question	Why It Matters	Transcript-Style Answer
How close am I to a goal?	Raw progress still matters.	A solution at distance `2` is usually better than distance `15`.
Which goal am I chasing?	Coverage matters when there are multiple goals.	If everyone is chasing `G1`, a `G2` seeker may be more valuable.
Who else is competing with me for the same goal?	Crowding reduces my internal value.	If five individuals have the same best distance to `G1`, they should share credit instead of all dominating selection.
Has that goal already been solved?	Once a goal is solved, more individuals chasing it have less value.	Push the population toward unsolved goals.

Exam takeaway: In 1-pop competitive coevolution, individuals are not only judged by raw objective quality. They are also judged by what role they play relative to others. A weaker-looking individual may be valuable if it covers an underrepresented goal.

6. 2-Pop Competitive Example

Firewall Rules vs Attack Scenarios

This is the clearest transcript example. There are two populations:

Population	Individual Means	Fitness Pressure
`P`	A candidate firewall rule set, or in another design one firewall rule.	Do well against attack/test scenarios from `Q`.
`Q`	A traffic scenario or adversarial test case.	Expose weakness in `P`. A good test separates strong rules from weak rules.

Good Test Case Intuition

The doctor compared this to exams/quizzes. A very easy quiz is bad because everyone passes. A very hard quiz is also bad because everyone fails. A good quiz discriminates.

Scenario From Q	Percent of P Rule Sets That Pass	Is It a Good Test?	Why
`Q1`	`100%`	No	Too easy. It does not reveal weakness.
`Q2`	`0%`	No	Too hard. It does not distinguish rule quality.
`Q3`	`70%` pass, `30%` fail	Yes	It has discrimination. It challenges some but not all.

Average and Variance Matter

The transcript also connects this to ML/testing: average performance alone can hide risk. A firewall can have good average performance but still fail badly on a subset of scenarios.

Rule Set	Scenario Results	Average	Risk
`P1`	`70%, 70%, 70%`	`70%`	Consistent.
`P2`	`100%, 100%, 10%`	`70%`	Same average, but dangerous because one scenario breaks it badly.

That is why external testing or robust fitness may consider both average and variance. In the doctor's wording, you want something consistent, not only a good average.

Q's Fitness: Tester vs Trainer

A Q scenario has two useful interpretations:

View	What Q Wants	Exam Wording
Tester / attacker	Break many `P` rule sets.	A scenario caught by only `10%` of firewalls exposes a serious weakness.
Trainer / quiz	Differentiate strong `P` from weak `P`.	A useful test is not trivial and not impossible; it gives a learning signal.

Exam takeaway: In 2-pop competitive coevolution, P becomes robust because Q keeps generating challenging cases. Q should not merely be impossible; it should reveal differences among P individuals.

Pittsburgh Approach

Individual = whole rule set

Each individual is an entire firewall.
Fitness is based on the whole rule set's performance.
Good rule inside a bad rule set may die with the bad individual.
Good for evaluating complete deployable solutions.

Michigan Approach

Individual = one rule

Each individual is a single rule.
Good rules can survive directly.
Many rules must cooperate to form a firewall.
Risk: many good rules may cover the same input, so niching may be needed.

Firewall Design Detail: What Can Crossover Mix?

The transcript spends time on a practical design question: if an individual contains firewall rules, should crossover swap whole rules or pieces of rules?

Design	What Crossover Does	Effect
Swap whole rules	Take rule 1 from parent A, rule 2 from parent B, etc.	Preserves meaningful rule schemas. More exploitative/stable.
Mix inside a rule	Take source IP from one rule and destination/action from another.	More exploratory, but may destroy useful rule structure.
Mutation of fields	Change one field such as IP, port, action, or time condition.	Controlled exploration around a rule.

Exam takeaway: In coevolution, the algorithm is not the hard part; the design of representation, crossover, mutation, and fitness is the hard part. For firewall rules, preserving whole rules protects good schemas, while breaking rules increases exploration but can damage meaning.

7. N-Pop Cooperative Example

Robot Soccer / Team Project

Here the populations are not fighting. They are each solving one part of a larger solution.

Subpopulation	Individuals Are	Fitness Must Ask
`P1`	Goalkeeper strategies	Does this goalkeeper help a complete team win?
`P2`	Defender strategies	Does this defender coordinate well with others?
`P3`	Attacker strategies	Does this attacker help the team score?

To evaluate one goalkeeper, you must assemble it with representatives from the other subpopulations and evaluate the complete team. Its individual quality is not enough.

Project Alignment Example

The transcript uses a team-project style explanation. Suppose Malik makes use cases and Abdullah makes backend APIs.

Person	Completed Work	Individual Count
Malik	Use cases: `UC1, UC2, UC3, UC4`	4
Abdullah	Backend APIs: `UC1, UC2, UC5`	3

Together they do not score 4 + 3 = 7. They only have two aligned working features: UC1 and UC2.

Team fitness = aligned complete features = 2

Exam takeaway: In N-pop cooperative coevolution, the fitness of a partial solution depends on how well it works with partial solutions from other populations. The goal is not local excellence only; it is contribution to a complete solution.

8. Diversity Maintenance / Niching

This is the last theme and it connects directly to the doctor's plot vocabulary: premature convergence, bully solution, loss of diversity, plateau.

Niching = do not let one crowded region take all the selection pressure.

Imagine many individuals are almost the same. Even if they are good, keeping all of them wastes population space. Niching says: keep some representatives, but push the rest of the population toward other regions.

Mechanism	Idea	Effect
Fitness sharing	Lower an individual's fitness if too many similar individuals are nearby.	Prevents one crowded region from dominating selection.
Crowding	A new child competes with similar individuals, not necessarily the global worst.	Maintains multiple niches/species.
Noise / mutation / restarts	Push individuals away from the current cluster.	More exploration when the population collapses.
Pick less-fit individuals sometimes	Do not let selection be too greedy.	Gives alternative basins a chance to survive.

Example A: Fitness Sharing

Suppose we maximize fitness. Four individuals have raw fitness values:

Individual	Region / Niche	Raw Fitness	How Crowded?	Shared Internal Fitness
`A`	Region 1	`90`	3 similar individuals	`90 / 3 = 30`
`B`	Region 1	`87`	3 similar individuals	`87 / 3 = 29`
`C`	Region 1	`84`	3 similar individuals	`84 / 3 = 28`
`D`	Region 2	`70`	1 individual	`70 / 1 = 70`

Without sharing, A, B, and C dominate selection. With sharing, D becomes attractive because it covers a different region. This is the same idea as not letting all individuals chase the same goal.

Exam takeaway: Fitness sharing lowers the internal fitness of crowded individuals. It does not say the crowded solution is bad externally; it says keeping too many copies is bad for search diversity.

Example B: Crowding

Crowding changes who a new child competes against.

Step	Normal Selection	Crowding Selection
New child appears	Child may replace the globally weakest individual.	Child is compared to the most similar existing individual.
Effect	A strong niche may keep taking space from all other niches.	Each child competes mostly inside its own neighborhood.
Diversity result	Population can collapse to one region.	Multiple regions survive longer.

Think of it as local competition instead of global replacement. A new solution near Region 1 should not kill the only representative of Region 2.

BPP Example: What Does "Too Similar" Mean?

Capacity is not important here. The point is item grouping.

Solution	Bins	Why Similar or Different?
`S1`	`{A,B,C}`, `{D,E}`, `{F}`	Baseline.
`S2`	`{A,B,C}`, `{D,F}`, `{E}`	Similar to S1 because `A,B,C` stay together.
`S3`	`{A,D}`, `{B,E}`, `{C,F}`	Different grouping; useful for exploration.

If S1 and S2 both have good fitness, the algorithm may overpopulate that grouping. Niching would reduce their internal selection advantage so S3-type alternatives can survive.

Plot Interpretation

Plot Behavior	Diagnosis	Niching Fix
CB/BSF improves early, then long plateau.	Population may have collapsed to one basin.	Add sharing/crowding, noise, or random restarts.
Many individuals have almost identical fitness and structure.	Low diversity, possible bully solution.	Penalize similarity or inject different individuals.
Current best varies across niches while BSF slowly improves.	Diversity is preserved; exploration is still alive.	Accept slower convergence if final search quality improves.

Three Ways Individuals Can Be Similar

Similarity Type	Meaning	BPP Analogy
Phenotypic	They behave similarly.	Both use 10 bins with similar fill pattern.
Genotypic	Their encoded structure is similar.	Same item-to-bin assignment or same item groupings.
Fitness value	They have similar score.	Both have 10 bins, even if structurally different.

Exam answer: Niching is a diversity maintenance method. It penalizes individuals that are too similar or forces competition within neighborhoods, so the population does not prematurely converge to one local optimum.

9. Exam Classification Practice

Prompt	Correct Classification	Why
A population of game agents gets fitness by playing against other agents in the same population.	1-Pop Competitive	Same-population competition.
One GA evolves firewall rules while another GA evolves attack scenarios.	2-Pop Competitive	Two adversarial populations: solution vs test.
One population evolves goalkeeper strategy, another defender strategy, another attacker strategy.	N-Pop Cooperative	Subpopulations cooperate to form a complete team.
Two individuals with nearly identical solutions have their fitness reduced so both do not dominate.	Diversity / Niching	Similarity penalty to preserve spread.
A candidate has worse raw distance but is the only one approaching an unsolved goal.	1-Pop Competitive / Niching logic	Context-sensitive internal fitness should preserve underrepresented goals.

10. Plot and Behavior Notes

Premature Convergence

If all individuals cluster around one solution, CB/BSF may plateau. Coevolution's diversity tools try to prevent this by preserving alternative roles, goals, or niches.

Internal Fitness Can Fluctuate

Because internal fitness depends on the current population, an individual's internal score can change even if its encoded solution does not change.

External BSF Should Be Tracked

Use external fitness to report best-so-far. Internal fitness is for selection and may be relative, so it is not always the right progress measure.

11. Likely Final Exam Prompts

Define Coevolution

Fitness depends on other individuals or populations. A may beat B in one context but lose ranking when C is present.

Internal vs External

Internal fitness is for selection and can be relative. External fitness is for real progress and should be absolute.

Classify a Scenario

Decide whether it is 1-pop competitive, 2-pop competitive, N-pop cooperative, or niching.

Design Fitness

Given a new problem, propose internal fitness and external fitness. Explain why they may differ.

Explain Niching

Penalize similarity or crowding to maintain diversity and avoid premature convergence.

Firewall Example

P is candidate firewall/rules. Q is adversarial scenarios. A good Q test is discriminating, not impossible or trivial.

12. Final One-Paragraph Answer

Coevolution means that fitness is context-sensitive: an individual's quality depends on other individuals or populations. This creates the need to separate internal fitness, which drives selection and may be relative, from external fitness, which measures real progress. The four main schemes are 1-pop competitive, where individuals compete inside one population; 2-pop competitive, where one population of solutions is challenged by another population of tests; N-pop cooperative, where subpopulations solve parts of a larger solution; and niching, where similarity is penalized to maintain diversity. For the final, the safest answers classify the scenario, define internal and external fitness, and explain the exploration/exploitation or diversity effect.