蚁群算法的优化计算——旅行商问题(TSP)优化.doc

蚁群算法的优化计算——旅行商问题(TSP)优化 1、案例背景 蚁群算法（Ant Colony Algorithm，ACA）是由意大利学者M.Dorigo等人于20世纪90年代初提出的一种新的模拟进化算法，其真实地模拟了自然界蚂蚁群体的觅食行为。M.Dorigo等人将其应用于解决旅行商问题（Traveling Salesman Problem，TSP），取得了较好的实验结果。近年来，许多专家与学者致力于蚁群算法的研究，并将其应用于交通、通信、化工、电力等领域，成功解决了许多组合优化问题，如调度问题（Job-shop Scheduling Problem）、指派问题（Quadratic Assignment Problem）、旅行商问题（Traveling Salesman Problem）等。本章将详细阐述蚁群算法的基本思想及原理，并以实例的形式介绍其应用于解决中国旅行商问题（Chinese TSP，CTSP）的情况。按照枚举法，我国31个直辖市、省会和自治区首府（未包括港、澳、台）的巡回路径应有约1.326*1032种，其中一条路径如图22-2所示。试利用蚁群算法寻找到一条最佳或者较佳的路径。  2、案例目录：  22.1 理论基础??22.1.1 蚁群算法基本思想??22.1.2 蚁群算法解决TSP问题基本原理??22.1.3 蚁群算法解决TSP问题基本步骤??22.1.4 蚁群算法的特点22.2 案例背景??22.2.1 问题描述??22.2.2 解决思路及步骤22.3 MATLAB程序实现??22.3.1 清空环境变量??22.3.2 导入数据??22.3.3 计算城市间相互距离??22.3.4 初始化参数??22.3.5 迭代寻找最佳路径??22.3.6 结果显示??22.3.7 绘图22.4 延伸阅读??22.4.1 参数的影响及选择??22.4.2 延伸阅读22.5 参考文献  3、主程序： %% 清空环境变量 clear all clc %% 导入数据 load citys_data.mat %% 计算城市间相互距离 n = size(citys,1); D = zeros(n,n); for i = 1:n for j = 1:n if i ~= j D(i,j) = sqrt(sum((citys(i,:) - citys(j,:)).^2)); else D(i,j) = 1e-4; end end end %% 初始化参数 m = 50; % 蚂蚁数量 alpha = 1; % 信息素重要程度因子 beta = 5; % 启发函数重要程度因子 rho = 0.1; % 信息素挥发因子 Q = 1; % 常系数 Eta = 1./D; % 启发函数 Tau = ones(n,n); % 信息素矩阵 Table = zeros(m,n); % 路径记录表 iter = 1; % 迭代次数初值 iter_max = 200; % 最大迭代次数 Route_best = zeros(iter_max,n); % 各代最佳路径 Length_best = zeros(iter_max,1); % 各代最佳路径的长度 Length_ave = zeros(iter_max,1); % 各代路径的平均长度 %% 迭代寻找最佳路径 while iter = iter_max % 随机产生各个蚂蚁的起点城市 start = zeros(m,1); for i = 1:m temp = randperm(n); start(i) = temp(1); end Table(:,1) = start; % 构建解空间 citys_index = 1:n; % 逐个蚂蚁路径选择