Artificial bee colony(ABC) is one of the most popular swarm intelligence optimization algorithms which have been widely used in numerical optimization and engineering applications. However, there are still deficiencie...Artificial bee colony(ABC) is one of the most popular swarm intelligence optimization algorithms which have been widely used in numerical optimization and engineering applications. However, there are still deficiencies in ABC regarding its local search ability and global search efficiency. Aiming at these deficiencies,an ABC variant named hybrid ABC(HABC) algorithm is proposed.Firstly, the variable neighborhood search factor is added to the solution search equation, which can enhance the local search ability and increase the population diversity. Secondly, inspired by the neuroscience investigation of real honeybees, the memory mechanism is put forward, which assumes the artificial bees can remember their past successful experiences and further guide the subsequent foraging behavior. The proposed memory mechanism is used to improve the global search efficiency. Finally, the results of comparison on a set of ten benchmark functions demonstrate the superiority of HABC.展开更多
A new local search method with hybrid neighborhood for Job shop scheduling problem is developed. The proposed hybrid neighborhood is not only efficient in local search, but also can help overcome entrapments while sea...A new local search method with hybrid neighborhood for Job shop scheduling problem is developed. The proposed hybrid neighborhood is not only efficient in local search, but also can help overcome entrapments while search procedure get trapped at local optima and carry the search to areas of the feasible set with better prospect. New strategies used for breaking out of entrapments are presented and they are helpful for the procedure to improve local optima. A performance comparison of the proposed method with some best-performing algorithms on all 10-job, 10-machine benchmark problems and the other two problems generated by Fisher and Thompson (ie., FT6 and FT20)is made. The experiment results show the better optimal performance of the proposed algorithm.展开更多
In a local search algorithm,one of its most important features is the definition of its neighborhood which is crucial to the algorithm's performance.In this paper,we present an analysis of neighborhood combination...In a local search algorithm,one of its most important features is the definition of its neighborhood which is crucial to the algorithm's performance.In this paper,we present an analysis of neighborhood combination search for solv-ing the single-machine scheduling problem with sequence-dependent setup time with the objective of minimizing total weighted tardiness(SMSWT).First,We propose a new neighborhood structure named Block Swap(B1)which can be con-sidered as an extension of the previously widely used Block Move(B2)neighborhood,and a fast incremental evaluation technique to enhance its evaluation efficiency.Second,based on the Block Swap and Block Move neighborhoods,we present two kinds of neighborhood structures:neighborhood union(denoted by B1UB2)and token-ring search(denoted by B1→B2),both of which are combinations of B1 and B2.Third,we incorporate the neighborhood union and token-ring search into two representative metaheuristic algorithms:the Iterated Local Search Algorithm(ILSnew)and the Hybrid Evolutionary Algorithm(HEA_(new))to investigate the performance of the neighborhood union and token-ring search.Exten-sive experiments show the competitiveness of the token-ring search combination mechanism of the two neighborhoods.Tested on the 120 public benchmark instances,our HEA_(new)has a highly competitive performance in solution quality and computational time compared with both the exact algorithms and recent metaheuristics.We have also tested the HEA,new algorithm with the selected neighborhood combination search to deal with the 64 public benchmark instances of the single-machine scheduling problem with sequence-dependent setup time.HEAnew is able to match the optimal or the best known results for all the 64 instances.In particular,the computational time for reaching the best well-known results for five chal-lenging instances is reduced by at least 61.25%.展开更多
邻域搜索算法的关键是邻域结构的选择,但每次迭代搜索的时间较长,缺少在解空间内自主搜索的能力.利用深度强化学习(DRL)模型对邻域搜索算法进行改进,设计了一个新的深度混合型邻域搜索(DHNS)模型来求解带容量的车辆路径问题(CVRP).首先...邻域搜索算法的关键是邻域结构的选择,但每次迭代搜索的时间较长,缺少在解空间内自主搜索的能力.利用深度强化学习(DRL)模型对邻域搜索算法进行改进,设计了一个新的深度混合型邻域搜索(DHNS)模型来求解带容量的车辆路径问题(CVRP).首先,利用贪婪算法为DRL模型提供初始解;其次,采用指针网络以及Transformer混合编码,利用不同网络的优势,深层次地提取节点特征信息;最后,将修复算子的修复过程转至DHNS模型,自动完成邻域搜索修复解的过程,扩大解空间的自主搜索能力.同时,针对混合编码中复杂传输机制以及解码输出误导性信息的问题,进一步在编码和解码过程中添加AOA(Attention on Attention)机制.AOA负责筛选有价值的信息,过滤不相关或误导性信息,有效刻画了注意力结果和查询之间的相关性,并对节点间的关系进行建模.实验结果表明,DHNS模型在100规模CVRP的优化效果上,优于现有DRL模型和部分传统算法.采用CVRPlib数据集中的算例对该算法的效能进行验证,结果表明,采用DHNS模型能够极大地提升路径问题的优化效能.展开更多
基金supported by the National Natural Science Foundation of China(7177121671701209)
文摘Artificial bee colony(ABC) is one of the most popular swarm intelligence optimization algorithms which have been widely used in numerical optimization and engineering applications. However, there are still deficiencies in ABC regarding its local search ability and global search efficiency. Aiming at these deficiencies,an ABC variant named hybrid ABC(HABC) algorithm is proposed.Firstly, the variable neighborhood search factor is added to the solution search equation, which can enhance the local search ability and increase the population diversity. Secondly, inspired by the neuroscience investigation of real honeybees, the memory mechanism is put forward, which assumes the artificial bees can remember their past successful experiences and further guide the subsequent foraging behavior. The proposed memory mechanism is used to improve the global search efficiency. Finally, the results of comparison on a set of ten benchmark functions demonstrate the superiority of HABC.
基金TheNationalGrandFundamentalResearch973ProgramofChina (No .G19980 30 6 0 0 )
文摘A new local search method with hybrid neighborhood for Job shop scheduling problem is developed. The proposed hybrid neighborhood is not only efficient in local search, but also can help overcome entrapments while search procedure get trapped at local optima and carry the search to areas of the feasible set with better prospect. New strategies used for breaking out of entrapments are presented and they are helpful for the procedure to improve local optima. A performance comparison of the proposed method with some best-performing algorithms on all 10-job, 10-machine benchmark problems and the other two problems generated by Fisher and Thompson (ie., FT6 and FT20)is made. The experiment results show the better optimal performance of the proposed algorithm.
基金supported by the National Natural Science Foundation of China under Grant Nos.62202192,71801218,and 72101094.
文摘In a local search algorithm,one of its most important features is the definition of its neighborhood which is crucial to the algorithm's performance.In this paper,we present an analysis of neighborhood combination search for solv-ing the single-machine scheduling problem with sequence-dependent setup time with the objective of minimizing total weighted tardiness(SMSWT).First,We propose a new neighborhood structure named Block Swap(B1)which can be con-sidered as an extension of the previously widely used Block Move(B2)neighborhood,and a fast incremental evaluation technique to enhance its evaluation efficiency.Second,based on the Block Swap and Block Move neighborhoods,we present two kinds of neighborhood structures:neighborhood union(denoted by B1UB2)and token-ring search(denoted by B1→B2),both of which are combinations of B1 and B2.Third,we incorporate the neighborhood union and token-ring search into two representative metaheuristic algorithms:the Iterated Local Search Algorithm(ILSnew)and the Hybrid Evolutionary Algorithm(HEA_(new))to investigate the performance of the neighborhood union and token-ring search.Exten-sive experiments show the competitiveness of the token-ring search combination mechanism of the two neighborhoods.Tested on the 120 public benchmark instances,our HEA_(new)has a highly competitive performance in solution quality and computational time compared with both the exact algorithms and recent metaheuristics.We have also tested the HEA,new algorithm with the selected neighborhood combination search to deal with the 64 public benchmark instances of the single-machine scheduling problem with sequence-dependent setup time.HEAnew is able to match the optimal or the best known results for all the 64 instances.In particular,the computational time for reaching the best well-known results for five chal-lenging instances is reduced by at least 61.25%.
文摘邻域搜索算法的关键是邻域结构的选择,但每次迭代搜索的时间较长,缺少在解空间内自主搜索的能力.利用深度强化学习(DRL)模型对邻域搜索算法进行改进,设计了一个新的深度混合型邻域搜索(DHNS)模型来求解带容量的车辆路径问题(CVRP).首先,利用贪婪算法为DRL模型提供初始解;其次,采用指针网络以及Transformer混合编码,利用不同网络的优势,深层次地提取节点特征信息;最后,将修复算子的修复过程转至DHNS模型,自动完成邻域搜索修复解的过程,扩大解空间的自主搜索能力.同时,针对混合编码中复杂传输机制以及解码输出误导性信息的问题,进一步在编码和解码过程中添加AOA(Attention on Attention)机制.AOA负责筛选有价值的信息,过滤不相关或误导性信息,有效刻画了注意力结果和查询之间的相关性,并对节点间的关系进行建模.实验结果表明,DHNS模型在100规模CVRP的优化效果上,优于现有DRL模型和部分传统算法.采用CVRPlib数据集中的算例对该算法的效能进行验证,结果表明,采用DHNS模型能够极大地提升路径问题的优化效能.
