Methods for Competitive Fitness in Coevolutionary Algorithms
Competitive fitness in coevolutionary algorithms relies on strategic opponent sampling methods to efficiently evaluate fitness against various opponents. Approaches like random sampling, round-robin evaluation, and single-elimination tournaments each offer unique trade-offs in accuracy and computational cost. Additionally, strategies like converting to winners and losers can provide valuable insights into individual performance.
Uploaded on Mar 17, 2025 | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Methods for Competitive Fitness Methods for Competitive Fitness in in Coevolutionary Coevolutionary Algorithms Algorithms Sean Harris For COMP 5660/6660 COMP 5660/6660 bonsai.auburn.edu
Overview Overview Competitive fitness depends on the relative capability of opponents Evaluating against every possible opponent is ideal, but infeasible Instead, we sample a subset of possible opponents While random sampling is the most common, other methods of opponent sampling have advantages COMP 5660/6660 bonsai.auburn.edu
Random Sampling Random Sampling Pair each individual with n random opponents, then average the fitnesses Tradeoff between accuracy and time spent Advantages: easy to implement, minimal bias Disadvantages: inefficient use of evaluations COMP 5660/6660 bonsai.auburn.edu
Round Round- -Robin Evaluation Robin Evaluation Pair each individual with each opponent, then average the fitnesses Advantages: very accurate measure of fitness for a given population size Disadvantages: extreme time cost, quadratic with population size COMP 5660/6660 bonsai.auburn.edu
Single Single- -Elimination Tournament Elimination Tournament Award fitness based on which round of a tournament individuals finished in Advantages: greatly limits number of evaluations Disadvantages: difficult to use for multiple populations, games need winners/losers, strong transitivity assumption 3 2 1 COMP 5660/6660 bonsai.auburn.edu
Aside: Converting to Winners and Losers Aside: Converting to Winners and Losers Compare two individuals against a mutual opponent The winner is whoever scored highest against that opponent This creates an artificial game between two individuals who may not have directly competed 3.45 > 2.66 COMP 5660/6660 bonsai.auburn.edu
Aside: Transitive and Intransitive Games Aside: Transitive and Intransitive Games When a game is transitive, A > B and B > C implies that A > C An intransitive game has cycles in its dominance graph, e.g. Rock Paper Scissors Nearly all real-world games have some amount of intransitivity However, many algorithms assume a transitive game A Intransitive B R S P C Transitive COMP 5660/6660 bonsai.auburn.edu
Sample High Sample High- -Fitness Opponents Fitness Opponents Pair each individual with the n highest-fitness opponents from last generation Advantages: doesn t waste time evaluating against bad opponents Disadvantages: Top-fitness individuals are often very similar, behaves poorly for intransitive games Generation t Generation t-1 COMP 5660/6660 bonsai.auburn.edu
Aside: Competitive Fitness Sharing Aside: Competitive Fitness Sharing Method of rewarding individuals who beat rarely-defeated opponents Assigns a bounty to each individual, divided between each opponent who beats them Helps encourage phenotypic diversity and preserve counter- strategies 6 6/1 6/2 3 3+2+3 6/3 6/2 2+3 2+6 6/1 COMP 5660/6660 bonsai.auburn.edu
Shared Sampling Shared Sampling Iteratively construct a sample with high competitive fitness sharing scores relative to each other, used for all opponents Like sampling high-fitness opponents, but more diverse Advantages: opponents are tested against a diverse sample of good opponents Disadvantages: requires games that have winners/losers Generation t Generation t-1 COMP 5660/6660 bonsai.auburn.edu
Selecting a Sampling Method Selecting a Sampling Method Direct comparison of resulting individuals Not always easy to do in competitive coevolution Comparison of sampling accuracy Need to compare sampled fitnesses to a ground truth Analysis of transitivity properties Determine whether sampling methods with transitivity assumptions are valid Analysis of phenotype space Determine how different strategy groups are organized and relate to each other COMP 5660/6660 bonsai.auburn.edu
Measuring Sampling Accuracy Measuring Sampling Accuracy Compare estimated fitness from a sampling technique to a ground truth fitness value One method: Perform round- robin evaluation on a population to get the ground truth Fitness error or rank error can be computed between estimated fitness and ground truth Rank Error Comparison Example Random Sampling Experimental Sampling Method 0.35 0.3 Average Fitness Rank Error (%) 0.25 0.2 0.15 0.1 0.05 0 0 500 1000 1500 2000 2500 Total Pairing Evaluations COMP 5660/6660 bonsai.auburn.edu
Alpha Alpha- -Rank Rank Skill rating system based on Markov chain modelling Finds the stationary distribution of a Markov chain, where edges represent a chance to switch to a strategy that beat you The strategy distribution of the game s resulting meta Extremely well-suited for modelling intransitive games COMP 5660/6660 bonsai.auburn.edu
References References Competitive fitness sharing, shared sampling: Christopher D. Rosin and Richard K. Belew. 1997. New methods for competitive coevolution. Alpha-Rank: Shayegan Omidshafiei et al. 2019. ?-rank: Multi-agent evaluation by evolution. COMP 5660/6660 bonsai.auburn.edu
