Sunday, November 13, 2005
Competent GAs revisited
Blogger and regular reader Nosophorus asks the following:
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.
...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:
<< Home
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)
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)
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)
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)
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)
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)
"[...]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)
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)
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
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
<< Home
