王建江[1]2015年在《云层不确定条件下光学对地观测卫星调度问题研究》文中研究指明光学对地观测卫星是搭载了光学遥感器,从太空获取地面影像数据的卫星平台,在军事和商业领域都发挥着重要作用。随着航天技术的不断发展,光学对地观测卫星在军事侦察、灾害监控、城市规划等诸多领域应用越来越广泛,促使用户对地观测需求快速增长。如何对有限的卫星观测资源进行合理的统筹规划,制定优化的观测方案,是满足用户需求,提高卫星观测效率,充分发挥对地观测卫星系统效能的关键问题。光学对地观测卫星具有空间分辨率高,信息获取准确等优势,其不足之处是对云层穿透能力弱,观测效果受到云量等级、云层厚度影响很大,实际应用中存在大部分光学对地观测由于云层遮挡而失败。为了获取高质量的地面目标影像数据,光学卫星对地观测应尽量避免云层遮挡的影响。需要注意的是,云层状态不是一成不变的,而是具有很强的不确定性,想要在调度前对云层状态进行准确预测并不现实。因此,分析云层遮挡不确定性对光学卫星对地观测的影响,研究云层不确定条件下光学卫星观测调度问题对于满足用户观测需求,提高卫星观测效能具有重要意义。论文针对云层不确定条件下光学对地观测卫星调度问题,从问题建模和算法求解两方面开展研究,主要工作及创新点如下:1)提出了云层不确定条件下光学对地观测卫星“前摄式+反应式”调度框架论文深入分析云层不确定性对卫星观测的影响,以及云层不确定条件下对地观测卫星调度的特点,考虑卫星观测调度中计划制定、计划实施各个阶段,提出了“前摄式+反应式”综合调度框架。前摄式调度是基于云层预测先验信息,对云层不确定条件下光学卫星观测调度问题建模求解,生成基准观测方案。反应式调度是在基准观测方案执行过程中,针对云层不确定性引起的扰动,对观测调度方案进行修复和调整,维持观测方案的可行性并提高观测收益。该调度框架将地面站静态前摄式调度与星上自主反应式调度有机结合,既能提高卫星观测效率,最大化满足用户需求,又能维持观测方案的稳定性,有效的支持用户决策。2)设计了卫星观测前摄式调度随机期望值模型及分支定价求解算法针对云层不确定条件下光学对地观测卫星前摄式调度问题,以最大化对地观测收益的期望为目标,建立了卫星观测调度随机期望值模型。考虑随机期望值模型具有分块对角结构的特点,论文基于Dantzig-Wolfe分解原理将问题重构为一个set packing主问题和多个约束最长路径规划子问题,然后设计了分支定价算法求问题。通过仿真实验比较了分支定价算法与优化软件CPLEX的求解性能,验证了算法的有效性。3)研究了前摄式调度机会约束规划模型及分支割平面、列生成启发式求解算法针对随机期望值模型不能有效规避风险的不足,在满足一定置信水平的条件下,以最大化观测收益的下界为目标,采用机会约束规划模型对卫星前摄式调度问题建模。针对机会约束规划模型中机会概率难以计算的特点,论文采用样本近似方法将机会约束规划模型转化为便于求解的混合整数规划模型。针对基于禁忌队列的任务指派模型,设计了基于惰性约束的分支割平面算法求解问题最优解。针对卫星观测调度“流变量”模型,基于Dantzig-Wolfe分解原理,设计了列生成启发式算法求解问题近似最优解。论文设计了大量仿真实验对算法性能进行了评估,验证了算法的有效性。4)提出了卫星观测前摄式调度鲁棒模型及精确、启发式求解算法针对云层不确定条件下光学对地观测卫星前摄式调度问题,随机期望值模型和机会约束规划模型都只考虑了将单个任务调度到单个观测资源上,没有考虑到将单个任务同时调度到多个资源上,能够增加任务观测成功的可能性。因此,论文考虑将单个任务同时调度到多个资源上,建立了云层不确定条件下卫星观测前摄式调度鲁棒模型。针对鲁棒模型非线性、难以求解的特点,将问题分解为一个方案选择主问题和多个路径规划子问题,提出了一种精确求解算法。该算法采用基于标记更新思想的动态规划算法求解子问题,基于子问题的所有可行解,采用枚举算法求解主问题。针对精确算法不能求解大规模问题的不足,论文基于随机采样思想设计了5个多通道启发式求解算法。采用仿真实验验证了鲁棒模型的优越性和求解算法的有效性,并分析了不同算法求解不同规模问题的性能优劣。5)提出了卫星观测反应式调度多目标优化模型及启发式求解算法针对云层不确定性引起的扰动,同时考虑调度收益和调度稳定性,论文建立了卫星观测反应式调度多目标优化模型。针对反应式调度时效性要求高,计算资源能力有限的特点,论文设计了基于任务插入、任务撤销、任务置换等策略的高效启发式求解算法。仿真实验结果表明,反应式调度不仅能够提高调度性能,增加观测收益,还能够降低云层不确定性对用户决策的干扰。
刘涛[2]1994年在《约束满足问题:算法和复杂性》文中研究说明约束满足问题(CSPs)在数据库检索(Database Retrieval)、集成电路设计、计算机视觉、定理证明、机器人规划、机器学习等诸多研究领域具有广泛的应用背景。正是因为CSP问题是一类十分普遍的问题以及近年来引人注目的复杂性理论研究促使我们从算法和复杂性两个角度来研究它。 本文工作的重点是针对那些属于NP-Complete的CSP问题(如SAT、K-着色和Hamilton圈问题等)。我们除提出了求解此类型问题的一系列目前最有效算法之外,还讨论了此类问题的难易分布和相变规律。 局部搜索算法和基于回溯的搜索算法是求解CSP问题的两种基本算法。本文结合CSP问题的特点并借助于分治策略将它们有机地结合起来而形成一种快速、完备的求解算法—多级重排搜索算法(MSRA)。MSRA算法在与一般D-P算法的性能比较中所表现出的优势是十分明显的。此外,我们找到了N-皇后问题一个特殊解(或构造解,它区别于历史上所出现的其他解),并且分析了该问题的特殊性。 之后,本文详尽分析了MSRA算法的平均时间复杂性并且用实验结果进一步证实了所得结论。 考虑到NP-Complete理论通常只关心问题在最坏情况下的复杂性而极少为具体的问题求解算法提供有价值的指导,本文主要从实验分析的角度来研究CSP问题的难解性。由于算法要面对的是一个个具体的问题例,而我们又可将这些具体的问题例以某种方式将其划归若干问题子类,这样,我们就可以通过分析所谓问题例的“难度”(Hardness)及其分布情况来研究CSP的内在规律。在这里,问题例的“难度”指的是该问题例所属问题子类的平均复杂性最小上界。已有研究结果表明CSP问题确实存在“相变”现象,即问题例的“难度”相对于特定序参量(通常指约束条件个数与变量个数之比值)而言分布上的突变现象。这在本文中不仅得到了进一步证实而且更准确地确定了各种CSP问
钟伟才[3]2004年在《多智能体进化模型和算法研究》文中认为多智能体系统和进化计算都是多学科相融合、具有很高实用价值的研究领域,它们也已在多个领域得到了广泛的应用,但其结合是一个具有挑战性的研究课题。本文从多智能体系统和进化计算相结合的角度出发,结合数值优化、组合优化、约束满足问题、约束布局问题、组播路由问题等多个具有挑战性的实际问题进行了系统深入地研究。针对不同问题为智能体设计了不同的行为,提出了多种新的算法和实现策略,主要工作概括如下: (1) 针对数值优化问题,基于智能体对环境的感知与反作用的能力,提出了一种新的数值优化方法——多智能体遗传算法。该方法将智能体固定在网格上,而每个智能体为了增加自身能量将与其邻域展丌竞争或合作,同样智能体也可利用自身的知识进行自学习来增加能量。从理论上证明了其具有全局收敛性。实验中用10个20~10 000维的标准测试函数对算法性能进行了测试。对上万维的函数,算法都能快速找到高智能量的解,充分显示了算法具有收敛速度快,不易陷入局部极值的优越性能。 (2) 针对连续域优化问题,提出了一种在进化算法中自适应伸缩搜索空间的方法,可有效求解实际问题中无法得知全局最优解所在区间上下界有关信息的问题。并将此方法与多智能体遗传算法相结合,提出了用于线性系统逼近的多智能体遗传算法,用稳定线性系统逼近问题和不稳定线性系统逼近问题对算法性能进行了测试验证。 (3) 针对可分解的函数优化问题,提出了一种宏智能体进化模型。并将其与多智能体遗传算法相结合,提出了层次多智能体遗传算法,证明了其全局收敛性。求解了高达50 000维的Rosenbrock函数,表现出了优越的性能。 (4) 针对组合优化问题,提出了组合优化多智能体进化算法,证明了其全局收敛性。实验中用强联接、弱联接、重叠联接等各种类型的欺骗问题和具有树状等级结构的问题对算法性能进行了全面测试,并用上千维的函数研究了算法求解大规模问题的计算复杂度。 (5) 针对约束满足问题,提出了约束满足智能体进化算法。该方法根据约束满足问题的特点,设计了智能体的竞争行为与自学习行为。为了克服已有编码方式的缺点,为智能体设计了最小冲突编码。对算法的空间复杂度和收敛性进行了理论分析。实验中首先用250个不同难度的标准二元约束满足问题对算法的两个参摘要数进行了系统分析。确定了其取值范围,便于读者应用。然后用104一107个皇后的问题对算法的时间复杂度进行了研究。 (6)针对两个实际问题—约束布局优化问题和组播路由问题,提出了用多智能体进化方式求解的方法。在争束布局优化问题中,分别用5个、7个和40个待布圆问题验证了算法性能。在组播路由问题中,针对进化算法求解时延受限组播路由问题出现的搜索空间过大的问题,提出了离散域中搜索空间动态扩展的方法。借鉴自组织临界现象,为智能体设计了自组织临界行为。实验中分析了算法随目的节点数和网络节点数增长的性能变化。结果表明该算法具有搜索能力强、收敛速度快的优点,同时具有良好的扩展性。关键词:进化算法 近问题多智能体系统数值优化搜索空间动态扩展可分解函数优化问题欺骗问题等级问题 线性系统逼约束满足问题n一皇后问题最小冲突编码约束布局优化问题组播路由问题自组织临界现象西安电子科技大学博士学位论文
刘洋[4]2004年在《成像侦察卫星动态重调度模型、算法及应用研究》文中指出成像侦察卫星调度是根据用户需求,合理分配卫星系统资源,充分发挥卫星系统的能力,以满足未来战争中日益增多的图像侦察需求。卫星工作的环境复杂多变,特别是在作战的情况下,各种干扰因素将会对卫星的状态产生影响,导致卫星不可用;同时用户的需求也将随着实际需要的变化而变化。这都将使得初始调度方案不能继续执行下去,因此需要在扰动发生后对初始调度方案进行必要的调整,并且从实际应用角度出发,调整后的方案与调整前的方案的差距要最小。 成像侦察卫星是一类观测卫星,而目前多颗成像侦察卫星动态调度问题不论是在国内还是国外都是一个新的课题。本文在对成像侦察卫星的工作原理和用户需求分析的基础上,基于动态约束满足理论和方法,建立了成像侦察卫星的初始调度模型,给出了初始模型的求解算法,并针对卫星状态变化和用户需求增加这两种动态变化情况,采用反应式重调度思想,建立了动态重调度模型,并分别给出了求解算法,最后给出了应用实例,说明了本文模型和算法的应用方法。本文的主要研究内容和创新成果如下: (1) 在分析成像侦察卫星的工作原理基础上,给出了成像侦察卫星调度中的主要约束条件,并且将成像侦察卫星调度分为预处理和优化两个阶段。其中预处理过程是根据用户需求来筛选卫星系统资源,确定每个观测任务的可选资源;优化过程是根据优化目标来确定哪些观测任务将安排执行以及为这些观测任务分配相应的卫星资源和执行时间。 (2) 分析了多成像侦察卫星动态调度问题特点及其主要类型,建立了动态调度的时序约束概念模型、面向资源的约束概念模型、面向任务的约束概念模型。这是本文的一个创新点。 (3) 在调度约束条件分析和一些基本假设的基础上,本文建立了多卫星初始调度约束模型,并给出了模型求解的贪婪算法。 (4) 针对卫星资源状态变化的情况,本文建立了多成像侦察卫星动态约束满足调度模型,并设计了模型求解的启发式搜索算法。这是本文的一个主要创新点。 (5) 针对新任务到达的情况,本文建立了包含新任务的多成像侦察卫星动态约束满足调度模型,并设计了模型求解的动态回溯算法和基于局部修改的递进规划算法。这是本文的一个主要创新点。 (6) 在调度模型及算法的研究基础上,文中设计了一个应用实例,说明了本文的模型
李伟[5]2005年在《基于约束的产品配置方法和产品优化配置研究》文中提出本文研究并提出了3种产品配置方法:基于传统约束满足问题、基于动态约束满足问题以及基于产品配置本体论和约束满足问题的产品配置方法。其中基于传统约束满足问题的配置方法能直接、自然地表示产品配置知识,在产品演化时具有良好的适应性,同时能够进行直接有效的求解,适合于对小规模的可配置产品实施产品配置。而基于动态约束满足问题的产品配置方法在保留了传统约束满足问题的知识表示和求解能力及特点的基础上,能够表示动态配置知识及组成结构知识,具有更强的知识表示能力,适合于对中等规模的可配置产品实施产品配置。基于产品配置本体论和约束满足问题的配置方法是一种理想的配置方法,适用于对大规模复杂的可配置产品实施产品配置。本文以合力H2000系列叉车为例,对基于传统和动态约束满足问题的配置方法进行了仿真实验和分析,验证了所提出求解算法的正确性,并指出3种配置方法的配置求解都是NP完全的。 本文还对产品优化配置进行了深入的研究,探讨了产品优化配置的概念,并提出了3种优化配置方法:基于ICSP和MBD的交互式配置方法、基于HCP网的优化配置方法和基于分支定界法的优化配置方法。其中基于ICSP和MBD的交互配置方法能够获得准确的最优配置结果,但配置求解的计算量和用户参与的程度都很大,适用于用户对优化配置结果要求很高,同时又有充足的时间来参与配置的情况。基于HCP网的优化配置方法能够获得比较准确的最优配置结果,配置求解的计算量和用户参与的程度不高,适用于用户对优化配置结果的要求较高,同时也有一定的时间来参与配置的情况。对基于分支定界法的最优配置结果,其准确度不高于基于HCP网的最优配置结果,但配置求解的计算量和用户参与的程度最低,适用于用户既不愿意花费时间参与配置,同时对优化配置的结果要求也不高的情况。本文还以合力H2000系列叉车为例,对基于HCP网的优化配置方法以及基于ICSP和MBD的交互配置方法进行了仿真验证。
牛军霞[6]2016年在《三种代价环境下的代价敏感属性择》文中研究指明代价敏感学习是数据挖掘的研究热点,预算约束满足问题是人工智能和机器学习领域著名的问题之一。最近几年,研究最小测试代价下的属性选择问题一直是代价敏感学习中的重点。但在实际应用中,由于任何一样资源都是有限的,所以解决任何一个实际问题,都是在一定的预算约束下完成的。因此研究预算约束下的代价敏感属性选择问题在众多的应用领域有着重要的意义和广泛的应用。另外,当前代价敏感算法普遍采用静态的静态误分类代价,仅能满足实验和前瞻性的需要,不能适应同一类分布样本数量变化的数据集的分类模型的学习。针对静态误分类代价的不足,如何设计动态的误分类代价机制正受到越来越多学者的青睐。本文针对最小测试代价下的属性选择问题,预算约束下的属性选择问题和动态误分类代价下的属性选择问题进行了研究,主要取得了如下创新成果。首先,研究了最小代价下的代价敏感属性选择问题。这个最小代价只单纯考虑了测试代价这一种代价类型。本文提出了一个对数加权算法来求解最小测试代价下的代价敏感属性选择问题。实验结果表明,在大多数情况下,新算法的效果优于已有的算法。其次,研究了预算约束下的代价敏感属性选择问题。预算约束是指所能花费的最大测试代价大于最小测试代价但不大于总测试代价。这意味着,在预算约束的条件下,只能求解能够最大程度保留系统信息的属性子集。本文在预算约束的条件下,设计了一个模拟退火算法来求解代价敏感属性选择问题。实验结果表明,我们设计的算法能够在效果和效率方面获得良好的实验结果,实验结果优于已有的启发式算法和遗传算法。最后,研究了动态误分类代价机制下的代价敏感属性选择问题,并设计了四个最优误分类代价函数,四个函数可以根据少数类与多数类以及与测试代价之间的关系,形成客观的具有代表性的误分类代价空间,并对不同数据子集可以灵活地选择更合适的误分类代价,这样能更好的逼近数据集真实的误分类代价。
朱兴军[7]2009年在《约束求解的推理技术研究》文中研究指明本文主要工作是研究与改进约束求解中的推理技术。具体内容包括:提出基于最先失败原则的约束传播算法FFP-AC;研究相容性技术传播级别,提出singleton子问题弧相容概念和相应算法;提出并证明多值传播定理,提出多值传播的相容性算法SAC-MP;给出完全独立相容性概念(entirety singleton consistency),提出基于完全独立相容的推理算法;对预处理技术进行改进和信息抽取,提出两种用于搜索过程中的新算法Pre-AC和Pre-AC*,并嵌入到BT框架中,形成新的搜索算法BT+MPAC和BT+MPAC*;为了不耗用额外空间,提出一种基于预处理技术的值启发式求解算法MAC_MPV;改进双向singleton弧相容算法,提出BiSAC-2、BiSAC-DF和BiSAC-DP算法,分别证明其空间和最坏、最优时间复杂度,并对正确性和完备性给出论证。将所有改进算法和技术,在“明月”求解平台中实现,结果表明,提出的新算法效率明显优于目前流行算法。
杜江珊[8]2017年在《基于减少遍历次数的表约束算法研究》文中认为约束程序的研究是人工智能领域的一个重要研究分支,它是一个良好、通用的框架,提供了解决多种现实问题的高效模型和算法,并广泛应用于资源分配、生物信息、规划调度等诸多领域。约束程序将问题抽象成由约束集、变量集、论域集组成的约束模型,再利用回溯搜索和约束传播两个主要技术对约束网络进行求解,最终得到问题的解决方案。相容性技术作为在约束传播中,应用最广泛、高效、成功的技术方法,是解决约束满足问题的核心和关键,它能够在约束问题的求解过程中,对一个约束消除局部不一致值后,再通过具有共同变量的约束,进行约束传递,删除不满足解决方案的值,实现全局一致,达到极大地简化问题规模、提高求解效率的作用。广义弧相容技术被认为是解决非二元约束满足问题的有效方法,简单表格缩减算法STR及其优化算法STR2,在实践中呈现出良好的性能,是用于在正表约束上实施广义弧相容技术的先进过滤技术。近年来,学者们提出了一种新的约束表示形式——对偶表,随之,基于对偶表的相容性算法STR3被提出,它利用了新的求解优化方式,通过放弃不相关的元组来减少遍历次数从而减少检索的方式进行优化,是一种路径最优算法。在不同结构特点的CSP实例中,STR2算法和STR3算法呈现出各自的优势。基于放弃遍历不相关元组的方式,目前只能应用于正表约束之上,不能直接运用到负表,因此,本文受STR3算法的启发,对负表约束算法STR-N进行优化改进,提出了基于负表约束的相容性算法STRN3,它同样是通过放弃遍历不相关元组的方式进行优化改进的。由于在正表中,保存支持元组,表中有效元组即为值的支持,在负表中,保存冲突元组,值的支持不可直接遍历约束表得到,因此,无论STR-N算法还是STRN3算法,它们寻找值支持的方式均相对复杂。STRN3算法最大的优化点是其寻找值支持的方式,相对于原负表约束算法STR-N,在每次约束传递中,均需要遍历所有有效元组,才可通过计算冲突元组,确定论域中值存在或不存在支持,STRN3算法不必再每次均遍历全部有效元组,而是通过上次约束传递所遍历的元组基础上,继续寻找最小有效支持区间,从而判断值是否存在支持,通过这种方式,在整个约束满足问题求解的过程中,每个对偶表仅最多遍历一次,减少了遍历次数,达到优化算法,提高效率的目的。实验结果表明,在搜索过程中,表的平均大小没有被大幅度减少的情况下,STRN3算法较STR-N算法有竞争力;在冲突元组较少的约束网络中,STRN3算法较STR3算法有竞争力。
贺仁杰[9]2004年在《成像侦察卫星调度问题研究》文中研究指明成像侦察卫星调度是根据用户需求,合理分配卫星系统资源,充分发挥卫星系统的能力,以满足未来战争中日益增多的图像需求。成像侦察卫星实际是一种对地观测卫星,目前多颗观测卫星调度问题不论是在国外还是国内都是一个崭新的课题。于是,开展成像侦察卫星调度问题的研究,不仅可以从理论探讨多颗观测卫星调度方法,也可以满足成像侦察卫星应用中的实际需求。在对成像侦察卫星的工作原理和用户需求分析的基础上,本文建立了成像侦察卫星的调度模型,给出了相应的模型求解算法,并最终设计和实现了一个资源调度软件系统。本文的主要研究内容和创新成果如下: 首先,在分析成像侦察卫星的工作原理基础上,给出了成像侦察卫星调度中的主要约束条件,并且将成像侦察卫星调度分为预处理和优化两个阶段。其中预处理过程是根据用户需求来筛选卫星系统资源,确定每个观测任务的可选资源;优化过程是根据优化目标来确定哪些观测任务将安排执行以及为这些观测任务分配相应的资源和执行时间。通过采用调度预处理过程,可以事先筛选不可能完成的任务,降低需要调度的任务的数量,同时可以针对任务给出失败的原因。这是本文的一个主要创新点。 其次,在调度约束条件分析和一些基本假设的基础上,本文建立了成像侦察卫星调度问题两种调度模型:约束满足问题模型和混合整数规划模型,并给出了相应的的禁忌搜索和列生成算法。这是本文研究的另一个主要创新点。 在禁忌搜索算法研究中,本文给出了一种初始解生成算法,提出了一种结合约束满足和邻域搜索技术的禁忌搜索算法,并且给出了针对多卫星调度问题的几种特殊的邻域结构和邻域的可行性判断算法。为了降低邻域交换中移动可行性判断的计算时间,本文提出了一种多时间窗口条件下任务的后移空余时间的概念,用来计算在不违反其他任务时间约束的情况下任务的最大后移时间,并在此基础上计算活动在插入活动队列时的有效性。 在列生成法算法研究中,本文将多卫星调度问题分解为一个集合分割主问题和一个单卫星调度子问题,通过循环迭代来求解调度模型。在单卫星调度子问题求解中,论文将该问题转换为一个具有时间窗口约束的最短路问题,并给出了相应的求解算法。该最短路算法具有一般性,可以对存在负权回路图的最短路进行求解。 最后,在调度模型及算法的研究基础上,文中设计和实现了成像侦察卫星调度的软件系统。同国外类似系统相比较,本文建立的软件系统能对卫星资源进行可视化管理,通过调度预处理模块能自动分析任务的可以满足其要求的卫星系统资源,提前筛选不可能完成的任务,并给出具体的失败原因。此外,本文研究的软件系统能够提供多种图形方式展现调度方案,并完全集成了STK软件的三维仿真演示模块,能够有针对性的对卫星侦察监视任务进行三维仿真演示,使用户可以很方便对侦察任务进行分析。
王冲[10]2011年在《基于Agent的对地观测卫星分布式协同任务规划研究》文中认为对地观测卫星(Earth Observing Satellites, EOSs)利用星载遥感器从太空获取地表信息,具有覆盖区域广、持续时间长、不受空域国界限制等诸多优势,在军事侦察、防灾减灾、环境保护等领域具有广泛的应用,已成为当前遥感信息获取的重要手段。随着当前在轨卫星数量的不断增加以及卫星智能水平的逐渐提升,面对日益复杂而繁多的目标观测请求,如何有效地协同规划调度多颗卫星完成观测任务,提高观测效益,成为近年来卫星应用领域研究的重点之一,其在军事和民用方面具有重要的应用价值和现实意义。本文立足于协同,重点针对不同任务规划环境的卫星分布式协同任务规划问题展开研究。主要工作及创新点如下:(1)分析了卫星分布式协同任务规划问题的要素,建立了卫星协同任务规划问题的分布式求解框架从基本的规划问题出发,深入分析了卫星协同任务规划所涉及的关键要素,分别建立了卫星资源、卫星能力、观测目标、网络通信在内的各组成要素的形式化模型;分析了卫星协同任务规划问题所具有的系统分散性、观测资源协作性、网络拓扑结构的复杂性以及环境不确定性等特点;基于单星层次化的物理结构,建立卫星自主规划的逻辑流程;进而建立了卫星协同任务规划的分布式系统结构,通过关键问题分解,提炼出信息实时获取条件下的多星协同规划、支持通信延迟的多星协同优化决策和面向动态任务的多星协同任务分配三个相互衔接的关键子问题。(2)针对信息实时获取条件下的卫星协同任务规划问题,建立了卫星分布式约束优化模型,提出了基于Nash最优与合作协同进化相结合的分布式优化迭代求解方法在分析多星之间的分布式协同结构和卫星约束的基础上,建立了基于分布式约束优化(DCOP)的卫星分布式协同任务规划模型。在假定在信息实时获取的基础上,基于“分治-合作”策略提出了Nash最优与合作协同进化相结合的卫星分布式迭代求解算法;采用k近邻方法分解观测目标集合,每颗卫星能够通过网络获取信息进行充分协同。仿真实验结果表明:所提出的分布式合作协同进化算法对于不同规模和分布的算例具有良好的优化性和散布性;本文算法虽然较集中式方法在整体观测效益上存在一定差异,但分布式方法能够有效地减少优化问题的规模,从而缩短优化计算的时间,降低计算的复杂性,对于提高卫星协同规划能力具有一定现实可行性。(3)针对通信延迟条件下的卫星协同优化决策问题,建立了卫星协同优化决策模型,提出了适应延迟通信的统一处理策略,设计了卫星优化策略的搜索方法构造了基于联合时序有向无圈图的多星协同优化决策环境;针对卫星协同优化决策系统动态性解耦的特点,研究了基于分布式部分可见马尔可夫决策过程(DEC-POMDP)的多星分布式系统建模方法;在此框架下,将集中式优化问题转化为多颗卫星之间有限独立的分布式优化决策问题;随后讨论了卫星分布式协同优化决策算法,分析了不同通信延迟条件对协同优化决策的影响,并给出了统一的通信延迟处理策略;提出了改进的快速模拟退火算法搜索卫星近似优化观测策略。仿真实验表明:改进的快速模拟退火算法相对于现有的模拟退火算法在观测策略的搜索效率和搜索质量上均有一定提升;协同近似策略迭代搜索算法在通信延迟的情况下性能优于基于值迭代算法,能够有效提高卫星协同优化决策系统对于通信延迟的适应性。(4)建立了一种面向动态任务的多星混合学习框架,提出了任务不变条件下的任务分配策略算法,提出了任务变化条件下的增量策略迁移学习算法首先建立了面向动态任务的卫星协同分配决策模型;针对求解多星动态任务协同分配问题中的规划质量和求解效率的需求,注意到动态任务是对历史观测目标集合的增量式扩展关系,提出了一个“优化策略-迁移策略”的混合学习框架;在此框架下,分别针对两个核心问题进行研究:当任务不发生变化时,基于多智能体强化学习的思想提出了MACoNEAT算法,迭代搜索协同规划学习策略;当出现新的观测目标请求时,提出了增量任务迁移学习算法,通过策略个体之间的相似性将历史规划学习策略迁移至至当前的解空间。仿真实验结果表明:当任务不变时,MACoNEAT算法在增加一定计算时间的前提下较其它分布式协同算法取得了更好的观测效益。当出现新的观测任务请求时,混合学习算法在保证优化质量的前提下,可以加快算法的计算收敛速度,保证了系统对随机出现的观测任务请求具有良好的适应性。
参考文献:
[1]. 云层不确定条件下光学对地观测卫星调度问题研究[D]. 王建江. 国防科学技术大学. 2015
[2]. 约束满足问题:算法和复杂性[D]. 刘涛. 中国科学院研究生院(计算技术研究所). 1994
[3]. 多智能体进化模型和算法研究[D]. 钟伟才. 西安电子科技大学. 2004
[4]. 成像侦察卫星动态重调度模型、算法及应用研究[D]. 刘洋. 国防科学技术大学. 2004
[5]. 基于约束的产品配置方法和产品优化配置研究[D]. 李伟. 合肥工业大学. 2005
[6]. 三种代价环境下的代价敏感属性择[D]. 牛军霞. 闽南师范大学. 2016
[7]. 约束求解的推理技术研究[D]. 朱兴军. 吉林大学. 2009
[8]. 基于减少遍历次数的表约束算法研究[D]. 杜江珊. 吉林大学. 2017
[9]. 成像侦察卫星调度问题研究[D]. 贺仁杰. 国防科学技术大学. 2004
[10]. 基于Agent的对地观测卫星分布式协同任务规划研究[D]. 王冲. 国防科学技术大学. 2011
标签:计算机软件及计算机应用论文; 智能算法论文; 协同软件论文; 测试模型论文; 优化策略论文; 资源卫星论文; 时间计算论文; 产品属性论文; 动态模型论文; 协同设计论文; 产品方案论文; 算法论文;