Lawrence J. Fogel Highlighted By The American Society For Cybernetics

Lawrence J. Fogel has been highlighted by the American Society For Cybernetics. See it here. For a complete list of cyberneticians, see here.

Lawrence Fogel is the father of the so called evolutionary programming, which his son, David B. Fogel, later improved and extended to work on real valued domains.

Via Natural Selection, Inc.

On The Analysis Of Biological Mutations

Browsing MEDAL Blogging, I got a nice link to a post at Olivia Judson's New York Times blog, see it here: A Mutual Affair.

That link was the pointer to another Olivia Judson's post: A Random Analysis. It deals with the biological nature of DNA mutations. Are they really random? Do they follow some kind of probabilistic distribution (or density) function? Are they weighted? Do small mutations happen much more often than the larger ones?

Of course, those questions are mine, not hers. :)

She states that mutations are small modification on the biological blueprint and, depending on the way they happen - small or large -, may affect seriously or not the living being's evolutionary path.

The manner through which mutations occur - be these deleting, inserting, and so on - can also affect the genome's configuration of a specimen. She says that when deletions are more frequent than insertions, the genome's configuration is prone to be compact and small, what may influence the specimen phisiology - those creatures holding small genomes own a heavy metabolic and growing rates.

Mutations are not only random, but also work different from species to species and the mutation flavours (deletion, insertion, etc.) also occur at different rates when taking into account other species. For example, in humans, deletions are more common and prominently working on DNA bases' repetitions, such as ATATAT or AGCAGCAGC. Why do mutations often occur on those repetitions? She explains:

"The reason mutations to repeated sequences are so common is that, in such repeats, it’s easy for the DNA copying machinery of the cell to slip and lose its place, and then put in too many repeats, or too few. (Even for a person, copying something like AAAAAAAA is harder than copying ACTGTCAG. Ahhh!) And although, obviously, these mutations can only happen in part of the genome where there is a repeated sequence, they happen at such a high rate that each of us probably carries as many new slippage mutations as “point mutations” — mutations that swap one base for another, say A for C."

Genomes, as Judson said, hold mutational hotspots and coldspots. These hotspots seem to be long repetitions of DNA bases, since "copying a long repeated segment without slipping is more difficult than copying a short one." Some creatures seem to have evolved their own kinds of mutational hotspots to aim for evolutionary profits - for instance, a pathogen developing the "stealth" ability before the immune system "eyes".

She advises that the manner mutations happen may trap a species in a specific evolutionary path, denying it the exploration of other evolutionary routes:

"But the mutational peppering has a consequence. As I mentioned at the start of this article, an important source of evolutionary novelty is when one member of a pair of duplicated genes evolves to take on a new function. In Neurospora [bread mold] this can’t happen: duplicated gene pairs get destroyed. Its use of mutations to defend its genome from invasion may have inadvertently blocked off some evolutionary paths."

Very nice article! :)


My Very Own Biased Comments

I think that there are so many lessons the evolutionary computation field may learn from Olivia Judson words. Of course, her small and layman article is just an initial step in that direction.

01. On Genetic Coldspots And Hotspots

For example, there is nothing in genetic algorithms that models the so-called mutational hotspots. On the contrary, take a common genetic algorithm book and the author - likely - advises you configuring the mutation rate between the range [0.0001, 0.001]. Crossover rates are set up at some point between [0.6, 0.9]. It seems that macromutations are avoided when it comes to genetic algorithms. When dealing with problems holding strong dependencies among theirs parameters, such a set up may even be harmful for the whole optimization process, since high crossover rates - along small mutation rates - tend to allow gene pool diversity losses, what can stuck the whole population in a specific local optima and/or optimization track. Sure, the GA community has made works on modelling genetic phenomena, such as gene linkage and viral infection.

Of course, detecting and handling the mutational coldspots is very valuable too, since we could avoid flipping bits (or a set of them) that must undergo small modifications or none at all.

I think that the optimization process of a given real world problem could benefit in some sense from that flavour of genetic phenomenon, since mutational hotspots and coldspots seem, at a first glance, to be useful for escaping local optima - remember: some problems require the modification of ALL parameters at same time to escape a local optimum. BUT... they could be harmful too. To avoid that drawback, mechanisms of self-adaptation could help to overtake that type of situation and could even implicitly identify mutational hotspots and coldspots, handling each one according to their respective nature.

