Journal articles: 'Search algorithms'

1

Siddique, Nazmul, and Hojjat Adeli. "Hybrid Harmony Search Algorithms." International Journal on Artificial Intelligence Tools 24, no. 06 (December 2015): 1530001. http://dx.doi.org/10.1142/s021821301530001x.

Full text

Abstract:

Harmony search algorithm (HSA) is a music-inspired population-based meta-heuristic search and optimization algorithm. In order to improve exploration or global search ability, exploit local search more effectively, increase convergence speed, improve solution quality, and minimize computational cost, researchers have advanced the concept of hybridizing HSA with other algorithms. This article presents a review of hybrid harmony search algorithms.

APA, Harvard, Vancouver, ISO, and other styles

2

Aine, Sandip, and Maxim Likhachev. "Search Portfolio with Sharing." Proceedings of the International Conference on Automated Planning and Scheduling 26 (March 30, 2016): 11–19. http://dx.doi.org/10.1609/icaps.v26i1.13760.

Full text

Abstract:

Over the years, a number of search algorithms have been proposed in AI literature, ranging from best-first to depth-first searches, from incomplete to optimal searches, from linear memory to unbounded memory searches; each having their strengths and weaknesses. The variability in performance of these algorithms makes algorithm selection a hard problem, especially for performance critical domains. Algorithm portfolios alleviate this problem by simultaneously running multiple algorithms to solve a given problem instance, exploiting their diversity. In general, the portfolio methods do not share information among candidate algorithms. Our work is based on the observation that if the algorithms within a portfolio can share information, it may significantly enhance the performance, as one algorithm can now utilize partial results computed by other algorithms. To this end, we introduce a new search framework, called Search Portfolio with Sharing (SP-S), which uses multiple algorithms to explore a given state-space in an integrated manner, seamlessly combining the partial solutions, while preserving the constraints/characteristics of the candidate algorithms. In addition, SP-S can be easily adopted to guarantee theoretical properties like completeness, bounded sub-optimality, and bounded re-expansions. We describe the basics of the SP-S framework and explain how different classes of search algorithms can be integrated in SP-S. We discuss its theoretical properties and present experimental results for multiple domains, demonstrating the utility of such a shared approach.

APA, Harvard, Vancouver, ISO, and other styles

3

KOREPIN, VLADIMIR E., and YING XU. "QUANTUM SEARCH ALGORITHMS." International Journal of Modern Physics B 23, no. 31 (December 20, 2009): 5727–58. http://dx.doi.org/10.1142/s0217979209054922.

Full text

Abstract:

This article reviews recent progress in quantum database search algorithms. The subject is presented in a self-contained and pedagogical way. The problem of searching a large database (a Hilbert space) for a target item is performed by the famous Grover algorithm which locates the target item with high probability and a quadratic speed-up compared with the corresponding classical algorithm. If the database is partitioned into blocks and one is searching for the block containing the target item instead of the target item itself, then the problem is referred to as partial search. Partial search trades accuracy for speed and the most efficient version is the Grover–Radhakrishnan–Korepin (GRK) algorithm. The target block can be further partitioned into sub-blocks so that GRK's can be performed in a sequence called a hierarchy. We study the Grover search and GRK partial search in detail and prove that a GRK hierarchy is less efficient than a direct GRK partial search. Both the Grover search and the GRK partial search can be generalized to the case with several target items (or target blocks for a GRK). The GRK partial search algorithm can also be represented in terms of group theory.

APA, Harvard, Vancouver, ISO, and other styles

4

Ambainis, A. "Quantum search algorithms." ACM SIGACT News 35, no. 2 (June 2004): 22–35. http://dx.doi.org/10.1145/992287.992296.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Yan, Shaoqiang, Weidong Liu, Xinqi Li, Ping Yang, Fengxuan Wu, and Zhe Yan. "Comparative Study and Improvement Analysis of Sparrow Search Algorithm." Wireless Communications and Mobile Computing 2022 (August 31, 2022): 1–15. http://dx.doi.org/10.1155/2022/4882521.

Full text

Abstract:

To solve the problem that the emerging sparrow search algorithm (SSA) lacks systematic comparison and analysis with other classical algorithms, this paper first introduces the principle of the sparrow search algorithm and then describes the mathematical model and algorithm description of the sparrow search algorithm. By comparing several classical intelligent algorithms with particle swarm optimization (PSO), differential evolution (DE), and gray wolf optimizer (GWO), the sparrow search algorithm’s theory and model are systematically compared and analyzed, and the advantages and disadvantages of SSA are summarized. Finally, based on the above research and previous research, the limitations of SSA and current improved SSA are analyzed, which provides ideas for further improvement of the algorithm.

APA, Harvard, Vancouver, ISO, and other styles

6

Tobing, Fenina Adline Twince, and Rena Nainggolan. "ANALISIS PERBANDINGAN PENGGUNAAN METODE BINARY SEARCH DENGAN REGULAR SEARCH EXPRESSION." METHOMIKA Jurnal Manajemen Informatika dan Komputerisasi Akuntansi 4, no. 2 (October 31, 2021): 168–72. http://dx.doi.org/10.46880/jmika.vol4no2.pp168-172.

Full text

Abstract:

The search system is a feature that is indispensable for an application or website. By comparing two algorithms that are often used, namely Binary Search and Regular Search Expression (REGEX) algorithms in a simple search system is a problem that will be discussed in this journal. Analysis of the two algorithms is carried out to solve problems in the search system so that the search algorithm can be applied more precisely and effectively. The results prove that the Binary Search has the advantage of searching large amounts of data in an ordered state and has a more effective iteration. While the Regular Expression Search has the advantage of performing searches that are not completely known about the results and keys, besides that this algorithm also allows you to search based on certain patterns in the data.

APA, Harvard, Vancouver, ISO, and other styles

7

Chen, Jingwei, Nathan Sturtevant, William Doyle, and Wheeler Ruml. "Revisiting Suboptimal Search." Proceedings of the International Symposium on Combinatorial Search 10, no. 1 (September 1, 2021): 18–25. http://dx.doi.org/10.1609/socs.v10i1.18498.

Full text

Abstract:

Suboptimal search algorithms can often solve much larger problems than optimal search algorithms, and thus have broad practical use. This paper returns to early algorithms like WA*, A*_e and Optimistic search. It studies the commonalities between these approaches in order to build a new bounded-suboptimal algorithm. Combined with recent research on avoiding node re-expansions in bounded-optimal search, a new solution quality bound is developed, which often provides proof of the solution bound much earlier during the search. Put together, these ideas provide a new state-of-the-art in bounded-optimal search.

