胞映射算法的开发和在动力学、控制和优化中的应用

发布时间：2018-01-09 07:02

本文关键词：胞映射算法的开发和在动力学、控制和优化中的应用　出处：《天津大学》2015年博士论文　论文类型：学位论文

【摘要】：胞映射方法最早由著名力学家徐皆苏先生于上世纪八十年代提出。该方法最初被用来解决非线性动力学的全局问题。胞映射方法的基本思想是通过离散动力学系统的状态空间,将原有连续的动力学轨迹转化成离散的胞对胞映射。一步胞映射的构造实际是通过短时积分动力学系统而得到的。通过构造状态空间中所有胞的一步映射,可以近似得到以任何胞作为初始条件的胞空间轨迹。进而可以通过分析某条轨迹的走向来判断该轨迹上所有胞的动力学行为和性质。该方法的优势在于,一旦确立了所有的胞的短时映射关系,系统的分析就无需再进行方程的积分。也就是说,相比于通常的点空间的分析,胞映射保留了积分轨迹上的所有时刻的信息。因此,和连续点空间的分析相比,胞映射能够节省大量的计算时间。传统的胞映射分为简单胞映射和广义胞映射。简单胞映射在构造短时映射时,通过从原像胞的中心点积分动力学方程,得到像点的位置,进而得到像点所在像胞的位置,从而构造短时一步胞映射。简单胞映射的特点是构造方法简单,分析思路清晰,容易编程实现。其分析的流程类似图论算法里的深度最优搜索策略,即对某一个正在处理的胞进行遍历,直到该轨迹遇到自循环结构或合并到其他已处理过的胞中。通过对胞进行分类,简单胞映射可得到诸如吸引子和吸引域等动力学信息。虽然简单胞映射在算法实现和深层逻辑上具有很强的优势性,但是其计算精度和计算量和胞的大小有着紧密的关系。鉴于简单胞映射仅接受一个像胞,为保证胞轨迹和真实连续轨迹的较小误差,胞的尺寸要尽可能的小。这样就增加的计算的复杂度和计算量。为了避免简单胞映射的缺陷,能够接受多个像胞的广义胞映射被发明出来。广义胞映射在构造一步映射时,在原像胞里采用多个初始点进行积分。其像胞为若干像点落入的胞中。换句话说,广义胞映射收集了若干条短时积分轨迹的信息,其像胞的个数也不唯一。因此,广义胞映射的储存需要用到有向图和稀疏矩阵的概念。广义胞映射的分析方法可以借助马尔科夫链和图论分析。这两个学科在离散数学和计算机科学已经有了成熟的发展和广泛的应用。和简单胞映射不同的是,在广义胞映射框架下,一个胞可能能够演化到不同的吸引域,演化到不同域的概率也可以通过简单的采样方法进行计算。这样就为随机系统的分析搭建了一个很好的框架。因此,除了分析确定性系统外,广义胞映射还能够有效分析随机系统的动力学行为。特别是当结合了有着解析解的短时高斯解后,广义胞映射能够准确快速地给出具有强非线性的随机系统稳态响应的概率密度函数。针对低维系统的模拟已经证明,广义胞映射的结果和大量蒙特卡洛模拟的结果吻合度相当高。值得一提的是,对于非线性系统,一旦通过广义胞映射确定了其一步转移矩阵,也就是广义胞映射的稀疏矩阵表达,系统的所有动力学信息,包括吸引子、吸引域、吸引盆边界乃至稳态概率密度分布,都可以通过一次分析广义胞映射矩阵而得到。这是其他现有方法无法达到的优势。随着胞映射方法在动力学系统中的大量成功应用,针对胞映射方法的改进也逐步被提出来,其中值得一提的一个改进是插值胞映射。严格来说,插值胞映射已经不属于离散数学处理的范畴。其基本思想虽然仍是将动力学系统状态空间离散成网格,但其分析的主要思路是通过每个胞网格角点的精确积分信息来插值拟合胞内任意一点的映射像点。该做法和有限元方法中的插值函数思路非常接近。插值胞映射能够在一定程度上克服传统胞映射离散误差的劣势,在提高求解精度上有一定的优势。但由于其插值格式仅限于二维平面问题,且其插值格式难以推广到更高维的问题,插值胞映射在八十年代后期到九十年代初逐步淡出研究者的视线。在本论文中,我们利用插值胞映射的思路,提出一种能适应任何维度的插值格式,并证明了所提插值格式的精度可以达到局部二阶近似。我们利用插值胞映射的思想对所求结果进行进一步的细化和精度提升。值得注意的是,插值胞映射仅是作为后处理的方法。在求解过程中,我们还是应用简单或者广义胞映射进行全局搜索。另一个针对胞映射的改进是面向集合的细分算法。该思路针对全局不变集搜索。其基本思想是通过由低分辨率到高分辨率的胞空间迭代逐步提高解的精确性。非线性动力学问题的全局不变集合通常仅占状态空间很小的一部分。因此,若仅要得到不变集,则没有必要对所有胞进行计算和处理。面向集合的细分算法正是基于这点,提出在不同分辨率胞空间下搜索的策略。初始所搜在粗胞下进行,当找到覆盖可能出现解的胞集合后,算法只处理这些覆盖集胞,所有的暂态胞则被丢掉。针对这些覆盖集合胞进行细分后,同样的搜索策略被应用在分辨率更高的小胞上。该过程如此反复,直到胞空间足够满足收敛条件。为保证每次迭代覆盖集能够全部找到,细分算法采用了一步逆映射指导搜索。严格的数学证明显示该策略能够最终收敛到真实的不变集合解。从胞映射被发明以来,在相当长的一段时间里,胞映射能解决的问题都局限在低维动力学系统中。尽管胞映射和其各种改进能够有效揭示低维动力学的复杂动力学行为,但随着动力学领域研究的发展和深入,人们需要了解越来越多的高维系统。维度诅咒是导致针对高维问题一直没有合适方法出现的重要瓶颈。在其他应用领域,例如优化和机器学习,基于随机搜索的启发式算法尽管能够在一定程度上避免维度诅咒,但其算法的适用性、收敛性、全局性都还处于一个未知的探索阶段。如何利用现有算法解决更高维的问题成为了胞映射算法向前发展必须要解决的问题。在本论文中,我们尝试通过并行计算的思路拓展胞映射的应用空间。由于胞映射在构造一步映射时任意两个胞的处理是相互独立的,所以胞映射在构造阶段可以针对一大批胞进行批量处理,也就是平行运算。基于该事实,我们应用显示处理单元(gpu)对胞映射算法进行加速。gpu由于其多核的特性已经被广泛应用在多个行业,如天气预报、金融分析、有限元计算等的并行计算和模拟中。显卡生产和制造的先驱企业英伟达公司于近些年开发了gpu编程的通用平台cuda。cuda平台能集成当今流行的计算机语言,通过将代码转化为在gpu上可执行的命令,从而使得gpu编程变得灵活和方便。在本论文中,我们应用cudac/c++环境对平行胞映射算法进行编程实现。应该指出的是,论文中所报道的加速效果和所进行计算的显卡非常相关,同样的代码在更好更快的新一代显卡上能够获得更多的加速。本论文基于胞映射的框架,提出了若干基于离散胞空间的算法来解决多目标优化、非线性动力学、零点搜索和稳定边界搜索等问题。平行运算贯穿了所有所提胞映射算法中。针对具体的应用,所提胞映射的局部构造和全局搜索策略也有所不同。在本文中,我们通过构造驱动胞对胞映射的底层动力学来将不同的应用统一在胞空间意义下的框架下。下面对本论文中胞映射方法的具体应用做简要介绍:多目标优化广泛存在于各种工程优化问题中。多目标优化通常考虑若干相互制约的优化指标。和传统的单目标优化不同,多目标优化的解不再在参数空间中的点,而是一个集合,称为帕累托集合。帕累托集合里的任意两个点满足非劣性,也就是无法找到一个解在多目标意义下比另一个解更优。多目标优化往往能给出一个较宽的设计范围,因此在实际工程中,多目标优化设计具有很强的优势。解决多目标优化问题的关键在于能否找到全局的帕累托集合。传统的目标加权虽然能将多目标问题转为单目标,但其权重参数的选择往往基于经验。随着演化算法的逐步兴起,基于生物种群演化的多目标优化启发式算法逐渐得到重视。演化算法的优势在于通过模拟生物种群的演化过程,能够用较少的计算量得到尽可能覆盖全局的非劣解集。其缺点是无法保证算法的收敛性和全局性。此外,演化算法是一种基于随机搜索的算法,在应用中通常需要多次运行,通过统计的办法确认多目标优化解集在参数空间的位置。基于胞映射的全局搜索能力,我们提出了一种简单胞映射混合算法来有效解决多目标优化的全局问题。我们混合了有梯度和无梯度的局部搜索策略。通过面向集合细分算法逐步提高解的精确性。其中,无梯度算法首先应用在较粗的胞中,通过比较某一个胞的相邻胞确定胞映射的像胞。注意该搜索策略仅为零阶精度,因此仅限于在精度要求较低的前提下进行计算。但该搜索策略速度较快,计算代价低,所以我们用它来初步确认覆盖集合的位置。一旦覆盖集确认,我们应用细分的胞空间,通过有梯度的搜索策略构造一步简单胞映射,进而对解集的更细结构进行捕捉。前期的研究通过一系列的标准问题证明了该算法的有效性和准确性。在本论文中,我们应用这种算法来解决多目标全状态反馈和含时滞pid控制器的优化设计。我们针对线性和非线性系统分别进行了控制器设计。将若干时域指标,诸如追踪控制中的超调、响应时间、积分误差等,设为多目标优化指标。对于含时滞的非线性系统,将局部线性化的闭环系统稳定性作为优化约束。应用所提混合算法,求得不同控制任务下控制器的多目标优化设计。数值模拟显示,所提多目标优化算法能够对控制器进行时域定量的优化设计。闭环系统的时域信号显示,多目标优化策略所得追踪响应呈一个紧凑的带状分布。胞映射算法搜索出的帕累托前沿,即帕累托集合的像,有着精细的内部结构。帕累托前沿能够很好的反映优化指标之间矛盾的本质。作为胞映射应用最广泛的领域,非线性动力学的全局分析一直是一个热门话题。在本文中,作者尝试使用并行计算、插值胞映射和面向集合细分算法将原有的简单胞映射和广义胞映射算法进行推广。针对不同分析,我们提出了两种基于胞空间的分析思路:其一,搜索状态空间中全局不变集合。不变集一般包括稳定平衡点、极限环、概周期解及混沌吸引子。所搜全局不变集,特别是有共存现象的非线性系统,对于认识非线性系统长期演化状态有着重要的意义。我们利用广义胞映射和细分算法,对覆盖集首先进行粗略估计。当细分进行到一定程度时,我们应用高维插值格式,将所求得的胞空间解作为已知数据库,对不变集的更细结构通过插值胞映射进行提取。所提插值格式的精度经证明可达到局部二阶精度。其二,针对非线性系统的全局分析,包括暂态胞的分类、吸引域标示和吸引边界的搜索。这类分析需要构造胞空间内所有胞的广义胞映射。由于我们对所有胞的性质和动力学行为都要进行研究,细分算法将不再适用。所有动力学信息的提取都将在较高分辨率的胞空间下一步转移矩阵确认后一次提取出来。显而易见的是,构造一步转移矩阵将占据全局分析的绝大部分计算资源和计算时间,因此,并行计算在这个阶段的引入将非常必要。针对所提出的胞映射分析框架,我们通过若干例子进行了验证。通过一个低维的隐式动力学系统验证了并行计算的显著加速效果。在不同胞空间划分下研究了不同计算量下并行计算的加速效果。通过中低维系统对胞映射全局分析的框架进行了验证。通过高维洛伦兹系统的不变集搜索,提出了若干高维动力学系统分析的困难和解决方案。作为非线性系统分析的前处理部分,搜索非线性代数方程的全局零解问题是关键。很多非线性问题的分析,例如分叉分析、稳定点搜索、稳定边界搜索等都可以转化为代数方程找零的形式。应用胞映射和面向集合混合算法,我们提出了一种类似搜索不变集的搜索算法。和非线性动力学分析不同的是,找零问题没有显式的动力学系统可以构造胞对胞映射。因此,我们需要根据找零问题的特点构造新的底层动力学。本文通过牛顿梯度方法构造找零问题胞映射的底层动力学,通过点对点映射将牛顿梯度法作用在胞空间中。应用简单和广义胞映射的混合算法,首先找到底层动力学的不变集,即零解的覆盖集。进而通过在覆盖集上的向前简单胞映射搜索,细分所求解集,使之达到求解精度。针对胞映射引入的离散误差,我们通过聚类分析,找出独立的胞集合。在某一胞集合上再次应用点空间精确的搜索找出高精度的零解。通过不同维度的例子,我们验证了算法的计算效率和精确性。通过计算我们发现,高维代数方程的零解可能显示出复杂的几何形状。通过分析方程的全局零解的稳定性,可以了解非线性系统平衡点的局部拓扑性质。由非线性系统理论可知,经过鞍点的所有稳定流行构成划分两个稳定平衡点的稳定边界。基于非线性系统的这个性质,我们提出了一种基于简单胞映射的稳定边界搜索算法。该算法从非线性系统的势能函数出发,首先利用找零算法求出非线性系统的全局平衡点并给出稳定性分析,然后应用简单胞映射,将各暂态胞进行归类。这样便求得稳定平衡点的吸引盆。从鞍点出发,通过辨识鞍点附近不同的吸引域,通过延拓的方法找出不同稳定点之间的稳定边界。进而完成对非线性系统稳定边界的搜索。该算法最大的计算量发生在简单胞映射构造的阶段,我们利用并行计算,显著提高了求解速度。计算表明,一个具有百万量级胞数的计算任务,仅需要五秒左右便可求解完毕。论文结尾给出了胞映射算法在其他领域的应用,其中包括滑模控制的多目标优化设计、参数不确定系统的鲁棒性设计、结构的多目标优化设计、多目标路径规划等。这些应用也都适合平行运算。此外,给出了胞映射算法仍需要研究的问题,其中包括胞空间划分策略、最优采样、胞映射与模式识别和机器学习的结合等。
[Abstract]:......
【学位授予单位】：天津大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：O19;O231

【相似文献】