遗传算法Matlab代码实现 - 旅行商问题示例

% 定义问题 n = 20; % 城市数量 x = rand(n,1); % 城市的 x 坐标 y = rand(n,1); % 城市的 y 坐标 d = zeros(n,n); % 城市之间的距离 for i=1:n for j=1:n d(i,j) = sqrt((x(i)-x(j))^2 + (y(i)-y(j))^2); end end

% 定义遗传算法参数 pop_size = 100; % 种群大小 num_gen = 500; % 迭代次数 mut_rate = 0.02; % 变异率 elite_rate = 0.1; % 精英率 tournament_size = 5; % 锦标赛选择的比较大小

% 初始化种群 pop = zeros(pop_size,n); for i=1:pop_size pop(i,:) = randperm(n); end

% 迭代 for gen=1:num_gen % 计算适应度 fitness = zeros(pop_size,1); for i=1:pop_size fitness(i) = 1/sum(d(pop(i,:),[1:n,1])); end

% 选择
elite_size = round(pop_size*elite_rate);
[sorted_fitness, idx] = sort(fitness,'descend');
elite = pop(idx(1:elite_size),:);
tournament = zeros(pop_size-elite_size,n);
for i=1:pop_size-elite_size
    candidates = randperm(pop_size,tournament_size);
    [~,winner_idx] = max(fitness(candidates));
    tournament(i,:) = pop(candidates(winner_idx),:);
end
pop = [elite;tournament];

% 交叉
for i=1:2:pop_size-elite_size
    parent1 = pop(i,:);
    parent2 = pop(i+1,:);
    child1 = parent1;
    child2 = parent2;
    crossover_point = randi(n-1);
    child1(crossover_point+1:end) = parent2(~ismember(parent2(1:crossover_point),parent1(1:crossover_point)));
    child2(crossover_point+1:end) = parent1(~ismember(parent1(1:crossover_point),parent2(1:crossover_point)));
    pop(elite_size+i,:) = child1;
    pop(elite_size+i+1,:) = child2;
end

% 变异
for i=elite_size+1:pop_size
    if rand<mut_rate
        mut_point1 = randi(n);
        mut_point2 = randi(n);
        pop(i,[mut_point1,mut_point2]) = pop(i,[mut_point2,mut_point1]);
    end
end

end

% 计算最优解 fitness = zeros(pop_size,1); for i=1:pop_size fitness(i) = 1/sum(d(pop(i,:),[1:n,1])); end [~,idx] = max(fitness); opt_tour = pop(idx,:); opt_dist = sum(d(opt_tour,[1:n,1]));