APA, Harvard, Vancouver, ISO, and other styles

8

Soongsathitanon, S., W. L. Woo, and S. S. Dlay. "Fast search algorithms for video coding using orthogonal logarithmic search algorithm." IEEE Transactions on Consumer Electronics 51, no. 2 (May 2005): 552–59. http://dx.doi.org/10.1109/tce.2005.1468001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Huang, J., and A. Darwiche. "The Language of Search." Journal of Artificial Intelligence Research 29 (June 24, 2007): 191–219. http://dx.doi.org/10.1613/jair.2097.

Full text

Abstract:

This paper is concerned with a class of algorithms that perform exhaustive search on propositional knowledge bases. We show that each of these algorithms defines and generates a propositional language. Specifically, we show that the trace of a search can be interpreted as a combinational circuit, and a search algorithm then defines a propositional language consisting of circuits that are generated across all possible executions of the algorithm. In particular, we show that several versions of exhaustive DPLL search correspond to such well-known languages as FBDD, OBDD, and a precisely-defined subset of d-DNNF. By thus mapping search algorithms to propositional languages, we provide a uniform and practical framework in which successful search techniques can be harnessed for compilation of knowledge into various languages of interest, and a new methodology whereby the power and limitations of search algorithms can be understood by looking up the tractability and succinctness of the corresponding propositional languages.

APA, Harvard, Vancouver, ISO, and other styles

10

SHAH, I. "DIRECT ALGORITHMS FOR FINDING MINIMAL UNSATISFIABLE SUBSETS IN OVER-CONSTRAINED CSPs." International Journal on Artificial Intelligence Tools 20, no. 01 (February 2011): 53–91. http://dx.doi.org/10.1142/s0218213011000036.

Full text

Abstract:

In many situations, an explanation of the reasons behind inconsistency in an overconstrained CSP is required. This explanation can be given in terms of minimal unsatisfiable subsets (MUSes) of constraints. This paper presents algorithms for finding minimal unsatisfiable subsets (MUSes) of constraints in overconstrained CSPs with finite domains and binary constraints. The approach followed is to generate subsets in the subset space, test them for consistency and record the inconsistent subsets found. We present three algorithms as variations of this basic approach. Each algorithm generates subsets in the subset space in a different order and curtails search by employing various search pruning mechanisms. The proposed algorithms are anytime algorithms: a time limit can be set on an algorithm's search and the algorithm can be made to find a subset of MUSes. Experimental evaluation of the proposed algorithms demonstrates that they perform two to three orders of magnitude better than the existing indirect algorithms. Furthermore, the algorithms are able to find MUSes in large CSP benchmarks.

APA, Harvard, Vancouver, ISO, and other styles

11

NASTOS, JAMES, and YONG GAO. "BOUNDED SEARCH TREE ALGORITHMS FOR PARAMETRIZED COGRAPH DELETION: EFFICIENT BRANCHING RULES BY EXPLOITING STRUCTURES OF SPECIAL GRAPH CLASSES." Discrete Mathematics, Algorithms and Applications 04, no. 01 (March 2012): 1250008. http://dx.doi.org/10.1142/s1793830912500085.

Full text

Abstract:

Many fixed-parameter tractable algorithms using a bounded search tree have been repeatedly improved, often by describing a larger number of branching rules involving an increasingly complex case analysis. We introduce a novel and general search strategy that branches on the forbidden subgraphs of a graph class relaxation. By using the class of P4-sparse graphs as the relaxed graph class, we obtain efficient bounded search tree algorithms for several parametrized deletion problems. We give the first non-trivial bounded search tree algorithms for the cograph edge-deletion problem and the trivially perfect edge-deletion problems. For the cograph vertex deletion problem, a refined analysis of the runtime of our simple bounded search algorithm gives a faster exponential factor than those algorithms designed with the help of complicated case distinctions and non-trivial running time analysis [R. Niedermeier and P. Rossmanith, An efficient fixed-parameter algorithm for 3-hitting set, J. Discrete Algorithms1(1) (2003) 89–102] and computer-aided branching rules [J. Gramm, J. Guo, F. Hüffner and R. Niedermeier, Automated generation of search tree algorithms for hard graph modification problems, Algorithmica39(4) (2004) 321–347].

APA, Harvard, Vancouver, ISO, and other styles

12

Moraes, Rubens O., Mario A. Nascimento, and Levi H. S. Lelis. "Asymmetric Action Abstractions for Planning in Real-Time Strategy Games." Journal of Artificial Intelligence Research 75 (November 30, 2022): 1103–37. http://dx.doi.org/10.1613/jair.1.13769.

Full text

Abstract:

Action abstractions restrict the number of legal actions available for real-time planning in zero-sum extensive-form games, thus allowing algorithms to focus their search on a set of promising actions. Even though unabstracted game trees can lead to optimal policies, due to real-time constraints and the tree size, they are not a practical choice. In this context, we introduce an action abstraction scheme which we call asymmetric action abstraction. Asymmetric abstractions allow search algorithms to “pay more attention” to some aspects of the game by unevenly dividing the algorithm’s search effort amongst different aspects of the game. We also introduce four algorithms that search in asymmetrically abstracted game trees to evaluate the effectiveness of our abstraction schemes. Two of our algorithms are adaptations of algorithms developed for searching in action-abstracted spaces, Portfolio Greedy Search and Stratified Strategy Selection, and the other two are adaptations of an algorithm developed for searching in unabstracted spaces, NaïveMCTS. An extensive set of experiments in a real-time strategy game shows that search algorithms using asymmetric abstractions are able to outperform all other search algorithms tested.

APA, Harvard, Vancouver, ISO, and other styles

13

Naseri, Narjes Khatoon, Elankovan A. Sundararajan, Masri Ayob, and Amin Jula. "Smart Root Search (SRS): A Novel Nature-Inspired Search Algorithm." Symmetry 12, no. 12 (December 7, 2020): 2025. http://dx.doi.org/10.3390/sym12122025.

Full text

Abstract:

In this paper, a novel heuristic search algorithm called Smart Root Search (SRS) is proposed. SRS employs intelligent foraging behavior of immature, mature and hair roots of plants to explore and exploit the problem search space simultaneously. SRS divides the search space into several subspaces. It thereupon utilizes the branching and drought operations to focus on richer areas of promising subspaces while extraneous ones are not thoroughly ignored. To achieve this, the smart reactions of the SRS model are designed to act based on analyzing the heterogeneous conditions of various sections of different search spaces. In order to evaluate the performance of the SRS, it was tested on a set of known unimodal and multimodal test functions. The results were then compared with those obtained using genetic algorithms, particle swarm optimization, differential evolution and imperialist competitive algorithms and then analyzed statistically. The results demonstrated that the SRS outperformed comparative algorithms for 92% and 82% of the investigated unimodal and multimodal test functions, respectively. Therefore, the SRS is a promising nature-inspired optimization algorithm.

