文献类型：学位论文

中文题名：基于DNA计算的加权属性图聚类算法研究及应用

作者：张楠[1];

机构：[1]华东理工大学;

导师：吴雪;华东理工大学|虞正华;华东理工大学

授予学位：硕士

语种：中文

中文关键词：无线传感器网络;加权图;聚类算法;DNA计算

摘要：图是用来描述和解决问题的直观而有效的手段，聚类是将数据集分成若干个簇或类的过程，一般的聚类分析问题可通过转化为图聚类问题来降低复杂度。图聚类算法用赋权图表示研究对象间的相互关系，通过对节点分组形成若干子图，达到聚类的目的。随着社会信息化的持续推进，用于描述现实世界问题的图的规模激增，随之而来的图聚类问题的计算复杂性也普遍呈指数性增长，电子计算机在大规模求解类似问题上已显得无能为力。<br>　　DNA计算的基本原理是以带有信息的DNA链作为编码的载体，参照DNA分子的碱基互补配对原则，把待求问题编码到特定的DNA分子上;然后在生物酶的催化作用下，通过生化操作生成解空间;最后利用适当的操作获取计算结果。DNA计算是一类新型的计算模式，具有高度的并行性。因此若能将DNA计算用于解决图聚类问题，可大幅提高图聚类速度。<br>　　现有的图聚类算法更侧重于将对象合理分簇，簇形成后一般选取中心点做簇头，但在实际应用中，簇头的挑选往往要顾及节点的能量、连接度等重要因素。针对这类问题，本文引入节点与边都加权的属性图，其中节点的权值代表对应节点的重要度，边的权值代表节点间的相似度。本文提出解决这类图的基于最小生成树的聚类算法，并给出了连贯的DNA计算方法，设计了一种改进的编码方式，将点和边权值同时编码到DNA链中，通过生物操作在试管中得到聚类结果及簇头信息。<br>　　本文在分析了加权属性图聚类DNA算法的复杂度之后，将其应用于无线传感器网络的静态分簇问题中，给出了网络路由机制及算法仿真结果，验证了算法的有效性。为网络分簇问题的节能优化提出了一个新颖有效的方法。