求强规划解的快速状态分层算法

在求强规划解时,通过状态分层可以大幅减少问题规模,提高搜索效率,并能得到规划路径较短的强规划解。但现有分层算法本身有一定的复杂度,在状态较多时开销较大。为此,通过改进已有分层算法,设计一种适用于求强规划解的快速状态分层算法。采用链式双向图结构保存数据,在分层时修改已遍历的状态动作序偶,并根据修改结果直接进行分层判断,使得分层时只需要判断前一层状态而不是所有已分层状态,避免对非必要状态转移的搜索以及对必要状态转移的重复搜索。实验结果表明,该算法的分层速度优于已有的矩阵乘分层算法。     

一种快速求强规划解的算法

为提高求解效率,设计一种求强规划解的简化分层算法。以传统分层算法为基础,引入贪心选择策略,对每个非目标状态的动作进行筛选,去除对求解强规划解无益的动作,加快状态向下搜索的速度,并在改进分层的基础上,优化求强规划解策略,由于在求解过程中会存在大量重复搜索,因此建立一个集合保存已访问状态的信息,避免对状态的重复搜索。分析结果表明,在初始状态到达目标状态路径都不重合的情况下,改进算法的时间复杂度为O( nm)( n为初始状态个数,m为层数),在都重合情况下为O( m),优于普通正向搜索算法与反向搜索算法。     

分层法求最小权值强规划解

在不确定规划领域中,以往对强规划解的研究侧重于解本身,很少考虑不确定转移系统执行动作所需的代价;而已有的研究最小权值强规划解的算法效率不高。针对这一问题,引入模型检测的强规划分层方法,设计了一种快速求解最小权值强规划解的算法。该算法首先将不确定规划问题中的状态进行强规划分层,然后利用分层信息反向搜索最小权值强规划解;且在搜索的过程中,根据算法策略,实时更新所需搜索层数的上界和下界,从而避免了大量的无用搜索,提高了搜索效率。实验表明:所设计的算法能快速求解出最小权值强规划解,求解效率比已有的直接求解最小权值强规划解的算法高;且分层数和动作数越大,优势越明显。     

自动并行化中不规则循环的代码生成

许多大规模计算程序包含了不规则循环,但在面向分布存储的自动并行化中,以往的研究难以在编译时为不规则循环生成并行代码。针对一类常见的不规则循环提出了一种代码生成方法, 该方法 能在编译时将串行代码转换成等价的并行计算和通信代码,通过计算分解和数组引用的访问表达式来求解不规则循环在各处理器的本地定义集,并通过部分冗余的通信来满足不规则数组引用的生产者-消费者关系。实验结果表明,该方法是有效的,并对测试用例取得了预期的加速比。     

不确定可逆规划的强循环规划解

动作的执行在理想情况下是确定的,但现实生活中常常因为意外情况的发生而造成了不确定性,并产生不利影响.针对这种情况,建立了一种新的不确定规划模型,在不确定规划中增加了两个约束：1)所有动作的执行是可逆的;2)若一个状态在理想情况下不能达到目标,那么它不能企图在执行一个动作时发生意外而接近或达到目标.在该模型下设计了求解强循环规划的算法,首先只考虑所有动作的执行是在理想情况下发生的,这时可以将规划子图转换为规划子树并求出规划子树中每个状态的可达性;接下来考虑所有动作执行意外的情况,若动作被意外执行之后不能到达目标状态,则删除这个动作并更新规划子图和规划子树,最后通过遍历规划子图和规划子树求强循环规划解.考虑到有些意外的发生并不可预知,该算法能够在意外发生时只对部分失效的规划解进行更新而不需要重新求规划解.实验结果证明该算法能够快速地更新规划解且与问题的规模大小无关.     

一种基于受体编辑和免疫抑制的人工免疫系统模型

被广泛采用的人工免疫系统模型ARTIS中的检测器没有主动学习能力,在具体应用中存在检测半径设定困难、检测性能低等问题,受生物免疫中受体编辑和免疫抑制的启发,提出了一种新的人工免疫系统模型REISAIS(Receptor Editing and Immune Suppression based Artificial Immune System),模型通过受体编辑分别 在耐受期和成熟期 赋予检测器一定的主动学习能力,从而提高了模型的检测率,而免疫抑制机制的引入则使得模型的误报率得到了有效控制。给出了模型中检测器和抑制器演化过程的形式化描述,对模型性能进行了分析,证明了受体编辑机制的引入在提高模型检测性能上的有效性。理论分析以及实验结果显示,与ARTIS模型相比,REISAIS模型无需设定检测半径并且检测性能更好。     