APA, Harvard, Vancouver, ISO, and other styles

14

Stern, Roni, Rami Puzis, and Ariel Felner. "Potential Search: A New Greedy Anytime Heuristic Search." Proceedings of the International Symposium on Combinatorial Search 1, no. 1 (August 25, 2010): 119–20. http://dx.doi.org/10.1609/socs.v1i1.18177.

Full text

Abstract:

In this paper we explore a novel approach for anytime heuristic search, in which the node that is most probable to improve the incumbent solution is expanded first. This is especially suited for the "anytime aspect" of anytime algorithms - the possibility that the algorithm will be be halted anytime throughout the search. The potential of a node to improve the incumbent solution is estimated by a custom cost function, resulting in Potential Search, an anytime best-first search. Experimental results on the 15-puzzle and on the key player problem in communication networks (KPP-COM) show that this approach is competitive with state-of-the-art anytime heuristic search algorithms, and is more robust.

APA, Harvard, Vancouver, ISO, and other styles

15

Song, Qi, Yourui Huang, Wenhao Lai, Tao Han, Shanyong XU, and Xue Rong. "Multi-membrane search algorithm." PLOS ONE 16, no. 12 (December 6, 2021): e0260512. http://dx.doi.org/10.1371/journal.pone.0260512.

Full text

Abstract:

This research proposes a new multi-membrane search algorithm (MSA) based on cell biological behavior. Cell secretion protein behavior and cell division and fusion strategy are the main inspirations for the algorithm. In order to verify the performance of the algorithm, we used 19 benchmark functions to compare the MSA test results with MVO, GWO, MFO and ALO. The number of iterations of each algorithm on each benchmark function is 100, the population number is 10, and the running is repeated 50 times, and the average and standard deviation of the results are recorded. Tests show that the MSA is competitive in unimodal benchmark functions and multi-modal benchmark functions, and the results in composite benchmark functions are all superior to MVO, MFO, ALO, and GWO algorithms. This paper also uses MSA to solve two classic engineering problems: welded beam design and pressure vessel design. The result of welded beam design is 1.7252, and the result of pressure vessel design is 5887.7052, which is better than other comparison algorithms. Statistical experiments show that MSA is a high-performance algorithm that is competitive in unimodal and multimodal functions, and its performance in compound functions is significantly better than MVO, MFO, ALO, and GWO algorithms.

APA, Harvard, Vancouver, ISO, and other styles

16

Sharma, Keshav, Pradyum Shetty, Rajith Shetty, and Prof Savita Lade. "Directional Search Algorithm Analysis." International Journal for Research in Applied Science and Engineering Technology 10, no. 3 (March 31, 2022): 2258–64. http://dx.doi.org/10.22214/ijraset.2022.41117.

Full text

Abstract:

Abstract: Apps such as Google maps have inevitably become the go-to app for travelling & we are all heavily reliant on them. But as developers can the ones starting in this field grasp the concept of these algorithms easily? Being able to use such navigational tools outdoors has been very helpful but the same cannot be applied indoors. everywhere. But understanding the core concepts & which algorithm will perform how in different situations can bring about a big change. In this project we plan to help the end-user ( developers, students ) visually study the search algorithms for the shortest distance between two points and how it is calculated by the various algorithms, thus being able to pick the best one possible. One of the main reasons to add visualizations is that we, humans, are better visual learners. Keywords: Navigation, Directional Algorithms, GUI, Shortest distance,

APA, Harvard, Vancouver, ISO, and other styles

17

Atzmon, Dor, Roni Stern, and Abdallah Saffidine. "Bounded Suboptimal Game Tree Search." Proceedings of the International Symposium on Combinatorial Search 9, no. 1 (September 1, 2021): 10–18. http://dx.doi.org/10.1609/socs.v9i1.18448.

Full text

Abstract:

Finding the minimax value of a game is an important problem in a variety of fields, including game theory, decision theory, statistics, philosophy, economics, robotics, and security. Classical algorithms such as the Minimax algorithm can be used to find the minimax value, but require iterating over the entire game tree, which is in many cases too large. Alpha-Beta pruning identifies portions of the game tree that are not necessary for finding the minimax value, but in many cases the remaining part of the game tree is still too large to search in reasonable time. For such cases, we propose a class of algorithms that accepts a parameter e and returns a value that is guaranteed to be at most e away from the true minimax value. We lay the theoretical foundation for building such algorithms and present one such algorithm based on Alpha-Beta. Experimentally, we show that our algorithm allows controlling this runtime/solution quality tradeoff effectively.

APA, Harvard, Vancouver, ISO, and other styles

18

Bosler, P. A., E. L. Roesler, M. A. Taylor, and M. Mundt. "Stride Search: a general algorithm for storm detection in high resolution climate data." Geoscientific Model Development Discussions 8, no. 9 (September 8, 2015): 7727–65. http://dx.doi.org/10.5194/gmdd-8-7727-2015.

Full text

Abstract:

Abstract. This article discusses the problem of identifying extreme climate events such as intense storms within large climate data sets. The basic storm detection algorithm is reviewed, which splits the problem into two parts: a spatial search followed by a temporal correlation problem. Two specific implementations of the spatial search algorithm are compared. The commonly used grid point search algorithm is reviewed, and a new algorithm called Stride Search is introduced. Stride Search is designed to work at all latitudes, while grid point searches may fail in polar regions. Results from the two algorithms are compared for the application of tropical cyclone detection, and shown to produce similar results for the same set of storm identification criteria. The time required for both algorithms to search the same data set is compared. Stride Search's ability to search extreme latitudes is demonstrated for the case of polar low detection.

APA, Harvard, Vancouver, ISO, and other styles

19

Korf, Richard E. "Space-efficient search algorithms." ACM Computing Surveys 27, no. 3 (September 1995): 337–39. http://dx.doi.org/10.1145/212094.212120.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Shasha, Dennis, and Nathan Goodman. "Concurrent search structure algorithms." ACM Transactions on Database Systems 13, no. 1 (March 1988): 53–90. http://dx.doi.org/10.1145/42201.42204.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Lange, Dustin, Tobias Vogel, Uwe Draisbach, and Felix Naumann. "Projektseminar „Similarity Search Algorithms“." Datenbank-Spektrum 11, no. 1 (February 12, 2011): 51–57. http://dx.doi.org/10.1007/s13222-011-0046-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Alatas, Bilal. "Chaotic harmony search algorithms." Applied Mathematics and Computation 216, no. 9 (July 2010): 2687–99. http://dx.doi.org/10.1016/j.amc.2010.03.114.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Alkhateeb, Faisal, and Bilal H. Abed-alguni. "A Hybrid Cuckoo Search and Simulated Annealing Algorithm." Journal of Intelligent Systems 28, no. 4 (September 25, 2019): 683–98. http://dx.doi.org/10.1515/jisys-2017-0268.

