Journal of Computer Applications ›› 2021, Vol. 41 ›› Issue (1): 95-102.DOI: 10.11772/j.issn.1001-9081.2020081218

Special Issue: 第八届中国数据挖掘会议(CCDM 2020)

• China Conference on Data Mining 2020 (CCDM 2020) • Previous Articles     Next Articles

Hybrid population-based incremental learning algorithm for solving closed-loop layout problem

DENG Wenhan1,2, ZHANG Ming1,2, WANG Lijin1,2, ZHONG Yiwen1,2   

  1. 1. College of Computer and Information Sciences, Fujian Agriculture and Forestry University, Fuzhou Fujian 350002 China;
    2. Key Laboratory of Smart Agriculture and Forestry(Fujian Agriculture and Forestry University), Fujian Province University, Fuzhou Fujian 350002, China
  • Received:2020-08-12 Revised:2020-08-26 Online:2021-01-10 Published:2020-09-07
  • Supported by:
    This work is partially supported by the Natural Science Foundation of Fujian Province (2019J01401).


邓文瀚1,2, 张铭1,2, 王李进1,2, 钟一文1,2   

  1. 1. 福建农林大学 计算机与信息学院, 福州 350002;
    2. 智慧农林福建省高等学校重点实验室(福建农林大学), 福州 350002
  • 通讯作者: 钟一文
  • 作者简介:邓文瀚(1995-),男,湖北襄阳人,硕士研究生,主要研究方向:机器学习、智能计算;张铭(1996-),女,福建莆田人,硕士研究生,主要研究方向:机器学习、智能计算;王李进(1977-),男,福建泉州人,教授,博士,主要研究方向:智能计算、智能信息处理;钟一文(1968-),男,福建上杭人,教授,博士,CCF会员,主要研究方向:计算智能、生物信息学、科学数据可视化。
  • 基金资助:

Abstract: The Closed-Loop Layout Problem (CLLP) is an NP-hard mixed optimization problem, in which an optimal placement order of facilities is found along adjustable rectangle loop with the objection of minimizing the total transport cost of material flow between facilities. In most of the existing methods, meta-heuristic algorithm was used to find the optimal order for the placement of facilities, and enumeration method was applied to find the optimal size of the rectangle loop, which causes extremely low efficiency. To solve this problem, a Hybrid Population-Based Incremental Learning (HPBIL) algorithm was proposed for solving CLLP. In the algorithm, the Discrete Population-Based Incremental Learning (DPBIL) operator and Continuous PBIL (CPBIL) operator were used separately to search the optimal placement order of facilities and the size of rectangle loop at the same time, which improved the efficiency of search. Furthermore, a local search algorithm was designed to optimize some good solutions in each iteration, enhancing the refinement ability. Simulation experiments were carried out on 13 CLLP instances. The results show that HPBIL algorithm finds the best new optimal layouts on 9 instances, and is significantly superior to the algorithms to be compared on the optimization ability for CLLP.

Key words: Population-Based Incremental Learning (PBIL) algorithm, Closed-Loop Layout Problem (CCLP), hybrid optimization, local search algorithm, meta-heuristic method

摘要: 闭环布局问题(CLLP)是一种NP-困难的混合优化问题,它在大小可调的矩形环上寻找设施最佳放置次序,目标是最小化设施之间物料流的运输成本。现有方法均采用元启发式算法来寻找最优的设施放置次序,并且通过枚举方法来获得最优的矩形环大小,而枚举方法的计算效率不高。为了解决这个问题,提出了求解CLLP的混合群体增量学习(HPBIL)算法,分别使用离散群体增量学习(DPBIL)算子和连续PBIL(CPBIL)算子同时对设施放置次序和矩形环大小进行优化,提高了搜索效率;同时还设计了一个局部搜索算法来优化每代中的部分优质解,以提高算法的求精能力。在13个CLLP测试实例上进行实验,结果表明HPBIL算法在9个测试实例上找到了新的最优布局,它对CLLP的寻优能力明显优于对比算法。

关键词: 群体增量学习算法, 闭环布局问题, 混合优化, 局部搜索算法, 元启发式方法

CLC Number: