Optimizing TSP with Genetic Algorithms in Micronaut

import io.micronaut.serde.annotation.Serdeable;
import lombok.*;

@Data
@Builder
@AllArgsConstructor
@NoArgsConstructor
@Serdeable.Serializable
public class Individual {

    int[] genome; // sequence of cities to visit, starting with first city 0
    double fitness; // total distance travelled
    String message; // additional information attached to the individual

}

// Configuration
final int POPULATION_SIZE = 100; // Population size
final int MAX_GENERATIONS = 1200; // Maximum number of generations
final double INITIAL_TEMPERATURE = 1000; // Initial temperature to start with
final double FINAL_TEMPERATURE = 1; // Terminate main loop when temperature reached
final double COOLING_RATE = 0.9995; // Cooling rate
final int FITNESS_MEMO_SIZE = 10000000; // Limit the size of the fitness memo (out of heap size, avoid OOM error)
final int STAGNATION_THRESHOLD = 50; // Number of generations without improvement to trigger action
final int LOCAL_SEARCH_ATTEMPTS = 50; // Number of attempts on local search before exiting local optima
final int MUTATION_ATTEMPTS = 50; // Number of attempts on mutation
int maxCities;
double[][] graph; // Populate with actual distances
double fitnessThreshold; // The desired fitness threshold
int maxStagnationRetry = 10;
ConcurrentHashMap<Integer, Double> fitnessMemo = new ConcurrentHashMap<>(); // Thread-safe memoization for fitness
int generation = 1;
DecimalFormat df = new DecimalFormat("#");
int optimalCount = 0;

Individual getIndividual(int[] genome) {
    return Individual.builder().genome(genome).fitness(calculateFitness(genome)).build();
}

Individual getIndividual(int[] genome, double fitness) {
    return Individual.builder().genome(genome).fitness(fitness).build();
}

// Random number generator function
int randNumber(int start, int end) {
    return (int) (Math.random() * (end - start)) + start;
}

double calculateCityDistance(double x1, double y1, double x2, double y2) {
    double xDelta = (x1 - x2);
    double yDelta = (y1 - y2);

    return Math.sqrt((xDelta * xDelta) + (yDelta * yDelta));
}

double calculateDistance(int[] genome) {
    double distance = 0;
    for (int i = 0; i < genome.length - 1; i++) {
        int from = genome[i];
        int to = genome[i + 1];
        distance += graph[from][to];
    }

    //NOTE: This is distance needed to travel back to the original city
    distance += graph[genome[genome.length-1]][0];
    return distance;
}

// Hash-based map for the fitness (total distance of the entire genome)
double calculateFitness(int[] genome) {
    int genomeHash = Arrays.hashCode(genome); // Compute the hashcode of entire genome as key, to reduce memory usage
    if (fitnessMemo.containsKey(genomeHash)) {
        return fitnessMemo.get(genomeHash);
    }

    double totalDistance = calculateDistance(genome);
    if (fitnessMemo.size() < FITNESS_MEMO_SIZE) {
        fitnessMemo.put(genomeHash, totalDistance);
    }
    return totalDistance;
}

// Function to create a genome
int[] createGenome() {
    int[] genome = new int[maxCities];
    genome[0] = 0;
    Set<Integer> newGenome = new HashSet<>();
    newGenome.add(0);

    int index = 1;
    while (newGenome.size() < maxCities) {
        int temp = randNumber(1, maxCities);
        if (!newGenome.contains(temp)) {
            genome[index++] = temp;
            newGenome.add(temp);
        }
    }
    return genome;
}

// Convenience method to reinit portion of population
void reinitializePartOfPopulation(List<Individual> population) {
    int reinitializeCount = POPULATION_SIZE / 5; // Reinitialize 20% of the population
    for (int i = 0; i < reinitializeCount; i++) {
        int[] genome = createGenome();
        population.set(randNumber(2, population.size()), getIndividual(genome)); // Replace random individuals (excluding the best two)
    }
}

List<Individual> initialPopulation() {
    List<Individual> population = Collections.synchronizedList(new ArrayList<>());
    for (int i = 0; i < POPULATION_SIZE; i++) {
        population.add(getIndividual(createGenome()));
    }
    return population;
}

double calculateDelta(int[] genome, int i, int j) {
    // Calculate the difference in the tour length if the swap (i, j) is made
    return graph[genome[i - 1]][genome[j]] + graph[genome[i]][genome[j + 1]]
            - graph[genome[i - 1]][genome[i]] - graph[genome[j]][genome[j + 1]];
}

void twoOptSwap(int[] genome, int i, int j) {
    while (i < j) {
        int temp = genome[i];
        genome[i] = genome[j];
        genome[j] = temp;
        i++;
        j--;
    }
}

