What is the difference between genetic algorithms and evolutionary game theory algorithms?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Philip's answer is good, but I'll add to it.
In a GA, a population of individuals (typically represented by bit strings) is evaluated for its fitness on a particular task. Each individual is evaluated separately by a fitness function than can determine its quality. In the Traveling Salesman Problem, the bit string might represent a sequence of numbers, for instance, corresponding to an order in which cities are visited during the tour. The fitness function would inspect a single individual, compute the total cost of the tour, and assign that individual a fitness based on that value. Low scoring individuals are removed, high scoring individuals generate variants on themselves, and the process repeats.
In Evolutionary Game Theory, a population of individuals is also evaluated on some task, but usually the task involves interaction between the individuals. For example, you could use an EGT simulation to study what happens in a game like Iterated Prisoner's Dilemma. Here, an individual's fitness doesn't just depend on the rules of the task, but on the behaviors and strategies of the other players in the population. A strategy that is highly effective at first (like always cooperate) will quickly die out once defectors appear. Defectors are effective as long as there are some cooperators to prey upon, but are quickly defeated by strategies like Tit-for-Tat. Usually researchers are not interested in the specific strategies that emerge so much as in the population dynamics over the course of the simulation, and in what kinds of population equilibria can emerge. Check out some of Dan Ashlock's papers on Game Theory for more.
answered Nov 28, 2019 at 14:23
$\begingroup$
$\endgroup$
A genetic algorithm is typically a single population designed to optimise to a specific task, say minimising the distance on the travelling salesman problem.
Evolutionary game theory algorithms typically model changes between populations that are in competition, generally by using genetic algorithms as above but framed within a broader competitive environment between actors.
In the case of a problem like the travelling salesman problem, it might frame the game as one with competing players where a player getting to a city 'locks' that city and makes it impassable to other players. In these situations new optimisations like localism over adventurism etc may develop, and while players are still trying to minimise the distance travelled overall via their respective genetic algorithm's fitness function, they have to do so in a directly competitive environment with other strategies which quickly creates a lot of additional nuance and depth.
