近年来,由于互联网的快速发展及数据库技术的普及,各种信息资源成指数级规模增长。传感和存储技术的广泛使用以及数字成像和视频监控等应用的急剧增长创造了许多高容量,高维度的数据集。人们迫切的需要在庞大的数据海洋中找到自己感兴趣的信息,帮助自己做出合理的决策。数据挖掘技术(Data Mining)就是在这种背景下被广泛研究并取得很大成功。聚类分析技术(Clustering Analysis)作为数据挖掘中十分强大的工具,受到人们越来越多的关注,其在图像处理,模式识别,机器学习,信息检索等诸多领域得到成功应用。聚类分析是根据“物以类聚”的思想,对样本或数据点进行分类的一种多元统计分析方法。聚类目标是将数据分类到不同的类或者簇的一个过程,满足同一个簇中的对象有很大的相似性,而不同簇间的对象有很大的相异性。本文重点研究了K-means等基于分区的聚类方法,但是K-means对初始解很敏感,并且很容易陷入局部最优,因此在本文中引入了几种智能优化算法来求解一些聚类问题。智能优化算法处理许多实际问题时可以在合理时间内得到质量不错的解。常用的智能优化算法包括贪心算法,爬山算法,模拟退火算法,遗传算法,禁忌搜索算法,变邻域搜索算法,粒子群优化算法等。本文将禁忌搜索算法,混合进化算法,文化基因算法等几种智能优化算法成功应用到一些聚类问题之上,通过实验验证取得了很不错的结果,主要工作内容包括如下四个方面:首先,我们提出了一种非常有效的启发式算法:禁忌搜索方法来求解带有容量限制的聚类问题。对于高度约束的问题,在搜索过程中考虑不可行解而不是将搜索过程局限于可行区域,可能有助于更好地探索搜索空间。因此所提出的算法在可行和不可行搜索空间交替搜索。在5组共计183个算例上的计算结果表明,提出的禁忌搜索算法与当前最先进的算法相比有优势。具体来说,本章提出的算法共改进了183个算例中的25个算例的此前国际上记录的最优解。其次,接着上一章的工作,我们提出了一种文化基因算法来解决带有容量限制的聚类问题,该算法使用基于簇的交叉算子生成有希望的子代解并使用上一章提出的禁忌搜索算法改进该子代解。此外,文化基因算法使用基于质量-距离的更新策略更新种群。本章实验结果表明,在给予延长的时间限制下,文化基因算法可以进一步提高禁忌搜索算法的性能。第三,我们提出了一种基于重构局部搜索的文化基因算法来求解在网络上的最小平方和聚类问题。提出的文化基因算法将用于后代生成的交叉算子与用于局部优化的重构局部搜索方法集成在一起。该交叉算子基于backbone思想,能够保存父代中的优良基因并传递到子代。重构局部搜索算法背后的主要思想是利用连续模型与其对应的离散模型之间的关系。计算结果表明,该算法与文献中最先进的算法相比具有很强的竞争力-它为40个实例中的10个报告了新的改进上界,同时在所有剩余的算例上达到了当前最优解。最后,我们研究了平衡的最小平方和聚类问题。我们为平衡最小平方和聚类问题提出了一种混合进化算法。它使用重组算子生成有希望的子代解,然后使用响应阈值搜索(responsive threshold search,RTS)改进子代解。RTS在基于阈值的探索阶段和基于下降的改进阶段交替运行,直到达到指定搜索深度。此外,其使用经典的种群更新策略更新种群。实验结果表明,我们提出的混合进化算法相比求解平衡的最小平方和聚类问题最先进的几种算法有明显优势。更准确地说,在共计152个测试算例上,提出的算法在115个算例上报告了新的改进上界,并且在剩下的所有算例(除了两个算例)上找到了国际上报告的最优解。