Genetic algorithm does not converge

[tekgrrl]

Logs:

Greedy algorithm results:
Best chromosome: [0, 1, 4, 3, 5, 2, 6]
Total distance: 939.2099999999999

Genetic algorithm results (num_gens=0):
Best chromosome: [2 0 1 4 5 3 6]
Total distance: 1015.64
Population Diversity Ratio: 1.00

Genetic algorithm results (num_gens=1):
Best chromosome: [6, 1, 5, 3, 4, 0, 2]
Total distance: 994.4499999999999
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00

Genetic algorithm results (num_gens=2):
Best chromosome: [0, 6, 3, 5, 2, 1, 4]
Total distance: 1173.35
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00

Genetic algorithm results (num_gens=3):
Best chromosome: [2, 1, 4, 0, 3, 5, 6]
Total distance: 1125.41
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00

Genetic algorithm results (num_gens=4):
Best chromosome: [5, 2, 1, 6, 0, 3, 4]
Total distance: 1350.7400000000002
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00

Genetic algorithm results (num_gens=5):
Best chromosome: [5, 1, 2, 6, 0, 3, 4]
Total distance: 1235.22
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00

Genetic algorithm results (num_gens=6):
Best chromosome: [4, 2, 0, 6, 5, 3, 1]
Total distance: 1164.2199999999998
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00

Genetic algorithm results (num_gens=7):
Best chromosome: [6, 3, 5, 4, 1, 0, 2]
Total distance: 1015.64
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00

Genetic algorithm results (num_gens=8):
Best chromosome: [6, 0, 4, 3, 5, 1, 2]
Total distance: 963.2599999999999
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00
Population Diversity Ratio: 1.00

Genetic algorithm results (num_gens=9):
Best chromosome: [6, 0, 4, 3, 5, 1, 2]
Total distance: 963.2599999999999

[tekgrrl]

Need to do more logging and monitoring. For each population log:

• best_fitness
• average_fitness
• worst_fitness

[tekgrrl]

I get the feeling that the best fitness hits a peak very early (and well below what's possible) and then that peak dominates. Needs more careful analysis with a smaller dataset

[tekgrrl]

Found a bug with the code that promoted elites when diversity was low. I was using the same population each time through the main generation loop.

I decided to just do elitism for every generation and at that point things started working better to the point where the genetic algorithm was doing better than the greedy.

Here are the tunables that were working at this commit.

elite_count = 4
num_cities = 10
population size = num_cities * 6
num_gens = 35
size in two_point_crossover() = len(parent1)
mutation_frequency = 0.25
random_seed = 600

With the main parameters that had an effect being elite_count, num_cities and num_gens

Going to try with 20 cities

[tekgrrl]

Initially I doubled elite_count and it had an effect. Greedy gave 7081.33 while genetic with elite_count=8 went from 10852 to 9216.

I moved straight on to num_gens.

35 =10852
50 = 9216
60 = 8807
70 = 8752

Clearly diminishing returns. So back to elitism (with `num_gens = 60`). Doubling it to 16 gave 8495. So incrementing from 8 to 16:

8 = 8807 9 = 8216 10 = 8349 11 = 8233 12 = 8847

So maybe 9 is the sweet spot. Going to try increasing the population size.

OK, found a bug, I'm not using the population_size value I had defined, I was using the number of cities as the population size. First test with population_size = num_cities * 3 gave a result of 7536. But increasing the multiplier to 4 led to a sharp increase in the result (9500).

Changing the multiplier to 2 gave a result of 9407 and I tested with 5 and 6 and they showed continuous increases.

With a population multiplier of 3 and the elite_count set to 32 I got the result down to 7075 which is better than the Greedy solution.

It's not surprising given the complexity that it's hard to tune. Going to do some final tweaking to see if I can get it to consistently out perform the greedy solution for a reasonable range of cities and with most of the parameters derived from the number of cities

[tekgrrl]

Current code gets to within 0.03% of the optimal solution