Full text

Abstract:

Abstract Simulated annealing (SA) proved its success as a single-state optimization search algorithm for both discrete and continuous problems. On the contrary, cuckoo search (CS) is one of the well-known population-based search algorithms that could be used for optimizing some problems with continuous domains. This paper provides a hybrid algorithm using the CS and SA algorithms. The main goal behind our hybridization is to improve the solutions generated by CS using SA to explore the search space in an efficient manner. More precisely, we introduce four variations of the proposed hybrid algorithm. The proposed variations together with the original CS and SA algorithms were evaluated and compared using 10 well-known benchmark functions. The experimental results show that three variations of the proposed algorithm provide a major performance enhancement in terms of best solutions and running time when compared to CS and SA as stand-alone algorithms, whereas the other variation provides a minor enhancement. Moreover, the experimental results show that the proposed hybrid algorithms also outperform some well-known optimization algorithms.

APA, Harvard, Vancouver, ISO, and other styles

24

Sultanova, A. "Comparative Analysis of Optimal Path Search Algorithms." Bulletin of Science and Practice 6, no. 12 (December 15, 2020): 248–55. http://dx.doi.org/10.33619/2414-2948/61/25.

Full text

Abstract:

This article discusses widely used algorithms for finding optimal paths. Currently, there is a fairly wide list of algorithms for the problem of finding the shortest path, and is actively used in mobile robotics to find the optimal route. The article offers a two-level system that performs traffic planning. Comparative analysis of various search methods was carried out: their length, complexity, and a number of turning points. The purpose of the article is to study and compare algorithms from the field of artificial intelligence for finding the shortest path in a maze and a hexagonal grid. Algorithms under study: A* (star), Dijkstra algorithm, BFS, DFS, and Greedy algorithm. Algorithms are compared based on two criteria: the length of the found path and the time it takes to find the path. The results, presented analytically and graphically, show the application of five algorithms for mazes with different size and number of obstacles.

APA, Harvard, Vancouver, ISO, and other styles

25

Zhang, Mengying, Hua Wang, Lin Ge, Hao Cheng, and Feng Cheng. "Automatic Search Algorithms for Near-Field Ferromagnetic Targets Based on Magnetic Anomaly Detection." Mathematical Problems in Engineering 2018 (July 4, 2018): 1–15. http://dx.doi.org/10.1155/2018/2130236.

Full text

Abstract:

For searching and detecting near-field unknown ferromagnetic targets, four automatic search algorithms are proposed based on magnetic anomaly information from any position on planes or in space. Firstly, gradient search algorithms and enhanced gradient search algorithms are deduced using magnetic modulus anomaly information and magnetic vector anomaly information. In each algorithm, there are plane search forms and space search forms considering different practical search situations. Then the magnetic anomaly space data of typical magnetic source of oblique magnetization are forwardly simulated by ANSYS MAXWELL software. The plane distributions of some variables are numerically computed and the search destinations of different algorithms are predicted. Four automatic search algorithms are applied to simulate search paths on three characteristic orthogonal planes and in whole solution space. The factor affecting the performance of algorithms is analyzed. Features of each algorithm in different conditions are analyzed and suitable applications are discussed and verified by the experiment. The results show that proposed search algorithms require few prior information and have real-time performance for searching and tracking magnetic anomaly target.

APA, Harvard, Vancouver, ISO, and other styles

26

Montanaro, A. "Quantum search of partially ordered sets." Quantum Information and Computation 9, no. 7&8 (July 2009): 628–47. http://dx.doi.org/10.26421/qic9.7-8-6.

Full text

Abstract:

We investigate the generalisation of quantum search of unstructured and totally ordered sets to search of partially ordered sets (posets). Two models for poset search are considered. In both models, we show that quantum algorithms can achieve at most a quadratic improvement in query complexity over classical algorithms, up to logarithmic factors; we also give quantum algorithms that almost achieve this optimal reduction in complexity. In one model, we give an improved quantum algorithm for searching forest-like posets; in the other, we give an optimal $O(\sqrt{m})$-query quantum algorithm for searching posets derived from $m \times m$ arrays sorted by rows and columns. This leads to a quantum algorithm that finds the intersection of two sorted lists of $n$ integers in $O(\sqrt{n})$ time, which is optimal.

APA, Harvard, Vancouver, ISO, and other styles

27

Üstüner, Betül, and Erkan Doğan. "Solution of design optimization problems via metaheuristic search methods." Journal of Structural Engineering & Applied Mechanics 5, no. 2 (June 30, 2022): 96–116. http://dx.doi.org/10.31462/jseam.2022.02096116.

Full text

Abstract:

Metaheuristic algorithms inspired by natural phenomena are frequently used in solving optimization problems recently. Just as every problem has its characteristics, every algorithm has its unique structure. Therefore, problem-specific algorithm selection is an important issue. In addition, metaheuristic algorithms are very open to development. Therefore, improved/modified versions of algorithms are common. Working with benchmarking problems and engineering design problems is the best way to compare the performance and reliability of metaheuristic algorithms. In this study, the performances of firefly (FA), particle swarm optimization (PSO), bat algorithm (BA), ant colony optimization (ACO), glow worms (GSO), and hunting search (HuS) algorithms are compared. An enhanced version of the firefly algorithm (RFA) is also recommended and included in the comparison. A benchmark and five engineering design problems were selected for comparison purposes. All algorithms are set to twenty thousand iterations. The results show that the metaheuristic algorithm that gives the best results varies according to the nature of the problem. Moreover, although it does not change the ranking of the algorithm that gives the best result according to the problem, it shows that RFA gives better results in every problem than FA.

APA, Harvard, Vancouver, ISO, and other styles

28

Benabbou, Nawal, Cassandre Leroy, Thibaut Lust, and Patrice Perny. "Combining Preference Elicitation with Local Search and Greedy Search for Matroid Optimization." Proceedings of the AAAI Conference on Artificial Intelligence 35, no. 14 (May 18, 2021): 12233–40. http://dx.doi.org/10.1609/aaai.v35i14.17452.

Full text

Abstract:

