Sunday, November 13, 2005

 

Competent GAs revisited

Blogger and regular reader Nosophorus asks the following:
...I only know that those Competent GAs "refer to principled procedures that solve a large category of hard problems quickly, reliably, and accurately". However, there is some canonical form for those GAs ?? There is some paper that reports about those GAs...
I'm glad you asked. Competent GAs take many different forms, but they all share certain characteristics and principles of operation. First, they are population based and they all possess an adaptive or self-adaptive crossfertilizing mechanism that learns and exchanges effective substructures. Second, the use of a population and crossfertilization mandates a certain physics of initialization, competition, decision, and exchange.

Interestingly, since 1993 and the fast messy GA, many different types of mechanisms have been developed for competent GAs, and if you would compare one to the other, you wouldn't recognize their similarities. For example, outwardly the fast messy GA looks nothing like hBOA. Only at the level of theory of operation do their similarities appear. There are many papers, theses, and dissertations that establish these principles going back to the late 80s and early 90s, but my book The Design of Innovation (see also here) is a one-stop source for surveying the principles and some of the mechanisms of competent GAs. The book provides the basics and you can dig into the different areas of concern at your leisure. A google searchable version of DOI is available here.

Comments:
Hi, Dr Goldberg!!

First, Thank You for your suggestions about Competent GAs, as the Professors of my University here in Brazil are in a strike, then, I have more free time to invest in other important readings.

But, I think that would be great if you and your colleagues at IlliGAL write some general paper about Competent GAs, talking about the principal ideas of Competent GAs, its history, evolution, development and current state. I know, there are a lot of informations in your book, DOI, however, if we have an article about Competent GAs, the ideas that form the core of Competent GAs would be more accessible for the general Evolutionary Computation community, principally students, and, thus, we could see a fast development of that kind of GAs.

Até Mais!!

Marcelo (a.k.a Nosophorus)
 
Hi, Dr Goldberg!

I have not seen a general software tool for doing GA that has been revised and generally approved by the researcher community and that is of commercial grade. Do you know of such tool? Can you recommend some? Furthermore, do you see it as part of ILLIGAL’s mandate to collaborate in developing a general software tool for doing GA?

I personally think that GA needs a common tool in order to be more broadly accepted and used. Right now, it seems like GA is still a method for intellectual elites, partly because there is no standard tool like a Java compiler is to Java.

Colbert Philippe
 
Hello!!

Well, I know that the question was not to me, but, if you permit me, I would like to point a suggestion for such a software.

There is the GAlib, that "[...]contains a set of C++ genetic algorithm objects. The library includes tools for using genetic algorithms to do optimization in any C++ program using any representation and genetic operators. The documentation includes an extensive overview of how to implement a genetic algorithm as well as examples illustrating customizations to the GAlib classes".

Could be nice to try GAlib, I do not use it, but it does not mean that GAlib is not a good tool, I think that is and I know some persons that use it and have achivied great results.

For more informations about GAlib:

http://lancet.mit.edu/ga/

Até Mais!! (Until Later!!)

Marcelo (a.k.a Nosophorus)
 
Thanks for your suggestion Marcelo (a.k.a Nosophorus)!

There are a few GA frameworks and/or libraries but I don’t think they meet the standard of complete solution (or near complete solution). For instance, one needs to be a C++ programmer to use GALib. Some say C++ is already a dead computer language. Any application written in it will follow its faith. In order for GA to move beyond the academic settings, it needs a rigorously designed and reviewed application so a broader public can do it without having to do some recompilation of some kind.

Please, don’t get me wrong. I am an experienced programmer myself. GALib is a cool package but it lacks many things to do many types of advanced GA. The analogy I give is: It's like tweaking and recompiling a compiler everytime you want to write a new program.

As a first step towards a solution, I would like to toss the idea that GA needs a specific computer programming language to meet its needs. Such language would have primitives to do routine GA things like defining a chromosome (be it linear or permutation or something else), doing hierarchical GA, co-evolution, …etc. Such language would evolve as the research in GA evolves. I could elaborate a number of requirements for such computer language but it is not the right place for that. I don’t know who has the technical skills the budget and the interest to develop such computer language. It’s a sizeable project. I feel that GA needs it to move forward.

Designing a computer language is somewhat academic, so maybe it should be handled by academic folks.

Colbert Philippe
 
Colbert,

I think that there are a few GA implementations that give you a sufficiently rich set of tools to apply your GA to any problem or representation you can imagine. But of course, you won't find many methods in these packages. For example, we could talk about competent GAs---you won't find any in standard GA libraries. So you are right, you don't have a "general tool" that would let you use any GA you could possibly find.

