As I finish writing GPI, it is important for its audience to have an understanding of many of the concepts of GP. While this material may seem difficult initially, take the time to read and become familiar with the terms and concepts. The implementation of GPI will be much more understandable.
Researchers in genetic programming attempt to find commonality in the discipline with other disciplines. The most obvious discipline is genetics. Genetics uses two terms that are useful when describing an individual: genotype and phenotype. Let's see if we can't describe in layman's terms how these apply in GP.
Genotype: Any representation of the program (genetic material) of the candidate solutions involved in the GP model.
Phenotype: Any resulting characteristic or behavior that results from the genotype.
Ok, I missed the mark on "in layman's terms". Let's simplify and take the human body for example. In some chromosome(s), there are genes which provide the building blocks for how the eyes are formed and actually mature. The color of the eyes is determined by these genes. The genes are the genotype and the eyecolor is the phenotype. Genotype determines phenotype (more on this in a moment), but phenotype doesn't determine genotype (more on this in a moment).
In GP, it's important to distinguish what we can observe as facts of the genotype and the observable results of the genotype on the phenotype. Phenotype results may be emergent properties.
So what is phenotype in GP? It is the resulting behavior that the GP exhibits. In functional GP, the phenotype is usually the fitness function and its value for the candidate solution. In imperative GP, the imperative program (genotype) may actually operate on attributes other than the genotype, e.g. variables in global storage for the candidate solution, or global scope variable storage for the population of candidate solutions or exhibit other results while observing the fitness function. There are other forms of GP (not in the public domain) which further this distinction or remove much of the distinction in favor of classifications of computing and language models with knowledge represenation.
There are a few debates regarding the real effects of genotype on phenotype and phenotype on genotype (wait didn't you just say phenotype doesn't affect genotype?). Let's take an example from nature, Lions and Gazelles:
Every year, the plains in Africa go through a cycle of seasons. During these seasons, the environment changes from hot (but cooler than the hottest times of the year), rainy season and summer. Suffice it say that we can "observe" many things about the seasons that would allow us to classify them, but these three will be our starting point.
Let's also say that in a given summer season, Lions need to eat but are less likely to hunt because it is hot and who wants to go chase some prey when you can sit in the shade and watch TV? Lions tend to eat less and become more lean, slightly weaker, but more agile (from the weight loss). These phenotypes (weight, strength and agility) are modified by the environment. Heavier lions lose weight and have to hunt less during this season.
During the summer season, the gazelle population through normal births and deaths grows. Because the predators are less likely to hunt, there are a smaller number of gazelles dying vs. the number of gazelles being born and the observable fact of the population is that it increases (not genotype, not phenotype). The gazelles are engaged in less predator-prey activity and thus become less agile, fatter and less concerned with the threat of predator. The phenotypes are less fit gazelles and the behaviors in the individuals.
As the summer winds down, the temperatures drop (but not by much) and the hungry lions and the fatter gazelles engage in more frequent predator-prey behavior. Because the leaner lions are more agile, they typically participate in the "better" kills and become stronger. Because the fatter gazelles are slower and weaker, they are likely the slowest prey and will be the easiest catch for the predator during the pursuit. This results in stronger lions getting stronger (genotype: better genetic structure of muscles; phenotype: added strength because of activity) and weaker gazelles getting killed (genotype: genes that "retain less fat"; phenotype: fatter and slower).
So we can observe a few simple things from this discussion:
-
Environment plays a role in the way in which an organism survives.
-
The genotype that is suited to predatory activity (lion) or avoidance activities (gazelles) typically have a higher rate of survival.
-
The phenotypes of the predator (loss of weight, gain in strength in higher frequency eating schedule) and that of the prey (fatter and slower) contribute to the survival of the predator or prey.
This survival study is natural selection and is the basis for the genetic operator selection in GP (and GA). An important distinction is that the program (genotype) exhibits behavior that determines its ability to survive (phenotype) in the population and setting (environment) of the GP. So while genotype is always said to determine phenotype, there are other interactions. Typical statements (where -> means loosely "determines"):
- genotype + environment -> phenotype
- phenotype + environment -> genotype (survival)
There is a great deal of controversy on this topic. Typical "bets" are made regularly on what makes a man: genetics or environment. Lamarck had an opinion on this topic and we'll cover that in a future post. Another point to be made is that intelligence as an emergent behavior or as a phenotype of an organism may bias its ability to survive, i.e. less fit individuals may survive because they can interact with their environment in ways that "dumb" organisms might not. Known as the Baldwin Effect, this too will be another topic in the future.
On May 9th, 2005, a team of researchers announced the factoring of RSA-200. The group, based at the German Federal Agency for Information Technology Security (BIS), announced the results demonstrating the two factors that when multiplied, provide a solution to the RSA Challenge problem RSA-200. While as of this writing RSA Security has not acknowledged the results in public, verification can be performed simply by multiplying the two factors and comparing them with the original challenge.
The group was also credited with the factoring of RSA-576 (a 174 digit number) in December, 2003, so this result demonstrates the determination and ingenuity of this team.
Because factoring is the basis for the RSA Public Key Cryptography, this result has some significance in cryptography. This public result is a barometer for the computational effort required to discover a private key of similar size (~665 bits). While the search space for factoring roughly doubles as the size of the candidate increases by a single bit, this increase of ~89 bits over the previous result represents a significant computational effort. While I haven't had a chance to look at the methods used in this result, it would be reasonable to conjecture that this team has found useful methods to reduce the search space and computational effort.
Congratulations to all that were involved in this result!!!
The problem, the results and further information may be found here.
(Unsubstantiated rumor has it that the NSA has in fact verified these results against their solution from the day of the introduction of this set of RSA Challenge numbers).