A Chaotic Local Search-Based Particle Swarm Optimizer for Large-Scale Complex Wind Farm Layout Optimization

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.

Necessary and Sufficient Conditions for Feasible Neighbourhood Solutions in the Local Search of the Job-Shop Scheduling Problem

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.

Emergency Local Searching Approach for Job Shop Scheduling

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.

Combined Timetabling Procedure and Complete Local Search for No-Wait Job Shop Scheduling with Total Tardiness

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.

A New Genetic Algorithm Based on Niche Technique and Local Search Method

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.

A Multiple-Neighborhood-Based Parallel Composite Local Search Algorithm for Timetable Problem

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.

Intelligent Iterated Local Search Methods for Solving Vehicle Routing Problem with Different Fleets

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.

Local Search Algorithm with Hybrid Neighborhood and Its Application to Job Shop Scheduling Problem

A new local search method with hybrid neighborhood for Job shop scheduling problem is developed. The proposed hybrid neighborhood is not only efficient in local search, but also can help overcome entrapments while search procedure get trapped at local optima and carry the search to areas of the feasible set with better prospect. New strategies used for breaking out of entrapments are presented and they are helpful for the procedure to improve local optima. A performance comparison of the proposed method with some best-performing algorithms on all 10-job, 10-machine benchmark problems and the other two problems generated by Fisher and Thompson (ie., FT6 and FT20)is made. The experiment results show the better optimal performance of the proposed algorithm.

Novel Local Search Method for the Traveling Salesman Problem

A new local search method for the traveling salesman problem based on an original greedy representation of solution space and neighborhood structure is proposed. First, a partial closed route that only consists of three cities is given; then other cities are added to this route by a greedy procedure successively. Implemented on a personal computer, this algorithm finds optimal solutions for 24 out of 27 standard benchmarks, and outperforms the Full Subpath Ejection Algorithm (F-SEC) proposed by Rego in 1998.

Hybrid particle swarm optimization with differential evolution and chaotic local search to solve reliability-redundancy allocation problems

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 meta-heuristics,and CDEPSO algorithm is the best in solving these problems.

Enhanced Particle Swarm Optimization Based Local Search for Reactive Power Compensation Problem

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.

A Hybrid Optimization Technique Coupling an Evolutionary and a Local Search Algorithm for Economic Emission Load Dispatch Problem

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.

Local Search Heuristics for NFA State Minimization Problem

In the present paper we introduce new heuristic methods for the state minimization of nondeterministic finite automata. These methods are based on the classical Kameda-Weiner algorithm joined with local search heuristics, such as stochastic hill climbing and simulated annealing. The description of the proposed methods is given and the results of the numerical experiments are provided.

An Evolutionary Algorithm with Multi-Local Search for the Resource-Constrained Project Scheduling Problem

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.

Learning to sample initial solution for solving 0-1 discrete optimization problem by local search

Local search methods are convenient alternatives for solving discrete optimization problems(DOPs).These easy-to-implement methods are able to find approximate optimal solutions within a tolerable time limit.It is known that the quality of the initial solution greatly affects the quality of the approximated solution found by a local search method.In this paper,we propose to take the initial solution as a random variable and learn its preferable probability distribution.The aim is to sample a good initial solution from the learned distribution so that the local search can find a high-quality solution.We develop two different deep network models to deal with DOPs established on set(the knapsack problem)and graph(the maximum clique problem),respectively.The deep neural network learns the representation of an optimization problem instance and transforms the representation to its probability vector.Experimental results show that given the initial solution sampled from the learned probability distribution,a local search method can acquire much better approximate solutions than the randomly-sampled initial solution on the synthesized knapsack instances and the Erd?s-Rényi random graph instances.Furthermore,with sampled initial solutions,a classical genetic algorithm can achieve better solutions than a random initialized population in solving the maximum clique problems on DIMACS instances.Particularly,we emphasize that the developed models can generalize in dimensions and across graphs with various densities,which is an important advantage on generalizing deep-learning-based optimization algorithms.

Local search yields a PTAS for fixed-dimensional k-means problem with penalties

