Slashdot Mirror

BTW: Not exactly the link I was looking for, but same topic: http://www.genetic-programming...

In a final real-world test, Koza chose a filter circuit to solve a design problem that a scholarly engineering journal had deemed too difficult to solve. "The tenth-order elliptic asymmetric bandpass filter was touted as being difficult to design, but we were easily able to solve it," Koza said.

To be fair, Koza did have to double the size of the population used to evolve a bandpass filter-up to 640,000 circuits-thereby multiplying the time it took the computer to evolve a "best" circuit. He had to devise a more extensive fitness measure by which the members of the evolving population were measured against one another. The problem took four days to run, on a 64-CPU parallel processor.

This article is from 1996, so I guess the same algorithm would be even faster now.

While it is true that evolutionary algorithms can be used to do an end-run around patents, it can also be used for new patents. In my opinion, this is what Genetic Programming, Inc. hopes to do: generate patents through evolutionary algorithms. (See, here, for example, on genetically derived patents -- in section 2). Dr. John Koza, as far as I know, teaches at Stanford and also runs this company, and he is considered the father of genetic programming. He has patents on genetic programming as well.

As far as I know, he has never explicitly given permission for any of his patents to be used license-free commercially or noncommercially.

The reason I have used "as far as I know" and "as far as I know" is that this should be an adequate defense of claims against libel. It is my own opinion and belief that Dr. Koza would not stoop to actually suing based on negative posts such as this one.

--Rob

While it is true that evolutionary algorithms can be used to do an end-run around patents, it can also be used for new patents. In my opinion, this is what Genetic Programming, Inc. hopes to do: generate patents through evolutionary algorithms. (See, here, for example, on genetically derived patents -- in section 2). Dr. John Koza, as far as I know, teaches at Stanford and also runs this company, and he is considered the father of genetic programming. He has patents on genetic programming as well.

As far as I know, he has never explicitly given permission for any of his patents to be used license-free commercially or noncommercially.

The reason I have used "as far as I know" and "as far as I know" is that this should be an adequate defense of claims against libel. It is my own opinion and belief that Dr. Koza would not stoop to actually suing based on negative posts such as this one.

--Rob

Oh you mean like this?

Well, he already has patents on all the methods.

Perhaps they'll be blocked by Koza's patents on genetic programming.

No matter how neatly programmed or how much time people spend writing a program, truth is software is highly unreliable.

Yes and no. I agree with you, that software TODAY is highly unreliable. Software TOMORROW will not be. Why, just the other day... okay, ten years ago... I wrote a program that evolved to find the square root of two. I knew the ultimate answer, of course, but the computer didn't, so effectively the program it used to generate the answer was filled with bugs. It guessed wrong, mostly, but it converged on the correct answer within a few generations.

Now generalize this to, "I know what I want the program to do. I just don't know exactly how to get it to do that." At least SEVEN years ago, programs evolved to come up with electronic circuit architectures for amplifiers with various parameters.

The machines will program better than we ever could.

--Rob

Following years? How about now?

http://www.genetic-programming.com/humancompetitiv e.html

http://www.human-competitive.org/