We propose two incremental preference elicitation methods for interactive preference-based optimization on weighted matroid structures. More precisely, for linear objective (utility) functions, we propose an interactive greedy algorithm interleaving preference queries with the incremental construction of an independent set to obtain an optimal or near-optimal base of a matroid. We also propose an interactive local search algorithm based on sequences of possibly improving exchanges for the same problem. For both algorithms, we provide performance guarantees on the quality of the returned solutions and the number of queries. Our algorithms are tested on the uniform, graphical and scheduling matroids to solve three different problems (committee election, spanning tree, and scheduling problems) and evaluated in terms of computation times, number of queries, and empirical error.

APA, Harvard, Vancouver, ISO, and other styles

29

Shankar, Rajendran, Narayanan Ganesh, Robert Čep, Rama Chandran Narayanan, Subham Pal, and Kanak Kalita. "Hybridized Particle Swarm—Gravitational Search Algorithm for Process Optimization." Processes 10, no. 3 (March 21, 2022): 616. http://dx.doi.org/10.3390/pr10030616.

Full text

Abstract:

The optimization of industrial processes is a critical task for leveraging profitability and sustainability. To ensure the selection of optimum process parameter levels in any industrial process, numerous metaheuristic algorithms have been proposed so far. However, many algorithms are either computationally too expensive or become trapped in the pit of local optima. To counter these challenges, in this paper, a hybrid metaheuristic called PSO-GSA is employed that works by combining the iterative improvement capability of particle swarm optimization (PSO) and gravitational search algorithm (GSA). A binary PSO is also fused with GSA to develop a BPSO-GSA algorithm. Both the hybrid algorithms i.e., PSO-GSA and BPSO-GSA, are compared against traditional algorithms, such as tabu search (TS), genetic algorithm (GA), differential evolution (DE), GSA and PSO algorithms. Moreover, another popular hybrid algorithm DE-GA is also used for comparison. Since earlier works have already studied the performance of these algorithms on mathematical benchmark functions, in this paper, two real-world-applicable independent case studies on biodiesel production are considered. Based on the extensive comparisons, significantly better solutions are observed in the PSO-GSA algorithm as compared to the traditional algorithms. The outcomes of this work will be beneficial to similar studies that rely on polynomial models.

APA, Harvard, Vancouver, ISO, and other styles

30

Heras, Federico, Antonio Morgado, and Joao Marques-Silva. "Core-Guided Binary Search Algorithms for Maximum Satisfiability." Proceedings of the AAAI Conference on Artificial Intelligence 25, no. 1 (August 4, 2011): 36–41. http://dx.doi.org/10.1609/aaai.v25i1.7822.

Full text

Abstract:

Several MaxSAT algorithms based on iterative SAT solving have been proposed in recent years. These algorithms are in general the most efﬁcient for real-world applications. Existing data indicates that, among MaxSAT algorithms based on iterative SAT solving, the most efﬁcient ones are core-guided, i.e. algorithms which guide the search by iteratively computing unsatisﬁable subformulas (or cores). For weighted MaxSAT, core-guided algorithms exhibit a number of important drawbacks, including a possibly exponential number of iterations and the use of a large number of auxiliary variables. This paper develops two new algorithms for (weighted) MaxSAT that address these two drawbacks. The ﬁrst MaxSAT algorithm implements core-guided iterative SAT solving with binary search. The second algorithm extends the ﬁrst one by exploiting disjoint cores. The empirical evaluation shows that core-guided binary search is competitive with current MaxSAT solvers.

APA, Harvard, Vancouver, ISO, and other styles

31

Bunnag, Dhiranuch. "Combining Interval Branch and Bound and Stochastic Search." Abstract and Applied Analysis 2014 (2014): 1–15. http://dx.doi.org/10.1155/2014/861765.

Full text

Abstract:

This paper presents global optimization algorithms that incorporate the idea of an interval branch and bound and the stochastic search algorithms. Two algorithms for unconstrained problems are proposed, the hybrid interval simulated annealing and the combined interval branch and bound and genetic algorithm. The numerical experiment shows better results compared to Hansen’s algorithm and simulated annealing in terms of the storage, speed, and number of function evaluations. The convergence proof is described. Moreover, the idea of both algorithms suggests a structure for an integrated interval branch and bound and genetic algorithm for constrained problems in which the algorithm is described and tested. The aim is to capture one of the solutions with higher accuracy and lower cost. The results show better quality of the solutions with less number of function evaluations compared with the traditional GA.

APA, Harvard, Vancouver, ISO, and other styles

32

Sigurdson, Devon, and Vadim Bulitko. "Deep Learning for Real-Time Heuristic Search Algorithm Selection." Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment 13, no. 1 (June 25, 2021): 108–14. http://dx.doi.org/10.1609/aiide.v13i1.12927.

Full text

Abstract:

Real-time heuristic search algorithms are used for creating agents that rely on local information and move in a bounded amount of time making them an excellent candidate for video games as planning time can be controlled. Path finding on video game maps has become the de facto standard for evaluating real-time heuristic search algorithms. Over the years researchers have worked to identify areas where these algorithms perform poorly in an attempt to mitigate their weaknesses. Recent work illustrates the benefits of tailoring algorithms for a given problem as performance is heavily dependent on the search space. In order to determine which algorithm to select for solving the search problems on a map the developer would have to run all the algorithms in consideration to obtain the correct choice. Our work extends the previous algorithm selection approach to use a deep learning classifier to select the algorithm to use on new maps without having to evaluate the algorithms on the map. To do so we select a portfolio of algorithms and train a classifier to predict which portfolio member to use on a unseen new map. Our empirical results show that selecting algorithms dynamically can outperform the single best algorithm from the portfolio on new maps, as well provide the lower bound for potential improvements to motivate further work on this approach.

APA, Harvard, Vancouver, ISO, and other styles

33

Sakuta, Makoto, and Hiroyuki Iida. "AND/OR-TREE SEARCH ALGORITHMS TN SHOGI MATING SEARCH1." ICGA Journal 24, no. 4 (December 1, 2001): 231–35. http://dx.doi.org/10.3233/icg-2001-24405.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Syed Shahul Hameed, A., and Narendran Rajagopalan. "SPGD: Search Party Gradient Descent Algorithm, a Simple Gradient-Based Parallel Algorithm for Bound-Constrained Optimization." Mathematics 10, no. 5 (March 2, 2022): 800. http://dx.doi.org/10.3390/math10050800.

Full text

Abstract:

