量子遗传算法在聚类分析中的应用研究
量子遗传算法在聚类分析中的应用研究[20200419160811]
摘要
由于传统进化算法在聚类分析方面存在着收敛速度慢，容易陷入局部最优等问题，本文提出了运用量子遗传算法对样品进行聚类分析。量子遗传算法是传统遗传算法与量子计算理论相结合而产生的新型优化算法。它不但继承了传统遗传算法的高效并行的优点，还同时具有种群规模小、搜索能力强、收敛速度快和最优解稳定性高等特点。阐述了利用该算法对样品进行聚类的具体步骤。通过实例仿真，表明了该算法能很好的实现对样品的聚类，并克服了过早收敛的现象，加快收敛速度。
*查看完整论文请 +Q: 3 5 1 9 1 6 0 7 2
关键字:量子遗传算法聚类分析识别分类
目录
1.绪论 1
1.1课题研究的目的及意义 1
1.2研究现状和主要内容 1
2.聚类分析 3
2.1聚类介绍 3
2.2基于遗传的数字识别聚类 5
3.基于量子遗传算法的聚类分析 8
3.1量子遗传算法的基本思想 8
3.2量子遗传算法的构成要素 8
3.3量子遗传算法的基本流程 10
3.4量子遗传算法设计 12
3.4.1构造个体 12
3.4.2量子位构造 13
3.4.3量子位值的确定 14
3.4.4计算适应度 14
3.4.5量子旋转门与量子非门变异 15
3.5可视化界面的设计制作 15
3.5.1界面布局设计 16
3.5.2界面编程 16
3.6实验仿真及结果分析 18
4.总结与展望 24
4.1工作总结 24
4.2今后展望 24
参考文献 25
致谢 26
1.绪论
1.1课题研究的目的及意义
聚类分析是对静态数据分析的一门技术，它是指将物理或抽象对象的集合分组成为由类似的对象组成的多个类的分析过程。聚类分析的目的就是收集相似的数据，以此来进行分类。它在许多领域都有广泛应用，包括机器学习，数据挖掘，模式识别，图像分析以及生物信息等方面[1]。
量子遗传算法是遗传算法与量子计算组合的产物，是新发展起来的一种概率演化算法，它是借鉴达尔文进化论中生物界自然选择和进化机制发展起来的一种拥有自适应性和自组织能力的搜索算法。优点是种群规模小，对全局的搜索能力比较强，收敛速度较快，广泛应用于对复杂优化问题的求解[2]。
基于上述原因本课题提出一种基于量子遗传算法的聚类方法，将聚类问题转化为聚类中心的寻优问题，通过量子遗传算法的进化计算实现对聚类中心的优化，通过量子遗传算法的整体搜索策略和优化搜索方法能够快速准确地找到最优解。
1.2研究现状和主要内容
上世纪年代末引入遗传算法的量子计算的一些概念，从而开辟了新的研究领域，这就是量子遗传算法。在量子遗传算法中，为了实现信息的量子化而采用量子态来表示量子位，这种表示增加了种群的多样性并且缩小了种群规模；要使信息可以在整个种群中进行交流，增加了种群发现优秀演化方向的个体能力，并扩大搜索范围，这就需要用到量子杂交，它体现了量子的纠缠特性；当然，还可以使用量子非门来实现变异这一操作。量子遗传算法实质上也是遗传算法的一种，所以，用传统遗传算法解决的问题，用量子遗传算法也可以解决，因为量子计算的特殊性，其显示的效果比传统进化算法更好[3]。
量子遗传算法与传统算法相比，出现的时间相对较晚，而且研究还在起步阶段，但量子遗传算法近几年来已成为一个新的研究热点，现在已经有许多算法被研究和改进，流行的有许多类型的进化算法，结合量子计算的演变产生了新的混合量子进化算法，如免疫量子进化算法、量子克隆进化算法、量子模拟退火算法、量子粒子群进化算法等[4]。探索新的量子遗传算法，并将它法更好地应用到实际的优化问题中是非常有必要的。
根据目前对量子遗传算法研究的情况，并在前人对聚类分析的方法和经验的基础上，再结合自己本次研究课题的情况，利用量子遗传算法对样品进行聚类分析，实现了对图片中样品的分组和归类。具体内容如下：
（1）建立适当、友好的可视化界面，为操作带来便利。
（2）研究聚类方法，运用量子遗传算法处理部分参数，通过迭代计算找到最优解。
（3）通过MATLAB仿真，实现对图中样品的分组和归类。
针对论文的研究内容，本文结构安排如下：
第一章为绪论，主要是介绍本课题的研究目的及其意义，并讲述了研究现状和主要内容。
第二章为聚类分析的介绍，阐述了聚类的原理和方法，介绍了它在数字聚类方面的应用，并做了MATLAB仿真。
第三章为基于量子遗传算法的聚类分析的实验结果及分析，通过绘制的GUI界面，结合所提出的量子遗传算法对样品特征进行聚类分析，并对实验结果进行了分析，证明所采用的量子遗传算法的准确率高，收敛速度快。
第四章为论文总结及展望，总结全文所研究的内容，对进一步的研究工作及未来工作的展望。
2.聚类分析
2.1聚类介绍
聚类分析是指将物理的或抽象的分类对象集合，依据样本间关联的度量标准将其自动分成多个类的一个分析过程。它使得个体相似度高的样本在同一群组内，而个体相异度高的样本在不同群组中，这是一种新的且多变量的统计方法。聚类分析的目的就是收集相似度高的数据，以此来进行分类。聚类源于很多学科领域，包括：数学、计算机科学、统计学、生物学和经济学等[5]。，聚类技术在不同的应用领域中都得到了相应的发展，这些技术和方法，被用来描述不同数据源和衡量它们之间的相似性，并分为不同的类别。聚类分析从实际应用的角度看，它是数据挖掘的主要任务之一。聚类分析可以作为一种工具，用它来获得数据的分布，观察每一类的特点，通过这些特点的观察，结合实际问题并进一步分析，最终得到满意的结果。
目前应用的最为广泛的一种聚类方法是系统聚类法，它的基本思想是：先把要聚类的n个样品或者变量分别视为一类，一共有n类；然后按照一定的方法计算类与类之间的聚类统计量，即按照某种距离指标或者有关的系数来进行聚类，并且把关系最为密切的两类视作同一类，其余的都不变，就能得到n-1类；接着重复之前的计算方法，计算更新后新类与其他类之间的距离指标或系数，再将关系最为密切的两类视作同一类，其余不变，就能得到n-2类；以此类推，在重复过程后每次都会减少一类，直到最后所有的样品或者变量都归为一类[7]。
聚类可以按照距离指标来计算。距离指标的计算方法非常多，按照不同性质的数据，可选用不同的距离指标来计算。有欧氏距离、夹角余弦距离、二值夹角余弦距离、Tanimoto测度等。距离计算关系到聚类的结果，所以用什么样的方法计算距离是比较重要的。距离变换在数字图像处理中应用比较广泛，特别是在处理二值图像时很有帮助，它将当前的像素的值转化为该点到达最近的背景点的距离。下面就分别给出几种距离指标的公式。
有两个样品 和 的特征向量分别为 ， 。它们之间的欧氏距离公式为2-1。
(2-1)
夹角余弦距离公式为2-2。
(2-2)
二值夹角余弦距离公式为2-3。
(2-3)
Tanimoto测度公式为2-4。
(2-4)
其中，夹角余弦的取值范围在-1到1之间。较小的两个向量之间的角度，它的余弦值越大，反之，较大的两个向量之间的角度，余弦值小。当两个向量之间的角度相吻合，能得到最大值1，当两个向量是完全相反的方向，余弦值的最小值为-1。
摘要
由于传统进化算法在聚类分析方面存在着收敛速度慢，容易陷入局部最优等问题，本文提出了运用量子遗传算法对样品进行聚类分析。量子遗传算法是传统遗传算法与量子计算理论相结合而产生的新型优化算法。它不但继承了传统遗传算法的高效并行的优点，还同时具有种群规模小、搜索能力强、收敛速度快和最优解稳定性高等特点。阐述了利用该算法对样品进行聚类的具体步骤。通过实例仿真，表明了该算法能很好的实现对样品的聚类，并克服了过早收敛的现象，加快收敛速度。
*查看完整论文请 +Q: 3 5 1 9 1 6 0 7 2
关键字:量子遗传算法聚类分析识别分类
目录
1.绪论 1
1.1课题研究的目的及意义 1
1.2研究现状和主要内容 1
2.聚类分析 3
2.1聚类介绍 3
2.2基于遗传的数字识别聚类 5
3.基于量子遗传算法的聚类分析 8
3.1量子遗传算法的基本思想 8
3.2量子遗传算法的构成要素 8
3.3量子遗传算法的基本流程 10
3.4量子遗传算法设计 12
3.4.1构造个体 12
3.4.2量子位构造 13
3.4.3量子位值的确定 14
3.4.4计算适应度 14
3.4.5量子旋转门与量子非门变异 15
3.5可视化界面的设计制作 15
3.5.1界面布局设计 16
3.5.2界面编程 16
3.6实验仿真及结果分析 18
4.总结与展望 24
4.1工作总结 24
4.2今后展望 24
参考文献 25
致谢 26
1.绪论
1.1课题研究的目的及意义
聚类分析是对静态数据分析的一门技术，它是指将物理或抽象对象的集合分组成为由类似的对象组成的多个类的分析过程。聚类分析的目的就是收集相似的数据，以此来进行分类。它在许多领域都有广泛应用，包括机器学习，数据挖掘，模式识别，图像分析以及生物信息等方面[1]。
量子遗传算法是遗传算法与量子计算组合的产物，是新发展起来的一种概率演化算法，它是借鉴达尔文进化论中生物界自然选择和进化机制发展起来的一种拥有自适应性和自组织能力的搜索算法。优点是种群规模小，对全局的搜索能力比较强，收敛速度较快，广泛应用于对复杂优化问题的求解[2]。
基于上述原因本课题提出一种基于量子遗传算法的聚类方法，将聚类问题转化为聚类中心的寻优问题，通过量子遗传算法的进化计算实现对聚类中心的优化，通过量子遗传算法的整体搜索策略和优化搜索方法能够快速准确地找到最优解。
1.2研究现状和主要内容
上世纪年代末引入遗传算法的量子计算的一些概念，从而开辟了新的研究领域，这就是量子遗传算法。在量子遗传算法中，为了实现信息的量子化而采用量子态来表示量子位，这种表示增加了种群的多样性并且缩小了种群规模；要使信息可以在整个种群中进行交流，增加了种群发现优秀演化方向的个体能力，并扩大搜索范围，这就需要用到量子杂交，它体现了量子的纠缠特性；当然，还可以使用量子非门来实现变异这一操作。量子遗传算法实质上也是遗传算法的一种，所以，用传统遗传算法解决的问题，用量子遗传算法也可以解决，因为量子计算的特殊性，其显示的效果比传统进化算法更好[3]。
量子遗传算法与传统算法相比，出现的时间相对较晚，而且研究还在起步阶段，但量子遗传算法近几年来已成为一个新的研究热点，现在已经有许多算法被研究和改进，流行的有许多类型的进化算法，结合量子计算的演变产生了新的混合量子进化算法，如免疫量子进化算法、量子克隆进化算法、量子模拟退火算法、量子粒子群进化算法等[4]。探索新的量子遗传算法，并将它法更好地应用到实际的优化问题中是非常有必要的。
根据目前对量子遗传算法研究的情况，并在前人对聚类分析的方法和经验的基础上，再结合自己本次研究课题的情况，利用量子遗传算法对样品进行聚类分析，实现了对图片中样品的分组和归类。具体内容如下：
（1）建立适当、友好的可视化界面，为操作带来便利。
（2）研究聚类方法，运用量子遗传算法处理部分参数，通过迭代计算找到最优解。
（3）通过MATLAB仿真，实现对图中样品的分组和归类。
针对论文的研究内容，本文结构安排如下：
第一章为绪论，主要是介绍本课题的研究目的及其意义，并讲述了研究现状和主要内容。
第二章为聚类分析的介绍，阐述了聚类的原理和方法，介绍了它在数字聚类方面的应用，并做了MATLAB仿真。
第三章为基于量子遗传算法的聚类分析的实验结果及分析，通过绘制的GUI界面，结合所提出的量子遗传算法对样品特征进行聚类分析，并对实验结果进行了分析，证明所采用的量子遗传算法的准确率高，收敛速度快。
第四章为论文总结及展望，总结全文所研究的内容，对进一步的研究工作及未来工作的展望。
2.聚类分析
2.1聚类介绍
聚类分析是指将物理的或抽象的分类对象集合，依据样本间关联的度量标准将其自动分成多个类的一个分析过程。它使得个体相似度高的样本在同一群组内，而个体相异度高的样本在不同群组中，这是一种新的且多变量的统计方法。聚类分析的目的就是收集相似度高的数据，以此来进行分类。聚类源于很多学科领域，包括：数学、计算机科学、统计学、生物学和经济学等[5]。，聚类技术在不同的应用领域中都得到了相应的发展，这些技术和方法，被用来描述不同数据源和衡量它们之间的相似性，并分为不同的类别。聚类分析从实际应用的角度看，它是数据挖掘的主要任务之一。聚类分析可以作为一种工具，用它来获得数据的分布，观察每一类的特点，通过这些特点的观察，结合实际问题并进一步分析，最终得到满意的结果。
目前应用的最为广泛的一种聚类方法是系统聚类法，它的基本思想是：先把要聚类的n个样品或者变量分别视为一类，一共有n类；然后按照一定的方法计算类与类之间的聚类统计量，即按照某种距离指标或者有关的系数来进行聚类，并且把关系最为密切的两类视作同一类，其余的都不变，就能得到n-1类；接着重复之前的计算方法，计算更新后新类与其他类之间的距离指标或系数，再将关系最为密切的两类视作同一类，其余不变，就能得到n-2类；以此类推，在重复过程后每次都会减少一类，直到最后所有的样品或者变量都归为一类[7]。
聚类可以按照距离指标来计算。距离指标的计算方法非常多，按照不同性质的数据，可选用不同的距离指标来计算。有欧氏距离、夹角余弦距离、二值夹角余弦距离、Tanimoto测度等。距离计算关系到聚类的结果，所以用什么样的方法计算距离是比较重要的。距离变换在数字图像处理中应用比较广泛，特别是在处理二值图像时很有帮助，它将当前的像素的值转化为该点到达最近的背景点的距离。下面就分别给出几种距离指标的公式。
有两个样品 和 的特征向量分别为 ， 。它们之间的欧氏距离公式为2-1。
(2-1)
夹角余弦距离公式为2-2。
(2-2)
二值夹角余弦距离公式为2-3。
(2-3)
Tanimoto测度公式为2-4。
(2-4)
其中，夹角余弦的取值范围在-1到1之间。较小的两个向量之间的角度，它的余弦值越大，反之，较大的两个向量之间的角度，余弦值小。当两个向量之间的角度相吻合，能得到最大值1，当两个向量是完全相反的方向，余弦值的最小值为-1。
版权保护: 本文由 hbsrm.com编辑，转载请保留链接: www.hbsrm.com/jxgc/zdh/4132.html
