Worse Is Better!

David Tow has written an instigating article on the role artificial intelligence (AI) methods are playing and will play concerning its use in e-business.

He outlines a set of major methods he believes will become a hotbed for e-commerce and web intelligence:

1. Evolutionary algorithms
2. Bayesian networks
3. Fuzzy logic
4. Swarm intelligence
5. Neural networks
6. Intelligent agents

Except for #4 and #6, I have seen so many enterprise applications of the remaining methods -- being pretty honest, not only enterprise ones, but a highly diversified spectrum of uses of those methods (#1, #2, #3, and #5).

But what David Tow argues is the increasing use of those methods in e-commerce and web intelligence. I think his arguments are well reasoned, since those kinds of endeavours are recent phenomena -- they arose after the Internet and the World Wide Web --, it is normal AI methods have not been widely applied in them so far.

His future trends prognostics are even more instigating:

"The enterprise of the future will increasingly depend on the wide range of rigorous artificial intelligence algorithms and methods outlined above, to drive its operations at all levels of management. 

Decision Engineering techniques are at the forefront of this revolution- while IBM has recently set up a new services unit focussed on applying predictive modelling to automate business decisions.  

These techniques will continue to be enhanced and packaged in different combinations, to provide immensely powerful problem solving capability as well as integrating with the global intelligence of the Web 4.0.  

Major decisions incorporating sophisticated levels of intelligent problem-solving will increasingly be applied autonomously and within real time constraints, in order to achieve the level of adaptability required to survive in an ever-changing and uncertain global environment.

I do not think traditional methods are sentenced to die out, just take a look at the operations research guys that have bred a shining research city on the hill since the early stages of that field around the 1930s and I do not consider they will suddenly vanish from the surface of this planet.

The author did not point an important issue: Better not always means better. The better definition here is not intented to slur other methods, but it embeds what an enthusiast of some research area thinks about his own field/research: Not so rarely, we can see researchers colourfully speaking when it comes to their own research. I consider that a sensible attitude, but hyper-hyped words do not help to solve problems in the real world and the real world, as an old saying states, is a cruel place that may tear into shreds any hype. The chills of the AI Winter can still be felt.

Other important point has to do with the user base a given method owns. Someone may have designed the best time complexity algorithm, the best neural network, the best fuzzy set tunning method, and so on, but if they do not have a significant user base, all those methods are useless -- they may serve as an interesting academic investigation endeavour, but not for application in the real world, since no one would be using them. The ultimate example that illustrates this is the so called worse is better approach:

[...] [S]omething can be "inferior" but still "better". For example, to a particular market or user, software that is limited but exceptionally simple to use may be "better" than software that is more comprehensive but harder to use.

I hope I am not slurring the work of anyone else out there, but the Elitist Simple Genetic Algorithm is, in my humble and insignificant opinion, a perfect example of worse is better in evolutionary computation.

No, I do not consider the elitist SGA a bad method. On the contrary: It is an amazing method devised by Professor John Holland and it has succeeded in so many fields -- thanks to the embedded knowledge its users have included in it and its simplicity. BUT, the elitist SGA, despite its drawbacks, is the most applied genetic algorithm (and evolutionary algorithm) until now, even though there are some new genetic-based techniques that are direct descendants of the SGA, such as EDAs (Estimation of Distribution Algorithms), that were made to overcome some drawbacks inherent to the SGA. Fifteen years after the publication of Baluja's seminal EDA paper, the SGA still is strong, well alive, and bigger than all of its offsprings. Worse is better! :)

Even the SGA siblings (evolution strategies, evolutionary programming and genetic programming) have not got the wide range SGA has. The SGA dominance and its offsprings struggle to obtain a bigger amount in the application market is, in my opinion, an example of worse is better. Would the SGA be an evolutionarily stable strategy? :)

So, I do not believe future problem solving will be strongly tied to artificial intelligence methods. At least not in a fatalistic manner as some believe. Those methods will play a role -- major or minor -- in different problem solving situations, but not to the point of relying 100% on them.

