In order to solve the problem of efficiently assigning tasks in an ad-hoc mobile cloud( AMC),a task assignment algorithm based on the heuristic algorithm is proposed. The proposed task assignment algorithm based on pa...In order to solve the problem of efficiently assigning tasks in an ad-hoc mobile cloud( AMC),a task assignment algorithm based on the heuristic algorithm is proposed. The proposed task assignment algorithm based on particle swarm optimization and simulated annealing( PSO-SA) transforms the dependencies between tasks into a directed acyclic graph( DAG) model. The number in each node represents the computation workload of each task and the number on each edge represents the workload produced by the transmission. In order to simulate the environment of task assignment in AMC,mathematical models are developed to describe the dependencies between tasks and the costs of each task are defined. PSO-SA is used to make the decision for task assignment and for minimizing the cost of all devices,which includes the energy consumption and time delay of all devices.PSO-SA also takes the advantage of both particle swarm optimization and simulated annealing by selecting an optimal solution with a certain probability to avoid falling into local optimal solution and to guarantee the convergence speed. The simulation results show that compared with other existing algorithms,the PSO-SA has a smaller cost and the result of PSO-SA can be very close to the optimal solution.展开更多
An ant colony optimization （ACO）-simulated annealing （SA）-based algorithm is developed for the target assignment problem （TAP） in the air defense （AD） command and control （C2） system of surface to air missi...An ant colony optimization （ACO）-simulated annealing （SA）-based algorithm is developed for the target assignment problem （TAP） in the air defense （AD） command and control （C2） system of surface to air missile （SAM） tactical unit. The accomplishment process of target assignment （TA） task is analyzed. A firing advantage degree （FAD） concept of fire unit （FU） intercepting targets is put forward and its evaluation model is established by using a linear weighted synthetic method. A TA optimization model is presented and its solving algorithms are designed respectively based on ACO and SA. A hybrid optimization strategy is presented and developed synthesizing the merits of ACO and SA. The simulation examples show that the model and algorithms can meet the solving requirement of TAP in AD combat.展开更多
The allocation of heterogeneous battlefield resources is crucial in Command and Control(C2).Balancing multiple competing objectives under complex constraints so as to provide decisionmakers with diverse feasible candi...The allocation of heterogeneous battlefield resources is crucial in Command and Control(C2).Balancing multiple competing objectives under complex constraints so as to provide decisionmakers with diverse feasible candidate decision schemes remains an urgent challenge.Based on these requirements,a constrained multi-objective multi-stage weapon-target assignment(CMOMWTA)model is established in this paper.To solve this problem,three constraint-feature-guided multi-objective evolutionary algorithms(CFG-MOEAs)are proposed under three typical multi-objective evolutionary frameworks(i.e.,NSGA-Ⅱ,NSGA-Ⅲ,and MOEA/D)to obtain various high-quality candidate decision schemes.Firstly,a constraint-feature-guided reproduction strategy incorporating crossover,mutation,and repair is developed to handle complex constraints.It extracts common row and column features from different linear constraints to generate the feasible offspring population.Then,a variable-length integer encoding method is adopted to concisely denote the decision schemes.Moreover,a hybrid initialization method incorporating both heuristic methods and random sampling is designed to better guide the population.Systemic experiments are conducted on three CFG-MOEAs to verify their effectiveness.The superior algorithm CFG-NSGA-Ⅱamong three CFG-MOEAs is compared with two state-of-the-art CMOMWTA algorithms,and extensive experimental results demonstrate the effectiveness and superiority of CFG-NSGA-Ⅱ.展开更多
Economic globalization has transformed many manufacturing enterprises from a single-plant production mode to a multi-plant cooperative production mode.The distributed flexible job-shop scheduling problem(DFJSP)has bec...Economic globalization has transformed many manufacturing enterprises from a single-plant production mode to a multi-plant cooperative production mode.The distributed flexible job-shop scheduling problem(DFJSP)has become a research hot topic in the field of scheduling because its production is closer to reality.The research of DFJSP is of great significance to the organization and management of actual production process.To solve the heterogeneous DFJSP with minimal completion time,a hybrid chemical reaction optimization(HCRO)algorithm is proposed in this paper.Firstly,a novel encoding-decoding method for flexible manufacturing unit(FMU)is designed.Secondly,half of initial populations are generated by scheduling rule.Combined with the new solution acceptance method of simulated annealing(SA)algorithm,an improved method of critical-FMU is designed to improve the global and local search ability of the algorithm.Finally,the elitist selection strategy and the orthogonal experimental method are introduced to the algorithm to improve the convergence speed and optimize the algorithm parameters.In the experimental part,the effectiveness of the simulated annealing algorithm and the critical-FMU refinement methods is firstly verified.Secondly,in the comparison with other existing algorithms,the proposed optimal scheduling algorithm is not only effective in homogeneous FMUs examples,but also superior to existing algorithms in heterogeneous FMUs arithmetic cases.展开更多
A real-life problem is the rostering of nurses at hospitals.It is a famous nondeterministic,polynomial time(NP)-hard combinatorial optimization problem.Handling the real-world nurse rostering problem(NRP)constraints i...A real-life problem is the rostering of nurses at hospitals.It is a famous nondeterministic,polynomial time(NP)-hard combinatorial optimization problem.Handling the real-world nurse rostering problem(NRP)constraints in distributing workload equally between available nurses is still a difficult task to achieve.The international shortage of nurses,in addition to the spread of COVID-19,has made it more difficult to provide convenient rosters for nurses.Based on the literature,heuristic-based methods are the most commonly used methods to solve the NRP due to its computational complexity,especially for large rosters.Heuristic-based algorithms in general have problems striking the balance between diversification and intensification.Therefore,this paper aims to introduce a novel metaheuristic hybridization that combines the enhanced harmony search algorithm(EHSA)with the simulated annealing(SA)algorithm called the annealing harmony search algorithm(AHSA).The AHSA is used to solve NRP from a Malaysian hospital.The AHSA performance is compared to the EHSA,climbing harmony search algorithm(CHSA),deluge harmony search algorithm(DHSA),and harmony annealing search algorithm(HAS).The results show that the AHSA performs better than the other compared algorithms for all the tested instances where the best ever results reported for the UKMMC dataset.展开更多
Team Formation(TF)is considered one of the most significant problems in computer science and optimization.TF is defined as forming the best team of experts in a social network to complete a task with least cost.Many r...Team Formation(TF)is considered one of the most significant problems in computer science and optimization.TF is defined as forming the best team of experts in a social network to complete a task with least cost.Many real-world problems,such as task assignment,vehicle routing,nurse scheduling,resource allocation,and airline crew scheduling,are based on the TF problem.TF has been shown to be a Nondeterministic Polynomial time(NP)problem,and high-dimensional problem with several local optima that can be solved using efficient approximation algorithms.This paper proposes two improved swarm-based algorithms for solving team formation problem.The first algorithm,entitled Hybrid Heap-Based Optimizer with Simulated Annealing Algorithm(HBOSA),uses a single crossover operator to improve the performance of a standard heap-based optimizer(HBO)algorithm.It also employs the simulated annealing(SA)approach to improve model convergence and avoid local minima trapping.The second algorithm is the Chaotic Heap-based Optimizer Algorithm(CHBO).CHBO aids in the discovery of new solutions in the search space by directing particles to different regions of the search space.During HBO’s optimization process,a logistic chaotic map is used.The performance of the two proposed algorithms(HBOSA)and(CHBO)is evaluated using thirteen benchmark functions and tested in solving the TF problem with varying number of experts and skills.Furthermore,the proposed algorithms were compared to well-known optimization algorithms such as the Heap-Based Optimizer(HBO),Developed Simulated Annealing(DSA),Particle SwarmOptimization(PSO),GreyWolfOptimization(GWO),and Genetic Algorithm(GA).Finally,the proposed algorithms were applied to a real-world benchmark dataset known as the Internet Movie Database(IMDB).The simulation results revealed that the proposed algorithms outperformed the compared algorithms in terms of efficiency and performance,with fast convergence to the global minimum.展开更多
Recent studies employing deep learning to solve the traveling salesman problem(TSP)have mainly focused on learning construction heuristics.Such methods can improve TSP solutions,but still depend on additional programs...Recent studies employing deep learning to solve the traveling salesman problem(TSP)have mainly focused on learning construction heuristics.Such methods can improve TSP solutions,but still depend on additional programs.However,methods that focus on learning improvement heuristics to iteratively refine solutions remain insufficient.Traditional improvement heuristics are guided by a manually designed search strategy and may only achieve limited improvements.This paper proposes a novel framework for learning improvement heuristics,which automatically discovers better improvement policies for heuristics to iteratively solve the TSP.Our framework first designs a new architecture based on a transformer model to make the policy network parameterized,which introduces an action-dropout layer to prevent action selection from overfitting.It then proposes a deep reinforcement learning approach integrating a simulated annealing mechanism(named RL-SA)to learn the pairwise selected policy,aiming to improve the 2-opt algorithm's performance.The RL-SA leverages the whale optimization algorithm to generate initial solutions for better sampling efficiency and uses the Gaussian perturbation strategy to tackle the sparse reward problem of reinforcement learning.The experiment results show that the proposed approach is significantly superior to the state-of-the-art learning-based methods,and further reduces the gap between learning-based methods and highly optimized solvers in the benchmark datasets.Moreover,our pre-trained model M can be applied to guide the SA algorithm(named M-SA(ours)),which performs better than existing deep models in small-,medium-,and large-scale TSPLIB datasets.Additionally,the M-SA(ours)achieves excellent generalization performance in a real-world dataset on global liner shipping routes,with the optimization percentages in distance reduction ranging from3.52%to 17.99%.展开更多
This paper presents a comparative study of evolutionary algorithms which are considered to be effective in solving the multilevel lot-sizing problem in material requirement planning(MRP)systems.Three evolutionary algo...This paper presents a comparative study of evolutionary algorithms which are considered to be effective in solving the multilevel lot-sizing problem in material requirement planning(MRP)systems.Three evolutionary algorithms(simulated annealing(SA),particle swarm optimization(PSO)and genetic algorithm(GA))are provided.For evaluating the performances of algorithms,the distribution of total cost(objective function)and the average computational time are compared.As a result,both GA and PSO have better cost performances with lower average total costs and smaller standard deviations.When the scale of the multilevel lot-sizing problem becomes larger,PSO is of a shorter computational time.展开更多
基金The National Natural Science Foundation of China(No.61741102,61471164,61601122)the Fundamental Research Funds for the Central Universities(No.SJLX_160040)
文摘In order to solve the problem of efficiently assigning tasks in an ad-hoc mobile cloud( AMC),a task assignment algorithm based on the heuristic algorithm is proposed. The proposed task assignment algorithm based on particle swarm optimization and simulated annealing( PSO-SA) transforms the dependencies between tasks into a directed acyclic graph( DAG) model. The number in each node represents the computation workload of each task and the number on each edge represents the workload produced by the transmission. In order to simulate the environment of task assignment in AMC,mathematical models are developed to describe the dependencies between tasks and the costs of each task are defined. PSO-SA is used to make the decision for task assignment and for minimizing the cost of all devices,which includes the energy consumption and time delay of all devices.PSO-SA also takes the advantage of both particle swarm optimization and simulated annealing by selecting an optimal solution with a certain probability to avoid falling into local optimal solution and to guarantee the convergence speed. The simulation results show that compared with other existing algorithms,the PSO-SA has a smaller cost and the result of PSO-SA can be very close to the optimal solution.
基金supported by the National Aviation Science Foundation of China(20090196002)
文摘An ant colony optimization （ACO）-simulated annealing （SA）-based algorithm is developed for the target assignment problem （TAP） in the air defense （AD） command and control （C2） system of surface to air missile （SAM） tactical unit. The accomplishment process of target assignment （TA） task is analyzed. A firing advantage degree （FAD） concept of fire unit （FU） intercepting targets is put forward and its evaluation model is established by using a linear weighted synthetic method. A TA optimization model is presented and its solving algorithms are designed respectively based on ACO and SA. A hybrid optimization strategy is presented and developed synthesizing the merits of ACO and SA. The simulation examples show that the model and algorithms can meet the solving requirement of TAP in AD combat.
基金supported by the National Science Fund of China under Grant Nos.62425304 and 62025301the Basic Science Center Programs of NSFC under Grant No.62088101+1 种基金Shanghai Municipal Science and Technology Major Project under Grant No.2021SHZDZX0100Shanghai Municipal Commission of Science and Technology Project under Grant No.19511132101。
文摘The allocation of heterogeneous battlefield resources is crucial in Command and Control(C2).Balancing multiple competing objectives under complex constraints so as to provide decisionmakers with diverse feasible candidate decision schemes remains an urgent challenge.Based on these requirements,a constrained multi-objective multi-stage weapon-target assignment(CMOMWTA)model is established in this paper.To solve this problem,three constraint-feature-guided multi-objective evolutionary algorithms(CFG-MOEAs)are proposed under three typical multi-objective evolutionary frameworks(i.e.,NSGA-Ⅱ,NSGA-Ⅲ,and MOEA/D)to obtain various high-quality candidate decision schemes.Firstly,a constraint-feature-guided reproduction strategy incorporating crossover,mutation,and repair is developed to handle complex constraints.It extracts common row and column features from different linear constraints to generate the feasible offspring population.Then,a variable-length integer encoding method is adopted to concisely denote the decision schemes.Moreover,a hybrid initialization method incorporating both heuristic methods and random sampling is designed to better guide the population.Systemic experiments are conducted on three CFG-MOEAs to verify their effectiveness.The superior algorithm CFG-NSGA-Ⅱamong three CFG-MOEAs is compared with two state-of-the-art CMOMWTA algorithms,and extensive experimental results demonstrate the effectiveness and superiority of CFG-NSGA-Ⅱ.
基金This work was supported by the National Natural Science Foundation of China(Nos.61973120,62076095,61673175,and 61573144).
文摘Economic globalization has transformed many manufacturing enterprises from a single-plant production mode to a multi-plant cooperative production mode.The distributed flexible job-shop scheduling problem(DFJSP)has become a research hot topic in the field of scheduling because its production is closer to reality.The research of DFJSP is of great significance to the organization and management of actual production process.To solve the heterogeneous DFJSP with minimal completion time,a hybrid chemical reaction optimization(HCRO)algorithm is proposed in this paper.Firstly,a novel encoding-decoding method for flexible manufacturing unit(FMU)is designed.Secondly,half of initial populations are generated by scheduling rule.Combined with the new solution acceptance method of simulated annealing(SA)algorithm,an improved method of critical-FMU is designed to improve the global and local search ability of the algorithm.Finally,the elitist selection strategy and the orthogonal experimental method are introduced to the algorithm to improve the convergence speed and optimize the algorithm parameters.In the experimental part,the effectiveness of the simulated annealing algorithm and the critical-FMU refinement methods is firstly verified.Secondly,in the comparison with other existing algorithms,the proposed optimal scheduling algorithm is not only effective in homogeneous FMUs examples,but also superior to existing algorithms in heterogeneous FMUs arithmetic cases.
文摘A real-life problem is the rostering of nurses at hospitals.It is a famous nondeterministic,polynomial time(NP)-hard combinatorial optimization problem.Handling the real-world nurse rostering problem(NRP)constraints in distributing workload equally between available nurses is still a difficult task to achieve.The international shortage of nurses,in addition to the spread of COVID-19,has made it more difficult to provide convenient rosters for nurses.Based on the literature,heuristic-based methods are the most commonly used methods to solve the NRP due to its computational complexity,especially for large rosters.Heuristic-based algorithms in general have problems striking the balance between diversification and intensification.Therefore,this paper aims to introduce a novel metaheuristic hybridization that combines the enhanced harmony search algorithm(EHSA)with the simulated annealing(SA)algorithm called the annealing harmony search algorithm(AHSA).The AHSA is used to solve NRP from a Malaysian hospital.The AHSA performance is compared to the EHSA,climbing harmony search algorithm(CHSA),deluge harmony search algorithm(DHSA),and harmony annealing search algorithm(HAS).The results show that the AHSA performs better than the other compared algorithms for all the tested instances where the best ever results reported for the UKMMC dataset.
文摘Team Formation(TF)is considered one of the most significant problems in computer science and optimization.TF is defined as forming the best team of experts in a social network to complete a task with least cost.Many real-world problems,such as task assignment,vehicle routing,nurse scheduling,resource allocation,and airline crew scheduling,are based on the TF problem.TF has been shown to be a Nondeterministic Polynomial time(NP)problem,and high-dimensional problem with several local optima that can be solved using efficient approximation algorithms.This paper proposes two improved swarm-based algorithms for solving team formation problem.The first algorithm,entitled Hybrid Heap-Based Optimizer with Simulated Annealing Algorithm(HBOSA),uses a single crossover operator to improve the performance of a standard heap-based optimizer(HBO)algorithm.It also employs the simulated annealing(SA)approach to improve model convergence and avoid local minima trapping.The second algorithm is the Chaotic Heap-based Optimizer Algorithm(CHBO).CHBO aids in the discovery of new solutions in the search space by directing particles to different regions of the search space.During HBO’s optimization process,a logistic chaotic map is used.The performance of the two proposed algorithms(HBOSA)and(CHBO)is evaluated using thirteen benchmark functions and tested in solving the TF problem with varying number of experts and skills.Furthermore,the proposed algorithms were compared to well-known optimization algorithms such as the Heap-Based Optimizer(HBO),Developed Simulated Annealing(DSA),Particle SwarmOptimization(PSO),GreyWolfOptimization(GWO),and Genetic Algorithm(GA).Finally,the proposed algorithms were applied to a real-world benchmark dataset known as the Internet Movie Database(IMDB).The simulation results revealed that the proposed algorithms outperformed the compared algorithms in terms of efficiency and performance,with fast convergence to the global minimum.
基金Project supported by the National Natural Science Foundation of China(Grant Nos.72101046 and 61672128)。
文摘Recent studies employing deep learning to solve the traveling salesman problem(TSP)have mainly focused on learning construction heuristics.Such methods can improve TSP solutions,but still depend on additional programs.However,methods that focus on learning improvement heuristics to iteratively refine solutions remain insufficient.Traditional improvement heuristics are guided by a manually designed search strategy and may only achieve limited improvements.This paper proposes a novel framework for learning improvement heuristics,which automatically discovers better improvement policies for heuristics to iteratively solve the TSP.Our framework first designs a new architecture based on a transformer model to make the policy network parameterized,which introduces an action-dropout layer to prevent action selection from overfitting.It then proposes a deep reinforcement learning approach integrating a simulated annealing mechanism(named RL-SA)to learn the pairwise selected policy,aiming to improve the 2-opt algorithm's performance.The RL-SA leverages the whale optimization algorithm to generate initial solutions for better sampling efficiency and uses the Gaussian perturbation strategy to tackle the sparse reward problem of reinforcement learning.The experiment results show that the proposed approach is significantly superior to the state-of-the-art learning-based methods,and further reduces the gap between learning-based methods and highly optimized solvers in the benchmark datasets.Moreover,our pre-trained model M can be applied to guide the SA algorithm(named M-SA(ours)),which performs better than existing deep models in small-,medium-,and large-scale TSPLIB datasets.Additionally,the M-SA(ours)achieves excellent generalization performance in a real-world dataset on global liner shipping routes,with the optimization percentages in distance reduction ranging from3.52%to 17.99%.
基金the National Natural Science Foundation of China(No.70971017)the Humanities and Social Sciences Project of Ministry of Education(No.10YJC630009)+1 种基金the Social Science Fund of Zhejiang Province(No.10CGGL21YBQ)the Natural Science Foundation of Zhejiang Province(No.Y1100854)
文摘This paper presents a comparative study of evolutionary algorithms which are considered to be effective in solving the multilevel lot-sizing problem in material requirement planning(MRP)systems.Three evolutionary algorithms(simulated annealing(SA),particle swarm optimization(PSO)and genetic algorithm(GA))are provided.For evaluating the performances of algorithms,the distribution of total cost(objective function)and the average computational time are compared.As a result,both GA and PSO have better cost performances with lower average total costs and smaller standard deviations.When the scale of the multilevel lot-sizing problem becomes larger,PSO is of a shorter computational time.
