Introduction, Main Issues, Experiment, Results, Review
The prevailing model of evolution from low-order creatures to high order ones, is the Darwinian Evolution Model. This model proposes that change in the genotype (created by the various gene operators, such as random mutation, sexual breeding, etc.) leads to new phenotypes. Since 'better' phenotypes survive better, more of them pass their genes to their offsprings, thus leaving the better genes in the 'gene-pool' and potentially creating new, better species.
However, before Darwin theory, Lamark suggested a different model. He had observed that the phenotype, in its lifetime, adjusts to its environment by means of learning and improving. His model proposed that these adjustments modify the genetic material passed to the phenotype's offspring, and that improvements to the gene-pool were mainly a result of that process (e.g. a giraffe that stretched its neck to reach higher leaves would have offsprings with longer necks).
It is now widely believed that Darwin's model is a much better representation of the evolution in nature. Still, There are instances in which Lamarkian evolution could prove helpful, and therefor it should not be discarded entirely. It should be noted that “evolution” in human societies is basically a Lamarkian process: each generation adjusts its social order and behavior by its interaction with the surrounding social environment. It then passes that social knowledge on to the next generation by directly teaching and 'socializing', rather than by assuming the next generation would develop similarly or better in response to the same social stimulus. It should also be observed that Artificial Life (at least in its present condition) works in a different environment than that of natural evolution. Ackley and Littman conjecture that in this artificial environment the Lamarkian model may serve as a method of creating better phenotypes faster.
The following summary will briefly examine the main issues arising from the use of Lamarkian Evolution in an Artificial Life framework. It will describe an experiment conducted by Ackley and Littman to illustrate these issues, present its results, and offer a critical review of their conclusions.
Main issues in Lamarkian Evolution
The Lamarkian model attributes great importance to the process of acquiring traits by means if the phenotype's adjustment to its environment, which we shall refer to as “learning”. While in the Darwinian model learning modifies the phenotype alone, Lamarkian evolution assumes that learning modifies the genotype, so as to pass the acquired attributes to the offspring directly.
Clearly Lamarkian Evolution could cause much faster convergence towards a “good” individual, since wisdom obtained throughout previous generations’ lifetimes is directly embedded in the offspring's genes. Still, one should bear in mind that fast convergence is both a blessing and curse: while it could lead us to the global maximum fast, it could also converge to a local maximum from which escape would be difficult. The described experiment will suggest a method of moderating the convergence rate without relinquishing the advantages of Lamarkianism.
A potentially much greater problem that the Lamarkian model raises is the need to change the genes as a function of the success of adjustments made to the phenotype. This necessitates finding the derivative of the phenotype's success with respect to the bits in the genotype. While normally only the function mapping the genotype to the phenotype is needed to create the individual, here a derivative of the reverse mapping is necessary. It is quite possible that this requirement hinders greatly the appearance of Lamarkian evolution in nature (Ackley and Littman hypothesize that it is the great complexity of transforming genetic DNA molecules into a phenotype which makes the reverse mapping impractical and renders natural Lamarkian Evolution impossible). And yet, in Artificial Life experiments, there are no chemical transformations, and it is sometimes possible to find that reverse mapping. For these cases Lamarkian evolution should be considered. The described experiment “overcomes” this hurdle by dealing with a special case where the genotype and the phenotype are the same.
To present the case for Lamarkian evolution Ackley and Littman devised an experiment in which a “creatures” try to find a solution to the “max-cut” problem on a clumpy graph. The problem is, given a graph, to divide its vertices into two groups, so as to maximize the number of edges between vertices of different groups. The problem is NP-complete, and when the graph is made of dense clusters with sparse inter-connections, the solution space contains an exponential number of local maxima. It should be noted that existing approximation techniques solve the problem quite well.
In the experiment, each individual is made up of N bits corresponding to the number of vertices on the target graph, which encode a graph partition. A population of M individuals is initialized with random bits, and evolves according to the rules below in the hope of finding the max-cut on the target graph.
A basic Lamarkian model could have been to let the creatures “adapt” using some type of hill-climbing method for a given amount of iterations (which we could call a generation). Then a fraction of the population whose scores (max-cut solution success) were the worst would be eliminated, and the genes of some "parents" would be combined into new offsprings (in what could be called a reproduction step). The next generation would then follow. The rules in this set-up are Lamarkian in the sense that hill-climbing qualities achieved by phenotype in its lifetime are passed on as genetic material to the next generation, since they are used as genes in the reproduction step.
However, the basic experiment suggested above does not refer to the problem of fast convergence. Ackley and Littman present a novel solution to this problem, by specifying who can mate with whom on a “geographic” basis. Their model-world is a torus, divided into 128*128 cells, where each cell is occupied by 64 creatures. Creatures from a given cell can mate only with other members of that same cell. Also, in every generation one individual from each cell “travels” to a near-by cell (a random small distance in a random direction), and so the populations mix. This “geographically” based mating pattern, along with relatively slow migrating habits, tend to limit the rapid convergence to small “communities”, while migration between communities maintains border areas of constant change through the mating of different individuals.
Another novel aspect of the experiment is the “time warping” algorithm used in the learning (hill-climbing) phase. The idea was to allow creatures that are still improving to perform more hill-climbing steps, instead of allotting time to creatures whose hill-climbing steps no longer produce improvement. This algorithm allows shorter and more effective hill-climbing phases, thus requiring less computing power.
There are several other details in the experiment to which I did not refer, but I believe they have less diverse applications.
Ackley and Littman conducted the experiment with two different sizes for target graphs (and hence for the genotype/phenotype bit string). In both cases they used relatively large graphs: 320 vertices and 768 vertices. While the experiment with the larger number of vertices failed to converge, the smaller one converged, producing a creature representing the perfect solution after about 18000 generations. A comparable Darwinian test did not converge to the perfect solution after 20000 generations, and its improvement slope was such that the perfect solution did not seem likely to be found even after ten times that many generations. Experiments with the same problem using only hill-climbing techniques were conducted only on much smaller graphs, and therefor are not quite comparable.
A study of the development pattern in the “geographical” setting of the experiment scheme shows that a very dynamic environment was produced. Converged “colonies” developed, while “border zones” appeared between “colonies” which converged to different (non-perfect) solutions. In them individuals who migrated from the colonies mated and created new and occasionally better solutions. The better creatures created in the border zones then migrated back into converged colonies, and spread their genes there.
There are two main issues that bothered me in the article. The first is the relevance of the experiment to Artificial Life research, and the second is the numerical results of the experiments, which in an appropriate scale are somewhat less than an irrefutable evidence to the Lamarkian approach's superiority.
While the case for Lamarkian Evolution is stated most convincingly at the beginning of the article, the experiment conducted is basically one of parametric search, and the whole scheme could be seen as an alternative to other stochastic parametric -search algorithms (such as stochastic hill-climbing). Many Artificial Life experiments involve complex interactions between creatures in the experiment and their environment, their genotype -phenotype mapping is not trivial, and the mapping from a phenotype representation to its success in solving a problem is also quite indirect. The article presents no solution to the problem of finding the reverse mapping derivative, which is a central problem in nature, and does not disappear in most artificial settings presented in our seminar.
A second source for concern is the numerical results of the Lamarkian experiment test as compared to the Darwinian “control” experiment. A graph of the improving results over 20,000 generations is given in the article, with its Y-axis (success measurement) covering the range 97,000 – 1,000,000. In this scale, after 10,000 generations, the Lamarkian experiment's results are quite near 1,000,000, while the Darwinian experiment's results are around 98,500. The article does not explain the measure used for success, but assuming it is linear, we see a difference of only 1.5-% in the results. Given all the trouble of the Lamarkian approach in a more realistic A-Life setting, it is not clear that such a small difference is actually worth it. --====================987654321_0==_ Content-Type: text/plain; charset="us-ascii" --====================987654321_0==_--