Abstract: In order to solve the quadratic assignment problem(QAP), a novel estimation of distribution algorithm(EDA), namely, hybrid EDA(HEDA) is proposed. Firstly, we design a heuristic rule, i.e., hypothesis-logistic-center-based heuristic rule(HLCBHR)according to the information of distance and material flow matrixes to generate the initial population, which is helpful to enhance the quality of initial population and the HEDA’s search efficiency. Secondly, focusing on the probability model of HEDA, both an initial configuration generating mechanism and a perturbation operation of probability matrix are developed in order to improve the global exploration ability. In addition, based on the sufficient analysis of QAP’s structure properties, a speed-up-evaluation-based local search strategy is embedded into the HEDA to enhance the local exploitation ability. Simulation experiments and comparisons demonstrate the optimization performance of the proposed HEDA.

Key words: quadratic assignment problem, estimation of distribution algorithm, heuristic rule, probability model, speed-up evaluation

摘要： 为了求解物流设施二次分配问题,提出了一种混合分布估计算法(HEDA)。首先,根据QAP的距离和物流量矩阵信息,提出了一种基于假设物流中心启发式规则的种群初始化方法,用于提高初始种群的质量和算法的搜索效率;其次,针对HEDA的概率模型,提出了一种概率矩阵初始构型生成机制和扰动操作,用于提高算法的全局探索能力;最后,在分析QAP的结构性质的基础上,设计了一种基于快速评价的局部搜索策略,用于提高算法的局部开发能力。仿真计算实验和算法比较验证了HEDA的优化性能。

关键词: 二次分配问题, 混合分布估计算法, 启发式规则, 概率模型, 快速评价