Nature-inspired metaheuristic algorithms remain a strong trend in optimization. Human-inspired optimization algorithms should be more intuitive and relatable. This paper proposes a novel optimization algorithm inspired by a human search party. We hypothesize the behavioral model of a search party searching for a treasure. Motivated by the search party’s behavior, we abstract the “Divide, Conquer, Assemble” (DCA) approach. The DCA approach allows us to parallelize the traditional gradient descent algorithm in a strikingly simple manner. Essentially, multiple gradient descent instances with different learning rates are run parallelly, periodically sharing information. We call it the search party gradient descent (SPGD) algorithm. Experiments performed on a diverse set of classical benchmark functions show that our algorithm is good at optimizing. We believe our algorithm’s apparent lack of complexity will equip researchers to solve problems efficiently. We compare the proposed algorithm with SciPy’s optimize library and it is found to be competent with it.

APA, Harvard, Vancouver, ISO, and other styles

35

Mahdad, Belkacem, and Kamel Srairi. "Interactive gravitational search algorithm and pattern search algorithms for practical dynamic economic dispatch." International Transactions on Electrical Energy Systems 25, no. 10 (July 9, 2014): 2289–309. http://dx.doi.org/10.1002/etep.1961.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

KAELO, P., and M. M. ALI. "NUMERICAL STUDIES OF SOME GENERALIZED CONTROLLED RANDOM SEARCH ALGORITHMS." Asia-Pacific Journal of Operational Research 29, no. 02 (April 2012): 1250016. http://dx.doi.org/10.1142/s0217595912500169.

Full text

Abstract:

This paper presents motivations and algorithmic details of some generalized controlled random search (CRS) algorithms for global optimization. It also carries out an extensive numerical study of the generalized CRS algorithms to demonstrate their superiorities over their original counterparts. The numerical study is carried out using a set of 50 test problems many of which are inspired by practical applications. Numerical experiments indicate that the generalized algorithms are considerably better than the previous versions. The algorithms are also compared with the DIRECT algorithm (Jones et al., 1993). The comparison shows that the generalized CRS algorithms are better than the DIRECT algorithm in high dimensional problems. Thus, they offer a reasonable alternative to many currently available stochastic algorithms, especially for problems requiring "direct search type" methods.

APA, Harvard, Vancouver, ISO, and other styles

37

Sharma, Divya, and Shikha Lohchab. "Search based Software Modularization Using Evolution Algorithm." NeuroQuantology 20, no. 5 (May 18, 2022): 822–31. http://dx.doi.org/10.14704/nq.2022.20.5.nq22240.

Full text

Abstract:

To comprehend a Software system, Software modularization strategies are used. The goal of modularization is to break down a software system into meaningful and intelligible sub-systems from its source-code (modules). Because software classification modularization is an NP-hard task, evolutionary methods produce better modularization quality rather than avaricious algorithms. All available transformative techniques for software modularization only take into account structural aspects reliant on programming language syntax. Because most computer languages lack a mechanism for extracting structural characteristics, they cannot be modularized. A novel heuristic is proposed in this work. with several objectives that accomplishes both in order to lead optimization algorithms towards a proper decomposition of software systems automatically, structural (e.g.; calling dependence and in-heritance dependency) and non- structural (e.g.; semantics in code comments and identifier names) aspects are used. It is analyzed using 3 optimization plans, viz; global-based-search, combining global and local search, and Estimation of Distribution (EoD) to upgrade it. According to outcomes on Mozilla Firefox, suggested optimization algorithm based on EoD and the newly developed MOF function exceed those so it use structural-based objective functions in finding more understandable modules, as well as guiding the optimization procedure. In the lack of a unique concept, structure, the original design can be identified by using the source code of the disturbed software. Effective software maintenance depends on the concept of software system. One of most powerful techniques in software clustering is the ability to divide enormous Software systems into workable subsystems with modules of identical characteristics, thereby reducing the complexity of the system. A metaheuristic optimization imperialist competitive system has emerged algorithm, genetic algorithm, and their combination is examined for software clustering in this paper. When it comes to value, of clustering, the number of epochs required for convergence, and the standard unconventionality found at the end of repeated application of these algorithms, it appears that recursive application is the most effective for achieving the best performance.

APA, Harvard, Vancouver, ISO, and other styles

38

Liu, Guole, Haipeng Peng, Lixiang Li, Yixian Yang, and Qun Luo. "Improved Degree Search Algorithms in Unstructured P2P Networks." Mathematical Problems in Engineering 2012 (2012): 1–18. http://dx.doi.org/10.1155/2012/923023.

Full text

Abstract:

Searching and retrieving the demanded correct information is one important problem in networks; especially, designing an efficient search algorithm is a key challenge in unstructured peer-to-peer (P2P) networks. Breadth-first search (BFS) and depth-first search (DFS) are the current two typical search methods. BFS-based algorithms show the perfect performance in the aspect of search success rate of network resources, while bringing the huge search messages. On the contrary, DFS-based algorithms reduce the search message quantity and also cause the dropping of search success ratio. To address the problem that only one of performances is excellent, we propose two memory function degree search algorithms: memory function maximum degree algorithm (MD) and memory function preference degree algorithm (PD). We study their performance including the search success rate and the search message quantity in different networks, which are scale-free networks, random graph networks, and small-world networks. Simulations show that the two performances are both excellent at the same time, and the performances are improved at least 10 times.

APA, Harvard, Vancouver, ISO, and other styles

39

Wang, Chao, Jie Ding, and Bin Hu. "Ranking Algorithms for Keyword Search over Relational Databases." Advanced Materials Research 605-607 (December 2012): 2291–96. http://dx.doi.org/10.4028/www.scientific.net/amr.605-607.2291.

Full text

Abstract:

Developing effective ranking algorithms for keyword search over relational databases is a hot study topic. Ranking algorithm largely determines the performance of a keyword search system. Good ranking algorithms not only provide user with the most relevant query results but also provide fast response time. A number of existing ranking algorithms were classified and compared. Several representational algorithms were summarized and analysed in detail. The principles, advantages and disadvantages of these algorithms were discussed. Finally, prospect for future work, especially the intelligent trends, in ranking were discussed.

APA, Harvard, Vancouver, ISO, and other styles

40

Dehghani, Mohammad, Zeinab Montazeri, Gaurav Dhiman, O. P. Malik, Ruben Morales-Menendez, Ricardo A. Ramirez-Mendoza, Ali Dehghani, Josep M. Guerrero, and Lizeth Parra-Arroyo. "A Spring Search Algorithm Applied to Engineering Optimization Problems." Applied Sciences 10, no. 18 (September 4, 2020): 6173. http://dx.doi.org/10.3390/app10186173.

Full text

Abstract:

