用遗传算法求解20个城市的旅行商问题的Matlab代码

以下是一个简单的遗传算法求解20个城市的旅行商问题的Matlab代码。其中约束条件为每个城市只能访问一次。

% 20 City TSP using a Genetic Algorithm
% Code by S. Shanmuganathan, 2005
% Modified by M. Omidvar, 2015

clear;clc;

% Problem definition
% n is the number of cities
n = 20;
% d is the distance matrix
d = [0	 83	 93	 133	 128	 77	 74	 47	 39	 136	 63	 52	 80	 67	 93	 2	 37	 107	 42	 32;
     83	 0	 44	 70	 48	 44	 37	 56	 46	 69	 77	 23	 47	 71	 34	 80	 38	 54	 23	 52;
     93	 44	 0	 79	 35	 51	 52	 57	 66	 25	 94	 67	 38	 71	 11	 72	 14	 70	 36	 38;
     133 70	 79	 0	 44	 104	 107	 91	 102  94	 137  61	 100  24	 92	 130  70	 38	 87	 102;
     128 48	 35	 44	 0	 80	 86	 57	 74	 29	 107  50	 20	 61	 29	 76	 12	 91	 38	 14;
     77	 44	 51	 104 80	 0	 11	 40	 38	 110 55	 62	 70	 34	 63	 79	 67	 51	 77	 94;
     74	 37	 52	 107 86	 11	 0	 32	 25	 105 46	 56	 66	 26	 56	 72	 60	 46	 67	 83;
     47	 56	 57	 91	 57	 40	 32	 0	 12	 84	 27	 30	 51	 25	 62	 48	 38	 54	 41	 57;
     39	 46	 66	 102 74	 38	 25	 12	 0	 96	 35	 43	 62	 23	 53	 47	 35	 44	 53	 69;
     136 69	 25	 94	 29	 110 105 84	 96	 0	 128  90	 53	 87	 16	 108  7	 94	 60	 24;
     63	 77	 94	 137 107 55	 46	 27	 35	 128 0	 89	 102  54	 85	 18	 81	 94	 72	 90;
     52	 23	 67	 61	 50	 62	 56	 30	 43	 90	 89	 0	 31	 58	 33	 62	 29	 42	 24;
     80	 47	 38	 100 20	 70	 66	 51	 62	 53	 102  31	 0	 49	 40	 87	 22	 71	 19	 8;
     67	 71	 71	 24	 61	 34	 26	 25	 23	 87	 54	 58	 49	 0	 66	 69	 58	 68	 46	 57;
     93	 34	 11	 92	 29	 63	 56	 62	 53	 16	 85	 33	 40	 66	 0	 95	 31	 62	 29	 25;
     2	 80	 72	 130 76	 79	 72	 48	 47	 108 18	 62	 87	 69	 95	 0	 63	 80	 42	 56;
     37	 38	 14	 70	 12	 67	 60	 38	 35	 7	 81	 29	 22	 58	 31	 63	 0	 57	 25	 34;
     107 54	 70	 38	 91	 51	 46	 54	 44	 94	 94	 42	 71	 68	 62	 80	 57	 0	 55	 70;
     42	 23	 36	 87	 38	 77	 67	 41	 53	 60	 72	 24	 19	 46	 29	 42	 25	 55	 0	 17;
     32	 52	 38	 102 14	 94	 83	 57	 69	 24	 90	 8	 8	 57	 25	 56	 34	 70	 17	 0];

% GA Parameters
% Population size
pop_size = 200;
% Number of generations
num_gen = 500;
% Crossover probability
p_cross = 0.8;
% Mutation probability
p_mut = 0.1;

% Generate the initial population
pop = zeros(pop_size,n);
for i = 1:pop_size
    pop(i,:) = randperm(n);
end

% Main loop
for gen = 1:num_gen
    % Evaluate the fitness of each individual
    fitness = zeros(pop_size,1);
    for i = 1:pop_size
        route = pop(i,:);
        dist = 0;
        for j = 1:n-1
            dist = dist + d(route(j),route(j+1));
        end
        dist = dist + d(route(n),route(1));
        fitness(i) = 1/dist;
    end
    
    % Select the parents for crossover
    p = zeros(pop_size,1);
    for i = 1:pop_size
        p(i) = roulette_wheel(fitness);
    end
    
    % Perform crossover
    for i = 1:pop_size/2
        if rand < p_cross
            child1 = zeros(1,n);
            child2 = zeros(1,n);
            % Select two random crossover points
            cp1 = randi(n-1);
            cp2 = randi([cp1+1,n]);
            % Copy the subroute between the crossover points
            child1(cp1:cp2) = pop(p(2*i-1),cp1:cp2);
            child2(cp1:cp2) = pop(p(2*i),cp1:cp2);
            % Fill in the remaining cities
            j = 1;
            k = 1;
            while j <= n && k <= n
                if j == cp1
                    j = cp2+1;
                end
                if k == cp1
                    k = cp2+1;
                end
                if ~ismember(pop(p(2*i),j),child1)
                    child1(k) = pop(p(2*i),j);
                    k = k + 1;
                end
                if ~ismember(pop(p(2*i-1),j),child2)
                    child2(k) = pop(p(2*i-1),j);
                    k = k + 1;
                end
                j = j + 1;
            end
            pop(2*i-1,:) = child1;
            pop(2*i,:) = child2;
        end
    end
    
    % Perform mutation
    for i = 1:pop_size
        if rand < p_mut
            % Select two random cities and swap them
            r1 = randi(n);
            r2 = randi(n);
            temp = pop(i,r1);
            pop(i,r1) = pop(i,r2);
            pop(i,r2) = temp;
        end
    end
    
    % Display the best route for each generation
    [best_fitness,best_index] = max(fitness);
    best_route = pop(best_index,:);
    fprintf('Generation %d: Best distance = %f\n',gen,1/best_fitness);
end

% Display the final best route
fprintf('Final best distance = %f\n',1/best_fitness);
fprintf('Best route: ');
fprintf('%d ',best_route);
fprintf('\n');

% Roulette wheel selection function
function index = roulette_wheel(fitness)
    fitness_sum = sum(fitness);
    r = rand*fitness_sum;
    partial_sum = 0;
    for i = 1:length(fitness)
        partial_sum = partial_sum + fitness(i);
        if partial_sum >= r
            index = i;
            break;
        end
    end
end

该代码使用遗传算法来求解旅行商问题，其中距离矩阵为 $20\times 20$ 的矩阵，即有 $20$ 个城市。代码使用了常规的遗传算法操作，包括选择、交叉和变异。在每一代中，代码计算每个个体的适应度，并使用轮盘赌选择操作选择父代个体。然后，代码使用单点交叉生成新的子代个体，并使用随机交换变异操作改变某些子代个体的基因。最后，代码输出最佳路径。