This paper presents a parallel composite local search algorithm based on multiple search neighborhoods to solve a special kind of timetable problem. The new algorithm can also effectively solve those problems that can...This paper presents a parallel composite local search algorithm based on multiple search neighborhoods to solve a special kind of timetable problem. The new algorithm can also effectively solve those problems that can be solved by general local search algorithms. Experimental results show that the new algorithm can generate better solutions than general local search algorithms.展开更多
This paper presents an optimization technique coupling two optimization techniques for solving Economic Emission Load Dispatch Optimization Problem EELD. The proposed approach integrates the merits of both genetic alg...This paper presents an optimization technique coupling two optimization techniques for solving Economic Emission Load Dispatch Optimization Problem EELD. The proposed approach integrates the merits of both genetic algorithm (GA) and local search (LS), where it maintains a finite-sized archive of non-dominated solutions which gets iteratively updated in the presence of new solutions based on the concept of ε-dominance. To improve the solution quality, local search technique was applied as neighborhood search engine, where it intends to explore the less-crowded area in the current archive to possibly obtain more non-dominated solutions. TOPSIS technique can incorporate relative weights of criterion importance, which has been implemented to identify best compromise solution, which will satisfy the different goals to some extent. Several optimization runs of the proposed approach are carried out on the standard IEEE 30-bus 6-genrator test system. The comparison demonstrates the superiority of the proposed approach and confirms its potential to solve the multiobjective EELD problem.展开更多
We apply the transitionless driving on the local adiabatic quantum search algorithm to speed up the adiabatic process. By studying quantum dynamics of the adiabatic search algorithm with the equivalent two-level syste...We apply the transitionless driving on the local adiabatic quantum search algorithm to speed up the adiabatic process. By studying quantum dynamics of the adiabatic search algorithm with the equivalent two-level system, we derive the transi- tionless driving Hamiltonian for the local adiabatic quantum search algorithm. We found that when adding a transitionless quantum driving term Ht~ （t） on the local adiabatic quantum search algorithm, the success rate is 1 exactly with arbitrary evolution time by solving the time-dependent Schr6dinger equation in eigen-picture. Moreover, we show the reason for the drastic decrease of the evolution time is that the driving Hamiltonian increases the lowest eigenvalues to a maximum of展开更多
The genetic algorithm has been widely used in many fields as an easy robust global search and optimization method. In this paper, a new generic algorithm based on niche technique and local search method is presented u...The genetic algorithm has been widely used in many fields as an easy robust global search and optimization method. In this paper, a new generic algorithm based on niche technique and local search method is presented under the consideration of inadequacies of the simple genetic algorithm. In order to prove the adaptability and validity of the improved genetic algorithm, optimization problems of multimodal functions with equal peaks, unequal peaks and complicated peak distribution are discussed. The simulation results show that compared to other niching methods, this improved genetic algorithm has obvious potential on many respects, such as convergence speed, solution accuracy, ability of global optimization, etc.展开更多
This paper introduces a hybrid evolutionary algorithm for the resource-constrained project scheduling problem (RCPSP). Given an RCPSP instance, the algorithm identifies the problem structure and selects a suitable dec...This paper introduces a hybrid evolutionary algorithm for the resource-constrained project scheduling problem (RCPSP). Given an RCPSP instance, the algorithm identifies the problem structure and selects a suitable decoding scheme. Then a multi-pass biased sampling method followed up by a multi-local search is used to generate a diverse and good quality initial population. The population then evolves through modified order-based recombination and mutation operators to perform exploration for promising solutions within the entire region. Mutation is performed only if the current population has converged or the produced offspring by recombination operator is too similar to one of his parents. Finally the algorithm performs an intensified local search on the best solution found in the evolutionary stage. Computational experiments using standard instances indicate that the proposed algorithm works well in both computational time and solution quality.展开更多
Symmetric workpiece localization algorithms combine alternating optimization and linearization. The iterative variables are partitioned into two groups. Then simple optimization approaches can be employed for each sub...Symmetric workpiece localization algorithms combine alternating optimization and linearization. The iterative variables are partitioned into two groups. Then simple optimization approaches can be employed for each subset of variables, where optimization of configuration variables is simplified as a linear least-squares problem (LSP). Convergence of current symmetric localization algorithms is discussed firstly. It is shown that simply taking the solution of the LSP as start of the next iteration may result in divergence or incorrect convergence. Therefore in our enhanced algorithms, line search is performed along the solution of the LSP in order to find a better point reducing the value of objective function. We choose this point as start of the next iteration. Better convergence is verified by numerical simulation. Besides, imposing boundary constraints on the LSP proves to be another efficient way.展开更多
To solve vehicle routing problem with different fleets, two methodologies are developed. The first methodology adopts twophase strategy. In the first phase, the improved savings method is used to assign customers to a...To solve vehicle routing problem with different fleets, two methodologies are developed. The first methodology adopts twophase strategy. In the first phase, the improved savings method is used to assign customers to appropriate vehicles. In the second phase, the iterated dynasearch algorithm is adopted to route each selected vehicle with the assigned customers. The iterated dynasearch algorithm combines dynasearch algorithm with iterated local search algorithm based on random kicks. The second methodplogy adopts the idea of cyclic transfer which is performed by using dynamic programming algorithm, and the iterated dynasearch algorithm is also embedded in it. The test results show that both methodologies generate better solutions than the traditional method, and the second methodology is superior to the first one.展开更多
An optimized volt-ampere reactive(VAR)control framework is proposed for transmission-level power systems to simultaneously mitigate voltage deviations and active-power losses through coordinated control of large-scale...An optimized volt-ampere reactive(VAR)control framework is proposed for transmission-level power systems to simultaneously mitigate voltage deviations and active-power losses through coordinated control of large-scale wind/solar farms with shunt static var generators(SVGs).The model explicitly represents reactive-power regulation characteristics of doubly-fed wind turbines and PV inverters under real-time meteorological conditions,and quantifies SVG high-speed compensation capability,enabling seamless transition from localized VAR management to a globally coordinated strategy.An enhanced adaptive gain-sharing knowledge optimizer(AGSK-SD)integrates simulated annealing and diversity maintenance to autonomously tune voltage-control actions,renewable source reactive-power set-points,and SVG output.The algorithm adaptively modulates knowledge factors and ratios across search phases,performs SA-based fine-grained local exploitation,and periodically re-injects population diversity to prevent premature convergence.Comprehensive tests on IEEE 9-bus and 39-bus systems demonstrate AGSK-SD’s superiority over NSGA-II and MOPSO in hypervolume(HV),inverse generative distance(IGD),and spread metrics while maintaining acceptable computational burden.The method reduces network losses from 2.7191 to 2.15 MW(20.79%reduction)and from 15.1891 to 11.22 MW(26.16%reduction)in the 9-bus and 39-bus systems respectively.Simultaneously,the cumulative voltage-deviation index decreases from 0.0277 to 3.42×10^(−4) p.u.(98.77%reduction)in the 9-bus system,and from 0.0556 to 0.0107 p.u.(80.76%reduction)in the 39-bus system.These improvements demonstrate significant suppression of line losses and voltage fluctuations.Comparative analysis with traditional heuristic optimization algorithms confirms the superior performance of the proposed approach.展开更多
针对传统地磁匹配中动态时间规整算法(Dynamic Time Warping,DTW)应用于地磁定位时存在误差较大、匹配速度较慢的问题,提出一种基于改进的DTW算法和边界搜索策略的地磁匹配定位方法。首先将传统地磁数据序列变换为一阶导数序列,其更能...针对传统地磁匹配中动态时间规整算法(Dynamic Time Warping,DTW)应用于地磁定位时存在误差较大、匹配速度较慢的问题,提出一种基于改进的DTW算法和边界搜索策略的地磁匹配定位方法。首先将传统地磁数据序列变换为一阶导数序列,其更能反应地磁场的变化趋势,以提高匹配的准确性。引入有限窗口对DTW算法计算单元数进行限制,以加快匹配速度。同时,采用边界搜索策略进行局部筛选,约束相邻两次定位点间的距离,避免出现不合理匹配点的现象。实验结果表明,所提算法相比传统DTW算法在室内环境下定位精度最高可提升87%,处理速度提升15%;室外环境下定位精度可提升17%,处理速度提升52%。研究成果满足地磁定位的实时性、高精度的需求,具有很强的实用性和广阔的发展空间。展开更多
This paper presents an efficient genetic algorithm for solving multiobjective transportation problem, assignment, and transshipment Problems. The proposed approach integrates the merits of both genetic algorithm (GA) ...This paper presents an efficient genetic algorithm for solving multiobjective transportation problem, assignment, and transshipment Problems. The proposed approach integrates the merits of both genetic algorithm (GA) and local search (LS) scheme. The algorithm maintains a finite-sized archive of non-dominated solutions which gets iteratively updated in the presence of new solutions based on clustering algorithm. The use clustering algorithm makes the algorithms practical by allowing a decision maker to control the resolution of the Pareto set approximation. To increase GAs’ problem solution power, local search technique is implemented as neighborhood search engine where it intends to explore the less-crowded area in the current archive to possibly obtain more nondominated solutions. The inclusion of local search and clustering algorithm speeds-up the search process and also helps in obtaining a fine-grained value for the objective functions. Finally, we report numerical results in order to establish the actual computational burden of the proposed algorithm and to assess its performances with respect to classical approaches for solving MOTP.展开更多
We present an improved hybrid genetic algorithm to solve the two-dimensional Eucli-dean traveling salesman problem (TSP), in which the crossover operator is enhanced with a local search. The proposed algorithm is expe...We present an improved hybrid genetic algorithm to solve the two-dimensional Eucli-dean traveling salesman problem (TSP), in which the crossover operator is enhanced with a local search. The proposed algorithm is expected to obtain higher quality solutions within a reasonable computational time for TSP by perfectly integrating GA and the local search. The elitist choice strategy, the local search crossover operator and the double-bridge random mutation are highlighted, to enhance the convergence and the possibility of escaping from the local optima. The experimental results illustrate that the novel hybrid genetic algorithm outperforms other genetic algorithms by providing higher accuracy and satisfactory efficiency in real optimization processing.展开更多
Evolutionary computation techniques have mostly been used to solve various optimization problems, and it is well known that graph isomorphism problem （GIP） is a nondeterministic polynomial problem. A simulated annea...Evolutionary computation techniques have mostly been used to solve various optimization problems, and it is well known that graph isomorphism problem （GIP） is a nondeterministic polynomial problem. A simulated annealing （SA） algorithm for detecting graph isomorphism is proposed, and the proposed SA algorithm is well suited to deal with random graphs with large size. To verify the validity of the proposed SA algorithm, simulations are performed on three pairs of small graphs and four pairs of large random graphs with edge densities 0.5, 0.1, and 0.01, respectively. The simulation results show that the proposed SA algorithm can detect graph isomorphism with a high probability.展开更多
A memetic algorithm （MA） for a multi-mode resourceconstrained project scheduling problem （MRCPSP） is proposed. We use a new fitness function and two very effective local search procedures in the proposed MA. The f...A memetic algorithm （MA） for a multi-mode resourceconstrained project scheduling problem （MRCPSP） is proposed. We use a new fitness function and two very effective local search procedures in the proposed MA. The fitness function makes use of a mechanism called ＂strategic oscillation＂ to make the search process have a higher probability to visit solutions around a ＂feasible boundary＂. One of the local search procedures aims at improving the lower bound of project makespan to be less than a known upper bound, and another aims at improving a solution of an MRCPSP instance accepting infeasible solutions based on the new fitness function in the search process. A detailed computational experiment is set up using instances from the problem instance library PSPLIB. Computational results show that the proposed MA is very competitive with the state-of-the-art algorithms. The MA obtains improved solutions for one instance of set J30.展开更多
In this paper, a hybrid genetic algorithm （GA） is proposed for the traveling salesman problem （TSP） with pickup and delivery （TSPPD）. In our algorithm, a novel pheromone-based crossover operator is advanced that...In this paper, a hybrid genetic algorithm （GA） is proposed for the traveling salesman problem （TSP） with pickup and delivery （TSPPD）. In our algorithm, a novel pheromone-based crossover operator is advanced that utilizes both local and global information to construct offspring. In addition, a local search procedure is integrated into the GA to accelerate convergence. The proposed GA has been tested on benchmark instances, and the computational results show that it gives better convergence than existing heuristics.展开更多
A clonal selection based memetic algorithm is proposed for solving job shop scheduling problems in this paper. In the proposed algorithm, the clonal selection and the local search mechanism are designed to enhance exp...A clonal selection based memetic algorithm is proposed for solving job shop scheduling problems in this paper. In the proposed algorithm, the clonal selection and the local search mechanism are designed to enhance exploration and exploitation. In the clonal selection mechanism, clonal selection, hypermutation and receptor edit theories are presented to construct an evolutionary searching mechanism which is used for exploration. In the local search mechanism, a simulated annealing local search algorithm based on Nowicki and Smutnicki＇s neighborhood is presented to exploit local optima. The proposed algorithm is examined using some well-known benchmark problems. Numerical results validate the effectiveness of the proposed algorithm.展开更多
文摘This paper presents a parallel composite local search algorithm based on multiple search neighborhoods to solve a special kind of timetable problem. The new algorithm can also effectively solve those problems that can be solved by general local search algorithms. Experimental results show that the new algorithm can generate better solutions than general local search algorithms.
文摘This paper presents an optimization technique coupling two optimization techniques for solving Economic Emission Load Dispatch Optimization Problem EELD. The proposed approach integrates the merits of both genetic algorithm (GA) and local search (LS), where it maintains a finite-sized archive of non-dominated solutions which gets iteratively updated in the presence of new solutions based on the concept of ε-dominance. To improve the solution quality, local search technique was applied as neighborhood search engine, where it intends to explore the less-crowded area in the current archive to possibly obtain more non-dominated solutions. TOPSIS technique can incorporate relative weights of criterion importance, which has been implemented to identify best compromise solution, which will satisfy the different goals to some extent. Several optimization runs of the proposed approach are carried out on the standard IEEE 30-bus 6-genrator test system. The comparison demonstrates the superiority of the proposed approach and confirms its potential to solve the multiobjective EELD problem.
基金Project supported by the National Basic Research Program of China(Grant No.2013CB338002)the National Natural Science Foundation of China(Grant Nos.11504430 and 61502526)
文摘We apply the transitionless driving on the local adiabatic quantum search algorithm to speed up the adiabatic process. By studying quantum dynamics of the adiabatic search algorithm with the equivalent two-level system, we derive the transi- tionless driving Hamiltonian for the local adiabatic quantum search algorithm. We found that when adding a transitionless quantum driving term Ht~ （t） on the local adiabatic quantum search algorithm, the success rate is 1 exactly with arbitrary evolution time by solving the time-dependent Schr6dinger equation in eigen-picture. Moreover, we show the reason for the drastic decrease of the evolution time is that the driving Hamiltonian increases the lowest eigenvalues to a maximum of
文摘The genetic algorithm has been widely used in many fields as an easy robust global search and optimization method. In this paper, a new generic algorithm based on niche technique and local search method is presented under the consideration of inadequacies of the simple genetic algorithm. In order to prove the adaptability and validity of the improved genetic algorithm, optimization problems of multimodal functions with equal peaks, unequal peaks and complicated peak distribution are discussed. The simulation results show that compared to other niching methods, this improved genetic algorithm has obvious potential on many respects, such as convergence speed, solution accuracy, ability of global optimization, etc.
文摘This paper introduces a hybrid evolutionary algorithm for the resource-constrained project scheduling problem (RCPSP). Given an RCPSP instance, the algorithm identifies the problem structure and selects a suitable decoding scheme. Then a multi-pass biased sampling method followed up by a multi-local search is used to generate a diverse and good quality initial population. The population then evolves through modified order-based recombination and mutation operators to perform exploration for promising solutions within the entire region. Mutation is performed only if the current population has converged or the produced offspring by recombination operator is too similar to one of his parents. Finally the algorithm performs an intensified local search on the best solution found in the evolutionary stage. Computational experiments using standard instances indicate that the proposed algorithm works well in both computational time and solution quality.
基金Supported by "973" National Fundamental Research Program (51332)
文摘Symmetric workpiece localization algorithms combine alternating optimization and linearization. The iterative variables are partitioned into two groups. Then simple optimization approaches can be employed for each subset of variables, where optimization of configuration variables is simplified as a linear least-squares problem (LSP). Convergence of current symmetric localization algorithms is discussed firstly. It is shown that simply taking the solution of the LSP as start of the next iteration may result in divergence or incorrect convergence. Therefore in our enhanced algorithms, line search is performed along the solution of the LSP in order to find a better point reducing the value of objective function. We choose this point as start of the next iteration. Better convergence is verified by numerical simulation. Besides, imposing boundary constraints on the LSP proves to be another efficient way.
基金The National Natural Science Founda-tion of China ( No.70471039)the National Social Science Foundation of China (No.07BJY038)the Program for New Century Excellent Talents in University (No.NCET-04-0886)
文摘To solve vehicle routing problem with different fleets, two methodologies are developed. The first methodology adopts twophase strategy. In the first phase, the improved savings method is used to assign customers to appropriate vehicles. In the second phase, the iterated dynasearch algorithm is adopted to route each selected vehicle with the assigned customers. The iterated dynasearch algorithm combines dynasearch algorithm with iterated local search algorithm based on random kicks. The second methodplogy adopts the idea of cyclic transfer which is performed by using dynamic programming algorithm, and the iterated dynasearch algorithm is also embedded in it. The test results show that both methodologies generate better solutions than the traditional method, and the second methodology is superior to the first one.
基金supported by Yunnan Power Grid Co.,Ltd.Science and Technology Project:Research and application of key technologies for graphical-based power grid accident reconstruction and simulation(YNKJXM20240333).
文摘An optimized volt-ampere reactive(VAR)control framework is proposed for transmission-level power systems to simultaneously mitigate voltage deviations and active-power losses through coordinated control of large-scale wind/solar farms with shunt static var generators(SVGs).The model explicitly represents reactive-power regulation characteristics of doubly-fed wind turbines and PV inverters under real-time meteorological conditions,and quantifies SVG high-speed compensation capability,enabling seamless transition from localized VAR management to a globally coordinated strategy.An enhanced adaptive gain-sharing knowledge optimizer(AGSK-SD)integrates simulated annealing and diversity maintenance to autonomously tune voltage-control actions,renewable source reactive-power set-points,and SVG output.The algorithm adaptively modulates knowledge factors and ratios across search phases,performs SA-based fine-grained local exploitation,and periodically re-injects population diversity to prevent premature convergence.Comprehensive tests on IEEE 9-bus and 39-bus systems demonstrate AGSK-SD’s superiority over NSGA-II and MOPSO in hypervolume(HV),inverse generative distance(IGD),and spread metrics while maintaining acceptable computational burden.The method reduces network losses from 2.7191 to 2.15 MW(20.79%reduction)and from 15.1891 to 11.22 MW(26.16%reduction)in the 9-bus and 39-bus systems respectively.Simultaneously,the cumulative voltage-deviation index decreases from 0.0277 to 3.42×10^(−4) p.u.(98.77%reduction)in the 9-bus system,and from 0.0556 to 0.0107 p.u.(80.76%reduction)in the 39-bus system.These improvements demonstrate significant suppression of line losses and voltage fluctuations.Comparative analysis with traditional heuristic optimization algorithms confirms the superior performance of the proposed approach.
文摘针对传统地磁匹配中动态时间规整算法(Dynamic Time Warping,DTW)应用于地磁定位时存在误差较大、匹配速度较慢的问题,提出一种基于改进的DTW算法和边界搜索策略的地磁匹配定位方法。首先将传统地磁数据序列变换为一阶导数序列,其更能反应地磁场的变化趋势,以提高匹配的准确性。引入有限窗口对DTW算法计算单元数进行限制,以加快匹配速度。同时,采用边界搜索策略进行局部筛选,约束相邻两次定位点间的距离,避免出现不合理匹配点的现象。实验结果表明,所提算法相比传统DTW算法在室内环境下定位精度最高可提升87%,处理速度提升15%;室外环境下定位精度可提升17%,处理速度提升52%。研究成果满足地磁定位的实时性、高精度的需求,具有很强的实用性和广阔的发展空间。
文摘This paper presents an efficient genetic algorithm for solving multiobjective transportation problem, assignment, and transshipment Problems. The proposed approach integrates the merits of both genetic algorithm (GA) and local search (LS) scheme. The algorithm maintains a finite-sized archive of non-dominated solutions which gets iteratively updated in the presence of new solutions based on clustering algorithm. The use clustering algorithm makes the algorithms practical by allowing a decision maker to control the resolution of the Pareto set approximation. To increase GAs’ problem solution power, local search technique is implemented as neighborhood search engine where it intends to explore the less-crowded area in the current archive to possibly obtain more nondominated solutions. The inclusion of local search and clustering algorithm speeds-up the search process and also helps in obtaining a fine-grained value for the objective functions. Finally, we report numerical results in order to establish the actual computational burden of the proposed algorithm and to assess its performances with respect to classical approaches for solving MOTP.
文摘We present an improved hybrid genetic algorithm to solve the two-dimensional Eucli-dean traveling salesman problem (TSP), in which the crossover operator is enhanced with a local search. The proposed algorithm is expected to obtain higher quality solutions within a reasonable computational time for TSP by perfectly integrating GA and the local search. The elitist choice strategy, the local search crossover operator and the double-bridge random mutation are highlighted, to enhance the convergence and the possibility of escaping from the local optima. The experimental results illustrate that the novel hybrid genetic algorithm outperforms other genetic algorithms by providing higher accuracy and satisfactory efficiency in real optimization processing.
基金the National Natural Science Foundation of China (60373089, 60674106, and 60533010)the National High Technology Research and Development "863" Program (2006AA01Z104)
文摘Evolutionary computation techniques have mostly been used to solve various optimization problems, and it is well known that graph isomorphism problem （GIP） is a nondeterministic polynomial problem. A simulated annealing （SA） algorithm for detecting graph isomorphism is proposed, and the proposed SA algorithm is well suited to deal with random graphs with large size. To verify the validity of the proposed SA algorithm, simulations are performed on three pairs of small graphs and four pairs of large random graphs with edge densities 0.5, 0.1, and 0.01, respectively. The simulation results show that the proposed SA algorithm can detect graph isomorphism with a high probability.
基金supported by the National Natural Science Foundation of China(71171038)
文摘A memetic algorithm （MA） for a multi-mode resourceconstrained project scheduling problem （MRCPSP） is proposed. We use a new fitness function and two very effective local search procedures in the proposed MA. The fitness function makes use of a mechanism called ＂strategic oscillation＂ to make the search process have a higher probability to visit solutions around a ＂feasible boundary＂. One of the local search procedures aims at improving the lower bound of project makespan to be less than a known upper bound, and another aims at improving a solution of an MRCPSP instance accepting infeasible solutions based on the new fitness function in the search process. A detailed computational experiment is set up using instances from the problem instance library PSPLIB. Computational results show that the proposed MA is very competitive with the state-of-the-art algorithms. The MA obtains improved solutions for one instance of set J30.
文摘In this paper, a hybrid genetic algorithm （GA） is proposed for the traveling salesman problem （TSP） with pickup and delivery （TSPPD）. In our algorithm, a novel pheromone-based crossover operator is advanced that utilizes both local and global information to construct offspring. In addition, a local search procedure is integrated into the GA to accelerate convergence. The proposed GA has been tested on benchmark instances, and the computational results show that it gives better convergence than existing heuristics.
文摘A clonal selection based memetic algorithm is proposed for solving job shop scheduling problems in this paper. In the proposed algorithm, the clonal selection and the local search mechanism are designed to enhance exploration and exploitation. In the clonal selection mechanism, clonal selection, hypermutation and receptor edit theories are presented to construct an evolutionary searching mechanism which is used for exploration. In the local search mechanism, a simulated annealing local search algorithm based on Nowicki and Smutnicki＇s neighborhood is presented to exploit local optima. The proposed algorithm is examined using some well-known benchmark problems. Numerical results validate the effectiveness of the proposed algorithm.
