启发式规则

启发式规则（共4篇）

启发式规则 篇1

摘要：网页信息提取方法中的启发式规则,是识别网页标签信息、利用网页节点分析结果、针对网页不同内容、完成信息提取的重要手段。本研究在对现有启发式规则进行研究分析的基础上,提出了几种优化的启发式规则,实现对网页标题、发布时间、来源以及正文内容等元素信息的精准提取。本研究进一步提出了运用编辑距离算法实现正文内容提取准确率的判定,并提出阙值优化方法,克服了正文提取中噪声节点多、内容识别不完全的缺陷,大大提高了提取的准确度。

关键词：启发式规则,优化,网页元素,精准提取

0 引言

随着时代的发展,互联网在我们生活中扮演的角色越来越重要,而组成互联网的这一实体的关键成分,即网页也得到了越来越多的关注。如何从网页中准确且快捷的获取我们需要的内容已经成为研究者所关注的话题。众所周知,网页是由HTML组成的文本文件。由于HTML并不规范,每个网页的编排又有着很大的差别,所以传统的基于标记的提取方法无法精确定位网页元素信息,只能进行一部分文字的抽取和图片的去除,对于不同信息的识别有着很大的盲目性。

人工智能具有处理不确定性乃至不可知性和学习、解释和推理的能力。因此,本研究利用人工智能方法实现网页信息的提取。在对网页元素提取主要手段———启发式方法进行分析和研究的基础上,我们进一步对启发式规则进行了优化研究。我们提出了运用编辑距离算法计算相似度的方法,根据相似度判断信息抽取的准确率,从而大大提高信息提取的准确度。

2 网页元素提取方法

启发式规则应用的单位是标签,所以信息抽取需要先对网页进行分解,提取出标签。本研究采用构建DOM树来实现HTML的解析以及标签的提取。DOM树构造简单,易于遍历,结合启发式规则,方便于网页元素的提取与分析。

2.1 构建DOM树

DOM树是一种数据结构,HTML文档中的所有节点组成一棵文档树,树中的节点表示HTML文档中的元素、属性、文本等。树起始于文档节点,由此继续伸出枝条,直到处于树叶的所有文本节点为止。DOM树的节点构成示例如图1所示。

2.2 过滤噪声

由于网页中存在着许多干扰源,如广告、图片等,因此构建DOM树过程中有很多节点是没用的。在对现有的方法进行深入研究的基础上,结合本研究的实验,我们利用遍历DOM树、过滤噪声节点的方法,提取出有用的文本节点以进行下一步的分析。

3 启发式规则的提出

人们的不同习惯会造成网页在设计布局上大相径庭,然而,总体上有规律可循。启发式规则就是利用这些规律对DOM树进行分析、提取信息的有效方法。启发式规则的优劣是决定网页元素提取准确度的重要因素。

本研究在对现有的启发式规则进行充分研究和实验的基础上,针对网页不同要素、提出更加全面优化的启发式规则。本节对发布时间、标题、正文及来源等要素所对应的启发式规则逐一介绍。

3.1 发布时间规则

(1)如果文本节点中包含一些关键词,例如,“发布时间”、“时间”、“提问时间”等,则该节点包含发布时间信息的可能性增加。(2)如果文本节点中包含特定的日期格式,例如2001-07-12或者2011年7月7日,则该节点包含发布时间信息的可能性增加。

3.2 来源规则

(1)如果文本节点中包含一些关键词例如“来源”、“转自”、“提问者”等,或者文本节点为“××网”,则该节点包含来源节点信息的可能性增加。(2)如果文本节点的前一个或者后一个文本节点是发布时间节点,则该节点包含来源节点信息的可能性增加。(3)如果文本节点的前一个或者后一个文本节点是标题节点,则该节点包含来源节点信息的可能性增加。

3.3 正文规则

正文在整个网页中所占比重是最大的,能否准确地获取正文决定着对网页信息把握的准确率。因此,正文规则及其优化尤为重要。

(1)一般正文的长度不会太短,所以如果文本节点的长度大于一个值,那么该节点包含正文信息的可能性增加。(2)一般正文由多个段落组成,所以如果一个节点的标签为

,并且其有一定数量的兄弟节点也是

,则此节点的子文本节点包含正文信息的概率增加。(3)一般正文的上下可能会有一些间距,也就是换行符,所以如果在文本节点的兄弟节点标签中如果有一定数量的
,那么该节点包含正文信息的可能性增加。(4)一般正文都存在于发布时间的下方,那么所有位于发布时间后的文本节点包含正文信息的可能性增加。

3.4 标题规则

(1)标题通常来说不会太长,但可以很短。因此,我们选择两个合适的长度做上下限,如果长度在此范围内则满足条件、包含标题信息的可能性增加。(2)如果文章中有或者为的标签,说明有粗体字,则该节点可能为标题,并且其兄弟节点也可能是标题的一部分,那么该部分包含标题信息的可能性增加。(3)如果节点的标签为H1或H2或H3,那么该节点的子节点包含标题信息的可能性增加。(4)如果满足前三个条件,那么第一个出现的可能是标题的节点之前的所有的文本节点包含标题信息可能性增加。

4 元素提取及验证

4.1 设置权值矩阵

依据启发式规则、凭借文本节点可能性度量筛选节点,进而实现信息抽取。根据经验,我们设计了计算节点可能性的初始权值矩阵,如图2所示,同时,表1给出了对应权值矩阵相关参数的详细解释。

权值矩阵的行数是最大规则数,列数是待抽取的信息数量,矩阵列的权值和为1。通常,概率矩阵有两种生成方法:(1)根据经验设置。例如,一般情况下,当有“发布日期”字样时,这个节点就非常接近发布时间节点了。这样,看到“发布日期”比单纯的看到一个日期格式的数字得到的信息更多。因此,把前者的权值设置得大一些,表示更重视包含这种特征的节点。(2)根据正确率设置。假设算法已经构造完整,那么可以从0开始穷举每列的各个权值。实验中保证每列权值相加为1,精度为0.05或0.1比较合适。每实验一组得出一个正确率,然后通过比较正确率得到正确率最高的一组权值。

由于自学习更改权值的方法开销较大,所以本实验结合经验、采用第一种方法设置权值。

4.2 元素的抽取

本研究首先建立网页数据库,然后提取载入网页中信息并与数据库中的信息进行匹配,从而得到各个网页元素提取的准确率,最后统计得出总的准确率。

实验中存在的一个问题是抽取出来的信息不可能百分百和数据库中的信息相吻合,比如,从网页中抽取的发布日期是“发布时间:2011-07-02”,而数据库中的信息是“2011-07-02”。本质上,这样应该归结于提取成功,然而,我们凭什么来判断呢?针对这个问题,本实验提出了应用著名的编辑距离算法(Levenshtein Distance)来进行字符串相似度的比较。通过对相似度的计算,判断是否提取出相应的信息。

