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.展开更多
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.展开更多
In view of the serious reactive power loss in the rural network, improved ant colony optimization algorithm （ACOA） was used to optimize the reactive power compensation for the rural distribution system. In this stud...In view of the serious reactive power loss in the rural network, improved ant colony optimization algorithm （ACOA） was used to optimize the reactive power compensation for the rural distribution system. In this study, the traditional ACOA was improved in two aspects： one was the local search strategy, and the other was pheromone mutation and re-initialization strategies. The reactive power optimization for a county＇s distribution network showed that the improved ACOA was practicable.展开更多
Based on the current cloud computing resources security distribution model’s problem that the optimization effect is not high and the convergence is not good, this paper puts forward a cloud computing resources secur...Based on the current cloud computing resources security distribution model’s problem that the optimization effect is not high and the convergence is not good, this paper puts forward a cloud computing resources security distribution model based on improved artificial firefly algorithm. First of all, according to characteristics of the artificial fireflies swarm algorithm and the complex method, it incorporates the ideas of complex method into the artificial firefly algorithm, uses the complex method to guide the search of artificial fireflies in population, and then introduces local search operator in the firefly mobile mechanism, in order to improve the searching efficiency and convergence precision of algorithm. Simulation results show that, the cloud computing resources security distribution model based on improved artificial firefly algorithm proposed in this paper has good convergence effect and optimum efficiency.展开更多
文摘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.
文摘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.
基金Supported by China Postdoctoral Science Foundation(20090460873)
文摘In view of the serious reactive power loss in the rural network, improved ant colony optimization algorithm （ACOA） was used to optimize the reactive power compensation for the rural distribution system. In this study, the traditional ACOA was improved in two aspects： one was the local search strategy, and the other was pheromone mutation and re-initialization strategies. The reactive power optimization for a county＇s distribution network showed that the improved ACOA was practicable.
文摘Based on the current cloud computing resources security distribution model’s problem that the optimization effect is not high and the convergence is not good, this paper puts forward a cloud computing resources security distribution model based on improved artificial firefly algorithm. First of all, according to characteristics of the artificial fireflies swarm algorithm and the complex method, it incorporates the ideas of complex method into the artificial firefly algorithm, uses the complex method to guide the search of artificial fireflies in population, and then introduces local search operator in the firefly mobile mechanism, in order to improve the searching efficiency and convergence precision of algorithm. Simulation results show that, the cloud computing resources security distribution model based on improved artificial firefly algorithm proposed in this paper has good convergence effect and optimum efficiency.