Mutational hotspots and coldspots in non-decomposable problems should be addressed considering the relationship between those bits located at those spots and the others - sure, and between those spots' bits themselves. A well designed mutation operator would be very important here. (Again, a self-adaptation mechanism would be helpful.)

Upon the evolution without mutation, see her another nice article: Stop The Mutants!

Another important point has to do with the detection of those mutational hotspots and coldspots. Although there are some works from the Estimation of Distribution Algorithms (EDA) community handling problems that loosely resemble those genetic phenomena (see the Extended Compact Genetic Algorithm or the Hierarchical Bayesian Optimization Algorithm), they were designed under the statistical philosophy of the EDAs - an approach that throws away the genetic stuffs in genetic algorithms replacing them by statistical sampling and probabilistic distribution functions. Let alone that their bioinspired aspect is completely flawed, since in nature there is not an entity that captures data, analyses them, and etc. I guess those methods were designed much more as an optimization tool rather than intended to be a medium to increase our understanding of biological evolution. As optimization tools, those methods have a nice performance, mainly when it comes to discrete nearly decomposable problems. Summing up this paragraph: Despite a loosely resemblance between some genetic phenomena and the inner working of some EDAs, the later were not bioinspired.

For the EDA enthusiasts, I left a simple question: Is there a probability distribution that behaves in the same way mutational hotspots and coldspots do? :)

My hunch: I guess there is!

02. On Gene Deletion And Duplication

One of the few works I am aware of using abstractions of those two genetic phenomena is Professor Hans-Paul Schwefel's nozzle experiment, see it here: Optimization of a Two-Phase Nozzle with an Evolution Strategy. John Koza has used a kind of deletion and duplication too.

He got impressive results applying those genetic phenomena as an experimental optimization abstraction.






Those nozzle designs were obtained through a (1+1)-ES - without computer!

03. On Long DNA Base Repetitions

I have little to say here, since in "01" I have said a lot about a similar phenomenon. But, the way the genes interact in DNA seem to be much more important than their arrangement itself.

In the evolutionary computation realm, that problem has been addressed by linkage learning techniques in genetic algorithms and through correlated mutations in evolution strategies.

EvoWeb Interviews John Koza

Check his interview here.

I have not been aware that John Koza was John Holland's student along the 1960s.

Interesting interview, despite my own disagreements on some points.

Koza summarizes his path towards genetic programming (GP), the choice for LISP as the main computer language of early GP implementations, the initial papers, the hostility from the GA community at that time (early 1990s), his practitioner style, his achievements, the 1000 nodes computer cluster at Stanford, and so on.

The interview is from 1998.

:.::.::.::.::.::.::.::.::.::.::.::.::.::.:

P.S: There is someone that extremely disagrees upon Koza's statements.

:.::.::.::.::.::.::.::.::.::.::.::.::.::.:

Evolving Movie Contracts Through Simulated Evolution

MEDAL Blogging has a nice link to an application of genetic algorithms that I have not seen so far: movie contracts between distributors and theaters. See the whole story here.

The author of that investigation, Eunkyu Lee, implemented a hybrid method using genetic algorithm and game theory to help in that kind of business among the parts.

One of the current structures of those contracts is the so-called slide scale:

"These contracts usually come in the form of a sliding scale: in the first week, when the movie is most in demand, the studios get a larger share of the revenue - sometimes as much as 80 percent. As time goes by and demand decreases, the shares even out or reverse, giving theaters a more favorable cut of the revenue. These weekly revenue shares are negotiated on a movie-by-movie basis and are typically augmented by exception clauses for unexpectedly strong box office performances."

The method applied is helping to bring to light new ways to those structures:

"New research by Eunkyu Lee, associate professor of marketing in the Whitman School of Management at Syracuse University, questions the necessity of the complicated and costly contracting practice in the industry. Using a combination of game-theory and an optimization technique called genetic algorithm, Lee and his research partners analyzed different contract structures in simulated movie markets and compared their effectiveness and performance to the current sliding scale structure.

