如果自己想建设网站该怎么做,四川住房和城乡建设局网站,网页定制哪家不错,北京网站建设电扬科技蚁群算法基本思想蚁群算法的基本原理来源于自然界中蚂蚁觅食的最短路径问题。根据昆虫学家的观察#xff0c;发现自然界的蚂蚁虽然视觉不发达#xff0c;但它可以在没有任何提示的情况下找到从食物源到巢穴的最短路径#xff0c;并且能在环境发生变化(如原有路径上有了障碍物…蚁群算法基本思想蚁群算法的基本原理来源于自然界中蚂蚁觅食的最短路径问题。根据昆虫学家的观察发现自然界的蚂蚁虽然视觉不发达但它可以在没有任何提示的情况下找到从食物源到巢穴的最短路径并且能在环境发生变化(如原有路径上有了障碍物)后自适应地搜索新的最佳路径。蚂蚁是如何做到这一点的呢原来蚂蚁在寻找食物源时能在其走过的路径上释放一种蚂蚁特有的分泌物一信息激素一也可称之为信息素使得一定范围内的其他蚂蚁能够察觉到并由此影响它们以后的行为。当一些路径上通过的蚂蚁越来越多时其留下的信息素也越来越多以致信息素强度增大(当然随时间的推移会逐渐减弱)所以蚂蚁选择该路径的概率也越高从而更增加了该路径的信息素强度这种选择过程被称之为蚂蚁的自催化行为。由于其原理是一种正反馈机制.因此也可将蚂蚁王国理解为所谓的增强型学习系统。在自然界中蚁群的这种寻找路径的过程表现为一种正反馈过程“蚁群算法”就是模仿生物学蚂蚁群觅食寻找最优路径原理衍生出来的。蚁群算法数学模型应该说前面介绍的蚁群算法只是一种算法思想要是想真正应用该算法还需要针对一个特定问题 建立相应的数学模型。现仍以经典的TSP问题为例来进一步阐述如何基于蚁群算法来求解实际问题。对于TSP问题为不失一般性设整个蚂蚁群体中蚂蚁的数量为m城市的数量为n城市i与城市j之间的距离为 (ij12…n)t时刻城市i与城市j连接路径上的信息素浓度为(t)。初始时刻蚂蚁被放置在不同的城市里且各城市间连接路径上的信息素浓度相同不妨设(0)(0)。然后蚂蚁将按一定概率选择线路不妨设为t时刻蚂蚁k从城市i转移到城市j的概率。我们知道,“蚂蚁TSP”策略会受到两方面的左右首先是访问某城市的期望另外便是其他蚂蚁释放的信息素浓度所以定义:其中 为启发函数表示蚂蚁从城市i转移到城市j的期望程度:(k1 2 … m)为蚂蚁k待访问城市集合开始时中有n一1个元素即包括除了蚂蚁k出发城市的其他多有城市 随着时间的推移中的元素越来越少直至为空a为信息素重要程度因子简称信息度因子。其值越大表示信息影响强度越大为启发函数重要程度因子简称启发函数因子其值越大表明启发函数影响越大。在蚂蚁遍历城市的过程中与实际情况相似的是在蚂蚁释放信息素的同时各个城市间连接路径上的信息素的强度也在通过挥发等方式逐渐消失。为了描述这一特征不妨令p(0其中为第k只蚂蚁在城市i与城市j连接路径上释放信息素而增加的信息素浓度为所有蚂蚁在城市i与城市j连接路径上释放信息素而增加的信息素浓度。一般的值可由ant cycle system模型进行计算其中Q为信息素常数表示蚂蚁循环一次所释放的信息素总量为第k只蚂蚁经过路径的总长度。蚁群算法流程用蚁群算法求解TSP问题的算法流程如下图所示具体每步的含义如下步骤1对相关参数进行初始化包括蚁初始化群规模、信息素因子、启发函数因子、信息素、挥发因子、信息素常数、最大迭代次数等以及将数据读人程序并对数据进行基本的处理如将城市的坐标位置转为城市间的矩阵。步骤2随机将蚂蚁放于不同的出发点对每个蚂蚁计算其下一个访问城市直至所更新信息素表有蚂蚁访问完所有城市。步骤3计算各个蚂蚁经过的路径长度记录当前迭代次数中的最优解同时对各个城市连接路径上的信息素浓度进行更新。步骤4判断是否达到最大迭代次数若否则返回步骤2否则终止程序。步骤5输出程序结果并根据需要输出程序寻优过程中的相关指标如运行时间、收敛迭代次数等。python简单实现import numpy as npimport matplotlib.pyplot as plt# 建立“蚂蚁”类class Ant(object):def __init__(self, path):self.path path # 蚂蚁当前迭代整体路径self.length self.calc_length(path) # 蚂蚁当前迭代整体路径长度def calc_length(self, path_): # path[A, B, C, D, A]注意路径闭环length_ 0for i in range(len(path_)-1):delta (path_[i].x - path_[i1].x, path_[i].y - path_[i1].y)length_ np.linalg.norm(delta)return length_staticmethoddef calc_len(A, B): # 静态方法计算城市A与城市B之间的距离return np.linalg.norm((A.x - B.x, A.y - B.y))# 建立“城市”类class City(object):def __init__(self, x, y):self.x xself.y y# 建立“路径”类class Path(object):def __init__(self, A): # A为起始城市self.path [A, A]def add_path(self, B): # 追加路径信息方便计算整体路径长度self.path.append(B)self.path[-1], self.path[-2] self.path[-2], self.path[-1]# 构建“蚁群算法”的主体class ACO(object):def __init__(self, ant_num50, maxIter300, alpha1, beta5, rho0.1, Q1):self.ants_num ant_num # 蚂蚁个数self.maxIter maxIter # 蚁群最大迭代次数self.alpha alpha # 信息启发式因子self.beta beta # 期望启发式因子self.rho rho # 信息素挥发速度self.Q Q # 信息素强度###########################self.deal_data(coordinates.dat) # 提取所有城市的坐标信息###########################self.path_seed np.zeros(self.ants_num).astype(int) # 记录一次迭代过程中每个蚂蚁的初始城市下标self.ants_info np.zeros((self.maxIter, self.ants_num)) # 记录每次迭代后所有蚂蚁的路径长度信息self.best_path np.zeros(self.maxIter) # 记录每次迭代后整个蚁群的“历史”最短路径长度###########################self.solve() # 完成算法的迭代更新self.display() # 数据可视化展示def deal_data(self, filename):with open(filename, rt) as f:temp_list list(line.split() for line in f) # 临时存储提取出来的坐标信息self.cities_num len(temp_list) # 1. 获取城市个数self.cities list(City(float(item[0]), float(item[1])) for item in temp_list) # 2. 构建城市列表self.city_dist_mat np.zeros((self.cities_num, self.cities_num)) # 3. 构建城市距离矩阵for i in range(self.cities_num):A self.cities[i]for j in range(i, self.cities_num):B self.cities[j]self.city_dist_mat[i][j] self.city_dist_mat[j][i] Ant.calc_len(A, B)self.phero_mat np.ones((self.cities_num, self.cities_num)) # 4. 初始化信息素矩阵# self.phero_upper_bound self.phero_mat.max() * 1.2 ###信息素浓度上限self.eta_mat 1/(self.city_dist_mat np.diag([np.inf]*self.cities_num)) # 5. 初始化启发函数矩阵def solve(self):iterNum 0 # 当前迭代次数while iterNum self.maxIter:self.random_seed() # 使整个蚁群产生随机的起始点delta_phero_mat np.zeros((self.cities_num, self.cities_num)) # 初始化每次迭代后信息素矩阵的增量##########################################################################for i in range(self.ants_num):city_index1 self.path_seed[i] # 每只蚂蚁访问的第一个城市下标ant_path Path(self.cities[city_index1]) # 记录每只蚂蚁访问过的城市tabu [city_index1] # 记录每只蚂蚁访问过的城市下标禁忌城市下标列表non_tabu list(set(range(self.cities_num)) - set(tabu))for j in range(self.cities_num-1): # 对余下的城市进行访问up_proba np.zeros(self.cities_num-len(tabu)) # 初始化状态迁移概率的分子for k in range(self.cities_num-len(tabu)):up_proba[k] np.power(self.phero_mat[city_index1][non_tabu[k]], self.alpha) * \np.power(self.eta_mat[city_index1][non_tabu[k]], self.beta)proba up_proba/sum(up_proba) # 每条可能子路径上的状态迁移概率while True: # 提取出下一个城市的下标random_num np.random.rand()index_need np.where(proba random_num)[0]if len(index_need) 0:city_index2 non_tabu[index_need[0]]breakant_path.add_path(self.cities[city_index2])tabu.append(city_index2)non_tabu list(set(range(self.cities_num)) - set(tabu))city_index1 city_index2self.ants_info[iterNum][i] Ant(ant_path.path).lengthif iterNum 0 and i 0: # 完成对最佳路径城市的记录self.best_cities ant_path.pathelse:if self.ants_info[iterNum][i] Ant(self.best_cities).length: self.best_cities ant_path.pathtabu.append(tabu[0]) # 每次迭代完成后使禁忌城市下标列表形成完整闭环for l in range(self.cities_num):delta_phero_mat[tabu[l]][tabu[l1]] self.Q/self.ants_info[iterNum][i]self.best_path[iterNum] Ant(self.best_cities).lengthself.update_phero_mat(delta_phero_mat) # 更新信息素矩阵iterNum 1def update_phero_mat(self, delta):self.phero_mat (1 - self.rho) * self.phero_mat delta# self.phero_mat np.where(self.phero_mat self.phero_upper_bound, self.phero_upper_bound, self.phero_mat) # 判断是否超过浓度上限def random_seed(self): # 产生随机的起始点下表尽量保证所有蚂蚁的起始点不同if self.ants_num self.cities_num: # 蚂蚁数 城市数self.path_seed[:] np.random.permutation(range(self.cities_num))[:self.ants_num]else: # 蚂蚁数 城市数self.path_seed[:self.cities_num] np.random.permutation(range(self.cities_num))temp_index self.cities_numwhile temp_index self.cities_num self.ants_num:self.path_seed[temp_index:temp_index self.cities_num] np.random.permutation(range(self.cities_num))temp_index self.cities_numtemp_left self.ants_num % self.cities_numif temp_left ! 0:self.path_seed[temp_index:] np.random.permutation(range(self.cities_num))[:temp_left]def display(self): # 数据可视化展示plt.figure(figsize(6, 10))plt.subplot(211)plt.plot(self.ants_info, g.)plt.plot(self.best_path, r-, labelhistory_best)plt.xlabel(Iteration)plt.ylabel(length)plt.legend()plt.subplot(212)plt.plot(list(city.x for city in self.best_cities), list(city.y for city in self.best_cities), g-)plt.plot(list(city.x for city in self.best_cities), list(city.y for city in self.best_cities), r.)plt.xlabel(x)plt.ylabel(y)plt.savefig(ACO.png, dpi500)plt.show()plt.close()ACO()输出参考文献[2]《matlab在数学建模中的应用》
