优化算法的研究与应用

第３３卷第１期　２０１０年３月　长春理工大学学报（自然科学版）　Ｊｏｕｒｎａｌ　ｏｆＣｈａｎｇｃｈｕｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆＳｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｅｄｉｔｉｏｎ）　Ｖ０１．３３　Ｎｏ．１　Ｍａｒ．２０１０　

数据挖掘算法性能优化的研究与应用　

顾洪博，赵万平　

（大庆石油学院计算机与信息技术学院，大庆１６３３１８）　

摘要：数据挖掘中经常使用ｋ－ｍｅａｎｓ算法，它是经常使用的一种聚类分析算法，但易受初始聚类中心和聚类个数　

ｋ的影响。因此对近年从算法原理、关键技术和优缺点等方面提出的较有代表性的关于初始聚类中心和ｋ值确定的　

改进的ｋ－ｍｅａｎｓ算法进行了分析。并选用知名数据集对一些典型算法进行测试和应用。上述工作将为数据挖掘的研　

究提供有益的参考。　

关键词：聚类算法；性能优化；ｋ—ｍｅａｎｓ　中图分类号：ＴＰ３０１．６　文献标识码：Ａ　文章编号：１６７２—９８７０（２０１０）０１－０１６４—０３　

Ｔｈｅ　Ｒｅｓｅａｒｃｈ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎ　ｆｏｒ　Ｏｐｔｉｍｉｚａｔｉｏｎ　ｏｆ　Ｐｅｒｆｏｒｍａｎｃｅ　

ｂａｓｅｄ　ｏｎ　ｔｈｅ　Ｄａｔａ　Ｍｉｎｉｎｇ　Ａｌｇｏｒｉｔｈｍ　

ＧＵ　Ｈｏｎｇｂｏ，ＺＨＡＯ　Ｗａｎｐｉｎｇ　

（Ｄａｑｉｎｇ　Ｐｅｔｒｏｌｅｕｍ　Ｉｎｓｔｉｔｕｔｅ　Ｓｃｈｏｏｌ　ｏｆＣｏｍｐｕｔｅｒ＆Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｅｃｈｎｏｌｏｇｙ　Ｈｅｉｌｏｎｇｊｉａｎｇ　Ｐｒｏｖｉｎｃｅ，Ｄａｑｉｎｇ　１６３３１８）　

Ａｂｓｔｒａｃｔ：Ｔｈｅ　ｃｌａｓｓｉｃ　ａｌｇｏｒｉｔｈｍ　ｏｆｋ－ｍｅａｎｓ　ｉｓ　ｄｉｓｃｕｓｓｅｄ，ｔｈａｔ　ｉｓ　ｏｎｅ　ｏｆｔｈｅ　ｍｏｓｔ　ｗｉｄｅｓｐｒｅａｄ　ｍｅｔｈｏｄｓ　ｉｎ　ｃｌｕｓｔｅｒｉｎｇ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｄａｔａ　ｍｉｎｉｎｇ．Ｂｕｔ　ｉｔ　ｉｓ　ｓｅｎｓｉｔｉｖｅ　ｔｏ　ｏｒｉｇｉｎａｌ　ｃｌｕｓｔｅｒｉｎｇ　ｃｅｎｔｅｒ　ａｎｄ　ｋ．Ｔｈｅ　ｒｅｓｅａｒｃｈ　ａｃｔｕａｌｉｔｙ　ａｎｄ　ｎｅｗ　ｐｒｏｇｒｅｓｓ　ｉｎ　ｋ－ｍｅａｎｓ　

龙源期刊网

稀疏优化问题算法研究

作者：李蒙

来源：《当代人（下半月）》2018年第03期

摘要：稀疏优化问题发展至今，已经广泛应用于压缩感知、图像处理、复杂网络、指数追踪、变量选择等领域，并取得了令人瞩目的成就。稀疏优化问题的求解算法种类繁多，根据算法设计原理的不同，可将其大致分为三类：贪婪算法、凸松弛方法和阈值类算法。本文主要介绍稀疏优化问题算法研究进展及各类算法的优缺点。

关键词：稀疏优化问题；压缩感知；信号重构；优化算法