At present, optimization algorithms are used extensively. One particular type of such algorithms includes random-based heuristic population optimization algorithms, which may be created by modeling scientific phenomena, like, for example, physical processes. The present article proposes a novel optimization algorithm based on Hooke’s law, called the spring search algorithm (SSA), which aims to solve single-objective constrained optimization problems. In the SSA, search agents are weights joined through springs, which, as Hooke’s law states, possess a force that corresponds to its length. The mathematics behind the algorithm are presented in the text. In order to test its functionality, it is executed on 38 established benchmark test functions and weighed against eight other optimization algorithms: a genetic algorithm (GA), a gravitational search algorithm (GSA), a grasshopper optimization algorithm (GOA), particle swarm optimization (PSO), teaching–learning-based optimization (TLBO), a grey wolf optimizer (GWO), a spotted hyena optimizer (SHO), as well as an emperor penguin optimizer (EPO). To test the SSA’s usability, it is employed on five engineering optimization problems. The SSA delivered better fitting results than the other algorithms in unimodal objective function, multimodal objective functions, CEC 2015, in addition to the optimization problems in engineering.

APA, Harvard, Vancouver, ISO, and other styles

41

Rachmut, Ben, Roie Zivan, and William Yeoh. "Communication-Aware Local Search for Distributed Constraint Optimization." Journal of Artificial Intelligence Research 75 (October 28, 2022): 637–75. http://dx.doi.org/10.1613/jair.1.13826.

Full text

Abstract:

Most studies investigating models and algorithms for distributed constraint optimization problems (DCOPs) assume that messages arrive instantaneously and are never lost. Specifically, distributed local search DCOP algorithms, have been designed as synchronous algorithms (i.e., they perform in synchronous iterations in which each agent exchanges messages with all its neighbors), despite running in asynchronous environments. This is true also for an anytime mechanism that reports the best solution explored during the run of synchronous distributed local search algorithms. Thus, when the assumption of perfect communication is relaxed, the properties that were established for the state-of-the-art local search algorithms and the anytime mechanism may not necessarily apply. In this work, we address this limitation by: (1) Proposing a Communication-Aware DCOP model (CA-DCOP) that can represent scenarios with different communication disturbances; (2) Investigating the performance of existing local search DCOP algorithms, specifically Distributed Stochastic Algorithm (DSA) and Maximum Gain Messages (MGM), in the presence of message latency and message loss; (3) Proposing a latency-aware monotonic distributed local search DCOP algorithm; and (4) Proposing an asynchronous anytime framework for reporting the best solution explored by non-monotonic asynchronous local search DCOP algorithms. Our empirical results demonstrate that imperfect communication has a positive effect on distributed local search algorithms due to increased exploration. Furthermore, the asynchronous anytime framework we proposed allows one to benefit from algorithms with inherent explorative heuristics.

APA, Harvard, Vancouver, ISO, and other styles

42

Halim, Felix, Panagiotis Karras, and Roland Yap. "Local Search in Histogram Construction." Proceedings of the AAAI Conference on Artificial Intelligence 24, no. 1 (July 5, 2010): 1680–85. http://dx.doi.org/10.1609/aaai.v24i1.7713.

Full text

Abstract:

The problem of dividing a sequence of values into segments occurs in database systems, information retrieval, and knowledge management. The challenge is to select a finite number of boundaries for the segments so as to optimize an objective error function defined over those segments. Although this optimization problem can be solved in polynomial time, the algorithm which achieves the minimum error does not scale well, hence it is not practical for applications with massive data sets. There is considerable research with numerous approximation and heuristic algorithms. Still, none of those approaches has resolved the quality-efficiency tradeoff in a satisfactory manner. In (Halim, Karras, and Yap 2009), we obtain near linear time algorithms which achieve both the desired scalability and near-optimal quality, thus dominating earlier approaches. In this paper, we show how two ideas from artificial intelligence, an efficient local search and recombination of multiple solutions reminiscent of genetic algorithms, are combined in a novel way to obtain state of the art histogram construction algorithms.

APA, Harvard, Vancouver, ISO, and other styles

43

Hernández, Carlos, Jorge A. Baier, and Roberto Asín. "Time-Bounded Best-First Search for Reversible and Non-reversible Search Graphs." Journal of Artificial Intelligence Research 56 (August 6, 2016): 547–71. http://dx.doi.org/10.1613/jair.5073.

Full text

Abstract:

Time-Bounded A* is a real-time, single-agent, deterministic search algorithm that expands states of a graph in the same order as A* does, but that unlike A* interleaves search and action execution. Known to outperform state-of-the-art real-time search algorithms based on Korf's Learning Real-Time A* (LRTA*) in some benchmarks, it has not been studied in detail and is sometimes not considered as a ``true'' real-time search algorithm since it fails in non-reversible problems even it the goal is still reachable from the current state. In this paper we propose and study Time-Bounded Best-First Search (TB(BFS)) a straightforward generalization of the time-bounded approach to any best-first search algorithm. Furthermore, we propose Restarting Time-Bounded Weighted A* (TB_R(WA*)), an algorithm that deals more adequately with non-reversible search graphs, eliminating ``backtracking moves'' and incorporating search restarts and heuristic learning. In non-reversible problems we prove that TB(BFS) terminates and we deduce cost bounds for the solutions returned by Time-Bounded Weighted A* (TB(WA*)), an instance of TB(BFS). Furthermore, we prove TB_R(WA*), under reasonable conditions, terminates. We evaluate TB(WA) in both grid pathfinding and the 15-puzzle. In addition, we evaluate TB_R(WA*) on the racetrack problem. We compare our algorithms to LSS-LRTWA*, a variant of LRTA* that can exploit lookahead search and a weighted heuristic. A general observation is that the performance of both TB(WA*) and TB_R(WA*) improves as the weight parameter is increased. In addition, our time-bounded algorithms almost always outperform LSS-LRTWA* by a significant margin.

APA, Harvard, Vancouver, ISO, and other styles

44

Bond, David, Niels Widger, Wheeler Ruml, and Xiaoxun Sun. "Real-Time Search in Dynamic Worlds." Proceedings of the International Symposium on Combinatorial Search 1, no. 1 (August 25, 2010): 16–22. http://dx.doi.org/10.1609/socs.v1i1.18174.

Full text

Abstract:

For problems such as pathfinding in video games and robotics, a search algorithm must be real-time (return the next move within a fixed time bound) and dynamic (accommodate edge costs that can increase and decrease before the goal is reached). Existing real-time search algorithms, such as LSS-LRTA*, can handle edge cost increases but do not handle edge cost decreases. Existing dynamic search algorithms, such as D* Lite, are not real-time. We show how these two families of algorithms can be combined using bidirectional search, producing Real-Time D* (RTD*), the first real-time search algorithm designed for dynamic worlds. Our empirical evaluation shows that, for dynamic grid pathfinding, RTD* results in significantly shorter trajectories than either LSS-LRTA* or naive real-time adaptations of D* Lite because of its ability to opportunistically exploit shortcuts.

