Multithreaded galib247 genetic algorithm stuck in local maxima

Question

I added multithreading support to galib247 (below), but I'm still seeing problems whereby solutions were getting stuck in local maxima.

Perhaps it's a shortcoming of genetic algorithms in general. Let me know if anyone has any suggestions. I've tried running 1000 independent populations, that are prioritized based on how recently the population has found a better solution, but I still think it's not finding the best solution.

I've also tried modifying the mutator. Perhaps the solution set it too complicated, there are a lot of local maxima. It usually finds different local maxima in every one of the 1000 pools of pools, but occasionally one of the pools of pools finds a better answer and is prioritized for scheduling.

What I'm trying to do is generate an optimal technical analysis indicator list with parameters to an FX trade signal generator for live trading based on an expanding set of historical prices. There was a book about it years ago, I think the author's name was Katz.

I'm testing the variance of the results against a second historical price set but basically, the real test is whether or not it is predictive of future prices.

GAPopulation.C (http://lancet.mit.edu/ga/Copyright.html):

#include <boost/thread.hpp>
#include <boost/threadpool.hpp>

boost::threadpool::pool GAPopulation::thpool(5);

void GAPopulationEvaluatorWorker(void* individual_ptr) {
    ((GAGenome*) individual_ptr)->evaluate();
    boost::this_thread::yield();
}

void GAPopulation::DefaultEvaluator(GAPopulation& p) {
    for(int i = 0; i < p.size(); i++) {
        thpool.schedule(boost::bind(GAPopulationEvaluatorWorker, p.individual_ptr(i)));
    }

    thpool.wait();
}

Answer 1

Do you think your problem is caused by the multi-threading? I wouldn't think so...

GA's always have the problem of overcoming local maxima. I was taught that as program time goes on, you're supposed to decrease the mutation rate to keep from jumping down. But recently, I made a GA that increased its mutation rate based on the lack of genetic diversity in its population. (Had to come up with a function that could calculate diversity).

With GA's, there are many things you need to do well: #1, have a solid way of calculating fitness that can be performed very quickly. This simply can't be done with a lot of problems. #2, describe your problem in a set of genes. Again, that can be really hard to do. #3, who to breed and how to breed them. I'd rather have a diverse breeding pool where the mid-performing genes can last for several generations, especially if your problem is overcoming local maxima. And of course, #4, your strategy for mutation. It just may not be enough to flip 1 bit on a .1% chance. Or it might be too much. How do you breed or mutate things like floating-point numbers? Flipping 1 bit a) makes a drastic change and b) has no discernible impact on fitness (it could be good or bad depending on the other bits).

So using a GA requires a lot of tuning. Evaluate #1 and #2 and make sure you're happy with it. Experiment with breeding. "Killing your parents" might help. Maybe keep a few of the parents around, but breed everyone but the lowest 25%. That way there's less of a chance of jumping down, but a good gene has a chance to go through a few sub-par mutations that might in the end create a better gene.

I hear you can use a GA to set the initial weights for a neural net. I've always wanted to try that, but I still haven't gotten around to writing neural nets.