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.
Labels: Artificial Intelligence, EDA, Evolutionary Algorithm, Genetic Algorithm, Julian Togelius, Old School, Search, Simulated Evolution
posted by Marcelo at 12:01 AM
11 Comments:
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.
Yes, I'm one of those people. I know roughly what an EDA does, but I couldn't sit down an implement one on the spot, and I'm a little bit scared of the math I'd have to digest to get it right. So when asked to optimize something, I'm likely to use something I know (ES, GA, PSO etc.) rather than an EDA, even if such algorithms might be better on particular problems.
So, the people who are busy coming up with new algorithms don't have much time for learning about applications, and vice versa...
Btw, thanks for your wishing me well on my blog!
Hi, Togelius! :)
So well remembered, my friend!
I guess you aimed at the right target: Outsiders researchers do not apply EDA because they, maybe, even are not aware of its existence! It's a pity, of course, since using those new GAs could fuel a little more a specific evolutionary computation area. Sure, sure... I know that EDAs are a hot spot nowadays. :)
<
"Yes, I'm one of those people. I know roughly what an EDA does[...]"
Well, simply put, an EDA takes into account the same philosophy behind the GA engine, except when it comes to the evolutionary operators, which are thrown away and gives place to a probability distribution.
The background mathematics necessary for handling/implementing an EDA has a wide range. For example: the Compact Genetic Algorithm (cGA) and the PIBIL (Probability Based Incremental Learning) are very simple, requiring few math skills. On the other hand, there are others EDAs relying on advanced statistics, such as Bayesian networks and multivariate distributions. (A little - and interesting - observation: Despite the simplicity of some evolutionary algorithms - such as the cGA, the CGA/SGA, PBIL, UMDA, etc. - it does not mean that they are not well suited to deal with problems that, at least at a first glance, would require evolutionary algorithms holding complex/advanced statistics/probability ways as their main, let's say, "engine".)
By the way, I agree with you. :)
Thank you for your nice comment!
Best Regards! :)
I think Julian is definitely right: the ease of implementation of an algorithm is the big problem, along with its rigourous validation.
And, talking about seeing further than genetic algorithms, I suggest that one talk about metaheuristics rather than NWOGA :-)
More explanations:
http://metah.nojhan.net/post/2008/03/03/The-problem-with-spreading-new-metaheuristics
Hi, Nojhan!
Indeed!
I guess there are few tutorials upon the NWOGA available free of charge, for example (if you find one, please, let me know!). Well written tutorials could help a lot spreading those NWOGA in other areas. On the other hand, there are some codes for academic/educational purposes only. Yes... I know, I know... there are tons of papers published about those new genetic algorithms. BUT, an outsider, without any evolutionary computation knowledge, would suffer a little to implement one from scratch.
The EDA/NWOGA books which have been published seem to be a nice way out. Looking at Amazon.com, there are few reviews upon them. What is a pity, since the opinions of others customers who bought them could help someone pursuing new horizons related to genetic algorithms.
Let's wait what the future will show us.
Best Regards!
Marcelo
I think there's only anecdotic evidence to support that; most people are using nowadays hybrids in many possible ways. However, it's difficult to use something if you have to write the stuff from the top down, so most people who are starting stick to the tried and true CGA.
Hi, JJ! :)
In general, I agree with you.
The Good Old CGA has successfully been applied because of two main reasons:
01. It requires a very low knowledge investiment from the user.
02. The CGA user, frequently, has used some a priori information in the simulation to solve a particular problem.
In short: The CGA is simple and flexible enough to accept outside informations to increase its performance.
I support the research on new algorithms, such as those inspired by predator-prey models, statistical sampling, and so on. :)
Hasta La Vista! :)
Marcelo
I think modern GAs (NWOGAs) aren't being more applied than the CGA's due to a lack of a good textbook, just as Goldberg's was, and the profusion of articles just gets researchers confused... All the tons of "a new EDA for..." that arise everyday in conferences and publications make people think that this is too advanced and turn to the "good old" CGA, well described in books from Goldberg, Mitchell and Michalewicz... It's time for a good textbook to arise...
It seems that David Goldberg is already preparing the final pages of his brand new book upon genetic algorithms. I am not aware if that book will deal with EDA/NWOGA. I hope so. It has been more than a decade that those new algorithms have entered the evolutionary computation field and still there is not any good book about them. It's a pity, of course, mainly for those interested on the subject.
However, from what I gathered at Amazon.com website, that new book has to do much more with his 2002 book (The Design Of Innovation) rather than to the famous 1989 text (Genetic Algorithms in Search, Optimization, and Machine Learning). See here a brief description.
Michalewicz' book is a very nice one. Melanie Mitchell is very good too, despite some biases in it, but her text, in general, is good.
Best Regards!
Marcelo
Thank you for useful information, but I suggest to use some software solutions of application load testing to reduce unexpected expenses in the future. If you develop a gaming application, it is recommended to use java engineering.
I'm glad to know more and read this great review. Let me share with cheap insurance that is supported by top home insurance companies. You may save on cheap homeowners insurance quotes which allow customers to obtain affordable cheap policy.
You laugh at me for being different, but I laugh at you for being the same Maple Story Mesos, the consequences of today are determined by the actions of the past MapleStory Mesos, to change your future, alter your decisions today Maple Story Mesos.
Post a Comment
<< Home