Lambda the Ultimate

Putting recombination or mutation rate under genetic control has been studied and it was found that it drops down to zero far faster than you would want. This is because the genome is optimizing the average fitness of its children, while you are aiming to optimise something more like the fitness of its best child (you are much less risk adverse).

I thought about that for a while, and realized something; if the thing is trying to maximize the average fitness of its whole population, I want to benefit from (and measure success in terms of) the average fitness of the population.

And this means using an Evolutionary Algorithm (ie, trying to maximize the performance of randomly drawn teams working together) rather than a genetic algorithm (ie, where individuals compete on the basis of each individual being "the" whole solution). This is a good idea for other reasons too. It should give survival value to anything valuable that is also rare in the population until it's not rare anymore, which is exactly what we want to avoid premature elimination of valuable traits. Also, having the population adjust the proportions devoted to different 'species' based on their contribution to average error should mean that the whole adjusts faster to online changes in fitness conditions.

Although I haven't coded it yet, I think it's more likely to be able to statistically detect fitness gradients and valuable alleles that would otherwise be very hard to find in genetic algorithms applied to programs.

So, thanks for that thread of thought; the more I considered it the more I realized that maximizing the population fitness is exactly the right thing to do.

And now I've spent the last day coding....

I think you are assuming an unchanging environment. You also assume mutation rates are uniform, rather than site-specific. Both these things are not true. In fact, the evolution of mutation rate is an exciting topic. See for a good but slightly dated review: Baer, Charles F., Michael M. Miyamoto, and Dee R. Denver. “Mutation Rate Variation in Multicellular Eukaryotes: Causes and Consequences.” Nat Rev Genet 8, no. 8 (2007): 619–31. doi:10.1038/nrg2158.

Also see this interesting paper: Barrick, Jeffrey E., and Richard E. Lenski. “Genome Dynamics during Experimental Evolution.” Nature Reviews Genetics (October 29, 2013). doi:10.1038/nrg3564.

Some of the things that I think are of particular theoretical importance for biological evolution are mentioned in my essay: Lamm, Ehud. “The Genome as a Developmental Organ.” The Journal of Physiology 592, no. 11 (2014): 2283–93.

First of all, thank you very much for the references to papers. I shall spend today's shift reading and consider it valuable research. Can I find resources online, or need I visit the local U library and request interlibrary loan?

One of the reasons I had though using an EA rather than a GA to be a good idea, was that in an EA, relatively rapid adaptation to a changing environment is possible without much mutation. So I really don't see how it involves assuming an unchanging environment.

An EA produces averaged output and so allows and preserves far greater population diversity, and the prevalence of diverse individuals bearing a rare trait valuable in the changed conditions can rapidly shift from (say) 1% to 10%, whereat the trait is expressed tenfold more in the averaged output. The requirement for mutation under changing environments is drastically reduced because adaptation of the averaged output can happen fairly rapidly without it.

I had been considering mutation rates differing per individual (which is the minimum granularity possible to evolve mutation rates) and wondering whether it would be a good idea to break them down further than that (by both individual and funge node, for example).

Concatenative languages are potentially convenient for simplifying mutation at the syntactic layer. One can even build nice EDSLs and constrain our programs to be expressed as a subset of concatenative primitives words, so whether it's "stack based" isn't especially critical.

But, having explored this idea a fair bit, I think we'd be wiser to look instead to the semantic layer, safe typeful mutations. Perhaps based on Editing Functional Programs Without Breaking Them by Amsden, Newton, and Siek.

Given a body of code, a 'safe mutation' is a (program → program) transform that preserves the type of the program, but not its behavior. It is possible to develop a set of safe mutations, and hence create a language for mutation of programs.

Conveniently, a composed sequence of mutations might be expressed as a string in a concatenative language. We could also evolve the set of useful safe mutations at the level of a population.

