蚁群算法(Ant Colony Optimization, ACO)

news/2024/11/24 18:42:05/

简介

蚁群算法(Ant Colony Optimization, ACO)是一种基于自然启发的优化算法,由意大利学者马可·多里戈(Marco Dorigo)在1992年首次提出。它受自然界中蚂蚁觅食行为的启发,用于解决离散优化问题。

在自然界中,蚂蚁通过释放和追踪一种化学物质(即信息素)找到最短路径。蚁群算法通过模拟这种信息素的机制,在优化问题中迭代寻找近似最优解。

代码说明

距离矩阵:distance_matrix 是问题的输入,表示城市之间的距离。
信息素更新:信息素会随时间蒸发,并根据路径长度进行强化。
路径构建:每只蚂蚁根据概率选择下一步的城市,概率由信息素和启发式因子共同决定。
运行结果:输出最佳路径和对应路径长度。
在这里插入图片描述

代码

python">import numpy as npclass AntColony:def __init__(self, distance_matrix, n_ants, n_iterations, alpha=1, beta=2, evaporation_rate=0.5, Q=100):self.distance_matrix = distance_matrixself.n_ants = n_antsself.n_iterations = n_iterationsself.alpha = alpha  # 控制信息素重要程度self.beta = beta  # 控制启发式因子的权重self.evaporation_rate = evaporation_rateself.Q = Q  # 信息素强度常数self.num_cities = distance_matrix.shape[0]self.pheromone_matrix = np.ones((self.num_cities, self.num_cities))  # 初始信息素矩阵def _initialize_ants(self):return [np.random.permutation(self.num_cities) for _ in range(self.n_ants)]def _calculate_path_length(self, path):return sum(self.distance_matrix[path[i], path[(i + 1) % len(path)]] for i in range(len(path)))def _update_pheromones(self, all_paths, all_lengths):self.pheromone_matrix *= (1 - self.evaporation_rate)  # 信息素蒸发for path, length in zip(all_paths, all_lengths):for i in range(len(path)):start, end = path[i], path[(i + 1) % len(path)]self.pheromone_matrix[start, end] += self.Q / length  # 信息素更新def _choose_next_city(self, current_city, visited):probabilities = []for city in range(self.num_cities):if city not in visited:pheromone = self.pheromone_matrix[current_city, city] ** self.alphavisibility = (1 / self.distance_matrix[current_city, city]) ** self.betaprobabilities.append(pheromone * visibility)else:probabilities.append(0)probabilities = probabilities / np.sum(probabilities)return np.random.choice(range(self.num_cities), p=probabilities)def _construct_solution(self, ant):path = [ant]visited = set(path)for _ in range(self.num_cities - 1):next_city = self._choose_next_city(path[-1], visited)path.append(next_city)visited.add(next_city)return pathdef run(self):best_path = Nonebest_length = float('inf')for iteration in range(self.n_iterations):all_paths = []all_lengths = []for ant in range(self.n_ants):start_city = np.random.randint(self.num_cities)path = self._construct_solution(start_city)length = self._calculate_path_length(path)all_paths.append(path)all_lengths.append(length)if length < best_length:best_path = pathbest_length = lengthself._update_pheromones(all_paths, all_lengths)print(f"Iteration {iteration + 1}: Best length = {best_length}")return best_path, best_length# 示例距离矩阵
distance_matrix = np.array([[0, 2, 2, 5, 7],[2, 0, 4, 8, 2],[2, 4, 0, 1, 3],[5, 8, 1, 0, 2],[7, 2, 3, 2, 0]
])# 创建蚁群算法实例
ant_colony = AntColony(distance_matrix, n_ants=10, n_iterations=100, alpha=1, beta=2, evaporation_rate=0.5, Q=100)# 运行算法
best_path, best_length = ant_colony.run()print("Best path:", best_path)
print("Best length:", best_length)

http://www.ppmy.cn/news/1549604.html

相关文章

jquery还有其应用场景,智慧慢慢地被边缘化,但不会消亡

一、jQuery 的辉煌过往 jQuery 的诞生与崛起 在前端开发的漫长历史中&#xff0c;2006 年诞生的 jQuery 犹如一颗耀眼的新星划破天际。它由 John Resig 创造&#xff0c;一出现便以其独特的魅力迅速吸引了广大开发者的目光。在那个前端技术发展相对缓慢的时期&#xff0c;jQue…

ESP32移植Openharmony外设篇(6)光敏电阻ADC读取

光照传感器 模块简介 产品描述 光敏电阻&#xff08;photoresistor orlight-dependent resistor&#xff0c;后者缩写为LDR&#xff09;是一种基于内光电效应的半导体元件&#xff0c;它的阻值依赖于入射光强的变化 。入射光强增加&#xff0c;光敏电阻的阻值减小&#xff0…

apr共享内存

下载&#xff1a; Download - The Apache Portable Runtime Project 编译&#xff1a; 使用cmake-gui生成库&#xff1a; apr-1.lib aprapp-1.lib libapr-1.lib libaprapp-1.lib libapr-1.dll 在Developer PowerShell for VS 2019中&#xff1a; 执行nmake -f Makefile.win来…

什么是“数学活动”?

数学活动嘛&#xff0c;不就是关于数学的活动&#xff0c;还有什么可说的&#xff1f;非也&#xff0c;且看下面定义。 一、不同人的定义&#xff1a; ① “数学活动”是指在数学教学过程中&#xff0c;以学生学习兴趣和内在需要为基础&#xff0c;以主动探索、变革、改造对象…

win10局域网加密共享设置

1、创建共享账户 我的电脑右键选择管理 选择本地用户和组 -> 用户 双击用户 在空白区域右键,新建用户 然后创建用户 点击创建后 2、设置网络 右下角网络右键

C++结构型设计模式的作用和特征

在C面向对象软件设计中&#xff0c;结构型模式&#xff08;Structural Patterns&#xff09;主要关注对象和类之间的组合&#xff0c;以形成更大的结构。这些模式帮助我们管理和组织对象之间的关系&#xff0c;使得系统更加灵活、可扩展和易于维护。以下是几种常见的结构型模式…

解决mfc100u.dll缺失问题,轻松恢复系统稳定

mfc100u.dll 是一个动态链接库&#xff08;DLL&#xff09;文件&#xff0c;属于 Microsoft Foundation Classes (MFC) 库的一部分。MFC 是微软公司开发的一套用于快速开发 Windows 应用程序的 C 类库。mfc100u.dll 文件包含了 MFC 库中一些常用的函数和类的定义&#xff0c;这…

【安卓脚本】Android工程中文硬编码抽取

【安卓脚本】Android工程中文硬编码抽取 Android 原生工程 中文硬编码抽取功能支持流程示意项目地址 Android 原生工程 中文硬编码抽取 安卓在进行国际化多语言功能时经常会遇到一个头疼的问题&#xff0c;就是在以往的项目中往往存在大量的中文硬编码&#xff0c;这块人工处理…