抽象数据关系的三维实时动态可视化研究

摘要

抽象数据关系可视化主要是针对于数据结构的可视化，而图是应用最一般且最广泛的数据结构。图的可视化包括静态图可视化和动态图可视化，但动态图可以看成是由静态图组成的序列，因此静态图布局算法是动态图布局算法的基础。 本文将协同进化遗传算法应用于静态图的布局算法中，通过协同进化遗传算法来求解布局目标函数极值。同时针对动态图，在协同进化遗传布局算法的基础上将现实中的“前进队伍插队”应用到动态稳定性布局算法中达到动态稳定性效果。“前进队伍插队”动态稳定性布局算法其最初的布局是由协同进化遗传布局算法产生，其美观性决定了动态图的后续美观性。对图的每一次动态更新都是在前一次稳定的布局的基础上，通过使用重心、牵制权重等概念，进行“局部变化大，整体变化小”的布局更新，并根据新图的结构和变化来控制节点的布局，从而在布局算法中即考虑了图的全局结构也尽量保持了原有图形的稳定性。 本文对这两种算法都进行了实验验证及分析，证明了这两种算法在静态图和动态图的布局中具有较高的可行性和有效性。

目录

文摘

英文文摘

声明

第一章绪论

1.1研究背景

1.2研究意义

1.3研究内容和目标

1.4设计与开发工具的选择

1.5论文的组织

第二章 图布局算法的研究现状

2.1布局算法的发展

2.1.1图的2D布局

2.1.2力导引布局

2.1.3图的3D布局

2.2 3D弹簧建模

2.2.1建模思想

2.2.2弹簧建模

2.3无向图通用布局算法

2.3.1目标函数的选择

2.3.2编码设计

2.3.3适应度函数的选择

2.3.4遗传算子的设定

2.3.5各种控制参数的设定

2.3.6模拟退火扰动选择

2.4协同进化遗传算法

2.4.1背景

2.4.2 CGA算法

2.4.3标准CGA算法

2.4.4 CGA算法的有效性

2.5本章小结

第三章协同进化遗传布局算法的设计

3.1遗传算法的缺陷

3.2算法思想

3.3个体基因块的划分

3.3.1平面子图划分

3.3.2团划分

3.3.3 MIECP划分算法

3.4编码设计

3.5适应度函数设计

3.6协同算子的设定

3.7算法描述

3.8本章小结

第四章 动态稳定性的研究与实现

4.1背景

4.2动态图

4.3图的美观性与动态稳定性

4.4算法思想

4.5算法实现

4.5.1初始化

4.5.2新增节点的插入

4.5.3计算牵制权重

4.5.4新布局输出

4.6算法描述

4.7本章小结

第五章 实验结果及其分析

5.1静态布局算法

5.1.1美观性比较

5.1.2算法复杂度分析

5.2动态布局算法

5.2.1动态稳定性效果

5.2.2算法复杂度分析

5.3算法演示平台

结论

参考文献

攻读硕士学位期间发表的论文

致谢