matlab禁忌搜索算法解决tsp

### 使用 MATLAB 实现禁忌搜索算法解决 TSP 问题

#### 距离矩阵计算
为了实现禁忌搜索算法，首先需要构建城市之间的距离矩阵。这一步骤确保后续可以方便地计算路径总长度。

function D = calculate_distance_matrix(citys)
    n = size(citys, 1);
    D = zeros(n, n);
    
    for i = 1:n
        for j = i+1:n
            D(i, j) = sqrt(sum((citys(i, :) - citys(j, :)).^2));
            D(j, i) = D(i, j);
        end
    end
end

#### 初始化参数设置
定义初始解、禁忌表大小以及其他控制参数：

n = length(D); % 城市数量
tabu_list_length = round(sqrt(n)); % 禁忌表长度
max_iterations = 500; % 最大迭代次数
current_solution = randperm(n); % 随机初始化当前解
best_solution = current_solution;
best_cost = inf;

% 创建空的禁忌表
tabu_list = cell(tabu_list_length, 1);

for iter = 1:max_iterations
    
    neighbors = generate_neighbors(current_solution, tabu_list, best_solution, D);
    
    [~, next_index] = min([neighbors.Cost]);
    next_solution = neighbors.Solution{next_index};
    next_cost = neighbors.Cost(next_index);
    
    if next_cost < best_cost
        best_solution = next_solution;
        best_cost = next_cost;
        
        % 更新禁忌表
        update_tabu_list(tabu_list, current_solution, next_solution);
    end
    
    current_solution = next_solution;
end

#### 生成邻居函数
此部分负责创建候选邻近解决方案集，并考虑禁忌条件筛选合适的移动方案。

function neighbors = generate_neighbors(solution, tabu_list, best_solution, distance_matrix)
    n = length(solution);
    neighbor_solutions = {};
    costs = [];
    
    for i = 1:(n-1)
        for j = (i+1):n
            
            new_sol = solution;
            temp = new_sol(i);
            new_sol(i) = new_sol(j);
            new_sol(j) = temp;
            
            cost = evaluate_path(new_sol, distance_matrix);
            
            isTabuMove = false;
            for k = 1:length(tabu_list)
                if ~isempty(tabu_list{k}) && ...
                   all(sort([new_sol(i), new_sol(j)]) == sort(tabu_list{k}))
                    isTabuMove = true;
                    break;
                end
            end
            
            if ~isTabuMove || better_than_best(best_solution, cost, distance_matrix)
                neighbor_solutions{end+1} = new_sol;
                costs(end+1) = cost;
            end
        end
    end
    
    neighbors.Solution = neighbor_solutions;
    neighbors.Cost = costs;
end

#### 辅助方法
评估路径成本并判断是否优于现有最佳解的方法如下所示：

function cost = evaluate_path(path, dist_mat)
    cost = sum(dist_mat(sub2ind(size(dist_mat), path([path, path(1)]'), circshift(path', 1))));
end

function flag = better_than_best(best_so_far, candidate_cost, dist_mat)
    flag = false;
    if isempty(best_so_far) || candidate_cost < evaluate_path(best_so_far, dist_mat)
        flag = true;
    end
end

#### 更新禁忌列表逻辑
当发现更优的新解时更新禁忌表中的记录。

function update_tabu_list(list, old_state, new_state)
    list = shift_down(list);
    move_to_add = find_diff(old_state, new_state);
    list{1} = move_to_add';
end

function diff = find_diff(a, b)
    [~, ia] = ismember(b, a);
    [~, ib] = ismember(a, b);
    diff = [ia(ib==false)', ib(ia==false)'];
end

function shifted = shift_down(cell_array)
    num_elements = numel(cell_array);
    shifted(2:num_elements) = deal(cell_array(1:end-1));
    shifted{1} = []; %#ok<UNRCH>
end

上述代码实现了基本版的禁忌搜索算法用于求解TSP问题[^1][^2][^3][^4]。