随着当代社会信息技术的飞速发展，所获取和需要处理的数据量大幅增多，而基于传统的香农奈奎斯特采样定理中要求采样频率不得低于信号最高频率的两倍才可以精确重构信号。2006年，Donoho、Candes等人针对稀疏信号或可稀疏表示的信号提出了新的采集和编解码理论，即压缩感知理论。该理论使得通过少量采样即可准确或近似重构原始信号。信号重构问题是一个非凸稀疏优化问题（问题）。该问题是一个NP-hard问题，所以出现了多种不同的处理模型近似地或在一定条件下等价地求解问题。以下就从压缩感知的信号重构理论出发，分析研究稀疏优化问题的模型和求解算法。

一、压缩感知重构问题

在压缩感知理论中，若信号本身是稀疏的，则原始信号和观测信号之间的表达式为：；若信号本身不是稀疏的，但在基底下具有稀疏表示，即，其中是一个稀疏向量，则原始信号和观测信号之间的表达式为：，此时，重构原始信号只需要得到满足该等式约束的稀疏解，便可通过得到原始信号，其中为测量矩阵，为变换矩阵，为感知矩阵。

在压缩感知理论中，感知矩阵是一个很重要的组成部分，感知矩阵的好坏会直接影响原始信号的重构质量。压缩感知理论中的稀疏信号重构问题旨在通过低维观测数据最大程度恢复出原始的高维信号，其本质为求一个欠定方程组的稀疏解，即 （1）

压缩感知的重构问题也可通过下述模型来求解：（2）

Matlab遗传算法优化工具箱(GAOT)的研究与应用*

周正武1,丁同梅1,2,田毅红2,3,王晓峰2,4(1.广东省技师学院,广东博罗󰀁516100;2.天津大学机械工程学院,天津󰀁300072;3.承德技师学院,河北承德󰀁067400;4.郑州职业技术学院,河南郑州󰀁450121)摘󰀁要:介绍遗传算法的基本原理和Matlab的遗传算法优化工具箱(GAOT),分析了优化工具函数。探讨Matlab遗传算法工具箱在参数优化和非线性规划中的应用。通过优化实例,说明遗传算法是一种具有良好的全局寻优性能的优化方法。用Matlab语言及Matlab语言编制的优化工具箱进行优化设计具有语言简单、函数丰富、用法比较灵活、编程效率高等特点。关键词:遗传算法;Matlab工具箱;优化中图分类号:TH164󰀁󰀁󰀁󰀁󰀁󰀁文献标识码:A󰀁󰀁󰀁󰀁󰀁󰀁文章编号:1007-4414(2006)06-0069-03ThestudyandapplicationofgeneticalgorithmoptimizationtoolboxinMatlabZhouZheng-wu1,DingTong-mei1,2,TianYi-hong2,3,WangXiao-feng2,4(1.Collegeofhigh-gradetechnician,BoluoGuangdong󰀁516100,China;2.Collegeofmechanicalandengineering,Tianjinuniversity,Tianjin󰀁300072,China;3.Chengdecollegeofhigh-gradetechnician,ChengdeHebei󰀁067400,China;4.Zhengzhouvocationalcollegeoftechnology,ZhengzhouHenan󰀁450121,China)Abstract:Thepaperintroducesgeneticalgorithm(GA)andMatlabgeneticalgorithmoptimizationtoolboxandanalysestheoptimizationtoolboxfunction.Thefunctionoptimizationproblemofparameteroptimizationandnonlinearhasbeengiventodemonstratethatgeneticalgorithmisabetterglobaloptimizationmethod.TheoptimizationdesigninMatlabandMatlaboptimi󰀁zationtoolboxhavesimplelanguage、abundantfunctions、flexiblemethodandhighprogrammingefficiency.Keywords:geneticagolrithm;matlabtoolbox;optimization󰀁󰀁遗传算法(GA)是一类借鉴生物界自然选择和遗传原理的随机优化搜索算法。其主要特点是群体搜索策略和群体中个体间的信息交换、搜索不依赖于梯度信息。遗传算法几乎渗透到从工程到社会科学的诸多领域,广泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域,是21世纪有关智能计算中的关键技术之一。Matlab语言是一种高效率的用于科学工程计算的高级语言,它的语法规则简单、更贴近人的思维方式,通俗易懂。Matlab语言有着丰富的各种工具箱,Matlab的优化工具箱提供对各种优化问题的一个完整的解决方案。遗传算法优化工具箱就是其中之一。采用Matlab遗传算法优化工具箱,不仅具有简单、易用、易于修改的特点,且为解决许多传统的优化方法难以解决的参数优化、非线性、多峰值之类的复杂问题提供有效的途径,为遗传算法的研究和应用提供很好的应用前景[1]。1󰀁遗传算法(GA)1.1󰀁遗传算法原理[2]遗传算法(GeneticAgolrithm)是由美国Michigan大学的JohnHolland教授在20世纪60年代提出,它是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。遗传算法是将问题的求解表示成󰀂染色体 ,将其置于问题的󰀂环境 中,根据适者生存的原则,从中选择出适应环境的󰀂染色体 进行复制,即再生(reproduction,selec󰀁tion),通过交叉(crossover)、变异(mutation)两种基因操作产生出新一代更适合环境的󰀂染色体 群,这样一代代不断改进,最后收敛到一个最适合环境的个体上(当然也有其它的收敛准则),求得问题的最佳解。由于最好的染色体不一定出现在最后一代,开始时保留最好的染色体,如果在新的种群又发现更好的染色体,则用它代替原来的染色体,进化完成后,这个染色体可看作是最优化的结果。1.2󰀁遗传算法的步骤[2]遗传算法与传统搜索算法不同,它以适应度(fitness)函数(目标函数)为依据,通过对种群(popldAfon)中的所有个体实施遗传操作,实现群体内个体结构重组的迭代过程搜索法。选择(selection)、杂交(crossover)、变异(mutation)构成遗传算法的3个主要遗传操作。参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定等要素组成遗传算法的核心内容。其主要步骤有:(1)编码󰀁由于GA不能直接处理空间的数据。必须通过编码将其表示成遗传空间的基因型串结构数据。(2)初始种群的生成󰀁随机产生N个初始串结构数据,每个串结构数据称为一个个体,也称为染色体(chromosome),N个个体构成一个种群。(3)适应度评估检测󰀁GA在搜索进化过程中一般不需要其它外部信息,仅用适应度来评估个体或解的优劣,并作为以后遗传操作的依据。对于不同的问题,适应度的定义方式也不同。(4)选择󰀁选择或复制是为从当前个体中选出优良的个体,使其有机会作为父辈为下一代繁殖子孙。个体适应度越!69!第19卷󰀁第6期2006年12月󰀁󰀁󰀁󰀁󰀁󰀁󰀁机械研究与应用MECHANICALRESEARCH&APPLICATION󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁Vol19󰀁No62006󰀁12