(2006 results aren't posted yet...)

I was at the GECCO06 conference (Genetic and Evolutionary Computation COnference) when the Human Competitive awards were handed out. The first place winner went to a guy whu evolved an oscillator that used HALF as many capacitors and resistors than the industry standard one. The second place winner evolved input parameters to Schrodinger's equations that enabled him to model a certain chemical reaction 10 and in some cases 1000 times faster than the earlier best result in the literature. And the rest of the entries were fascinating as well.

http://www.genetic-programming.org/hc2006/entrants _table.html

The 1st and 2nd place entries were #5 and #6 respectively.

Why can't you accept the fact that there is a being greater than man? A being that has the power to create the universe in which we live. A being that set up the rules that we discover via science. That being is God, and he is the one that is responsible for us being here today.

The evolution-creationism discussion is not about whether there's a being greater than man, but about whether that being (if indeed he exists) used evolution to create us or not.

My position in this discussion is that I can use evolution to create new things, and if I can, then certainly so can God. Creationists seem to claim that God can't do that, for some reason.

For more information about using evolution to create software, take a look at John Koza's work on Genetic Programming. It works, and it easily refutes all the silly Intelligent Design claims about what evolution can't do.

Furthermore, I'd like to stress that the 168 hours of creation are a personal interpretation of the bible, and most christians do not interpret Genesis 1 quite that literally. Consider that the world around you is God's creation (if indeed God exists at all, for which I don't have any proof, but I do think he does), and teaches you just as much about who God is and what he does as the bible does, and certainly should be considered a more accurate source than your (or my) own fallible interpretation of the bible.

This is an interesting concept, but it is hardly a new field/application. (see 'Gentic Programming', by Koza, for example. Website).

Actually, I kind of liked Koza's technique of applying genetic programming to synthesizing analog transistor circuits. GP was able to evolve circuits that square-rooted, frequency discriminated, filtered, amplified with specific parameters, and so on -- and even develop novel circuits. To me, this was proof that GP could solve problems in a space that was immense (the universe of all circuits containing under, say, a few hundred transistors), and incredibly bumpy. Well, maybe not quite so bumpy -- perhaps the circuits evolved so that a small change didn't adversely affect the circuit.

The interesting thing is that the genetic program evolved not a circuit, but a set of instructions on building that circuit. Then the circuit plan was built in RAM and simulated. So the GP was several steps removed from what was tested.

More info on this is in Koza's Genetic Programming III: Automatic Programming and Automatic Circuit Synthesis

--Rob

Although others have pointed out that the fight isn't over the FAT system - I have noted that no one has even mentioned the mainframes and minis which came long before micros ever appeared.

I've worked on Univac 1108's, 1106's, NAS 9000s, IBM System 3's, Honeywell systems, and the original Vax's as well as some PDP systems. These all used the 8.3 filename convention and is where (I believe) the usage of 8.3 filenames under DOS came about. (Remember original DOS used EBCDIC which is an IBM standard and the PC was to originally be a "very small" mainframe.) All of these mainframes had a FAT system in place for the usage of the disk drives. So there are decades of prior FAT usage and setup. So FAT and the 8.3 filenaming convention is a done deal.

The usage of long/short names and the mapping of long/short names one to the other was done under Unix years before Microsoft even came along. This was called linking. Further, Digital Equipment Corporation, under VMS, came out with a method to do the same thing prior to Microsoft ever having done this. It is such an obvious misuse of the patent system that, as another poster put it, this is just another example of how broken our government is in this respect.

The truth, as I see it, is that we are in a war over whether or not our original systems of Patenting and Copyrighting things, as created by the people who put pen to paper, will survive. When the rules were written; it was another time. A time when it took months or years to do even one thing. (Like filing for a patent.) In today's world things are vastly different and, with the push of a button, you can submit a patent on anything to the PTO. This reduction of time means that, at some point, it becomes an exercise in logic programming to generate new patents. The basic idea behind the Patent system was to guarantee time to an individual - because it took so long to recoup your investment - so they could make a profit. Today, some inventions are overnight successes. Granted - not all, but even the creation-to-market time span is shortening. Especially when there are devices out there that can create 3D objects. So the question becomes - is the Patent and Copyright system broken because of misuse - or because they are an outmoded methodology? I think the latter.

Maybe it's time we re-invented the Patent and Copyright systems so they work in the modern world. For instance, centralize where all payments on Patents and Copyrights go. Standardize on how much has to be paid per P&C. (Like 1% of a company's gross has to be set aside to pay P&Cs. Or maybe a default amount per unit sold could be come up with. <Whatever is come up with - it should be fair - as in "Atom smashers are a lot more rare than bubble gum."> This would eliminate some P&Cs being sold at some high amount versus others which are paid only minimal amounts. And yes - there are some really stupid P&Cs out there. This is just a general methodology that I am writing.) Standardize how much is to be paid on Patents and Copyrights. Standardize how often payments are to be made to the holders of Patents and Copyrights. Standardize on how long Patents and Copyrights can exist. (I personally am in favor of the life of the author plus twenty years and no more. I am also in favor of making it illegal to change this in any way, shape, or form because of what we just went through via the DMCA. Or at least make it illegal to change it without the consent of the people. Not Congress and/or the Senate as both have been shown to be untrustworthy in this area.) Standardize top level categories. Create a standardized entry number system. Entry numbers into the system could be assigned based upon the importance/weight of an entry. (In other words - truly unique ideas are at the top. Those t

Good point, you have elaborated fairly well on my frost pist.

I have tried to point this out on multiple occasions, but slashdot readers are hung up on the fact that some people seriously abuse patents. Not everyone does.

In this case, the patentability of an invention provides a direct comparison between genetic programming (or in fact, any AI that purports to be able to design or invent software or hardware) and human intelligence.

With such a yardstick, we can directly measure the progress that genetic programming is making as a science.

Other than that, John Koza (the inventor of GP and [less known fact] scratch-off lottery tickets) doesn't seem to me to be the type to hold patents over peoples heads.

DNA is [like] spaghetti code because nature has been tinkering with the system for billions of years like a bad programmer.

How ignorant of you to say that. There was an article in the Feb. 2003 issue of Scientific American about genetic programming - the creation of new devices and electronic circuity by computer.

It basically involves starting out the core components (resistors, inductors, capacitors, etc) and a design (for a voltage-current converter, perhaps). A supercomputer is able to rewire the circuit through basic evolutionary processes including crossover, copying, and extinction, and come up with a much more efficient circuit.

The resulting circuitry is so effective and original that there have been designs that earned approval from the patent office. They're so complex, much like nature's genetic code.

Sure, it might look like spaghetti code - but you mean to tell me, nature is a bad programmer? Heh.

Google search on genetic programming
Everything2: Genetic programming
What is Genetic Engineering?

Software (and now hardware too...) that is inspired by DNA recombination.

In his 1950 paper ''Computing Machinery and Intelligence,'' Turing 84 described how evolution and natural selection might be used to automatically create an intelligent computer program.

We cannot expect to find a good child-machine at the first attempt. One must experiment with teaching one such machine and see how well it learns. One can then try another and see if it is better or worse.

...

What do we mean when we say that an automatically created solution to a problem is competitive with a human-produced result? We think it is fair to say that an automatically created result is competitive with one produced by human engineers, designers, mathematicians, or programmers if it satisfies any one or more of the following eight (first two only shown here) or any other similarly stringent criteria:

A. The result was patented as an invention in the past, is an improvement over a patented invention, or would qualify today as a patentable new invention.

B. The result is equal to or better than a result that was accepted as a new scientific result at the time when it was published in a peer-reviewed scientific journal.

does this method work at all?

Take a look at this room A 1000-Pentium Beowulf-Style Cluster Computer half way down the page.

A simple proof of evolution is to look at genetic programming (for example here, here and here).
Just look at the classic example of ants collection food. It is beautifully described in John R. Koza's great books (1, 2 and 3) on the subject.
Just imagine adding a fermone layer to freeciv and let the random search for a superior player begin.

A simple proof of evolution is to look at genetic programming (for example here, here and here).
Just look at the classic example of ants collection food. It is beautifully described in John R. Koza's great books (1, 2 and 3) on the subject.
Just imagine adding a fermone layer to freeciv and let the random search for a superior player begin.

Koza et al have been doing this for years via Genetic Programming (www.genetic-programming.com).

But in some cases, these are legitimately quite difficult problems. Remember you're searching a many-dimensional space (R^n for n large) for the point that maximizes some function. The hassle is when evaluating the function is itself an expensive thing. Every tuple might represent a costly experiment.

For instance, suppose you're designing airplane wings. You've come up with a generalized wing design that has twelve parameters. You want the 12-tuple that gives the best wing. In the days before computers, you would have run experiments in a wind tunnel. But with a peak-Cold-War black budget, you couldn't have made 10^12 wing prototypes and tested them all. Nowadays we can skip the wind tunnel and simulate the aerodynamics of a wing on a computer, but it's still a non-trivial effort. If each 12-tuple involves one CPU-hour, those 10^12 experiments will still take 114 years on your million-processor parallel computer.

Evolution is a partial search algorithm for the genome that, within its environment, reproduces the most rapidly. Every individual genome is an experiment that involves the entire lifespan of at least one organism. If you're talking about giant Sequioa trees with multi-century lifespans, that's a slow process no matter what you do.

Throwing a lot of computation at these kinds of things is a good idea. I laud John Koza's effort in that direction. But even if we use the masses of Jupiter and Saturn to build networked petahertz nanocomputers, there will still be interesting problems for which exhaustive search remains infeasible.

As pointed out, it was John Koza, a professor at Stanford. He's built a 1000-node beowulf cluster of PII-300s. You can see pictures of it at www.genetic-programming.com. According to the site (which appears down right now, so this is from memory), they've evolved several (17 sticks out in my mind...) algorithms that are either patented or at the least competitive with the best known solution to the problem. The simple fact that you can say "find me a program that does X" with evolution and have it be competitive with what a human can produce is amazing.

No such luck

certain operating systems will likely beat you to the punch

;)

Actually thinking of software generated by genetic programming, etc. which produces code that obviously never passed through human fingers.

The Father of GP (John Koza) may disagree with me - he runs genetic-programming.org and more or less invented the field. He's also known for his vigorous defences of GP: anybody know of real applications?

A somewhat more complete description of GP can be found at Genetic-programming.com.

I was suprised that there was no information at all to be found regarding genetic programming. This method builds a large population of random computer programs and then refines them through genetic mutation to accomodate a specific task. Darwinian selection ensures that only the most fit programs survive, and less useful ones die off quickly.

I have been doing some work involving genetic programming lately, and have found it to be an amazing tool for finding creative solutions to complex problems. The problem domain I have been training my genetic program to solve is purely mathematical, but it seems to me that the technique could easily be adapted to find solutions to some of the tougher problems in AI, including but not limited to: data mining, natural language processing, and parellization.

I read somewhere (can't find the reference right now, sorry) that some work was being done whereby the genetic programs were being evolved that could themselves create neural networks. Each genetic program could be considered a template for creating a neural network. This seems to me like the most likely means of creating a software that could eventually pass a Turing test. I won't get into the self-conciousness debate here.

One method is with classifier systems, where you evolve the rules that determine the output based either directly on the input, or a chain leading from some input. It starts with a pool of random bit strings which are evolved based on their success. The rule used is determined by a bidding scheme.

Another method, which is about as general as you can get, is genetic programming (GP). GP involves creating a set of functions and terminals and randomly generating a set of parse trees using them. Each of these programs is evaluated, and based on that the standard genetic algorithm operations are performed for form a new generation. Essentially, genetic programming is automatic programming, if given the right function and terminal set. Unfortunately, it would probably be too slow a process for this competition.

Both of the above methods have been proved over and over again. Classifier systems, for instance, have been used to run a simulated oil pipeline (with leaks, blockages, etc). Starting from a random population, it achieved human competitive results. Genetic programming has produced results that are not only human-competitive, but also infringe on pre-existing patents.

They do exist in a variety of implementations. What you refer to is the "island model" for evolutionary algorithms, of which there are many variations on the theme. Another use for parallel architectures is for mitigating computationally expensive operations, which typically are the individual fitness calculations.

Here is an example of a Beowulf cluster being used for genetic programming.

Now, these Netfinity machines at best are 550 MHz Xeons (according to the best model I saw in IBM's Homepage) so I seriously doubt they outrun the Beowulf cluster of 1000 Pentium 2 350MHz machines (and the controlling host) being used for Genetic Programming, were they in fact clustered together to achieve the type of speed benchmarks IBM was after, rather than being used for a useful purpose as these are. Do they even outrun the 70 machine cluster of 533MHz DEC Alpha's that had previously been used for Genetic Programming? I doubt it. I tried to submit the Genetic Programming thing as an article once a while back, but it was rejected for some reason or another, even though someone posted about it in a forum like this once long ago, and people seem to continuously forget about this amazing cluster and what possibilities it presents to the computing world. Imagine if you told it to try to create a better version of itself? Once we have the storage capacity (the Petabyte, theorized to be necessary to store the totality of a human consoiusness) what would happen if you give it a pipe to the internet and told to to absorb data, correlate it with data it already has, "remember" or "forget" the data as is considered relevant based on things it already "knows"? Anyway. that's beyond the point... Which is this IBM cluster isn't amazingly new or ground breaking at all, and I have to doubt IBM's claim as fastest.

I'm currently taking John Koza's (the inventor of GP) class on genetic programming at Stanford, and his company has built a 1000 node beowulf cluster to solve GP problems. Genetic programming is a powerful, generic, and highly parellizable method of solving difficult problems - GP has already managed to produce some patentable designs, and distributed.net could make potentially make a real contribution to humanity if they were to apply themselves to GP or GA.

Yes, the problem is here much too simple to be interesting, but you can see them groping towards the idea of genetic programming, which is extremely interesting from a philosophical standpoint, and is also a powerful way of automatically evolving computer programs that solve difficult problems. There's a nice article by Salon here on the topic.

The list only counts those systems where linpack has been run. I imagine that there are several beowulf (and other self-built)systems that are actually achieving more computational throughput, but aren't going to be noticed. Also, I'm sure the government doesn't release everything it has working on satellite images and what not. Overall, I'd imagine that a large subset of the people who are actually using huge machines for real work (rather than academic research) wouldn't take the time away from their work to even run linpack on their system.

As one example of such a computer, Professor John Koza has a 1000 node (Pentium II 350Mhz) beowulf machine for his Genetic Programming Inc. ( GPI's web site ) research group. He's running genetic programming applied to difficult problems on the machine (such as automatic analog circuit design), and is getting a nearly linear speedup because of the embarrasingly parallel nature of GP.

Cheers,

David Andre
my web site

disclaimer: I worked with Professor Koza for several years and helped him build some of his previous machines.

Check out this site: genetic-programming.com they have quite a lot introductory information and examples etc.

Last I heard, John Koza (at Stanford) was in the process of building a 1,000-Pentium Beowulf-Style Cluster Computer for Genetic Programming.

Koza has been doing very cool things with GP for a long time, ever since he was at Michigan working with John Holland.