同时,本实验提出了对正文信息的抽取进行迭代筛选的方法。首先,设置阙值为0.2,提取所有正文权值大于0.2的节点;第二步,计算提取出的正文与待比较数据的相似度,存储到一个变量中;第三步,把初始值增加0.05,再次重复第二步;如果相似度呈增长趋势,那么就一直重复第三步和第二步;直到相似度出现下降,则终止迭代,取其前一次的阙值,即当前阙值减去0.05,则可提取出相似度最大的正文。

这种方法可以用来寻找不同阙值对正文相似度的影响,找到最大值。因为在不同的网页中页面排版格式是不一样的,无法找到一个通用的阙值,所以这种动态寻找最佳阙值的方法是十分有效的。

为了保证所抽取节点内容的完整性,本实验在获取单个节点内容的同时也获取了其子节点和兄弟节点内容,这样可以避免在有些网页上信息抽取不全的问题。

4.3 准确率验证与分析

本文对新闻型和论坛型两类网站、20个网页实施了信息相似度的测试,记录了相关项的综合相似度,进一步分析了实验结果,完成了实验准确度的判定。

从以上两表中可知标题的相似度最高,但并不能只从相似度来判断准确率。比如发布时间是“2012-2-18”,而提取出来的内容一般是“发布时间:2012-2-18”,虽然相似度只有64.29%,但其结果已经是提取成功了。而标题之所以相似度较大,主要是噪声节点比较少,因为标题通常是作为单独节点出现的。

新闻型网页总体上的准确率要远大于论坛型网页,主要是两方面的原因:(1)论坛型网页正文占所有回帖的比例不确定,比例越大,相似度越高。有的时候一楼中的文本很短,那么最后的相似度会非常小。(2)论坛型网页在来源及标题上并无特殊格式约束,只能通过对文本进行匹配来判断。比如在论坛中一个帖子有时会被编辑多次,这样在楼主的帖中就会显示“本帖最后由XXXX于XXXX-XX-XX编辑”,我们通过对文字的匹配来增加其权值。然而对于没有被编辑过的帖子则没有办法。

5 总结

启发式网页信息提取方法对新闻型网页提取的准确率已经相当高了,对于标题、发布时间和来源几乎做到了100%提取。由于正文由多个节点组成,所以会有一定量的噪声干扰,对准确率产生了一定程度的影响。由于采用了字符串匹配算法,我们能精准地得出相似度,这对于完善算法和研究网页排版是很有帮助的。

在实际操作过程中,我们发现针对不同类型的网站可以对规则进行适当的变化,权值矩阵也需要不断调整。并且,对于文本匹配类的规则,我们可以把它当做一个小型专家系统。比如发现节点中如果包含“发布时间”,那么其权值就应该比单纯包含“时间”要大。当然,这些需要在实践中积累经验,并对不同类型的网页应用不同的设置,使提取出来的信息达到最大的准确率。

参考文献

[1]胡金柱,周星,舒江波,熊春秀.基于启发式规则的网页主题信息精确定位方法[J].计算机应用研究.2010年02期.

[2]李铭岳,周军.基于改进HTML-Tree的中文网页特征向量提取方法[J].信息技术.2009年01期.

[3]王磊,蒋建中,郭军利.基于扩展DOM树的Web页面信息抽取[J].计算机应用与软件.2007年第24卷第6期.

[4]常红要,朱征宇.网页正文提取中与正文无关的图像清除技术[J].计算机技术与发展.2010年07期.

[5]时达明,林鸿飞,杨志豪.基于网页框架和规则的网页噪音去除方法[J].计算机工程.2007年19期.

启发式规则 篇2

由于Internet的飞速发展,网络上信息量的剧增以及人们对信息资源的需求,Web数据挖掘成为当今比较活跃的研究领域。Web使用挖掘是Web挖掘技术的一个重要分支,它是应用数据挖掘的技术从Web数据中发现用户访问模式的过程[1]。Web使用挖掘的结果对提供个性化服务与定制、改进Web系统性能和结构、改善Web站点结构、为商业组织提供商业智能和向用户推荐页面等方面都有重要的理论和实际意义[2,3]。

用户识别是从日志中的每一个记录中识别出相应的用户,是Web使用挖掘预处理过程中的一个非常重要的环节。目前,用户识别方法有启发式规则方法,嵌入SessionID方法,代理软件等方法。通常使用启发式规则来识别用户。这种方法简单易行,但是在实际应用当中有些问题使用启发式规则的方法不能解决。比如有些ISP(Internet Service Provider)对来自同一个用户的请求,会随机分配一个IP地址给用户,这样用户每次上网的时候就会有一个不同的IP地址,因此在这种情况下一个用户就会有很多的IP地址,即单用户多IP地址问题。如果使用启发式规则识别用户,不同IP地址代表一个新用户,导致一个用户分成多个用户的错误,这样就严重的影响了在模式识别阶段用户聚类中挖掘用户行为的准确率。另外由于代理服务器的使用,使得用户识别变得很复杂。

针对启发式规则识别用户时将一个用户分成多个用户的错误,将Cookie技术和启发式规则相结合,形成一种用户识别的综合算法CTHR(Cookie Technology and Heuristic Rule)。由于一个用户在一定期限内登陆网站时,日志中Cookie属性值不变,所以可以首先通过Cookie属性值确定一个用户。这样就弥补了启发式规则使用IP地址识别用户时产生的错误,提高了算法的准确性及效率。论文首先分析了日志数据及Cookie技术,然后给出了启发式规则的思想和CTHR综合算法。最后通过实验分析与比较了两种算法的准确性及时间复杂度,验证了CTHR综合算法的有效性。

2 相关工作

2.1 日志数据

Web服务器的log文件是进行Web使用挖掘的重要来源,因为它显性地记录了站点访问者的浏览行为。这些log文件有多种存储格式,常见的有普通日志文件CLF和扩展型日志文件ECLF。这两种格式的文件都是ASCII 文本文件,其常用的字段和含义如表1所示。

用户访问记录实例:

Fields: date time c-ip s-computername Cs-method Cs-uri-stem Sc-status Cs-version User-agent Cs(referrer)

2009-03-16 11:20:15 192.68.27.9 ZYP Get /Login.aspx 200 http/1.0 Mozilla/4.0+(MSIE+5.5;+Windows+95) default.htm

其中“-”表示没有相关的记录,这条记录表示在2009年3月16日,11点20分15秒,IP地址为192.68.7.33的用户成功访问了服务器zyp上的login.asp页面。用户传输用的协议版本是http/1.0,用户代理是Mozilla/4.0+(MSIE+5.5;+Windows+95),引用页是default.htm。

