Transcript Pareto Coevolution - Department of Computer Science

Pareto Coevolution
Presented by KC Tsui
Based on [1]
Sorting Networks and MOO
• First work on coevolution with host-parasite model and
two independent evolving but interacting gene pool
– sorting networks (SNs) and test cases (TCs)
• Two fitness functions
– SN: score according to number of test cases it succeeded in
handling
– TC: score according to number of failed SNs that tests on it
• In MOO, a pareto front defines a set of solutions that have
the same fitness according to a aggregated measure of all
objectives
2
Motivations
• Coevolutionary systems plays an arms race game and
provides a task for each other to tackle
• Each system requires the ability to dynamically adjust the
learning environment
• There is no guarantee that coevolution will lead to
effective learning
• Borrow idea from multi-objective optimization to
formulate the task to be learned
3
Search as Teaching and Learning
• Search involve a fitness landscape, but can be dynamically
changed according to different objectives
• Teachers: create a search gradient
• Learners: following a search gradient
• A good teacher is one that is able to identify some
knowledge ‘gap’ in some learners
• A good learner is one that has learned the tasks set by some
teachers
• Evolution: The process of variation to discover better
teachers and students
4
Learning
• Pareto dominance, commonly used in MOO, is used to
obtain a rank among the population concerned
• Learner x (pareto) dominates learner y iff Gx,w > Gy,w and
Gx,v > Gy,v, G is a payoff matrix and w,v are teachers
• x and y are mutually non-dominating iff Gx,w > Gy,w and
Gx,v < Gy,v
5
Learning (cont.)
• Learning: a recursive process of identifying the nondominated learners, exclude them from the population and
start over again (find the pareto layers)
– Pareto layer Fn is less broad in competence than some learners in
Fn-1
– Every learner in Fn-1 can do something better than some other
learner in Fn
• Ranking is done by some kind of tournament
6
Teaching
• Given the payoff matrix G (row=learners;
columns=teachers) for assessing student performance,
transform it to become a student dominance matrix M
(row=teachers, column=pair of students) for assessing
teacher performance
vk
s

M
d k   M i ,k
• Score of a teacher j is j  j ,k
dk
k
i
– i.e. the value of a learner pair across the learners distinguished by j
discounted by total number of teachers that distinguish it
– j distinguish x from y if Gx,j > Gy,j
7
Results
• Second best performance in the majority problem
for cellular automata
• Similar idea has been applied to game strategy
discovery [2]
8
Discussion
• Pros
– Smooth divide-and-conquer strategy
• Cons
– Payoff matrix G (and hence M) is not always readily
available or computed easily
– Requires a lot of function evaluations
9
References
1.
2.
Sevan G. Ficici and Jordan B. Pollack, Pareto Optimality
in Coevolutionary Learning, Computer Science Technical
Report CS-01-216, University of Brandeis.
J. Noble and R.A. Watson, Pareto coevolution: Using
performance against coevolved opponents in a game as
dimensions for Pareto selection , in Proceedings of the
Genetic and Evolutionary Computation Conference,
GECCO-2001, pp. 493-500. Morgan Kauffman, San
Francisco.
10