Jake Moilanen released an updated version of his genetic library patches [story] for the 2.6.10 Linux kernel [story]. He notes, "the major change in this version is the introduction of phenotypes. A phenotype is a set of genes the affect an observable property. In genetic-library terms, it is a set of genes that will affect a particular fitness measurement." He adds, "now multiple fitness routines can be ran for each genetic library user. Then depending on the results of a particular fitness measure, the specific genes that directly affect that fitness measure can be modified. This introduces a finer granularity that was missing in the first release of the genetic-library."
Additional improvements include a dynamic mutation rate, "if the current generation outperformed the previous generation, then the rate of mutation will go down. Conversely if the current generation performed worst then the previous generation, the mutation rate will go up." Jake points out that this should improve the situation where performance is increasing by minimizing the overhead of mutation, and conversely it should improve the handling of drastic workload changes by quickly adapting to it. Regarding performance, "SpecJBB and UnixBench are still yielding a 1-3% performance improvement, however (though it's subjective) the interactiveness has had noticeable improvements." Looking forward, some possible future improvements include utilizing pre-defined tunables, and saving tunings that performed well for a given workload allowing the algorithm to restore the tunings when the workload returns.
From: Jake Moilanen [email blocked] To: linux-kernel Subject: [ANNOUNCE 0/4] Genetic-lib version 0.2 Date: Tue, 15 Feb 2005 13:29:06 -0600 Here is the next release of the genetic library based against 2.6.10 kernel. There were numerous changes from the first release, but the major change in this version is the introduction of phenotypes. A phenotype is a set of genes the affect an observable property. In genetic-library terms, it is a set of genes that will affect a particular fitness measurement. Each phenotype will have a set of children that contain genes that affect a fitness measure. Now multiple fitness routines can be ran for each genetic library user. Then depending on the results of a particular fitness measure, the specific genes that directly affect that fitness measure can be modified. This introduces a finer granularity that was missing in the first release of the genetic-library. I would like to thank Peter Williams for reworking the Zaphod Scheduler and help designing the phenotypes. Some of the other features introduced is shifting the number of mutations depending on how well a phenotype is performing. If the current generation outperformed the previous generation, then the rate of mutation will go down. Conversely if the current generation performed worst then the previous generation, the mutation rate will go up. This mutation rate shift will do two things. When generations are improving, it will reduce the number unnecessary mutations and hone in on the optimal tunables. When a workload drastically changes, the fitness should go way down, and the mutation rate will increase in order to test a greater space of better values quicker. This should decrease the time it takes to adjust to a new workload. There is a limit at 45% of the genes being mutated every generation in order to prevent the mutation rate spiralling out of control. SpecJBB and UnixBench are still yielding a 1-3% performance improvement, however (though it's subjective) the interactiveness has had noticeable improvements. I have not broke the Anticipatory IO Scheduler down to a fine granularity in phenotypes yet. Any assistance would be greatly appreciated. Currently I am hosting this project off of: http://kernel.jakem.net [1/4 genetic-lib]: This is the base patch for the genetic algorithm. [2/4 genetic-io-sched]: The base patch for the IO schedulers to use the genetic library. [3/4 genetic-as-sched]: A genetic-lib hooked anticipatory IO scheduler. [4/4 genetic-zaphod-cpu-sched]: A hooked zaphod CPU scheduler. Depends on the zaphod-v6.2 patch. Thanks, Jake
| Why Windows is better than Linux | 16 minutes ago | Linux general |
| magical mounts | 1 hour ago | Linux kernel |
| Problem in scim in Fedora 9 | 2 hours ago | Linux general |
| The new Western Digital power saving drives | 2 hours ago | Hardware |
| Battery Maximizer Software | 22 hours ago | Linux kernel |
| windows folder creation surprise | 23 hours ago | Windows |
| Firewall | 1 day ago | OpenBSD |
| IP layer send packet | 2 days ago | Linux kernel |
| dtrace for linux available | 2 days ago | Linux kernel |
| Unable to mount ramdisk image using UBoot while upgrading to 2.6.15 kernel for a MPC8540 based target | 2 days ago | Linux kernel |
mainstream
Just curious... how long is this likely to take before it reaches a mainstream kernel?
AS scheduler need to be broke
AS scheduler need to be broken to fine granularity. If this genetic library can be used to tune TCP/IP stack tunable and improves performance than it could be prove beneficial. Unfortunately either you or your friends or some one has to come up to prove it's usability. Until lots of ppl may protest its inclusion in main stream kernel. It is my guess that combined improvements of TCP/IP and IO needs to be atleast 5% or more, or complete transformation of manually tunable parameters to phenotypes from kernel space...
Any way great work!
About time. Windows has been
About time. Windows has been using biologically-inspired technology to destabilise it for years.
Yeah, but if it shows a 3% im
Yeah, but if it shows a 3% improvement in an obscure, unrepeatable benchmark, isn't it worth it?
Worthless? Who cares?
Even if it'll be proven to be absolutely useless, it's still great work. At least it shows what can be done in GNU and/or free software world. Even such weird ideas can be realized no matter what some absolvent of economic faculty thinks about it.
patch cleanly against 2.6.11-rc4
For those who are interested, these seem to apply cleanly (with some offset fuzz) against a vanilla 2.6.11-rc4 source tree using the -p1 option:
$ cd /path/to/kernel/src
$ cat /path/to/genetic-*.patch | patch -p1
Four words
Keep it simple stupid.
Thet is the whole point of th
Thet is the whole point of this. Parameter tuning is a complex task. If it can be automated with a genetic algorithm to determine the best configuration, so much the better.
exactly. all these tunables a
exactly. all these tunables are extremely complex, and the interactions between them are simply impossible to understand. the genetic algoritm works very simple: try some out, if it works good, use it, if not, dump it.
Where are the logs to analyze the performance?
Why not A*? Why not Cellular-Automaton? Why not Neural-Motor? Why not Kohonen? ...
Analyze!!!
KISS!!!
Isn't it obvious? It's becau
Isn't it obvious? It's because "genetic algorithms" are, like, "in" and cool these days. Despite not actually being algorithmically better than lots of other stuff, and quite often worse, it caries with it that special warm fuzzy factor. You can bet it wouldn't be picked up by sites like this if it weren't for the name either.
I think it's the wrong solution
If the problem is complex, certainly the answer is not to make it even more complex by semirandomly changing the system's tunables. The answer ought to be to make the system simpler.
So I oppose inclusion of this sort of stuff even though I think it's useful in discovering the ways you have to change kernel tunables to improve system performance given a particular metric. So in that sense this project is invaluable aid.
In the end, we must have better heuristics in the kernel. This patch should simply be a stepping-stone to find those heuristics.
Ooh! You distroyed my illusio
Ooh! You distroyed my illusions. I tought this genetic algorithm randomly mutates the code of the kernel, not just the tunables. Now, _that_ could be interesting. Only keeping those mutations which "work" (i.e. pass all tests) AND have improved performance. Of course, a recompile after each mutation is a bit too much fuss. So first we'd need to
a) Rewrite the Linux kernel in Lisp (or any other language that supports reflection)
b) Find a way to do reflection in C.
Is b) possible? (I suspect it must be, see, C is Turing-complete in the end). Or no? Don't tell me no >;(
Bah!
Both A and B are too hard. Just use TinyCC which pretty much eliminates the recompile overhead.
Of course, you'll have to reboot and run a test suite. Writing and optimizing said test suite is left as an exercise for the reader.
mwhahhaa, that's great. Add a
mwhahhaa, that's great. Add a compiler to the kernel, then compile it and insert itself into itself as a module.
Mix, Pray, Repeat...
Better Yet
Setup a cluster of User Mode Linux hosts with some kind of code mutation routine...I swear it'll work ;)
1) Evolve the kernel
2) ???
3) Profit!
Stupid idea. There's no way o
Stupid idea. There's no way of veryfying that the changes in the kernel code wouldn't crash the kernel completely, and it's obvious that almost any random change would cause the kernel to work less well, if at all.
Much better to tune parameters for an algorithm that's already known to work.
You are correct that paramete
You are correct that parameter tuning is more sensible now.
Offtopic Side note, following is a VERY LONG-TERM question, it is not meant to be answered in our lifetime for now. I suppose.
1. We know real life forms likely evolve without harming themselves along the way. yes/no?
2. Can we have a self-evolving kernel that will evolve and not harm itself along the way? yes/no?
Obviously we are extremely far from reaching such a stage, but one-day if we ever found some concrete kernel/computer/robotic evolution progresses that exhibit such behavior, the lesson learned might be tremendous when you cross-examing your finding with real life forms.
1. We know real life forms li
No.
Evolution is trial and error. but errors won't survive for long.
If this would be possible, you wouldn't need to go the way, you can jump to the end right from the start, because you know for sure which steps to take (if you wouldn't know, you could harm yourself).
Evolution is trial and fail.
Evolution is trial and fail. Yes. Code evolution can also be trial and fail. That's why the tests. That UserModeLinux idea is good. Run the compiled kernel in user mode and test it. Or run it as an other domain under Xen. Only replace the current working kernel if the new passes all tests. So the main problems that remain are:
There are commercial operating systems that can do it, but I guess they still require that some internal data structures are not changed, etc. But this is not impossible.
Entropy is the problem.
Biological evolution is totally different from computer program evolution. Biological organisms have no other tests to pass in their life than that they reproduce. You can not test that a kernel works, because there is no such similar test.
Your "test that the kernel works" is not good enough. Obviously the current kernel already passed all those tests. You would only replace the current kernel with new kernel that also passed the same testsuite. That testsuite can not produce any evolution to any direction at all, because it can only preserve the status quo. As soon as the kernel fails some test, it's dead.
Think about it. What would be the evolutionary goals of your kernel test system. How would you evolve a new feature into kernel? Say, support for new graphics card?
(I'm the original anon). A mo
(I'm the original anon). A more immediate point is that if you were mutating kernel code while the kernel was running, any bad change would crash the kernel. And there is in principle no way of ensuring that a change to some piece of code won't cause it to crash, because it reduces to the halting problem.
So an evolving kernel would just crash all the time.
No you're not. Please don't l
No you're not. Please don't lie. I don't know who you are but I posted the original not you :|
My previous comment was not clear.
With the first paragraph I meant that you can not define a simple-minded test that determines whether kernel is good or not because evolution does not really work with that kind of hard constraints.
Think about birds that grow wings or fish that grow legs. It appears that animals that have needed some kind of air control have fared the better the bigger their wings have been, and the better suited for controlling falling, because being able to control your descend in air can be the matter of life and death and even slightly better wings do help. Thus, there's an evolutionary pressure for improving the wing shape with respect to what the animal is doing with its wings as it survives.
It's similar to how fish that have evolved eyes on just one of their sides because they like to press themselves flat on the bottom of sea and in that case the eye in sand is not very useful, and there's evolutionary pressure to move the eyes to only one side of the organism.
In order to be able to use evolutionary processes, you must have some kind of selection criteria that gives you a scale, makes some of your virtual organisms more likely to survive than others. Just doing a simple black&white test is not good at all because you can't possibly evolve anything with it. All you will evolve is some kernel that exactly passes the test suite but might not actually work for any real world task. The kernels need to compete with other kernels in obtaining some real new features, and must get rewards for making progress to the right direction.
That's what evolution takes: lots of small steps that gradually take you to the right direction, no random at-once changes that suddenly produce something new.
That's why the original crite
That's why the original criteria "it must pass all tests and perform better than the current kernel". I think plain black&white tests would do. We just need to time them. That gives the scale.
Building the environment for code evolution
The two previous replies raise valid points and observations. Based on the feedback,
(Maybe this discussion is only meaningful if you look at it from AI viewpoint. You can ignore entire post if you only want to talk about the pure computing kernel for today)
1. Yes it is trial and error, error won't survive for long. Agreed. That is why in real physical world, for example, you need quantity, some will fail, but some will survive, as a whole, the species will continue given enough breeding rate to sustain it.
2. When a human baby is born, he lives on "initial clean state". What he doesn't know could harm him, nevertheless, he doesn't stop in the "initial clean state", he will explore to learn the world around him. natural evolution has given him enough protection upon initial contact with this physical world. That is enough to protect him of some immediate dangers, but not enough to cover all dangers. It also helps that he has nurturing parent/elders offering food and protection. He will learn and gain knowledge along the way, Some time he do things he should be careful, example, got a small burn when playing with fire, he will suffer but will recover with the experience imprinted in his mind. Maybe some are not lucky and gotten worse result, its part of life.
Don't you think one day we will eventually see such an AI-kernel?
Now come back to more low-level discussion, if you have a massively linked computer networks, you could take the similar idea of UserModeLinux or Xen to next level to spawn thousands of instances of such evolving kernels, yes some will fail, but some will succeed, those successful instances become candidate in your new gene pool for new spawning. Initially the giant network nodes offers parental care, as successful childs instance are born and mature, they may take over the parental duty for their own child instances. This environment will surely requires a lot of resources, just like human being has library to keep the learned knowledge, I could elaborate more, anyhow, you get the picture.
Obviously how to do this, what causes the kernel to mutate and the meaning of "successful" are not clear in this context, and all such discussion are purely academic for now since it is of no immediate concern to Linux people here, but it never stops me from wondering what if ....
Yes it is trial and error, er
Yes it is trial and error, error won't survive for long. Agreed. That is why in real physical world, for example, you need quantity, some will fail, but some will survive, as a whole, the species will continue given enough breeding rate to sustain it.
But how will you evaluate whether or not a kernel has errors? The only current known way to get a reliable kernel is to test it for months under heavy loads. If you're trying to test a kernel in real time you need to do it in seconds. It's not even possible to verify that some particular piece of code won't crash (halting problem), let alone verify that it will do something useful.
[snip baby example]
Don't you think one day we will eventually see such an AI-kernel?
I think you chose a bad example. Babies are borne with massive amounts of innate knowledge and ability. Learning is more akin to a process of changing parameters, or filling out data structure schemeta, than randomly changing the structure of the system and hoping for the best.
The truth is, the kernel already evolves in exactly the same way that babies have evolved. Good kernel code has been kept and extended, and bad kernel code as been cut. Individual babies and kernels do not (and could not) evolve in the strict sense of the word -- natural selection operates on groups, not within individuals. A human who randomly mutated his genes in the hope that he'd get an advantage would quickly kill himself, and the same goes for a kernel.
Now come back to more low-level discussion, if you have a massively linked computer networks, you could take the similar idea of UserModeLinux or Xen to next level to spawn thousands of instances of such evolving kernels, yes some will fail, but some will succeed, those successful instances become candidate in your new gene pool for new spawning.
Again, you have no practical criterion for success. Are you going to stress test each kernel for months to decide whether or not it's fit? How will you test new features when you don't even know what they are?
You seem to think that these problems might somehow be overcome, but I can't understand why you're so optimistic. All the available evidence would seem to suggest that a self-mutating kernel is a terrible, terrible idea. As I've pointed out, there is not even any sensible analogy between such a kernel and evolution in the natural world.
Right. Maybe there should be
Right. Maybe there should be two versions of the kernel, one "production" and one "evolving". Maybe the evolving one would need special or virtual hardware. Example:
Adding support for a new graphics card:
You construct a physical or virtual machine with that graphic card as an unknown black box in it. You run the "evolving" version of the kernel on the machine, and one of the tests in that it must successfully draw a circle on the screen (virtual hardware may be more feasible here, easier to verify). Maybe it would take months for the kernel's small random mutations to result in the new video driver. Then, writing it by hand is clearly a better choice. But computing power of machines doesn't seem to stop to increase in the foreseeable future. Maybe on a machine in 2015, It'd only take half a day.
Given that there are an infin
Given that there are an infinite number of possible programs, it seems unlikely that it would be possible to evolve any particular one of them. Remember, most programs will not even draw anything on the screen, so it is not possible to choose between those programs in terms of fitness. Evolution is not a magic process. It only obtains under certain conditions, i.e. when each individual mutation makes some contribution to the fitness of the organism.
Regarding computing power, I doubt an increase in it would make any difference. As I've just argued, the process you're describing is so hopelessly unlikely to work that any increase in computing power that's conceiveable within the next 50-100 years would have no effect.
Also, you still have the problem of testing drivers once they have evolved. It takes weeks/months of widespread usage to test a driver properly, and the chances are that any driver that had been evolved would be full of subtle bugs.
Evolution is not a magic proc
Evolution is not a magic process. It only obtains under certain conditions, i.e. when each individual mutation makes some contribution to the fitness of the organism.
That's false. Evolution is completely random. Attributes that are neutral could survive just as attributes that contribute to fitness.
Testing the drivers can be automated. I really don't see why it needs human interaction... Of course it needs well written tests.
:)
Anyway I might start implementing this. The 6th generation language[tm]. You just tell the compiler what you want the program to acomplish (ala Prolog), and it generates random code and mutates it randomly until the resulted code does what you want it to. Well, anyone has an idea on how to compare the complexity of deducing the solution with clp(FD) and generating code for that versus this random code evolution? Maybe it's slower and thus doesn't make sense.
RE: Evolution is not a magic proc
Evolution is not completely random... There are a few subtleties here.
First, the "fitness" test is anything you want it to be. Just looking for "error free" operation is one, but what about relative fitness? (Didn't all this start with a parameter tuning discussion?) How about this: Choose the fastest 20 versions, discard the others, and create the next generation. The idea is to select a subset of the current generation and let them mix-it-up for the next generation, with a few mutations thrown in. The selection is done with the fitness criteria.
Second, Evolution is not "completely random." It is directed by the selection / fitness-testing process. Some random mutations are brought in, and there is some random mutation thrown in to make sure the space around the present generation is explored some, but generally each successive generation is guided along a path toward "better performance."
Third, genetic algorithms do well in highly complex situations where it is difficult or impractical to produce deep analyses. Look for the book "Blondie 24" for an example.
Fun stuff.
I am clearly indicating up fr
I am clearly indicating up front here my thoughts are oriented toward Artificial intelligence. I am definately not talking about a standard Linux kernel that RedHat can sell :)
However, the lesson learned might be equally important in many area.
I am trying to to see the kernel one day as an electronic life form, a self evolving autonomous hybird(it does depend on having resources such has hard disks, memory, circuitry as internal conduits, cover and casing as physical protection, electricity to be alive, failing component mimicking aging, networking paip to external world, software/services to attract external entities like flowers and fruits of plant to attract insects to help spread the seeds, constant bombardment of old and new protocols/service on network that either enhance or endanger its existence, misc.
We already have computer systems that attempt to learn, they started with initial amount of knwoledge and build additional on the way, example, by pattern matching, visual, audio misc. Just days ago I think slashdot or somewhere talked about systems that given enough reading will start to decode meaning..(sorry I dont have the URL). 99.999999% will argue that why kernel, it should be software services. But I think this Hybrid may want to be able to one-day, detecting that its components failing, will pack its stuff and search for new home. Only a highly intelligent autonomous hybird kernel will have low to high level skills in this transition in hostile networks. I am reluctant to say just like physical world, it may have to engage in resource conflict among various entities, will it then exhibit tribal behavior by alignling with hybrid kernels from the same origin to compete for resources? I am sorry to say such hybrid kernel may also monitor SecurityFocus List to find holes to explore new environments...
There are too many things flying in my mind, for focused enhancement, This could be one of the example scenario. When we are haplessly thrown into a foreign country with different culture/lanaguage, we will have very difficult time initially, but sooner or later after many years, some will eventually adapt and even able to understand and speak the local dialects. If I have a self-evolving kernel, arm with all the protocol code/knwoledge from ethereal project, can I put it into a hostile network to watch old/new familair and unfamiliar protocols and find ways to finally decode its meaning? it needs to evolve as we cannot be constantly feeding new protocol info or updates from Ethereal project:) If I put thousands of such hybrid everywhere and give them capability to communicate, can they share the load to find ways to understand? or will they decide to form a local community among the hybrid and ignore the foreigners? :)
The primary focus of some hybirds may be to survive and reproduce, aka the original computer virus problem. IN human world you do not need to be IQ above 180 high intelligent being to survive, a lot of people are living just fine with lower IQ, low EQ, or genetic defects. Therefore to say 100% correct test suite passing is not necessary. Will the hybrid then decide to evolve and junk out capa that no longer suitable for its primary motive? Will it degenerate to simple life form? I don't know. IF this happen, does it validate pattern what we already observe in human society? A bloatware OS/App system that finally return to sensible state? Some ask why junk capa? Because capa takes resources to maintain? Limited resource is a problem. If this hybrid is born in slower CPU with lowerIQ pool, will it decicde the best strategy might be simpler and easier defensive posture with alliance? Or like some people after years of high profile way decided to return to simpler lifestye?
When hybrid junk away capa to gain resource efficiency for survival, they will lack certain skiils, will this hybird evolve to bargain with each other? barter trading if needed? can we put in a coomunication base that will let the hybird generate new electronic terms that only they understand to facilitate they language development?
Just too many things to ask, if such hybird kernel exists...
You've not really responded t
You've not really responded to any of my points, but here goes...
I am trying to to see the kernel one day as an electronic life form, a self evolving autonomous hybird
Right, and I've argued that this is an unworkable concept for a number of reasons (see above). In particular, the idea of "self-evolution" is rather problematic.
We already have computer systems that attempt to learn, they started with initial amount of knowledge and build additional on the way, example, by pattern matching, visual, audio misc. Just days ago I think slashdot or somewhere talked about systems that given enough reading will start to decode meaning.
There are no such computer systems. It's possible to extract some meaning from texts using computers, and there are various methods of doing it, though none are very successful. All of the most effective systems start with a large knowledge of the language they are parsing. The idea that significant knowledge can be learned by some unspecified process of "pattern matching" is a myth, which is unfortunately very pervasive. It is of course possible to perform statistical analysis on large bodies of linguistic data and get very useful results, but it is not possible to magically "learn" how to comprehend language in this way.
Anyway, make your mind up. Do you want the kernel to learn? Or evolve? Or both? Or what? Or do you just feel like using a new set of buzzwords today?
When we are haplessly thrown into a foreign country with different culture/lanaguage, we will have very difficult time initially, but sooner or later after many years, some will eventually adapt and even able to understand and speak the local dialects. If I have a self-evolving kernel, arm with all the protocol code/knwoledge from ethereal project, can I put it into a hostile network to watch old/new familair and unfamiliar protocols and find ways to finally decode its meaning?
It seems unlikely. It is probably not possible to decode the meaning of a network protocol simply by monitoring network traffic -- you need to know what the protocol is for, and no analysis of the network traffic can tell you this. Humans are able to learn new languages because we have a built-in knowledge of what languages are for, and also because we share a large body of common-sense knowledge. It's tempting to think that network protocols may be learnable in the same way as languages, but I suspect that they serve too many diverse purposes.
I agree it would be amazing if we had ultra-intelligent self-modifying kernels. However, it seems pretty clear that such things could never exist, since they would have to have a number of magic abilities to be useful (e.g. a magic ability to develop drivers for new hardware, a magic ability to decode network protocols, etc.) Humans certainly do not have any magic abilities of this kind, and so belief in the future existence of computer systems which do seems to be entirely faith-based.
It is probably not possible t
It is probably not possible to decode the meaning of a network protocol simply by monitoring network traffic -- you need to know what the protocol is for, and no analysis of the network traffic can tell you this. Humans are able to learn new languages because we have a built-in knowledge of what languages are for
Altought I agree with you more than the other poster, and that "pattern matching, visual, audio" etc are just buzzwords, but here is how humans (babies) learn a language:
They observe others speaking, and associate the answers/reactions with the questions/statements, morphems with objects/feelings, etc (computers don't have feelings. But they can associate morphems/words with the broader context). After a while they start to mimic others. That's all. Of course later on you go to school and learn grammar, but you can already speak the language perfectly by that time. And naturally, "someone" has to speak that language first.
Nope, that's not how they lea
Nope, that's not how they learn language. There's lots of research in linguistics and psychology supporting a very rich innate language learning ability (whether or not you go so far as to believe in a Chomskyan universal grammar). Virtually no-one believes in a naive associationist account of language learning these days.