The evolutionary approach to algorithms isn't something I've ever really gotten into (though I've occasionally thought I'd caught a glimpse of something I never got a chance to pursue... oh well), but it seems to me to entail a profoundly different sort of algorithmic language than human programming, exactly because evolution doesn't think. It seems that scientists trying to explain evolution so that lay people will appreciate how powerful it is have at last settled on describing it as if it were sapient. Unfortunately, this tends I think to result in underappreciating actual sapience. Evolution, I think, is one of a variety of things in our world that can address a vast search space but altogether lacks sapience. As noted here, it seems one wants a language where mutations have a relatively high chance of producing similar behavior to the original (partly because we want faster evolution and partly because we aren't really looking for general evolution but rather for evolution toward some goal we have in... mind). The less likely a mutation is to produce a useful result, the less common mutation must be in order to keep mutation from destroying population fitness; if mutation is likely to be detrimental but is very rare, almost all mutations will get weeded out, and the very rare useful mutations will cause very, very slow evolution. This seems to fit well with the ridiculously high fidelity of DNA copying, and the stunningly long time-scale of real-world evolution.

For the immediate problem: In a programming language for humans, the next step beyond 'pure stack-based' would seem to be making stack-states first-class values; data-stack states would be essentially environments, while program-stack states would be essentially continuations. This however would seem to produce a language in which blind mutation would be very inefficient. Humans might find such a language far more useable since a human expert doesn't actually contemplate the entire formal search space of options, which might lead us to try to design a more restricted formal language to exclude the possible mutations that the human programmer wouldn't bother to consider — except that the deep "language" the human is using to search is self-constructed rather than externally imposed.