基于特征模糊贴近的数据库约束挖掘算法

传统的关联规则算法,只考虑了类内的关联性,忽略了类间的相似性特征、高开销的分类过程、耗时的关联过程。提出了数据内间特征模糊贴近分类的数据库约束挖掘算法,其通过数据模糊集间的贴近度描述数据间的一致度,在传统的神经网络挖掘技术中,引入数据融合技术,对类间数据进行分类处理后,对原始挖掘数据的动态特征进行分析获取新的挖掘模型,以在大规模数据库中准确查询目标数据。仿真实验结果表明,算法挖掘稀疏数据集和密集数据集的效率都优于传统的关联规则算法,极大提高了数据库的挖掘效率。     

基于ASP的CSP进程描述与组合研究

前期工作中,为解决CSP模型检测不支持一次运行验证多条性质的问题,构建了基于ASP的CSP模型检测框架,但其存在着可描述并发进程形态不完善与可验证并发系统规模受限的问题。构建了全新的并发系统ASP描述体系,其解决了前期工作中前缀描述不允许出现类环状结构的问题,可完整描述各种形态的CSP进程。研究了并发组合进程生成技术,它可使多个进程自动化并发组合,并生成一个满足所有行为特性、具有一致结构特性的新进程,保持了验证框架内进程描述的一致性,有利于并发进程的抽象与验证。实验表明了基于ASP的CSP进程描述与组合进程生成技术的有效性,以及基于该ASP描述体系的系统性质验证的可行性。     

一种基于GPU的并行算法功耗评估方法

随着软件和硬件的不断发展,图形处理器(GPUs)已经广泛用于通用计算领域,并作为加速器来协助CPU加速程序的运行。为了追求高性能,GPU往往包含成百上千个核心运算单元,高密度的计算资源使其在性能远高于CPU的同时功耗也高于CPU,因此功耗问题已经成为制约GPU发展的重要问题之一。分析了并行程序在GPU上运行时消耗的功耗,提出了并行算法在GPU上运行的功耗评估方法,接着通过并行前缀求和算法对该方法进行了详细的论述与分析。在实验部分通过稀疏矩阵向量乘算法的实际应用对该方法的正确性以及敏感性进行了证明与分析。结果表明,对于给定的程序,在满足性能要求的前提下,最优线程块数、存储访问方式以及任务分配顺序是影响系统功耗的关键因素。     

基于不可追踪模型的轻量级RFID认证协议

在Ha等提出的基于Hash函数的低成本RFID认证协议中, 敌手捕获 标签和读卡器之间传送的信息后,就可以实现跟踪攻击。在分析Ha等提出的低成本RFID认证协议的基础上,设计出了 效率更高的追踪攻击算法。Ha等提出的低成本RFID认证协议易于遭受追踪攻击,敌手可以从低位到高位,逐个比特位地猜测出合法的标签密钥的比特位,针对这一缺点提出了可以抵抗追踪攻击的改进协议,并用不可追踪模型形式化证明了该协议不可追踪的鲁棒性。     

不确定规划中非循环可达关系的求解方法

对一个不确定状态转移系统求多个规划问题,那么获得不确定状态转移系统的状态可达关系可以方便求解规划问题,减少冗余计算,建立系统的引导信息。提出一个关于矩阵求不确定领域的状态可达性关系的方法,主要思想是以矩阵乘法来模拟状态转移系统中状态转移,对不确定动作带来的扩散和确定关系带来的聚合进行了统计和处理,从而获得状态可达信息。证明了方法的正确性和有效性。在不确定规划中确定了状态之间的可达性关系,可以在求规划解时删除对规划没有用的状态节点和状态动作序偶;选择能到达目标节点的状态节点和状态动作序偶;进行启发式正向搜索;减少大量冗余计算;提高求解效率。     

多agent规划领域中的观察信息约简