We study a problem called the k-means problem with penalties(k-MPWP),which is a natural generalization of the typical k-means problem.In this problem,we have a set D of client points in R^(d),a set F of possible centers in R^(d),and a penalty cost Pj>O for each point j∈D.We are also given an integer k which is the size of the center point set.We want to find a center point set S■F with size k,choose a penalized subset of clients P■D,and assign every client in D\P to its open center.Our goal is to minimize the sum of the squared distances between every point in D\P to its assigned centre point and the sum of the penalty costs for all clients in P.By using the multi-swap local search technique and under the fixed-dimensional Euclidean space setting,we present a polynomial-time approximation scheme(PTAS)for the k-MPWP.

A Modified Oppositional Chaotic Local Search Strategy Based Aquila Optimizer to Design an Effective Controller for Vehicle Cruise Control System

In this work,we propose a real proportional-integral-derivative plus second-order derivative(PIDD2)controller as an efficient controller for vehicle cruise control systems to address the challenging issues related to efficient operation.In this regard,this paper is the first report in the literature demonstrating the implementation of a real PIDD2 controller for controlling the respective system.We construct a novel and efficient metaheuristic algorithm by improving the performance of the Aquila Optimizer via chaotic local search and modified opposition-based learning strategies and use it as an excellently performing tuning mechanism.We also propose a simple yet effective objective function to increase the performance of the proposed algorithm(CmOBL-AO)to adjust the real PIDD2 controller's parameters effectively.We show the CmOBL-AO algorithm to perform better than the differential evolution algorithm,gravitational search algorithm,African vultures optimization,and the Aquila Optimizer using well-known unimodal,multimodal benchmark functions.CEC2019 test suite is also used to perform ablation experiments to reveal the separate contributions of chaotic local search and modified opposition-based learning strategies to the CmOBL-AO algorithm.For the vehicle cruise control system,we confirm the more excellent performance of the proposed method against particle swarm,gray wolf,salp swarm,and original Aquila optimizers using statistical,Wilcoxon signed-rank,time response,robustness,and disturbance rejection analyses.We also use fourteen reported methods in the literature for the vehicle cruise control system to further verify the more promising performance of the CmOBL-AO-based real PIDD2 controller from a wider perspective.The excellent performance of the proposed method is also illustrated through different quality indicators and different operating speeds.Lastly,we also demonstrate the good performing capability of the CmOBL-AO algorithm for real traffic cases.We show the CmOBL-AO-based real PIDD2 controller as the most efficient method to control a vehicle cruise control system.

基于LocalSearch的智能货运路线匹配设计与实现

传统物流行业中,货主需要向全国各个省市区发送货物,存在上千条线路。这就导致了货主每次招标时都要对这些线路的报价进行计算后选择2~3家承运商,靠手工Excel填写统计计算非常浪费时间。为了解决这个问题,设计并实现了基于LocalSearch的智能货运路线匹配系统,通过采用退火模拟和禁忌搜索等方式,能够在极短的时间内计算一个满足货主复杂招标要求的近似最优解,且计算结果要比手工计算优于20%以上,有助于节约人力成本,降低运费。

Crossover Iterated Local Search for SDCARP

This paper introduces a new algorithm based on local search for the capacitated arc routing problem(CARP)and the split-delivery capacitated arc routing problem(SDCARP).We present a intermediate model to transfer CARP to SDCARP and then solve the two problems by an algorithm which combines the iterated local search and the memetic algorithm.We use crossovers to perform fully reproducible initializations in each local search iteration and edge-marking to save computation time.The computational results on 63 instances of standard benchmarks show that the proposed algorithm outperforms most of the existing best-known solutions obtained by other heuristics within a reasonable computing time.Furthermore,compared with the CARP solutions,our algorithm finds three optimums for the SDCARP.

Complete Boolean Satisfiability Solving Algorithms Based on Local Search

Boolean satisfiability （SAT） is a well-known problem in computer science, artificial intelligence, and operations research. This paper focuses on the satisfiability problem of Model RB structure that is similar to graph coloring problems and others. We propose a translation method and three effective complete SAT solving algorithms based on the characterization of Model RB structure. We translate clauses into a graph with exclusive sets and relative sets. In order to reduce search depth, we determine search order using vertex weights and clique in the graph. The results show that our algorithms are much more effective than the best SAT solvers in numerous Model RB benchmarks, especially in those large benchmark instances.