1
$\begingroup$

Until now, I always thought that Genetic Algorithm can be used for problems of which the solution space can be encoded (modeled) as a chromosome of a specific length. However, some people claim that they used GA for this game and this game. They are basically games in which we control an agent on a 2-dimensional area.

Obviously, the length of the genome sequence depends on how fast the game is finished. So, how is GA used for such games?

If you think GA is not the most suitable method for this kind of problems can you explain why and give better alternatives?

$\endgroup$
  • $\begingroup$ When it comes to alternative solutions, how about Evolutionary Algorithms (EA)? Seems to me EAs are more flexible then GAs and can find their use in more applications than GAs. $\endgroup$ – Makintosz Mar 5 at 14:55
  • $\begingroup$ Evolutionary Algorithm is a class of machine learning comprising of at least 3 sub-classes namely: Genetic Algorithms (GA) [Holland et al](Including GPs), Evolutionary Programs (EP) [Fogel et al], Evolutionary Strategies (ES)(Rechenberg et al). Back was the first to categorise these algorithms in 1997. See his book dl.acm.org/citation.cfm?id=548530 $\endgroup$ – Jason Mar 6 at 6:37
1
$\begingroup$

Before I answer your question, it is important to frame what a GA is, so please allow me to cover some history.

Friedman and Fraser performed some of the earliest evolutionary computation experiments. Fraser presented the case of diploid organisms represented by binary strings of a given length. Each bit in the string represented a gene. Fraser proposed the process of single-point crossover for binary string reproduction.

American computer scientist John Henry Holland and his colleagues at the University of Michigan formalised the evolutionary algorithms originally implemented by Bremermann, Fraser, Friedman and Friedberg.

Holland's formal algorithm is known as a Genetic Algorithm (GA). A GA has a fixed length chromosome structure. Traditionally it was binary based. However due to hamming distances of various bit strings a GA using a binary encoded chromosome string can get stuck at local minima. Holland experimented with integer based GAs too.

Getting back to your question, theoretically and in its strictest sense, a Genetic Algorithm has a fixed length chromosome vector. The primary reason for this is that each gene represents something. If it was variable then the meaning of the gene must be encoded into the chromosome, which makes evolution more difficult. However, there are other chromosome structures that are variable length. The chromosome structure itself implies meaning.

Koza experimented with an alternative version of a GA called a genetic programming (GP). A GP replaces the fixed length vector structure used in a genetic algorithm with a variable length, non-linear, hierarchical abstract data structure, known as a tree.

The tree consists of branch nodes and leaf nodes. Leaf nodes have no children and implement a number or constant from a terminal set. A leaf node is also known as a terminal node. A branch node is connected to other branch nodes or leaf nodes and implement an operator from a functional set. A branch node is also known as a non-terminal node.

The tree structure naturally accommodates a game rule. A tree is not restricted to a fixed length. A tree is a natural structure to represent hierarchical decisions rules, and a tree can store both binary, logical, and numeric functions within its nodes. Logical functions allow the GP to evolve conditional execution of game play functions not easily implemented using a fixed length vector. Tree does need a traversal path and grammar (syntax and semantics).

In short to answer your questions:

  1. A GA (fixed length) is generally not used for games, but rather a GP (variable with decisions).
  2. A GA is not the most suitable method for this kind of problem as it is fixed length, and each gene corresponds to a rule or value.

I would implement a GP, where the operators of mutation and crossover are adapted for a GP. I would also use the game itself as a fitness function, where a pool of individuals either using a single population, or co-evolution evolve players that gradually increase their score.

The paragraphs above were taken from Nicholls' MSc thesis. His thesis was on stock market trading rule generation which is similar to game rule generation. His thesis is available here (Only available after April 2019).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.