算法的收敛性

遗传算法的收敛性不仅取决于前面已讨论过的编码，初始群体，适应度函数，选择算子的设计，而且还取决于交叉算子和变异算子的设计。但是，遗传算法的收敛性主要决定于作为其核心操作的交叉算子。交叉算子收敛性是当今遗传算法研究中最重要课题之一，目前仍无系统而全面的论述。但是，通过局部的理论分析，尤其是大量的卓有成效的实验，对于交叉收敛性已有若干共识。现大致规纳如下：

（1）交叉算子并未提供收敛性保证。模式定理只是在考虑选择算子可维持模式而交叉和变异算子会破坏模式的基础上提供了通过不断的交叉，低阶、短距的模式可呈指数倍增长的论述，但它未能确认这呈指数增长的模式一定向最优解收敛。

（2）交叉算子的有效工作范围以及其边界可通过骗定理或骗问题的分析而得到描述。

（3）虽然交叉缺乏收敛保证，但这并不影响遗传算法的实用性。有时，许多收敛算法由于其收敛性却牺牲了它们的全局性和灵活性。因此，不少对于收敛算法是很难求解的问题，对于基于交叉的遗传算法而言反而是简单可解的了。

（4）排除变异仅有交叉的遗传算法可等效为有限吸收的Markov过程.在适应的选择策略下,通过交叉可实现向最优解收敛。

遗传算法导入变异的目的有两个:一是使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解邻域时,得用变异算子的这种局部随机搜索能力可以加速向最优解收敛。显然,此种情况下的变异概率应取较小值,否则接近最优解的积木块会因变异而遭到破坏。二是使遗传算法可维持群体多样性,以防止出现未成熟收敛现象。此时收敛概率应取较大值。

遗传算法中,交叉算子因其全局搜索能力而作为主要算子,变异算子因其局部搜索能力而伤为辅助算子。遗传算法通过交叉和变异这一对相互配合又相互竞争的......

......

通过对例1和例2的对比分析，K均值算法对初始值敏感，不同的初始值收敛于不同的局部极优点；而利用遗传算法进行聚类每次都在基本相同的最优点处收敛；由此可得结论；遗传聚类算法与K均值相比，具有较强的全局收敛能力。遗传K均值聚类算法兼顾了局部收敛和全局收敛性能，在兼顾局部收敛速度的同时寻找的空间聚类中心保持了良好的全局分布特性。

遗传K均值聚类算法克服了传统K均值聚类算法收敛时易陷入局部极值问题和对初始选值敏感的缺点，同时又保持了K均值算法快速度收敛的特点。实验表明，其方法显著提高了聚类性能，其结果也优于传统的K均值聚类方法。