基于区块挖掘与重组的启发式算法求解置换流水车间调度问题

doi:10.11896/JsJkx.190300151

摘要/Abstract

摘要： 组合优化广泛应用于任务问题,例如旅行推销员问题(Traveling Salesman Problem,TSP)、调度问题等。文中提出基于进化式的区块模型(Evolutionary-Based Block Model,EBBM)来提升优化算法的收敛效果,以避免陷入局部优化困境。区块的主要思想是从染色体中找到关键区块,并使用这些区块来改进进化式算法(Evolutionary Algorithms,EAs)以求解组合优化问题(Combinatorial Optimization Problems,COPs)。区块是一种挖掘染色体中基因对演化影响的信息,包含了对进化有帮助的信息以及阻碍进化的信息,所提方法借助区块信息指引算法的演化方向,通过两种不同信息的相互影响,不仅提高了算法的收敛速度,还提高了算法求解的多样性,从而达到求解稳定性高和求解质量优良的目标。文中提出的区块机制包括构建概率矩阵,通过关联规则生成区块并应用块来构建人造染色体。由于将区块作为构建人造解的基本单位,因此通过关联规则所挖掘的区块不仅具有多样性,还能按照设定置信度的大小控制演化过程所需的区块信息强度。最后为评估所提算法的求解能力,以置换流水车间调度问题(Permutation Flow-shop Scheduling Problem,PFSP)为测试的例题,采用平均误差率、最佳误差率以及收敛曲线图探讨算法的求解效果。实验结果表明,通过正反信息所产生的区块机制有助于提高收敛效果,且可避免陷入局部优化问题。

关键词: 关联规则, 区块挖掘与重组, 人造解, 演化式计算, 置换流水车间调度问题

Abstract: Combinatorial optimization is widely used in task problems,such as traveling salesman problem (TSP),scheduling problems.In this study,an evolutionary-based block model (EBBM) was proposed to enhance the speed of convergence so as to avoid premature convergenceproblem.The main idea of blocks is to find key blocks from chromosomes and use these blocks to improve evolutionary algorithms (EAs) to solve combinatorial optimization problems (COPs).Block is a kind of information that explores the effects of individual genes on the evolution of chromosomes,containing information that is helpful for evolution and information that hinders evolution.In this paper,these two different kinds of information are stored and used.The evolution direction of the information providing algorithm,through the influence of two different information,not only improves the convergence speed of the algorithm,but also improves the diversity of the algorithm solution,so as to achieve goals of high stability and good solution quality.The block mechanism proposed includs building a probability matrix,generating blocks by associated rule and applying blocks to construct artificial chromosomes.Since the block is used as the basic unit for constructing the artificial solution in this paper,the blocks mined by the association rules not only have diversity,but also control the block information strength required for the evolution process according to the set confidence level.Finally,in order to confirm the quality of solutions,the proposed approach is experimentally implemented on permutation flow-shop scheduling problem (PFSP).According to the average error rate,the optimal error rate and the convergence curve,the solution effect of the algorithm is discussed,the experimental results show that the block mechanism by positive and negative information is useful to improve the speed of convergence and avoid premature convergence problem.In additional,the results also demonstrate that BBEM is applicable and efficient to the COPs.

Key words: Artificial chromosome, Association rule, Block mining and restructuring, Evolutionary algorithm, Permutation flow-shop scheduling problem

中图分类号:

TP301.6

陈孟辉, 曹黔峰, 兰彦琦. 基于区块挖掘与重组的启发式算法求解置换流水车间调度问题[J]. 计算机科学, 2020, 47(6A): 108-113. https://doi.org/10.11896/JsJkx.190300151

CHEN Meng-hui, CAO Qian-feng and LAN Yan-qi. Heuristic Algorithm Based on Block Mining and Recombination for Permutation Flow-shop Scheduling Problem[J]. Computer Science, 2020, 47(6A): 108-113. https://doi.org/10.11896/JsJkx.190300151

参考文献

