基本蚁群算法.pptVIP

“ ” “ ” Ant Colony Algorithms 蚁群算法 目 录 什么是蚁群算法 （起源，原理，特征） 解决什么问题 （问题分类，问题描述，具体实现，仿真模拟） 为什么使用它 （时间/空间复杂度, 收敛性, 与回溯/贪心算法比较） 定义及起源 蚁群算法是一种模拟蚂蚁群体觅食行为的仿生优化算法 它由Marco Dorigo于1992年在他的博士论文“Ant system: optimization by a colony of cooperating agents”中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。 蚂蚁觅食规律 开始，所有蚂蚁从蚁穴出发，随机的选择前进方向寻找食物 当遇到食物的时候就返回蚁穴， 同时释放信息素（Pheromone）到环境中 蚂蚁在觅食过程中，会根据环境中的信息素浓度及时调整前进的方向 环境中的信息素会随时间挥发减少 抽象成算法模型 蚂蚁，抽象成为一个类的实体(线程)，它能完成寻路的功能，也即求解 自然环境即问题空间，三维的空间抽象成为二维的平面，连续的空间抽象为离散的点，也就是抽象为图。 信息素浓度，抽象为图的各条边上的属性 蚁穴到食物的路径，抽象为问题的解 特征 该算法采用了正反馈并行自催化机制，具有较强的鲁棒性、优良的分布式计算机制、易于其他方法结合等特点 蚁群算法解决的问题 蚁群优化算法应用于许多组合优化问题 调度问题：车间作业调度、开发式车间调度等 车辆路径问题：限量车辆路径、分批配送车辆路径等 分配问题：二次分配、冗余分配等 设置问题：多背包问题、最大独立集等 其他：网络路由、数据挖掘、图像处理、武器目标分配等 TSP(旅行商)问题 设有n 个城市，旅行商要找遍访每个城市恰好一次的一条回路，并且路径总长度最短。 对称TSP问题：两城市往返的距离相同 应用蚁群算法模型求解TSP 所有蚂蚁从一个随机的城市出发，即把蚂蚁放到不同的城市上 蚂蚁根据城市之间的信息素浓度和距离，按概率选择下一个城市，同时记住走过的城市 走完一圈，计算路径总长度，更新环境中的信息素 状态转移概率公式 信息素更新公式 流程图 开始 初始化 循环次数t = t + 1 蚂蚁k = 1 按照概率公式选择下一个城市 记录走过城市 蚂蚁k = k + 1 走完所有城市? ? 蚂蚁存在? ? 按公式更新信息素 t = N ? 输出结果 结束 Y ? Y Y ? N N N 时间/空间复杂度 轮盘赌选择Roulette?Wheel?Selection 轮盘赌选择又称比例选择算子 每一条路径对应轮盘上的一块扇形区域， 被选择的概率与扇形区域大小成正比， 选择路径时，只需转动轮盘， 到轮盘停止时，指针指向的扇形， 就是被选中的路径。 轮盘赌选择代码 double randomRotation = RandomDouble();//随机转动轮盘，即随机产生一个0——1.0之间的浮点数 int SelectedPos = -1; //被选中的个体下标 for (int i = 0; i Path_Count; i++){ randomRotation -= PathsProbability[i]; //开始转动，即减去转过区域对应的概率 if (randomRotation 0) { SelectedPos = i; break; } } return SelectedPos; “ ” “ ”