智能调度 与 蚁群算法

我在前面的一篇文章《浅谈资源管理技术的未来发展之路》之中谈到,资源管理还需要完善三个方面的能力分别是:

1、完善资源使用收集反馈机制,资源分配出去之后,使用率怎么样?效果怎么样?应该有一个收集反馈机制。

2、资源分配策略智能学习能力,结合收集反馈的信息,可以动态调整资源分配调度策略,具有自主学习决策的能力。

3、异构集群的管理能力,当前资源管理平台,主要聚焦在同构平台,异构平台在工业界是一个非常现实的问题,老机器还要发挥余热,新机器要充分挖掘性能潜力,就同时存在新老并存的场面。资源管理框架应该要能抽象异构平台,进行统一管理和分配,合理调度任务的运行。

今天我们说下第2点,调度智能化,调度根据收集到的反馈信息动态调整资源,做到智能需要一定的算法支撑,今天讲讲和调度很契合的蚁群算法。

蚁群算法蚁群算法(ant colony optimization, ACO),又称蚂蚁算法,是一种用来寻找最优解决方案的机率型技术。它由Marco Dorigo于1992年在他的博士论文中引入,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。

蚂蚁在路径上前进时会根据前边走过的蚂蚁所留下的分泌物选择其要走的路径。其选择一条路径的概率与该路径上分泌物的强度成正比。因此,由大量蚂蚁组成的群体的集体行为实际上构成一种学习信息的正反馈现象:某一条路径走过的蚂蚁越多,后面的蚂蚁选择该路径的可能性就越大。蚂蚁的个体间通过这种信息的交流寻求通向食物的最短路径。

蚁群算法就是根据这一特点,通过模仿蚂蚁的行为,从而实现寻优。这种算法有别于传统编程模式,其优势在于,避免了冗长的编程和筹划,程序本身是基于一定规则的随机运行来寻找最佳配置。也就是说,当程序最开始找到目标的时候,路径几乎不可能是最优的,甚至可能是包含了无数错误的选择而极度冗长的。但是,程序可以通过蚂蚁寻找食物的时候的信息素原理,不断地去修正原来的路线,使整个路线越来越短,也就是说,程序执行的时间越长,所获得的路径就越可能接近最优路径。这看起来很类似与我们所见的由无数例子进行归纳概括形成最佳路径的过程。实际上好似是程序的一个自我学习的过程。

蚁群算法的特点:

1)蚁群算法是一种自组织的算法。在系统论中,自组织和它组织是组织的两个基本分类,其区别在于组织力或组织指令是来自于系统的内部还是来自于系统的外部,来自于系统内部的是自组织,来自于系统外部的是他组织。如果系统在获得空间的、时间的或者功能结构的过程中,没有外界的特定干预,我们便说系统是自组织的。在抽象意义上讲,自组织就是在没有外界作用下使得系统熵减小的过程(即是系统从无序到有序的变化过程)。蚁群算法充分体现了这个过程,以蚂蚁群体优化为例子说明。当算法开始的初期,单个的人工蚂蚁无序的寻找解,算法经过一段时间的演化,人工蚂蚁间通过信息激素的作用,自发的越来越趋向于寻找到接近最优解的一些解,这就是一个无序到有序的过程。

2)蚁群算法是一种本质上并行的算法。每只蚂蚁搜索的过程彼此独立,仅通过信息激素进行通信。所以蚁群算法则可以看作是一个分布式的多agent系统,它在问题空间的多点同时开始进行独立的解搜索,不仅增加了算法的可靠性,也使得算法具有较强的全局搜索能力。

3)蚁群算法是一种正反馈的算法。从真实蚂蚁的觅食过程中我们不难看出,蚂蚁能够最终找到最短路径,直接依赖于最短路径上信息激素的堆积,而信息激素的堆积却是一个正反馈的过程。对蚁群算法来说,初始时刻在环境中存在完全相同的信息激素,给予系统一个微小扰动,使得各个边上的轨迹浓度不相同,蚂蚁构造的解就存在了优劣,算法采用的反馈方式是在较优的解经过的路径留下更多的信息激素,而更多的信息激素又吸引了更多的蚂蚁,这个正反馈的过程使得初始的不同得到不断的扩大,同时又引导整个系统向最优解的方向进化。因此,正反馈是蚂蚁算法的重要特征,它使得算法演化过程得以进行。