// Few variations, used this as it seems to be work better for both small and large number of cities
int[] localSearch(int[] genome) {
    int[] newGenome = genome.clone();
    boolean improvement = true;
    int iteration = 0;

    while (improvement && iteration < LOCAL_SEARCH_ATTEMPTS) {
        improvement = false;

        for (int i = 1; i < newGenome.length - 2; i++) {
            for (int j = i + 1; j < (newGenome.length - 1); j++) {
                if (i == j) continue;

                double delta = calculateDelta(newGenome, i, j);
                if (delta < 0) {
                    twoOptSwap(newGenome, i, j);
                    improvement = true;
                    break; // Early exit on improvement
                }
            }
            if (improvement) break; // Early exit on improvement
        }
        iteration++;
    }
    return newGenome;
}

int[] inversionMutation(int[] genome) {
    int[] newGenome = genome.clone();
    int start = randNumber(1, maxCities);
    int end = randNumber(1, maxCities);

    while (start > end) {
        end = randNumber(1, maxCities);
    }

    while (start < end) {
        int temp = newGenome[start];
        newGenome[start] = newGenome[end];
        newGenome[end] = temp;
        start++;
        end--;
    }
    return newGenome;
}

int[] insertionMutation(int[] genome) {
    int[] newGenome = genome.clone();
    int start = randNumber(1, maxCities);
    int end = randNumber(1, maxCities);
    while (start == end) {
        end = randNumber(1, maxCities);
    }
    int temp = newGenome[start];
    if (start < end) {
        System.arraycopy(newGenome, start + 1, newGenome, start, end - start);
    } else {
        System.arraycopy(newGenome, end, newGenome, end + 1, start - end);
    }
    newGenome[end] = temp;
    return newGenome;
}

int[] swapMutation(int[] genome) {
    int[] newGenome = genome.clone();
    int index1 = randNumber(1, maxCities);  // Avoid swapping the first position
    int index2 = randNumber(1, maxCities);
    int temp = genome[index1];
    genome[index1] = genome[index2];
    genome[index2] = temp;
    return newGenome;
}

// Mutation Operator to maintain diversity in population
int[] mutateGenome(int[] genome) {
    int[] newGenome = genome.clone();
    int mutationType = randNumber(0, 3);  // Adjust to the number of mutation operators
    return switch (mutationType) {
        case 0 -> inversionMutation(newGenome);
        case 1 -> insertionMutation(newGenome);
        default -> swapMutation(newGenome);
    };
}

int[] performMutation(Individual individual, double temperature) {
    int[] newGenome = individual.genome.clone();
    double newFitness;
    int mutationAttempts = 0;

    while (mutationAttempts < MUTATION_ATTEMPTS) {
        mutationAttempts++;

        newGenome = mutateGenome(newGenome); // Apply mutation
        newGenome = localSearch(newGenome);  // Integrate local search
        newFitness = calculateFitness(newGenome);

        if (newFitness < individual.fitness || Math.exp((individual.fitness - newFitness) / temperature) > Math.random()) {
            return newGenome;
        }
    }

    // No improvements after mutation attempts
    return individual.genome;
}

 int[] performCrossover(int[] parent1, int[] parent2) {
    int length = parent1.length;
    int[] child = new int[length];
    Set<Integer> usedGenes = new HashSet<>();

    // Choose a segment from parent1
    int startPos = randNumber(1, length);
    int endPos = randNumber(1, length);

    // Ensure startPos is less than endPos
    if (startPos > endPos) {
        int temp = startPos;
        startPos = endPos;
        endPos = temp;
    }

    // Copy the segment from parent1 to the child
    for (int i = startPos; i < endPos; i++) {
        child[i] = parent1[i];
        usedGenes.add(parent1[i]);
    }

    // Ensure the first position is always the starting point
    child[0] = 0;
    usedGenes.add(0);

    // Fill the remaining positions with genes from parent2 in the order they appear
    int currentPos = endPos;
    for (int i = 1; i < length; i++) {
        int geneFromParent2 = parent2[i];
        if (!usedGenes.contains(geneFromParent2)) {
            usedGenes.add(geneFromParent2);
            if (currentPos >= length) {
                currentPos = 1; // Wrap around to start filling from the beginning (skipping index 0)
            }
            if (child[currentPos] == 0) {
                child[currentPos] = geneFromParent2;
                currentPos++;
            }
        }
    }

    // Fill any remaining unfilled positions with random unused genes
    for (int i = 1; i < length; i++) {
        if (child[i] == 0) {
            int rand;
            do {
                rand = randNumber(1, length);
            } while (usedGenes.contains(rand));
            child[i] = rand;
            usedGenes.add(rand);
        }
    }

    return child;
}

double adaptiveCooling(double temperature, int generation) {
    return temperature * Math.pow(COOLING_RATE, generation / (double) MAX_GENERATIONS);
}

 // Combine simulated annealing with genetic algorithm