APA, Harvard, Vancouver, ISO, and other styles

45

Grebner, Christoph, Johannes Becker, Svetlana Stepanenko, and Bernd Engels. "Efficiency of tabu-search-based conformational search algorithms." Journal of Computational Chemistry 32, no. 10 (May 3, 2011): 2245–53. http://dx.doi.org/10.1002/jcc.21807.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

Zedadra, Ouarda, Antonio Guerrieri, and Hamid Seridi. "LFA: A Lévy Walk and Firefly-Based Search Algorithm: Application to Multi-Target Search and Multi-Robot Foraging." Big Data and Cognitive Computing 6, no. 1 (February 21, 2022): 22. http://dx.doi.org/10.3390/bdcc6010022.

Full text

Abstract:

In the literature, several exploration algorithms have been proposed so far. Among these, Lévy walk is commonly used since it is proved to be more efficient than the simple random-walk exploration. It is beneficial when targets are sparsely distributed in the search space. However, due to its super-diffusive behavior, some tuning is needed to improve its performance, specifically when targets are clustered. Firefly algorithm is a swarm intelligence-based algorithm useful for intensive search, but its exploration rate is very limited. An efficient and reliable search could be attained by combining the two algorithms since the first one allows exploration space, and the second one encourages its exploitation. In this paper, we propose a swarm intelligence-based search algorithm called Lévy walk and Firefly-based Algorithm (LFA), which is a hybridization of the two aforementioned algorithms. The algorithm is applied to Multi-Target Search and Multi-Robot Foraging. Numerical experiments to test the performances are conducted on the robotic simulator ARGoS. A comparison with the original firefly algorithm proves the goodness of our contribution.

APA, Harvard, Vancouver, ISO, and other styles

47

Al-Nuaimi, Adawiya. "Local Search Algorithms for Multiobjective Scheduling Problem." Journal of Al-Rafidain University College For Sciences ( Print ISSN: 1681-6870 ,Online ISSN: 2790-2293 ), no. 2 (October 13, 2021): 201–17. http://dx.doi.org/10.55562/jrucs.v36i2.255.

Full text

Abstract:

This paper presents local search algorithms for finding approximation solutions of the multiobjective scheduling problem within the single machine context, where the problem is the sum of the three objectives total completion time, maximum tardiness and maximum late work. Late work criterion estimates the quality of a schedule based on durations of late parts of jobs. Local search algorithms descent method (DM), simulated annealing (SA) and genetic algorithm (GA) are implemented. Based on results of computational experiments, conclusions are formulated on the efficiency of the local search algorithms.

APA, Harvard, Vancouver, ISO, and other styles

48

El-Mihoub, Tarek, Christoph Tholen, and Lars Nolle. "Towards Reducing the Impact of Localisation Errors on the Behaviour of a Swarm of Autonomous Underwater Vehicles." MENDEL 26, no. 2 (December 21, 2020): 1–8. http://dx.doi.org/10.13164/mendel.2020.2.001.

Full text

Abstract:

Localisation errors have a great impact on Autonomous Underwater Vehicles (AUVs) as search agents. Different approaches for solving the localisation problem can be used and combined together for greater accuracy in estimating AUVs’ locations. The effect of localisation errors on locating a target can be lightened by designing a search algorithm that avoids extensive use of exact lo-cation information. In this paper, two cooperative search algorithms are proposed and evaluated. In these algorithms, a high-level mechanism is employed for building a global view of the search space using minimum possible search information. These algorithms rely on low-level search algorithms with exploring roles. Particle Swarm Optimisation (PSO) and all-to-one Self-Organising Migrating Algorithm (SOMA) are selected as high-level mechanisms. The conducted experiments demonstrate that both algorithms show a robust behaviour within a range of localisation errors.

APA, Harvard, Vancouver, ISO, and other styles

49

Mishra, Abhishek, and Pramod Kumar Mishra. "A Randomized Scheduling Algorithm for Multiprocessor Environments Using Local Search." Parallel Processing Letters 26, no. 01 (March 2016): 1650002. http://dx.doi.org/10.1142/s012962641650002x.

Full text

Abstract:

The LOCAL(A, B) randomized task scheduling algorithm is proposed for fully connected multiprocessors. It combines two given task scheduling algorithms (A, and B) using local neighborhood search to give a hybrid of the two given algorithms. Objective is to show that such type of hybridization can give much better performance results in terms of parallel execution times. Two task scheduling algorithms are selected: DSC (Dominant Sequence Clustering as algorithm A), and CPPS (Cluster Pair Priority Scheduling as algorithm B) and a hybrid is created (the LOCAL(DSC, CPPS) or simply the LOCAL task scheduling algorithm). The LOCAL task scheduling algorithm has time complexity O(|V||E|(|V |+|E|)), where V is the set of vertices, and E is the set of edges in the task graph. The LOCAL task scheduling algorithm is compared with six other algorithms: CPPS, DCCL (Dynamic Computation Communication Load), DSC, EZ (Edge Zeroing), LC (Linear Clustering), and RDCC (Randomized Dynamic Computation Communication). Performance evaluation of the LOCAL task scheduling algorithm shows that it gives up to 80.47 % improvement of NSL (Normalized Schedule Length) over other algorithms.

APA, Harvard, Vancouver, ISO, and other styles

50

Barbulescu, L., A. E. Howe, L. D. Whitley, and M. Roberts. "Understanding Algorithm Performance on an Oversubscribed Scheduling Application." Journal of Artificial Intelligence Research 27 (December 28, 2006): 577–615. http://dx.doi.org/10.1613/jair.2038.

Full text

Abstract:

The best performing algorithms for a particular oversubscribed scheduling application, Air Force Satellite Control Network (AFSCN) scheduling, appear to have little in common. Yet, through careful experimentation and modeling of performance in real problem instances, we can relate characteristics of the best algorithms to characteristics of the application. In particular, we find that plateaus dominate the search spaces (thus favoring algorithms that make larger changes to solutions) and that some randomization in exploration is critical to good performance (due to the lack of gradient information on the plateaus). Based on our explanations of algorithm performance, we develop a new algorithm that combines characteristics of the best performers; the new algorithm's performance is better than the previous best. We show how hypothesis driven experimentation and search modeling can both explain algorithm performance and motivate the design of a new algorithm.

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Search algorithms'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles