对不确定规划中观测约简的进一步研究

从3个方面改进了不确定规划(non-deterministic planning,简称NDP)中的观测约简:一是如何找最小观测集合(minimal observation set,简称MOS),二是如何在观测代价不均等时找最优观测集合(optimal observation set,简称OOS),三是如何找到容错的OOS.通过MOS问题和图论中的最小覆盖集问题(minimal set cover,简称MSC)的类似性,可证MOS是NP难的问题,还可参考MSC算法得出时间复杂性不超过O(2mm2)且不低于Ω(2m-1)的算法,其中m是观测的个数.通过使用整数规划(integer programming,简称IP)技术,可找到OOS以及容错的OOS.可以证明,上述算法能够保证找到解,并且能够保证解的最优性.

基于不确定规划的产品拆卸序列规划

分析了产品拆卸序列规划中的不确定性,在基于混合图的产品拆卸模型的基础上,将产品拆卸序列规划转化为一类不确定规划问题。以机会约束规划模型为基础,使用模拟退火算法,给出了基于不确定规划的产品拆卸序列规划求解流程和算法。最后,通过一个简化的计算机主机箱实例说明了方法的有效性及优越性。

不确定规划的研究现状及其发展前景

本文简要介绍不确定规划理论、算法以及应用研究的现状 ,描绘了不确定规划理论的基本框架。首先介绍处理各种不确定性的数学工具 ;接着阐述不确定规划的建模机理与求解方法 ;然后提出了不确定规划中值得进一步研究的一些问题 ;

基于模糊路段流量的OD反推的不确定规划模型与算法研究

考虑调查数据存在的偏差,将路段流量视为一个模糊数,在此基础上构造一个OD反推的双层规划模型,其上层为一模糊期望值模型,即以路段计算流量与实测流量的偏差模糊期望值最小为目标;下层为用户平衡分配模型。为求解该模型,将模糊模拟、二分法、人工神经网络以及遗传算法相结合,给出一种混合智能算法及其步骤。通过一个简单的路网进行仿真试验,最后对这一新方法的有效性进行检验,并对结果进行了分析。

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

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

模糊灰色智能优化算法在生产计划不确定规划中的应用

在模糊和灰色两类不确定因素并存条件下定义了模糊灰色变量,基于模糊灰色变量的可信性和机会测度建立了生产计划不确定规划模型。采用模糊灰色模拟技术对不确定目标函数和不确定约束产生输入输出数据,用产生的输入输出数据训练神经网络逼近不确定函数,通过基于遗传算法的混合智能优化算法得出最优解,并用实例说明了本模型和算法的有效性。

不确定规划模型及其算法研究

分析并建立不确定规划的期望值处理模型,机会测度分析模型,极大化事件实现机会的数学模型。给出不确定环境下多层规划的数学模型,不确定Monte-Carlo规划,不确定多属性决策区间熵权规划以及不确定结构规划的神经网络优化模型。并给出不确定规划的混合智能算法。不确定复杂问题决策系统表象和实质各异,有效分析、评价的方式和方法多样,定量的和科学的描述与解析既是问题的深入的前提,也是复杂系统得以优化的保障。

不确定规划中一种观察信息高效约简算法

在不确定规划中,可通过观察周围的信息来区分多个状态,但周围的观察信息较多,因此如何从大量的观察信息中筛选必须的信息非常重要。以往算法是在直接搜索过程中增加一些剪枝条件来达到优化的目的,存在一定的局限性。在对观察信息约简研究中,为提高搜索效率,设计一种高效的不确定规划中观察信息约简算法。该算法将规划问题转化为求解0-1矩阵的覆盖问题,使用数据结构十字链表来表示0-1矩阵,通过维护十字链表并采用启发式函数来加速求解一个最小观察变量集。实验结果表明,该算法不仅能够找最小观察变量集,而且运行速度超过同类算法。

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

在不确定规划领域中,不确定状态转移系统求规划解常常会搜索大量无用的状态和动作,造成冗余计算。获得不确定状态转移系统的状态可达关系可以避免无用搜索、减少冗余计算,为系统提供引导信息。以非循环可达关系为基础,定义矩阵的计算规则,使用系统的邻接矩阵来计算可达矩阵。同时首次提出了循环可达关系的分类、二可达关系等,并设计了求循环可达关系的算法,且以实例证明了算法的有效性和正确性。在不确定规划中获得状态之间的可达性关系,在求规划解的过程中可以删除大量无用的状态动作序偶,降低问题规模,提高求解规划问题的效率。

不确定规划中可达关系的快速求解算法

在不确定规划领域中,通常需要在同一个不确定状态转移系统中解决多个规划问题,如果能得到不确定规划中状态之间的可达关系即可方便求解该规划问题,然而现有矩阵乘法求解可达关系时存在算法复杂度高的问题。为此,设计一种快速求解不确定规划中状态之间可达关系的算法,将确定动作和不确定动作区分处理,先求解所有确定动作的可达关系,再采用链表和队列求解不确定动作的可达关系。实验结果表明,与矩阵乘法相比,该算法能得到更全面的可达关系,且求解效率更高。

不确定规划领域中带权值的观察信息约简