On the other hand, the question is, would you like to have a tool with all operators proposed in the past? Probably not. I personally have my own code that served me well for a number of years and it has all that I need (from the GA code...)

But your question was interesting from another perspective. One of the goals of competent GAs is that they solve *broad* classes of problems efficiently and reliably. One motivation for this is to not have to choose one of 1000 specialized crossover and mutation operators each time you are trying to solve a problem, but to have one powerful variation operator that can adapt to your problem and figure out how to perform crossover in this particular case. That's where our research on EDAs is going, for instance.
 
Hello, Colbert!! :D

Well, hardly you will find some tool that fits completely good to your problem and, in Engineering, we are (almost?) always working very far from the ideal conditions, neither any of the Evolutionary Algorithms available out there will be fit to give you a complete or, at least, a near complete solution.

If you read the tutorial that comes together with the GAlib, I think that you can run some simple simulations at the beginning and, with more simulations and learning about GAlib, I guess that you can run more complex simulations. But, another choice could be learn C++. I do not think that C++ is a already-dead computer language (NASA used C++ in some embedded softwares in the rovers Spirit and Opportunity), I think that C++ is a very useful language that allows you to do low and high programming, a thing that JAVA, I guess, does not permit (only high level programming). If you have some problem with C++, well, still there are some persons that program in FORTRAN, ADA (the rocket ARIANE-5 from ESA uses ADA), Pascal and COBOL, and there are Evolutionary Algorithms writen with those languages. I think that learn C++ is a good option if the person wants to make some Evolutionary Algorithms (principally when talking about time performance). A Tip: Try Chris Jamsa book: Rescued by C++, it is a great book for a beginner. :D

If you want to avoid recompilation and all the academic settings, well, there is the Genetic Algorithm Toolbox inside Matlab, I have some friends that use it and they told me that the GUI (Graphical User Interface) is very friendly, but I do not know if that toolbox is included in the normal Matlab package, if not, you will need to pay 1000$ bucks to have one. Oh, I almost forgot: Matlab is an interpreter and, if you buy the Genetic Algorithm Toolbox and want to run simulations with large populations and long time generations, well, I can only say this: buy a pillow and a mattress. Gosh!! It remembers me when I once run a neural net simulation in Matlab: I was in the second day of simulation and my sister reboot the computer!

"[...] Such language would have primitives to do routine GA things like defining a chromosome (be it linear or permutation or something else), doing hierarchical GA, co-evolution, …etc. Such language would evolve as the research in GA evolves[...]". Well, the GAlib allows you to do some of those stuffs that you said, but, you need to know a little bit of C++.

Até Mais!!

Marcelo (a.k.a Nosophorus)
 
TO Martin Pelikan
I will reply to Martin Pelikan first because he understands my point.

The issue is not difficulty in programming C++. I have over 20 years experience in programming C++ (since its very beginning). The issue is standardization.

I believe you entirely when you say: “I personally have my own code that served me well for a number of years and it has all that I need (from the GA code...)”. But to push your idea further, if your set of code served you well, why can’t other GA researchers agree with you enough to make that set of code standard? It’s like GA researchers think that GA is something personal. No standard is necessary.

In several other programming fields, when a task is repetitive, complex and error prone, a specialized computer language is often created to deal with the task. For instance: In the field of video card programming, companies such as ATI and NVIDIA have created a specialized computer language (a C++ derivative) to program video cards. In the field of network communications, companies such as IBM, CISCO have created specialized computer languages for programming network routers and such. As a last example; in the field of computer security, a number of specialized computer languages have been created to program software and network security.

I feel that a computer language should be created for competent-GA. A computer language quickly establishes a de-facto standard way of doing things. It brings efficiency, consistency and reliability in routine programming.

There are other important reasons why this should be done like hiding parallel-programming (multi-threading..etc). A computer language could hide all that.

CP
 
"[...]But to push your idea further, if your set of code served you well, why can’t other GA researchers agree with you enough to make that set of code standard? It’s like GA researchers think that GA is something personal. No standard is necessary".

Well, there is a problem here: although today we have Evolutionary Algorithms that deal with a wide range of problems (BOA, hBOA), those same algorithms, frequently, do not solve another wide range of problems, so, the Evolutionary Algorithmist should make his implementation problem-dependent and, when a person deals with problems that need a specific implementation, it is very dificult to convert that in a standard, because you always will have problems that need a special attention and code implementation.

