智能调度 与 蚁群算法

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

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

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

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

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

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

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

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

蚁群算法的特点:

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

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

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

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

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

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

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

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

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

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

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

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏奇点大数据

OpenAI发布强化学习环境Gym Retro:支持千种游戏

项目链接:https://github.com/openai/retro/tree/develop

16630
来自专栏AI研习社

想快速部署机器学习项目?来看看几大主流机器学习服务平台对比吧

日前,kdnuggets 上的一篇文章对比了三大公司(谷歌、微软和亚马逊)提供的机器学习服务平台,对于想要启动机器学习项目的公司或是数据科学新手来说,提供了非常...

573170
来自专栏目标检测和深度学习

资源 | OpenAI发布强化学习环境Gym Retro:支持千种游戏

项目链接:https://github.com/openai/retro/tree/develop

7220
来自专栏腾讯移动品质中心TMQ的专栏

腾讯TMQ在线沙龙回顾|测试建模

测试建模 活动时间:2017年4月27日 QQ群视频交流 活动介绍: TMQ在线沙龙第二十期分享 本次分享的主题是:测试建模 共有72位测试小伙伴报名参加活动,...

25870
来自专栏IT大咖说

Web与人工智能时代

摘要 “人工智能”一词最初是在1956年Dartmouth学会上提出的。从那以后,研究者们发展了众多理论和原理,人工智能的概念也随之扩展。人工智能(Artifi...

44360
来自专栏织云平台团队的专栏

智能运维机器人--AI运维的实践探索【二】

当越来越多的AI技术引入运维领域后,我们能憧憬,我们的征途,正驶向星辰大海吗?

1.5K60
来自专栏架构师之路

通俗易懂,互联网的常见推荐算法

没有复杂的公式,没有晦涩的技术词汇,从最简易的案例,了解互联网最常见的推荐算法,每篇1分钟,保证弄懂。 一、《从电影推荐开始,聊协同过滤》 什么是协同过滤 协同...

434130
来自专栏ATYUN订阅号

谷歌发布自己的前端机器学习库——deeplearn.js

目前看来,在人工智能时代,不管是手机、汽车,还是音箱等智能产品,没有用上的人都不好意思和别人打招呼;此外,谷歌和Facebook都分别在TensorFlow和C...

42540
来自专栏挖掘大数据

推荐系列02,每个职场中的你都有必要了解的推荐系统常识

接上一篇《推荐系列01:人工智能与推荐系统》,上一篇文章主要解决的什么是推荐系统以及为什么要有推荐系统的问题。这一篇我们关注的是,更细节的一些东西,把推荐系统的...

34800
来自专栏机器之心

业界 | 无缝整合PyTorch 0.4与Caffe2,PyTorch 1.0即将问世

20850

扫码关注云+社区

领取腾讯云代金券