10分钟搞懂蚁群算法 |
您所在的位置：网站首页 › 蚂蚁云算是什么东西 › 10分钟搞懂蚁群算法 |
10分钟搞懂蚁群算法
|
蚂蚁几乎没有视力，但他们却能够在黑暗的世界中找到食物，而且能够找到一条从洞穴到食物的最短路径。它们是如何做到的呢？ 蚂蚁寻找食物的过程单只蚂蚁的行为及其简单，行为数量在10种以内，但成千上万只蚂蚁组成的蚁群却能拥有巨大的智慧，这离不开它们信息传递的方式——信息素。 蚂蚁在行走过程中会释放一种称为“信息素”的物质，用来标识自己的行走路径。在寻找食物的过程中，根据信息素的浓度选择行走的方向，并最终到达食物所在的地方。 信息素会随着时间的推移而逐渐挥发。 在一开始的时候，由于地面上没有信息素，因此蚂蚁们的行走路径是随机的。蚂蚁们在行走的过程中会不断释放信息素，标识自己的行走路径。随着时间的推移，有若干只蚂蚁找到了食物，此时便存在若干条从洞穴到食物的路径。由于蚂蚁的行为轨迹是随机分布的，因此在单位时间内，短路径上的蚂蚁数量比长路径上的蚂蚁数量要多，从而蚂蚁留下的信息素浓度也就越高。这为后面的蚂蚁们提供了强有力的方向指引，越来越多的蚂蚁聚集到最短的路径上去。 什么是蚁群算法？蚁群算法就是模拟蚂蚁寻找食物的过程，它能够求出从原点出发，经过若干个给定的需求点，最终返回原点的最短路径。这也就是著名的旅行商问题(Traveling Saleman Problem，TSP)。 本文使用蚁群算法来解决分布式环境下的负载均衡调度问题。 蚁群算法的应用——负载均衡调度集群模式是目前较为常用的一种部署结构，也就是当单机处理能力无法满足业务需求，那么就增加处理节点，并由一个负载均衡器负责请求的调度。然而对于一个庞大系统而言，情况往往比较复杂。集群中节点的处理能力往往各不相同，而且不同任务的处理复杂度也不尽相同。那么负载均衡器如何进行任务分配，使得集群性能达到最优？资源利用率达到最高呢？这是一个极具挑战又很有价值的问题。 本文我们就采用蚁群算法来解决这一问题。 数学建模在开始之前，我们首先需要将“负载均衡调度”这个问题进行数学建模，量化各项指标，并映射到蚁群算法中。 问题描述求一种最优的任务分配策略，能够将N个长度不等的任务按照某一种策略分配给M个处理能力不同的服务器节点，并且N个任务的完成时间最短。 在这个问题中，我们将所有任务的完成时间作为衡量分配策略优良的指标。每一种分配策略都是这个问题的一个可行解。那么具有最小完成时间的分配策略就是这个问题的最优解。  title参数定义代码语言：javascript复制var tasks = [];
var taskNum = 100;tasks：任务数组，数组的下标表示任务的编号，数组的值表示任务的长度。比如：tasks[0]=10表示第一个任务的任务长度是10.taskNum：任务的数量，也就是tasks数组的长度。这里为了提高代码的可读性才专门使用taskNum来表示任务数量。代码语言：javascript复制var nodes = [];
var nodeNum = 10;nodes：处理节点的数组。数组的下标表示处理节点的编号，数组值表示节点的处理速度。比如：nodes[0]=10表示第1个处理节点的处理速度为10.nodeNum：处理节点的数量，也就是nodes数组的长度。这里也是为了提高代码的可读性才专门使用nodeNum来表示节点的数量。代码语言：javascript复制var iteratorNum;
var antNum;iteratorNum：蚁群算法一共需要迭代的次数，每次迭代都有antNum只蚂蚁进行任务分配。antNum：每次迭代中蚂蚁的数量。每只蚂蚁都是一个任务调度者，每次迭代中的每一只蚂蚁都需要完成所有任务的分配，这也就是一个可行解。代码语言：javascript复制var timeMatrix = [];任务处理时间矩阵。
它是一个二维矩阵。比如：timeMatrix[i][j]就表示第i个任务分配给第j个节点所需的处理时间。这个矩阵是基于tasks数组和nodes数组计算而来的。比如task[i]表示第i个任务的任务长度，nodes[j]表示第j个节点的处理速度。所以，timeMatrix[i][j]=task[i]/nodes[j].代码语言：javascript复制var pheromoneMatrix = [];
var maxPheromoneMatrix = [];
var criticalPointMatrix = [];pheromoneMatrix：信息素矩阵
它是一个二维矩阵，用于记录任务i分配给节点j这条路径上的信息素浓度。比如：pheromoneMatrix[i][j]=0.5就表示任务i分配给节点j这条路径上的信息素浓度为0.5maxPheromoneMatrix：pheromoneMatrix矩阵的每一行中最大信息素的下标。
比如：maxPheromoneMatrix[0]=5表示pheromoneMatrix第0行的所有信息素中，最大信息素的下标是5.criticalPointMatrix：在一次迭代中，采用随机分配策略的蚂蚁的临界编号。
比如：如果将蚂蚁数量设为10，那么每次迭代中都有10只蚂蚁完成所有任务的分配工作。并且分配过程是按照蚂蚁编号从小到大的顺序进行的(蚂蚁从0开始编号)。如果criticalPointMatrix[0]=5，那么也就意味着，在分配第0个任务的时候，编号是0～5的蚂蚁根据信息素浓度进行任务分配(即：将任务分配给本行中信息素浓度最高的节点处理)，6～9号蚂蚁则采用随机分配的方式(即：将任务随机分配给任意一个节点处理)。为什么要这么做？
如果每只蚂蚁都将任务分配给信息素浓度最高的节点处理，那么就会出现停滞现象。也就是算法过早地收敛至一个局部最优解，无法发现全局最优解。
因此需要一部分蚂蚁遵循信息素最高的分配策略，还需要一部分蚂蚁遵循随机分配的策略，以发现新的局部最优解。代码语言：javascript复制var p = 0.5;
var q = 2;p：每完成一次迭代后，信息素衰减的比例。
我们知道，在真实的蚁群中，蚂蚁分泌的信息素会随着时间的推移而渐渐衰减。那么在算法中，我们使得信息素每完成一次迭代后进行衰减，但在一次迭代过程中，信息素浓度保持不变。q：蚂蚁每次经过一条路径，信息素增加的比例。
我们也知道，在真实的蚁群中，蚂蚁会在行进过程中分泌信息素。那么在算法中，我们使得算法每完成一次迭代后，就将蚂蚁经过的路径上增加信息素q，但在一次迭代过程中，信息素浓度不变。算法初始化代码语言：javascript复制// 初始化任务集合
tasks = initRandomArray(_taskNum, taskLengthRange);
// 初始化节点集合
nodes = initRandomArray(_nodeNum, nodeSpeendRange);在正式开始之前，我们需要初始化任务数组和节点数组。这里采用随机赋值的方式，我们给tasks随机创建100个任务，每个任务的长度是10～100之间的随机整数。再给nodes随机创建10个节点，每个节点的处理速度是10～100之间的随机整数。 OK，准备工作完成，下面来看蚁群算法的实现。 蚁群算法代码语言：javascript复制/** * 蚁群算法 */ function aca() { // 初始化任务执行时间矩阵 initTimeMatrix(tasks, nodes); // 初始化信息素矩阵 initPheromoneMatrix(taskNum, nodeNum); // 迭代搜索 acaSearch(iteratorNum, antNum); }正如你所看到的，蚁群算法并不复杂，总体而言就是这三部： 初始化任务执行时间矩阵初始化信息素矩阵迭代搜索当然，第一第二步都较为简单，相对复杂的代码在“迭代搜索”中。那么下面我们就分别来看一下这三个步骤的实现过程。 初始化任务执行时间矩阵代码语言：javascript复制/** * 初始化任务处理时间矩阵 * @param tasks 任务(长度)列表 * @param nodes 节点(处理速度)列表 */ function initTimeMatrix(tasks, nodes) { for (var i=0; i |
【本文地址】
今日新闻 |
推荐新闻 |