'The major finding of this analysis is that the contract between studios and theaters does not have to be as complicated as the current industry practice,' says Lee. 'Much simpler contracts such as a 50-50 split or a two-part tariff are just as effective as or better than the sliding scale, and they are also not as costly to implement.'"

Remember: "We'll always have Evolutionary Computation." :)

Evolving Genomics Through Simulated Evolution

Very good pointer from Epistasis blog, see it here.

It outlines the urgent need of computational intelligence approaches in genomics in general and what kind of (tremendously) high dimensional problems that field is facing nowadays. Jason Moore - the article's author - claims computational intelligence can ease those dificulties, softnening, in some sense, the problems' hardnesses.

The section four is of main interest for evolutionary computation fans, since it deals a lot with genetic algorithms, non-linearities in gene interaction, and so on.

Evolutionary Computation Researcher In Antarctica Has Found The Best Time Complexity Evolutionary Algorithm

My news webservice has brought to me the following evolutionary computation findings:

"An international mission based in Antarctica in a special lab has found the best time complexity evolutionary algorithm ever! Professor Pangloss Van Thunder-ten-Tronckh is the director of the project, which began along the late 1970s and had the former U.S.S.R. as the main manager beside U.S.A - Professor Trollov Buraninev is the director of the U.S.S.R. part. 'It is a finding that will open the doors of a new kind of science among all other sciences', said Professor Pangloss. He continues: 'This discovery is to evolutionary computation as the calculus was to physics and mathematics.'

Professor Pangloss states that his team was the first to solve an over a billion variables problems and they did it using just an AMIGA 500. He comments: 'Although some guys from Urbana-Champaign have claimed that they are the first ones, it is not true! As we are funded by CIA and the former KGB, our results never made the big mainstream publication magazines!'.

He claims he was the inventor of the Estimation of Distribution Algorithms (EDA): 'What outside Antarctica evolutionary computation researchers call EDA, was invented by me when I was an undergrad student during the 1950s! It was a homework that my advisor gave me.'

He also said that what Professor Hans-Georg Beyer has made upon the theory of evolution strategies is, indeed, a less elegant version of what Professor Buraninev's team had already done in 1981. Professor Buraninev states: 'I know very well the work of those German guys! Of course, it is just a lower quality flavour of my own research that I started in April 1st, 1977. What Professor Beyer has made is valid only under certain conditions, that is, Gaussian mutation, intermediate recombination, and comma/truncation selection - let alone that my self-adaptation mechanism is much more general than Schwefel's and/or Rechenberg's, since it can adapt to any kind of fitness/objective function! We made a complete theory of evolution strategies under all imaginable conditions, taking into account correlations, covariances, discrete recombination, noise, plus selection, comma selection, Gaussian mutation, Cauchy mutation, Gamma mutation, Geometric mutation, Bernoulli mutation, Poison mutation, Laplace mutation, uniform mutation, Zipf-Mandelbrot mutation, Student mutation, and so on... both univariate and multivariate distributions! And I did it in my special built Agat computer! And... remember: In Soviet Russia genetic algorithms rotate... YOU!!!'

Professor Pangloss comments about a strange guy that once entered his iglu: 'Yes... he was very strange! He stayed here for almost two weeks and he worn every single day only striped shirts! He promised me that he would teach us how to always win when betting in lottery. I thought him a nice guy and showed him my new invention - Programs that generates, through simulated evolution, others programs! I gave him a source code in LISP! To my very own desperation, years later I was told that he had invented an invention machine and was using my code on it!'

Professor Buraninev once met a Californian guy from La Jolla: 'Yes! That guy once told me that he would introduce me to a friend of his, her name was Blondie24. At a first glance, I thought her name a little strange, since girls do not use to put numbers on their names. But he stated that that was a new Western fad and that the girl was a true master in checkers. Oh, heavens! I would finally realize my Soviet Nerd dream: Date a girl which also is a checkers master! Then, he fixed a day for a meeting. I believed... how fool I was! While the girl, the so-called Blondie24, had not arrived, he showed me some of his father's work on automata. I decided to show him my new evolutionary algorithm flavour which is almost the same as evolution strategies, except on the selection mechanism and the self-adaptation procedure. The guy went insane! He immediately ran away from the Iglu Cafe! Some years later, I got aware that he was engaged in a new business endeavour and using my mind child!! The girl, Blondie24, has never appeared!'

