论文部分内容阅读
为了解决软件复杂性危机,学术界和产业界提出了自主计算的概念.自主计算的核心是使计算机系统具有自管理能力,包括自配置、自优化、自恢复和自保护.虽然自主计算描述了美好的蓝图,但是它不仅面临巨大的工程挑战,而且面临很多科学难题.自主计算对学习和优化理论提出了新的挑战.本文从理论上研究自主计算的自优化问题,这个问题目前还比较少研究.复杂自主系统的优化不是单个目标的优化,而是多个目标的同时优化,这样才能达到整体性能最优.因此研究多目标优化是提高自主系统的自优化能力的重要方面.自主环境是由很多主体构成的动态变化的复杂系统.因此动态环境中优化是自主计算亟需解决的问题.本文从两方面深入研究了自主计算中的自优化问题:利用进化计算的方法研究多目标优化问题;利用强化学习研究动态环境中的优化问题.本文的研究工作主要有以下几个方面:
提出了新颖的数据结构一占优树,以减少多目标优化进化算法中适应值指派的时间复杂度.占优树是能保存三值比较关系的二叉树.我们系统提出了占优树的定义、算法、性质以及算法的时间复杂度.根据占优树的有用特性,我们将它应用进化多目标优化的两个方面:基于占优树的适应值指派方法;基于占优树的多目标进化算法.性能和效率两方面的实验表明基于占优树的算法能够产生比SPEA2和NSGA-II有竞争力的解,但是该算法比它们要快得多.针对基于占优树的多目标进化算法中存在的缺乏密度估计和固定的种群大小的缺点,我们进行了相应的改进.实验结果表明改进算法明显优于原先的算法.
提出了应用于多目标优化的多主体协作系统.针对现实世界广泛存在的多目标优化问题,我们分析其中有三类主体:规划主体规划全局最大利益,行为主体规划单个目标的最大利益,资源主体管理公共资源.我们将进化多目标优化的算法流程应用于多主体协作过程.该方法实现了进化多目标优化的分布并行计算.种群作为资源主体中的资源,行为主体评价单个目标的适应值,规划主体的全局优化是个体的排序过程.这三类主体合作达到Pareto最优解.模拟实验证实该方法是有效的.
提出了单向值方法自动找到子目标.基于option的分层强化学习的关键问题在于学习过程中如何自动找到子目标,我们提出了子目标的有效动作受限的启发式策略.根据这个策略,寻找子目标的问题转化为寻找路径中最匹配的动作受限状态.针对网格环境的学习任务,利用动作受限特性,我们设计了单向值方法自动找到子目标.我们将该方法进行了两方面的应用:离线和在线自动寻找option.实验表明不管是离线还是在线方法,基于单向值方法找到的option的Q学习比基本的Q学习方法要快得多.提出了共享经验的多主体强化学习.我们通过猎人围捕问题深入研究了共享经验对多主体强化学习的学习速度的影响.我们提出了三种状态空间的表示方法:以猎人为中心的建立独立的状态空间;以猎物为中心的建立共享的状态空间以及利用问题的对称性进一步将状态空间压缩到第一象限.通过实验发现共享的状态空间加快了学习的速度;状态空间越小,学习速度也越快.
基于上述研究,本文最后对自主计算的自优化问题研究进行了讨论和总结,并指出了未来的工作方向.