大连理工大学

硕士学位论文

多目标优化的粒子群算法及其应用研究

姓名：陈绍新

申请学位级别：硕士

专业：软件工程

指导教师：周宽久

20071118大连理工大学硕士学位论文

摘要

粒子群算法伊ｓｏ）是近几年发展起来的解决多目标优化问题的群智能算法。该算法基于这样的假设：群体中的各个粒子能够从其过去的经历和其它粒子的经历得到有效的

信息。实验发现，对于大多数优化问题，其有更快的收敛速度，需要设置的参数较少等

特点，但它们在解集分布性、收敛性方面仍存在不足，涉及到的实际应用较少。本文对

多目标粒子群算法进行了系统研究，在前人研究的基础上从三个方面改进了多目标粒子

群算法，并将改进的多目标粒子群算法应用到营养配餐计算模型的求解过程之中，本文

的工作主要有以下几个方面：

１．总结了多目标优化的传统解决方法和基于进化算法计算的解决算法，并重点介

绍了粒子群算法及其在多目标优化领域的研究现状。

２．设计了一种新的多目标粒子群求解方法，主要从三个方面对算法进行了改进和优

化：（１）在粒子全局最优值选取过程中，先后采用了拥挤机制和禁忌算法，从而使全局最

优值的选取更为合理，避免了算法过早陷入局部最优，保持了解的分布性；（２）在处理约

束条件方面，传统的处理方法大多只考虑粒子所在区域，致使边界值处理精度不高，本

文引入半可行域的概念，进而改进了适应度函数的求解方式，克服了传统的约束处理存

在的问题；（３）在时间复杂度方面，传统的构造非支配集的方法时间复杂度较高，本文采

用了随机选择策略交换分组的非支配集构造方法，提高了构造非支配集的效率，减少了

算法的时间复杂度。３．针对传统的营养配餐模型多为经济目标函数，主要考虑食物价格因素的特点，

提出了新的营养配餐模型，能在满足人体各种营养需求的基础上，满足各类人群的需求，

具有种类多样化、灵活化的特点。

最后，将提出的新的多目标粒子群算法应用到新的营养配餐模型中，针对营养配餐

的特点设计并实现了基于Ｗｅｂ的新的营养配餐决策支持系统。通过与传统营养配餐模