求解最大分散度问题的混合分布估计算法

李 涛，林 耿

(闽江学院 数学系，福建 福州 350108)



求解最大分散度问题的混合分布估计算法

李 涛，林 耿

(闽江学院 数学系，福建 福州 350108)

最大分散度问题是一个NP困难问题,提出了一个有效求解最大分散度问题的混合分布估计算法.该算法利用搜索过程中的全局和局部信息来构造新解，提高了搜索的多样性，避免早熟.根据最大分散度问题的特点，构造局部搜索算法来改进分布估计算法的局部搜索能力，采用18个标准测试例子测试本研究提出的算法,与其他算法比较的结果证明了本算法是有效的.

最大分散度问题; 进化算法; 分布估计算法; 启发式算法

给定一个集合N={e1,…,en}，其中的两个元素ei和ej之间的距离为dij(dij=dji).如i≠j，则dij>0；否则，dij=0.最大分散度问题(Maximum Diversity Problem,MDP)是寻找集合N的一个具有m个元素的子集，使该子集中元素间的距离总和最大.引入n维0-1解向量x=(x1,…,xn)，xi=1表示ei被选中，否则ei没有被选中.最大分散度问题可以描述为如下的0-1规划问题：

最大分散度问题是一个典型的NP困难问题，在定位、生态系统、遗传学、制造设计、课程设计等方面有着广泛的应用背景.由于精确算法只能求解较小规模的实例，近年来，元启发式算法成为人们的研究热点之一，如禁忌搜索[1-2]、贪心随机自适应搜索[3]、memetic算法[4]、变邻域搜索[5]被应用于求解大规模最大分散度问题，取得了较好的结果.

分布估计算法(Estimation of Distribution Algorithms,EDA)是一种基于统计原理的随机优化算法，它已经成功应用于求解许多组合优化问题[6-8].然而，由于EDA过多侧重于解空间宏……