Статті в журналах з теми "Encodings and local search operators"
Щоб переглянути інші типи публікацій з цієї теми, перейдіть за посиланням: Encodings and local search operators.
Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями
Ознайомтеся з топ-50 статей у журналах для дослідження на тему "Encodings and local search operators".
Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.
Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.
Переглядайте статті в журналах для різних дисциплін та оформлюйте правильно вашу бібліографію.
1
Raidl, Günther R., and Jens Gottlieb. "Empirical Analysis of Locality, Heritability and Heuristic Bias in Evolutionary Algorithms: A Case Study for the Multidimensional Knapsack Problem." Evolutionary Computation 13, no. 4 (December 2005): 441–75. http://dx.doi.org/10.1162/106365605774666886.
Анотація:
Our main aim is to provide guidelines and practical help for the design of appropriate representations and operators for evolutionary algorithms (EAs). For this purpose, we propose techniques to obtain a better understanding of various effects in the interplay of the representation and the operators. We study six different representations and associated variation operators in the context of a steady-state evolutionary algorithm for the multidimensional knapsack problem. Four of them are indirect decoder-based techniques, and two are direct encodings combined with different initialization, repair, and local improvement strategies. The complex decoders and the local improvement and repair strategies make it practically impossible to completely analyze such EAs in a fully theoretical way. After comparing the general performance of the chosen EA variants for the multidimensional knapsack problem on two benchmark suites, we present a hands-on approach for empirically analyzing important aspects of initialization, mutation, and crossover in an isolated fashion. Static, inexpensive measurements based on randomly created solutions are performed in order to quantify and visualize specific properties with respect to heuristic bias, locality, and heritability. These tests shed light onto the complex behavior of such EAs and point out reasons for good or bad performance. In addition, the proposed measures are also examined during actual EA runs, which gives further insight into dynamic aspects of evolutionary search and verifies the validity of the isolated static measurements. All measurements are described in a general way, allowing for an easy adaption to other representations and problems.
2
Varnamkhasti, M. Jalali. "A genetic algorithm rooted in integer encoding and fuzzy controller." IAES International Journal of Robotics and Automation (IJRA) 8, no. 2 (June 1, 2019): 113. http://dx.doi.org/10.11591/ijra.v8i2.pp113-124.
Анотація:
The premature convergence is the essential problem in genetic algorithms and it is strongly related to the loss of genetic diversity of the population. In this study, a new sexual selection mechanism which utilizing mate chromosome during selection proposed and then technique focuses on selecting and controlling the genetic operators by applying the fuzzy logic controller. Computational experiments are conducted on the proposed techniques and the results are compared with some other operators, heuristic and local search algorithms commonly used for solving benchmark problems published in the literature.
3
Gao, Yilong, Zhiqiang Xie, Xinyang Liu, Wei Zhou, and Xu Yu. "Integrated scheduling algorithm based on the priority constraint table for complex products with tree structure." Advances in Mechanical Engineering 12, no. 12 (December 2020): 168781402098520. http://dx.doi.org/10.1177/1687814020985206.
Анотація:
Aiming at the existing intelligent optimization algorithms for solving the integrated scheduling problem of complex products with tree structure, there are problems of missing optimal solutions when designing encoding methods or generating infeasible offspring while designing evolutionary operators, an integrated scheduling algorithm based on the priority constraint table is proposed in this paper. A novel encoding method based on the dynamic priority constraint table is developed, which can guarantee the feasibility and completeness of the initial population individuals. For the legitimacy of the generated offspring individuals, two new different crossover and mutation methods are designed separately. The introduced evolutionary operators can avoid the detection and repairment of the infeasible individuals. An insertion-based greedy decoding method is also developed. In addition, based on the critical operations, a local search strategy is presented to enhance the search ability for the superior solutions. The feasibility and superiority of the proposed algorithm is verified by comparative experiments.
4
Jalali Varnamkhasti, M., and L. S. Lee. "A Fuzzy Genetic Algorithm Based on Binary Encoding for Solving Multidimensional Knapsack Problems." Journal of Applied Mathematics 2012 (2012): 1–23. http://dx.doi.org/10.1155/2012/703601.
Анотація:
The fundamental problem in genetic algorithms is premature convergence, and it is strongly related to the loss of genetic diversity of the population. This study aims at proposing some techniques to tackle the premature convergence by controlling the population diversity. Firstly, a sexual selection mechanism which utilizes the mate chromosome during selection is used. The second technique focuses on controlling the genetic parameters by applying the fuzzy logic controller. Computational experiments are conducted on the proposed techniques and the results are compared with other genetic operators, heuristics, and local search algorithms commonly used for solving multidimensional 0/1 knapsack problems published in the literature.
5
Jiang, Tianhua. "A Hybrid Grey Wolf Optimization for Job Shop Scheduling Problem." International Journal of Computational Intelligence and Applications 17, no. 03 (September 2018): 1850016. http://dx.doi.org/10.1142/s1469026818500165.
Анотація:
This paper aims to develop a hybrid grey wolf optimization algorithm (HGWO) for solving the job shop scheduling problem (JSP) with the objective of minimizing the makespan. Firstly, to make the GWO suitable for the discrete nature of JSP, an encoding mechanism is proposed to implement the continuous encoding of the discrete scheduling problem, and a ranked-order value (ROV) rule is used to conduct the conversion between individual position and operation permutation. Secondly, a heuristic algorithm and the random rule are combined to implement the population initialization in order to ensure the quality and diversity of initial solutions. Thirdly, a variable neighborhood search algorithm is embedded to improve the local search ability of our algorithm. In addition, to further improve the solution quality, genetic operators (crossover and mutation) are introduced to balance the exploitation and exploration ability. Finally, experimental results demonstrate the effectiveness of the proposed algorithm based on 23 benchmark instances.
6
Yang, Jinfeng, and Hua Xu. "Hybrid Memetic Algorithm to Solve Multiobjective Distributed Fuzzy Flexible Job Shop Scheduling Problem with Transfer." Processes 10, no. 8 (August 1, 2022): 1517. http://dx.doi.org/10.3390/pr10081517.
Анотація:
Most studies on distributed flexible job shop scheduling problem (DFJSP) assume that both processing time and transmission time are crisp values. However, due to the complexity of the factory processing environment, the processing information is uncertain. Therefore, we consider the uncertainty of processing environment, and for the first time propose a multiobjective distributed fuzzy flexible job shop scheduling problem with transfer (MO-DFFJSPT). To solve the MO-DFFJSPT, a hybrid decomposition variable neighborhood memetic algorithm (HDVMA) is proposed with the objectives of minimizing the makespan, maximum factory load, and total workload. In the proposed HDVMA, the well-designed encoding/decoding method and four initialization rules are used to generate the initial population, and several effective evolutionary operators are designed to update populations. Additionally, a weight vector is introduced to design high quality individual selection rules and acceptance criteria. Then, three excellent local search operators are designed for variable neighborhood search (VNS) to enhance its exploitation capability. Finally, a Taguchi experiment is designed to adjust the important parameters. Fifteen benchmarks are constructed, and the HDVMA is compared with four other famous algorithms on three metrics. The experimental results show that HDVMA is superior to the other four algorithms in terms of convergence and uniformity of non-dominated solution set distribution.
7
Weise, Thomas. "Software - motipy: the Metaheuristic Optimization in Python Library." ACM SIGEVOlution 16, no. 4 (December 2023): 1–2. http://dx.doi.org/10.1145/3638461.3638464.
Анотація:
We are thankful for the opportunity to announce our Python package "moptipy," which offers a rich set of tools for implementing, applying, and experimenting with metaheuristic optimization algorithms. Our package has been designed with benchmarking in mind and thus provides very comprehensive experimentation, data collection, and evaluation facilities out of the box. moptipy has the following features: 1. Very comprehensive documentation with many examples, reaching down to literature references inside the code and up to complex example experiments. 2. Several standard search spaces (bit strings, permutations, real vectors), operators, and algorithms, including randomized local search/hill climbers, simulated annealing, evolutionary algorithms, memetic algorithms, NSGA-II, several numerical optimization algorithms, etc., are already implemented and ready for use. 3. It is very easy to implement new algorithms using moptipy, be they general black-box methods or tailored for specific optimization problems. 4. It is also easy to integrate algorithms from external libraries and unify them under our API, which we did as proof-of-concept with CMA-ES, BOBYQA, as well as for the algorithms from SciPy. 5. Data can be collected at different verbosity levels, ranging from only providing the final result and its quality via the API (without creating any files) to creating log files with all (or all improving) steps of an algorithm, the result, the algorithm and problem parameters, the system setup, non-dominated solutions, and the random seed for fully-reproducible experiments. [1] 6. An experiment execution facility for very simple and robust parallel and distributed experimentation is provided. Parallelization and distribution works out-of-the-box based on shared folders and thus does not require additional libraries or programming effort [1]. 7. Stopping criteria for optimization processes can be defined based on goal solution qualities, clock time, and/or consumed objective function evaluations. 8. All experiments are fully reproducible, i.e., from a log file an algorithm and problem can be configured such that, in the replication experiment, exactly the same search steps are performed as in the original setting [1]. 9. The experiment evaluation facility can parse the log files and generate progress plots, result tables, ERT and ECDF plots, statistical test tables, and export data towards Excel or the popular IOHanalyzer. 10. Both single-objective and multi-objective optimization are supported under the same unified API. 11. The package has a good unit test coverage and pre-defined tools to unit test your own code. When implementing new objective functions, algorithms, encodings, oder operators, it is possible to use these tools to look for errors.
8
Zhang, L., and U. Kleine. "A novel bottom-left packing genetic algorithm for analog module placement." Advances in Radio Science 1 (May 5, 2003): 191–96. http://dx.doi.org/10.5194/ars-1-191-2003.
Анотація:
Abstract. This paper presents a novel genetic algorithm for analog module placement. It is based on a generalization of the two-dimensional bin packing problem. The genetic encoding and operators assures that all constraints of the problem are always satisfied. Thus the potential problems of adding penalty terms to the cost function are eliminated, so that the search configuration space decreases drastically. The dedicated cost function covers the special requirements of analog integrated circuits. A fractional factorial experiment was conducted using an orthogonal array to study the algorithm parameters. A meta-GA was applied to determine the optimal parameter values. The algorithm has been tested with several local benchmark circuits. The experimental results show this promising algorithm makes the better performance than simulated annealing approach with the satisfactory results comparable to manual placement.
9
Salcedo-Sanz, S., J. Del Ser, and Z. W. Geem. "An Island Grouping Genetic Algorithm for Fuzzy Partitioning Problems." Scientific World Journal 2014 (2014): 1–15. http://dx.doi.org/10.1155/2014/916371.
Анотація:
This paper presents a novel fuzzy clustering technique based on grouping genetic algorithms (GGAs), which are a class of evolutionary algorithms especially modified to tackle grouping problems. Our approach hinges on a GGA devised for fuzzy clustering by means of a novel encoding of individuals (containing elements and clusters sections), a new fitness function (a superior modification of the Davies Bouldin index), specially tailored crossover and mutation operators, and the use of a scheme based on a local search and a parallelization process, inspired from an island-based model of evolution. The overall performance of our approach has been assessed over a number of synthetic and real fuzzy clustering problems with different objective functions and distance measures, from which it is concluded that the proposed approach shows excellent performance in all cases.
10
Yu, Zhenao, Peng Duan, Leilei Meng, Yuyan Han, and Fan Ye. "Multi-objective path planning for mobile robot with an improved artificial bee colony algorithm." Mathematical Biosciences and Engineering 20, no. 2 (2022): 2501–29. http://dx.doi.org/10.3934/mbe.2023117.
Анотація:
<abstract><p>Effective path planning (PP) is the basis of autonomous navigation for mobile robots. Since the PP is an NP-hard problem, intelligent optimization algorithms have become a popular option to solve this problem. As a classic evolutionary algorithm, the artificial bee colony (ABC) algorithm has been applied to solve numerous realistic optimization problems. In this study, we propose an improved artificial bee colony algorithm (IMO-ABC) to deal with the multi-objective PP problem for a mobile robot. Path length and path safety were optimized as two objectives. Considering the complexity of the multi-objective PP problem, a well-environment model and a path encoding method are designed to make solutions feasible. In addition, a hybrid initialization strategy is applied to generate efficient feasible solutions. Subsequently, path-shortening and path-crossing operators are developed and embedded in the IMO-ABC algorithm. Meanwhile, a variable neighborhood local search strategy and a global search strategy, which could enhance exploitation and exploration, respectively, are proposed. Finally, representative maps including a real environment map are employed for simulation tests. The effectiveness of the proposed strategies is verified through numerous comparisons and statistical analyses. Simulation results show that the proposed IMO-ABC yields better solutions with respect to hypervolume and set coverage metrics for the later decision-maker.</p></abstract>
11
Vallati, Mauro, Lukáš Chrpa, and Diane Kitchin. "ASAP: An Automatic Algorithm Selection Approach for Planning." International Journal on Artificial Intelligence Tools 23, no. 06 (December 2014): 1460032. http://dx.doi.org/10.1142/s021821301460032x.
Анотація:
Despite the advances made in the last decade in automated planning, no planner outperforms all the others in every known benchmark domain. This observation motivates the idea of selecting different planning algorithms for different domains. Moreover, the planners' performances are affected by the structure of the search space, which depends on the encoding of the considered domain. In many domains, the performance of a planner can be improved by exploiting additional knowledge, for instance, in the form of macro-operators or entanglements. In this paper we propose ASAP, an automatic Algorithm Selection Approach for Planning that: (i) for a given domain initially learns additional knowledge, in the form of macro-operators and entanglements, which is used for creating different encodings of the given planning domain and problems, and (ii) explores the 2 dimensional space of available algorithms, defined as encodings–planners couples, and then (iii) selects the most promising algorithm for optimising either the runtimes or the quality of the solution plans.
12
Rowe, Jonathan, Darrell Whitley, Laura Barbulescu, and Jean-Paul Watson. "Properties of Gray and Binary Representations." Evolutionary Computation 12, no. 1 (March 2004): 47–76. http://dx.doi.org/10.1162/evco.2004.12.1.47.
Анотація:
Representations are formalized as encodings that map the search space to the vertex set of a graph. We define the notion of bit equivalent encodings and show that for such encodings the corresponding Walsh coefficients are also conserved. We focus on Gray codes as particular types of encoding and present a review of properties related to the use of Gray codes. Gray codes are widely used in conjunction with genetic algorithms and bit-climbing algorithms for parameter optimization problems. We present new convergence proofs for a special class of unimodal functions; the proofs show that a steepest ascent bit climber using any reflected Gray code representation reaches the global optimum in a number of steps that is linear with respect to the encoding size. There are in fact many different Gray codes.Shifting is defined as a mechanism for dynamically switching from one Gray code representation to another in order to escape local optima. Theoretical results that substantially improve our understanding of the Gray codes and the shifting mechanism are presented. New proofs also shed light on the number of unique Gray code neighborhoods accessible via shifting and on how neighborhood structure changes during shifting. We show that shifting can improve the performance of both a local search algorithm as well as one of the best genetic algorithms currently available.
13
Chen, Wenxiang, Darrell Whitley, Adele Howe, and Brian Goldman. "Stochastic Local Search over Minterms on Structured SAT Instances." Proceedings of the International Symposium on Combinatorial Search 7, no. 1 (September 1, 2021): 125–26. http://dx.doi.org/10.1609/socs.v7i1.18403.
Анотація:
We observed that Conjunctive Normal Form (CNF) encodings of structured SAT instances often have a set of consecutive clauses defined over a small number of Boolean variables. To exploit the pattern, we propose a transformation of CNF to an alternative representation, Conjunctive Minterm Canonical Form (CMCF). The transformation is a two-step process: CNF clauses are first partitioned into disjoint subsets such that each subset contains CNF clauses with shared Boolean variables. CNF clauses in each subset are then replaced by Minterm Canonical Form (i.e., partial solutions), which is found by enumeration. We show empirically that a simple Stochastic Local Search (SLS) solver based on CMCF can consistently achieve a higher success rate using fewer evaluations than the SLS solver WalkSAT on two representative classes of structured SAT problems.
14
Gyllenberg, M., T. Koski, T. Lund, and O. Nevalainen. "Clustering by Adaptive Local Search with Multiple Search Operators." Pattern Analysis & Applications 3, no. 4 (December 1, 2000): 348–57. http://dx.doi.org/10.1007/s100440070006.
15
Frisch, Alan M., Timothy J. Peugniez, Anthony J. Doggett, and Peter W. Nightingale. "Solving Non-Boolean Satisfiability Problems with Stochastic Local Search: A Comparison of Encodings." Journal of Automated Reasoning 35, no. 1-3 (January 19, 2006): 143–79. http://dx.doi.org/10.1007/s10817-005-9011-0.
16
Wu, J., S. F. Wang, and P. Perdikaris. "A dive into spectral inference networks: improved algorithms for self-supervised learning of continuous spectral representations." Applied Mathematics and Mechanics 44, no. 7 (July 2023): 1199–224. http://dx.doi.org/10.1007/s10483-023-2998-7.
Анотація:
AbstractWe propose a self-supervising learning framework for finding the dominant eigenfunction-eigenvalue pairs of linear and self-adjoint operators. We represent target eigenfunctions with coordinate-based neural networks and employ the Fourier positional encodings to enable the approximation of high-frequency modes. We formulate a self-supervised training objective for spectral learning and propose a novel regularization mechanism to ensure that the network finds the exact eigenfunctions instead of a space spanned by the eigenfunctions. Furthermore, we investigate the effect of weight normalization as a mechanism to alleviate the risk of recovering linear dependent modes, allowing us to accurately recover a large number of eigenpairs. The effectiveness of our methods is demonstrated across a collection of representative benchmarks including both local and non-local diffusion operators, as well as high-dimensional time-series data from a video sequence. Our results indicate that the present algorithm can outperform competing approaches in terms of both approximation accuracy and computational cost.
17
Ni, Jian, and Yu Duo Li. "Heuristic Search with a New Operator Based Krisch Combination of Image Edge Detection." Advanced Materials Research 461 (February 2012): 461–65. http://dx.doi.org/10.4028/www.scientific.net/amr.461.461.
Анотація:
This paper designed a new edge detection[1,3] operator based on Krisch edge detector and direction encoding and combining the local average, while proposed heuristic search algorithm in the noise image based on segmentation edge of the self-enhanced. First, use small-scale Gaussian filtering in the noise image, and then use this edge detector for edge detection, and trajectory of each sub-search self-reinforcing, and finally according to the degree of self-reinforcing accumulation of noise to obtain the image edge. The results show that: This algorithm can effectively extract the real object from the noise, and to maximize the retention of details. And the performance better than Krisch and has some speed advantage
18
Wanner, Elizabeth F., Ricardo H. C. Takahashi, Frederico G. Guimarães, Jaime A. Ramírez, and David A. Lowther. "Hybrid genetic algorithms using quadratic local search operators." COMPEL - The international journal for computation and mathematics in electrical and electronic engineering 26, no. 3 (June 19, 2007): 773–87. http://dx.doi.org/10.1108/03321640710751217.
19
Müller, Felipe Martins, and Iaê Santos Bonilha. "Hyper-Heuristic Based on ACO and Local Search for Dynamic Optimization Problems." Algorithms 15, no. 1 (December 24, 2021): 9. http://dx.doi.org/10.3390/a15010009.
Анотація:
Hyper-heuristics comprise a set of approaches that are motivated (at least in part) by the objective of intelligently combining heuristic methods to solve hard optimization problems. Ant colony optimization (ACO) algorithms have been proven to deal with Dynamic Optimization Problems (DOPs) properly. Despite the good results obtained by the integration of local search operators with ACO, little has been done to tackle DOPs. In this research, one of the most reliable ACO schemes, the MAX-MIN Ant System (MMAS), has been integrated with advanced and effective local search operators, resulting in an innovative hyper-heuristic. The local search operators are the Lin–Kernighan (LK) and the Unstringing and Stringing (US) heuristics, and they were intelligently chosen to improve the solution obtained by ACO. The proposed method aims to combine the adaptation capabilities of ACO for DOPs and the good performance of the local search operators chosen in an adaptive way and based on their performance, creating in this way a hyper-heuristic. The travelling salesman problem (TSP) was the base problem to generate both symmetric and asymmetric dynamic test cases. Experiments have shown that the MMAS provides good initial solutions to the local search operators and the hyper-heuristic creates a robust and effective method for the vast majority of test cases.
20
Bartoccini, Umberto, Arturo Carpi, Valentina Poggioni, and Valentino Santucci. "Memes Evolution in a Memetic Variant of Particle Swarm Optimization." Mathematics 7, no. 5 (May 11, 2019): 423. http://dx.doi.org/10.3390/math7050423.
Анотація:
In this work, a coevolving memetic particle swarm optimization (CoMPSO) algorithm is presented. CoMPSO introduces the memetic evolution of local search operators in particle swarm optimization (PSO) continuous/discrete hybrid search spaces. The proposed solution allows one to overcome the rigidity of uniform local search strategies when applied to PSO. The key contribution is that memes provides each particle of a PSO scheme with the ability to adapt its exploration dynamics to the local characteristics of the search space landscape. The objective is obtained by an original hybrid continuous/discrete meme representation and a probabilistic co-evolving PSO scheme for discrete, continuous, or hybrid spaces. The coevolving memetic PSO evolves both the solutions and their associated memes, i.e. the local search operators. The proposed CoMPSO approach has been experimented on a standard suite of numerical optimization benchmark problems. Preliminary experimental results show that CoMPSO is competitive with respect to standard PSO and other memetic PSO schemes in literature, and its a promising starting point for further research in adaptive PSO local search operators.
21
Tsou, Ming-Cheng. "Genetic algorithm for solving celestial navigation fix problems." Polish Maritime Research 19, no. 3 (October 1, 2012): 53–59. http://dx.doi.org/10.2478/v10012-012-0031-5.
Анотація:
ABSTRACT As we enter the 21st century and advance further into the information age, traditional methods for computing a celestial navigation fix can no longer meet the requirements of modern vessels in terms of calculation speed and precision. Study of precise, rapid, and convenient celestial navigation computational methods and the application of information technology to modern celestial navigation is especially meaningful, considering the current push for e-Navigation. In this work, we employ a genetic algorithm, from the field of artificial intelligence, due to its superior search ability that mimics the natural process of biological evolution. Unique encodings and genetic operators designed in this study, in combination with the fix principle of celestial circles of equal altitude in celestial navigation, allow the rapid and direct attainment of accurate optimum vessel position. Test results indicate that this method has more flexibility, and avoids tedious and complicated computation and graphical procedures.
22
Sengupta, Lahari, Radu Mariescu-Istodor, and Pasi Fränti. "Which Local Search Operator Works Best for the Open-Loop TSP?" Applied Sciences 9, no. 19 (September 23, 2019): 3985. http://dx.doi.org/10.3390/app9193985.
Анотація:
The traveling salesman problem (TSP) has been widely studied for the classical closed-loop variant. However, very little attention has been paid to the open-loop variant. Most of the existing studies also focus merely on presenting the overall optimization results (gap) or focus on processing time, but do not reveal much about which operators are more efficient to achieve the result. In this paper, we present two new operators (link swap and 3–permute) and study their efficiency against existing operators, both analytically and experimentally. Results show that while 2-opt and relocate contribute equally in the closed-loop case, the situation changes dramatically in the open-loop case where the new operator, link swap, dominates the search; it contributes by 50% to all improvements, while 2-opt and relocate have a 25% share each. The results are also generalized to tabu search and simulated annealing.
23
Ślażyński, Mateusz. "Research Report on Automatic Synthesis of Local Search Neighborhood Operators." Electronic Proceedings in Theoretical Computer Science 306 (September 19, 2019): 433–40. http://dx.doi.org/10.4204/eptcs.306.59.
24
Liu, Xiaohan, Xiaoguang Gao, Zidong Wang, and Xinxin Ru. "Improved Local Search with Momentum for Bayesian Networks Structure Learning." Entropy 23, no. 6 (June 15, 2021): 750. http://dx.doi.org/10.3390/e23060750.
Анотація:
Bayesian Networks structure learning (BNSL) is a troublesome problem that aims to search for an optimal structure. An exact search tends to sacrifice a significant amount of time and memory to promote accuracy, while the local search can tackle complex networks with thousands of variables but commonly gets stuck in a local optimum. In this paper, two novel and practical operators and a derived operator are proposed to perturb structures and maintain the acyclicity. Then, we design a framework, incorporating an influential perturbation factor integrated by three proposed operators, to escape current local optimal and improve the dilemma that outcomes trap in local optimal. The experimental results illustrate that our algorithm can output competitive results compared with the state-of-the-art constraint-based method in most cases. Meanwhile, our algorithm reaches an equivalent or better solution found by the state-of-the-art exact search and hybrid methods.
25
Merz, Peter, and Bernd Freisleben. "Fitness Landscapes, Memetic Algorithms, and Greedy Operators for Graph Bipartitioning." Evolutionary Computation 8, no. 1 (March 2000): 61–91. http://dx.doi.org/10.1162/106365600568103.
Анотація:
The fitness landscape of the graph bipartitioning problem is investigated by performing a search space analysis for several types of graphs. The analysis shows that the structure of the search space is significantly different for the types of instances studied. Moreover, with increasing epistasis, the amount of gene interactions in the representation of a solution in an evolutionary algorithm, the number of local minima for one type of instance decreases and, thus, the search becomes easier. We suggest that other characteristics besides high epistasis might have greater influence on the hardness of a problem. To understand these characteristics, the notion of a dependency graph describing gene interactions is introduced. In particular, the local structure and the regularity of the dependency graph seems to be important for the performance of an algorithm, and in fact, algorithms that exploit these properties perform significantly better than others which do not. It will be shown that a simple hybrid multi-start local search exploiting locality in the structure of the graphs is able to find optimum or near optimum solutions very quickly. However, if the problem size increases or the graphs become unstructured, a memetic algorithm (a genetic algorithm incorporating local search) is shown to be much more effective.
26
Trojanowski, Krzysztof, and Artur Mikitiuk. "Wireless Sensor Network Coverage Optimization: Comparison of Local Search-Based Heuristics." Applied Computational Intelligence and Soft Computing 2022 (November 12, 2022): 1–21. http://dx.doi.org/10.1155/2022/3745358.
Анотація:
The Maximum Lifetime Coverage Problem (MLCP) requires heuristic optimization methods due to its complexity. A real-world problem model determines how a solution is represented and the operators applied in these heuristics. Our paper describes adapting a local search scheme and its operators to MLCP optimization. The operators originate from three local search algorithms we proposed earlier: LSHMA, LSCAIA, and LSRFTA. Two steps of the LS scheme’s main loop can be executed in three different ways each. Hence, nine versions of the LS approach can be obtained. In experimental research, we verified their effectiveness. Test cases come from three benchmarks: SCP1, proposed and used in our earlier research on the three LS algorithms mentioned above, and two others found in the literature. The results obtained with SCP1 showed that the algorithm based on the hypergraph model approach (HMA) is the most effective. The remaining results of the other algorithms divide them into two groups: effective ones and weak ones. However, other benchmarks showed that the more redundant the coverage of points of interest (POIs) by sensors, the more effective the perturbation method from the approach inspired by cellular automata (CAIA). The findings expose the strengths and weaknesses of the problem-specific steps applied in the LS algorithms.
27
Yang, Yaowen, Chao Wang, and Chee Kiong Soh. "Hybrid Genetic Programming with Local Search Operators for Dynamic Force Identification." Journal of Computing in Civil Engineering 21, no. 5 (September 2007): 311–20. http://dx.doi.org/10.1061/(asce)0887-3801(2007)21:5(311).
28
Lozano, Manuel, Francisco Herrera, Natalio Krasnogor, and Daniel Molina. "Real-Coded Memetic Algorithms with Crossover Hill-Climbing." Evolutionary Computation 12, no. 3 (September 2004): 273–302. http://dx.doi.org/10.1162/1063656041774983.
Анотація:
This paper presents a real-coded memetic algorithm that applies a crossover hill-climbing to solutions produced by the genetic operators. On the one hand, the memetic algorithm provides global search (reliability) by means of the promotion of high levels of population diversity. On the other, the crossover hill-climbing exploits the self-adaptive capacity of real-parameter crossover operators with the aim of producing an effective local tuning on the solutions (accuracy). An important aspect of the memetic algorithm proposed is that it adaptively assigns different local search probabilities to individuals. It was observed that the algorithm adjusts the global/local search balance according to the particularities of each problem instance. Experimental results show that, for a wide range of problems, the method we propose here consistently outperforms other real-coded memetic algorithms which appeared in the literature.
29
DEVARENNE, ISABELLE, HAKIM MABED, and ALEXANDRE CAMINADA. "INTELLIGENT NEIGHBORHOOD EXPLORATION IN LOCAL SEARCH METHOD." International Journal on Artificial Intelligence Tools 17, no. 01 (February 2008): 195–204. http://dx.doi.org/10.1142/s0218213008003844.
Анотація:
Standard tabu search methods are based on the complete exploration of current solution neighborhood. However, for some problems due to the neighborhood size or to the fitness evaluation complexity, the total exploration of the neighborhood is impractical. The main purpose of this paper is to propose a local search method with no enumeration procedure. In other words, a single solution is examined at each iteration and retained for the future iterations. The idea is to randomly select one solution among a sub-set of the neighborhood of the current one. An adaptive exploration of neighborhood, using extension and restriction mechanisms represented by loop detection and tabu list structure, determines this sub-set. This approach is applied to the K-coloring problem and evaluated on standard benchmarks like DIMACS. The objective is to show how a generic method, without full neighborhood exploration, degradation control and problem-oriented operators, provides a very competitive results comparing to the best dedicated algorithms for graph coloring problems published in the literature.
30
Ma, Zhenfang, Kaizhou Gao, Hui Yu, and Naiqi Wu. "Solving Heterogeneous USV Scheduling Problems by Problem-Specific Knowledge Based Meta-Heuristics with Q-Learning." Mathematics 12, no. 2 (January 19, 2024): 339. http://dx.doi.org/10.3390/math12020339.
Анотація:
This study focuses on the scheduling problem of heterogeneous unmanned surface vehicles (USVs) with obstacle avoidance pretreatment. The goal is to minimize the overall maximum completion time of USVs. First, we develop a mathematical model for the problem. Second, with obstacles, an A* algorithm is employed to generate a path between two points where tasks need to be performed. Third, three meta-heuristics, i.e., simulated annealing (SA), genetic algorithm (GA), and harmony search (HS), are employed and improved to solve the problems. Based on problem-specific knowledge, nine local search operators are designed to improve the performance of the proposed algorithms. In each iteration, three Q-learning strategies are used to select high-quality local search operators. We aim to improve the performance of meta-heuristics by using Q-learning-based local search operators. Finally, 13 instances with different scales are adopted to validate the effectiveness of the proposed strategies. We compare with the classical meta-heuristics and the existing meta-heuristics. The proposed meta-heuristics with Q-learning are overall better than the compared ones. The results and comparisons show that HS with the second Q-learning, HS + QL2, exhibits the strongest competitiveness (the smallest mean rank value 1.00) among 15 algorithms.
31
LUONG, THÉ VAN, NOUREDINE MELAB, and EL-GHAZALI TALBI. "NEIGHBORHOOD STRUCTURES FOR GPU-BASED LOCAL SEARCH ALGORITHMS." Parallel Processing Letters 20, no. 04 (December 2010): 307–24. http://dx.doi.org/10.1142/s0129626410000260.
Анотація:
Local search algorithms are powerful heuristics for solving computationally hard problems in science and industry. In these methods, designing neighborhood operators to explore large promising regions of the search space may improve the quality of the obtained solutions at the expense of a high-cost computation process. As a consequence, the use of GPU computing provides an efficient way to speed up the search. However, designing applications on a GPU is still complex and many issues have to be faced. We provide a methodology to design and implement different neighborhood structures for LS algorithms on a GPU. The work has been evaluated for binary problems and the obtained results are convincing both in terms of efficiency, quality and robustness of the provided solutions at run time.
32
Soria-Alcaraz, Jorge A., Gabriela Ochoa, Andres Espinal, Marco A. Sotelo-Figueroa, Manuel Ornelas-Rodriguez, and Horacio Rostro-Gonzalez. "A Methodology for Classifying Search Operators as Intensification or Diversification Heuristics." Complexity 2020 (February 13, 2020): 1–10. http://dx.doi.org/10.1155/2020/2871835.
Анотація:
Selection hyper-heuristics are generic search tools that dynamically choose, from a given pool, the most promising operator (low-level heuristic) to apply at each iteration of the search process. The performance of these methods depends on the quality of the heuristic pool. Two types of heuristics can be part of the pool: diversification heuristics, which help to escape from local optima, and intensification heuristics, which effectively exploit promising regions in the vicinity of good solutions. An effective search strategy needs a balance between these two strategies. However, it is not straightforward to categorize an operator as intensification or diversification heuristic on complex domains. Therefore, we propose an automated methodology to do this classification. This brings methodological rigor to the configuration of an iterated local search hyper-heuristic featuring diversification and intensification stages. The methodology considers the empirical ranking of the heuristics based on an estimation of their capacity to either diversify or intensify the search. We incorporate the proposed approach into a state-of-the-art hyper-heuristic solving two domains: course timetabling and vehicle routing. Our results indicate improved performance, including new best-known solutions for the course timetabling problem.
33
Viana, Monique Simplicio, Orides Morandin Junior, and Rodrigo Colnago Contreras. "A Modified Genetic Algorithm with Local Search Strategies and Multi-Crossover Operator for Job Shop Scheduling Problem." Sensors 20, no. 18 (September 22, 2020): 5440. http://dx.doi.org/10.3390/s20185440.
Анотація:
It is not uncommon for today’s problems to fall within the scope of the well-known class of NP-Hard problems. These problems generally do not have an analytical solution, and it is necessary to use meta-heuristics to solve them. The Job Shop Scheduling Problem (JSSP) is one of these problems, and for its solution, techniques based on Genetic Algorithm (GA) form the most common approach used in the literature. However, GAs are easily compromised by premature convergence and can be trapped in a local optima. To address these issues, researchers have been developing new methodologies based on local search schemes and improvements to standard mutation and crossover operators. In this work, we propose a new GA within this line of research. In detail, we generalize the concept of a massive local search operator; we improved the use of a local search strategy in the traditional mutation operator; and we developed a new multi-crossover operator. In this way, all operators of the proposed algorithm have local search functionality beyond their original inspirations and characteristics. Our method is evaluated in three different case studies, comprising 58 instances of literature, which prove the effectiveness of our approach compared to traditional JSSP solution methods.
34
Fosin, Juraj, Davor Davidović, and Tonči Carić. "A GPU Implementation of Local Search Operators for Symmetric Travelling Salesman Problem." PROMET - Traffic&Transportation 25, no. 3 (June 19, 2013): 225–34. http://dx.doi.org/10.7307/ptt.v25i3.300.
Анотація:
The Travelling Salesman Problem (TSP) is one of the most studied combinatorial optimization problem which is significant in many practical applications in transportation problems. The TSP problem is NP-hard problem and requires large computation power to be solved by the exact algorithms. In the past few years, fast development of general-purpose Graphics Processing Units (GPUs) has brought huge improvement in decreasing the applications’ execution time. In this paper, we implement 2-opt and 3-opt local search operators for solving the TSP on the GPU using CUDA. The novelty presented in this paper is a new parallel iterated local search approach with 2-opt and 3-opt operators for symmetric TSP, optimized for the execution on GPUs. With our implementation large TSP problems (up to 85,900 cities) can be solved using the GPU. We will show that our GPU implementation can be up to 20x faster without losing quality for all TSPlib problems as well as for our CRO TSP problem.
35
Mendoza, Martha, Susana Bonilla, Clara Noguera, Carlos Cobos, and Elizabeth León. "Extractive single-document summarization based on genetic operators and guided local search." Expert Systems with Applications 41, no. 9 (July 2014): 4158–69. http://dx.doi.org/10.1016/j.eswa.2013.12.042.
36
Pongchairerks, Pisut. "An Enhanced Two-Level Metaheuristic Algorithm with Adaptive Hybrid Neighborhood Structures for the Job-Shop Scheduling Problem." Complexity 2020 (June 28, 2020): 1–15. http://dx.doi.org/10.1155/2020/3489209.
Анотація:
For solving the job-shop scheduling problem (JSP), this paper proposes a novel two-level metaheuristic algorithm, where its upper-level algorithm controls the input parameters of its lower-level algorithm. The lower-level algorithm is a local search algorithm searching for an optimal JSP solution within a hybrid neighborhood structure. To generate each neighbor solution, the lower-level algorithm randomly uses one of two neighbor operators by a given probability. The upper-level algorithm is a population-based search algorithm developed for controlling the five input parameters of the lower-level algorithm, i.e., a perturbation operator, a scheduling direction, an ordered pair of two neighbor operators, a probability of selecting a neighbor operator, and a start solution-representing permutation. Many operators are proposed in this paper as options for the perturbation and neighbor operators. Under the control of the upper-level algorithm, the lower-level algorithm can be evolved in its input-parameter values and neighborhood structure. Moreover, with the perturbation operator and the start solution-representing permutation controlled, the two-level metaheuristic algorithm performs like a multistart iterated local search algorithm. The experiment’s results indicated that the two-level metaheuristic algorithm outperformed its previous variant and the two other high-performing algorithms in terms of solution quality.
37
HARYANTO, Zelania In, and Niniet Indah ARVITRIDA. "Improvement of Solution Using Local Search Operators on the Multi-Trip Electric Vehicle Routing Problem Backhaul with Time Window." Eurasia Proceedings of Science Technology Engineering and Mathematics 23 (October 16, 2023): 316–31. http://dx.doi.org/10.55549/epstem.1368274.
Анотація:
In order to reduce greenhouse gas emissions, logistics companies are strongly encouraged to make their operations more environmentally friendly through efficient solutions by implementing electric vehicles (EVs). However, the driving range is one of the aspects that restricts the introduction of EVs in logistics fleets as it poses new challenges in designing distribution routes. In this regard, this paper investigates the issue of the Electric Vehicle Routing Problem (EVRP) raised by logistics companies in real time. There are many models that extend the classic VRP model to consider electric vehicles, but VRP by combining the features of capacity VRP, VRP with time window, backhaul VRP, multi-trip VRP, and electric VRP (MT-EVRPBTW) has not been worked out yet. We present a mathematical model of the MT-EVRPBTW to explain the problem in detail with the objective function to minimize the total distance travelled, where each vehicle could be charged nightly at the depot and during the day at the rest time of the driver in the depot. A feasible initial solution is built using a constructive heuristic to solve this problem, namely, the sequential insertion heuristic, which will be done by improving the solution using Local Search operators. Several Local Search processes using inter-route and intra-route operators for improvement solutions are tested and compared to their performance in measuring the impact of Local Search operator usage on overall travelled distance. Computational experiments for five Local Search operators will be presented and analyzed based on data from one of Indonesia’s post and parcel companies.
38
Zamani, Reza. "Integrating Iterative Crossover Capability in Orthogonal Neighborhoods for Scheduling Resource-Constrained Projects." Evolutionary Computation 21, no. 2 (May 2013): 341–60. http://dx.doi.org/10.1162/evco_a_00085.
Анотація:
An effective hybrid evolutionary search method is presented which integrates a genetic algorithm with a local search. Whereas its genetic algorithm improves the solutions obtained by its local search, its local search component utilizes a synergy between two neighborhood schemes in diversifying the pool used by the genetic algorithm. Through the integration of these two searches, the crossover operators further enhance the solutions that are initially local optimal for both neighborhood schemes; and the employed local search provides fresh solutions for the pool whenever needed. The joint endeavor of its local search mechanism and its genetic algorithm component has made the method both robust and effective. The local search component examines unvisited regions of search space and consequently diversifies the search; and the genetic algorithm component recombines essential pieces of information existing in several high-quality solutions and intensifies the search. It is through striking such a balance between diversification and intensification that the method exploits the structure of search space and produces superb solutions. The method has been implemented as a procedure for the resource-constrained project scheduling problem. The computational experiments on 2,040 benchmark instances indicate that the procedure is very effective.
39
Li, Jun-qing, Quan-ke Pan, and Kun Mao. "Hybrid Particle Swarm Optimization for Hybrid Flowshop Scheduling Problem with Maintenance Activities." Scientific World Journal 2014 (2014): 1–11. http://dx.doi.org/10.1155/2014/596850.
Анотація:
A hybrid algorithm which combines particle swarm optimization (PSO) and iterated local search (ILS) is proposed for solving the hybrid flowshop scheduling (HFS) problem with preventive maintenance (PM) activities. In the proposed algorithm, different crossover operators and mutation operators are investigated. In addition, an efficient multiple insert mutation operator is developed for enhancing the searching ability of the algorithm. Furthermore, an ILS-based local search procedure is embedded in the algorithm to improve the exploitation ability of the proposed algorithm. The detailed experimental parameter for the canonical PSO is tuning. The proposed algorithm is tested on the variation of 77 Carlier and Néron’s benchmark problems. Detailed comparisons with the present efficient algorithms, including hGA, ILS, PSO, and IG, verify the efficiency and effectiveness of the proposed algorithm.
40
Satman, Mehmet Hakan, and Emre Akadal. "Machine-coded genetic operators and their performances in floating-point genetic algorithms." International Journal of Advanced Mathematical Sciences 5, no. 1 (January 25, 2017): 8. http://dx.doi.org/10.14419/ijams.v5i1.7128.
Анотація:
Machine-coded genetic algorithms (MCGAs) use the byte representation of floating-point numbers which are encoded in the computer memory. Use of the byte alphabet makes classical crossover operators directly applicable in the floating-point genetic algorithms. Since effect of the byte-based mutation operator depends on the location of the mutated byte, the byte-based mutation operator mimics the functionality of its binary counterpart. In this paper, we extend the MCGA by developing new type of byte-based genetic operators including a random mutation and a random dynamic mutation operator. We perform a simulation study to compare the performances of the byte-based operators with the classical FPGA operators using a set of test functions. The prepared software package, which is freely available for downloading, is used for the simulations. It is shown that the byte-based genetic search obtains precise results by carrying out the both exploration and exploitation tasks by discovering new fields of the search space and performing a local fine-tuning. It is also shown that the introduced byte-based operators improve the search capabilities of FPGAs by means of convergence rate and precision even if the decision variables are in larger domains.
41
Molina, Daniel, Manuel Lozano, Carlos García-Martínez, and Francisco Herrera. "Memetic Algorithms for Continuous Optimisation Based on Local Search Chains." Evolutionary Computation 18, no. 1 (March 2010): 27–63. http://dx.doi.org/10.1162/evco.2010.18.1.18102.
Анотація:
Memetic algorithms with continuous local search methods have arisen as effective tools to address the difficulty of obtaining reliable solutions of high precision for complex continuous optimisation problems. There exists a group of continuous local search algorithms that stand out as exceptional local search optimisers. However, on some occasions, they may become very expensive, because of the way they exploit local information to guide the search process. In this paper, they are called intensive continuous local search methods. Given the potential of this type of local optimisation methods, it is interesting to build prospective memetic algorithm models with them. This paper presents the concept of local search chain as a springboard to design memetic algorithm approaches that can effectively use intense continuous local search methods as local search operators. Local search chain concerns the idea that, at one stage, the local search operator may continue the operation of a previous invocation, starting from the final configuration (initial solution, strategy parameter values, internal variables, etc.) reached by this one. The proposed memetic algorithm favours the formation of local search chains during the memetic algorithm run with the aim of concentrating local tuning in search regions showing promise. In order to study the performance of the new memetic algorithm model, an instance is implemented with CMA-ES as an intense local search method. The benefits of the proposal in comparison to other kinds of memetic algorithms and evolutionary algorithms proposed in the literature to deal with continuous optimisation problems are experimentally shown. Concretely, the empirical study reveals a clear superiority when tackling high-dimensional problems.
42
Guo, Jia, Binghua Shi, Ke Yan, Yi Di, Jianyu Tang, Haiyang Xiao, and Yuji Sato. "A twinning bare bones particle swarm optimization algorithm." PLOS ONE 17, no. 5 (May 2, 2022): e0267197. http://dx.doi.org/10.1371/journal.pone.0267197.
Анотація:
A twinning bare bones particle swarm optimization(TBBPSO) algorithm is proposed in this paper. The TBBPSO is combined by two operators, the twins grouping operator (TGO) and the merger operator (MO). The TGO aims at the reorganization of the particle swarm. Two particles will form as a twin and influence each other in subsequent iterations. In a twin, one particle is designed to do the global search while the other one is designed to do the local search. The MO aims at merging the twins and enhancing the search ability of the main group. Two operators work together to enhance the local minimum escaping ability of proposed methods. In addition, no parameter adjustment is needed in TBBPSO, which means TBBPSO can solve different types of optimization problems without previous information or parameter adjustment. In the benchmark functions test, the CEC2014 benchmark functions are used. Experimental results prove that proposed methods can present high precision results for various types of optimization problems.
43
Li, Kun, and Huixin Tian. "A DE-Based Scatter Search for Global Optimization Problems." Discrete Dynamics in Nature and Society 2015 (2015): 1–9. http://dx.doi.org/10.1155/2015/303125.
Анотація:
This paper proposes a hybrid scatter search (SS) algorithm for continuous global optimization problems by incorporating the evolution mechanism of differential evolution (DE) into the reference set updated procedure of SS to act as the new solution generation method. This hybrid algorithm is called a DE-based SS (SSDE) algorithm. Since different kinds of mutation operators of DE have been proposed in the literature and they have shown different search abilities for different kinds of problems, four traditional mutation operators are adopted in the hybrid SSDE algorithm. To adaptively select the mutation operator that is most appropriate to the current problem, an adaptive mechanism for the candidate mutation operators is developed. In addition, to enhance the exploration ability of SSDE, a reinitialization method is adopted to create a new population and subsequently construct a new reference set whenever the search process of SSDE is trapped in local optimum. Computational experiments on benchmark problems show that the proposed SSDE is competitive or superior to some state-of-the-art algorithms in the literature.
44
Lin, Yung Chien. "A Memetic Algorithm for Mixed-Integer Optimization Problems." Applied Mechanics and Materials 284-287 (January 2013): 2970–74. http://dx.doi.org/10.4028/www.scientific.net/amm.284-287.2970.
Анотація:
Evolutionary algorithms (EAs) are population-based global search methods. Memetic Algorithms (MAs) are hybrid EAs that combine genetic operators with local search methods. With global exploration and local exploitation in search space, MAs are capable of obtaining more high-quality solutions. On the other hand, mixed-integer hybrid differential evolution (MIHDE), as an EA-based search algorithm, has been successfully applied to many mixed-integer optimization problems. In this paper, a memetic algorithm based on MIHDE is developed for solving mixed-integer constrained optimization problems. The proposed algorithm is implemented and tested on a benchmark mixed-integer constrained optimization problem. Experimental results show that the proposed algorithm can find a better optimal solution compared with some other search algorithms.
45
Weise, Thomas, and Raymond Chiong. "A Novel Extremal Optimization Approach for the Template Design Problem." International Journal of Organizational and Collective Intelligence 2, no. 2 (April 2011): 1–16. http://dx.doi.org/10.4018/joci.2011040101.
Анотація:
This paper presents a novel algorithm based on extremal dynamics for tackling the template design problem, a constrained optimization problem that originated in the printing industry. The template design problem involves printing several variations of a design onto one or more stencil sheets, where the aims are to minimize the number of stencils as well as the overproduction of prints of a particular design. In this paper, the authors introduce several search operators to be used in conjunction with the proposed algorithm. Different combinations of these search operators are tested via extensive numerical experiments. The solutions indicate that the algorithm is a feasible approach for template design optimization. In particular, hybridizing it with a deterministic local search has proven to be very effective.
46
Wu, Daqing, Rong Yan, Hongtao Jin, and Fengmao Cai. "An Adaptive Nutcracker Optimization Approach for Distribution of Fresh Agricultural Products with Dynamic Demands." Agriculture 13, no. 7 (July 19, 2023): 1430. http://dx.doi.org/10.3390/agriculture13071430.
Анотація:
In the operational, strategic and tactical decision-making problems of the agri-food supply chain, the perishable nature of the commodities can represent a particular complexity problem. It is, therefore, appropriate to consider decision support tools that take into account the characteristics of the products, the needs and the requirements of producers, sellers and consumers. This paper presents a green vehicle routing model for fresh agricultural product distribution and designs an adaptive hybrid nutcracker optimization algorithm (AH-NOA) based on k-means clustering to solve the problem. In the process, the AH-NOA uses the CW algorithm to increase population diversity and adds genetic operators and local search operators to enhance the global search ability for nutcracker optimization. Finally, the experimental data show that the proposed approaches effectively avoid local optima, promote population diversity and reduce total costs and carbon emission costs.
47
Yu, Hang, Yu Zhang, Pengxing Cai, Junyan Yi, Sheng Li, and Shi Wang. "Stochastic Multiple Chaotic Local Search-Incorporated Gradient-Based Optimizer." Discrete Dynamics in Nature and Society 2021 (December 2, 2021): 1–16. http://dx.doi.org/10.1155/2021/3353926.
Анотація:
In this study, a hybrid metaheuristic algorithm chaotic gradient-based optimizer (CGBO) is proposed. The gradient-based optimizer (GBO) is a novel metaheuristic inspired by Newton’s method which has two search strategies to ensure excellent performance. One is the gradient search rule (GSR), and the other is local escaping operation (LEO). GSR utilizes the gradient method to enhance ability of exploitation and convergence rate, and LEO employs random operators to escape the local optima. It is verified that gradient-based metaheuristic algorithms have obvious shortcomings in exploration. Meanwhile, chaotic local search (CLS) is an efficient search strategy with randomicity and ergodicity, which is usually used to improve global optimization algorithms. Accordingly, we incorporate GBO with CLS to strengthen the ability of exploration and keep high-level population diversity for original GBO. In this study, CGBO is tested with over 30 CEC2017 benchmark functions and a parameter optimization problem of the dendritic neuron model (DNM). Experimental results indicate that CGBO performs better than other state-of-the-art algorithms in terms of effectiveness and robustness.
48
Lin, Yung Chien. "A Mixed-Integer Memetic Algorithm Applied to Batch Process Optimization." Applied Mechanics and Materials 300-301 (February 2013): 645–48. http://dx.doi.org/10.4028/www.scientific.net/amm.300-301.645.
Анотація:
Evolutionary algorithms (EAs) are population-based global search methods. Memetic Algorithms (MAs) are hybrid EAs that combine genetic operators with local search methods. With global exploration and local exploitation in search space, MAs are capable of obtaining more high-quality solutions. On the other hand, mixed-integer hybrid differential evolution (MIHDE), as an EA-based search algorithm, has been successfully applied to many mixed-integer optimization problems. In this paper, a mixed-integer memetic algorithm based on MIHDE is developed for solving mixed-integer constrained optimization problems. The proposed algorithm is implemented and applied to the optimal design of batch processes. Experimental results show that the proposed algorithm can find a better optimal solution compared with some other search algorithms.
49
Abuhamdah, Anmar, Wadii Boulila, Ghaith M. Jaradat, Anas M. Quteishat, Mutasem K. Alsmadi, and Ibrahim A. Almarashdeh. "A novel population-based local search for nurse rostering problem." International Journal of Electrical and Computer Engineering (IJECE) 11, no. 1 (February 1, 2021): 471. http://dx.doi.org/10.11591/ijece.v11i1.pp471-480.
Анотація:
Population-based approaches regularly are better than single based (local search) approaches in exploring the search space. However, the drawback of population-based approaches is in exploiting the search space. Several hybrid approaches have proven their efficiency through different domains of optimization problems by incorporating and integrating the strength of population and local search approaches. Meanwhile, hybrid methods have a drawback of increasing the parameter tuning. Recently, population-based local search was proposed for a university course-timetabling problem with fewer parameters than existing approaches, the proposed approach proves its effectiveness. The proposed approach employs two operators to intensify and diversify the search space. The first operator is applied to a single solution, while the second is applied for all solutions. This paper aims to investigate the performance of population-based local search for the nurse rostering problem. The INRC2010 database with a dataset composed of 69 instances is used to test the performance of PB-LS. A comparison was made between the performance of PB-LS and other existing approaches in the literature. Results show good performances of proposed approach compared to other approaches, where population-based local search provided best results in 55 cases over 69 instances used in experiments.
50
Yuan, Xiaohui, Zhihuan Chen, Yanbin Yuan, Yuehua Huang, and Xiaopan Zhang. "A Strength Pareto Gravitational Search Algorithm for Multi-Objective Optimization Problems." International Journal of Pattern Recognition and Artificial Intelligence 29, no. 06 (August 12, 2015): 1559010. http://dx.doi.org/10.1142/s0218001415590107.
Анотація:
A novel strength Pareto gravitational search algorithm (SPGSA) is proposed to solve multi-objective optimization problems. This SPGSA algorithm utilizes the strength Pareto concept to assign the fitness values for agents and uses a fine-grained elitism selection mechanism to keep the population diversity. Furthermore, the recombination operators are modeled in this approach to decrease the possibility of trapping in local optima. Experiments are conducted on a series of benchmark problems that are characterized by difficulties in local optimality, nonuniformity, and nonconvexity. The results show that the proposed SPGSA algorithm performs better in comparison with other related works. On the other hand, the effectiveness of two subtle means added to the GSA are verified, i.e. the fine-grained elitism selection and the use of SBX and PMO operators. Simulation results show that these measures not only improve the convergence ability of original GSA, but also preserve the population diversity adequately, which enables the SPGSA algorithm to have an excellent ability that keeps a desirable balance between the exploitation and exploration so as to accelerate the convergence speed to the true Pareto-optimal front.