Recently I've come up with an idea that traditional approach for programming EAs may have a strong alternative.
In a traditional way we are dancing from the EA perspective, that is, there are individuals = candidate-solutions, they form population, which is modified by EA, consisting of various operators and a (posssibly hardcoded) scheme for their application sequence. Problem domain is somewhat alien and is communicated via fitness function. If some unusual representation of the solution is used (like Gray-coded strings for real-valued optimization problem), then genotype->phenotype transform should be made to evaluate an individual's performance. This transform is often made somewhere inside a fitness function, which means that fitness function can be divided into 2 sections:
We can say that here fitness function is a 'friend' for EA, which means that EA can work with any representation and the function performs all the necessary transformations itself or that individuals can convert themselves to different phenotypes (arrays, matrices, networks etc.). It's very convenient for EA, but not very convenient for the problem, we have to track whether individual can be transformed to the proper representation for fitness evaluation.
Nothing is wrong with this approach, it's good, but there's another decomposition variant.
Suppose that candidate-solutions are independent things. That is they have two sides (or faces/facets): one for EA and the other for a problem. The first side can be binary chromosome, or Lisp expression, or some graph representation, whatever the EA operators can work with. The second side is for the problem: real-valued vector, neural network, agent's policy representation, whatever the fitness function should handle.
In other words, candidate solutions are no longer parts of EA (although they can still be named individuals, particles, and so on), neither they are parts of a problem. This can be convenient for both EA and a problem, because there's no need to worry about conversions and transforms. When EA side is set, the problem's side can be updated at once, or on the first demand (implementing so called 'lazy' programming concept). If 1-to-1 mapping between genotype and phenotype exists, then this transform can be reversed and if problem's side is updated, for example by some local search algorithm, the EA side can be updated as well.
There're no miracles, it just means that all conversions are localized and they should be implemented explicitely, but neither EA nor problem's side should worry how it's done and by what means.
If genotype and phenotype are the same (real-valued EAs, direct graphs representation etc.) the individuals can be made either one-sided (I would call it 'Moebius representation' ;)) or two-sided, but with no difference between sides.
And as adopted, some pros and cons of this approach:
Pros:
P.S. Oh, it's possible that I've just rediscovered someone else's idea. Yeah. What if Plato was right? ;)
In a traditional way we are dancing from the EA perspective, that is, there are individuals = candidate-solutions, they form population, which is modified by EA, consisting of various operators and a (posssibly hardcoded) scheme for their application sequence. Problem domain is somewhat alien and is communicated via fitness function. If some unusual representation of the solution is used (like Gray-coded strings for real-valued optimization problem), then genotype->phenotype transform should be made to evaluate an individual's performance. This transform is often made somewhere inside a fitness function, which means that fitness function can be divided into 2 sections:
- Transform of the solution to the representation, which can be evaluated, even if a single method is called.
- Evaluation itself.
We can say that here fitness function is a 'friend' for EA, which means that EA can work with any representation and the function performs all the necessary transformations itself or that individuals can convert themselves to different phenotypes (arrays, matrices, networks etc.). It's very convenient for EA, but not very convenient for the problem, we have to track whether individual can be transformed to the proper representation for fitness evaluation.
Suppose that candidate-solutions are independent things. That is they have two sides (or faces/facets): one for EA and the other for a problem. The first side can be binary chromosome, or Lisp expression, or some graph representation, whatever the EA operators can work with. The second side is for the problem: real-valued vector, neural network, agent's policy representation, whatever the fitness function should handle.
In other words, candidate solutions are no longer parts of EA (although they can still be named individuals, particles, and so on), neither they are parts of a problem. This can be convenient for both EA and a problem, because there's no need to worry about conversions and transforms. When EA side is set, the problem's side can be updated at once, or on the first demand (implementing so called 'lazy' programming concept). If 1-to-1 mapping between genotype and phenotype exists, then this transform can be reversed and if problem's side is updated, for example by some local search algorithm, the EA side can be updated as well.
There're no miracles, it just means that all conversions are localized and they should be implemented explicitely, but neither EA nor problem's side should worry how it's done and by what means.
If genotype and phenotype are the same (real-valued EAs, direct graphs representation etc.) the individuals can be made either one-sided (I would call it 'Moebius representation' ;)) or two-sided, but with no difference between sides.
And as adopted, some pros and cons of this approach:
Pros:
- Can appear as two distinct objects at the same time.
- Potentially faster (because phenotype can be computed when genotype is changed)
- More natural (genotype + phenotype)
- Objective function does not need to support different encodings, it obtains the object it's meant to evaluate --> Easier to adapt for 3rd party applications
- Possibly easier to parallelize because problem side representations are independent and there very small chance of their conflicts.
- Requires more memory, because problem-side representations are stored for each EA-side representation.
- Adds extra interaction layer between EA and a problem.
- Probably more code to write due to more complex structure of candidate-solutions.
- The candidate-solutions become 'heavier'.
P.S. Oh, it's possible that I've just rediscovered someone else's idea. Yeah. What if Plato was right? ;)
No comments:
Post a Comment