(If I seem ambivalent about the whole evolutionary approach to AI, that's probably because I am ambivalent about it; I'm aware that some of the processes involved in human neural development are somewhat evolution-like, but I believe the resulting phenomenon of sapience is rather profoundly different from evolution in character, in some way that's absurdly difficult for evolutionary search to stumble onto.)

I'm a believer that the Evolutionary approach to AI can produce useful components. I am under no illusions however that evolution thinks (see also: "Blind uncomprehending idiot"), nor do I believe that anything produced by evolution alone will get anywhere near what we think of as adult intellectual capabilities.

What I've been observing is that there seems to be a practical limit to the degree of complexity that can be evolved. Mutation is destructive of information, and to preserve complexity you have to preserve information.

So you can set a mutation rate high when you're doing what is essentially a random search for a simple behavior or attempting to optimize a known behavior. But when searching for a complex, unknown behavior you need lower and lower mutation rates and/or larger and larger populations in order to preserve the complexity that's working while continuing to occasionally experiment. Both of those things, lower mutation rate and larger population, make the process take much longer. So - the bigger the problem, the slower it works.

In fact the switch from RNA in unnucleated cells to DNA protected in cells with nuclei and DNA repair mechanisms, etc, was probably all a necessary part of a lowered mutation rate that allowed more complex organisms to evolve. Higher complexity implies slower evolution and ability to adapt. (Hence today we worry about relatively simple pathogens that have rapidly evolved to be resistant to antibiotics, while we terrifyingly complex humans haven't been able to evolve nearly as rapidly to be resistant to those pathogens).

Having several independent evolving mutation rates applied to different parts of the genome seems to help; important complexity that must be preserved, over time, gets preserved best in those individuals that for whatever reason happen to have it in their lowest-mutation-rate sections of genome. Then, if there are also high-mutation-rate areas where experimentation can take place, that can happen without destroying that important information.

Even so, evolution can never really get more than "structure." Babies are born knowing everything evolution can teach them. Every refinement of adult thought over infant thought, every adaptation of an individual to the opportunities, threats and niches unique to that individual, every application of memory or symbol, has to be learnt in other ways.

So.... 3.65 billion years or so of a highly parallel Evolutionary Algorithm has given us brains (an UNBELIEVABLY complex type of meat), but everything that makes us unique or gives us individual capabilities has to be learnt by that brain in the relatively short span of a lifetime.

Likewise, anything produced via GA or EA, no matter how wonderful and no matter how many technical hurdles (like the above conundrum of mutation rate) we overcome, is at best unlikely to be viable if it uses EA or GA to decide its real-time actions and responses.

Finally, you may be right about brains capable of human-type thought being incredibly unlikely for evolution to produce. Fermi's paradox is staring us in the face after all. It might even be that brains as used by terrestrial animals are the astronomically unlikely thing to evolve in the first place.

I think part of the reason geneticists have trouble with memetics (I include Dawkins here) is that they're so sure evolution can only happen with very high fidelity. Memetics, imho, has evolved insanely fast with an insanely high rate of mutation over most of the memome. (I reckon there are some things that do get copied very faithfully but those are abstract patterns that we don't have the means to identify accurately.) The reason memetic evolution can tolerate these high rates of mutation over parts of the memome is that a tool is available, if very cunningly exploited, to vigorously cull non-viable mutations: the hosts of a memetic organism are themselves sapient. The evolutionary "intent" of the memetic organism is potentially independent of the sapient intent of any of the hosts, but it's entirely possible for memetic organisms to evolve ways to arrange that the motives of the sapient hosts will inadvertently further the evolutionary motives of the memetic organism.

As you say there is mechanism in place to vigorously cull non-viable mutations. But there are other mechanisms in place too; First, memomes are Larmarckian; We the hosts actively work to extend and refine memes that we find useful, rather than just passing them on.

Second, there is a vigorous corrective mechanism that frequently transforms maladaptive mutations into adaptive ones, which is that many a good idea has its origins as an ambiguously expressed or misunderstood bad idea. We the hosts are always interpreting language, asking ourselves, what possible interpretation of those words could be the underlying idea that causes them to seem sensible to the speaker? And frequently someone with a really stupid idea or ignorant of basic limitations, produces a string of words that a more knowledgeable person can either interpret as a good idea, or as a misstatement of a good idea, which the more knowledgeable person wouldn't have otherwise had.

This is part of what Larry Wall had in mind when he designed (yes, I'm using the word "designed") Perl. Wall is, among other interests, something of a linguist. Specifically, a tagmemic linguist. He was designing by analogy to spoken languages, and as a tagmemist, wanted most of the strings people somewhat familiar with the language might produce, whether by intent or accident, to have a definite and potentially useful semantics. Believe it or not, according to tagmemic thought it's a secondary consideration for that to be one they intended. But it should be one that will make sense to them having observed it and which having observed they may find useful later. So while Perl is utterly awful from the perspective and by the standards normally used to evaluate programming languages, it is something of a design success in that people who get used to using it become "fluent and flexible" in a way more reminiscent of spoken languages.

Yeah, the gene–meme analogy is poor at best; the analogy gets much more impressive imho at the level of organisms, where I see birth, death, reproduction, inactive replicative material, and differentiated organs. (Sorry to link my blog, but, to be perfectly clear: yonder.) Though it's not obvious to me this has any immediate applications to this thread since we don't, at our level of technology, have the option to write blueprints for our devices that call for transistors there there and there, capacitors there and there, and sapiences at those strategic points over there. (Or do we know how to do that? The word crowdsourcing comes to mind.)

I did not know that about Perl.

I think the contrast between Religion and Science as organizing principles of human thought is rather like an analogy to the shift between RNA in unnucleated cells and DNA protected in cells with nuclei. ie, these organism types thrive under different levels of mutation frequency.

Religion requires oral culture for its transmission; its substance, in terms of ideas, stories, values, etc, is among the most sophisticated that can be easily transmitted orally, subject to leaky human memory and reinterpretation with every retelling. Scientific knowledge is relatively recent, and requires literate culture for its transmission; its substance, in terms of ideas, experimental histories, conclusions, etc, must be recorded in a form that does NOT change every time it's retold, or else the whole system doesn't work. Scientific thought simply can't thrive without literate culture. The drastically increased copying fidelity (ie, the much lower mutation rate) enables a much higher level of complexity to be retained and transmitted.

So while religion (and things even less fixed in form than religion, such as superstition and magical thinking) can adapt more rapidly to human need or desire the way RNA-based organisms adapt more rapidly to different hosts and conditions, the increased copying fidelity of literate culture has made historic and scientific studies, analogous to DNA-based organisms, possible and these organisms both require and benefit from the ability to sustain and refine much greater complexity.

...the differences can be exaggerated. Science can't survive in oral society, certainly couldn't evolve there, and yes that has to do with copying fidelity of at least parts of the memome. But religion can live in literate society, and there the two taxa compete vigorously. (What happens in internet society, I'd guess we don't have enough of a baseline to judge yet.) Despite obvious anatomical differences between the taxa (which religions may encourage people to ignore), they also have anatomical similarities. We know about various "discarded" scientific beliefs mainly because we're taught them as part of our indoctrination in the scientific ideas we are supposed to believe; ditto various "discarded" religious beliefs.

The connection to PLs is, of course, weak; though PL wars are notoriously religious...

RNA organisms still thrive in today's world where we DNA organisms have the temerity to think we've become dominant. It's not as though the conditions under which they thrive have ceased to be, nor even diminished. In fact many have adapted to take advantage of us DNA organisms. That high mutation rate still serves them well in terms of rapid adaptability, although it limits the complexity of any particular exemplar.

Likewise the existence of conditions under which science can thrive has not diminished the conditions that religion requires. And to some extent religious memeplexes have adapted to take advantage of the lowered mutation rate now available as well.

Apropos of programming languages, however, the requirements for our blind uncomprehending idiot programmer remain unchanged. The "genomes" of these organisms must allow the preservation of latent traits, and the recombination operations that the idiot is capable of must make it at least somewhat possible that recombination will reactivate latent traits as well as refine expressed traits. Further, the genome has to express its own mutation rates applicable to different parts of itself, so that when important structures happen to be expressed in a low-mutation zone of the genome (or one that via recombination becomes a low-mutation zone) they can be preserved.

These are completely inhuman requirements for any kind of semantic expression language. But humans aren't blind uncomprehending idiots about the semantics they want to express.

I favor higher-level views of memetic organisms, which is also why I avoid the term memeplex as (in my experience) it's used to describe less coherent, less highly evolved creatures than I see populating the ideosphere. That's more a matter of preferred metaphor, though; I think we're basically in agreement. And yes, the rules change profoundly when the basic agents of replication are sapient (which, again, I see as a major reason geneticists haven't been able to come to grips with memetics; it's just too alien for them). The tricky thing about evolutionary tactics in AI, seems to me, is that neural development in genetic biology isn't free-form evolution — it's a process devised by evolution at its subtlest, and from the perspective of sapient beings with their naturally modular thinking, evolution is profoundly subtle (so much so that if one tries to imagine a sapient mind behind it, one ends up envisioning something very like a deity).

Advanced organisms should be an occasion for some degree of this "try out a mutation before committing" business, since an organism has to live a while before it gets a chance to reproduce. Sexual reproduction as a source of mutation would also seem to provide a certain degree of somewhat-robustly increased mutation rate.

Tl:Dr version:

I think recombination is essential to robustness and doubt that masking or altering its effect with a mutation is a good idea.

Especially if the 'test-flight period for mutations' rule is in effect. In that case an individual subject to both is benefiting from an untested (mutated-recombined) version of the genome while reproducing another untested version (recombination alone).

Full version:

Recombination has other effects that are important. I doubt if it's a good idea to mask those effects by adding mutations that might disguise them. Especially true if the 'test-flight' rule applies to mutant recombinations, because then the organism is benefiting (or not) from the mutation while passing along an unmutated (and untested!) version of the recombined genome.

Recombination remixes to try new combinations of the parent's genes. If our blind idiot programmer has primitives that work the way it works with them that means they also have some new combination of the same traits both parents had, which might work synergistically or interfere with each other. And if building anything complicated, recombination is much more immediately necessary than mutation.

Recombination gets really short shrift in a lot of implementations. Lots of people skip it all together and do what amounts to a resource-wasteful parallelized hill-climbing with mutations-only. But recombination is the only way individually-weak but synergistic traits get reinforced together, and the only way individually-strong but interfering traits get selected against. And I think selecting for synergistic and against interfering traits is something you have to do continually in order to produce a population of complex genomes that, despite complexity, can work without self-interference and can tolerate or take advantage of the next mutation.

I remember thinking some years ago, listening to a talk about this stuff, that the Hull-Dawkins distinction was missing from the treatment, with the associated distinction between phenotypic and non-phentypic genes. In case of sexual reproduction (note, not replication but reproduction; this was one of the points in my treatment of memetic organisms, that one may be able to identify organisms by their reproductive process, which is a different, higher-level process than mere replication) — in the case of sexual reproduction, recessive genes serve a similar purpose to your 'test-flight' device. But of course, looking for a solution is different from evolving a population of variant individuals.