[1] GAREY M R,GRAHAM R L,JOHNSON D S.Some np-complete geometric problems//Proceedings of the 8th Annual ACM Symposium on Theory of Computing.New York:ACM,1976:10-22.
[2] CHAN F T S,CHUNG S H,CHAN P L Y.Application of genetic algorithms with dominant genes in a distributed scheduling problem in flexible manufacturing systems.International Journal of Production Research,2006,44(3):523-543.
[3] DORIGO M,MANIEZZO V,COLORNI A.The ant system:optimization by a colony of cooperating agents.IEEE Transactions on Systems,Man & Cybernetics,Part B:Cybernetics,1996,26(1):1-13.
[4] DASGUPTA D,JI Z,GONZLEZ F A.Artificial immune system research in the last five years//IEEE Congress on Evolutionary Computation.New York:IEEE,2003:123-130.
[5] BUDINICH M.A self-organizing neural network for the traveling salesman problem that is competitive with simulated annealing.Neural Computing,1996,8(2):416-424.
[6] LIU G Y,HE Y,FANG Y,et al.A novel adaptive search strategy of intensification and diversification in tabu search//Neural Networks and Signal Processing.New York:IEEE,2003:428-431.
[7] WALL M B.A genetic algorithm for resource-constrained scheduling.Cambridge:Massachusetts Institute of Technolo-gy,1996.
[8] HAO X,LIN L,GEN M,et al.Effective estimation of distribution algorithm for stochastic Job shop scheduling problem.Procedia Computer Science,2013,20:102-107.
[9] SANGKAVICHITR C,PRABHAS C.Fragment as a small evidence of the building blocks existence.Berlin:Exploitation of Linkage Learning in Evolutionary Algorithms,2010:25-44.
[10] CHEN M H,CHANG P C,TIWARI A,et al.Bi-variance estimation of distribution model to generate block.Paris World Academy of Science,Engineering & Technology.2013:77.
[11] RUIZ R,MAROTO C,ALCARAZ J.Two newrobust genetic algorithms for the flow shop scheduling problem.Omega,2006,34(5):461-476.
[12] CHANG P C,CHEN S S,FAN C Y.Mining gene structures to inJect artificial chromosomes for genetic algorithm in single machine scheduling problems.Applied Soft Computing,2008,8(1):767-777.
[13] CHEN Y M,CHEN M C,CHANG P C,et al.Extended artificial chromosome genetic algorithm for permutation flow shopschedu-ling problems.Computers & Industrial Engineering,2012,62(2):536-545.
[14] PELIKAN M.Bayesian optimization algorithm.Berlin: Springer,2005:31-48.
[15] CHANG P C,WANG Y W,LIU C H.New operators for faster convergence and better solution quality in modified genetic algorithm//Advances in Natural Computation.Springer Berlin Heidelberg.Berlin:Springer,2005:983-991.
[16] CHANG P C,HUANG W H,WU J L,et al.A block mining and re-combination enhanced genetic algorithm for the permutation flow shop scheduling problem.International Journal of Production Economics,2013,141(1):45-55.
[17] BALUJA S.Population-based incremental learning:a method for integrating genetic search based function optimization and competitive learning.Computer Sciences & Machine Learning,1994.
[18] CHANG P C,CHEN M H,TIWARI M K,et al.A block-based evolutionary algorithm for flow-shop scheduling problem.Applied Soft Computing,2013,13(12):4536-4547.
[19] TAN P N,STEINBACH M,KUMAR V.Introduction to data mining.Addison Wesley,2006.
[20] AGRAWAL R,MIELISKIT,SWAMI A.Mining association rules between sets of items in large databases//ACM SIGMOD Record.New York:ACM,1993:207-216.
[21] MCNICHOLAS P D,MURPHY T B,O’REGAN M.Standardi-sing the lift of an association rule.Computational Statistics &Data Analysis,2008,52(10):4712-4721.
[22] REZA HEJAZI S,SAGHAFIAN S.Flow shop-scheduling prob lems with makespan criterion:a review.International Journal of Production Research,2005,43(14):2895-2929.
[23] REEVES C R.A genetic algorithm for flow shop sequencing .Computers & Operations Research,1995,22(1):5-13.
[24] LIAN Z,GU X,JIAO B.A similar particle swarm optimization algorithm for permutation flow shop scheduling to minimize makespan.Applied Mathematics & Computation,2006,175(1):773-785.
[25] SKELLAM J G.Studies in statistical ecology.Spatial Pattern,Biometrika,1952,39(3/4):346-362.
[26] MILLER B L,GOLDBERG D E.Genetic algorithms,tournament selection,and the effects of noise.Complex Systems,1995,9(3):193-212.
[27] TAILLARD E.Benchmarks for basic scheduling problems.European Journal of Operational Research,1993,64(2):278-285.
[28] CHANG P C,CHEN M H.A block based estimation of distribution algorithm using bivariate model for scheduling problems.Soft Computing,2014,18(6):1177-1188.
[29] HSU C Y,CHANG P C,CHEN M H.A linkage mining in block-based evolutionary algorithm for permutation flowshop scheduling problem.Computers & Industrial Engineering,2015,83:159-171.