Web日志文件记录中存储的是用户访问站点信息的原始记录,但是Web日志中的数据并不完整,数据冗余量大,直接在Web日志上挖掘非常困难,而且有可能得到错误的结果,所以在进行挖掘之前,必须进行数据预处理。

2.2 Cookie技术

现在大多数浏览器都支持使用Cookie。Cookie是一种允许HTTP协议的服务器端取出或存储在客户端的文本信息。它伴随着用户请求的页面在Web服务器和浏览器之间传递。当用户请求网站页面时,应用程序发送给该用户的不仅仅是一个页面,还有一个包含日期时间和用户信息的Cookie,用户的浏览器在获得页面的同时还获得了该Cookie。Cookie的发送是通过http头部(header)来实现的,它早于文件的传递。Cookie中包含name,value,expires,path等内容。其中name为Cookie名,命名时不能使用分号和逗号,有多个name值时用分号分隔;value为此Cookie值;expires为Cookie的有效期限,即此Cookie的生存期;path为Cookie支持的路径。如果Path是一个路径,则Cookie对这个目录下的所有文件及子目录生效,如果path是一个文件,则Cookie只对这个文件生效[4]。

读写Cookie是在服务器和客户端进行的。在服务器端加入对用户访问站点的Cookie读写操作,用户访问站点时服务器不仅在用户本机内写入唯一标识此用户的Cookie,而且将其写入服务器的Web日志的扩充属性中,即在用户访问站点的每条访问记录中都有可唯一标识此用户的Cookie属性项。当用户再次访问站点时,如果用户本机中的Cookie已经存在而且有效,就继续使用该cookie作为用户标示。客户端发送页面请求,浏览器检测本机是否有相应的Cookie存在,如果有就将Cookie附在http头部,发送给服务器,服务器端响应客户端的请求,读出Cookie值,写入Web日志。关键是Cookie值的设置,在实际使用中因为Cookie值主要是用来标识用户,所以必须使用唯一标识,用户标识可以用多个属性值合并表示,例如userid=用户名+密码。同时要将Cookie的有效期设置为一个固定时间段,超出这个时间段后的用户请求可以认为是一个新的用户请求,这是为了区分一台计算机多个用户使用的情况[4]。通过使用Cookie,所有用户将由其Cookie值唯一确定,可以更快更准确的识别用户。

3 用户识别技术

3.1 启发式规则

用户识别就是从日志文件中识别出都有哪些用户访问了网站,每个用户访问了那些网页.通常使用启发式规则来识别用户。具体算法思想是:

(1):

不同的IP地址代表着不同的用户;

(2):

当IP地址相同时,不同的操作系统或浏览器(用户代理)代表不同的用户;

(3):

在IP地址相同,用户使用的操作系统和浏览器也相同的情况下,则根据网站的拓扑结构图对用户进行识别:如果用户请求的某个页面不能从已访问的任何页面到达,则判断这是一个新的用户[5]。

例如,图1代表一个简单网站的拓扑结构,该网站部分日志记录如表2所示。

根据第一个启发式规则,由于所有的日志记录具有相同IP地址,所以只能识别出一个用户,其浏览路径为:A-B-D-A-C-E-F-G-E-H-B。

根据第二个启发式规则,1,2,3,9,10与4,5,6,7,8,11的用户代理不同,这就说明至少有两个用户,其浏览路径分别是:A-B-D-E-H,A-C-E-F-G-B。

根据第三个启发式规则,如果用户请求的某个页面不能从已访问的任何页面到达,则判断这是一个新的用户。即如果当前请求的页面同用户已浏览的页面之间没有超链接关系,那么就认为存在另外一个用户。在图1中,E页不能从A或C直接到达,G只能从E到达,这就说明存在第三个用户使用相同的IP地址。所以对表1中的日志进行用户识别后,发现有三个用户,其浏览路径分别是:A-B-D-E-H,A-C-F-B,E-G。

这种方法简单易行,但如果日志数据量越大,会使得用户识别变的越复杂。因为不仅要比较所有的IP地址还要比较所有用户代理及网站的拓扑结构。如果根据Cookie属性值识别用户,就会快速而准确的识别用户。比如根据表2的Cookie属性值的不同,可以快速有效识别出3个用户。这三个用户的浏览路径也是:A-B-D-E-H,A-C-F-B,E-G。另外针对单用户多IP地址的问题,使用启发式的第一个规则IP地址去识别用户时,会造成一个用户分成几个用户的错误。笔者使用ISP连续两次登陆了辽宁工业大学电子与信息工程学院创新学分管理系统,及时从服务器上提取了50条日志记录,清理之后如表3所示。

60.23.7.247与119.115.197.35是笔者两次登录辽宁工业大学电子与信息工程学院创新学分管理系统时,ISP提供的两个不同的IP地址。u2vtuy55xle是 笔者登录网站服务器的Cookie属性值。60.21.206.190是笔者登录网站期间另外一个用户的IP地址,0o45vtzu2rry是其Cookie属性值。使用启发式规则识别用户时,由于IP地址不同,则判断共有3个用户。实际上在08:53:25 与10:02:31期间只有两个用户。这样与实际不符,所以产生了错误。

3.2 CTHR算法

针对日志数据量越大,启发式规则识别用户变的越复杂以及第一个规则IP地址识别用户产生的错误,将Cookie技术和启发式规则相结合,形成一种用户识别的综合算法CTHR。由于一个用户在一定期限内登陆网站时,日志中Cookie属性值不变,所以可以首先通过Cookie属性值确定一个用户。但是部分用户的客户端浏览器不使用Cookie,日志属性中也就不会存在Cookie值。所以算法思想分为两部分。第一部分扫描所有的Cookie属性值,根据Cookie值确定用户。第二部分的内容是:如果一些客户端浏览器不支持或不允许使用Cookie,Web日志的扩充属性中就没有Cookie属性值,这时我们使用启发式规则的思想确定用户。具体算法(伪代码)如下所示:

符号说明:Log为清洗后的日志数据库文件;U为用户的集合;L为日志文件中的一条记录;N为日志的所有记录;L.ip代表记录中的IP地址;L.agent为客户端浏览器的类型;L.Cookie为记录中的Cookie值;L.referer用户浏览的上一页,L.url为记录中的cs-Uri-stem。U.Length是用户集合的有效长度。U′是存放Cookie值为空的用户集合。

输入:日志Log

输出:用户集合U(IP,agent,Cookie,referrer,url) (初始值U为空集)

UserIdentify()