现实的规划问题中,观察信息的获取所需的代价是不同的,并且在规划解执行过程中,并非所有的观察信息都是有意义的,因此为了减少执行过程中的开销而对大量的带权值的观察信息进行约简就显得十分重要。首次针对带权值的观察信息约简问题做出研究,定义了带权值的最优观察集的概念,设计了SOWOS算法。该算法找出所有需要区分的状态对,用贪心的思想使搜索按指定顺序选择观察变量,并在搜索的过程中增加剪枝,减少了大量不必要的搜索,最终求得总花费最小的观察集,达到了减少执行成本的目的。实验结果表明,SOWOS算法可以高效地求得带权值的最优观察集,对减少规划执行中的开销贡献明显。

基于不确定规划的遗传算法PID控制器在矿井输送机中的应用

矿井输送机运行过程具有非线性特性和不确定性等因素,传统自适应PID控制算法难以满足控制要求。针对这一问题,提出了一种基于不确定规划遗传算法的PID参数整定方法。并对PID控制器加一个误差约束,运用模糊随机模拟方法检验染色体的可行性,并计算目标函数值,这样可有效防止超调,并尽可能减小误差。实验结果表明,这种PID控制器在矿井输送机中达到了很好的效果。

供应链网络设计不确定规划模型及应用

利用不确定规划,根据决策者的要求,对供应链网络设计问题进行建模。并采用由随机模拟、模糊模拟以及例子群算法相结合的混合智能算法来求解,最后给出了生活中的实际例子来说明模型和算法的有效性。

不确定规划中的多Agent带权值强规化算法

在智能规划领域中,以往对不确定规划问题的研究主要集中于单个Agent,而对多Agent规划的研究则侧重于确定规划。针对该问题,提出基于多Agent的带权值不确定规划问题,对所求解的强规划解,设计使其所需动作权值总和近似最小的算法。根据基于模型检测的强规划分层方法,对每个Agent进行强规划分层,合并所有Agent的分层信息,并在合并的过程中得到同层状态之间的冲突表。在保证冲突最小的情况下,以最小动作权值优先的贪心方法,求出强规划解。实验结果表明,该算法能较快地求解出使所选择的动作权值总和近似最小的强规划解。

基于不确定规划理论的配电网优化规划

随着分布式电源(distributed generation,DG)发电技术越来越多地渗透到电力系统中,给配电网规划带来了一定的冲击和影响。为此,利用不确定规划理论,对配电网中风力发电输出功率、光伏发电输出功率以及负荷大小的不确定性进行了模糊模拟,并建立了基于该理论的配电网网架优化模型。采用了基于树形结构编码的改进单亲遗传算法对模型进行求解。最后,通过对16节点配电网络算例的仿真分析,验证了基于不确定规划理论网架规划模型的可行性和改进单亲遗传算法的有效性。

顺序价值迭代算法求解不确定规划

基于Markov决策过程(MDP)的规划方法可以处理多种不确定规划问题,价值迭代算法(VI)是求解MDP的经典算法,但VI需要计算更新每个状态的值,求解过程相当缓慢。在分析了MDP状态图本身的因果依赖关系的基础上,提出一种改进的价值迭代算法,称为顺序价值迭代算法(SVI)。它先将一个MDP分解成多个拓扑有序的强连通分量,然后应用价值迭代算法顺序求解各个分量,这样处理可以避免对大量无用状态的计算并使得可用状态排成拓扑序列。对比实验结果证明了该算法的有效性及优异性能。

不确定凸函数及其在不确定规划中的应用

借助实函数的凸性给出了不确定函数的几种广义凸性的定义并研究了它们之间的关系。证明了不确定函数期望算子的保序性,并由此证明了凸(拟凸、严格凸及弱凸)的不确定函数的期望也是凸(拟凸、严格凸及弱凸)的实函数。最后,讨论了带有不确定函数的几种不确定规划的解的存在性及其性质。

不确定规划中循环可达状态信息的维护

动态环境下,动作执行的不确定性会因外部因素存在变动,因此将导致不确定系统中的状态可达关系可能发生改变。为解答这一问题,论文对信息传递法中状态之间可达关系的更新方式进行改进,提出一种新的状态可达关系的维护算法。该算法将变更的状态之间可达关系与原可达矩阵对比,利用邻接矩阵中对应可达信息对变更后状态的可达信息进行修改,然后通过状态之间信息传递,求解不确定系统中局部状态可达关系,从而避免了更新过程中的重复计算。实验结果表明,该方法在运算时间上要优于重新利用信息传递法来维护系统的状态可达关系。

机组恢复问题的不确定规划方法

对航空公司来说应急航班调度问题是最具挑战性的活动之一.机组配对是规划中十分重要的一环.一个以延误时间为不确定变量的机组恢复不确定规划模型,在机组规划被扰乱时,可以降低航空公司的成本.该模型的目标为最小化旅客失望率,同时将估计延误成本作为机会约束条件.运用不确定理论,将该模型转化为一个等价的确定性模型.并采用列生成算法解决该模型.该模型和算法有较强的实用性.

应急海运路径的不确定规划模型

不确定规划广泛用于处理不确定环境下的优化问题,比如车辆调度问题、网络优化问题、作业排序问题等。本文在不确定理论框架下,建立一个应急海运路径运输的不确定规划模型,同时考虑路径行进时间、风险和约束变量的置信水平,利用Pareto最优解的遗传算法进行求解,最后通过两个数值实例验证了该模型的有效性和实用性。