当前位置：首页 > news >正文

智能优化算法-禁忌搜索算法（TS）（附源码）

news 2024/10/22 20:34:00

目录
1.内容介绍
2.部分代码
3.实验结果
4.内容获取

1.内容介绍

禁忌搜索优化算法 (Tabu Search, TS) 是一种基于局部搜索的元启发式优化算法，由Fred Glover于1986年提出。TS通过引入“禁忌表”来避免重复搜索已经访问过的解，从而跳出局部最优解，寻找全局最优解。

TS的工作机制主要包括：

初始化：随机生成一个初始解。
邻域搜索：在当前解的邻域内寻找更好的解。
禁忌表：记录已经访问过的解或移动操作，避免重复搜索。
** aspiration criteria**：当找到的解比当前最优解更好时，即使该解在禁忌表中，也可以接受。
更新：根据搜索结果更新当前解和禁忌表。

优点包括：

避免局部最优：通过禁忌表机制，TS能够有效地避免陷入局部最优解。
灵活性：适用于多种优化问题，包括组合优化和连续优化。
易于实现：算法设计直观，易于编程实现。

不足之处：

参数敏感性：算法性能受禁忌表长度、邻域大小等参数的影响较大，需要适当调优。
计算成本：对于大规模问题，TS的计算复杂度较高，可能需要较高的计算资源。
收敛速度：在某些情况下，TS的收敛速度可能较慢。

TS的应用范围广泛，例如：

工程设计：优化机械部件设计、电路设计等，考虑多个性能指标。
资源分配：解决生产调度、物流管理等问题，平衡多个目标。
机器学习：用于特征选择、参数调优等，提高模型性能。
经济金融：投资组合优化、风险管理等，平衡风险与收益。

总之，TS作为一种有效且灵活的优化算法，在处理复杂优化问题方面展现了显著的优势。随着进一步的研究和应用，TS将在更多领域发挥重要作用。

2.部分代码

clc;
clear;
close all;

%% 问题定义

model = CreateModel(); % 建立TSP模型

CostFunction = @(tour) TourLength(tour, model); % 适应函数即路径长度

ActionList = CreatePermActionList(model.n); % 操作列表

nAction = numel(ActionList); % 操作数

%% 禁忌搜索算法参数

MaxIt = 50; % 迭代次数

TL = round(0.5*nAction); % 禁忌表长度

%% 初始化

% 建立空的个体结构体
empty_individual.Position = [];
empty_individual.Cost = [];

% 建立初始解
sol = empty_individual;
sol.Position = randperm(model.n);
sol.Cost = CostFunction(sol.Position);

% 初始化找到的最优解
BestSol = sol;

% 保存每一代的最优值
BestCost = zeros(MaxIt, 1);

% 初始化操作禁忌计数器
TC = zeros(nAction, 1);

%% 主循环

for it = 1:MaxIt

bestnewsol.Cost = inf;

% 应用操作
for i = 1:nAction
if TC(i) == 0
newsol.Position = DoAction(sol.Position, ActionList{i});
newsol.Cost = CostFunction(newsol.Position);
newsol.ActionIndex = i;

if newsol.Cost <= bestnewsol.Cost
bestnewsol = newsol;
end
end
end

% 更新当前解
sol = bestnewsol;

% 更新禁忌表
for i = 1:nAction
if i == bestnewsol.ActionIndex
TC(i) = TL; % 添加入禁忌表中
else
TC(i) = max(TC(i)-1, 0); % 减少禁忌计数器
end
end

% 更新最优解
if sol.Cost <= BestSol.Cost
BestSol = sol;
end

% 保存最优值
BestCost(it) = BestSol.Cost;

% 显示每一代的最优值
disp(['Iteration ' num2str(it) ': Best Cost = ' num2str(BestCost(it))]);

% 画出最优解
figure(1);
PlotSolution(BestSol, model);
pause(0.01);

end