{

Set LogReader =Server.CreateObject(“IISLog”); //创建读取文件流对象

LogReader.OpenLogFile(); //打开日志文件

LogReader.ReadLogRecord(); //从日志文件中读取一条记录

U.ip=L.ip; U.Cookie=L.Cookie; U.agent=L.agent;

U.referer=L.referer; U.url=L.url; //赋值

While NOT LogReader.EndOfLogRecord //判断日志文件是否为空,非空执行操作

{

LogReader.ReadLogRecord(); //从日志文件中读取一条记录

For(j=0;j<U′.Length;j++) //循环语句

{

If(L.Cookie !=’- ’ && L.Cookie!=U[j].Cookie) //如果日志记录中Cookie属性值存在且与用户

集合中Cookie值不同,就能确定一个用户,那么U集合中增加一条新的用户记录

用户表中增加一个用户记录;

If(L.Cookie ==’- ’) //如果日志记录中Cookie属性值是字符‘-’,即不存在Cookie值

HR(L); //调用函数HR(L)

}

U=U+U′; //两个集合合并

}

HR(L)

{

If (U′.length==0) //如果U′用户集合为空,用户表中增加一条记录

U′[0].ip=L.ip ,U′[0].Cookie=L.Cookie ,U′[0].agent=L.agent ,

U′[0].referer=L.referer ,U′[0].url=L.url;

For(j=0;j<U′.Length;j++) //循环

{

If(L.ip!= U′[j].ip || L.agent!= U′[j].agent) //如果日志记录中Cookie值是‘-’即不存在Cookie值。IP地址不同或agent不同,表明是新的用户,那么U集合中增加一条新的用户记录

用户表中增加一个用户记录 ;

Else 当前请求页面不能从已访问的任何页面到达 // 如果日志记录中IP地址与U′集合中的IP地址相同, agent相同,当前请求页面不能从已访问的任何页面到达,表明是新的用户,那么U′集合中增加一条新的用户记录

用户表中增加一个用户记录;

} } }

4 算法比较与分析

4.1 经典的启发式规则与CTHR算法准确性比较

根据表3日志,使用启发式规则识别用户,由于IP地址不同,则判断共有3个用户。这样与实际不符,所以产生了错误。而使用CTHR算法,由于Cookie值存在,且有两个不同的Cookie值,所以可以判断两个用户,这与实际符合。由此可见CTHR算法比通常使用的启发式规则更能准确的识别用户。

4.2 算法时间复杂度分析

假设数据清理后日志文件中有n条记录,用户集合中最多有m个用户,每个用户最多访问p个网页。则启发式规则的时间复杂度为O(n×m×p)。CTHR算法在最坏的情况下也就是日志属性中没有Cookie值的情况,时间复杂度也是O(n×m×p),最好的情况下,即所有日志属性中都有Cookie值,时间复杂度为O(n×m)。如果一部分日志有Cookie值,一部分没有Cookie值,则时间复杂度在O(n×m×p)和 O(n×m)之间。所以说CTHR算法略优于启发式规则算法。

5 结束语

用户识别是Web使用挖掘的一个重要的预处理步骤,也是预处理过程中比较复杂的部分,直接影响挖掘算法的效率。为了得到更准确的用户访问模式,将一种基于Cookie技术和启发式规则的综合算法CTHR应用于用户识别中。通过实验比较与分析经典的启发式规则与CTHR算法的准确性及时间复杂度,证明了CTHR算法比经典的启发式规则方法更能准确有效的识别用户。由于很多用户支持与使用Cookie,此方法也能较好的解决代理服务器引发的多用户单IP的问题,所以该算法是可取的。下一步的工作是识别用户在一次访问过程中所访问的Web页面序列,即会话识别。

参考文献

[1]Srivastava J,Cooley R,Deshpande M,et al.Web usage mining:discovery and applications of usage patterns from web data[J].SIGKDD Explorations,2000,1(2):1-12

[2]Mohd Helmy Abd Wahab,Mohd Norzali Haji Mohd,et al.Data Pre-processing on Web Server Logs for Generalized Association Rules Mining Algorithm[J].proceedings of world academy of science,engineering and technology volume36december2008.

[3]Federico Michele Facca,Pier Luca Lanzi.Mining interesting knowledge from weblogs:a survey[J].Data&Knowledge Engineer-ing53(2005)225-24

[4]吴强,梁继民,杨万海.Web日志挖掘预处理中的用户识别技术[J].计算机科学,2002,29(4):

启发式规则 篇3

关键词：车间作业调度问题,蚁群算法,启发式规则

0引言

车间作业调度问题JSSP (Job Shop Scheduling Problem) 是按一定的时间顺序要求分配资源来完成任务的问题。JSSP是一类复杂且极具代表性的生产调度问题, 它具有约束松弛度紧、约束内联度高和NP-hard等特性。一直以来, 人们普遍尝试采用各种方法来求解JSSP, 如:遗传算法[1]、禁忌搜索[2]、蚁群算法[3]、演化算法[4]和模拟退火[5]等。采用单个方法的调度结果似乎不甚理想, 因而各国学者普遍采用混合方法来求解JSSP问题。这里的“混合”包括两层含义: (1) 将启发式规则融入到现有的求解方法中; (2) 两种或多种方法的有效集成。鉴于此, 本文提出了一种基于启发式规则和蚁群算法的车间作业调度方法。该方法将启发式规则有效地融入到蚁群算法中, 使得该混合方法的优化效率得到极大的改进。

1本文的混合方法

为了有效地求解JSSP, 本文提出了一种基于启发式规则和蚁群算法的混合调度方法。该方法首先采用蚁群算法得到车间作业调度问题的一组可行解, 然后采用一些启发式规则进一步优化这些可行解。该混合方法的计算流程如图1所示。

1.1状态转移规则

在t次迭代时, 蚂蚁k选择工序j的概率公式为:

$p{}_j^k\left(t\right)=\frac{[\tau {}_j(t)]{}^{\alpha }[\eta {}_j]{}^{\beta }}{{\displaystyle \sum _{p\in allowed{}_k}[}\tau {}_p(t)]{}^{\alpha }[\eta {}_p]{}^{\beta }}$ (1)

这里, allowedk表示蚂蚁k在当前位置 (当前时刻的给定机器) 可加工工序的集合;$\tau {}_j\left(t\right)$表示t时刻工序j上的信息素水平;ηj=1/tj表示工序加工时间的倒数;α, β分别表示工序j的信息素启发值和加工时间启发值的权重。本文只研究制造周期最短这种单目标优化的JSSP。从蚂蚁选择工序的概率公式 (1) 可看出, 本文工序选择规则优先选取信息素水平比较高的、加工时间比较短的一些工序。

1.2信息素局部更新规则

信息素是蚂蚁找寻路径的依据, 信息素越多, 找到该路径的概率越大。在JSSP问题中, 排在前面的工序都是优先加工的。为了保障前面工序的优先性, 本文通过公式 (2) 来进行信息素的更新。通过公式 (2) 不难发现对于那些排在前面加工的工序, 蚁群算法给它们追加更多的信息素;使得在构造后续可行方案时, 这些工序能优先加工。同时, 对于那些排在后面加工的工序, 蚁群算法给它们追加较少的信息素;使得在构造后续可行方案时, 这些工序不能被优先加工。通过对信息素局部更新规则的执行, 可以尽可能地保留本次迭代最优解的工序加工顺序。

