国防科大计算机学院工学博士学位论文 摘要
虚拟环境中碰撞检测问题的研究作者：魏迎梅(2000.10)导师：吴泉源教授 本文以虚拟手术仿真为应用背景，着重论述了一个基于固定方向凸包包围 盒层次的碰撞检测方法。固定方向凸包是一种特殊类型的凸包，它的所有面方向都来自一个 固定的方向集合，它克服了以往包围盒类型的缺点，在紧密性和简单性之间达到了一定的折 衷。本文在充分研究了固定方向凸包的固有特性的基础上，开发并证明了它适用于复杂环境 中软体碰撞检测的性质，并着重解决了包围盒间的相交测试、对象运动后包围盒的更新、对 象变形后包围盒树的更新等问题。 文中提出并证明了一种快速区间测试法以解决两个固定方向凸包包围盒间的相交测试问题， 通过查找两个包围盒在由固定方向集合所定义的方向轴上的范围区间是否存在不重叠的情况 ，来判断它们是否不相交。通过这种简单的区间测试法，两个包围盒间的相交测试最多只需 要k次比较运算(k为固定方向集合的大小)。 对象运动后包围盒的更新是层次包围盒方法中的一个重要问题。根据固定方向凸包的定义和 性质，文中提出了一种基于线性规划的更新算法，不需要在构造包围盒层次时增加任何额外 的计算量和存储量，在对象运动后可以仅通过3k次乘法得到更新后的包围盒。 对象变形后的处理是碰撞检测问题的一个难点。本文在对几种变形情况进行分析的基础上， 分别提出了相应的解决方法，并着重提出了一种自底向上的包围盒树快速更新算法，通过k 次比较运算由子结点的包围盒得到父结点的包围盒，以解决拉压变形和拓扑变化后包围盒树 的更新问题。 此外，在充分开发和利用虚拟环境中对象运动的时空相关性的基础上，提出了加速对象间碰 撞检测速度的遍历跟踪策略。这是一个启发式的策略，通过跟踪上一时间采样点对包围盒树 的遍历过程，确定当前时间采样点的遍历路径，从而有效地减少了遍历过程中包围盒相交测 试的次数，提高了算法效率，同时通过对跟踪表的维护，保证了碰撞检测的正确性和有效性 。 实验结果和具体应用表明，基于固定方向凸包包围盒层次的碰撞检测方法不仅能 很好地解决刚体间的碰撞检测，而且为解决和处理软体对象环境中的碰撞检测问题提供了一 种可靠而有效的途径。本文的研究成果，对大规模复杂环境中的碰撞检测有重要的理论价值 和实际意义。网络计算中任务分配与调度的遗传算法研究作者：钟求喜(2000.10)导师：陈火旺院士 任务分配与调度是网络计算中的一项关键技术，直接影响到整 个系统的计算性能。任务分配与调度问题是一类NP问题，经典调度理论一般仅能获得问题的 近似最优解。尽管已有用于任务分配与调度的遗传算法求解质量优于传统方法，但传统单种 群遗传算法的效率随任务数增多而下降。本文采用理论分析与仿真实验相结合的方法，研究 网络计算中单任务和独立多任务分配与调度的遗传算法。 本文首先针对同构系统 中任务分配与调度问题提出一个通用的遗传算法。算法直接采用任务列表编码结构，在此基 础上设计出三个专门的遗传算子，即改进的交叉算子、内部交叉算子和具有变异功能的迁移 算子。种群初始化技术采用均衡水平分割法，以保证初始个体的有效性和质量。算法主要控 制参数的取值通过仿真实验确定。 针对传统单种群遗传算法求解独立多任务分配与调度问题的伸缩性差的缺点，本文基于多物 种共同进化的生物学背景，从理论上探讨合作式共同进化计算模型的机理。数学分析表明， 对于独立多问题，共同进化算法采用按比例选择策略时，高于平均适应值的模式的逐代递增 指数高于传统单种群遗传算法，说明共同进化算法的效率高于传统的单种群遗传算法。对于 不可作独立子问题分解的问题，则以基因连锁一般模型-NK模型进行了实例研究。 将合作式共同进化计算模型应用于同构系统中的独立多任务分配与调度问题，提出一个独立 多任务分配与调度的共同进化遗传算法，包括子种群中子分配与调度实例组合成总分配与调 度实例的启发式合并方法，以及子种群个体的适应值计算方法等。 针对网络导构计算的简化模型和一般模型分别提出任务与调度的遗传算法。一般模型中任务 分配与调度受到系统多种因素的影响，如任务间的数据逻辑关系、各处理机的计算速度、网 络拓扑结构、节点间通信机制以及通信波特率、数据流量大小等等。在考虑上述影响因素的 基础上，分别提出单任务分配与调度的遗传算法和独立多任务分配与调度的共同进化算法。 从同构系统到异构计算环境，从单任务到独立多任务，本文提出了针对不同系统环境下任务 分配与调度的遗传算法。理论分析与仿真实验均表明，本文所提算法的问题求解性能优于传 统调度方法和已有用于任务分配与调度的遗传算法。
国防科大、计算机学、任务分配与调度、包围盒树、遗传算法、碰撞检测、固定方向凸包、合作式共同进化、多任务分配、方法、调度问题、一般模型、环境、对象、相交测试、同构系统、网络计算、进化算法、检测问题、仿真实验
23
TP3;G64
2004-01-08（万方平台首次上网日期，不代表论文的发表时间）
共1页
109
