Wind energy has been widely applied in power generation to alleviate climate problems.The wind turbine layout of a wind farm is a primary factor of impacting power conversion efficiency due to the wake effect that red...Wind energy has been widely applied in power generation to alleviate climate problems.The wind turbine layout of a wind farm is a primary factor of impacting power conversion efficiency due to the wake effect that reduces the power outputs of wind turbines located in downstream.Wind farm layout optimization(WFLO)aims to reduce the wake effect for maximizing the power outputs of the wind farm.Nevertheless,the wake effect among wind turbines increases significantly as the number of wind turbines increases in the wind farm,which severely affect power conversion efficiency.Conventional heuristic algorithms suffer from issues of low solution quality and local optimum for large-scale WFLO under complex wind scenarios.Thus,a chaotic local search-based genetic learning particle swarm optimizer(CGPSO)is proposed to optimize large-scale WFLO problems.CGPSO is tested on four larger-scale wind farms under four complex wind scenarios and compares with eight state-of-the-art algorithms.The experiment results indicate that CGPSO significantly outperforms its competitors in terms of performance,stability,and robustness.To be specific,a success and failure memories-based selection is proposed to choose a chaotic map for chaotic search local.It improves the solution quality.The parameter and search pattern of chaotic local search are also analyzed for WFLO problems.展开更多
Existing methods of local search mostly focus on how to reach optimal solution.However,in some emergency situations,search time is the hard constraint for job shop scheduling problem while optimal solution is not nece...Existing methods of local search mostly focus on how to reach optimal solution.However,in some emergency situations,search time is the hard constraint for job shop scheduling problem while optimal solution is not necessary.In this situation,the existing method of local search is not fast enough.This paper presents an emergency local search(ELS) approach which can reach feasible and nearly optimal solution in limited search time.The ELS approach is desirable for the aforementioned emergency situations where search time is limited and a nearly optimal solution is sufficient,which consists of three phases.Firstly,in order to reach a feasible and nearly optimal solution,infeasible solutions are repaired and a repair technique named group repair is proposed.Secondly,in order to save time,the amount of local search moves need to be reduced and this is achieved by a quickly search method named critical path search(CPS).Finally,CPS sometimes stops at a solution far from the optimal one.In order to jump out the search dilemma of CPS,a jump technique based on critical part is used to improve CPS.Furthermore,the schedule system based on ELS has been developed and experiments based on this system completed on the computer of Intel Pentium(R) 2.93 GHz.The experimental result shows that the optimal solutions of small scale instances are reached in 2 s,and the nearly optimal solutions of large scale instances are reached in 4 s.The proposed ELS approach can stably reach nearly optimal solutions with manageable search time,and can be applied on some emergency situations.展开更多
In order to solve reliability-redundancy allocation problems more effectively, a new hybrid algorithm named CDEPSO is proposed in this work, which combines particle swarm optimization (PSO) with differential evoluti...In order to solve reliability-redundancy allocation problems more effectively, a new hybrid algorithm named CDEPSO is proposed in this work, which combines particle swarm optimization (PSO) with differential evolution (DE) and a new chaotic local search. In the CDEPSO algorithm, DE provides its best solution to PSO if the best solution obtained by DE is better than that by PSO, while the best solution in the PSO is performed by chaotic local search. To investigate the performance of CDEPSO, four typical reliability-redundancy allocation problems were solved and the results indicate that the convergence speed and robustness of CDEPSO is better than those of PSO and CPSO (a hybrid algorithm which only combines PSO with chaotic local search). And, compared with the other six improved meta-heuristics, CDEPSO also exhibits more robust performance. In addition, a new performance was proposed to more fairly compare CDEPSO with the same six improved recta-heuristics, and CDEPSO algorithm is the best in solving these problems.展开更多
The meta-heuristic algorithm with local search is an excellent choice for the job-shop scheduling problem(JSP).However,due to the unique nature of the JSP,local search may generate infeasible neighbourhood solutions.I...The meta-heuristic algorithm with local search is an excellent choice for the job-shop scheduling problem(JSP).However,due to the unique nature of the JSP,local search may generate infeasible neighbourhood solutions.In the existing literature,although some domain knowledge of the JSP can be used to avoid infeasible solutions,the constraint conditions in this domain knowledge are sufficient but not necessary.It may lose many feasible solutions and make the local search inadequate.By analysing the causes of infeasible neighbourhood solutions,this paper further explores the domain knowledge contained in the JSP and proposes the sufficient and necessary constraint conditions to find all feasible neighbourhood solutions,allowing the local search to be carried out thoroughly.With the proposed conditions,a new neighbourhood structure is designed in this paper.Then,a fast calculation method for all feasible neighbourhood solutions is provided,significantly reducing the calculation time compared with ordinary methods.A set of standard benchmark instances is used to evaluate the performance of the proposed neighbourhood structure and calculation method.The experimental results show that the calculation method is effective,and the new neighbourhood structure has more reliability and superiority than the other famous and influential neighbourhood structures,where 90%of the results are the best compared with three other well-known neighbourhood structures.Finally,the result from a tabu search algorithm with the new neighbourhood structure is compared with the current best results,demonstrating the superiority of the proposed neighbourhood structure.展开更多
This paper presents an enhanced Particle Swarm Optimization (PSO) algorithm applied to the reactive power compensation (RPC) problem. It is based on the combination of Genetic Algorithm (GA) and PSO. Our approach inte...This paper presents an enhanced Particle Swarm Optimization (PSO) algorithm applied to the reactive power compensation (RPC) problem. It is based on the combination of Genetic Algorithm (GA) and PSO. Our approach integrates the merits of both genetic algorithms (GAs) and particle swarm optimization (PSO) and it has two characteristic features. Firstly, the algorithm is initialized by a set of a random particle which traveling through the search space, during this travel an evolution of these particles is performed by a hybrid PSO with GA to get approximate no dominated solution. Secondly, to improve the solution quality, dynamic version of pattern 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 proposed approach is carried out on the standard IEEE 30-bus 6-generator test system. The results demonstrate the capabilities of the proposed approach to generate true and well-distributed Pareto optimal nondominated solutions of the multiobjective RPC.展开更多
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 study examines the multicriteria scheduling problem on a single machine to minimize three criteria: the maximum cost function, denoted by maximum late work (V<sub>max</sub>), maximum tardy job, denote...This study examines the multicriteria scheduling problem on a single machine to minimize three criteria: the maximum cost function, denoted by maximum late work (V<sub>max</sub>), maximum tardy job, denoted by (T<sub>max</sub>), and maximum earliness (E<sub>max</sub>). We propose several algorithms based on types of objectives function to be optimized when dealing with simultaneous minimization problems with and without weight and hierarchical minimization problems. The proposed Algorithm (3) is to find the set of efficient solutions for 1//F (V<sub>max</sub>, T<sub>max</sub>, E<sub>max</sub>) and 1//(V<sub>max</sub> + T<sub>max</sub> + E<sub>max</sub>). The Local Search Heuristic Methods (Descent Method (DM), Simulated Annealing (SA), Genetic Algorithm (GA), and the Tree Type Heuristics Method (TTHM) are applied to solve all suggested problems. Finally, the experimental results of Algorithm (3) are compared with the results of the Branch and Bound (BAB) method for optimal and Pareto optimal solutions for smaller instance sizes and compared to the Local Search Heuristic Methods for large instance sizes. These results ensure the efficiency of Algorithm (3) in a reasonable time.展开更多
In this paper,we propose a hybrid algorithm for finding a set of non dominated solutions of a multi objective optimization problem.In the proposed algorithm,a local search procedure is applied to each solution gener...In this paper,we propose a hybrid algorithm for finding a set of non dominated solutions of a multi objective optimization problem.In the proposed algorithm,a local search procedure is applied to each solution generated by genetic operations.The aim of the proposed algorithm is not to determine a single final solution but to try to find all the non dominated solutions of a multi objective optimization problem.The choice of the final solution is left to the decision makers preference.High search ability of the proposed algorithm is demonstrated by computer simulation.展开更多
By considering the eigenratio of the Laplacian matrix as the synchronizability measure, this paper presents an efficient method to enhance the synchronizability of undirected and unweighted networks via rewiring. The ...By considering the eigenratio of the Laplacian matrix as the synchronizability measure, this paper presents an efficient method to enhance the synchronizability of undirected and unweighted networks via rewiring. The rewiring method combines the use of tabu search and a local greedy algorithm so that an effective search of solutions can be achieved. As demonstrated in the simulation results, the performance of the proposed approach outperforms the existing methods for a large variety of initial networks, both in terms of speed and quality of solutions.展开更多
Feature selection has been widely used in data mining and machine learning.Its objective is to select a minimal subset of features according to some reasonable criteria so as to solve the original task more quickly.In...Feature selection has been widely used in data mining and machine learning.Its objective is to select a minimal subset of features according to some reasonable criteria so as to solve the original task more quickly.In this article,a feature selection algorithm with local search strategy based on the forest optimization algorithm,namely FSLSFOA,is proposed.The novel local search strategy in local seeding process guarantees the quality of the feature subset in the forest.Next,the fitness function is improved,which not only considers the classification accuracy,but also considers the size of the feature subset.To avoid falling into local optimum,a novel global seeding method is attempted,which selects trees on the bottom of candidate set and gives the algorithm more diversities.Finally,FSLSFOA is compared with four feature selection methods to verify its effectiveness.Most of the results are superior to these comparative methods.展开更多
This paper presents a bi-level hybrid local search(BHLS)algorithm for the three-dimensional loading problem with balancing constraints(3DLP-B),where several rectangular boxes with even densities but different sizes ar...This paper presents a bi-level hybrid local search(BHLS)algorithm for the three-dimensional loading problem with balancing constraints(3DLP-B),where several rectangular boxes with even densities but different sizes are loaded into a single cubic bin to meet the requirements of the space or capacity utilization and the balance of the center of gravity.The proposed algorithm hybridizes a novel framed-layout procedure in which the concept of the core block and its generation strategy are introduced.Once the block-loading sequence has been determined,we can load one block at a time by the designed construction heuristic.Then,the double-search is introduced;its external search procedure generates a list of compact packing patterns while its internal search procedure is used to search the core-block frames and their best distribution locations.The approach is extensively tested on weakly to strongly heterogeneous benchmark data.The results show that it has better performance in improving space utilization rate and balanced condition of the placement than existed techniques:the overall averages from 79.85%to 86.45%were obtained for the balanced cases and relatively high space-usage rate of 89.44%was achieved for the unbalanced ones.展开更多
The strong non-deterministic polynomial-hard( NP-hard)character of job shop scheduling problem( JSSP) has been acknowledged widely and it becomes stronger when attaches the nowait constraint,which widely exists in man...The strong non-deterministic polynomial-hard( NP-hard)character of job shop scheduling problem( JSSP) has been acknowledged widely and it becomes stronger when attaches the nowait constraint,which widely exists in many production processes,such as chemistry process, metallurgical process. However,compared with the massive research on traditional job shop problem,little attention has been paid on the no-wait constraint.Therefore,in this paper, we have dealt with this problem by decomposing it into two sub-problems, the timetabling and sequencing problems,in traditional frame work. A new efficient combined non-order timetabling method,coordinated with objective of total tardiness,is proposed for the timetabling problems. As for the sequencing one,we have presented a modified complete local search with memory combined by crossover operator and distance counting. The entire algorithm was tested on well-known benchmark problems and compared with several existing algorithms.Computational experiments showed that our proposed algorithm performed both effectively and efficiently.展开更多
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.展开更多
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.展开更多
Iterated local search(ILS)is used to construct the optimal experimental designs for multi-dimensional constrained spaces,in which the inner loop is based on the stochastic coordinate-exchange(SCE)algorithm.Every time ...Iterated local search(ILS)is used to construct the optimal experimental designs for multi-dimensional constrained spaces,in which the inner loop is based on the stochastic coordinate-exchange(SCE)algorithm.Every time a local optimal solution is found by the SCE algorithm,the perturbation operator is applied to it,and then a new solution is explored in the areas where the exchange of coordinates may produce improvement,so as to retain the features and attributes of the current optimal solution and avoid the defects of random restart.We implement the iterated local coordinate-exchange algorithm for experimental designs in the multi-dimensional constrained spaces.In addition,sensitivity analysis was conducted to analyze the impacts of the parameters on the performance of the proposed algorithm.Also we compared the performance of the proposed algorithm to the SCE algorithm using the random restart strategy.The analysis shows that the proposed algorithm is better than the SCE algorithm in terms of efficiency and quality,especially in the experimental designs for high-dimensional constrained space.展开更多
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.展开更多
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.展开更多
Recently, Zhang and Lu provided a quantum search algorithm based on partial adiabatic evolution, which beats the time bound of local adiabatic search when the number of marked items in the unsorted database is larger ...Recently, Zhang and Lu provided a quantum search algorithm based on partial adiabatic evolution, which beats the time bound of local adiabatic search when the number of marked items in the unsorted database is larger than one. Later, they found that the above two adiabatic search algorithms had the same time complexity when there is only one marked item in the database. In the present paper, following the idea of Roland and Cerf [Roland J and Cerf N J 2002 Phys. Rev. A 65 042308], if within the small symmetric evolution interval defined by Zhang et al., a local adiabatic evolution is performed instead of the original "global" one, this "new" algorithm exhibits slightly better performance, although they are progressively equivalent with M increasing. In addition, the proof of the optimality for this partial evolution based local adiabatic search when M = 1 is also presented. Two other special cases of the adiabatic algorithm obtained by appropriately tuning the evolution interval of partial adiabatic evolution based quantum search, which are found to have the same phenomenon above, are also discussed.展开更多
基金partially supported by the Japan Society for the Promotion of Science(JSPS)KAKENHI(JP22H03643)Japan Science and Technology Agency(JST)Support for Pioneering Research Initiated by the Next Generation(SPRING)(JPMJSP2145)JST through the Establishment of University Fellowships towards the Creation of Science Technology Innovation(JPMJFS2115)。
文摘Wind energy has been widely applied in power generation to alleviate climate problems.The wind turbine layout of a wind farm is a primary factor of impacting power conversion efficiency due to the wake effect that reduces the power outputs of wind turbines located in downstream.Wind farm layout optimization(WFLO)aims to reduce the wake effect for maximizing the power outputs of the wind farm.Nevertheless,the wake effect among wind turbines increases significantly as the number of wind turbines increases in the wind farm,which severely affect power conversion efficiency.Conventional heuristic algorithms suffer from issues of low solution quality and local optimum for large-scale WFLO under complex wind scenarios.Thus,a chaotic local search-based genetic learning particle swarm optimizer(CGPSO)is proposed to optimize large-scale WFLO problems.CGPSO is tested on four larger-scale wind farms under four complex wind scenarios and compares with eight state-of-the-art algorithms.The experiment results indicate that CGPSO significantly outperforms its competitors in terms of performance,stability,and robustness.To be specific,a success and failure memories-based selection is proposed to choose a chaotic map for chaotic search local.It improves the solution quality.The parameter and search pattern of chaotic local search are also analyzed for WFLO problems.
基金supported by National Natural Science Foundation of China(Grant No.61004109)Fundamental Research Funds for the Central Universities of China(Grant No.FRF-TP-12-071A)
文摘Existing methods of local search mostly focus on how to reach optimal solution.However,in some emergency situations,search time is the hard constraint for job shop scheduling problem while optimal solution is not necessary.In this situation,the existing method of local search is not fast enough.This paper presents an emergency local search(ELS) approach which can reach feasible and nearly optimal solution in limited search time.The ELS approach is desirable for the aforementioned emergency situations where search time is limited and a nearly optimal solution is sufficient,which consists of three phases.Firstly,in order to reach a feasible and nearly optimal solution,infeasible solutions are repaired and a repair technique named group repair is proposed.Secondly,in order to save time,the amount of local search moves need to be reduced and this is achieved by a quickly search method named critical path search(CPS).Finally,CPS sometimes stops at a solution far from the optimal one.In order to jump out the search dilemma of CPS,a jump technique based on critical part is used to improve CPS.Furthermore,the schedule system based on ELS has been developed and experiments based on this system completed on the computer of Intel Pentium(R) 2.93 GHz.The experimental result shows that the optimal solutions of small scale instances are reached in 2 s,and the nearly optimal solutions of large scale instances are reached in 4 s.The proposed ELS approach can stably reach nearly optimal solutions with manageable search time,and can be applied on some emergency situations.
基金Project(20040533035)supported by the National Research Foundation for the Doctoral Program of Higher Education of ChinaProject(60874070)supported by the National Natural Science Foundation of China
文摘In order to solve reliability-redundancy allocation problems more effectively, a new hybrid algorithm named CDEPSO is proposed in this work, which combines particle swarm optimization (PSO) with differential evolution (DE) and a new chaotic local search. In the CDEPSO algorithm, DE provides its best solution to PSO if the best solution obtained by DE is better than that by PSO, while the best solution in the PSO is performed by chaotic local search. To investigate the performance of CDEPSO, four typical reliability-redundancy allocation problems were solved and the results indicate that the convergence speed and robustness of CDEPSO is better than those of PSO and CPSO (a hybrid algorithm which only combines PSO with chaotic local search). And, compared with the other six improved meta-heuristics, CDEPSO also exhibits more robust performance. In addition, a new performance was proposed to more fairly compare CDEPSO with the same six improved recta-heuristics, and CDEPSO algorithm is the best in solving these problems.
基金Supported by National Natural Science Foundation of China(Grant Nos.U21B2029 and 51825502).
文摘The meta-heuristic algorithm with local search is an excellent choice for the job-shop scheduling problem(JSP).However,due to the unique nature of the JSP,local search may generate infeasible neighbourhood solutions.In the existing literature,although some domain knowledge of the JSP can be used to avoid infeasible solutions,the constraint conditions in this domain knowledge are sufficient but not necessary.It may lose many feasible solutions and make the local search inadequate.By analysing the causes of infeasible neighbourhood solutions,this paper further explores the domain knowledge contained in the JSP and proposes the sufficient and necessary constraint conditions to find all feasible neighbourhood solutions,allowing the local search to be carried out thoroughly.With the proposed conditions,a new neighbourhood structure is designed in this paper.Then,a fast calculation method for all feasible neighbourhood solutions is provided,significantly reducing the calculation time compared with ordinary methods.A set of standard benchmark instances is used to evaluate the performance of the proposed neighbourhood structure and calculation method.The experimental results show that the calculation method is effective,and the new neighbourhood structure has more reliability and superiority than the other famous and influential neighbourhood structures,where 90%of the results are the best compared with three other well-known neighbourhood structures.Finally,the result from a tabu search algorithm with the new neighbourhood structure is compared with the current best results,demonstrating the superiority of the proposed neighbourhood structure.
文摘This paper presents an enhanced Particle Swarm Optimization (PSO) algorithm applied to the reactive power compensation (RPC) problem. It is based on the combination of Genetic Algorithm (GA) and PSO. Our approach integrates the merits of both genetic algorithms (GAs) and particle swarm optimization (PSO) and it has two characteristic features. Firstly, the algorithm is initialized by a set of a random particle which traveling through the search space, during this travel an evolution of these particles is performed by a hybrid PSO with GA to get approximate no dominated solution. Secondly, to improve the solution quality, dynamic version of pattern 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 proposed approach is carried out on the standard IEEE 30-bus 6-generator test system. The results demonstrate the capabilities of the proposed approach to generate true and well-distributed Pareto optimal nondominated solutions of the multiobjective RPC.
基金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 study examines the multicriteria scheduling problem on a single machine to minimize three criteria: the maximum cost function, denoted by maximum late work (V<sub>max</sub>), maximum tardy job, denoted by (T<sub>max</sub>), and maximum earliness (E<sub>max</sub>). We propose several algorithms based on types of objectives function to be optimized when dealing with simultaneous minimization problems with and without weight and hierarchical minimization problems. The proposed Algorithm (3) is to find the set of efficient solutions for 1//F (V<sub>max</sub>, T<sub>max</sub>, E<sub>max</sub>) and 1//(V<sub>max</sub> + T<sub>max</sub> + E<sub>max</sub>). The Local Search Heuristic Methods (Descent Method (DM), Simulated Annealing (SA), Genetic Algorithm (GA), and the Tree Type Heuristics Method (TTHM) are applied to solve all suggested problems. Finally, the experimental results of Algorithm (3) are compared with the results of the Branch and Bound (BAB) method for optimal and Pareto optimal solutions for smaller instance sizes and compared to the Local Search Heuristic Methods for large instance sizes. These results ensure the efficiency of Algorithm (3) in a reasonable time.
文摘In this paper,we propose a hybrid algorithm for finding a set of non dominated solutions of a multi objective optimization problem.In the proposed algorithm,a local search procedure is applied to each solution generated by genetic operations.The aim of the proposed algorithm is not to determine a single final solution but to try to find all the non dominated solutions of a multi objective optimization problem.The choice of the final solution is left to the decision makers preference.High search ability of the proposed algorithm is demonstrated by computer simulation.
基金Project supported by the grant from City University of Hong Kong (Grant No. 7008105)
文摘By considering the eigenratio of the Laplacian matrix as the synchronizability measure, this paper presents an efficient method to enhance the synchronizability of undirected and unweighted networks via rewiring. The rewiring method combines the use of tabu search and a local greedy algorithm so that an effective search of solutions can be achieved. As demonstrated in the simulation results, the performance of the proposed approach outperforms the existing methods for a large variety of initial networks, both in terms of speed and quality of solutions.
基金National Science Foundation of China(Nos.U1736105,61572259,41942017)The authors extend their appreciation to the Deanship of Scientific Research at King Saud University for funding this work through research group no.RGP-VPP-264.
文摘Feature selection has been widely used in data mining and machine learning.Its objective is to select a minimal subset of features according to some reasonable criteria so as to solve the original task more quickly.In this article,a feature selection algorithm with local search strategy based on the forest optimization algorithm,namely FSLSFOA,is proposed.The novel local search strategy in local seeding process guarantees the quality of the feature subset in the forest.Next,the fitness function is improved,which not only considers the classification accuracy,but also considers the size of the feature subset.To avoid falling into local optimum,a novel global seeding method is attempted,which selects trees on the bottom of candidate set and gives the algorithm more diversities.Finally,FSLSFOA is compared with four feature selection methods to verify its effectiveness.Most of the results are superior to these comparative methods.
基金Project(16B134)supported by Hunan Provincial Department of Education,China
文摘This paper presents a bi-level hybrid local search(BHLS)algorithm for the three-dimensional loading problem with balancing constraints(3DLP-B),where several rectangular boxes with even densities but different sizes are loaded into a single cubic bin to meet the requirements of the space or capacity utilization and the balance of the center of gravity.The proposed algorithm hybridizes a novel framed-layout procedure in which the concept of the core block and its generation strategy are introduced.Once the block-loading sequence has been determined,we can load one block at a time by the designed construction heuristic.Then,the double-search is introduced;its external search procedure generates a list of compact packing patterns while its internal search procedure is used to search the core-block frames and their best distribution locations.The approach is extensively tested on weakly to strongly heterogeneous benchmark data.The results show that it has better performance in improving space utilization rate and balanced condition of the placement than existed techniques:the overall averages from 79.85%to 86.45%were obtained for the balanced cases and relatively high space-usage rate of 89.44%was achieved for the unbalanced ones.
基金National Natural Science Foundations of China(Nos.61174040,61104178)Shanghai Commission of Science and Technology,China(No.12JC1403400)the Fundamental Research Funds for the Central Universities,China
文摘The strong non-deterministic polynomial-hard( NP-hard)character of job shop scheduling problem( JSSP) has been acknowledged widely and it becomes stronger when attaches the nowait constraint,which widely exists in many production processes,such as chemistry process, metallurgical process. However,compared with the massive research on traditional job shop problem,little attention has been paid on the no-wait constraint.Therefore,in this paper, we have dealt with this problem by decomposing it into two sub-problems, the timetabling and sequencing problems,in traditional frame work. A new efficient combined non-order timetabling method,coordinated with objective of total tardiness,is proposed for the timetabling problems. As for the sequencing one,we have presented a modified complete local search with memory combined by crossover operator and distance counting. The entire algorithm was tested on well-known benchmark problems and compared with several existing algorithms.Computational experiments showed that our proposed algorithm performed both effectively and efficiently.
文摘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.
文摘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 work was supported by the National Natural Science Foundation of China(72171231).
文摘Iterated local search(ILS)is used to construct the optimal experimental designs for multi-dimensional constrained spaces,in which the inner loop is based on the stochastic coordinate-exchange(SCE)algorithm.Every time a local optimal solution is found by the SCE algorithm,the perturbation operator is applied to it,and then a new solution is explored in the areas where the exchange of coordinates may produce improvement,so as to retain the features and attributes of the current optimal solution and avoid the defects of random restart.We implement the iterated local coordinate-exchange algorithm for experimental designs in the multi-dimensional constrained spaces.In addition,sensitivity analysis was conducted to analyze the impacts of the parameters on the performance of the proposed algorithm.Also we compared the performance of the proposed algorithm to the SCE algorithm using the random restart strategy.The analysis shows that the proposed algorithm is better than the SCE algorithm in terms of efficiency and quality,especially in the experimental designs for high-dimensional constrained space.
基金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.
文摘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.
基金Project supported by the National Natural Science Foundation of China(Grant No.61173050)
文摘Recently, Zhang and Lu provided a quantum search algorithm based on partial adiabatic evolution, which beats the time bound of local adiabatic search when the number of marked items in the unsorted database is larger than one. Later, they found that the above two adiabatic search algorithms had the same time complexity when there is only one marked item in the database. In the present paper, following the idea of Roland and Cerf [Roland J and Cerf N J 2002 Phys. Rev. A 65 042308], if within the small symmetric evolution interval defined by Zhang et al., a local adiabatic evolution is performed instead of the original "global" one, this "new" algorithm exhibits slightly better performance, although they are progressively equivalent with M increasing. In addition, the proof of the optimality for this partial evolution based local adiabatic search when M = 1 is also presented. Two other special cases of the adiabatic algorithm obtained by appropriately tuning the evolution interval of partial adiabatic evolution based quantum search, which are found to have the same phenomenon above, are also discussed.