Δτj=1-log2h/log2H (2)

这里的h表示在第t次迭代的最优可行方案中, 工序j在给定机器上的加工次序, H表示所有任务的最大工序数。

当所有蚂蚁完成当前可行解的构造后, 蚁群算法将按照信息素局部更新规则来改变所有工序上的信息素水平。

τj (t+1) =τj (t) +Δτj (3)

1.3信息素全局更新规则

在蚁群算法中, 为了增加当前最优解被访问的机会, 用公式 (4) 来加大当前最优可行方案的信息素水平 (通过试验发现倍数取3比较合适) 。因此给出信息素全局更新规则如下:在某次迭代中, 如果当前最优可行方案被改进, 蚁群算法将应用公式 (4) 所示的信息素全局更新规则来更新当前最优可行方案上的信息素水平。

Δτj=3 (1-log2h/log2H) (4)

τj (t+1) =τj (t) +Δτj (5)

这里的hh表示在当前最优可行方案中, 工序j在给定机器上的加工次序, HH表示所有任务的最大工序数。

1.4信息素衰退规则

在每次迭代后, 所有工序上的信息素都会发生一定程度的衰减。为了防止算法陷于停滞状态, 蚁群算法将每个工序上的信息素都控制在范围[τmin, τmax]内。

$\tau {}_j\left(t\right)=\{\begin{array}{l}\min \{\tau {}_{\max },(1-\rho )\tau {}_j(t)\}\text{i}\text{f}\tau {}_{ij}(t)>\tau {}_{\max }\\ \max \{\tau {}_{\min },(1-\rho )\tau {}_j(t)\}\text{o}\text{t}\text{h}\text{e}\text{r}\end{array}$

(6)

这里ρ (0<ρ<1) 表示信息素衰减因子。

1.5启发式规则1—关键工序优先

启发式规则“关键工序优先”的主导思想:调整当前可行方案中关键工序 (关键路径上的工序) 的加工顺序, 改进当前可行方案的质量。选择条件:当前方案中存在关键工序, 即此工序是其他工序的前提或对整个工序有重要影响。在实施本规则时, 可考虑按照以下优先顺序改进当前的可行解: (1) 优先安排当前可行方案中的关键工序; (2) 优先安排当前可行方案中原先安排的工序; (3) 优先安排加工时间最短的工序。

1.6启发式规则2—剩余加工时间最长的任务优先

启发式规则“剩余加工时间最长的任务优先”的主导思想:调整当前可行方案中剩余加工时间最长任务的工序的加工顺序, 改进当前可行方案的质量。选择条件:当前方案中存在剩余加工时间最长的任务工序, 即对此工序进行改进可大大提高整个工序方案质量。在实施本规则时, 可考虑按照以下优先顺序改造当前的可行解: (1) 优先安排当前方案中剩余加工时间最长任务的工序; (2) 优先安排当前可行方案中原先安排的工序; (3) 优先安排加工时间最短的工序。

1.7启发式规则3—剩余加工时间最长的机器优先

启发式规则“剩余加工时间最长的机器优先”的主导思想:调整当前可行方案中剩余加工时间最长机器的工序的加工顺序, 改进当前可行方案的质量。选择条件:当前方案中存在剩余加工时间最长机器的工序, 即对此机器工序进行改进可大大提高整个工序方案质量。在实施本规则时, 可考虑按照以下优先顺序改造当前的可行解: (1) 优先安排当前方案中剩余加工时间最长机器的工序; (2) 优先安排当前可行方案中原先安排的工序; (3) 优先安排加工时间最短的工序。

2仿真实例

为了验证本方法的有效性, 我们采用8个不同规模的JSSP标准实例 (见表1) 来验证4种不同的实验方案 (蚁群算法、基于规则1的蚁群算法、基于规则2的蚁群算法和基于规则3的蚁群算法) 。本文所有算法均采用Matlab语言实现, 在内存为256M、CPU为Intel 2.4G的PC中运行。笔者应用每种方案求解每个实例各10次, 取其均值作为最终优化结果。本文蚁群算法中的参数设置如下:α=2、β=3、ρ=0.02、τmax =50、τmin=1、τj (0) =10。算法终止条件为: (1) 当前最优解连续30代内没有被改进; (2) 当前最优解和已知最优解的误差小于0.005; (3) 达到最大迭代次数=max (200, 2倍工序数) 。采用4种实验方案求解8个测试实例的优化结果如表2所示。实验结果表明:将调度规则融入到蚁群算法中, 并不增加混合蚁群算法的总体优化时间;相反, 知识型蚁群算法的优化时间比标准蚁群算法在一定程度上要少。总的来讲, 无论是优化结果还是优化时间, 本文提出的混合蚁群算法都明显优于标准蚁群算法。

3结论

本文的主要创新点:提出了一种基于启发式规则和蚁群算法的车间作业调度方法。该方法将启发式规则有效地融入到蚁群算法中, 使得该混合方法的优化效率得到极大的改进。仿真实例表明, 该方法是可行的、正确的和有效的。

参考文献

[1] GoncalvesJ F, Magalhaes Mendes J J De, Re-Sende M G C.A hybrid genetic algorithm for the job shop scheduling problem [J].European Journal of Operational Research, 2005, 167:77-95.

[2]Pezzella F, Merelli E.A taboo search method guided by shifting bottle-neck for the job shop scheduling problem[J].European Journal of Op-erational Research, 2000, 120:297-310.

[3]Huang K L, Liao C J.Ant colony optimization combined with taboosearch for the job shop scheduling problem[J].Computers and Opera-tions Research, 2007:Article in Press.

[4] Tanev I T, Uozumi T, Morotome Y.Hybrid evolutionary algorithm-based real-world flexible job shop scheduling problem: application service provider approach [J].Applied Soft Computing, 2004, 5:87-100.

启发式规则 篇4

卫星调度是指在满足卫星资源约束的条件下,将任务分配到各卫星资源上执行,对用户请求做出响应的过程。在实际调度中,任务通常都具有实时性,即任务存在一个截止期,并且任务必须在其截止期内完成。例如,当地震发生时,救灾部门希望及时获取灾区图像,以便迅速展开救援行动。如果时间过长,就会导致大量人员伤亡,造成巨大的损失。因此,卫星实时调度已成为目前各国研究的热点问题。

调度问题具有动态性。比如任务动态到达、云层覆盖、卫星资源失效等[1]。而传统的调度模式假定与调度问题有关的信息事先可知,预先生成调度方案,并且调度方案在任务执行过程中不能改变,显然不适用于动态调度问题。动态调度是指在调度过程中,对调度方案重新调整以适应任务、环境、资源的动态变化。

针对卫星动态调度问题,国内外学者已取得一定研究成果。J.C.Pemberton, L.G.Greenwald[2]从理论上研究了多星动态调度问题,提出动态调度的观点。Stephen C.Billups[3]介绍了卫星动态调度的概念,分别采用遗传算法、整数规划算法和图论方法求解任务动态到达条件下的卫星调度问题。Sun Baolin等[4]将卫星动态调度问题描述为约束条件动态变化的动态权重最大的CSP问题。刘洋等[5,6]基于动态约束满足问题,针对初始方案执行过程中任务动态到达的情况,建立以最大化完成任务优先级和最小扰动为目标的多星动态调度模型。王军民等[7]针对有新任务插入的多星动态调度问题,在不考虑卫星能量和存储容量的条件下,提出了一种基于自由度规则的动态启发式求解算法。以上研究没有考虑任务的截止期要求,不适用于实时调度问题。

目前,国内外针对卫星实时调度研究十分有限,主要存在以下几方面的难点:

1)必须综合考虑任务截止期、任务执行时间窗口、动态环境等因素,比传统调度更为复杂。