4)蚁群算法具有较强的鲁棒性。相对于其它算法,蚁群算法对初始路线要求不高,即蚁群算法的求解结果不依赖子初始路线的选择,而且在搜索过程中不需要进行人工的调整。其次,蚁群算法的参数数目少,设置简单,易于蚁群算法应用到其它组合优化问题的求解。

学术界对蚁群算法和调度的结合研究也比较多,大家可以到搜索引擎中搜索“蚁群算法 调度”可以搜索出很多相关的研究文章。

通过蚁群算法,可以做到以下几点:

1、 可以自动找出最佳调度路径,决定任务调度顺序。

2、 调度参数学习,比如调优系统资源对任务的分配,系统最大并发数学习。

3、 子系统任务自动分配,等等。

对于智能调度这个课题,大家还想到什么算法比较契合吗?大家有更好的想法,可以在下方评论。

原文发布于微信公众号 - 大数据和云计算技术(jiezhu2007)

原文发表时间:2014-09-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏about云

大数据术语入门整理

问题导读 我们在学习的过程中经常听到一些术语,那么这些都是什么含义? 1.什么是大数据? 2.什么是数据分析? 3.什么是数据挖掘? 4.什么是数据可视化? 这...

3397
来自专栏新智元

【AI大红包】Facebook发布张量理解库,几分钟自动生成ML代码

新智元报道 来源:research.fb.com 编译:文强 【新智元导读】Facebook今天宣布发布Tensor Comprehensions,能够...

33515
来自专栏华章科技

在机器学习方面使用 R + Hadoop 方案真的有那么好?

因为他们在不懂R和Hadoop的特征应用场景的情况下,恰好抓到了一根免费,开源的稻草。

843
来自专栏量化投资与机器学习

【Python量化投资】基于技术分析研究股票市场

一 金融专业人士以及对金融感兴趣的业余人士感兴趣的一类就是历史价格进行的技术分析。维基百科中定义如下,金融学中,技术分析是通过对过去市场数据(主要是价格和成交量...

2169
来自专栏机器之心

业界 | 深度学习芯片公司Graphcore初探:颠覆GPU、FPGA和CPU的新一代处理器IPU

选自Nextplatform 作者:Nicole Hemsoth 机器之心编译 参与:朱朝阳、侯韵楚、李亚洲、黄小天 ? 作为思维锻炼,让我们将神经网络视为大量...

2414
来自专栏PPV课数据科学社区

【工具】为什么有些公司在机器学习业务方面倾向使用 R + Hadoop 方案?

引言:众所周知,R在解决统计学问题方面无与伦比。但是R在数据量达到2G以上速度就很慢了,于是就催生出了与Hadoop相结合跑分布式算法这种解决方案,但是,pyt...

2657
来自专栏PPV课数据科学社区

R语言和 Python —— 一个错误的分裂

最近有一些文章提出与年龄相关的问题:“崭露头角的年轻数据科学家们是学习R语言还是Python更好?” 答案似乎都是“视情况而定”,在现实中没有必要在R和Pyt...

34711
来自专栏机器学习养成记

关联分析(1):概念及应用

关联分析应用在项不多的情况下,从整体数据中挖掘潜在关联。具体应用场景可分为如下几个:

942
来自专栏互联网数据官iCDO

大数据时代,用户的隐私如何守护

本文转载自雷锋网。 雷锋网(公众号:雷锋网)按:本文介绍了学术界和工业界对于用户隐私保护的努力成果,其中主要讲到了k-anonymity(k-匿名化),l-di...

3757
来自专栏PPV课数据科学社区

【学习】大数据相关术语500例解释及中英文对照①

本文由36大数据编辑“陌上花”收集整理,转载必须标明来源36大数据和作者。 一、大数据 英文:big data,mega data 大数据,或称巨量资料,指的是...

3638

扫描关注云+社区