Well, despite all those confusions along the years, Professor Pangloss is really happy to announce the ultimate finding of his lab team. He says: 'Finally, after 30 years of research, we are able to declare that we have found an evolutionary algorithm whose complexity is only O(n^-100-100)! This is the complexity of our algorithm in ALL classes of problems! Both decomposable - the easy ones! - and non-decomposable!!' So, where is such a poweful evolutionary algorithm? Professor Pangloss explains: 'Since we have been fooled by those guys from mainstream academia, we will not show how our procedure works! It is even impossible to rescue its inner working, because this was written on a sheet of ice that Professor Buraninev applied on his vodka research!'

But... what about computer codes and simulations? Again, Professor Pangloss has an explanation: 'Our codes, simulations, and computers were all eaten out by a blue whale! This animal is very common by this side of the world and even ate my favourite grad student!'

It seems that evolutionary computation will need to wait a little more to be completely formalized and put on formal grounds!"

Evolving Poetry Through Simulated Evolution

From Wired and posted at Bruce Sterling's blog, see here.

It is a genetic algorithm that evolves poetry. Each 200 generations a new population of poems is created. There is an interesting video outlining the genetic algorithm general working.

It reminds me of the famous Mark V. Shaney created by our blog friend Don P. Mitchell and put on USENET as a cyber-prank by Rob Pike and Bruce Ellis. See an instance here. I was told by Don Mitchell that his first experiments concerning Mark V. Shaney were performed using the Tao Te Ching text.

An excerpt from the surrealistic Mark V. Shaney composing ability:

"While at a conference a few weeks back, I spent an interesting evening with a grain of salt."

I wonder about the time when those programs really will compose human level literature. What about a Literature Nobel Prize for the next generation evolutionary algorithms?

Professor Schwefel's Keynote At EvoStar

Our blog friend Juan Julián Merelo Guervós is posting about the EvoStar 2008 event.

His first post is a short summary concerning the opening keynote given by Professor Hans-Paul Schwefel, see it here.

His recent post summarizes a little bit more the keynote presented by Professor Schwefel, see here.

Very interesting posts!

Upon the future of evolutionary computation, Professor Schwefel said that "the unexpected should be expected".

Professor Schwefel also mentioned a situation when a paper reviewer commented the following: "Why should other optimization algorithms be necessary?" This comment is strongly correlated to traditional optimization methods and the development of the evolution strategies, since some researchers - along the 1960s and 1970s - thought that gradient-based methods and others techniques (such as Gauss-Seidel method) were all the stuffs they needed.

He also spoke of the application of evolution strategies (under the form of the so-called experimental optimization) to a two-phase flashing nozzle optimization, which was performed without computers! Even today, it is not possile to calculate what happens within such nozzle: thermodynamically far away from equilibrium, drag between slow water droplets and fast steam, three-dimensional turbulent boundary layer with liquid sublayer, supersonic behind nozzle throat, etc.

There were several challenges to be overtaken when preparing the grounds to the evolution strategy, such as self-adaptation, non-elitist selection method, parallelism, and so on. He obtained inspiration in natural systems to implement solutions to those problems.

An important comment that evolutionary computation researchers should pay attention:

"He's commented that evolutionary algorithms are getting less bio-inspired in time, this is not good or bad, but it's more interesting for him to look at models than to have super-tweaked ultra-tuned purportedly bio-inspired algorithms."

Evolving Crystal Structure Through Simulated Evolution

From my news webservice I got this interesting sample of genetic algorithm application, see here.

An excerpt:

"[Julio] Facelli, director of the University of Utah's Center for High Performance Computing and a biomedical informatics professor, uses NCSA's Mercury cluster to predict crystal structures for organic molecules that are frequently used in pharmaceuticals, fertilizers, and explosives."