观察信息约减是近年来不确定规划中的研究热点,但研究集中于单个agent的环境,在多agent规划环境下的研究不足。面对多agent环境下的规划问题,设计了一种用于不确定规划领域中多agent求解协同规划解的ORMAP算法。该算法首先根据基于模型检测的不定规划中的状态分层思想,将问题领域的所有状态进行分层,以此来减少不同的agent的冲突,再利用以最小代价优先的回溯法搜索协同规划解,同时在解的搜索过程中选择最小的观察信息集,使求出的协同规划解在众多符合条件的协同规划解中所需要的观察信息最少或接近最少,这样就达到了信息约简的目的。最后通过实验证明,在考虑了观察信息约简的限制条件后,这种算法的效率较高。     

基于遗传算法的机器人分层模糊控制

为解决模糊多变量控制中规则数随系统变量数呈指数增长的问题,针对机器人轨迹跟踪的特点,提出了一种分层模糊控制器的设计方法。该方法不仅减少了模糊规则数,而且使模糊控制逻辑变得清晰明了,其中控制参数采用遗传算法整定。实验结果证实:该方法控制效果好、系统跟踪速度快。     

实时通信Agent在楼宇智能控制中的研究与实现

文章依据递阶智能控制系统理论,将人工智能原理中的智能Agent技术运用于楼宇智能控制系统(IBAS,Intelligent Building Automation System)当中,论述了如何开发一个处于协调级的实时通信软件Agent,此Agent除完成实时通信的主要功能外,还可完成故障诊断、缓冲控制、数据过滤等人性化功能。文中给出了已经开发完成的软件Agent的主要思路和相关代码,最后总结展望了研发此类软件的改进途径和方向。     

基于学习的规划技术研究

经过近十多年的努力,现代智能规划器无论是效率还是处理能力均得到了极大提高。鉴于现有规划理论的局限性,进一步提高现有规划技术效率已愈显困难。现有的大多数规划器均不具备学习能力,无法从先前求解经验中学习有用知识。综述了基于学习的规划技术的发展现状,然后重点介绍了规划大赛中最佳学习器所使用的学习技术,最后指出当前基于学习的规划技术研究领域中存在的主要问题。     

化工企业优化多智能体系统的通信机制与协调规则

分析了用于复杂化工企业生产优化的多智能体系统。采取将大部分运算时间用于各智能体自身的局部优化求解,而只花少量时间将优化任务和局部优化结果通过网络进行交换作为基本准则,提出了适合化工企业多层优化多智能体系统的通信机制与协调规则。     

分层构造方法在建筑平面布局中的应用

分层构造的自动造型方法针对方案设计过程由抽象到具体、由模糊到精确的特点，支持从概念到形状的方案设计全过程。分析了建筑平面布局设计过程中不同抽象层次和不同求解阶段的特点，应用分层构造的方法建立了一个以辅助方案设计为核心的建筑平面布局CAD实验系统。     

A robust hierarchical production planning for a capacitated two-stage production system

In this paper, we propose a robust hierarchical production planning approach for a two-stage real world capacitated production system operating in an uncertain environment. The first stage of the system produces a set of semi-finished products having relatively stable annual demands, and the second finishing stage produces finished products having highly variable weekly demands. The fixed production setup costs incurred at the first stage are considerably high. Fixed production setup costs incurred at the second stage are fairly small compared to those of the first stage. We propose an integrated hierarchical planning model, where semi-finished products from the first stage (i.e. the aggregate level) are disaggregated into finished products to be produced in the second stage (i.e. the operational level). As a result of the relatively stable demands and the high setup costs experienced at the first stage, a cyclical aggregate planning model is proposed for production planning at the upper level of the hierarchical plan. Based on this aggregate plan, a modified periodic review policy is then proposed for production planning at the lower level. Finally, a coupling plan, linking the two planning levels, is proposed to ensure the feasibility of the disaggregation process at every period.     

基于数据挖掘的弱关系社交网络及弱关系强化的研究

以新浪微博作为弱关系社交网络的代表。针对弱关系社交网络,在聚类和相关性方面做了详细分析,并对弱关系社交网络中弱关系的强化做了适当的条件假设。然后,随机选取了若干不同类型的话题微博,并获取了不同数量的样本点;对话题微博进行研究与分析,用实验证明了该假设的合理性,并找到了弱关系变强的具体条件。