智能调度 与 蚁群算法

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

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

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

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

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

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

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

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

蚁群算法的特点:

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

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

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

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

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

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

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

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

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

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

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

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏IT派

推荐:35个热门又实用的开源 AI 项目!

2017年企业界在AI技术上的开支将达到125亿美元,比2016年增长逾59.3%。这股强劲的增长势头可能会一直持续到2020年,到时收入有望达到460亿美元。...

3459
来自专栏玉树芝兰

如何用人工智能帮你找论文?

传统的关键词检索论文,浩如烟海的结果让你无所适从?试试人工智能检索引擎。根据你的研究兴趣和偏好,便捷而靠谱帮你找论文。

741
来自专栏机器学习算法与Python学习

干货 | 自然语言处理入门资料推荐

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第一 【Python】:排名第三 【算法】:排名第四 源 | AI深入浅出 最近几个月小编...

4435
来自专栏人工智能LeadAI

一个优雅的框架 | Pytorch 初体验

pytorch是啥呢?其实pytorch是一个python优先的深度学习框架,是一个和tensorflow,Caffe,MXnet一样,非常底层的框架,它的前身...

3819
来自专栏AI研习社

2017 深度学习框架发展大盘点——迎来 PyTorch,告别 Theano

深度学习是机器学习中一种基于对数据进行表征学习的方法,作为当下最热门的话题,谷歌、Facebook、微软等巨头纷纷围绕深度学习做了一系列研究,一直在支持开源深度...

2746
来自专栏AI研习社

我是这样从零开始用深度学习做狗脸识别 iOS App 的

我是一个初创公司的软件工程师。曾经有段时间在谷歌工作,做谷歌财经图表和Multiple inboxes,并主管谷歌地图的业务。最近,我开了一家叫Spring的购...

1252
来自专栏PaddlePaddle

从第一本书开始,如何成为深度学习工程师(上篇)

小编结合资料与工程师经验,梳理出一条深度学习工程师的成长路径及“练级大法”,希望可以帮到各位“炼丹师”稳步进阶,畅游深度学习海洋~

802
来自专栏AI研习社

TensorFlow 1.0 正式发布 你需要知道的都在这里

【AI研习社】关注AI前沿、开发技巧及技术教程等方面的内容。欢迎技术开发类文章、视频教程等内容投稿,邮件发送至:zhangxian@leiphone.com ?...

3269
来自专栏数据科学与人工智能

【陆勤践行】机器学习最佳入门学习资料汇总

这篇文章的确很难写,因为我希望它真正地对初学者有帮助。面前放着一张空白的纸,我坐下来问自己一个难题:面对一个对机器学习领域完全陌生的初学者,我该推荐哪些最适合的...

2226
来自专栏用户2442861的专栏

DL4J与Torch、Theano、Caffe、TensorFlow的比较

https://deeplearning4j.org/cn/compare-dl4j-torch7-pylearn

882

扫码关注云+社区