void simulatedAnnealing(Individual individual, double temperature) {
    for (int i = 0; i < 100; i++) {  // Simulated annealing iterations
        int[] mutatedGenome = mutateGenome(individual.genome);
        double mutatedFitness = calculateFitness(mutatedGenome);
        if (mutatedFitness < individual.fitness || Math.exp((individual.fitness - mutatedFitness) / temperature) > Math.random()) {
            individual.genome = mutatedGenome;
            individual.fitness = mutatedFitness;
            break;
        }
    }
}

@Singleton
public class TspGaService {

    // Configurations

    // Helper methods

    // LocalSearch

    // Mutation

    // Crossover

    // Simulated Annealing

    Individual solve(double[][] input) {
        Instant startTime = Instant.now(); // Record the start time
        fitnessMemo.clear();
        graph = input;
        maxCities = graph.length;

        List<Individual> population = initialPopulation();
        Individual bestIndividual = null;

        double bestFitness = Double.MAX_VALUE;
        int stagnationCount = 0;
        int stagnationResetCount = 0;
        double temperature = INITIAL_TEMPERATURE;

        while (temperature > FINAL_TEMPERATURE && generation < MAX_GENERATIONS && stagnationResetCount < maxStagnationRetry) {
            // Sort the population by fitness
            Collections.sort(population, Comparator.comparingDouble(a -> a.fitness));

            // Retain the best two individuals for elitism and crossover
            Individual bestCurrentIndividual = population.get(0);
            Individual secondBestIndividual = population.get(1);
            List<Individual> newPopulation = Collections.synchronizedList(new ArrayList<>());
            newPopulation.add(bestCurrentIndividual);
            newPopulation.add(secondBestIndividual);

            // Perform crossover and mutation
            for (int i = 0; i < POPULATION_SIZE; i++) {
                int[] newGnome;
                if (Math.random() < 0.5) {
                    newGnome = performCrossover(bestCurrentIndividual.genome, secondBestIndividual.genome);
                } else {
                    Individual randomIndividual = population.get(i);
                    newGnome = performMutation(randomIndividual, temperature);
                }

                newGnome = localSearch(newGnome);
                Individual newIndividual = getIndividual(newGnome, calculateFitness(newGnome));
                simulatedAnnealing(newIndividual, temperature); // Apply simulated annealing
                newPopulation.add(newIndividual);
            }

            // Ensure population is updated correctly
            if (!newPopulation.isEmpty()) {
                // Use a mix of old and new population to maintain diversity
                population = new ArrayList<>(newPopulation);
                while (population.size() < POPULATION_SIZE) {
                    int[] genome = createGenome();
                    population.add(getIndividual(genome, calculateFitness(genome)));
                }

            } else {
                for (int i = 0; i < POPULATION_SIZE; i++) {
                    int[] genome = createGenome();
                    population.add(getIndividual(genome, calculateFitness(genome)));
                }
            }

            // Update temperature regardless of population changes
            temperature = adaptiveCooling(temperature, generation);

            // Check for stagnation
            Individual currentBest = Collections.min(population, Comparator.comparingDouble(a -> a.fitness));
            if (currentBest.fitness == bestFitness) {
                optimalCount++;
                System.out.println("Potentially an optimal solution! " + bestFitness);
                if (optimalCount > 3) {
                    System.out.println("Optimal solution, existing " + bestFitness);
                    break;
                }

            } else if (currentBest.fitness < bestFitness) {
                 optimalCount = 0;
                bestIndividual = currentBest;
                bestFitness = bestIndividual.fitness;
                Duration elapsedDuration = Duration.between(startTime, Instant.now());
                System.out.println(elapsedDuration.toSeconds() + ", generation " + generation + ", fitness " + df.format(bestFitness) + ", fitnessMemo " + fitnessMemo.size());
                stagnationCount = 0;

            } else {
                stagnationCount++;
                if (stagnationCount >= STAGNATION_THRESHOLD) {
                    // Increase mutation rate to escape local optima
                    Duration elapsedDuration = Duration.between(startTime, Instant.now());
                    System.out.println(elapsedDuration.toSeconds() + ", stagnation detected: " + stagnationResetCount);

                    reinitializePartOfPopulation(population);  // Reinitialize part of the population
                    stagnationCount = 0;  // Reset stagnation count
                    stagnationResetCount++;
                }
            }

            generation++;

            // Check if the current best fitness meets the required threshold
            if (bestIndividual != null && bestIndividual.fitness <= fitnessThreshold) {
                System.out.println("Reached the fitness threshold. Stopping the algorithm.");
                break;
            }
        }

        // Find and print the most efficient path
        System.out.println("Most efficient path after " + generation  + " generations, threshold=" + fitnessThreshold + ", temp:" +temperature);
        return bestIndividual;
    }

}

@Controller("/tsp")
public class TSPController {
    ...
    private final TspGaService tspGaService;

    @Post("/solveGa")
    @Produces(MediaType.APPLICATION_JSON)
    @Consumes(MediaType.APPLICATION_JSON)
    public Individual solveTspGa(@Body double[][] distances) {
        return tspGaService.solve(distances);
    }

}