编辑代码

using System;
using System.Linq;
using System.Collections.Generic;

class TSP_DE
{
    static Random rand = new Random();
    
    // 20个城市坐标
    static (double, double)[] cities = {
        (88, 16), (42, 76), (5, 76), (69, 13), (73, 56), (100, 100), (22, 92), (48, 74), (73, 46),
        (39, 1), (51, 75), (92, 2), (101, 44), (55, 26), (71, 27), (42, 81), (51, 91), (89, 54),
        (33, 18), (40, 78)
    };
    static int numCities = cities.Length;
    
    // 计算路径总距离
    static double TotalDistance(int[] order)
    {
        double dist = 0;
        for (int i = 0; i < order.Length - 1; i++)
            dist += Distance(cities[order[i]], cities[order[i + 1]]);
        dist += Distance(cities[order[order.Length - 1]], cities[order[0]]); // 回到起点
        return dist;
    }

    // 计算两点间的欧几里得距离
    static double Distance((double, double) a, (double, double) b) =>
        Math.Sqrt(Math.Pow(a.Item1 - b.Item1, 2) + Math.Pow(a.Item2 - b.Item2, 2));

    // 变异：随机交换两个城市
    static int[] Mutate(int[] order)
    {
        int[] newOrder = (int[])order.Clone();
        int idx1 = rand.Next(numCities);
        int idx2 = rand.Next(numCities);
        (newOrder[idx1], newOrder[idx2]) = (newOrder[idx2], newOrder[idx1]); // 交换
        return newOrder;
    }

    // 交叉：部分映射交叉（PMX）
    static int[] Crossover(int[] parent1, int[] parent2)
    {
        int size = parent1.Length;
        int[] child = new int[size];
        Array.Fill(child, -1);

        int start = rand.Next(size);
        int end = rand.Next(start, size);

        for (int i = start; i <= end; i++)
            child[i] = parent1[i];

        for (int i = 0; i < size; i++)
        {
            if (child.Contains(parent2[i])) continue;
            for (int j = 0; j < size; j++)
            {
                if (child[j] == -1)
                {
                    child[j] = parent2[i];
                    break;
                }
            }
        }
        return child;
    }

    // 差分进化算法
    static int[] DifferentialEvolution(int populationSize, int generations, double mutationRate, double crossoverRate)
    {
        List<int[]> population = new List<int[]>();
        for (int i = 0; i < populationSize; i++)
            population.Add(Enumerable.Range(0, numCities).OrderBy(_ => rand.Next()).ToArray());

        int[] bestSolution = population[0];
        double bestDistance = TotalDistance(bestSolution);

        for (int gen = 0; gen < generations; gen++)
        {
            List<int[]> newPopulation = new List<int[]>();

            foreach (var individual in population)
            {
                // 选择三个不同个体
                var candidates = population.OrderBy(_ => rand.Next()).Take(3).ToArray();
                int[] mutant = Mutate(candidates[0]);
                
                int[] trial;
                if (rand.NextDouble() < crossoverRate)
                    trial = Crossover(mutant, individual);
                else
                    trial = (int[])mutant.Clone();

                double trialDistance = TotalDistance(trial);
                double individualDistance = TotalDistance(individual);

                // 选择较优个体
                if (trialDistance < individualDistance)
                {
                    newPopulation.Add(trial);
                    if (trialDistance < bestDistance)
                    {
                        bestDistance = trialDistance;
                        bestSolution = trial;
                    }
                }
                else
                {
                    newPopulation.Add(individual);
                }
            }

            population = newPopulation;
            Console.WriteLine($"Generation {gen + 1}: Best Distance = {bestDistance}");
        }

        return bestSolution;
    }

    static void Main()
    {
        int populationSize = 50;
        int generations = 2000;
        double mutationRate = 0.5;
        double crossoverRate = 0.5;

        Console.WriteLine("Starting Differential Evolution for TSP...");
        int[] bestOrder = DifferentialEvolution(populationSize, generations, mutationRate, crossoverRate);

        Console.WriteLine("\nOptimal Route:");
        foreach (var city in bestOrder)
            Console.Write(city + " -> ");
        Console.WriteLine(bestOrder[0]); // 回到起点
        Console.WriteLine("Optimal Distance: " + TotalDistance(bestOrder));
    }
}