"Modeling the crystal structure of a given substance, Facelli and his team begin with nothing more than the atoms in the molecule and the nature of their bonds. They're looking for structures with the lowest energies, which typically mark the molecules' standard crystal structures or something very close. The problem is that this straightforward data and straightforward goal create billions of possible solutions. Just imagine finding the needle of the lowest energy in that haystack of possible structures."

"'An exhaustive search is not feasible, so we have to have a way to direct the search,' says Facelli. '[Genetic algorithms] are based on the principle of survival of the fittest. Trial solutions compete with one another in the population for survival and produce offspring for the next generation of tests. These algorithms offer excellent scaling properties, which make them good for large-scale parallel computing systems like those at NCSA and emerging computational grids like TeraGrid.'"

Here the article outlines through a simple manner the inner working of the genetic algorithm used:

"For example, an initial calculation on NCSA's Mercury may run 20 simulations on 20 different processors simultaneously, calculating possible crystal structures for a given set of atoms and their bonds. The energies for these structures are compared. The 10 with the lowest energies are kept, and the features of those 10 are mixed and matched to generate the structures for another 10 possible structures. Energies are calculated again, comparisons are made, best candidates are kept, and the cycle continues.

The 'mating operation,' as the mixing and matching is called, stagnates quickly, producing very similar structures over the course of thousands of generations. To combat this lack of variety, the genetic algorithm also introduces arbitrary mutations into the process, occasionally taking one variable from one of the best candidates and including a random number for that variable in the next generation."

Stagnation has been, since immemorial times, a hard drawback to overcome, mainly when using an elitist selection method. Taking into account that those individuals holding the lowest levels of energy are the best ones, then it is, in some sense, normal that the genetic algorithm got stuck quickly. Surely, there already are techniques to treat that, such as truncation selection.

If I were the author and considering he is using mutation and crossover, I would set up a high mutation rate (0.85 to 0.95) and a mild crossover rate (0.45-0.6), of course I would put the elitist rate (the number of fittest individuals saved per generation) as a rate of 1/7 of population size. Inversion could help too!

Swarms

Very good point from the masterminds behind the Grey Thumb blog. It's a link to Dr. Deborah Gordon's lecture on how ants know to do what they do, see here.

Understanding the inner working of ants' behaviour - and others swarms too - may be important to further the current state of those bio-inspired methods relying on that.

I read her book Ants at Work: How an Insect Society is Organized. She even applied neural networks to model the way that ants interact.

Maybe, the main lesson we may learn from those little insects is directly linked to the fact that ants (and other kinds of swarms) do what they do without a central control and the nest works fine. Sure, when it comes to the evolutionary computation realm, it is always sensible to remember that ants' nests own a very big population and in optimization (and machine learning in general) the population size may be a drawback if set up so big in some problems. Let alone that keeping a small population is very useful when dealing with expensive fitness/objective function evaluations.

Evolving Electrical Circuits Through Simulated Evolution

Another application of genetic algorithm to optimize circuit components' values, see here.

The resistor's and NTC thermistor's values must be set up such that the resulting curve (from the circuit equation) matches the curve on the chart below:



At a first glance, it seems a very simple problem, but, as the article observes, it may get hard to solve as the circuit complexity increases.

It remembers me of a tale of a senior student in a class of electrical circuits. The professor put some hard circuit problems to be solved through variable substitutions and so on. There were so many derivatives to be solved and etc. The senior student used a tricky way to solve them:

01. He organized all the equations.

02. He used the Laplace transform to all of them.

03. He put all the parameters on a matrix.

04. He solved all the equations through the Gauss-Jordan method.

I was not there, but some "persons" state that the professor refused his solution!!!

I wonder if that professor is the same guy which once said that 1/2 Ohm is not the same as 0.5 Ohm!!!!

Three Years!!!!

Hi, There!!!!

Today is the third anniversary of this humble and simple blog! :)

I acknowledge the old friends and the new ones too! :)

I hope that you have enjoyed some posts I have made along this time. I have learned a lot writing them.

By the way, it's nice to welcome the new friends, such as Juan Julián Merelo Guervós, Nojhan, Hrafn Thorri Thórisson, Michael Trick, and others!! :)

Thank You! :)