Transcript Cooperative Coevolutionary EA

Cooperative Coevolutionary EA
KC Tsui
base on [Potter & De Jong 2000]
Objectives
“The basic hypothesis … to apply EA
effectively to increasingly complex
problems, explicit notions of modularity
must be introduced … for solutions to
evolve in the form of interacting coadapted
subcomponents”
Major Issues
•
•
•
•
•
Problem decomposition
Interdependency of subcomponents
Maintain diversity during search
Credit assignment
CCGA
– let decomposition emerges
– apply evolutionary pressure to force species to
find their own niches
Basic Algorithm
gen = 0
for each species s do begin
Pops(gen) = randomly initialized population
evaluate fitness of each individual in Pops(gen)
end
while termination condition = false do begin
gen = gen +1
for each species s do begin
select Pops (gen) from Pops (gen-1) based on fitness
apply genetic operators to Pops (gen)
evaluate fitness of each individual in Pops (gen)
end
end
Fitness Evaluation
choose representative from each species
FOR each individual i from S requiring evaluation
BEGIN
form collaboration between i and representatives
evaluate collaboration by applying it to the target problem
assign fitness of collaboration to i
END
Variable # of Species
• Add one species when the ecosystem is stagnated
– Initialize population randomly
– Evaluate fitness based on the overall fitness of the ecosystem
• Stagnation is defined by:
– f(t) – f(t-L) < G, where
– f(t) is the fitness of best collaboration at time t – an ecosystem
generation
– L is a window size
– G is the threshold above which considerable amount of
improvement has occurred
• Destroy the species that is not making enough contribution
Testbeds
• Function optimization
• Rules learning – two species of rules
• String cover problem
– more species leads to higher improvement over
canonical GA
– Stagnation/contribution measurement provides a good
measure for the algorithm to adapt the number of
species
• Cascade (neural) network architecture for the
double spiral separation task
Related Papers
• Potter & De Jong. (2000). Cooperative Coevolution: An
Architecture for Evolving Coadapted Subcomponents,
Evolutionary Computation 8(1): 1-29.
• Rosin & Belew. (1997). New Methods for Competitive
Coevolution, Evolutionary Computation 5(1): 1-29.
• Moriatry & Miikkulainen. (1998). Forming Neural
Networks Through Efficient and Adaptive Coevolution,
Evolutionary Computation 5(4): 373-399.
Related Papers (2)
• Ficici & Pollack. (2001). Game Theory and the Simple
Coevolutionary Algorithm: Some Preliminary Results on
Fitness Sharing. GECCO 2001 Workshop on Coevolution:
Turning Adaptive Algorithms upon Themselves.
• Ficici & Pollack. (2001). Pareto Optimality in
Coevolutionary Learning. Sixth European Conference on
Artificial Life, Jozef Kelemen (ed.), Springer, 2001.
• Watson & Pollack. (2001). Coevolutionary Dynamics in a
Minimal Substrate. Proceedings of the 2001 Genetic and
Evolutionary Computation Conference, Spector, L, et al
(eds.), Morgan Kaufmann, 2001.