模拟退火算法和遗传算法结合的java代码示例

下面是一个简单的Java代码示例，演示了如何结合模拟退火算法和遗传算法来解决TSP问题：

import java.util.Random;

public class TSPSolver {
    private int[][] distanceMatrix; // 距离矩阵
    private int numCities; // 城市数量
    private int[] bestSolution; // 最优解
    private double bestFitness; // 最优解的适应度

    public TSPSolver(int[][] distanceMatrix) {
        this.distanceMatrix = distanceMatrix;
        this.numCities = distanceMatrix.length;
        this.bestSolution = new int[numCities];
        this.bestFitness = Double.MAX_VALUE;
    }

    public void solve(int numIterations, double initialTemperature, double coolingRate) {
        // 初始化遗传算法参数
        int populationSize = 100;
        double crossoverRate = 0.8;
        double mutationRate = 0.2;

        // 初始化种群
        int[][] population = generateInitialPopulation(populationSize);

        // 进行模拟退火与遗传算法的迭代优化
        Random random = new Random();
        double temperature = initialTemperature;

        for (int iteration = 0; iteration < numIterations; iteration++) {
            // 模拟退火
            for (int i = 0; i < populationSize; i++) {
                int[] solution = population[i];
                double fitness = evaluateFitness(solution);

                for (int j = 0; j < numCities; j++) {
                    int randomIndex = random.nextInt(numCities);
                    int temp = solution[j];
                    solution[j] = solution[randomIndex];
                    solution[randomIndex] = temp;

                    double newFitness = evaluateFitness(solution);
                    double delta = newFitness - fitness;

                    if (delta < 0 || random.nextDouble() < Math.exp(-delta / temperature)) {
                        fitness = newFitness;
                    } else {
                        temp = solution[j];
                        solution[j] = solution[randomIndex];
                        solution[randomIndex] = temp;
                    }
                }

                if (fitness < bestFitness) {
                    bestFitness = fitness;
                    System.arraycopy(solution, 0, bestSolution, 0, numCities);
                }
            }

            // 遗传算法
            int[][] newPopulation = new int[populationSize][numCities];

            for (int i = 0; i < populationSize; i++) {
                int[] parent1 = selectParent(population);
                int[] parent2 = selectParent(population);

                int[] child = crossover(parent1, parent2, crossoverRate);
                child = mutate(child, mutationRate);

                newPopulation[i] = child;
            }

            population = newPopulation;
            temperature *= coolingRate;
        }
    }

    private int[][] generateInitialPopulation(int populationSize) {
        int[][] population = new int[populationSize][numCities];

        for (int i = 0; i < populationSize; i++) {
            for (int j = 0; j < numCities; j++) {
                population[i][j] = j;
            }

            // 随机打乱顺序
            shuffleArray(population[i]);
        }

        return population;
    }

    private void shuffleArray(int[] array) {
        Random random = new Random();

        for (int i = array.length - 1; i > 0; i--) {
            int index = random.nextInt(i + 1);
            int temp = array[index];
            array[index] = array[i];
            array[i] = temp;
        }
    }

    private double evaluateFitness(int[] solution) {
        double fitness = 0;

        for (int i = 0; i < numCities - 1; i++) {
            int city1 = solution[i];
            int city2 = solution[i + 1];
            fitness += distanceMatrix[city1][city2];
        }

        fitness += distanceMatrix[solution[numCities - 1]][solution[0]]; // 回到起始城市的距离

        return fitness;
    }

    private int[] selectParent(int[][] population) {
        Random random = new Random();
        int parentIndex = random.nextInt(population.length);
        return population[parentIndex];
    }

    private int[] crossover(int[] parent1, int[] parent2, double crossoverRate) {
        Random random = new Random();
        int[] child = new int[numCities];

        if (random.nextDouble() < crossoverRate) {
            int startPos = random.nextInt(numCities);
            int endPos = random.nextInt(numCities);

            for (int i = 0; i < numCities; i++) {
                if (startPos < endPos && i > startPos && i < endPos) {
                    child[i] = parent1[i];
                } else if (startPos > endPos && !(i < startPos && i > endPos)) {
                    child[i] = parent1[i];
                }
            }

            for (int i = 0; i < numCities; i++) {
                if (!containsValue(child, parent2[i])) {
                    for (int j = 0; j < numCities; j++) {
                        if (child[j] == 0) {
                            child[j] = parent2[i];
                            break;
                        }
                    }
                }
            }
        } else {
            System.arraycopy(parent1, 0, child, 0, numCities);
        }

        return child;
    }

    private int[] mutate(int[] solution, double mutationRate) {
        Random random = new Random();

        if (random.nextDouble() < mutationRate) {
            int pos1 = random.nextInt(numCities);
            int pos2 = random.nextInt(numCities);

            int temp = solution[pos1];
            solution[pos1] = solution[pos2];
            solution[pos2] = temp;
        }

        return solution;
    }

    public int[] getBestSolution() {
        return bestSolution;
    }

    public double getBestFitness() {
        return bestFitness;
    }
}

这段代码实现了一个简单的TSP问题求解器，结合了模拟退火算法和遗传算法。它首先生成一个初始种群，然后进行模拟退火和遗传算法的迭代优化。在每次迭代中，使用模拟退火对种群中的每个个体进行优化，然后使用遗传算法生成新的种群。最终得到的最优解存储在`bestSolution`数组中，最优解的适应度存储在`bestFitness`变量中。

请注意，这只是一个简单的示例代码，实际应用中可能需要根据具体问题进行修改和优化。