韩　海

（江汉大学 数学与计算机科学学院，湖北　武汉　430056）

K进制遗传算法在聚类问题求解中的应用

韩海

（江汉大学 数学与计算机科学学院，湖北武汉430056）

文章提出了用K进制串作为遗传算法的染色体的方案，给出了用该算法求解聚类问题的一般性步骤，并对该方法的适用性进行了分析。

聚类；遗传算法；K进制串；染色体

尽管计算机在重复计算方面具有人类无法比拟的速度，但在处理高复杂度的问题时，穷举法随着数据量的增长仍然会很快失效。有着广泛应用的聚类问题是典型的高复杂度问题、TSP问题［1］、Web文档聚类［2］是其中的典型应用。穷举法可以确保找出问题的最优解，但在面对计算量巨大的聚类问题时，穷举法显得无能为力。为此，遗传算法、蚁群算法、粒子群算法、退火算法等应运而生，这些算法都是在解空间内做部分搜索，在可以接受的时间内找出已搜索到最优解，并以此作为原问题的解。

1　遗传算法与聚类问题

遗传算法（Genetic Algorithm）是一种通过模拟生物进化过程搜索最优解的方法。它模拟生物进化过程中的自然选择和遗传机理，能较好地在解空间中进行搜索。遗传算法首先需要有一个由若干个生物体构成的种群，每个个体都包含有一组特定的信息，称为染色体。染色体具有相同的结构。遗传就是由当前种群把染色体所包含的信息按一定规则传递给下一代。传递规则既保证了对当前种群的择优，也保证了适应性较差的个体也能有一定的遗传机会。……