# How to use Genetic Algorithm for varying lengths of solutions

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?

• 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. Mar 5, 2019 at 14:55
• 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 Mar 6, 2019 at 6:37

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).