相关文章 15

[1]	曹扬晨, 朱国胜, 孙文和, 吴善超. 未知网络攻击识别关键技术研究 Study on Key Technologies of Unknown Network Attack Identification 计算机科学, 2022, 49(6A): 581-587. https://doi.org/10.11896/jsjkx.210400044
[2]	徐慧慧, 晏华. 基于相对危险度的儿童先心病风险因素分析算法 Relative Risk Degree Based Risk Factor Analysis Algorithm for Congenital Heart Disease in Children 计算机科学, 2021, 48(6): 210-214. https://doi.org/10.11896/jsjkx.200500082
[3]	沈夏炯, 杨继勇, 张磊. 基于不相关属性集合的属性探索算法 Attribute Exploration Algorithm Based on Unrelated Attribute Set 计算机科学, 2021, 48(4): 54-62. https://doi.org/10.11896/jsjkx.200800082
[4]	张素梅, 张波涛. 一种基于量子耗散粒子群的评估模型构建方法 Evaluation Model Construction Method Based on Quantum Dissipative Particle Swarm Optimization 计算机科学, 2020, 47(6A): 84-88. https://doi.org/10.11896/JsJkx.190900148
[5]	崔巍, 贾晓琳, 樊帅帅, 朱晓燕. 一种新的不均衡关联分类算法 New Associative Classification Algorithm for Imbalanced Data 计算机科学, 2020, 47(6A): 488-493. https://doi.org/10.11896/JsJkx.190600132
[6]	王青松, 姜富山, 李菲. 大数据环境下基于关联规则的多标签学习算法 Multi-label Learning Algorithm Based on Association Rules in Big Data Environment 计算机科学, 2020, 47(5): 90-95. https://doi.org/10.11896/jsjkx.190300150
[7]	朱岸青, 李帅, 唐晓东. Spark平台中的并行化FP_growth关联规则挖掘方法 Parallel FP_growth Association Rules Mining Method on Spark Platform 计算机科学, 2020, 47(12): 139-143. https://doi.org/10.11896/jsjkx.191000110
[8]	张蕾,蔡明. 基于主题融合和关联规则挖掘的图像标注 Image Annotation Based on Topic Fusion and Frequent Patterns Mining 计算机科学, 2019, 46(7): 246-251. https://doi.org/10.11896/j.issn.1002-137X.2019.07.037
[9]	陆鑫赟, 王兴芬. 基于领域关联冗余的教务数据关联规则挖掘 Educational Administration Data Mining of Association Rules Based on Domain Association Redundancy 计算机科学, 2019, 46(6A): 427-430.
[10]	张维国. 面向知识推荐服务的选课决策 Decision Making of Course Selection Oriented by Knowledge Recommendation Service 计算机科学, 2019, 46(6A): 507-510.
[11]	李智星, 任诗雅, 王化明, 沈柯. 基于非结构化文本增强关联规则的知识推理方法 Knowledge Reasoning Method Based on Unstructured Text-enhanced Association Rules 计算机科学, 2019, 46(11): 209-215. https://doi.org/10.11896/jsjkx.181001939
[12]	王斌, 马俊杰, 房新秀, 魏天佑. 基于时间戳和垂直格式的关联规则挖掘算法 Association Rule Mining Algorithm Based on Timestamp and Vertical Format 计算机科学, 2019, 46(10): 71-76. https://doi.org/10.11896/jsjkx.190100223
[13]	贾熹滨,叶颖婕,陈军成. 基于关联规则的交通事故影响因素的挖掘 Influence Factors Mining of Traffic Accidents Based on Association Rules 计算机科学, 2018, 45(6A): 447-452.
[14]	丁勇, 朱长水, 武玉艳. 一种基于Hadoop的关联规则挖掘算法 Association Rule Mining Algorithm Based on Hadoop 计算机科学, 2018, 45(11A): 409-411.
[15]	丁铛,张志飞,苗夺谦,陈岳峰. 基于消费者行为的点餐推荐算法 Ordering Recommender Algorithm Based on Consumers’ Behavior 计算机科学, 2017, 44(Z11): 46-50. https://doi.org/10.11896/j.issn.1002-137X.2017.11A.008

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed