Dealing with duplicates in Genetic Algorithm

Question

I'm using Genetic Algorithm to create a rota for home-care organisation. All the groundwork is complete, I'm getting the results, but results are not as good as expected. If I calculate fitness for existing rota made by somebody, I get about £6000 (I measure fitness in money - great point for management).

When I run my GA, the best I manage to get is £8K after about 30K generations. So I know the better solution exists and I'm trying to get better result. I have tried different approaches - big population, small population, different number of crossover points, swap-mutation, random-mutation, hill-climber-mutation. And nothing improved the results.

The resulting curve looks like this:

I can run GA much longer, but it does not give me any better results - the curve is just flat horizontal to the right.

I figured that I get quite a lot of duplicated individuals in final population. And that slows down the improvement of the solution. I learned how to find duplicate individuals. But what do I do with them? I have tried replacing them with randomly created solutions, but usually their fitness is much worse then every body else in the solution space, so they get "killed" quite soon without giving any offsprings or other influence to the solution space.

Any ideas/suggestions/papers will be highly appreciated, as I've run out of ideas and research papers and almost no time left.

UPD: some description of the problem: There are number of visits(shifts) that are located in different geographical places (distances between locations are known). Currently I work with 700 visits per week with durations from 30 minutes to 5hrs. There are workers with different levels of contractual arrangements: some have 0 contracted hours - relief workers, there are part-timers and full-timers. I need to allocated workers for every shift in a best possible manner with this factors in mind:

1. Minimise travel distance for workers. When they have number of shifts in a day, the locations should be roughly in the same area
2. Workers should not do a lot of overtime hours
3. Workers should not work less than their contract says
4. Workers with 0-contracts should be allocated no or very limited working hours
5. Minimise waiting time between shifts. So no situations when somebody starts one visit at 9am to 10am, and next visit is at 6pm.
6. There is a limit of total number of hours that can be worked per day
7. There is a minimum of working hours per day: nobody should be deployed for only 30-minute visit and no other visits per day.
8. At least 2 days off allocated for anybody, but can be more
9. At least 2 days off must be adjacent.

And other minor fitness function adjustments. I hope this is sufficient for description.

Answer 1

What you've hit upon is the basic mechanism that drives GAs -- convergence to some fixed point that you hope is near optimal. In your case, clearly it isn't. So the name of the game is to try and balance this tendency to drive convergence with the competing interest of exploring the space looking for other solutions. There's no silver bullet for this problem -- you always end up tuning things to suit your particular problem.

In general, there are two ways to do this. One is to delay convergence for longer, thus giving the algorithm more time to find better solutions. You can switch to a weaker selection operator (binary tournament selection for example), you can increase your mutation rate, etc. The other option is to allow the algorithm to converge, but figure out a sensible way to restart the search (as you mentioned, putting random points in tends not to work because their fitness is too low to allow them to survive and contribute to the search).

I'll give an example of the latter approach. There is a relatively-little known algorithm called CHC (Eshelman 1991) that tends to work really well for a lot of problems. Unfortunately, one reason it's little-known is that the only way to access the original paper is to buy the printed proceedings of the first FOGA conference, but you can probably find a little bit of information online, hopefully enough to get you started. I can give you something of a quick overview though. In rough pseudocode, CHC looks like

delta = k/4               # k = chromosome length
while not done
    create new child population
    for i = 1 to n/2     # n = population size
        select p1, p2 from population without replacement
        if hamming_distance(p1, p2) > delta
            c1, c2 = HUX crossover(p1, p2)
            insert c1, c2 into child pop
        end if
    end for
    if child pop is empty
        delta = delta - 1
    else
        take best n individuals from union of parent and child populations as next population
    end if
    if delta < 0
        keep one copy of best individual in population
        generate n-1 new population members by flipping 35% of the bits of the best individual
        delta = k/4
    end if

The HUX crossover operator is like uniform crossover, but instead of choosing randomly between the parents independently for each bit, it exchanges precisely half the differing bits from the parents.

You then just keep running this loop until you decide to quit, either because you've found a good enough solution, you've exhausted the amount of time you have to spend on the problem, or whatever other criteria you desire.

Answer 2

The following answer is a shameless self-promotion, but I don't have any other reference. I did some stuff some years ago on how to deal with "premature" local optima in local search algorithms, i.e., when you get stuck too soon in the search. However, this is not a TCS answer, so maybe out of scope for this site.

The paper is this: Ant Colony Optimization with Adaptive Fitness Function for Satisfiability Testing. Also check the references.

The idea is to make your fitness landscape to adapt during the search. To do that, you add some weight schemes to the objective function. Then you change the weights according to some rules based on how good or bad your doing. Please consult the paper about how to define these weight schemes.

The target problem in the paper was random MAX-SAT, because that problem has a bunch of feasible solutions with the same fitness, and that gives you a lot of plateaus, and in general evolutionary algorithms don't work very well for MAX-SAT. So changing the landscape really helps. However, it should be easy to adapt the weight schemes to different problems.