演化计算是一种适用于求解复杂、高维、大规模问题的全局搜索算法。通过将数据向量模拟为生物中的基因型,模拟自然界中物种的进化过程,对数据向量进行交叉、变异等操作,并从新生成的个体以及原有个体中选取更加适应环境的个体作为新的种群,从而不断迭代对数据进行优化,最终寻找全局最优解。在聚类问题中,作为一种经典的全局优化算法,演化计算提供了强大的求解办法。根据应用的场景,聚类算法又可以分为在向量空间和图空间上的应用:在向量空间上,本文发现演化聚类算法中的个体编码方案存在冗余和不一致的问题,不仅浪费了搜索资源,而且扰乱了个体之间的相互学习过程。为了解决聚类冗余的问题,本文提出了一种基因序列重排列的方法。该方法首先选取当前适应度最佳的参考向量,然后根据每个个体内的基因到参考向量的距离,重新排列基因型的编码顺序。这样,每个个体所代表的聚类方案是统一且相互对应的,从而消除冗余并解决算法中个体间相互学习不一致的问题。结合以上方法,本文针对基于距离的凸聚类和基于密度的非凸聚类两种不同类型的聚类算法进行改进,开发了一种通用的演化聚类框架。实验表明,该方法可以有效地提高演化聚类算法在不同形状数据集上的性能。另一方面,在图空间上,演化算法使用局部邻接编码方案时由于相邻的类之间存在连接的边,导致随机选取邻接边的过程中会将本应属于不同类的节点错误地选取到同一类中,造成不可行解的产生。针对以上问题,本文设计了一种基于线图的边关闭局部邻接编码方案,通过在邻接列表中引入假想空边的概念临时关闭部分边,从而获取正确的局部划分方案。另外,本文设计了一种启发式的初始化策略,对于邻接边的选择更倾向于与当前边更接近或在簇中处于更中心位置的边,以加快算法的收敛速度。基于以上编码方案和初始化策略,本文提出一种基于线图的文化基因算法LGMA（Line Graph Memetic Algorithm）,该方法在经典文化基因算法的基础上,使用模拟退火算法和带有精英策略的爬山算法进行局部优化。实验结果表明,基于线图的文化基因算法可以有效地解决节点划分错误的问题,提高文化基因算法在图聚类中的搜索精度和稳定性。