"In several other programming fields, when a task is repetitive, complex and error prone, a specialized computer language is often created to deal with the task".

Depend in wich way you see the situation, because, if you consider the side of the Evolutionary Algorithmist, that tries to find better ways and theory to the Evolutionary Computation field, his work is not repetitive, on the contrary, often he needs to implement things (like evolutionary operators) from the scratch. Build and program a video card is very different of program Evolutionary Algorithms. The former is just a product that has a very specific application and its principal characteristics do not "change" (not so) frequently like in the Evolutionary Computation field (because you have so many problems that need specific implementation). The other is a tool to help you to solve real world problems and, as some (a lot??) of those problems needs a specific implementation, is very dificult to make a standard for anything. For example: I can have an Evolutionary Algorithm that solves the Schaffer Function, but that same algorithm does not solve the Traveler Salesman Problem, but you can use the core ideas of Evolutionary Computation to solve both. :D Those two problems are classical inside the Evolutionary Computation and not so dificult to solve, now imagine other real world problems that need specific implementation, specific evolutionary operators and so on, to build a standard would be a hard problem.

If ATI and NVIDIA need to build a specific video card for each computer in the world, so, a computer language to help in that task would not be useful. The same happens with Evolutionary Computation: We have a lot of problems to solve and a wide range of them needs a very specific implementation such that, try to build a standard would be a waste of time.

Até Mais!! :D

Marcelo (a.k.a Nosophorus)
 
CP:

I do understand your point. I don't really agree though that the development of a new language is what we need. I personally would prefer to not have to learn a new language, especially when C/C++ that I use provides me enough tools to make my programming effective.

But I think there are efforts that go in the direction of designing a universal tool for evolutionary algorithms. One example I know about is OpenBeagle. One of the points it that it might be good if there were more modules available for approaches that are not implemented in this package, but that always requires that you find someone who will do that.

Marcelo:
Yes, certainly we cannot expect one algorithm for one representation to solve all our problems, at least not right now. But there are ways to deal with multiple representations, multiple types of variation operators, multiple types of selection and replacement strategies, etc.
 
Martin Pelikan & Marcelo raise some good points.

However, I want to point out to you both that the business community had similar problems and resolved it long ago. The solution is: component-based environment. Each GA innovation should be wrapped in a component.

Each part of GA should be implemented in a separate component. Of course, you can have several component for doing the same task like component for selection. When required an application can simply create it and use it. The component itself can be in the same computer box or remote. That’s what Java EJB is about. .NET has something similar.

In order for this to work the GA community must agree on a component-based environment and protocol. I take this back. You don’t really need all the GA researchers in the world to agree. You need a medium-seize group of people to agree. An institution like ILLAGAL can start such project and it might take-off.

The business community did years ago. It works wonderfully. Just look at an environment like IBM Eclipse.

CP
 
TO Nosophorus

Please, read my reply about component-based software environment.

All the issues you talked about concerning the need for flexibility for the researcher can be handled with a component-based platform.

Previously you disagreed that C++ is not a dead language. I beg to say that the signs are so obvious. I don't know how many years you have been programming, but C/C++ is at least 15 years old now. It's time for something new and more practical. Companies such as Intel, AMD, IBM and Sun have stated clearly that they are going to shift technological directions to produce multiple core microprocessors instead of single-core. You can already buy a dual-processor computer at your local store. AMD and Intel have already announced 4-core processors for 2007 (very soon indeed) and 8-core processors for 2009 (that's just around the corner). The future of programming is seamless multi-threading. You will see shortly some newer languages taking over that hide the complexity of multi-threading. Yes, you can do multi-threading in C++ but it's too complicated to write and dubug for many. So C++ as we know it is very dead. Read microprocessor forums for further aguments.

I want to talk more about standards in GA.

CP
 
Hi, Colbert!! :D

Well, I am just a newbie/freshman/the-new-kid-on-the-block when the subject is C++ programming. The first time I used it was in 2002 and, in my first experience, to be honest, I really dislike it!! I will not do here propaganda related to some programming language, I think that C++ is very useful to my purposes and I will continue to use it. :D FORTRAN is older (from 1950's) than C++, but, who would say that it is dead or outdated ?? I know persons who program in FORTRAN and have achivied good results using it. :D

Martin:

I agree with you, but will be very hard to find an algorithm that solves all our problems and the problem-dependent implementation, maybe, always will be a "nightmare" for the Evolutionary Algorithmist.

Até Mais!!

Marcelo
 
Post a Comment

<< Home

This page is powered by Blogger. Isn't yours?