2)任务的数量及到达时间不确定,增加了建模求解的难度。

3)实时调度需要考虑多个目标,并且目标之间相互冲突,如方案扰动最小、任务完成优先级之和最大、消耗能量最小等,导致求解困难。

本文考虑任务实时性要求,分析了多星实时调度的复杂约束,建立了基于优先权值最大和扰动最小的多目标实时调度模型。在此基础上,提出了基于任务紧迫度和最大比例自由度的双启发式退出规则的多星实时调度算法(MSRTSA)。最后进行了大量仿真实验,实验结果表明本文提出的算法具有较好的调度收益和稳定性,能够有效解决多星实时调度问题。

1 问题描述

为便于问题求解,我们做出如下假设:

1)任务类型为点目标任务,即在卫星一次过境时就能完成的任务。

2)任务具有唯一性和不可分割性,即一个任务只能被执行一次,并且任务一旦被执行,就不能被中止;

3)任务具有互斥性,即一个资源在同一时刻最多只能处理一个任务;

4)卫星在两个相邻任务之间需要满足一定的动作转换时间。在实际中,卫星对不同任务具有不同的观测角度,并且,相邻任务之间转换还要考虑卫星的开关机时间、侧摆时间、姿态稳定时间等,本文将这些因素统一描述为动作转换时间。

5)在多星实时调度问题中存在以下四类任务:已完成任务(FT),正在执行任务(ET),等待任务(WT)和新到达任务(NT)。本文采用非抢占调度方式,即FT和ET中的任务调度决策不能改变,WT和NT可以进一步调度优化。因此,本文主要针对WT和NT中的任务进行规划调度。

基于以上假设,我们建立一个基于多星实时调度的数学规划模型,包含五个基本对象:任务、资源、时间窗口、执行约束和调度目标。

1.1 任务

设集合T={t1,t2,…,tn}为任务集合, T中每一个任务ti∈T有一个优先级pi,到达时间ai,执行时间di,截止期ei,以及完成该任务需要消耗的存储容量和能量分别为ui和vi。考虑到实际情况,用户通常会一次性提交多个任务,因此,本文假设新任务是分批到达的。

1.2 卫星资源

设卫星资源集合为R={r1,r2,…,rm},每个卫星资源rj∈R可表示为rj=(Mj,Ej,M′j,E′j),其中Mj,Ej分别表示卫星总容量、总能量、当前可用容量、当前可用能量。

1.3 时间窗口

设TWij={aoij1,aoij2,…,aoijKij}是任务ti在卫星资源rj上的一组时间窗口。对给定的时间窗口aoijk∈AOij,可表示为aoijk={[wsijk,weijk]},其中[wsijk,weijk]表示任务ti在卫星rj上的第k个时间窗口。为减轻计算复杂性,本文将时间离散化处理,即时间变量τ为整数。

矩阵X={xijk}n×m×Kij用来表示任务的调度信息,如果任务ti被分配到卫星rj的第k个时间窗口,元素xijk等于“1”;否则,xijk等于“0”。另外,btij,ftij分别表示卫星rj上任务ti的开始执行时间,结束执行时间,并且有ftij=btij+di。

1.4 执行约束

因为每个任务都是不可分且非抢占的,一个任务只能被分配给一个资源,并且只能被执行一次。因此,得到任务唯一性约束C1:

C1:${\displaystyle \sum _{j=1}^m{\displaystyle \sum _{k=1}^{{\rm K}{}_{ij}}x}}{}_{ijk}\le 1\forall t{}_i\in {\rm T}$。

由任务的实时性,每个任务ti必须在其截止期内执行,否则该任务的完成就失去了意义。从而,得到任务截止期约束C2:

C2:ftij≤ei, ∀rj∈R,aoijk∈AOij,xijk=1;

另外,每个任务还必须在卫星的有效成像时间窗口内执行,假设对卫星rj上一个任务ti,满足成像时间窗口约束C3:

C3:btij∈[wsijk,weijk-di],

∀ti∈T,rj∈R,xijk=1。

考虑卫星rj上的一组正在等待执行任务的集合序列Tj={t1j,t2j,…,tHj}(Tj∈T＼FT),即Tj中t1j最先被执行,tHj最后被执行。如果任务tij成功执行,卫星需要足够的准备时间,以便执行下一个任务ti+1,j。因此,必须考虑准备时间约束。

定义1 动作转换时间。动作转换时间ci,i+1,j定义为在卫星rj上从完成任务tij到开始执行下一任务ti+1,j需要的最小时间。

定义2 动作转换能量。动作转换能量zi,i+1,j定义为在卫星rj上从任务tij完成到任务ti+1,j开始执行需要消耗的能量。

对于任意卫星rj上的任务ti,必须满足动作转换时间约束C4和能量约束C5:

此外,在卫星rj中任务ti还必须满足卫星容量约束C6:

C6:${\displaystyle \sum _{i=1}^{{\rm H}j}u}{}_i\le {\rm M}{}_j,\forall r{}_j\in \mathit{R}$。

1.5 调度目标

卫星每完成一个任务,就能获得相应的收益。本文的调度目标首先考虑提高调度收益,即主要调度目标是在满足约束条件下最大化任务优先级之和。

$\max {\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^{{\rm H}j}{\displaystyle \sum _{k=1}^{{\rm K}{}_{ij}}x}}}{}_{ijk}p{}_i$。

此外,调度过程中应当最小化所有任务的扰动。在介绍这个目标之前,我们先给出扰动的定义。

定义3 扰动:扰动δj定义为在第j次调度中,新生成的调度方案与原方案之间距离的度量。在本文中扰动主要来源于以下两类任务变化:

(1)任务结束时间变化;

(2)新任务被拒绝。