Evolving Proteomics Through Simulated Evolution - UPDATED

Excellent post by our blog friend Martin Pelikan, see it here.

It deals with the use of a genetic algorithm to select a subset of conformations explaining the experimental scattering profile best.

Despite choosing geophysics as my grad school career, I consider proteomics a big deal and it would worth a lot investing time and dedication pursuing a career in that field.

It would be interesting if Martin told us what kind of genetic algorithm he applied (EDA or classical ones).

------------------------------------------------------------

Martin Pelikan explained the evolutionary algorithm they used for evolving protein conformations:

"[...]The genetic algorithm we used is similar to a simple GA, but slightly crossed over with UMDA. We started with this simple method inspired by some prior work in this area and since the method worked, we used it. We tested it on artificially created examples and it worked great, and it gave reasonable results also for the real-world cases. More should be published soon, I hope."

------------------------------------------------------------

Thank you very much, Martin! I hope you achieve great results!

Estimation of Distribution Algorithms Video Tutorial

Martin Pelikan has uploaded his nice tutorial upon Estimation of Distribution Algorithms, see it here. The tutorial was given at GECCO 2008.

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.

Evolving Grid Computing Optimization Through Simulated Evolution (Updated)

Interesting stuff I got via my webnews service: Evolving towards the future of science: genetic algorithms and grid computing.

The main objective has to do with the optimization of job scheduling on a computing grid. Through this, lots of valuable resources are saved, such as energy consumption, CPU time, human resources, and so on.

It seems that the genetic algorithm (GA) applied is the good old CGA or Canon Genetic Algorithm (likely holding some slight modifications, for instance elitism, stochastisc tournament selection, etc.), what stands for bit flip mutation, one point crossover and a fitness based selection scheme. Of course, I may be wrong about that, since I have not read nothing (except that news) upon the genetic algorithm they use for that task.

From the article:

"Standing for Distributed Optimal GENEtic algorithm for Grid applications Scheduling, DIOGENES quickly determines the most efficient way to schedule of a set of jobs on a computing grid, optimizing both time and resources in the process."

I have noticed an interesting (strange?) phenomenon which has taken place in the, let's say, New Wave Of Genetic Algorithms (NWOGA): It seems as though no one is applying them! From my surveys inside the Internet and looking for nice real world applications of evolutionary algorithms, what I have noticed is that when it comes to genetic algorithms, the most applied one still is the... Canon Genetic Algorithm! Surely, as stated above, that CGA which is being applied to solve a particular problem, very frequently, holds modifications, be these on the selection scheme, the evolutionary operators (mutation, crossover, and, from time to time, inversion), population size, or even on the probability tunning of mutation and crossover. The fiddling CGA game has generated, sometimes, strange algorithms.

By the way, I have nothing against NWOGA.

Our blog friend, Julian Togelius, wrote an interesting observation upon that situation. I consider that he aimed at the right target, see:

"I think the reason so few people are using other types of evolutionary algorithms than standard GAs is that few people know of, or understand, anything else. It's really amazing how little people know of what's going on next doors to their own little research field.

[...]

So, the people who are busy coming up with new algorithms don't have much time for learning about applications, and vice versa..."

Absolutely! :)

The big academic/technical organizations/publishers (ACM, IEEE, Springer, etc.) could sponsor more crossover events in which different research areas could come a little closer to share their respective experiences, new ideas and so on trying to find common points so that one area could help the other. Perhaps, that attitude could bring more open air to both fields.

P.S: To better understand why I wrote NWOGA, please, see here. :)

Update: Also via MEDAL Blogging.

More On The 2007 IEEE Congress On Evolutionary Computation (CEC)

Takayuki Higo has a post upon his report on the 2007 IEEE Congress On Evolutionary Computation (CEC), see here.

Don't forget to check the pictures he took!

-------------------------------------------

The picture above I took from his Flickr personal album.

-------------------------------------------