集合划分问题的分布估计求解

Estimation of distribution algorithm for number partitioning problems

集合划分问题对日常生活中的仓库装填问题,生产线排程问题有很大意义,但是无论采用精确算法还是启发式算法都不能很好求解。提出一种改进的分布估计算法,采用实数编码和基于矩阵的概率向量存储方式,并且引入权值的概念,改进了概率向量的更新方式。将它与标准DM(the Differencing Method)算法进行了比较,实验结果证明,它可以有效解决DM算法在25维以下得不到正解的问题。另外,算法还延伸到高维和多分类问题上,这里给出了实验结果。

The Number Partitioning Problems（NPP）,arising from the bin packing problem and line balancing problem in daily life,pose considerate challenge to both exact and heuristic solution methods.This paper introduces an improved estimation of distribution algorithm to the solution of NPP,adopting real coding,matrix-based storage of probability vectors and weight coordination method.Comparison is made between the standard Differencing Method（DM） and the improved EDA.Results show that the improved EDA has great advantage over DM in solving NPP of less than 25 dimensions.The algorithm is extended to higher dimension and multi-partitioning problems as a further exploration in its scalability.Some computational experience is presented here.