The nature of code: Chapter 9
Recently in my CS course, we were tasked with reading chapter 9 in the book The Nature of Code. The chapter revolves around the creation of complex algorithms that can simulate evolution, albeit in a broad way. The principle behind this resides in the use of genetic algorithms, following three basic concepts in Darwinian evolution: Variation, Heredity and selection.
A genetic algorithm is stated to be “a specific algorithm implemented in a specific way to solve specific sorts of problems”. In other words, it is stated to be an algorithm that can “learn” as it is being executed, thus presenting the idea of learning or evolution. Genetic algorithms are used when there is a great amount of information to process and the implementation of a “brute force algorithm” could result in a program that takes too long to find the solution (as it would check every single part of the information), while a genetic algorithm would “learn” and “evolve” from the information in order to reach the solution in a faster way.
It can be seen that a genetic algorithm “evolves” through the use of terms such as variance, genotype and phenotype. The variance would be the population of answers from which the algorithm would “learn”, the genotype would be the internal genetic information the variables in the code have, and the phenotype would be the physical or visible expression of the program created in every iteration of the code. The algorithm evolves by taking into account the natural selection, or survival of the fittest. This is done in the following way:
1. The “population” (all possible answers) is evaluated in order to find the members of the population with the most valuable “traits” (parts of the information that would lead to an absolute answer to the problem posed). This is done (in programming) by assigning a numerical value (percentage of closeness to absolute answer) to all possible answers, in order to determine the possible answers that are “closest” to absolute answer.
2. Then, based in probability, the answers that more closely fit the absolute answer should be picked most times, while answers that don’t resemble the absolute answer should be picked fewer times. This ensures that all possible answer have a degree of probability of being picked based on their traits, following the rule of the survival of the fittest.
3. Then, the population should “reproduce” and pass on traits to the “children”. Just like in evolution, children should inherit traits from both parents. This is ensured through: (1) Cross over: The creation of a child with genetic code from both parents. There should be a 50/50 distribution of the traits given to the child (50% from mother, and 50% from father). Nonetheless, the traits given to the child should be random (not all children from the same parents will receive the same traits). In code, this should be seen as the fact that, the “children” created from two possible answers should contain a 50/50 distribution of “traits” from the parents, but the information should be randomly given out to each child, creating variance in the genetic code each child has.
(2) Mutation: After creating a child with traits from the parents, a final step should be taken. This is the inclusion of a mutation of a child’s genetic code. This could be the changing of a character in an array of Strings, for example. The mutations should happen in a rate, like in nature. There is a probability that a child may or may not receive a mutation. Normally, the probability for mutations is small; therefore, the code should include a 5% mutation probability, for example.
After going through these steps, the “population” will evolve, and the “children” will obtain “traits” from the “parents” that will closely resemble the absolute answer. And the “population” will keep on evolving until the absolute answer is found. For example, there could be a code tasked with constructing the phrase “To be or not to be” from at least a 1000 other phrases. The genetic algorithm will check every phrase and compare them, classifying the phrases by fitness or closeness to final answer. Then, the phrases that more closely resemble the final answer will be picked and have a “child”, which will have traits from both parents. Since both parents both closely resemble the final answer, the child should be even more close to the answer. The child will repeat the cycle, having a child with another phrase that closely resembles the final answer. This cycle will repeat itself until the phrase “To be or not to be” is constructed. To summarize this, it could be seen that a genetic algorithm follows these steps:
SETUP: 1) Initialization: Creation of a population of N elements, each randomly generated
LOOP: 2) Selection: Fitness is evaluated, and the phrases mate and have children 3) Reproduction: Which is repeated until final answer is reached. Divided in: a) Selection of parents b) Crossover: Creation of child with traits from both parents c) Mutation: Chance of genetic code of child to change d) Add new child to population 4) Return previous population with new population and return to step 2
With this topic, I saw how we have come so far into our understanding of the world and its mechanisms that we have already transported them to our code, which can help us in creating better, more intelligent code. This could be the base of artificial intelligence, and the fact that it is so close to us is seriously amazing. By having the possibility to create our own intelligent code, we can now transport the rules of nature and have the possibility to create a truly autonomous agent.