最优化问题是指从一系列解决某问题的可行方案中找到解决该问题的最优方案。最优化问题出现在许多的领域中,比如说,信息,经济、生产制造、交通运输等。因此,寻找解决这些问题的最优方案具有很重要的社会意义,同时也能产生巨大的社会经济效益。最优化是数学领域的一个独立分支,主要是用来解决最优化问题,其具体的解决优化问题的方法被称为最优化方法。以数学为基础的传统优化方法比如迭代、Newton法等对问题的求解通常要求问题的目标函数和约束条件是连续可微的这一严格的前提条件。而现实世界生产生活中的大多优化问题都不满足这一前提条件,它们大都具有很复杂的特点,比如,不可导、不连续的搜索空间、多个局部极值点、变量间存在强耦合关系等,而这些问题传统的确定性优化算法是很难解决的。因此,寻求面向复杂问题的可行性优化方法是一个亟待解决的问题。演化算法(Evolutionary Algorithm-EA)源自于人们对自然界或生物界一‘些现象的观察和模拟。相对于传统的优化方法,以演化计算为代表的仿生智能算法通常对各类复杂优化问题具有很强的适应性、鲁棒性和并行处理等优点,并被广泛地应用于科学研究和工业生产等众多领域。在过去数十年中,研究人员提出了很多的基于群体的演化算法,如遗传算法、差分进化算法、粒子群优化算法、蚁群优化算法、人工蜂群算法、猫群优化算法等。粒子群优化算法(Particle Swarm Optimization-PSO)作为演化算法中的一种,是一种通过模拟生物觅食现象而提出的群智能算法。由于其简单、参数较少且易于实现等特点,吸引了很多学者的关注,同时也在众多领域得到了成功的应用。但是粒子群优化算法也存在一些缺点,如局部搜索能力较差,搜索精度不高,并且容易陷入局部极值等。针对这些问题,人们提出了许多的改进方法和策略。本文基于粒子群优化算法,对复杂优化问题进行了研究,提出了一些粒子群优化算法的改进版本,并通过大量的实验对算法的性能进行了验证,实验结果表明,本文提出的算法能够有效地克服粒子群算法过早收敛,同时求解质量也有了显著的提升。这些缺点抑制了PSO算法在现实世界中的广泛应用。因此,在PSO算法研究中,提高算法的精度和避免局部极值是两上重要的方向。近年,很多的PSO的改进版本被提出以实现这两个目的。然而,对于具有高复杂性和大规模特性的现实问题,PSO算法的性能仍令人不满意。在演化算法的研究中,影响算法性能的因素主要有两个：1)勘探能力(exploration);2)开采能力(exploitation)。勘探能力是指算法在解空间中探测未知区域寻找全局最优解的能力,具有较强勘探能力的算法能够有效地避免局部极值的影响。开采能力是指算法利用已有的较好个体的信息来搜索更优解的能力。从算法性能的角度来看,勘探能力是和全局搜索性能相关的,影响到算法的解的精度；而开采能力则和局部搜索性能相关,影响到算法的收敛速度。然而,这两种能力是相互冲突的,如何平衡好这两种能力是提高演化算法性能的关键。针对粒子群算法的改进,勘探能力和开采能力的平衡也是本文的主要研究内容。本文主要有以下四个创新点：i)提出了两种基于邻居搜索的新策略,即局部邻居搜索和全局邻居搜索,并以此分别增强PSO算法的开采能力和勘探能力。提出的新邻居搜索的策略中,选用邻居中最好的粒子来改进搜索策略。构建了一个自适应机制以平衡局部与全局两个邻居搜索策略。ii)针对多峰问题,构建了一个自适应机制以在两个多层搜索策略中自动选择一个策略执行,通过这个自适应机制提高了PSO算法对于勘探能力和开采能力的平衡。iii)为了提高勘探和开采的平衡控制,本文提出了两种自适应机制。一种是控制邻居搜索策略,另外一种是控制多层搜索策略。iv)利用粒子群优化算法的优点,针对聚类数据和图像分割问题,本文提出了几个应用算法,一是使用三种聚类数据算法来解决两种聚类数据问题：即确定和不确定的分类数量。二是根据聚类数据方法提出了四种图像分割算法。本文的主要贡献如下所述：1)提出了两种PSO的改进算法。对于粒子的邻居拓扑结构的研究,研究人员提出了很多的方法。Kennedy测试了四种邻居拓扑(环型、轮型、星型和随机型)以引导粒子的飞行。Mendes等提出了全面学习的粒子群方法,这样粒子可以学习到全面的信息。Liang等提出了综合学习粒子群优化算法(CLPSO). Nasir等对CLPSO进行改进,提出了动态邻居学习粒子群优化算法(DNLPSO)。此外,Wang等提出了一种使用邻居搜索的多样性增强的粒子群优化算法(DNSPSO),其中使用了局部和全局的邻居搜索策略。通过改进DNSPSO的邻居搜索策略,Tran等提出了增强的多样性与邻居搜索的粒子群优化算法(EPSODNS)。 Tran等还将邻居搜索与柯西变异结合起来提出了AMPSONS。多种应用了多样性驱动方法的粒子群改进算法也被提出。Gong等基于粒子群优化算法提出了一种有效的资源分配方式,其中粒子在寻优的过程中向它自已和邻居进行综合的学习。为了提高粒子群优化算法处理复杂问题,特别是多峰问题的能力,Wang等提出了一种多层的粒子群优化算法(MLPSO),它由全局MLPSO和局部MLPSO组成,种群的层数由二层到多层不等。以上的改进算法都取得了比较好的实验结果,然而算法的性能仍不是令人满意,特别是对复杂的现实问题。在这两个提出的方法中,对上文中提到的邻居搜索、多层搜索、多样性和自适应机制进行了改进并应用到了改进的PSO算法中,以下是两个提出的改进算法：i)提出的第一个算法为ANSPSO。在该算法中,自适应邻居搜索(Adaptive neighourhood search)机制用来增强PSO的收敛性能。此外,为了提高勘探能力,在算法中引入了新的多样性(Diversity)机制。为了验证算法的性能,在实验中,使用了两类测试函数集,分别为包括13个常用测试函数的测试集和CEC 2013年提出的测试函数集,这些函数中既有单峰问题也有多峰问题,具有不同的复杂度和特点,问题的维数有10维和50维。在这两个测试函数集上的实验结果以及与其它知名PSO算法的比较,证明了该方法的优异性能。ⅱ)本文提出的第二种改进的PSO算法(APSOMNS)是基于两个自适应机制建立的多层和邻居搜索的PSO算法。在该算法中,为了增强其求解多峰优化问题的性能,使用了多层搜索策略。类似于ANSPSO算法,构建了局部多层搜索和全局多层搜索的自适应机制。除了自适应多层搜索机制,算法中仍然采用ANSPSO算法中的自适应邻居搜索机制。通过使用上述两种自适应机制,算法性能得到了改善。ANSPSO算法中使用的两测试函数集也被用于评价所提出APSOMNS算法的性能。实验结果表明,所提出的APSOMNS算法优于其他参与比较的知名的PSO改进算法。2)本文的第二个主要贡献是PSO在数据聚类上的应用。通过将PSO和K-means混合提出了三个聚类算法。数据聚类被认为是在机器学习中最困难和最具有挑战性的问题之一,特别是由于其无监督的性质。从优化的角度来看,数据聚类可以被视为一种特殊的分组问题。数据聚类是一种无监督的分类技术,其根据预设的规则将最相似的数据对象划分到相同的类中。分层法和划分法是最常用的两种数据聚类技术。分层聚类算法首先将所有的对象作为一类,然后随着算法的执行直到找到所有的分类,反之亦然。划分聚类算法根据相适应的目标函数直接将数据对象划分为固定数目的分类。能处理大数据集是划分方法的优势之一。本文主要研究划分聚类方法。当类数目已知,聚类可以理解为是数据对象在多维空间中的分布,类内的数据比类间的数据更相似,聚类也是对某一外在优化规则的最小化过程。Hartigan提出的K-means聚类算法是最受欢迎和使用最广泛的数据聚类技术之一,其易于实现、高效且具有线性时间复杂度。然而,它有两个主要的缺陷,一是K-means算法高度依赖于类中心的初始值,二是K-means算法的目标函数非凸,它可能包含很多的局部极值,因此在目标函数的优化过程中,解可能易于收敛到局部极值,而不是全局最优值。为了克服这些缺点,近年很多算法被提出用来进行聚类。为了提高K-means的性能,大量基于K-means的聚类算法被提出。在此假设下,为了解决数据聚类问题,很多文章提出了使用演化算法来求解。这些算法是通过优化一个或多目标函数来指导演化搜索求解聚类数据问题。i)提出的第一个算法是ANSPSO与K-means的混合(ANSPSO-KM),其中ANSPSO算法是本文提出的第一种改进PSO算法。ANSPSO-KM用来解决数据聚类问题,其中类数目预先设定。通过与PSO结合的K-means聚类算法克服了其缺点,比如容易陷入局部最优和初始点敏感。ANSPSO-KM的性能通过在14个基准数据集上的仿真实验得以验证,这些数据集中4个为人工生成10个为现实世界的数据集。实验结果表明,ANSPSO-KM取得令人满意的结果。实验结果还证明了将PSO算法引入到K-means中进行数据聚类的有效性。ⅱ)类似于ANSPSO-KM,第二种数据聚类算法是APSOMNS与K-means的混合(APSOMNS-KM)。APSOMNS-KM是用于类数目未知的数据聚类。对该算法的性能评估使用了14个基准数据集。通过实验结果可以看出,所提出的APSOMNS-KM聚类算法优于其它参与比较的聚类算法。iii)事实上,现实世界中的聚类问题的类数目通常是未知的,这增加了数据聚类的难度。为了解决这个问题,本文提出了第三种聚类算法。该算法是PSO与K-means混合进行动态聚类(DCPSONS)。在这个算法中,改进了Omran和Kuo提出的点子,首先使用二进制编码的PSO得到类数目,然后利用K-means得到每个分类的中心。接着为了提高PSO算法的性能,将集成了邻居搜索策略和多样性机制的DCPSONS算法与K-means算法相结合。从而DCPSONS算法能够自动的确定最优的类数目并在最小的人工干预下对数据集进行聚类。在DCPSONS中,使用离散粒子群算法来求解类数目并聚类。为了加强算法能力,该算法使用了多样性机制和邻居搜索两种机制。算法的性能也通过使用14个基准数据集进行了验证。实验结果证明了算法具有较高的准确率和聚类质量。3)提出了四个图像分割的算法。算法研究的思路是使用聚类方法来构建图像分割算法。图像分割是从图像背景中区分出不同的对象,或是将图像划分为相关联的区域。它也是一个细分图像组成部分的过程并从中提取需要的部分。图像分割的目标是简化图像或是将图像改为更有意义或更易于分析的表示。图像分割通常用于定位图像中的对象或是边界(线条、曲线等)。更精确的描述是图像分割是给图像中每一个像素分配一个标签的过程,这些拥有相同标签的像素具有某些相同的特征。它也是计算机视觉应用中的基础部分。文献中关于图像分割问题有很多的方法,现有的图像分割方法主要分以下几类：基于阈值的分割方法、基于区域的分割方法、基于边缘的分割方法以及基于聚类算法(如K-means,FCM, IT2FCM等)的分割方法等。应用聚类算法进行图像分割已数十年之久,且最开始提出的技术方法一直沿用至今。其中主要是依据某一规则将图像中相似部分尽可能的划分到相同的类而将不相似的部分划分到不同的类中。本文主要关注于运用聚类算法来设计图像分割算法。i)第一个算法是FCM和PSO的混合图像分割算法,称为GFCM-PSO。GFCM-PSO是PSO和Generalized Fuzzy C-means (GFCM)的结合。这个算法基于噪声图像。在GFCM-PSO算法中,GFCM是H. Zhang提出的一种图像分割算法。通过人工合成、Berkeley和自然图像进行的实验结果表明,该方法取得了较好的效果和图像质量。ii)第二个图像分割算法是Fast Generalized FCM with PSO,称为FGFCM-PSO。这个提出的新算法是基于Cai等提出的FGFCM和Zhao等提出的S-FCM而设计的。在S-FCM中,隶属度值改为针对每一次迭代更改的图像X中的所有数据点。Zhao指出如果隶属度值接近于0.5,那么这个数据点可能在某一聚类的边界上。然而S-FCM算法对于β值敏感,从而影响到算法的收敛速度和聚类效果。在提出的算法中β值基于高斯分布进行计算。依据FGFCM,首先生成新的图像ξ,然后将PSO引入到FCM中对图像ξ进行分割,其中隶属度值使用改进的源自于S-FCM的最优选择策略得到。在实验中使用的噪声是Gaussian和salt&pepper,使用Matlab软件生成。通过在人工合成、Berkeley和自然图像上进行的实验结果表明,该方法获得了不错的图像分割效果。iii)第三个算法是应用所提出的动态聚类算法DCPSONS来分割图像,其中类数目未知。通过在人工合成和自然图像上进行的实验表明,依据类数目的正确性的图像分割的质量,该方法具有较高的图像分割质量和效果。iv)第四个图像分割算法是基于Interval Type-2 Fuzzy C-means (IT2FCM)和PSO的混合算法,称为IT2FCM-PSO。IT2FCM是一个适用于类数目未知的聚类算法。它是基于Type-2 Fuzzy集设计。Type-2 Fuzzy集是在Type-1 Fuzzy集上的扩展,提高了处理不确定性问题的性能。此外,Interval Type-2 Fuzzy C-means算法在聚类方法中增加了一个步骤,建立了不确定性的足迹方法(FOU),其中使用两个参数来模糊化处理m1和m2,从而使得聚类算法更有效。IT2FCM-PSO算法中粒子群被引入到IT2FCM来提高IT2FCM的性能。通过在自然图像上的实验结果表明,所提出的IT2FCM-PSO算法与其他图像分割算法相比效果较好。总之,本文利用改进的PSO算法的优点设计并提出了多种基于PSO的算法。对数值优化问题、数据聚类和图像分割的实验证明了所提出的改进PSO算法的有效性和效率。