蚁群算法
MATLAB–基于蚁群算法的机器人最短路径规划*
https://blog.csdn.net/woai210shiyanshi/article/details/104712540?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522168853912916800215023827%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=168853912916800215023827&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2allfirst_rank_ecpm_v1~hot_rank-28-104712540-null-null.142v88control_2,239v2insert_chatgpt&utm_term=%E8%9A%81%E7%BE%A4%E7%AE%97%E6%B3%95%E8%B7%AF%E5%BE%84%E8%A7%84%E5%88%92matlab&spm=1018.2226.3001.4187
一、蚁群算法蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来寻找最优解决方案的机率型技术。它由Marco Dorigo于1992年在他的博士论文中引入，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。
蚂蚁在路径上前进时会根据前边走过的蚂蚁所留下的分泌物选择其要走的路径。其选择一条路径的概率与该路径上分泌物的强度成正比。因此，由大量蚂蚁组成的群体的集体行为实际上构成一种学习信息的正反馈现象：某一条路径走过的蚂蚁越多，后面的蚂蚁选择该路径的可能性就越大。蚂蚁的个体间通过这种信息的交流寻求通向食物的最短路径。
蚁群算法就是根据这一特点，通过模仿蚂蚁的行为，从而实现寻优。这种算法有别于传统编程模式，其优势在于，避免了冗长的编程和筹划，程序本身是基于一定规则的随机运行来寻找最佳配置。也就是说，当程序最开始找到目标的时候，路径几乎不可能是最优的，甚至可能是包含了无数错误的选择而极度冗长的。但是，程序可以通过蚂蚁寻找食物的时候的信息素原理，不断地去修正原来的路线，使整个路线越来越短，也就是说，程序执行的时间越长，所获得的路径就越可能接近最优路径。这看起来很类似与我们所见的由无数例子进行归纳概括形成最佳路径的过程。实际上好似是程序的一个自我学习的过程。
二、这种优化过程的本质在于：
选择机制：信息素越多的路径，被选择的概率越大。更新机制：路径上面的信息素会随蚂蚁的经过而增长，而且同时也随时间的推移逐渐挥发消失。
协调机制：蚂蚁间实际上是通过分泌物来互相通信、协同工作的。蚁群算法正是充分利用了选择、更新和协调的优化机制，即通过个体之间的信息交流与相互协作最终找到最优解，使它具有很强的发现较优解的能力。基于以上机制编写的程序的核心代码可能不过上百行，却完成了类似于学习的过程。原因就是所谓的自组织理论，简单规则的涌现。事实上，每只蚂蚁并不是像我们想象的需要知道整个世界的信息，他们其实只关心很小范围内的眼前信息，而且根据这些局部信息利用几条简单的规则进行决策，但是，当集群里有无数蚂蚁的时候，复杂性的行为就会凸现出来。这就是人工生命、复杂性科学解释的规律！
那么，这些简单规则是什么呢？下面详细说明：
1、范围：蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3），那么它能观察到的范围就是3*3个方格世界，并且能移动的距离也在这个范围之内。
2、环境：蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让信息素消失。
3、觅食规则：在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地方走，并且每只蚂蚁多会以小概率犯错误，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应。
4、移动规则： 每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开。
5、避障规则：如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为。
6、播撒信息素规则：每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走远的距离，播撒的信息素越来越少。根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁都和环境发生交互，而通过信息素这个纽带，实际上把各个蚂蚁之间关联起来了。比如，当一只蚂蚁找到了食物，它并没有直接告诉其它蚂蚁这儿有食物，而是向环境播撒信息素，当其它的蚂蚁经过它附近的时候，就会感觉到信息素的存在，进而根据信息素的指引找到了食物。
****https://www.cnblogs.com/Qling/p/9348098.html
蚁群算法简介及应用https://www.cnblogs.com/lfri/p/12242311.html
对蚁群算法的解释https://www.cnblogs.com/wukuanglin/p/11799162.html
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CAHGDXbo-1688540710156)(2023-07-01-11-41-34.png)]
C语言实现https://www.cnblogs.com/paulbai/archive/2012/03/21/2410695.html
蚁群算法求解TSP问题https://www.cnblogs.com/twzh123456/p/11798800.html
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Zdjy73I4-1688540710158)(2023-07-01-11-41-44.png)]
蚁群算法的原理
蚁群算法的原理主要基于蚂蚁在寻找食物过程中的行为和信息素的释放。其基本步骤如下：
- 初始化：设置蚂蚁的数量、城市之间的距离信息、信息素初始浓度等参数。
- 蚂蚁路径选择：每只蚂蚁根据一定的规则选择下一个要访问的城市。一般情况下，蚂蚁会根据信息素浓度和启发函数值来做出选择。信息素浓度高的路径和启发函数值大的路径更容易被选择。
- 路径更新：蚂蚁访问完所有的城市后，根据其走过的路径长度更新路径上的信息素浓度。一般情况下，路径上的信息素浓度会随时间蒸发，而蚂蚁经过的路径上会释放一定量的信息素。路径上的信息素浓度更新公式如下：
Δτij = Q / L ，其中 Δτij 为路径上信息素的增量，Q 为信息素常数，L 是蚂蚁经过的路径长度。 - 全局信息素更新：所有蚂蚁完成路径选择和信息素更新后，进行全局信息素的更新。全局信息素的更新可以通过蒸发和新信息素的释放来实现。蒸发可以将信息素浓度逐渐降低，而新信息素的释放可以在最短路径上增加信息素浓度。
- 终止条件判断：根据预定的终止条件（例如达到最大迭代次数或找到满意的解），判断是否需要终止算法。如果不满足终止条件，则返回步骤2；否则，输出当前最优解。
通过不断的迭代，蚁群算法能够逐渐收敛到问题的最优解。由于蚂蚁之间的信息交流和信息素的更新，蚁群算法能够在搜索空间中进行全局搜索和局部搜索，找到较优的解。
蚁群算法（Ant Colony Optimization，ACO）是一种基于蚂蚁行为模拟的启发式优化算法，通常用于解决组合优化问题，如旅行商问题（TSP）和任务分配问题等。蚁群算法的核心思想是通过模拟蚂蚁在搜索空间中的移动和信息交流来寻找问题的最优解。
蚁群算法的基本原理是通过大量的人工蚂蚁在问题空间中进行随机搜索，并通过信息素的更新和挥发来引导蚂蚁的行动。每只蚂蚁在搜索过程中根据信息素以及启发函数（heuristic function）做出决策，选择下一个要遍历的节点。成功的路径上会释放更多的信息素，这样其他蚂蚁就有更大可能性选择该路径，逐步形成一个正向反馈的过程，最终收敛到问题的最优解。
蚁群算法包括两个重要的步骤：路径选择和信息素更新。路径选择是蚂蚁根据信息素和启发函数选择下一个节点的过程。信息素更新是指在每次迭代后，根据蚂蚁的走过的路径和目标函数值，更新问题空间中各个路径上的信息素。
蚁群算法的优势在于能够处理复杂的组合优化问题，并且具有一定的鲁棒性和适应性。它结合了局部搜索和全局搜索的特点，能够在搜索过程中充分利用已有的信息，并通过信息素的引导实现全局搜索。
然而，蚁群算法也存在一些挑战和限制。首先，算法的性能高度依赖于参数的选择和调整。不同问题可能需要不同的参数设置，这对问题的适应性和通用性提出了要求。其次，蚁群算法在解决大规模问题时可能遇到搜索空间爆炸的问题，导致计算复杂度增加。此外，蚁群算法的收敛速度较慢，需要进行多次迭代才能得到较好的解。
总之，蚁群算法是一种基于模拟蚂蚁行为的启发式优化算法，适用于解决组合优化问题。它通过蚂蚁的搜索和信息交流来寻找最优解，并具有一定的鲁棒性和适应性。然而，在使用蚁群算法时需要仔细选择参数和调整算法以获得较好的性能。
蚁群算法的基本原理:
1、蚂蚁在路径上释放信息素。
2、碰到还没走过的路口，就随机挑选一条路走。同时，释放与路径长度有关的信息素。
3、信息素浓度与路径长度成反比。后来的蚂蚁再次碰到该路口时，就选择信息素浓度较高路径。
4、最优路径上的信息素浓度越来越大。
5、最终蚁群找到最优寻食路径。
当应用蚁群算法解决问题时，通常会遵循以下步骤：
- 定义问题：明确问题的目标和约束条件。将问题转化为适合蚁群算法求解的形式，如旅行商问题、任务分配问题等。
- 初始化参数：确定蚁群算法的相关参数，包括蚂蚁数量、信息素初始值、信息素挥发率等。这些参数的选择对算法的性能和收敛速度有重要影响。
- 创建蚂蚁群体：根据问题的规模和复杂程度，创建一定数量的蚂蚁，并将它们放置在问题空间中的不同位置。
- 路径选择：每只蚂蚁根据信息素和启发函数决策下一个要遍历的节点。信息素表示路径上的足迹，启发函数则提供了节点间的启发信息。蚂蚁可以通过概率方法（如轮盘赌选择法）来选择下一个节点。
- 更新信息素：在每一次迭代结束后，根据蚂蚁的路径和目标函数值，更新问题空间中各个路径上的信息素。成功的路径上将释放更多的信息素，而信息素会随时间挥发。这样，经过多次迭代，优良路径上的信息素逐渐增加，而不良路径上的信息素则减少。
- 判断终止条件：根据问题的要求和算法的性能，设定适当的终止条件，如达到最大迭代次数、目标函数值达到阈值等。
- 输出最优解：最终，根据蚁群算法的迭代结果，输出找到的最优解或近似最优解。
需要注意的是，蚁群算法中的启发函数和信息素更新策略可以根据具体问题进行设计。启发函数可以根据节点间的距离、经验知识等提供指导信息。信息素更新策略可以根据蚂蚁的走过的路径和目标函数值来确定。
此外，为了提高蚁群算法的性能，常常使用一些改进策略，如引入局部搜索机制（如2-opt操作）、采用多种信息素调整方式（如最大最小蚁群系统）等。
总结起来，蚁群算法通过模拟蚂蚁行为的方式，通过路径选择和信息素更新来求解组合优化问题。这个算法的基本步骤包括定义问题、初始化参数、创建蚂蚁群体、路径选择、信息素更新、判断终止条件和输出最优解。通过合理的参数设置和改进策略，蚁群算法可以得到较好的优化性能和近似最优解。
以下是一个简单的 Matlab 代码示例，演示如何使用蚁群算法解决旅行商问题（TSP）：
% TSP问题的距离矩阵 distanceMatrix = [0, 2, 9, 10; 1, 0, 6, 4; 15, 7, 0, 8; 6, 3, 12, 0]; % 参数设置 numAnts = 10; % 蚂蚁数量 numIterations = 100; % 迭代次数 alpha = 1; % 信息素重要程度因子 beta = 2; % 启发信息重要程度因子 rho = 0.5; % 信息素挥发率 Q = 1; % 信息素增加强度因子 % 初始化信息素矩阵 pheromoneMatrix = ones(size(distanceMatrix)) / numel(distanceMatrix); % 迭代寻找最优路径 bestPath = []; bestDistance = Inf; for iter = 1:numIterations % 每只蚂蚁的当前位置和已经访问过的节点 antPos = ones(numAnts, 1); visitedNodes = false(size(distanceMatrix)); % 每只蚂蚁进行路径选择 for ant = 1:numAnts while any(~visitedNodes(ant,:)) currentNode = antPos(ant); unvisitedNodes = find(~visitedNodes(ant,:)); % 计算节点选择概率 nodeProbs = (pheromoneMatrix(currentNode, unvisitedNodes) .^ alpha) ... .* ((1 ./ distanceMatrix(currentNode, unvisitedNodes)) .^ beta); nodeProbs = nodeProbs / sum(nodeProbs); % 根据概率选择下一个节点 nextNode = randsample(unvisitedNodes, 1, true, nodeProbs); % 更新蚂蚁位置和已访问节点 antPos(ant) = nextNode; visitedNodes(ant, nextNode) = true; end end % 计算每只蚂蚁的路径距离 pathDistances = zeros(numAnts, 1); for ant = 1:numAnts nodes = [antPos(ant); find(visitedNodes(ant,:))]; pathDist = distanceMatrix(sub2ind(size(distanceMatrix), nodes(1:end-1), nodes(2:end))); pathDistances(ant) = sum(pathDist); end % 更新最优路径 [minDist, minIdx] = min(pathDistances); if minDist < bestDistance bestDistance = minDist; bestPath = [antPos(minIdx), find(visitedNodes(minIdx,:))]; end % 更新信息素矩阵 deltaPheromoneMatrix = zeros(size(distanceMatrix)); for ant = 1:numAnts nodes = [antPos(ant); find(visitedNodes(ant,:))]; for i = 1:length(nodes)-1 deltaPheromoneMatrix(nodes(i), nodes(i+1)) = deltaPheromoneMatrix(nodes(i), nodes(i+1)) + Q / pathDistances(ant); end end pheromoneMatrix = (1-rho) * pheromoneMatrix + deltaPheromoneMatrix; end % 输出结果 disp('最优路径：'); disp(bestPath); disp('最优距离：'); disp(bestDistance);
蚁群算法的用途
蚁群算法是一种模拟蚂蚁在寻找食物时的行为而发展起来的优化算法。它通过模拟蚂蚁群体的行为，利用蚂蚁间的信息交流和反馈机制，寻找最优解或接近最优解。
蚁群算法在许多领域都有广泛的应用，包括但不限于以下几个方面：
- 旅行商问题（TSP）：蚁群算法可以用于求解旅行商问题，即在给定一系列城市和距离的情况下，找到最短路径，让旅行商依次访问每个城市并返回起始城市。
- 网络路由优化：蚁群算法可以用于优化网络中的路由选择，使得数据包在网络中传输的路径更加高效。
- 图像处理：蚁群算法可以用于图像分割、图像识别等图像处理任务中，帮助寻找最优的分割或特征提取方法。
- 电力系统优化：蚁群算法可以用于电力系统中的潮流计算、最优电压控制、电力调度等问题，优化电力系统的运行效率。
- 机器学习：蚁群算法可以用于优化机器学习算法中的参数选择和模型选择，提高机器学习算法的性能和准确度。
蚁群算法可以应用于很多优化问题，特别是那些复杂、多约束的问题。它具有并行、自适应、全局搜索和鲁棒性等优点，对于求解大规模和复杂问题具有一定的优势。
以下是一个使用蚁群算法解决旅行商问题（TSP）的示例代码：
import numpy as np # 蚂蚁类 class Ant: def __init__(self, num_cities): self.num_cities = num_cities self.tabu_list = [] # 已经访问过的城市 self.total_distance = 0 # 路径总距离 self.curr_city = -1 # 当前所在城市 self.tour = [0] * self.num_cities # 已经访问的路径 # 选择下一个要访问的城市 def choose_next_city(self, pheromone, distance, alpha, beta): probs = self.calculate_probs(pheromone, distance, alpha, beta) next_city = np.random.choice(range(self.num_cities), p=probs) self.tabu_list.append(next_city) self.tour[next_city] = 1 self.total_distance += distance[self.curr_city][next_city] self.curr_city = next_city # 计算下一个城市的选择概率 def calculate_probs(self, pheromone, distance, alpha, beta): pheromone_tau = np.power(pheromone[self.curr_city], alpha) # 信息素 visibility_eta = np.power(1 / distance[self.curr_city], beta) # 能见度 numerator = np.multiply(pheromone_tau, visibility_eta) denominator = np.sum(numerator) probs = numerator / denominator probs[self.tabu_list] = 0 # 已访问过的城市概率设为0 probs /= np.sum(probs) # 归一化 return probs # 蚁群算法类 class AntColony: def __init__(self, num_ants, num_iterations, alpha, beta, rho, q): self.num_ants = num_ants # 蚂蚁数量 self.num_iterations = num_iterations # 迭代次数 self.alpha = alpha # 信息素重要程度 self.beta = beta # 能见度重要程度 self.rho = rho # 信息素挥发速度 self.q = q # 信息素增强强度 # 通过蚁群算法解决TSP问题 def solve(self, distance): num_cities = distance.shape[0] pheromone = np.ones((num_cities, num_cities)) # 信息素矩阵 best_tour = None best_distance = np.inf for iteration in range(self.num_iterations): ants = [Ant(num_cities) for _ in range(self.num_ants)] for ant in ants: for _ in range(num_cities - 1): ant.choose_next_city(pheromone, distance, self.alpha, self.beta) ant.total_distance += distance[ant.curr_city][0] # 返回起始城市 if ant.total_distance < best_distance: best_distance = ant.total_distance best_tour = ant.tour.copy() delta_pheromone = np.zeros((num_cities, num_cities)) for ant in ants: for i in range(num_cities - 1): delta_pheromone[ant.tabu_list[i]][ant.tabu_list[i + 1]] += self.q / ant.total_distance delta_pheromone[ant.tabu_list[-1]][ant.tabu_list[0]] += self.q / ant.total_distance pheromone = pheromone * (1 - self.rho) + delta_pheromone return best_tour, best_distance # 定义城市坐标和距离矩阵 cities = np.array([[0, 0], [1, 5], [2, 3], [3, 7], [4, 1]]) num_cities = cities.shape[0] distance_matrix = np.zeros((num_cities, num_cities)) for i in range(num_cities): for j in range(num_cities): distance_matrix[i][j] = np.linalg.norm(cities[i] - cities[j]) # 创建蚁群算法对象并求解TSP问题 ant_colony = AntColony(num_ants=10, num_iterations=100, alpha=1, beta=5, rho=0.5, q=100) best_tour, best_distance = ant_colony.solve(distance_matrix) # 输出结果 print("最优路径:", best_tour) print("最优距离:", best_distance)
这个示例代码演示了如何使用蚁群算法解决旅行商问题。首先定义了蚂蚁类和蚁群算法类，然后根据城市坐标计算距离矩阵。接下来，创建蚁群算法对象并调用solve方法求解TSP问题。最后，输出最优路径和最优距离。
clear all clc G=[ 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 1 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0 1 1 1 0 0 1 1 0 0 0 1 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 1 1 1 1 0 0 1 1 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 ]; MM = size(G,1); figure(3) axis([0,MM,0,MM]) for i=1:MM for j=1:MM if G(i,j)==1 x1=j-1;y1=MM-i; x2=j;y2=MM-i; x3=j;y3=MM-i+1; x4=j-1;y4=MM-i+1; fill([x1,x2,x3,x4],[y1,y2,y3,y4],[0.3,0.3,0.3]); hold on else x1=j-1;y1=MM-i; x2=j;y2=MM-i; x3=j;y3=MM-i+1; x4=j-1;y4=MM-i+1; fill([x1,x2,x3,x4],[y1,y2,y3,y4],[1,1,1]); hold on end end end %把栅格地图转为邻接矩阵 MM=size(G,1);%返回G的行数 D=zeros(MM*MM,MM*MM);%N表示问题的规模（象素个数）返回矩阵D行数 a=1;%小方格象素的边长 % Ex=a*(mod(E,MM)-0.5);%终止点横坐标 a乘以变量E对MM（行）取余(得到列)后减0.5 即所处列 % if Ex==-0.5 % Ex=MM-0.5; % end % Ey=a*(MM+0.5-ceil(E/MM));%E/MM结果取整 终止点纵坐标 % Eta=zeros(1,N);%启发式信息，取为至目标点的直线距离的倒数 初始信息素矩阵 for i= 1:MM for j=1:MM if G(i,j)==0 for m=1:MM for n=1:MM if G(m,n)==0 im=abs(i-m); jn=abs(j-n); if(im+jn==1)||(im==1&&jn==1) D((i-1)*MM+j,(m-1)*MM+n)=(im+jn)^0.5; end end end end end end end for i= 1:MM for j=1:MM if G(i,j)==1 for m=1:MM for n=1:MM if G(m,n)==1 im=abs(i-m); jn=abs(j-n); if(im==1&&jn==1) if j>n if i>m D((i-2)*MM+j,(i-1)*MM+j-1)=0; %YY=(i-2)*MM+j; end if i<m D(i*MM+j,(i-1)*MM+j-1)=0; %YY=i*MM+j; end %%XX=(i-1)*MM+j-1; end if j<n %XX=(i-1)*MM+j+1; if i>m D((i-2)*MM+j,(i-1)*MM+j+1)=0; %YY=(i-2)*MM+j; end if i<m D(i*MM+j,(i-1)*MM+j+1)=0; %YY=i*MM+j; end end end end end end end end end N=size(D,1); %下面构造启发式信息矩阵 Eta=zeros(1,N);%启发式信息，取为至目标点的直线距离的倒数 初始信息素矩阵 for i=1:MM for j=1:MM Eta(1,(i-1)*MM+j)=((MM-i)^2+(MM-j)^2)^0.5; end end Eta(1,MM*MM)=0.01; K=100; S=1; M=50; p = 2 ; Alpha= 1.5 ; %% Alpha表征信息素重要程度的参数 Beta = 6 ; % % Beta表征启发式因子重要程度的参数 Rho = 0.2; % Rho信息素蒸发系数 sim= 0.3 ; %西格玛 Q = 1 ; % Q信息素增加强度系数 minkl = inf ; minkm = inf ; N=size(D,1); minl = 0 ; Tau=ones(N,N);%信息素 ROUTES=cell(K,M);%用细胞结构存储每一代的每一只蚂蚁的爬行路线 蚂蚁个数*迭代次数矩阵，每个元素是一个结构 PL=zeros(K,M);%用矩阵存储每一代的每一只蚂蚁的爬行路线长度 %% -----------启动K轮蚂蚁觅食活动，每轮派出M只蚂蚁-------------------- tic for k=1:K %disp(k); for m=1:M %% 第一步：状态初始化 W=S;%当前节点初始化为起始点 Path=S;%爬行路线初始化 pathlength=0;%爬行路线长度初始化 Tabu=ones(1,N); %生成禁忌列表,所有节点均未走过，所以都置为1 Tabu(S)=0;%已经在初始点了，因此要排除 DD=D;%邻接矩阵初始化 %% 第二步：下一步可以前往的节点 DW=DD(W,:); LJD=find(DW>0);%可选节点集 即返回可以走的节点坐标<矩阵编号> Len_LJD=length(LJD);%计数 可选节点的个数 %% 觅食停止条件：蚂蚁未遇到食物或者陷入死胡同 while Len_LJD>=1&&W~=N %W~=E&& %% 第三步：转轮赌法选择下一步怎么走 node=zeros(1,Len_LJD); %遍历可选节点 for i=1:Len_LJD node(i)=(Tau(W,LJD(i))^Alpha)*((1/Eta(1,LJD(i)))^Beta); %w行i个节点 end node=node/(sum(node));%建立概率分布 把各个路径的概率统一到和为1； Pcum=cumsum(node); %node累计值 Select=find(Pcum>=rand);%产生任意0~1之间的随机数，轮盘赌算法，尽量避免陷入局部最优解 to_visit=LJD(Select(1));%下一步将要前往的节点 %% 第四步：状态更新和记录 Path=[Path,to_visit];%路线节点增加 pathlength=pathlength+DD(W,to_visit);%路径长度增加，记录本次迭代最佳路线长度，每只蚂蚁都有自己走过的长度记录在向量中。 W=to_visit;%蚂蚁移到下一个节点 %N：所有点 for n=1:N if Tabu(n)==0 %禁忌列表 DD(W,n)=0; %在此次循环中设置为不可达 DD(n,n)=0; end end Tabu(W)=0;%已访问过的节点从禁忌表中删除 DW=DD(W,:); LJD=find(DW>0);%可选节点集 Len_LJD=length(LJD);%可选节点的个数 end %% 第五步：记下每一代每一只蚂蚁的觅食路线和路线长度 ROUTES{k,m}=Path; %第k次迭代 第m只蚂蚁的路线 if Path(end)==N PL(k,m)=pathlength; %到达目标点的路线长度 else PL(k,m)=inf; %进入死胡同 end end %% 第六步：更新信息素 Delta_Tau=zeros(N,N);%更新量初始化 for mm=1:M %M只蚂蚁 if PL(k,mm)<inf %顺利到达目标点的蚂蚁路线长度 ROUT=ROUTES{k,mm}; %具体路线 TS=length(ROUT)-1; %跳数 蚂蚁转移次数 PL_km=PL(k,mm);%路线长度 for s=1:TS x=ROUT(s); %上一个节点 y=ROUT(s+1); %下一个节点 Delta_Tau(x,y)=Delta_Tau(x,y)+Q/PL_km; %(x,y)即两个节点之间的关系(信息素量) 系数除以路线长度 Delta_Tau(y,x)=Delta_Tau(y,x)+Q/PL_km; end end end Tau=(1-Rho).*Tau+Delta_Tau;%信息素挥发一部分，新增加一部分 end toc %% ---------------------------绘图-------------------------------- figure(4) axis([0,K,0,20]) for i=1:K ggb=PL(i,:); mmmda(i)=sum(ggb)/50; end plot(mmmda) plotif=1; %是否绘图的控制参数 if plotif==1 %绘收敛曲线 meanPL=zeros(1,K); %k：迭代次数 minPL=zeros(1,K); for i=1:K PLK=PL(i,:); %将第i次迭代爬行路线长度赋值给PLK Nonzero=find(PLK<inf);%返回一系列可行路线的编号 if length(Nonzero)~=0 PLKPLK=PLK(Nonzero);%留下可行路线，重新排列 meanPL(i)=mean(PLKPLK); %求取这次可行路径的平均值 minPL(i)=min(PLKPLK);%提出最小路径 end end end plotif3=1;%绘最短蚂蚁爬行图 if plotif3==1 figure(2) axis([0,MM,0,MM]) for i=1:MM for j=1:MM if G(i,j)==1 x1=j-1;y1=MM-i; x2=j;y2=MM-i; x3=j;y3=MM-i+1; x4=j-1;y4=MM-i+1; fill([x1,x2,x3,x4],[y1,y2,y3,y4],[0.2,0.2,0.2]); hold on else x1=j-1;y1=MM-i; x2=j;y2=MM-i; x3=j;y3=MM-i+1; x4=j-1;y4=MM-i+1; fill([x1,x2,x3,x4],[y1,y2,y3,y4],[1,1,1]); hold on end end end minmumPLK=inf; for k=1:K PLK=PL(k,:); %将第k次迭代爬行路线长度赋值给PLK minPLK=min(PLK); if(minPLK<minmumPLK) pos=find(PLK==minPLK); %找到与最短爬行路线长度相等的路径标号 minmumPLK=minPLK; minm=pos(1); mink=k ; %迭代k次 end end ROUT=ROUTES{mink,minm}; %找出最小路径路线 LENROUT=length(ROUT); Rx=ROUT; Ry=ROUT; for ii=1:LENROUT Rx(ii)=a*(mod(ROUT(ii),MM)-0.5); if Rx(ii)==-0.5 Rx(ii)=MM-0.5; end Ry(ii)=a*(MM+0.5-ceil(ROUT(ii)/MM)); end plot(Rx,Ry) hold on end
TSP问题求解代码：
https://blog.csdn.net/weixin_43102634/article/details/102996297?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522168853912916800215023827%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=168853912916800215023827&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2allfirst_rank_ecpm_v1~hot_rank-7-102996297-null-null.142v88control_2,239v2insert_chatgpt&utm_term=%E8%9A%81%E7%BE%A4%E7%AE%97%E6%B3%95%E8%B7%AF%E5%BE%84%E8%A7%84%E5%88%92matlab&spm=1018.2226.3001.4187
%% 清空环境变量 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; % 逐个蚂蚁路径选择 for i = 1:m % 逐个城市路径选择 for j = 2:n tabu = Table(i,1:(j - 1)); % 已访问的城市集合(禁忌表) allow_index = ~ismember(citys_index,tabu); allow = citys_index(allow_index); % 待访问的城市集合 P = allow; % 计算城市间转移概率 for k = 1:length(allow) P(k) = Tau(tabu(end),allow(k))^alpha * Eta(tabu(end),allow(k))^beta; end P = P/sum(P); % 轮盘赌法选择下一个访问城市 Pc = cumsum(P); target_index = find(Pc >= rand); target = allow(target_index(1)); Table(i,j) = target; end end % 计算各个蚂蚁的路径距离 Length = zeros(m,1); for i = 1:m Route = Table(i,:); for j = 1:(n - 1) Length(i) = Length(i) + D(Route(j),Route(j + 1)); end Length(i) = Length(i) + D(Route(n),Route(1)); end % 计算最短路径距离及平均距离 if iter == 1 [min_Length,min_index] = min(Length); Length_best(iter) = min_Length; Length_ave(iter) = mean(Length); Route_best(iter,:) = Table(min_index,:); else [min_Length,min_index] = min(Length); Length_best(iter) = min(Length_best(iter - 1),min_Length); Length_ave(iter) = mean(Length); if Length_best(iter) == min_Length Route_best(iter,:) = Table(min_index,:); else Route_best(iter,:) = Route_best((iter-1),:); end end % 更新信息素 Delta_Tau = zeros(n,n); % 逐个蚂蚁计算 for i = 1:m % 逐个城市计算 for j = 1:(n - 1) Delta_Tau(Table(i,j),Table(i,j+1)) = Delta_Tau(Table(i,j),Table(i,j+1)) + Q/Length(i); end Delta_Tau(Table(i,n),Table(i,1)) = Delta_Tau(Table(i,n),Table(i,1)) + Q/Length(i); end Tau = (1-rho) * Tau + Delta_Tau; % 迭代次数加1，清空路径记录表 iter = iter + 1; Table = zeros(m,n); end %% 结果显示 [Shortest_Length,index] = min(Length_best); Shortest_Route = Route_best(index,:); disp(['最短距离:' num2str(Shortest_Length)]); disp(['最短路径:' num2str([Shortest_Route Shortest_Route(1)])]); %% 绘图 figure(1) plot([citys(Shortest_Route,1);citys(Shortest_Route(1),1)],... [citys(Shortest_Route,2);citys(Shortest_Route(1),2)],'o-'); grid on for i = 1:size(citys,1) text(citys(i,1),citys(i,2),[' ' num2str(i)]); end text(citys(Shortest_Route(1),1),citys(Shortest_Route(1),2),' 起点'); text(citys(Shortest_Route(end),1),citys(Shortest_Route(end),2),' 终点'); xlabel('城市位置横坐标') ylabel('城市位置纵坐标') title(['蚁群算法优化路径(最短距离:' num2str(Shortest_Length) ')']) figure(2) plot(1:iter_max,Length_best,'b',1:iter_max,Length_ave,'r:') legend('最短距离','平均距离') xlabel('迭代次数') ylabel('距离') title('各代最短距离与平均距离对比') %% 二维路线规划代码： %% 清空环境 clc;clear %% 障碍物数据 position = load('barrier.txt'); plot([0,200],[0,200],'.'); hold on B = load('barrier.txt'); xlabel('km','fontsize',12) ylabel('km','fontsize',12) title('二维规划空间','fontsize',12) %% 描述起点和终点 S = [20,180]; T = [160,90]; plot([S(1),T(1)],[S(2),T(2)],'.'); % 图形标注 text(S(1)+2,S(2),'S'); text(T(1)+2,T(2),'T'); %% 描绘障碍物图形 fill(position(1:4,1),position(1:4,2),[0,0,0]); fill(position(5:8,1),position(5:8,2),[0,0,0]); fill(position(9:12,1),position(9:12,2),[0,0,0]); fill(position(13:15,1),position(13:15,2),[0,0,0]); % 下载链路端点数据 L = load('lines.txt'); %% 描绘线及中点 v = zeros(size(L)); for i=1:20 plot([position(L(i,1),1),position(L(i,2),1)],[position(L(i,1),2)... ,position(L(i,2),2)],'color','black','LineStyle','--'); v(i,:) = (position(L(i,1),:)+position(L(i,2),:))/2; plot(v(i,1),v(i,2),'*'); text(v(i,1)+2,v(i,2),strcat('v',num2str(i))); end %% 描绘可行路径 sign = load('matrix.txt'); [n,m]=size(sign); for i=1:n if i == 1 for k=1:m-1 if sign(i,k) == 1 plot([S(1),v(k-1,1)],[S(2),v(k-1,2)],'color',... 'black','Linewidth',2,'LineStyle','-'); end end continue; end for j=2:i if i == m if sign(i,j) == 1 plot([T(1),v(j-1,1)],[T(2),v(j-1,2)],'color',... 'black','Linewidth',2,'LineStyle','-'); end else if sign(i,j) == 1 plot([v(i-1,1),v(j-1,1)],[v(i-1,2),v(j-1,2)],... 'color','black','Linewidth',2,'LineStyle','-'); end end end end path = DijkstraPlan(position,sign); j = path(22); plot([T(1),v(j-1,1)],[T(2),v(j-1,2)],'color','yellow','LineWidth',3,'LineStyle','-.'); i = path(22); j = path(i); count = 0; while true plot([v(i-1,1),v(j-1,1)],[v(i-1,2),v(j-1,2)],'color','yellow','LineWidth',3,'LineStyle','-.'); count = count + 1; i = j; j = path(i); if i == 1 || j==1 break; end end plot([S(1),v(i-1,1)],[S(2),v(i-1,2)],'color','yellow','LineWidth',3,'LineStyle','-.'); count = count+3; pathtemp(count) = 22; j = 22; for i=2:count pathtemp(count-i+1) = path(j); j = path(j); end path = pathtemp; path = [1 9 8 7 13 14 12 22]; %% 蚁群算法参数初始化 pathCount = length(path)-2; %经过线段数量 pheCacuPara=2; %信息素计算参数 pheThres = 0.8; %信息素选择阈值 pheUpPara=[0.1 0.0003]; %信息素更新参数 qfz= zeros(pathCount,10); %启发值 phePara = ones(pathCount,10)*pheUpPara(2); %信息素 qfzPara1 = ones(10,1)*0.5; %启发信息参数 qfzPara2 = 1.1; %启发信息参数 m=10; %种群数量 NC=500; %循环次数 pathk = zeros(pathCount,m); %搜索结果记录 shortestpath = zeros(1,NC); %进化过程记录 %% 初始最短路径 dijpathlen = 0; vv = zeros(22,2); vv(1,:) = S; vv(22,:) = T; vv(2:21,:) = v; for i=1:pathCount-1 dijpathlen = dijpathlen + sqrt((vv(path(i),1)-vv(path(i+1),1))^2+(vv(path(i),2)-vv(path(i+1),2))^2); end LL = dijpathlen; %% 经过的链接线 lines = zeros(pathCount,4); for i = 1:pathCount lines(i,1:2) = B(L(path(i+1)-1,1),:); lines(i,3:4) = B(L(path(i+1)-1,2),:); end %% 循环搜索 for num = 1:NC %% 蚂蚁迭代寻优一次 for i=1:pathCount for k=1:m q = rand(); qfz(i,:) = (qfzPara2-abs((1:10)'/10-qfzPara1))/qfzPara2; %启发信息 if q<=pheThres%选择信息素最大值 arg = phePara(i,:).*(qfz(i,:).^pheCacuPara); j = find(arg == max(arg)); pathk(i,k) = j(1); else % 轮盘赌选择 arg = phePara(i,:).*(qfz(i,:).^pheCacuPara); sumarg = sum(arg); qq = (q-pheThres)/(1-pheThres); qtemp = 0; j = 1; while qtemp < qq qtemp = qtemp + (phePara(i,j)*(qfz(i,j)^pheCacuPara))/sumarg; j=j+1; end j=j-1; pathk(i,k) = j(1); end % 信息素更新 phePara(i,j) = (1-pheUpPara(1))*phePara(i,j)+pheUpPara(1)*pheUpPara(2); end end %% 计算路径长度 len = zeros(1,k); for k=1:m Pstart = S; Pend = lines(1,1:2) + (lines(1,3:4)-lines(1,1:2))*pathk(1,k)/10; for l=1:pathCount len(1,k) = len(1,k)+sqrt(sum((Pend-Pstart).^2)); Pstart = Pend; if l<pathCount Pend = lines(l+1,1:2) + (lines(l+1,3:4)-lines(l+1,1:2))*pathk(l+1,k)/10; end end Pend = T; len(1,k) = len(1,k)+sqrt(sum((Pend-Pstart).^2)); end %% 更新信息素 % 寻找最短路径 minlen = min(len); minlen = minlen(1); minant = find(len == minlen); minant = minant(1); % 更新全局最短路径 if minlen < LL LL = minlen; end % 更新信息素 for i=1:pathCount phePara(i,pathk(i,minant)) = (1-pheUpPara(1))* phePara(i,pathk(i,minant))+pheUpPara(1)*(1/minlen); end shortestpath(num) = minlen; end figure; plot(1:NC,shortestpath,'color','blue'); hold on % plot(1:NC,dijpathlen,'color','red'); ylabel('路径总长度'); xlabel('迭代次数'); function path = DijkstraPlan(position,sign) %% 基于Dijkstra算法的路径规划算法 %position input %节点位置 %sign input %节点间是否可达 %path output %规划路径 %% 计算路径距离 cost = ones(size(sign))*10000; [n,m] = size(sign); for i = 1:n for j = 1:m if sign(i,j) == 1 cost(i,j) = sqrt(sum((position(i,:)-position(j,:)).^2)); end end end %% 路径开始点 dist = cost(1,:); %节点间路径长度 s = zeros(size(dist)); %节点经过标志 s(1) = 1;dist(1) = 0; path = zeros(size(dist)); %依次经过的节点 path(1,:) = 1; %% 循环寻找路径点 for num = 2:n % 选择路径长度最小点 mindist = 10000; for i = 1:length(dist) if s(i) == 0 if dist(i)< mindist mindist = dist(i); u = i; end end end % 更新点点间路径 s(u) = 1; for w = 1:length(dist) if s(i) == 0 if dist(u)+cost(u,w) < dist(w) dist(w) = dist(u)+cost(u,w); path(w) = u; end end end end 三维路线规划代码： %% 该函数用于演示基于蚁群算法的三维路径规划算法 %% 清空环境 clc clear %% 数据初始化 %下载数据 load HeightData HeightData %网格划分 LevelGrid=10; PortGrid=21; %起点终点网格点 starty=10;starth=4; endy=8;endh=5; m=1; %算法参数 PopNumber=10; %种群个数 BestFitness=[]; %最佳个体 %初始信息素 pheromone=ones(21,21,21); %% 初始搜索路径 [path,pheromone]=searchpath(PopNumber,LevelGrid,PortGrid,pheromone, ... HeightData,starty,starth,endy,endh); fitness=CacuFit(path); %适应度计算 [bestfitness,bestindex]=min(fitness); %最佳适应度 bestpath=path(bestindex,:); %最佳路径 BestFitness=[BestFitness;bestfitness]; %适应度值记录 %% 信息素更新 rou=0.2; cfit=100/bestfitness; for i=2:PortGrid-1 pheromone(i,bestpath(i*2-1),bestpath(i*2))= ... (1-rou)*pheromone(i,bestpath(i*2-1),bestpath(i*2))+rou*cfit; end %% 循环寻找最优路径 for kk=1:100 %% 路径搜索 [path,pheromone]=searchpath(PopNumber,LevelGrid,PortGrid,... pheromone,HeightData,starty,starth,endy,endh); %% 适应度值计算更新 fitness=CacuFit(path); [newbestfitness,newbestindex]=min(fitness); if newbestfitness<bestfitness bestfitness=newbestfitness; bestpath=path(newbestindex,:); end BestFitness=[BestFitness;bestfitness]; %% 更新信息素 cfit=100/bestfitness; for i=2:PortGrid-1 pheromone(i,bestpath(i*2-1),bestpath(i*2))=(1-rou)* ... pheromone(i,bestpath(i*2-1),bestpath(i*2))+rou*cfit; end end %% 最佳路径 for i=1:21 a(i,1)=bestpath(i*2-1); a(i,2)=bestpath(i*2); end figure(1) x=1:21; y=1:21; [x1,y1]=meshgrid(x,y); mesh(x1,y1,HeightData) axis([1,21,1,21,0,2000]) hold on k=1:21; plot3(k(1)',a(1,1)',a(1,2)'*200,'--o','LineWidth',2,... 'MarkerEdgeColor','k',... 'MarkerFaceColor','g',... 'MarkerSize',10) plot3(k(21)',a(21,1)',a(21,2)'*200,'--o','LineWidth',2,... 'MarkerEdgeColor','k',... 'MarkerFaceColor','g',... 'MarkerSize',10) text(k(1)',a(1,1)',a(1,2)'*200,'S'); text(k(21)',a(21,1)',a(21,2)'*200,'T'); xlabel('km','fontsize',12); ylabel('km','fontsize',12); zlabel('m','fontsize',12); title('三维路径规划空间','fontsize',12) set(gcf, 'Renderer', 'ZBuffer') hold on plot3(k',a(:,1)',a(:,2)'*200,'--o') %% 适应度变化 figure(2) plot(BestFitness) title('最佳个体适应度变化趋势') xlabel('迭代次数') ylabel('适应度值') function fitness=CacuFit(path) %% 该函数用于计算个体适应度值 %path input 路径 %fitness input 路径 [n,m]=size(path); for i=1:n fitness(i)=0; for j=2:m/2 %适应度值为长度加高度 fitness(i)=fitness(i)+sqrt(1+(path(i,j*2-1)-path(i,(j-1)*2-1))^2 ... +(path(i,j*2)-path(i,(j-1)*2))^2)+abs(path(i,j*2)); end End function qfz=CacuQfz(Nexty,Nexth,Nowy,Nowh,endy,endh,abscissa,HeightData) %% 该函数用于计算各点的启发值 %Nexty Nexth input 下个点坐标 %Nowy Nowh input 当前点坐标 %endy endh input 终点坐标 %abscissa input 横坐标 %HeightData input 地图高度 %qfz output 启发值 %% 判断下个点是否可达 if HeightData(Nexty,abscissa)<Nexth*200 S=1; else S=0; end %% 计算启发值 %D距离 D=50/(sqrt(1+(Nowh*0.2-Nexth*0.2)^2+(Nexty-Nowy)^2)+sqrt((21-abscissa)^2 ... +(endh*0.2-Nexth*0.2)^2+(endy-Nowy)^2)); %计算高度 M=30/abs(Nexth+1); %计算启发值 qfz=S*M*D; function [path,pheromone]=searchpath(PopNumber,LevelGrid,PortGrid,pheromone,HeightData,starty,starth,endy,endh) %% 该函数用于蚂蚁蚁群算法的路径规划 %LevelGrid input 横向划分格数 %PortGrid input 纵向划分个数 %pheromone input 信息素 %HeightData input 地图高度 %starty starth input 开始点 %path output 规划路径 %pheromone output 信息素 %% 搜索参数 ycMax=2; %蚂蚁横向最大变动 hcMax=2; %蚂蚁纵向最大变动 decr=0.9; %信息素衰减概率 %% 循环搜索路径 for ii=1:PopNumber path(ii,1:2)=[starty,starth]; %记录路径 NowPoint=[starty,starth]; %当前坐标点 %% 计算点适应度值 for abscissa=2:PortGrid-1 %计算所有数据点对应的适应度值 kk=1; for i=-ycMax:ycMax for j=-hcMax:hcMax NextPoint(kk,:)=[NowPoint(1)+i,NowPoint(2)+j]; if (NextPoint(kk,1)<20)&&(NextPoint(kk,1)>0)&&(NextPoint(kk,2)<20)&&(NextPoint(kk,2)>0) qfz(kk)=CacuQfz(NextPoint(kk,1),NextPoint(kk,2),NowPoint(1),NowPoint(2),endy,endh,abscissa,HeightData); qz(kk)=qfz(kk)*pheromone(abscissa,NextPoint(kk,1),NextPoint(kk,2)); kk=kk+1; else qz(kk)=0; kk=kk+1; end end end %选择下个点 sumq=qz./sum(qz); pick=rand; while pick==0 pick=rand; end for i=1:25 pick=pick-sumq(i); if pick<=0 index=i; break; end end oldpoint=NextPoint(index,:); %更新信息素 pheromone(abscissa+1,oldpoint(1),oldpoint(2))=0.5*pheromone(abscissa+1,oldpoint(1),oldpoint(2)); %路径保存 path(ii,abscissa*2-1:abscissa*2)=[oldpoint(1),oldpoint(2)]; NowPoint=oldpoint; end path(ii,41:42)=[endy,endh]; end
3）构建启发式信息矩阵
对应main中的第37-59行。首先根据的是公式（1）计算终止栅格点的横纵坐标值，然后计算矩阵中每个栅格点的横纵坐标ix，iy。每个栅格的启发信息就是该点至目标点的直线距离的倒数。
用名为ROUTES的细胞结构存储每一代的每一只蚂蚁的爬行路线，MATLAB中自带的函数cell(K,M)为K行M列的数组，存储第k次迭代中第M至蚂蚁的路线。
用PL矩阵存储每一代的每一只蚂蚁的爬行路线长度，第k次迭代中第M只蚂蚁爬行路线的长度。
当参数和需要用到的信息矩阵都设置好之后，就开始迭代寻路了，对应main中第61行到150行。
（4）tic是用来计算运行时间的，从tic到to可以用来计算法的运行时间。
①对于第k次迭代中的第M只蚂蚁，都要先进行状态初始化：
将当前节点初始化为起始点。矩阵TABUkm为禁忌列表，禁忌表大小为地图像素个数，全部初始化为1，禁忌表记录走过的位置，将走过的位置由1变0。将邻栅格点代价值也初始化。
②然后开始筛选下一步可以前往的栅格点，对应main中第71-81行：
先取G2D矩阵中以当前点为局部起始点的一行。在DW1矩阵中通过调用函数find()，存储该行所有无障碍相邻栅格点（元素不为0）的索引位置。通过if循环语句，先判断TABUkm禁忌表中，该位置是否为之前走过的点 ，删除DW中所有之前已经走过的邻节点。办法是如果禁忌表中记录该位置已经走过，则取出的该行对应点位置由非0置为0，之后的寻路不再重复记录该点。这样通过for循环语句，DW中为当前节点可以选择的所有邻栅格点了。通过调用find()函数，在矩阵LJD记录未走过的点的索引号，即下一步可选的节点。调用length()，设置Len_LJD为可选节点的个数。
③对于第k次迭代中的第M只蚂蚁，开始寻找路径，对应main中第82-120行：
通过 while循环语句，蚂蚁开始觅食，while语句循环的条件是局部起始点不等于终止点，且可选节点个数大于等于1。先计算各可选择邻节点的选择概率，记录在Pcum中。然后通过轮盘赌选择下一步要走的城市，方法是：产生随机数，选出比随机大的积累概率，选择积累概率比随机数大的第一个可选择点作为行走的下一步，并取该点的索引号。然后，更新和记录该蚂蚁当前的行走路线及路径长度Path和PLkm。
④蚂蚁移到下一个节点 ，这里记得对应禁忌表修改G2D中可选择邻节点的值。还是用if循环语句，若禁忌表中该点为以走过的点，将G2D中表示起始点到终止点的对应栅格置零，以后不再对该点进行寻路。
⑤之后开始本只蚂蚁继续下一步节点继续寻路更新禁忌表：即将当前的W点在紧急表中置为以访问过的节点。禁忌表中以访问过的节点为0，未访问过的节点为1。
⑥最后，本次迭代的该蚂蚁寻路完毕。记录k次迭代中的蚂蚁m的行走路线ROUTES{k,m}。然后用if语句判断本只蚂蚁寻找路径的最后一个节点是否为终点，即判断返回矩阵Path中的最后一个元素。用if循环语句，先判断该蚂蚁到没到达终点，若该蚂蚁到达终点，将本次路线长度放到PL的第k行m列PL(k,m)。若本次路径长度<当前已知的最短路径长度，记录完成本次最短路径的迭代次数哪只蚂蚁及最短路线的长度。若该蚂蚁没有到达终点长，则本次路径长度为0
（5）返回第63行进行下一只蚂蚁的寻路
（6）本次迭代所有蚂蚁都寻路完后，更新信息素Delta_Tau，用到的length已经介绍了，这里注意，在139行，少最后一只蚂蚁的路线，是因为后面143行需要y=ROUT(s+1)更新完信息素矩阵，本次迭代完成，返回进行下一次迭代。这样蚁群寻路的程序就完成了，下面就是Matlab的画图部分。
（7）绘图的基本步骤为：创建图像窗口→添加坐标轴→添加栅格→设置填充图框→转换坐标→绘制路线。
①绘制行走路线：PL为K*M的矩阵，记录每次迭代中每只蚂蚁行走的路径长度，通过find函数提取本次迭代路径长度不为0的索引号存储至Nonzero，将路径长度不为0的路径索引号对应的路径长度存储至PLKPLK，最后通过min函数选出本次迭代最短路径存储至minPL的相应迭代位置。
调用fprintf()函数，输出最短路径 。
②绘制“收敛曲线变化趋势”图，将每次迭代的最短路径放在图中表示。调用 figure() 函数，生成图形窗口。调用 plot()生成的图横坐标为1至矩阵行数，纵坐标为0到矩阵中最大的数，矩阵中的每一列对应坐标中的一条曲线。hold on是用来保持当前图的。grid on 实在当前图上加栅格。
③在调用figure() 建立第二个图形窗口，调用axis() 设置图的横纵坐标。接下来对地图G中1的那个栅格进行涂色，涂成黑色，在175-179行里，x1234和y1234就是地图G中1那个栅格的四个顶点的坐标，fill（）函数为颜色填充。用同样的方法对对地图G中0的那些栅格进行涂白色，最后，为了使图方便看，即蚂蚁从坐标（00）走到（20 20）吧纵坐标调整一下。这里主程序的第188行和我参考的博文不同。
④画完地图就可以话上面算法求出的最短路径了，将该路线的栅格索引号转换为横纵坐标Rx,Ry，根据的公式（1），调用plot() 函数绘制路线。运行结果如下。
蚁群算法的C语言实现
https://www.cnblogs.com/paulbai/archive/2012/03/21/2410695.html
#define SPACE 0x20 /*按键定义*/ #define ESC 0x1b #define ANT_CHAR_EMPTY '+' #define ANT_CHAR_FOOD 153 /*携带食物的蚂蚁*/ #define HOME_CHAR 'H' #define FOOD_CHAR 'F' #define FOOD_CHAR2 'f' #define FOOD_HOME_COLOR 12 /*红色*/ #define BLOCK_CHAR 177 /*障碍物*/ #define MAX_ANT 50 /*蚂蚁数量*/ #define INI_SPEED 3 /*速度半径为3*3*/ #define MAXX 80 /*活动空间为80*23格*/ #define MAXY 23 #define MAX_FOOD 10000 /*最大食物量*/ #define TARGET_FOOD 200 /*需要采集回家的食物量*/ #define MAX_SMELL 5000 /*最大信息素*/ #define SMELL_DROP_RATE 0.05 /*信息素释放率*/ #define ANT_ERROR_RATE 0.02 /*蚂蚁犯错率（创新率）*/ #define ANT_EYESHOT 3 /**/ #define SMELL_GONE_SPEED 50 /*信息素消失速度*/ #define SMELL_GONE_RATE 0.05 /*信息素消失比率*/ #define TRACE_REMEMBER 50 /*蚂蚁记忆力*/ #define MAX_BLOCK 100 /*最大障碍物个数*/ #define NULL 0 #define UP 1 /*方向定义*/ #define DOWN 2 #define LEFT 3 #define RIGHT 4 #define SMELL_TYPE_FOOD 0 /*信息素类型定义*/ #define SMELL_TYPE_HOME 1 #include "stdio.h" #include "conio.h" /*getch函数需要此头文件*/ #include "dos.h" #include "stdlib.h" #include "dos.h" #include "process.h" #include "ctype.h" #include "math.h" void WorldInitial(void); /*环境初始化函数*/ void BlockInitial(void); /*障碍物地图初始化*/ void CreatBlock(void); /*产生障碍物地图*/ void SaveBlock(void); /*保存障碍物地图*/ void LoadBlock(void); /*载入障碍物地图*/ void HomeFoodInitial(void); /*食物与家的位置初始化*/ void AntInitial(void); /*蚂蚁初始化*/ void WorldChange(void); /*更改环境*/ void AntMove(void); /*蚂蚁移动*/ void AntOneStep(void); /*蚂蚁动作一步*/ void DealKey(char key); /*按键扫描，功能键有p,t,1,2,3,s,l*/ void ClearSmellDisp(void); /*关闭信息素的显示*/ void DispSmell(int type); /*显示当前信息素的情况*/ int AntNextDir(int xxx, int yyy, int ddir); /*得到蚂蚁下一次移动的方向*/ int GetMaxSmell(int type, int xxx, int yyy, int ddir); /*获取最大信息素的值*/ int IsTrace(int xxx, int yyy); /*是否是曾经走过的路径*/ int MaxLocation(int num1, int num2, int num3); /*获得三个值中最大的一个的序号*/ int CanGo(int xxx, int yyy, int ddir); /*返回可以走的路径*/ int JudgeCanGo(int xxx, int yyy); /*判断某方向是否可以通过*/ int TurnLeft(int ddir); /*左传，右转，后退*/ int TurnRight(int ddir); int TurnBack(int ddir); int MainTimer(void); /*返回自上次调用后经历了多少个10ms的时间*/ char WaitForKey(int secnum); /*没有键则等待键盘输入，有键则返回键值*/ void DispPlayTime(void); /*显示运行时间*/ int TimeUse(void); /*计算时间花费*/ void HideCur(void); /*隐藏鼠标*/ void ResetCur(void); /*重置鼠标*/ /* --------------- */ struct HomeStruct { int xxx, yyy; int amount; /*已经搬运回家的食物数量*/ int TargetFood; /*需要搬运回家的食物数量*/ } home; struct FoodStruct { int xxx, yyy; int amount; /*剩余食物数量*/ } food; struct AntStruct { int xxx, yyy; /*蚂蚁当前位置*/ int dir; /*行走方向*/ int speed; /*蚂蚁速度，即计数器计到此则移动一步，所以越小蚂蚁移动越快*/ int SpeedTimer; /*速度计数器，每10ms记一次*/ int food; /*是否携带食物*/ int SmellAmount[2]; /*两种信息素的含量*/ int tracex[TRACE_REMEMBER]; /*所记忆的x坐标*/ int tracey[TRACE_REMEMBER]; /*所记忆的y坐标*/ int TracePtr; /*记录路径所用的指针*/ int IQ; /*好象没有用到。。。。。*/ } ant[MAX_ANT]; /*全局变量定义*/ int AntNow; /*当前蚂蚁*/ int timer10ms; /*记录多少个10ms已经过去*/ struct time starttime, endtime; /*起始结束时间定义*/ int Smell[2][MAXX + 1][MAXY + 1]; /*信息素数组*/ int block[MAXX + 1][MAXY + 1]; /*障碍物数组*/ int SmellGoneTimer; /*信息素消失计数器*/ int SmellDispFlag; /*信息素显示标志*/ int CanFindFood; /*可以找到获取食物的路径标志*/ int HardtoFindPath; /*找到路径比较困难的标志*/ /* ----- Main -------- */ void main(void) { char KeyPress; int tu; clrscr(); HideCur(); WorldInitial(); do { timer10ms = MainTimer(); if (timer10ms) AntMove(); if (timer10ms) WorldChange(); tu = TimeUse(); if (tu >= 60 && !CanFindFood) { gotoxy(1, MAXY + 1); printf("Can not find food, maybe a block world."); WaitForKey(10); WorldInitial(); } if (tu >= 180 && home.amount < 100 && !HardtoFindPath) { gotoxy(1, MAXY + 1); printf("God! it is so difficult to find a path."); if (WaitForKey(10) == 0x0d) WorldInitial(); else { HardtoFindPath = 1; gotoxy(1, MAXY + 1); printf(" "); } } if (home.amount >= home.TargetFood) { gettime(&endtime); KeyPress = WaitForKey(60); DispPlayTime(); WaitForKey(10); WorldInitial(); } else if (kbhit()) { KeyPress = getch(); DealKey(KeyPress); } else KeyPress = NULL; } while (KeyPress != ESC); gettime(&endtime); DispPlayTime(); WaitForKey(10); clrscr(); ResetCur(); } /* ------ general sub process ----------- */ int MainTimer(void) /* output: how much 10ms have pass from last time call this process */ { static int oldhund, oldsec; struct time t; int timeuse; gettime(&t); timeuse = 0; if (t.ti_hund != oldhund) { if (t.ti_sec != oldsec) { timeuse += 100; oldsec = t.ti_sec; } timeuse += t.ti_hund - oldhund; oldhund = t.ti_hund; } else timeuse = 0; return (timeuse); } char WaitForKey(int secnum) /* funtion: if have key in, exit immediately, else wait 'secnum' senconds then exit input: secnum -- wait this senconds, must < 3600 (1 hour) output: key char, if no key in(exit when timeout), return NULL */ { int secin, secnow; int minin, minnow; int hourin, hournow; int secuse; struct time t; gettime(&t); secin = t.ti_sec; minin = t.ti_min; hourin = t.ti_hour; do { if (kbhit()) return (getch()); gettime(&t); secnow = t.ti_sec; minnow = t.ti_min; hournow = t.ti_hour; if (hournow != hourin) minnow += 60; if (minnow > minin) secuse = (minnow - 1 - minin) + (secnow + 60 - secin); else secuse = secnow - secin; /* counting error check */ if (secuse < 0) { gotoxy(1, MAXY + 1); printf("Time conuting error, any keyto exit..."); getch(); exit(3); } } while (secuse <= secnum); return (NULL); } void DispPlayTime(void) { int ph, pm, ps; ph = endtime.ti_hour - starttime.ti_hour; pm = endtime.ti_min - starttime.ti_min; ps = endtime.ti_sec - starttime.ti_sec; if (ph < 0) ph += 24; if (pm < 0) { ph--; pm += 60; } if (ps < 0) { pm--; ps += 60; } gotoxy(1, MAXY + 1); printf("Time use: %d hour- %d min- %d sec ", ph, pm, ps); } int TimeUse(void) { int ph, pm, ps; gettime(&endtime); ph = endtime.ti_hour - starttime.ti_hour; pm = endtime.ti_min - starttime.ti_min; ps = endtime.ti_sec - starttime.ti_sec; if (ph < 0) ph += 24; if (pm < 0) { ph--; pm += 60; } if (ps < 0) { pm--; ps += 60; } return (ps + (60 * (pm + 60 * ph))); } void HideCur(void) { union REGS regs0; regs0.h.ah = 1; regs0.h.ch = 0x30; regs0.h.cl = 0x31; int86(0x10, ? s0, ? s0); } void ResetCur(void) { union REGS regs0; regs0.h.ah = 1; regs0.h.ch = 0x06; regs0.h.cl = 0x07; int86(0x10, ? s0, ? s0); } /* ------------ main ANT programe ------------- */ void WorldInitial(void) { int k, i, j; randomize(); clrscr(); HomeFoodInitial(); for (AntNow = 0; AntNow < MAX_ANT; AntNow++) { AntInitial(); } /* of for AntNow */; BlockInitial(); for (k = 0; k <= 1; k++) /* SMELL TYPE FOOD and HOME */ for (i = 0; i <= MAXX; i++) for (j = 0; j <= MAXY; j++) Smell[k][i][j] = 0; SmellGoneTimer = 0; gettime(&starttime); SmellDispFlag = 0; CanFindFood = 0; HardtoFindPath = 0; } void BlockInitial(void) { int i, j; int bn; for (i = 0; i <= MAXX; i++) for (j = 0; j <= MAXY; j++) block[i][j] = 0; bn = 1 + MAX_BLOCK / 2 + random(MAX_BLOCK / 2); for (i = 0; i <= bn; i++) CreatBlock(); } void CreatBlock(void) { int x1, y1, x2, y2; int dx, dy; int i, j; x1 = random(MAXX) + 1; y1 = random(MAXY) + 1; dx = random(MAXX / 10) + 1; dy = random(MAXY / 10) + 1; x2 = x1 + dx; y2 = y1 + dy; if (x2 > MAXX) x2 = MAXX; if (y2 > MAXY) y2 = MAXY; if (food.xxx >= x1 && food.xxx <= x2 && food.yyy >= y1 && food.yyy <= y2) return; if (home.xxx >= x1 && home.xxx <= x2 && home.yyy >= y1 && home.yyy <= y2) return; for (i = x1; i <= x2; i++) for (j = y1; j <= y2; j++) { block[i][j] = 1; gotoxy(i, j); putch(BLOCK_CHAR); } } void SaveBlock(void) { FILE *fp_block; char FileNameBlock[20]; int i, j; gotoxy(1, MAXY + 1); printf(" "); gotoxy(1, MAXY + 1); printf("Save to file...", FileNameBlock); gets(FileNameBlock); if (FileNameBlock[0] == 0) strcpy(FileNameBlock, "Ant.ant"); else strcat(FileNameBlock, ".ant"); if ((fp_block = fopen(FileNameBlock, "wb")) == NULL) { gotoxy(1, MAXY + 1); printf("Creat file %s fail...", FileNameBlock); getch(); exit(2); } gotoxy(1, MAXY + 1); printf(" "); fputc(home.xxx, fp_block); fputc(home.yyy, fp_block); fputc(food.xxx, fp_block); fputc(food.yyy, fp_block); for (i = 0; i <= MAXX; i++) for (j = 0; j <= MAXY; j++) fputc(block[i][j], fp_block); fclose(fp_block); } void LoadBlock(void) { FILE *fp_block; char FileNameBlock[20]; int i, j, k; gotoxy(1, MAXY + 1); printf(" "); gotoxy(1, MAXY + 1); printf("Load file...", FileNameBlock); gets(FileNameBlock); if (FileNameBlock[0] == 0) strcpy(FileNameBlock, "Ant.ant"); else strcat(FileNameBlock, ".ant"); if ((fp_block = fopen(FileNameBlock, "rb")) == NULL) { gotoxy(1, MAXY + 1); printf("Open file %s fail...", FileNameBlock); getch(); exit(2); } clrscr(); home.xxx = fgetc(fp_block); home.yyy = fgetc(fp_block); food.xxx = fgetc(fp_block); food.yyy = fgetc(fp_block); gotoxy(home.xxx, home.yyy); putch(HOME_CHAR); gotoxy(food.xxx, food.yyy); putch(FOOD_CHAR); food.amount = random(MAX_FOOD / 3) + 2 * MAX_FOOD / 3 + 1; /* food.amount = MAX_FOOD; */ home.amount = 0; home.TargetFood = (food.amount < TARGET_FOOD) ? food.amount : TARGET_FOOD; for (AntNow = 0; AntNow < MAX_ANT; AntNow++) { AntInitial(); } /* of for AntNow */; for (i = 0; i <= MAXX; i++) for (j = 0; j <= MAXY; j++) { block[i][j] = fgetc(fp_block); if (block[i][j]) { gotoxy(i, j); putch(BLOCK_CHAR); } } for (k = 0; k <= 1; k++) /* SMELL TYPE FOOD and HOME */ for (i = 0; i <= MAXX; i++) for (j = 0; j <= MAXY; j++) Smell[k][i][j] = 0; SmellGoneTimer = 0; gettime(&starttime); SmellDispFlag = 0; CanFindFood = 0; HardtoFindPath = 0; fclose(fp_block); } void HomeFoodInitial(void) { int randnum; int homeplace; /* 1 -- home at left-up, food at right-down -- home at left-down, food at right-up -- home at right-up, food at left-down -- home at right-down, food at left-up */ randnum = random(100); if (randnum < 25) homeplace = 1; else if (randnum >= 25 && randnum < 50) homeplace = 2; else if (randnum >= 50 && randnum < 75) homeplace = 3; else homeplace = 4; switch (homeplace) { case 1: home.xxx = random(MAXX / 3) + 1; home.yyy = random(MAXY / 3) + 1; food.xxx = random(MAXX / 3) + 2 * MAXX / 3 + 1; food.yyy = random(MAXY / 3) + 2 * MAXY / 3 + 1; break; case 2: home.xxx = random(MAXX / 3) + 1; home.yyy = random(MAXY / 3) + 2 * MAXY / 3 + 1; food.xxx = random(MAXX / 3) + 2 * MAXX / 3 + 1; food.yyy = random(MAXY / 3) + 1; break; case 3: home.xxx = random(MAXX / 3) + 2 * MAXX / 3 + 1; home.yyy = random(MAXY / 3) + 1; food.xxx = random(MAXX / 3) + 1; food.yyy = random(MAXY / 3) + 2 * MAXY / 3 + 1; break; case 4: home.xxx = random(MAXX / 3) + 2 * MAXX / 3 + 1; home.yyy = random(MAXY / 3) + 2 * MAXY / 3 + 1; food.xxx = random(MAXX / 3) + 1; food.yyy = random(MAXY / 3) + 1; break; } food.amount = random(MAX_FOOD / 3) + 2 * MAX_FOOD / 3 + 1; /* food.amount = MAX_FOOD; */ home.amount = 0; home.TargetFood = (food.amount < TARGET_FOOD) ? food.amount : TARGET_FOOD; /* data correctness check */ if (home.xxx <= 0 || home.xxx > MAXX || home.yyy <= 0 || home.yyy > MAXY || food.xxx <= 0 || food.xxx > MAXX || food.yyy <= 0 || food.yyy > MAXY || food.amount <= 0) { gotoxy(1, MAXY + 1); printf("World initial fail, any key to exit..."); getch(); exit(2); } gotoxy(home.xxx, home.yyy); putch(HOME_CHAR); gotoxy(food.xxx, food.yyy); putch(FOOD_CHAR); } void AntInitial(void) /* initial ant[AntNow] */ { int randnum; int i; ant[AntNow].xxx = home.xxx; ant[AntNow].yyy = home.yyy; randnum = random(100); if (randnum < 25) ant[AntNow].dir = UP; else if (randnum >= 25 && randnum < 50) ant[AntNow].dir = DOWN; else if (randnum >= 50 && randnum < 75) ant[AntNow].dir = LEFT; else ant[AntNow].dir = RIGHT; ant[AntNow].speed = 2 * (random(INI_SPEED / 2) + 1); ant[AntNow].SpeedTimer = 0; ant[AntNow].food = 0; ant[AntNow].SmellAmount[SMELL_TYPE_FOOD] = 0; ant[AntNow].SmellAmount[SMELL_TYPE_HOME] = MAX_SMELL; ant[AntNow].IQ = 1; for (i = 0; i < TRACE_REMEMBER; i++) { ant[AntNow].tracex[i] = 0; ant[AntNow].tracey[i] = 0; } ant[AntNow].TracePtr = 0; /* a sepecail ant */ if (AntNow == 0) ant[AntNow].speed = INI_SPEED; } void WorldChange(void) { int k, i, j; int smelldisp; SmellGoneTimer += timer10ms; if (SmellGoneTimer >= SMELL_GONE_SPEED) { SmellGoneTimer = 0; for (k = 0; k <= 1; k++) /* SMELL TYPE FOOD and HOME */ for (i = 1; i <= MAXX; i++) for (j = 1; j <= MAXY; j++) { if (Smell[k][i][j]) { smelldisp = 1 + ((10 * Smell[k][i][j]) / (MAX_SMELL * SMELL_DROP_RATE)); if (smelldisp >= 30000 || smelldisp < 0) smelldisp = 30000; if (SmellDispFlag) { gotoxy(i, j); if ((i == food.xxx && j == food.yyy) || (i == home.xxx && j == home.yyy)) /* don't over write Food and Home */; else { if (smelldisp > 9) putch('#'); else putch(smelldisp + '0'); } } Smell[k][i][j] -= 1 + (Smell[k][i][j] * SMELL_GONE_RATE); if (Smell[k][i][j] < 0) Smell[k][i][j] = 0; if (SmellDispFlag) { if (Smell[k][i][j] <= 2) { gotoxy(i, j); putch(SPACE); } } } } /* of one location */ } /* of time to change the world */ } /* of world change */ void AntMove(void) { int antx, anty; int smelltodrop, smellnow; for (AntNow = 0; AntNow < MAX_ANT; AntNow++) { ant[AntNow].SpeedTimer += timer10ms; if (ant[AntNow].SpeedTimer >= ant[AntNow].speed) { ant[AntNow].SpeedTimer = 0; gotoxy(ant[AntNow].xxx, ant[AntNow].yyy); putch(SPACE); AntOneStep(); gotoxy(ant[AntNow].xxx, ant[AntNow].yyy); /* ant0 is a sepecail ant, use different color */ if (AntNow == 0) textcolor(0xd); if (ant[AntNow].food) putch(ANT_CHAR_FOOD); else putch(ANT_CHAR_EMPTY); if (AntNow == 0) textcolor(0x7); /* remember trace */ ant[AntNow].tracex[ant[AntNow].TracePtr] = ant[AntNow].xxx; ant[AntNow].tracey[ant[AntNow].TracePtr] = ant[AntNow].yyy; if (++(ant[AntNow].TracePtr) >= TRACE_REMEMBER) ant[AntNow].TracePtr = 0; /* drop smell */ antx = ant[AntNow].xxx; anty = ant[AntNow].yyy; if (ant[AntNow].food) /* have food, looking for home */ { if (ant[AntNow].SmellAmount[SMELL_TYPE_FOOD]) { smellnow = Smell[SMELL_TYPE_FOOD][antx][anty]; smelltodrop = ant[AntNow].SmellAmount[SMELL_TYPE_FOOD] * SMELL_DROP_RATE; if (smelltodrop > smellnow) Smell[SMELL_TYPE_FOOD][antx][anty] = smelltodrop; /* else Smell[...] = smellnow */ ant[AntNow].SmellAmount[SMELL_TYPE_FOOD] -= smelltodrop; if (ant[AntNow].SmellAmount[SMELL_TYPE_FOOD] < 0) ant[AntNow].SmellAmount[SMELL_TYPE_FOOD] = 0; } /* of have smell to drop */ } /* of have food */ else /* no food, looking for food */ { if (ant[AntNow].SmellAmount[SMELL_TYPE_HOME]) { smellnow = Smell[SMELL_TYPE_HOME][antx][anty]; smelltodrop = ant[AntNow].SmellAmount[SMELL_TYPE_HOME] * SMELL_DROP_RATE; if (smelltodrop > smellnow) Smell[SMELL_TYPE_HOME][antx][anty] = smelltodrop; /* else Smell[...] = smellnow */ ant[AntNow].SmellAmount[SMELL_TYPE_HOME] -= smelltodrop; if (ant[AntNow].SmellAmount[SMELL_TYPE_HOME] < 0) ant[AntNow].SmellAmount[SMELL_TYPE_HOME] = 0; } /* of have smell to drop */ } } /* of time to go */ /* else not go */ } /* of for AntNow */ textcolor(FOOD_HOME_COLOR); gotoxy(home.xxx, home.yyy); putch(HOME_CHAR); gotoxy(food.xxx, food.yyy); if (food.amount > 0) putch(FOOD_CHAR); else putch(FOOD_CHAR2); textcolor(7); gotoxy(1, MAXY + 1); printf("Food %d, Home %d ", food.amount, home.amount); } void AntOneStep(void) { int ddir, tttx, ttty; int i; ddir = ant[AntNow].dir; tttx = ant[AntNow].xxx; ttty = ant[AntNow].yyy; ddir = AntNextDir(tttx, ttty, ddir); switch (ddir) { case UP: ttty--; break; case DOWN: ttty++; break; case LEFT: tttx--; break; case RIGHT: tttx++; break; default: break; } /* of switch dir */ ant[AntNow].dir = ddir; ant[AntNow].xxx = tttx; ant[AntNow].yyy = ttty; if (ant[AntNow].food) /* this ant carry with food, search for home */ { if (tttx == home.xxx && ttty == home.yyy) { home.amount++; AntInitial(); } if (tttx == food.xxx && ttty == food.yyy) ant[AntNow].SmellAmount[SMELL_TYPE_FOOD] = MAX_SMELL; } /* of search for home */ else /* this ant is empty, search for food */ { if (tttx == food.xxx && ttty == food.yyy) { if (food.amount > 0) { ant[AntNow].food = 1; food.amount--; ant[AntNow].SmellAmount[SMELL_TYPE_FOOD] = MAX_SMELL; ant[AntNow].SmellAmount[SMELL_TYPE_HOME] = 0; ant[AntNow].dir = TurnBack(ant[AntNow].dir); for (i = 0; i < TRACE_REMEMBER; i++) { ant[AntNow].tracex[i] = 0; ant[AntNow].tracey[i] = 0; } ant[AntNow].TracePtr = 0; CanFindFood = 1; } /* of still have food */ } if (tttx == home.xxx && ttty == home.yyy) ant[AntNow].SmellAmount[SMELL_TYPE_HOME] = MAX_SMELL; } /* of search for food */ } void DealKey(char key) { int i; switch (key) { case 'p': gettime(&endtime); DispPlayTime(); getch(); gotoxy(1, MAXY + 1); for (i = 1; i <= MAXX - 1; i++) putch(SPACE); break; case 't': if (SmellDispFlag) { SmellDispFlag = 0; ClearSmellDisp(); } else SmellDispFlag = 1; break; case '1': DispSmell(SMELL_TYPE_FOOD); getch(); ClearSmellDisp(); break; case '2': DispSmell(SMELL_TYPE_HOME); getch(); ClearSmellDisp(); break; case '3': DispSmell(2); getch(); ClearSmellDisp(); break; case 's': SaveBlock(); break; case 'l': LoadBlock(); break; default: gotoxy(1, MAXY + 1); for (i = 1; i <= MAXX - 1; i++) putch(SPACE); } /* of switch */ } void ClearSmellDisp(void) { int k, i, j; for (k = 0; k <= 1; k++) /* SMELL TYPE FOOD and HOME */ for (i = 1; i <= MAXX; i++) for (j = 1; j <= MAXY; j++) { if (Smell[k][i][j]) { gotoxy(i, j); putch(SPACE); } } /* of one location */ } void DispSmell(int type) /* input: 0 -- Only display food smell -- Only display home smell -- Display both food and home smell */ { int k, i, j; int fromk, tok; int smelldisp; switch (type) { case 0: fromk = 0; tok = 0; break; case 1: fromk = 1; tok = 1; break; case 2: fromk = 0; tok = 1; break; default: fromk = 0; tok = 1; break; } SmellGoneTimer = 0; for (k = fromk; k <= tok; k++) /* SMELL TYPE FOOD and HOME */ for (i = 1; i <= MAXX; i++) for (j = 1; j <= MAXY; j++) { if (Smell[k][i][j]) { smelldisp = 1 + ((10 * Smell[k][i][j]) / (MAX_SMELL * SMELL_DROP_RATE)); if (smelldisp >= 30000 || smelldisp < 0) smelldisp = 30000; gotoxy(i, j); if (i != food.xxx || j != food.yyy) { if ((i == food.xxx && j == food.yyy) || (i == home.xxx && j == home.yyy)) /* don't over write Food and Home */; else { if (smelldisp > 9) putch('#'); else putch(smelldisp + '0'); } } } } /* of one location */ } int AntNextDir(int xxx, int yyy, int ddir) { int randnum; int testdir; int CanGoState; int cangof, cangol, cangor; int msf, msl, msr, maxms; int type; CanGoState = CanGo(xxx, yyy, ddir); if (CanGoState == 0 || CanGoState == 2 || CanGoState == 3 || CanGoState == 6) cangof = 1; else cangof = 0; if (CanGoState == 0 || CanGoState == 1 || CanGoState == 3 || CanGoState == 5) cangol = 1; else cangol = 0; if (CanGoState == 0 || CanGoState == 1 || CanGoState == 2 || CanGoState == 4) cangor = 1; else cangor = 0; if (ant[AntNow].food) type = SMELL_TYPE_HOME; else type = SMELL_TYPE_FOOD; msf = GetMaxSmell(type, xxx, yyy, ddir); msl = GetMaxSmell(type, xxx, yyy, TurnLeft(ddir)); msr = GetMaxSmell(type, xxx, yyy, TurnRight(ddir)); maxms = MaxLocation(msf, msl, msr); /* maxms - 1 - msf is MAX - msl is MAX - msr is MAX - all 3 number is 0 */ testdir = NULL; switch (maxms) { case 0: /* all is 0, keep testdir = NULL, random select dir */ break; case 1: if (cangof) testdir = ddir; else if (msl > msr) if (cangol) testdir = TurnLeft(ddir); else if (cangor) testdir = TurnRight(ddir); break; case 2: if (cangol) testdir = TurnLeft(ddir); else if (msf > msr) if (cangof) testdir = ddir; else if (cangor) testdir = TurnRight(ddir); break; case 3: if (cangor) testdir = TurnRight(ddir); else if (msf > msl) if (cangof) testdir = ddir; else if (cangol) testdir = TurnLeft(ddir); break; default: break; } /* of maxms */ randnum = random(1000); if (randnum < SMELL_DROP_RATE * 1000 || testdir == NULL) /* 1. if testdir = NULL, means can not find the max smell or the dir to max smell can not go then random select dir . if ant error, don't follow the smell, random select dir */ { randnum = random(100); switch (CanGoState) { case 0: if (randnum < 90) testdir = ddir; else if (randnum >= 90 && randnum < 95) testdir = TurnLeft(ddir); else testdir = TurnRight(ddir); break; case 1: if (randnum < 50) testdir = TurnLeft(ddir); else testdir = TurnRight(ddir); break; case 2: if (randnum < 90) testdir = ddir; else testdir = TurnRight(ddir); break; case 3: if (randnum < 90) testdir = ddir; else testdir = TurnLeft(ddir); break; case 4: testdir = TurnRight(ddir); break; case 5: testdir = TurnLeft(ddir); break; case 6: testdir = ddir; break; case 7: testdir = TurnBack(ddir); break; default: testdir = TurnBack(ddir); } /* of can go state */ } return (testdir); } int GetMaxSmell(int type, int xxx, int yyy, int ddir) { int i, j; int ms; /* MAX smell */ ms = 0; switch (ddir) { case UP: for (i = xxx - ANT_EYESHOT; i <= xxx + ANT_EYESHOT; i++) for (j = yyy - ANT_EYESHOT; j < yyy; j++) { if (!JudgeCanGo(i, j)) continue; if ((i == food.xxx && j == food.yyy && type == SMELL_TYPE_FOOD) || (i == home.xxx && j == home.yyy && type == SMELL_TYPE_HOME)) { ms = MAX_SMELL; break; } if (IsTrace(i, j)) continue; if (Smell[type][i][j] > ms) ms = Smell[type][i][j]; } break; case DOWN: for (i = xxx - ANT_EYESHOT; i <= xxx + ANT_EYESHOT; i++) for (j = yyy + 1; j <= yyy + ANT_EYESHOT; j++) { if (!JudgeCanGo(i, j)) continue; if ((i == food.xxx && j == food.yyy && type == SMELL_TYPE_FOOD) || (i == home.xxx && j == home.yyy && type == SMELL_TYPE_HOME)) { ms = MAX_SMELL; break; } if (IsTrace(i, j)) continue; if (Smell[type][i][j] > ms) ms = Smell[type][i][j]; } break; case LEFT: for (i = xxx - ANT_EYESHOT; i < xxx; i++) for (j = yyy - ANT_EYESHOT; j <= yyy + ANT_EYESHOT; j++) { if (!JudgeCanGo(i, j)) continue; if ((i == food.xxx && j == food.yyy && type == SMELL_TYPE_FOOD) || (i == home.xxx && j == home.yyy && type == SMELL_TYPE_HOME)) { ms = MAX_SMELL; break; } if (IsTrace(i, j)) continue; if (Smell[type][i][j] > ms) ms = Smell[type][i][j]; } break; case RIGHT: for (i = xxx + 1; i <= xxx + ANT_EYESHOT; i++) for (j = yyy - ANT_EYESHOT; j <= yyy + ANT_EYESHOT; j++) { if (!JudgeCanGo(i, j)) continue; if ((i == food.xxx && j == food.yyy && type == SMELL_TYPE_FOOD) || (i == home.xxx && j == home.yyy && type == SMELL_TYPE_HOME)) { ms = MAX_SMELL; break; } if (IsTrace(i, j)) continue; if (Smell[type][i][j] > ms) ms = Smell[type][i][j]; } break; default: break; } return (ms); } int IsTrace(int xxx, int yyy) { int i; for (i = 0; i < TRACE_REMEMBER; i++) if (ant[AntNow].tracex[i] == xxx && ant[AntNow].tracey[i] == yyy) return (1); return (0); } int MaxLocation(int num1, int num2, int num3) { int maxnum; if (num1 == 0 && num2 == 0 && num3 == 0) return (0); maxnum = num1; if (num2 > maxnum) maxnum = num2; if (num3 > maxnum) maxnum = num3; if (maxnum == num1) return (1); if (maxnum == num2) return (2); if (maxnum == num3) return (3); } int CanGo(int xxx, int yyy, int ddir) /* input: xxx,yyy - location of ant ddir - now dir output: 0 - forward and left and right can go - forward can not go - left can not go - right can not go - forward and left can not go - forward and right can not go - left and right can not go - forward and left and right all can not go */ { int tx, ty, tdir; int okf, okl, okr; /* forward can go ? */ tdir = ddir; tx = xxx; ty = yyy; switch (tdir) { case UP: ty--; break; case DOWN: ty++; break; case LEFT: tx--; break; case RIGHT: tx++; break; default: break; } /* of switch dir */ if (JudgeCanGo(tx, ty)) okf = 1; else okf = 0; /* turn left can go ? */ tdir = TurnLeft(ddir); tx = xxx; ty = yyy; switch (tdir) { case UP: ty--; break; case DOWN: ty++; break; case LEFT: tx--; break; case RIGHT: tx++; break; default: break; } /* of switch dir */ if (JudgeCanGo(tx, ty)) okl = 1; else okl = 0; /* turn right can go ? */ tdir = TurnRight(ddir); tx = xxx; ty = yyy; switch (tdir) { case UP: ty--; break; case DOWN: ty++; break; case LEFT: tx--; break; case RIGHT: tx++; break; default: break; } /* of switch dir */ if (JudgeCanGo(tx, ty)) okr = 1; else okr = 0; if (okf && okl && okr) return (0); if (!okf && okl && okr) return (1); if (okf && !okl && okr) return (2); if (okf && okl && !okr) return (3); if (!okf && !okl && okr) return (4); if (!okf && okl && !okr) return (5); if (okf && !okl && !okr) return (6); if (!okf && !okl && !okr) return (7); return (7); } int JudgeCanGo(int xxx, int yyy) /* input: location to judeg output: 0 -- can not go -- can go */ { int i, j; if (xxx <= 0 || xxx > MAXX) return (0); if (yyy <= 0 || yyy > MAXY) return (0); if (block[xxx][yyy]) return (0); return (1); } int TurnLeft(int ddir) { switch (ddir) { case UP: return (LEFT); case DOWN: return (RIGHT); case LEFT: return (DOWN); case RIGHT: return (UP); default: break; } /* of switch dir */ } int TurnRight(int ddir) { switch (ddir) { case UP: return (RIGHT); case DOWN: return (LEFT); case LEFT: return (UP); case RIGHT: return (DOWN); default: break; } /* of switch dir */ } int TurnBack(int ddir) { switch (ddir) { case UP: return (DOWN); case DOWN: return (UP); case LEFT: return (RIGHT); case RIGHT: return (LEFT); default: break; } /* of switch dir */ }
下面是一个简单的使用C语言实现蚁群算法的示例： ```c #include <stdio.h> #include <stdlib.h> #include <math.h> #define MAX_CITIES 10 // 最大城市数量 #define MAX_ANTS 100 // 最大蚂蚁数量 #define MAX_ITERATIONS 100 // 最大迭代次数 double distance[MAX_CITIES][MAX_CITIES]; // 城市之间的距离 double pheromone[MAX_CITIES][MAX_CITIES]; // 信息素浓度 int cities[MAX_CITIES]; // 城市数组 int bestTour[MAX_CITIES]; // 最佳路径 double bestLength; // 最佳路径长度 int numCities; // 城市数量 int numAnts; // 蚂蚁数量 void init() { // 初始化城市之间的距离和信息素浓度 // 这里可以根据实际问题进行初始化 // 初始化城市数组 for (int i = 0; i < numCities; i++) { cities[i] = i; } // 初始化最佳路径和长度 for (int i = 0; i < numCities; i++) { bestTour[i] = 0; } bestLength = INFINITY; } double euclideanDistance(int city1, int city2) { // 计算城市之间的欧氏距离 // 这里可以根据实际问题进行距离计算 // 返回城市之间的距离 } void constructSolutions() { // 构建蚂蚁的解 // 这里可以根据具体问题的要求进行构建 // 计算每只蚂蚁的路径长度 // 更新最佳路径和长度 } void updatePheromone() { // 更新信息素浓度 // 信息素的蒸发 // 这里可以根据具体问题设置蒸发系数 // 信息素的增加 // 这里可以根据具体问题设置增加系数 } void antColonyOptimization() { init(); for (int iteration = 0; iteration < MAX_ITERATIONS; iteration++) { constructSolutions(); updatePheromone(); // 更新最佳路径和长度 } // 输出最佳路径和长度 } int main() { // 设置城市数量和蚂蚁数量 numCities = 5; numAnts = 10; // 调用蚁群算法 antColonyOptimization(); return 0; }
上述代码只是一个简单的框架示例，你需要根据具体问题进行适当的修改和补充。其中，init()函数用于初始化城市之间的距离和信息素浓度，euclideanDistance()函数用于计算城市之间的欧氏距离，constructSolutions()函数用于构建蚂蚁的解，updatePheromone()函数用于更新信息素浓度，antColonyOptimization()函数用于执行蚁群算法的迭代过程。
需要注意的是，蚁群算法的具体实现涉及到问题的建模、启发函数的定义、信息素的更新策略等。以上示例只是一个基本的框架，具体问题中的细节和优化需要根据实际情况进行处理。