假设总共有新到达s个任务,则总的调度次数为s,从而扰动

$\delta ={\displaystyle \sum _{j=1}^s\delta }{}_j={\displaystyle \sum _{j=1}^s{\displaystyle \sum _{i=1}^n{\displaystyle \sum _{k=1}^2\omega }}}{}_{k}disturb{}_k(i,j)$。

其中,δ是所有任务调度过程中总的扰动,ωk(k=1,2)表示任务第k类变化的影响因子,且ω1<ω2。

disturbk(i,j)定义如下:

$disturb{}_k(i,j)=\{\begin{array}{l}1‚\text{如}\text{果}\text{在}j\text{次}\text{调}\text{度}\text{中}\text{发}\text{生}\text{第}k\text{种}\text{变}\text{化}\\ 0‚\text{否}\text{则}。\end{array}$

因此,最小扰动目标为

$\underset{t{}_i\in {\rm T},r{}_j\in \mathbf{R}}{{\displaystyle \min }}{\displaystyle \sum _{j=1}^s{\displaystyle \sum _{i=1}^n{\displaystyle \sum _{k=1}^2\omega }}}{}_{k}disturb{}_k(i,j)$。

2 问题求解

多星实时调度涉及目标多、约束条件杂、计算复杂性大,采用一般的最优化算法很难求解,目前针对此类问题主要采用启发式算法,虽然启发式方法不能证明解的最优性,但是它能够在一定的计算复杂度下获得问题的近似最优解。

本文针对新任务动态到达的多星实时调度问题,借鉴了迭代修复思想[10]和基于自由度的退出启发式规则[7],提出了一种基于任务紧迫度和最大比例自由度的双启发式退出规则的求解算法。算法的主要思想是任务置换[8,9],首先基于任务截止期和优先级对新任务进行排序,然后取出紧迫度最高的任务,在不影响原卫星资源任务执行序列的条件下直接插入该任务,如果成功则转下一个任务;否则根据该任务的冲突集查找可与该任务进行置换的任务,并且对可置换的任务计算紧迫度,根据紧迫度的高低逐个迭代置换新任务到队列中,并对置换出的任务进行重新直接插入,如果成功则表明新任务插入成功,否则任务插入失败。

2.1 规则

在介绍算法前,首先给出如下定义:

定义4 紧迫度。定义任务ti的紧迫度Qi:

$Q{}_i=\frac{p{}_i}{e{}_i-a{}_i}$; ∀ti∈NT。

本文中紧迫度用于选择新任务,优先级高、截止期短的任务应当优先调度。

定义5 可置换任务。如图1所示,在任务ti的某一时间窗口$ao{}_{ijk}(ao{}_{ijk}\in {\displaystyle \underset{r{}_j\in \mathbf{R}}{\cup }A}{\rm O}{}_{ij})$中,ti不能直接插入,若要插入,需退出任务k或者k+1,称任务k或k+1是任务ti的在时间窗口aoijk下的可置换任务(图1)。

在实际卫星序列中,可能需要退出两个及以上任务才能保证当前任务的成功插入,然而,退出后的多个任务由于截止期、优先级不同以及重新插入会造成更大的扰动和计算复杂性,因此在本文中暂不予考虑。

定义6 可置换任务集。可置换任务集定义为在任务ti的所有时间窗口内,其可置换任务的集合,记为TRi。

定义 7 置换任务集。令TRi中所有任务的到达时间为任务ti的到达时间ai,计算TRi中所有任务的紧迫度,并与任务ti的紧迫度比较,置换任务集定义为TRi中紧迫度比任务ti低的任务集合,记为TEi,TEi⊆TRi。

TRi中能够与任务ti发生置换的任务的紧迫度高于ti,则置换ti会产生扰动,同时会降低任务的收益,故可置换任务集与置换任务集的区别在于舍去了紧迫度比ti高的任务。

定义8 时间窗口度。设TEi中的任务序列TEi={TE1i,TE2i,…,TEαi},其中第j(j∈[1,α])个任务的时间窗口度TWji定义为该任务在所有卫星资源上的可行时间窗口个数。

定义9 比例自由度。TEi中第j个任务的比例自由度PROji定义为:

${\rm P}R{\rm O}{}_{ji}=\frac{{\rm T}W{}_{ji}}{{\displaystyle \sum _{j=1}^{\alpha }{\rm T}}W{}_{ji}}\frac{1}{Q{}_j}$; j∈[1,α]。

定义10 最大比例自由度。任务ti的置换集TEi最大比例自由度REi定义为:

REi=max{PROji}, j∈[1,α]。

最大比例自由度用于选择与任务ti置换的任务,比例自由度越大,表明该任务的可行时间窗口较多,紧迫度相对较低,再调度成功率较高。

定义11 保护集。保护集TP定义为该集合中的任务不能与其他任务发生置换关系。

2.2 新任务插入

新任务的插入是指在满足卫星资源约束条件下,直接将新到达任务插入到卫星队列中去,同时不影响原调度方案的序列。

新任务ti的直接插入过程描述为:遍历整个卫星资源,在新任务ti所有时间窗口中查找可插入时间片,同时验证是否满足相关约束条件,如果满足,则将ti插入,同时更新当前调度方案CurrentSchedule,否则插入失败。

新任务直接插入函数描述如表1。

2.3 多星实时调度算法(MSRTSA)

由于每个任务都有到达时间和截止期,在给定了初始调度方案CurrentSchedule后,针对新到达的任务,应该综合考虑任务优先级和截止期的影响来对新到达的任务进行排序。

针对新任务ti,首先采用直接插入的方式对其调度,若成功则ti调度成功,否则采取任务置换的方式对ti进行调度,本文基于任务紧迫度和最大比例自由度的双启发式的退出规则提出了多星实时调度算法(MSRTSA)。

该算法简要描述如下:

Step 1:计算NT中每个任务的紧迫度;

Step 2:取紧迫度最大的任务调用任务直接插入函数TaskInsertion,且NT=NT＼ti;

Step 3:若成功,返回Step 2,否则转下一步;

Step 4:求出任务ti在整个卫星资源上的可置换任务集TRi;

Step 5:求出任务ti在整个卫星资源上的置换任务集TEi;

Step 6:根据TEi中每个任务的时间窗口度分别计算其中所有任务的比例自由度;

Step 7:取最大比例自由度的任务置换ti,同时将该任务从TEi加入到保护集TP,并从TEi中删除该任务,同时验证任务ti是否满足相关约束。若满足,任务ti暂时插入成功,然后对TP中的任务调用任务插入函数TaskInsertion,若插入成功,则说明任务ti成功插入,返回Step 2;否则,取TEi中最大比例自由度的任务继续迭代,直至任务ti成功插入或者TEi为空。

Step 8:TEi为空时,任务ti插入失败,返回Step 2。

3 实验分析

为验证MSRTSA算法的性能优越性,将其与基于最大自由度的启发式算法(MFHA)[7]和基本实时调度算法(DISA)进行比较。

(1)MFHA:不考虑任务实时性对任务直接插入,插入失败则选择最大自由度冲突的任务进行置换,然后再重新插入置换出来的任务,如果重插入成功则表明新任务插入成功,否则基于收益插入优先级高的任务。

(2)DISA:仅考虑任务的紧迫度,直接对任务进行插入。

3.1 实验方法与参数

本文考虑了在不同卫星平台上的两个传感器资源,表2列出了其相关参数。

表3列出了实验的主要参数及取值范围。

(1)任务ti的截止期描述为ei=ai+DueDate,其中DueDate服从N(BaseDueDate,1)的正态分布。

(2)间隔时间表示批次任务到达的时间间隔,是一个随机正整数,服从均匀分布。

(3)任务优先级、任务执行时间、任务间转换能量、任务间转换时间、任务耗费能量、任务耗费容量均为相应区间内随机正整数,服从均匀分布。

任务与卫星之间的时间窗口由STK软件计算生成。此外,ω1=0.5, ω2=1.5,仿真次数为10次。

3.2 任务数量对算法影响

本节主要研究任务数量对算法产生的影响。实验结果如图2所示。

图2(a)表明随着任务数量的增加三种算法的任务优先级也不断增大,这是因为任务数量越多,可接受的任务也就越多,从而任务优先级也就越大。此外,MSRTSA的任务优先级比MFHA略低,原因在于MSRTSA综合考虑了任务优先级和扰动,为降低扰动,当置换出的紧迫度较低的任务不能重新获得资源时,舍弃该新任务。MSRTSA的任务优先级比DISA高,原因在于MSRTSA考虑了任务置换,为新任务的插入创造了空间。

图2(b)表明随着任务数量的增加,MSRTSA和MFHA的扰动也增大。MSRTSA的扰动明显比MFHA小,原因在于MFHA为追求最大收益,舍弃了置换出的优先级低的任务,增加了扰动。此外,DISA不与任何任务发生置换,其已调度任务不发生变化,故其扰动始终为“0”。

3.3 任务到达率时间对算法影响

本节主要研究任务到达率对算法的影响,实验结果如图3所示。

图3(a)表明随着任务到达率的增加,调度任务优先级也不断增大,原因在于任务到达间隔时间增大,新任务之间的调度冲突变小,使得任务有更多的时间被接受。MSRTSA增长的幅度明显大于MFHA和DISA,这是因为任务到达率增大,MSRTSA有足够的时间根据任务的紧迫度的大小来对任务进行合理排序并调度,使得可接受任务也逐渐比MFHA和DISA更多。

图3(b)表明随着任务到达率的增加,扰动逐渐减小,原因在于任务到达率的增加使得任务之间的冲突度越来越小,更多的任务不用与其他任务发生置换就能被接受。

3.4 任务截止期对算法影响

本节主要研究任务截止期对算法的影响,仿真结果如图4所示。

图4(a)表明随着任务截止期的增加,调度任务优先级不断增大,原因在于任务截止期越长,任务可调度的时间越宽松,被接受机会也越大。MSRTSA比MFHA和DISA略高,这是因为任务截止期越长,MSRTSA根据任务紧迫度的大小对任务进行合理分配调度时间,增加了任务被接受的机会,使得更多的任务被接受。

图4(b)表明随着任务截止期的增加,MSRTSA的扰动增大,而MFHA的扰动逐渐减小,且MSRTSA的扰动小于MFHA,原因在于任务截止期越长,MSRTSA根据任务紧迫度的大小对任务进行合理分配调度时间,增加了任务被接受的机会,使得更多的任务通过任务置换被接受,增加了MSRTSA的扰动; 而MFHA则是在任务截止期逐渐增大时, 任务之间的冲突相对减小,使得扰动也逐步减小,但MFHA基于调度收益出发,接受优先级高的任务而舍弃优先级低的任务,故其产生的扰动大于MSRTSA。

4 结论与展望

本文建立了一个多星实时调度的数学规划模型,综合考虑任务收益和扰动提出了基于紧迫度和最大比例自由度的双启发式退出规则对模型求解。最后通过大量仿真实验,与MFHA和DISA算法在任务规模、任务到达率和任务截止期三个方面进行了性能比较分析。实验结果表明,本文算法适用于多星实时调度问题。在下步研究中,本文主要从三个方面细化研究:1)细化任务间转换时间,进一步考虑卫星视场角、开关机、姿态稳定等时间约束。2)考虑卫星在使用过程中突然失效而不能正常工作导致的任务重新分配问题。

