|
I'm writing a linear genetic programming framework and I'm having a few problems which are probably connected. I'll begin by explaining the framework as it stands. The framework itself uses something like a virtual machine to interpret the candidates (the representation of the candidates is outside the scope of this question but I'll describe it if it turns out to be a significant to the problems), and uses a multi-objective selection algorithm based on the concept of Pareto efficiency. The size of each new generation is the maximum of 4 and the size of the current pool, each generation is added to the pool, then the Pareto optimal set is calculated and the candidates which are not in the Pareto optimal set are removed. When all the objectives being measured relate directly to performance or size: the candidates converge on a local optimum very quickly and the population never gets very large. But when I add another objective that's meant to measure how much each candidate contributes to the pool's diversity: the population starts increasing exponentially once the local optimum has been found. My question is: is there anything I can do to let the candidates escape local optima without exponentially increasing the population size? Or alternatively: what can I do to better handle a variable and sometimes large population? The strategy I'm testing at the moment is to exclude the previous generations once the population reaches a certain size, but I still don't know how effective that is at escaping the local optima. |
|
I'm not sure whether or not I've solved the issue of premature convergence because the current version converges very slowly and I haven't run it for long enough yet. The solution to the population explosion problem was to first remove the genetic similarity function, then add another fitness value which is initially zero. During the Pareto-sorting stage, if two candidates have identical fitness vectors then the extra value is incremented on one of them selected at random and the Pareto-sorting stage is restarted. Then instead of selecting just the Pareto optimal front, select enough fronts so that a minimum number of candidates is included. In the future: rather than selecting at random when two candidates have identical fitness vectors: I might choose another candidate at random and compare them both to it, demoting the one which is most similar. I should give credit where it's due. Although I didn't directly use any of the algorithms described in this paper I would have taken much longer to solve my problems without it: Multi-objective Techniques in Genetic Programming for Evolving Classifiers |
|
Are you using any kind of mutation operator, or some kind of random jumps, that is usually the best way to avoid local minimum. I'm not sure about that issue on the population expanding rapidly. I've never used GP before. I am using three different mutation operators but only in combination with crossover. Should I try using them separately? The population explosion is because of the selection algorithm not because it's GP. In the past I've done GP with a more conventional selection algorithm and it works well with fixed length genomes, but has its own set of problems when it's applied to variable length genomes.
(Dec 07 '12 at 23:23)
Jeremy List
|