摘要：多星实时调度问题是目前卫星调度领域的研究热点。针对实时任务动态到达的情况,建立了多星实时调度数学规划模型。提出了基于任务紧迫度和最大比例自由度的双启发式退出规则的多星实时调度算法。仿真实验结果表明,该算法较好地平衡了调度收益和稳定性,适用于多星实时调度问题。

关键词：多星实时调度,任务置换,紧迫度,最大比例自由度

参考文献

[1] Verfaillie G,Bensana E,Michelon-Edery C,et al.Dealing with un-certainty when managing an earth observation satellite.Fifth Interna-tional Symposium on Artificial Intelligence,Robotics and Automationin Space,1—3 June,1999:205—207

[2] Pemberton J C,Greenwald L G.On the need for dynamic schedulingof imaging satellites.Land Satellite Information IV/ISPRS Commis-sion I/FIEOS 2002 Conference.Colorado,USA,2002

[3] Billups S C.Satellite mission scheduling with dynamic tasking.Uni-versity of Colorado at Denver and Health Sciences Center MathematicsDepartment,2005

[4] Sun Baolin,Wang Wenxiang,Qi Qianqing.Satellites scheduling al-gorithm based on dynamic constraint satisfaction problem.Internation-al Conference on Computer Science and Software Engineering,Wu-han,2008;4:167—170

[5]刘洋,陈英武,谭跃进.一种有新任务到达的多卫星动态调度模型与方法.系统工程理论与实践,2005;4:35—41

[6]刘洋.成像侦察卫星动态重调度模型、算法及应用研究.长沙:国防科技大学博士学位论文,2005

[7] Wang Junmin,Li Jufang,Tan Yuejin.Study on heuristic algorithmfor dynamic scheduling problem of earth observing satellites.EighthACIS International Conference on Software Engineering,Artificial In-telligence,NPC,2007;1:9—14

[8] Kramer L A,Smith S F.Task swapping:making space in schedulefor space.Fourth International Workshop on Planning and Schedulingfor Space,2004

[9] Kramer L A,Smith S F.Task swapping for schedule improvement:Abroader analysis.Fourteenth International Conference on AutomatedPlanning and Scheduling.AAAI,Canada,2004:235—243