Journal articles: 'Greedy search algorithm'

1

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

2

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

3

Dor, Avner. "The Greedy Search Algorithm on Binary Vectors." Journal of Algorithms 27, no. 1 (April 1998): 42–60. http://dx.doi.org/10.1006/jagm.1997.0893.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Prihozhy, A. A. "Exact and greedy algorithms of allocating experts to maximum set of programmer teams." «System analysis and applied information science», no. 1 (June 8, 2022): 40–46. http://dx.doi.org/10.21122/2309-4923-2022-1-40-46.

Full text

Abstract:

The allocation of experts to programmer teams, which meet constraints on professional competences related to programming technologies, languages and tools an IT project specifies is a hard combinatorial problem. This paper solves the problem of forming the maximum number of teams whose experts meet all the constraints within each team. It develops and compares two algorithms: a heuristic greedy and exact optimal. The greedy algorithm iteratively solves the set cover problem on a matrix of expert competences until can create the next workable team of remaining experts. The paper proves that the allocation greedy algorithm is not accurate even if the set cover algorithm is exact. We call the allocation algorithm as double greedy if the set cover algorithm is greedy. The exact algorithm we propose finds optimal solution in three steps: generating a set of all non-redundant teams, producing a graph of team’s independency, and searching for a maximum clique in the graph. The algorithm of generating the non-redundant teams traverses a search tree constructed in such a way as to guarantee the creation of all non-redundant teams and absorbing all redundant teams. The edges of the non-redundant team independency graph connect teams that have no common expert. The maximum clique search algorithm we propose accounts for the problem and graph features. Experimental results show that the exact algorithm is a reference one, and the double-greedy algorithm is very fast and can yield suboptimal solutions for large-size allocation problems.

APA, Harvard, Vancouver, ISO, and other styles

5

Heusner, Manuel, Thomas Keller, and Malte Helmert. "Understanding the Search Behaviour of Greedy Best-First Search." Proceedings of the International Symposium on Combinatorial Search 8, no. 1 (September 1, 2021): 47–55. http://dx.doi.org/10.1609/socs.v8i1.18425.

Full text

Abstract:

A classical result in optimal search shows that A* with an admissible and consistent heuristic expands every state whose f-value is below the optimal solution cost and no state whose f-value is above the optimal solution cost. For satisficing search algorithms, a similarly clear understanding is currently lacking. We examine the search behaviour of greedy best-first search (gbfs) in order to make progress towards such an understanding. We introduce the concept of high-water mark benches, which separate the search space into areas that are searched by a gbfs algorithm in sequence. High-water mark benches allow us to exactly determine the set of states that are not expanded under any gbfs tie-breaking strategy. For the remaining states, we show that some are expanded by all gbfs searches, while others are expanded only if certain conditions are met.

APA, Harvard, Vancouver, ISO, and other styles

6

Piacentini, Chiara, Sara Bernardini, and J. Christopher Beck. "Autonomous Target Search with Multiple Coordinated UAVs." Journal of Artificial Intelligence Research 65 (August 8, 2019): 519–68. http://dx.doi.org/10.1613/jair.1.11635.

Full text

Abstract:

Search and tracking is the problem of locating a moving target and following it to its destination. In this work, we consider a scenario in which the target moves across a large geographical area by following a road network and the search is performed by a team of unmanned aerial vehicles (UAVs). We formulate search and tracking as a combinatorial optimization problem and prove that the objective function is submodular. We exploit this property to devise a greedy algorithm. Although this algorithm does not offer strong theoretical guarantees because of the presence of temporal constraints that limit the feasibility of the solutions, it presents remarkably good performance, especially when several UAVs are available for the mission. As the greedy algorithm suffers when resources are scarce, we investigate two alternative optimization techniques: Constraint Programming (CP) and AI planning. Both approaches struggle to cope with large problems, and so we strengthen them by leveraging the greedy algorithm. We use the greedy solution to warm start the CP model and to devise a domain-dependent heuristic for planning. Our extensive experimental evaluation studies the scalability of the different techniques and identifies the conditions under which one approach becomes preferable to the others.

APA, Harvard, Vancouver, ISO, and other styles

7

Kazakovtsev, Lev, Dmitry Stashkov, Mikhail Gudyma, and Vladimir Kazakovtsev. "Algorithms with greedy heuristic procedures for mixture probability distribution separation." Yugoslav Journal of Operations Research 29, no. 1 (2019): 51–67. http://dx.doi.org/10.2298/yjor171107030k.

Full text

Abstract:

For clustering problems based on the model of mixture probability distribution separation, we propose new Variable Neighbourhood Search algorithms (VNS) and evolutionary genetic algorithms (GA) with greedy agglomerative heuristic procedures and compare them with known algorithms. New genetic algorithms implement a global search strategy with the use of a special crossover operator based on greedy agglomerative heuristic procedures in combination with the EM algorithm (Expectation Maximization). In our new VNS algorithms, this combination is used for forming randomized neighbourhoods to search for better solutions. The results of computational experiments made on classical data sets and the testings of production batches of semiconductor devices shipped for the space industry demonstrate that new algorithms allow us to obtain better results, higher values of the log likelihood objective function, in comparison with the EM algorithm and its modifications.

APA, Harvard, Vancouver, ISO, and other styles

8

Xiao, Zhuolei, Yerong Zhang, Kaixuan Zhang, Dongxu Zhao, and Guan Gui. "GARLM: Greedy Autocorrelation Retrieval Levenberg–Marquardt Algorithm for Improving Sparse Phase Retrieval." Applied Sciences 8, no. 10 (October 1, 2018): 1797. http://dx.doi.org/10.3390/app8101797.

Full text

Abstract:

The goal of phase retrieval is to recover an unknown signal from the random measurements consisting of the magnitude of its Fourier transform. Due to the loss of the phase information, phase retrieval is considered as an ill-posed problem. Conventional greedy algorithms, e.g., greedy spare phase retrieval (GESPAR), were developed to solve this problem by using prior knowledge of the unknown signal. However, due to the defect of the Gauss–Newton method in the local convergence problem, especially when the residual is large, it is very difficult to use this method in GESPAR to efficiently solve the non-convex optimization problem. In order to improve the performance of the greedy algorithm, we propose an improved phase retrieval algorithm, which is called the greedy autocorrelation retrieval Levenberg–Marquardt (GARLM) algorithm. Specifically, the proposed GARLM algorithm is a local search iterative algorithm to recover the sparse signal from its Fourier transform magnitude. The proposed algorithm is preferred to existing greedy methods of phase retrieval, since at each iteration the problem of minimizing the objective function over a given support is solved by using the improved Levenberg–Marquardt (ILM) method and matrix transform. A local search procedure such as the 2-opt method is then invoked to get the optimal estimation. Simulation results are given to show that the proposed algorithm performs better than the conventional GESPAR algorithm.

APA, Harvard, Vancouver, ISO, and other styles

9

Oktaviandi, Rizky Berlia, M. Sadid Tafsirul Hadi, Alanfansyah Ghozy Santoso, and Nova El Maidah. "Perbandingan Algoritma Genetika dengan Algoritma Greedy Untuk Pencarian Rute Terpendek." INFORMAL: Informatics Journal 3, no. 1 (February 25, 2019): 6. http://dx.doi.org/10.19184/isj.v3i1.9847.

Full text

Abstract:

In everyday life we often travel from place to place. So that we need to consider the time and cost efficient. Therefore, accuracy is needed to determine the shortest path as a consideration in decision to show the path to be taken. The results obtained also require speed and accuracy with the help of a computer. Using or functioning a computer there must be a distributed program in it. The programs contained in the computer vary widely and each program must use an algorithm. Algorithm is a collection of commands to solve a problem gradually from start to finish. There are various algorithms that can be used to find the shortest route such as Breadth First Search algorithm, Depth First Search, A *, Hill Climbing and others. For that required comparison algorithm which is able to find the shortest route accurately and efficiently. In this journal, the algorithm to be compared is the genetic algorithm and greedy algorithm to find the shortest route on a map. Some aspects to be compared are aspects of the accuracy, speed, and complexity of genetic algorithms and greedy algorithms for the shortest route search.

APA, Harvard, Vancouver, ISO, and other styles

10

Wang, Chao, Deguang Wang, and Chun Jin. "A quick Heuristic and a general search algorithm for traveling salesman problem." E3S Web of Conferences 360 (2022): 01097. http://dx.doi.org/10.1051/e3sconf/202236001097.

Full text

Abstract:

This paper puts forward a constructive heuristic algorithm called the method of inserting the minimum neighbor edge from outside to the center (IMNEFOTC) that can be applied to solve large-scale and ultra-large-scale travelling salesman problems. Through it and the randomized greedy heuristic algorithm (RGH) which greedy heuristic algorithm is modified, a general meta-heuristic search algorithm framework is built. The general search algorithm (GSA) is based on a set of initial solutions, and continuous 2-opt operations are performed, so as to search for solutions in better quality. The data from the experiment reveals that the performance of IMNEFOTC is better than the traditional greedy algorithm, and the GSA can obtain a pretty satisfactory solution in a reasonable range of time.

APA, Harvard, Vancouver, ISO, and other styles

11

Feldman, A., G. Provan, and A. Van Gemund. "Approximate Model-Based Diagnosis Using Greedy Stochastic Search." Journal of Artificial Intelligence Research 38 (July 27, 2010): 371–413. http://dx.doi.org/10.1613/jair.3025.

Full text

Abstract:

We propose a StochAstic Fault diagnosis AlgoRIthm, called SAFARI, which trades off guarantees of computing minimal diagnoses for computational efficiency. We empirically demonstrate, using the 74XXX and ISCAS-85 suites of benchmark combinatorial circuits, that SAFARI achieves several orders-of-magnitude speedup over two well-known deterministic algorithms, CDA* and HA*, for multiple-fault diagnoses; further, SAFARI can compute a range of multiple-fault diagnoses that CDA* and HA* cannot. We also prove that SAFARI is optimal for a range of propositional fault models, such as the widely-used weak-fault models (models with ignorance of abnormal behavior). We discuss the optimality of SAFARI in a class of strong-fault circuit models with stuck-at failure modes. By modeling the algorithm itself as a Markov chain, we provide exact bounds on the minimality of the diagnosis computed. SAFARI also displays strong anytime behavior, and will return a diagnosis after any non-trivial inference time.

APA, Harvard, Vancouver, ISO, and other styles

12

Tian, Heng, Fuhai Duan, Yong Sang, and Liang Fan. "Novel algorithms for sequential fault diagnosis based on greedy method." Proceedings of the Institution of Mechanical Engineers, Part O: Journal of Risk and Reliability 234, no. 6 (May 2, 2020): 779–92. http://dx.doi.org/10.1177/1748006x20914498.

Full text

Abstract:

Test sequencing for binary systems is a nondeterministic polynomial-complete problem, where greedy algorithms have been proposed to find the solution. The traditional greedy algorithms only extract a single kind of information from the D-matrix to search the optimal test sequence, so their application scope is limited. In this study, two novel greedy algorithms that combine the weight index for fault detection with the information entropy are introduced for this problem, which are defined as the Mix1 algorithm and the Mix2 algorithm. First, the application scope for the traditional greedy algorithms is demonstrated in detail by stochastic simulation experiments. Second, two new heuristic formulas are presented, and their scale factors are determined. Third, an example is used to show how the two new algorithms work, and four real-world D-matrices are employed to validate their universality and stability. Finally, the application scope of the Mix1 and Mix2 algorithms is determined based on stochastic simulation experiments, and the two greedy algorithms are also used to improve a multistep look-ahead heuristic algorithm. The Mix1 and Mix2 algorithms can obtain good results in a reasonable time and have a wide application scope, which also can be used to improve the multistep look-ahead heuristic algorithm.

APA, Harvard, Vancouver, ISO, and other styles

13

Khanna, Munish, Naresh Chauhan, and Dilip Kumar Sharma. "Search for Prioritized Test Cases during Web Application Testing." International Journal of Applied Metaheuristic Computing 10, no. 2 (April 2019): 1–26. http://dx.doi.org/10.4018/ijamc.2019040101.

Full text

Abstract:

Regression testing of evolving software is a critical constituent of the software development process. Due to resources constraints, test case prioritization is one of the strategies followed in regression testing during which a test case that satisfies predefined objectives the most, as the tester perceives, would be executed the earliest. In this study, all the experiments were performed on three web applications consisting of 65 to 100 pages with lines of code ranging from 5000 to 7000. Various state-of-the-art approaches such as, heuristic approaches, Greedy approaches, and meta heuristic approaches were applied so as to identify the prioritized test sequence which maximizes the value of average percentage of fault detection. Performance of these algorithms was compared using different parameters and it was concluded that the Artificial Bee Colony algorithm performs better than all. Two novel greedy algorithms are also proposed in the study, of which the goal is to smartly manage the state of a tie, where a tie exhibits the condition that all the test cases participating in the tie are of equal significance in achieving the objective. It has also been validated that the performance of these novel proposed algorithm(s) is better than that of traditionally followed greedy approach, most of the time.

APA, Harvard, Vancouver, ISO, and other styles

14

Si, Wei-Jian, Qiang Liu, and Zhi-An Deng. "Adaptive Reconstruction Algorithm Based on Compressed Sensing Broadband Receiver." Wireless Communications and Mobile Computing 2021 (January 15, 2021): 1–12. http://dx.doi.org/10.1155/2021/6673235.

Full text

Abstract:

Existing greedy reconstruction algorithms require signal sparsity, and the remaining sparsity adaptive algorithms can be reconstructed but cannot achieve accurate sparsity estimation. To address this problem, a blind sparsity reconstruction algorithm is proposed in this paper, which is applied to compressed sensing radar receiver system. The proposed algorithm can realize the estimation of signal sparsity and channel position estimation, which mainly consists of two parts. The first part is to use fast search based on dichotomy search, which is based on the high probability reconstruction of greedy algorithm, and uses dichotomy search to cover the number of sparsity. The second part is the signal matching and tracking algorithm, which is mainly used to judge the signal position and reconstruct the signal. Combine the two parts together to realize the blind estimation of the sparsity and the accurate estimation of the number of signals when the number of signals is unknown. The experimental analyses are carried out to evaluate the performance of the reconstruction probability, the accuracy of sparsity estimation, the running time of the algorithm, and the signal-to-noise ratio.

APA, Harvard, Vancouver, ISO, and other styles

15

Zhang, Yongfei, Jun Wu, Liming Zhang, Peng Zhao, Junping Zhou, and Minghao Yin. "An Efficient Heuristic Algorithm for Solving Connected Vertex Cover Problem." Mathematical Problems in Engineering 2018 (September 6, 2018): 1–10. http://dx.doi.org/10.1155/2018/3935804.

Full text

Abstract:

The connected vertex cover (CVC) problem, which has many important applications, is a variant of the vertex cover problem, such as wireless network design, routing, and wavelength assignment problem. A good algorithm for the problem can help us improve engineering efficiency, cost savings, and resources consumption in industrial applications. In this work, we present an efficient algorithm GRASP-CVC (Greedy Randomized Adaptive Search Procedure for Connected Vertex Cover) for CVC in general graphs. The algorithm has two main phases, i.e., construction phase and local search phase. In the construction phase, to construct a high quality feasible initial solution, we design a greedy function and a restricted candidate list. In the local search phase, the configuration checking strategy is adopted to decrease the cycling problem. The experimental results demonstrate that GRASP-CVC is better than other comparison algorithms in terms of effectivity and efficiency.

APA, Harvard, Vancouver, ISO, and other styles

16

Xu, Yuehua, Alan Fern, and Sungwook Yoon. "Iterative Learning of Weighted Rule Sets for Greedy Search." Proceedings of the International Conference on Automated Planning and Scheduling 20 (May 25, 2021): 201–8. http://dx.doi.org/10.1609/icaps.v20i1.13416.

Full text

Abstract:

Greedy search is commonly used in an attempt to generate solutions quickly at the expense of completeness and optimality. In this work, we consider learning sets of weighted action-selection rules for guiding greedy search with application to automated planning. We make two primary contributions over prior work on learning for greedy search. First, we introduce weighted sets of action-selection rules as a new form of control knowledge for greedy search. Prior work has shown the utility of action-selection rules for greedy search, but has treated the rules as hard constraints, resulting in brittleness. Our weighted rule sets allow multiple rules to vote, helping to improve robustness to noisy rules. Second, we give a new iterative learning algorithm for learning weighted rule sets based on RankBoost, an efficient boosting algorithm for ranking. Each iteration considers the actual performance of the current rule set and directs learning based on the observed search errors. This is in contrast to most prior approaches, which learn control knowledge independently of the search process. Our empirical results have shown significant promise for this approach in a number of domains.

APA, Harvard, Vancouver, ISO, and other styles

17

Aldous, David. "Greedy Search on the Binary Tree with Random Edge-Weights." Combinatorics, Probability and Computing 1, no. 4 (December 1992): 281–93. http://dx.doi.org/10.1017/s096354830000033x.

Full text

Abstract:

There is a simple greedy algorithm for seeking large values of a function f defined on the vertices of the binary tree. Modeling f as a random function whose increments along edges are i.i.d., we show that (under a natural assumption) the values found by the greedy algorithm grow linearly in time, with rate specified in terms of a fixed-point identity for distributions.

APA, Harvard, Vancouver, ISO, and other styles

18

Lu, Ni Y., Kun Zhang, and Changhe Yuan. "Improving Causal Discovery By Optimal Bayesian Network Learning." Proceedings of the AAAI Conference on Artificial Intelligence 35, no. 10 (May 18, 2021): 8741–48. http://dx.doi.org/10.1609/aaai.v35i10.17059.

Full text

Abstract:

Many widely-used causal discovery methods such as Greedy Equivalent Search (GES), although with asymptotic correctness guarantees, have been reported to produce sub-optimal solutions on finite data, or when the causal faithfulness condition is violated. The constraint-based procedure with Boolean satisfiability (SAT) solver, and the recently proposed Sparsest Permutation (SP) algorithm have shown superb performance, but currently they do not scale well. In this work, we demonstrate that optimal score-based exhaustive search is remarkably useful for causal discovery: it requires weaker conditions to guarantee asymptotic correctness, and outperforms well-known methods including PC, GES, GSP, and NOTEARS. In order to achieve scalability, we also develop an approximation algorithm for larger systems based on the A* method, which scales up to 60+ variables and obtains better results than existing greedy algorithms such as GES, MMHC, and GSP. Our results illustrate the risk of assuming the faithfulness assumption, the advantages of exhaustive search methods, and the limitations of greedy search methods, and shed light on the computational challenges and techniques in scaling up to larger networks and handling unfaithful data.

APA, Harvard, Vancouver, ISO, and other styles

19

Flynn, Deanna, P. Michael Furlong, and Brian Coltin. "Search Tree Pruning for Progressive Neural Architecture Search (Student Abstract)." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 10 (April 3, 2020): 13783–84. http://dx.doi.org/10.1609/aaai.v34i10.7163.

Full text

Abstract:

Our neural architecture search algorithm progressively searches a tree of neural network architectures. Child nodes are created by inserting new layers determined by a transition graph into a parent network up to a maximum depth and pruned when performance is worse than its parent. This increases efficiency but makes the algorithm greedy. Simpler networks are successfully found before more complex ones that can achieve benchmark performance similar to other top-performing networks.

APA, Harvard, Vancouver, ISO, and other styles

20

Mandal, Ranjit Kr, Pinaki Mukherjee, and Mousumi Maitra. "Solving Travelling Salesman Problem using Artificial Immune System Optimization (AISO)." Journal of Scientific Research 66, no. 04 (2022): 114–20. http://dx.doi.org/10.37398/jsr.2022.660416.

Full text

Abstract:

Travelling Salesman Problem (TSP) is a typical NP complete combinatorial optimization problem with various applications. In this paper, a nature inspired meta-heuristic optimization algorithm named as Artificial Immune System Optimization (AISO) algorithm is proposed for solving TSP. There are other approaches for solving this problem, namely Greedy Method, Brunch and Bound (B&B), and Dynamic Programming (DP) but they are not very efficient. The time complexity of Greedy approach is O (n2). However, the Greedy method doesn't always converge to an optimum solution whereas the B&B increases search space exponentially and DP finds out optimal solution in O (n22 n) time. The population based meta-heuristic optimization algorithms such as Artificial Immune System Optimization (AISO) and Genetic Algorithm (GA) provide a way to find solution of the TSP in linear time complexity. The proposed algorithm finds out the best cell (optimum solution) using a Survivor Selection (SS) operator which reduces the search space to ensure that effective information is not lost. Dataset, results and convergence graphs are presented and accuracy of the analysis is briefly discussed.

APA, Harvard, Vancouver, ISO, and other styles

21

Naderi, B., Shadi Rahmani, and Shabnam Rahmani. "A Multiobjective Iterated Greedy Algorithm for Truck Scheduling in Cross-Dock Problems." Journal of Industrial Engineering 2014 (May 8, 2014): 1–12. http://dx.doi.org/10.1155/2014/128542.

Full text

Abstract:

The cross-docking system is a new distribution strategy which can reduce inventories, lead times, and improve responding time to customers. This paper considers biobjective problem of truck scheduling in cross-docking systems with temporary storage. The objectives are minimizing both makespan and total tardiness. For this problem, it proposes a multiobjective iterated greedy algorithm employing advance features such as modified crowding selection, restart phase, and local search. To evaluate the proposed algorithm for performance, it is compared with two available algorithms, subpopulation particle swarm optimization-II and strength Pareto evolutionary algorithm-II. The comparison shows that the proposed multiobjective iterated greedy algorithm shows high performance and outperforms the other two algorithms.

APA, Harvard, Vancouver, ISO, and other styles

22

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.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

23

Moraes, Rubens, Julian Mariño, and Levi Lelis. "Nested-Greedy Search for Adversarial Real-Time Games." Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment 14, no. 1 (September 25, 2018): 67–73. http://dx.doi.org/10.1609/aiide.v14i1.13017.

Full text

Abstract:

Churchill and Buro (2013) launched a line of research through Portfolio Greedy Search (PGS), an algorithm for adversarial real-time planning that uses scripts to simplify the problem's action space. In this paper we present a problem in PGS's search scheme that has hitherto been overlooked. Namely, even under the strong assumption that PGS is able to evaluate all actions available to the player, PGS might fail to return the best action. We then describe an idealized algorithm that is guaranteed to return the best action and present an approximation of such algorithm, which we call Nested-Greedy Search (NGS). Empirical results on MicroRTS show that NGS is able to outperform PGS as well as state-of-the-art methods in matches played in small to medium-sized maps.

APA, Harvard, Vancouver, ISO, and other styles

24

Seeja, K. R. "HybridHAM: A Novel Hybrid Heuristic for Finding Hamiltonian Cycle." Journal of Optimization 2018 (October 16, 2018): 1–10. http://dx.doi.org/10.1155/2018/9328103.

Full text

Abstract:

Hamiltonian Cycle Problem is one of the most explored combinatorial problems. Being an NP-complete problem, heuristic approaches are found to be more powerful than exponential time exact algorithms. This paper presents an efficient hybrid heuristic that sits in between the complex reliable approaches and simple faster approaches. The proposed algorithm is a combination of greedy, rotational transformation and unreachable vertex heuristics that works in three phases. In the first phase, an initial path is created by using greedy depth first search. This initial path is then extended to a Hamiltonian path in second phase by using rotational transformation and greedy depth first search. Third phase converts the Hamiltonian path into a Hamiltonian cycle by using rotational transformation. The proposed approach could find Hamiltonian cycles from a set of hard graphs collected from the literature, all the Hamiltonian instances (1000 to 5000 vertices) given in TSPLIB, and some instances of FHCP Challenge Set. Moreover, the algorithm has O(n3) worst case time complexity. The performance of the algorithm has been compared with the state-of-the-art algorithms and it was found that HybridHAM outperforms others in terms of running time.

APA, Harvard, Vancouver, ISO, and other styles

25

Soper, Daniel S. "Greed Is Good: Rapid Hyperparameter Optimization and Model Selection Using Greedy k-Fold Cross Validation." Electronics 10, no. 16 (August 16, 2021): 1973. http://dx.doi.org/10.3390/electronics10161973.

Full text

Abstract:

Selecting a final machine learning (ML) model typically occurs after a process of hyperparameter optimization in which many candidate models with varying structural properties and algorithmic settings are evaluated and compared. Evaluating each candidate model commonly relies on k-fold cross validation, wherein the data are randomly subdivided into k folds, with each fold being iteratively used as a validation set for a model that has been trained using the remaining folds. While many research studies have sought to accelerate ML model selection by applying metaheuristic and other search methods to the hyperparameter space, no consideration has been given to the k-fold cross validation process itself as a means of rapidly identifying the best-performing model. The current study rectifies this oversight by introducing a greedy k-fold cross validation method and demonstrating that greedy k-fold cross validation can vastly reduce the average time required to identify the best-performing model when given a fixed computational budget and a set of candidate models. This improved search time is shown to hold across a variety of ML algorithms and real-world datasets. For scenarios without a computational budget, this paper also introduces an early stopping algorithm based on the greedy cross validation method. The greedy early stopping method is shown to outperform a competing, state-of-the-art early stopping method both in terms of search time and the quality of the ML models selected by the algorithm. Since hyperparameter optimization is among the most time-consuming, computationally intensive, and monetarily expensive tasks in the broader process of developing ML-based solutions, the ability to rapidly identify optimal machine learning models using greedy cross validation has obvious and substantial benefits to organizations and researchers alike.

APA, Harvard, Vancouver, ISO, and other styles

26

SITORUS, IRMA YOLANDA, and PENDA SUDARTO HASUGIAN. "Shortest These search Heading Attractions Lubukpakam Using Greedy Algorithm." Journal Of Computer Networks, Architecture and High Performance Computing 2, no. 2 (June 1, 2020): 245–49. http://dx.doi.org/10.47709/cnapc.v2i2.417.

Full text

Abstract:

In the case of this shortest route search actually has many different types of solutions for path searching, for example the greedy algorithm, dijkstra, floyd-warshall and bellman-ford but what is commonly used to solve this problem is the Greedy algorithm because this algorithm is an algorithm that uses a problem solving approach with look for a temporary maximum value at each step. Of all the tourist attractions such as the Fruit Garden, Deli Serdang Swimming Pool, Deli Serdang Museum, Deli Serdang Regency Government Square, Tengku Raja Muda Field, the writer will look for the shortest path to take the closest route because of the many paths that can be taken to get the optimum path as well as using google maps. This application is made web-based with PHP and MySQL scripts as a database manager so that it is enough to connect to the internet network that everyone can easily access.

APA, Harvard, Vancouver, ISO, and other styles

27

Jiang, Jianguo. "A Shuffled Frog Leaping Algorithm Using Greedy Search Strategy." Journal of Information and Computational Science 11, no. 3 (February 10, 2014): 963–70. http://dx.doi.org/10.12733/jics20102913.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Hu, Ta-Yin, and Li-Wen Chen. "Traffic Signal Optimization with Greedy Randomized Tabu Search Algorithm." Journal of Transportation Engineering 138, no. 8 (August 2012): 1040–50. http://dx.doi.org/10.1061/(asce)te.1943-5436.0000404.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Feng, Yunhe, and Chirag Shah. "Has CEO Gender Bias Really Been Fixed? Adversarial Attacking and Improving Gender Fairness in Image Search." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 11 (June 28, 2022): 11882–90. http://dx.doi.org/10.1609/aaai.v36i11.21445.

Full text

Abstract:

Gender bias is one of the most common and well-studied demographic biases in information retrieval, and in general in AI systems. After discovering and reporting that gender bias for certain professions could change searchers' worldviews, mainstreaming image search engines, such as Google, quickly took action to correct and fix such a bias. However, given the nature of these systems, viz., being opaque, it is unclear if they addressed unequal gender representation and gender stereotypes in image search results systematically and in a sustainable way. In this paper, we propose adversarial attack queries composed of professions and countries (e.g., 'CEO United States') to investigate whether gender bias is thoroughly mitigated by image search engines. Our experiments on Google, Baidu, Naver, and Yandex Image Search show that the proposed attack can trigger high levels of gender bias in image search results very effectively. To defend against such attacks and mitigate gender bias, we design and implement three novel re-ranking algorithms -- epsilon-greedy algorithm, relevance-aware swapping algorithm, and fairness-greedy algorithm, to re-rank returned images for given image queries. Experiments on both simulated (three typical gender distributions) and real-world datasets demonstrate the proposed algorithms can mitigate gender bias effectively.

APA, Harvard, Vancouver, ISO, and other styles

30

Liu, Haiqiang, Gang Hua, Hongsheng Yin, and Yonggang Xu. "An Intelligent Grey Wolf Optimizer Algorithm for Distributed Compressed Sensing." Computational Intelligence and Neuroscience 2018 (2018): 1–10. http://dx.doi.org/10.1155/2018/1723191.

Full text

Abstract:

Distributed Compressed Sensing (DCS) is an important research area of compressed sensing (CS). This paper aims at solving the Distributed Compressed Sensing (DCS) problem based on mixed support model. In solving this problem, the previous proposed greedy pursuit algorithms easily fall into suboptimal solutions. In this paper, an intelligent grey wolf optimizer (GWO) algorithm called DCS-GWO is proposed by combining GWO and q-thresholding algorithm. In DCS-GWO, the grey wolves’ positions are initialized by using the q-thresholding algorithm and updated by using the idea of GWO. Inheriting the global search ability of GWO, DCS-GWO is efficient in finding global optimum solution. The simulation results illustrate that DCS-GWO has better recovery performance than previous greedy pursuit algorithms at the expense of computational complexity.

APA, Harvard, Vancouver, ISO, and other styles

31

Lin, Jin. "Path planning based on reinforcement learning." Applied and Computational Engineering 5, no. 1 (June 14, 2023): 853–58. http://dx.doi.org/10.54254/2755-2721/5/20230728.

Full text

Abstract:

With the wide application of mobile robots in industry, path planning has always been a difficult problem for mobile robots. Reinforcement learning algorithms such as Q-learning play a huge role in path planning. Traditional Q-learning algorithm mainly uses - greedy search policy. But for a fixed search factor -greedy. For example, the problems of slow convergence speed, time-consuming and many continuous action transformations (such as the number of turns during robot movement) are not conducive to the stability requirements of mobile robots in industrial transportation. Especially for the transportation of dangerous chemicals, continuous transformation of turns will increase the risk of objects toppling. This paper proposes a new method based on - greedy 's improved dynamic search strategy is used to improve the stability of mobile robots in motion planning. The experiment shows that the dynamic search strategy converges faster, consumes less time, has less continuous transformation times of action, and has higher motion stability in the test environment.

APA, Harvard, Vancouver, ISO, and other styles

32

Tsegelyk, G. G., and R. P. Krasniuk. "The optimization of databases replication in distributed information systems." Information extraction and processing 2017, no. 45 (December 26, 2017): 104–12. http://dx.doi.org/10.15407/vidbir2017.45.104.

Full text

Abstract:

New mathematical models of optimal distribution of databases replication in nodes of distributed information systems are formulated by the criteria: minimization of maintenance costs; restricted memory resources; minimizing synchronization time; minimizing the average time needed to search information. Precise solutions of the problems with the use of dynamic programming methods are constructed, Bellman recursive equations are obtained. The general scheme of the computational algorithm using the “greedy” choice procedure is presented and an algorithm for improving the obtained result is proposed. The strategies of greedy choice were investigated, the choice of criteria in the strategy of greedy choice is substantiated. The proposals have been formed regarding the formation of a balance between the accuracy and computational complexity of the algorithm through the introduction of a restricted search strategy. The computational complexity of the algorithm is estimated and its correctness is substantiated.

APA, Harvard, Vancouver, ISO, and other styles

33

Cao, Leilei, Lihong Xu, and Erik D. Goodman. "A Guiding Evolutionary Algorithm with Greedy Strategy for Global Optimization Problems." Computational Intelligence and Neuroscience 2016 (2016): 1–10. http://dx.doi.org/10.1155/2016/2565809.

Full text

Abstract:

A Guiding Evolutionary Algorithm (GEA) with greedy strategy for global optimization problems is proposed. Inspired by Particle Swarm Optimization, the Genetic Algorithm, and the Bat Algorithm, the GEA was designed to retain some advantages of each method while avoiding some disadvantages. In contrast to the usual Genetic Algorithm, each individual in GEA is crossed with the current global best one instead of a randomly selected individual. The current best individual served as a guide to attract offspring to its region of genotype space. Mutation was added to offspring according to a dynamic mutation probability. To increase the capability of exploitation, a local search mechanism was applied to new individuals according to a dynamic probability of local search. Experimental results show that GEA outperformed the other three typical global optimization algorithms with which it was compared.

APA, Harvard, Vancouver, ISO, and other styles

34

Wilt, Christopher, and Wheeler Ruml. "When Does Weighted A* Fail?" Proceedings of the International Symposium on Combinatorial Search 3, no. 1 (August 20, 2021): 137–44. http://dx.doi.org/10.1609/socs.v3i1.18250.

Full text

Abstract:

Weighted A* is the most popular satisficing algorithm for heuristic search. Although there is no formal guarantee that increasing the weight on the heuristic cost-to-go estimate will decrease search time, it is commonly assumed that increas- ing the weight leads to faster searches, and that greedy search will provide the fastest search of all. As we show, however, in some domains, increasing the weight slows down the search. This has an important consequence on the scaling behavior of Weighted A*: increasing the weight ad infinitum will only speed up the search if greedy search is effective. We examine several plausible hypotheses as to why greedy search would sometimes expand more nodes than A* and show that each of the simple explanations has flaws. Our contribution is to show that greedy search is fast if and only if there is a strong correlation between h(n) and d∗(n), the true distance-to-go, or if the heuristic is extremely accurate.

APA, Harvard, Vancouver, ISO, and other styles

35

RAFTOPOULOU, PARASKEVI, MANOLIS KOUBARAKIS, KOSTAS STERGIOU, and PETER TRIANTAFILLOU. "FAIR RESOURCE ALLOCATION IN A SIMPLE MULTI-AGENT SETTING: SEARCH ALGORITHMS AND EXPERIMENTAL EVALUATION." International Journal on Artificial Intelligence Tools 14, no. 06 (December 2005): 887–99. http://dx.doi.org/10.1142/s0218213005002454.

Full text

Abstract:

We study the problem of fair resource allocation in a simple cooperative multi-agent setting where we have k agents and a set of n objects to be allocated to those agents. Each object is associated with a weight represented by a positive integer or real number. We would like to allocate all objects to the agents so that each object is allocated to only one agent and the weight is distributed fairly. We adopt the fairness index popularized by the networking community as our measure of fairness, and study centralized algorithms for fair resource allocation. Based on the relationship between our problem and number partitioning, we devise a greedy algorithm for fair resource allocation that runs in polynomial time but is not guaranteed to find the optimal solution, and a complete anytime algorithm that finds the optimal solution but runs in exponential time. Then we study the phase transition behavior of the complete algorithm. Finally, we demonstrate that the greedy algorithm actually performs very well and returns almost perfectly fair allocations.

APA, Harvard, Vancouver, ISO, and other styles

36

Chan, Shao-Hung, Roni Stern, Ariel Felner, and Sven Koenig. "Greedy Priority-Based Search for Suboptimal Multi-Agent Path Finding." Proceedings of the International Symposium on Combinatorial Search 16, no. 1 (July 2, 2023): 11–19. http://dx.doi.org/10.1609/socs.v16i1.27278.

Full text

Abstract:

Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths, one for each agent, in a shared environment, while minimizing their sum of travel times. Since solving MAPF optimally is NP-hard, researchers have explored algorithms that solve MAPF suboptimally but efficiently. Priority-Based Search (PBS) is the leading algorithm for this purpose. It finds paths for individual agents, one at a time, and resolves collisions by assigning priorities to the colliding agents and replanning their paths during its search. However, PBS becomes ineffective for MAPF instances with high densities of agents and obstacles. Therefore, we introduce Greedy PBS (GPBS), which uses greedy strategies to speed up PBS by minimizing the number of collisions between agents. We then propose techniques that speed up GPBS further, namely partial expansions, target reasoning, induced constraints, and soft restarts. We show that GPBS with all these improvements has a higher success rate than the state-of-the-art suboptimal algorithm for a 1-minute runtime limit, especially for MAPF instances with small maps and dense obstacles.

APA, Harvard, Vancouver, ISO, and other styles

37

Gelfand, Andrew, Kalev Kask, and Rina Dechter. "Stopping Rules for Randomized Greedy Triangulation Schemes." Proceedings of the AAAI Conference on Artificial Intelligence 25, no. 1 (August 4, 2011): 1043–48. http://dx.doi.org/10.1609/aaai.v25i1.8021.

Full text

Abstract:

Many algorithms for performing inference in graphical models have complexity that is exponential in the treewidth — a parameter of the underlying graph structure. Computing the (minimal) treewidth is NPcomplete, so stochastic algorithms are sometimes used to find low width tree decompositions. A common approach for finding good decompositions is iteratively executing a greedy triangulation algorithm (e.g. minfill) with randomized tie-breaking. However, utilizing a stochastic algorithm as part of the inference task introduces a new problem — namely, deciding how long the stochastic algorithm should be allowed to execute before performing inference on the best tree decomposition found so far. We refer to this dilemma as the Stopping Problem and formalize it in terms of the total time needed to answer a probabilistic query. We propose a rule for discontinuing the search for improved decompositions and demonstrate the benefit (in terms of time saved) of applying this rule to Bayes and Markov network instances.

APA, Harvard, Vancouver, ISO, and other styles

38

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

39

Gil-Gala, Francisco J., Carlos Mencía, María R. Sierra, and Ramiro Varela. "Learning ensembles of priority rules for online scheduling by hybrid evolutionary algorithms." Integrated Computer-Aided Engineering 28, no. 1 (December 21, 2020): 65–80. http://dx.doi.org/10.3233/ica-200634.

Full text

Abstract:

This paper studies the computation of ensembles of priority rules for the One Machine Scheduling Problem with variable capacity and total tardiness minimization. Concretely, we address the problem of building optimal ensembles of priority rules, starting from a pool of rules evolved by a Genetic Programming approach. Building on earlier work, we propose a number of new algorithms. These include an iterated greedy search method, a local search algorithm and a memetic algorithm. Experimental results show the potential of the proposed approaches.

APA, Harvard, Vancouver, ISO, and other styles

40

Tian, Chuan. "Monte-Carlo tree search with Epsilon-Greedy for game of amazons." Applied and Computational Engineering 6, no. 1 (June 14, 2023): 904–9. http://dx.doi.org/10.54254/2755-2721/6/20230956.

Full text

Abstract:

The Game of the Amazons is an abstract strategy board game. It has a high computational complexity similar to the game of Go. Due to its NP-complete nature and large branching factor of game tree, finding the optimal move given a specific game state is infeasible and it is not trivial to design a computer algorithm that is competitive to an expert in the game of amazons. One way to tackle this problem is to leverage the Monte-Carlo Tree Search by using random simulations. In this article, a computationally cheap heuristic function is proposed and use together with Monte-Carlo Tree Search algorithm with Epsilon-Greedy policy aiming to design a competitive AI for the Game of the Amazon. The effectiveness of the -greedy based Monte-Carlo algorithm is compared to the widely used MCTS with Upper Confidence Bound and other classical tree search method such as breadth-first search, depth-first search, minmax search and alpha-beta pruning.

APA, Harvard, Vancouver, ISO, and other styles

41

Wang, Xiaogang, Guanghui Yan, Shikui Li, and Ning Zhou. "Population Cross Learning Algorithm Combining Greedy Search for Community Detection." Journal of Physics: Conference Series 1601 (July 2020): 032006. http://dx.doi.org/10.1088/1742-6596/1601/3/032006.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

Luo, Wenxiang, Yong Huang, Wenhao Zhou, Yin Nie, and Chunqin Lai. "MPPT Control Research of Improved Gray Wolf Algorithm According to Levy Flight and Greedy Strategy." Journal of Physics: Conference Series 2456, no. 1 (March 1, 2023): 012032. http://dx.doi.org/10.1088/1742-6596/2456/1/012032.

Full text

Abstract:

Abstract MPPT control study of improved Gray Wolf algorithm (GWO) according to Levy flight and greedy strategy: Solving the problems of maximum power point tracking (MPPT) with traditional Gray Wolf algorithm (GWO) under local shadows of photovoltaic arrays and sudden environmental changes, which is easily trapped in local optimum and has a slow convergence rate, and poor solution accuracy, a improved gray wolf algorithm (LGWO) according to Levy flight and greedy strategy is presented. It is used for the first time for maximum power point tracking under partial shadow and dynamic shadow changes of photovoltaic array. It is based on the traditional Grey Wolf algorithm (GWO), it introduces Levy’s flight search strategy, improve the algorithm of global search ability, expands search range, and filters optimal range through greedy strategy to further accelerate the convergence speed. MPPT simulation model according to Boost circuit is built using MATLAB/Simulink to verify. Experiments in the presence of partial shadows and shadow mutations. The results of simulation experiments show that the ameliorated Gray Wolf algorithm (LGWO) improves the tracking accuracy of MPPT by 0.03%, improves the convergence speed by 1.1 times and is more stable after reaching the maximum number of iterations. This verifies the feasibility and superiority of the ameliorated Grey Wolf algorithm in maximum power point tracking control.

APA, Harvard, Vancouver, ISO, and other styles

43

Herli, Audrey Maximillian, Indra Kharisma Raharjana, and Purbandini Soeparman. "Sistem Pencarian Hotel Berdasarkan Rute Perjalanan Terpendek Dengan Mempertimbangkan Daya Tarik Wisata Menggunakan Algoritma Greedy." Journal of Information Systems Engineering and Business Intelligence 1, no. 1 (June 25, 2015): 9. http://dx.doi.org/10.20473/jisebi.1.1.9-16.

Full text

Abstract:

Abstrak— Pencarian hotel merupakan hal yang penting dilakukan wisatawan dalam melakukan perjalanan wisata. Wisatawan akan mempertimbangkan kriteria hotel seperti kelas, harga dan review hotel. Selain itu faktor jarak hotel dan tempat wisata yang dikunjunginya adalah hal yang penting untuk dipertimbangkan. Pada penelitian ini dibangun sistem untuk melakukan pencarian hotel berdasarkan rute perjalanan wisata terpendek dengan daya tarik wisata mengunakanalgoritma greedy untuk memudahkan wisatawan dalam melakukan efisensi jarak perjalanan wisata serta membantu dalam pemilihan hotel. Penelitian ini dilakukan melalui empat tahap, tahap pertama adalah pengumpulan data dan informasi daya tarik wisata dan hotel. Tahap kedua adalah analisa data dengan algoritma greedy serta melakukan penyesuian pengunaan algoritma berdasarkan karakteristik perjalanan yang dilakukan wisatawan. Tahap ketiga adalah pembangunan sistem, dan tahap terakhir adalah melakukanevaluasi sistem bersama para ahli yang telah berpengalaman dalam bidang pariwisata dan calon penguna aplikasi ini.Hasil dari penelitian ini adalah sistem yang dapat memberikan rekomendasi rute dan urutan perjalanan terpendek antara hotel dan daya tarik wisata berdasarkan algoritma greedy. Kata Kunci— Hotel, Daya Tarik Wisata, Algoritma Greedy, Rute Perjalanan TerpendekAbstract— Hotel search was an important thingfor travelers in their traveling journey. Travelers would consider criteria such as class, price and review of the hotel.Beside those things, distance between Hotel and tourist attractionswasalsoimportant factor to be considered. In this research, system was constructed to perform a hotels search by shortest travelling route using Greedy Algorithm. This research was conducted through four stages, the first stage wasdata and information collectingof tourist attraction and hotel. Second stagewasdata analysis with greedy algorithm in purpose to classify the data and implementing greedy algorithm with manual calculation to the problem research. The third stage was the development of the system, and the last stage wasevaluating the system with the experts who are experienced in the field of tourism and the prospective user of this application. Results from this study was the system can provide recommendations and sequence the shortest journey between the hotel and tourist attraction based on the greedy algorithm. Keywords— Hotel, Tourist Attraction, Greedy Algorithm, Travelling Salesman Problem

APA, Harvard, Vancouver, ISO, and other styles

44

Ali, Yasser A., Emad Mahrous Awwad, Muna Al-Razgan, and Ali Maarouf. "Hyperparameter Search for Machine Learning Algorithms for Optimizing the Computational Complexity." Processes 11, no. 2 (January 21, 2023): 349. http://dx.doi.org/10.3390/pr11020349.

Full text

Abstract:

For machine learning algorithms, fine-tuning hyperparameters is a computational challenge due to the large size of the problem space. An efficient strategy for adjusting hyperparameters can be established with the use of the greedy search and Swarm intelligence algorithms. The Random Search and Grid Search optimization techniques show promise and efficiency for this task. The small population of solutions used at the outset, and the costly goal functions used by these searches, can lead to slow convergence or execution time in some cases. In this research, we propose using the machine learning model known as Support Vector Machine and optimizing it using four distinct algorithms—the Ant Bee Colony Algorithm, the Genetic Algorithm, the Whale Optimization, and the Particle Swarm Optimization—to evaluate the computational cost of SVM after hyper-tuning. Computational complexity comparisons of these optimization algorithms were performed to determine the most effective strategies for hyperparameter tuning. It was found that the Genetic Algorithm had a lower temporal complexity than other algorithms.

APA, Harvard, Vancouver, ISO, and other styles

45

Yousif, Adil, Samar M. Alqhtani, Mohammed Bakri Bashir, Awad Ali, Rafik Hamza, Alzubair Hassan, and Tawfeeg Mohmmed Tawfeeg. "Greedy Firefly Algorithm for Optimizing Job Scheduling in IoT Grid Computing." Sensors 22, no. 3 (January 23, 2022): 850. http://dx.doi.org/10.3390/s22030850.

Full text

Abstract:

The Internet of Things (IoT) is defined as interconnected digital and mechanical devices with intelligent and interactive data transmission features over a defined network. The ability of the IoT to collect, analyze and mine data into information and knowledge motivates the integration of IoT with grid and cloud computing. New job scheduling techniques are crucial for the effective integration and management of IoT with grid computing as they provide optimal computational solutions. The computational grid is a modern technology that enables distributed computing to take advantage of a organization’s resources in order to handle complex computational problems. However, the scheduling process is considered an NP-hard problem due to the heterogeneity of resources and management systems in the IoT grid. This paper proposed a Greedy Firefly Algorithm (GFA) for jobs scheduling in the grid environment. In the proposed greedy firefly algorithm, a greedy method is utilized as a local search mechanism to enhance the rate of convergence and efficiency of schedules produced by the standard firefly algorithm. Several experiments were conducted using the GridSim toolkit to evaluate the proposed greedy firefly algorithm’s performance. The study measured several sizes of real grid computing workload traces, starting with lightweight traces with only 500 jobs, then typical with 3000 to 7000 jobs, and finally heavy load containing 8000 to 10,000 jobs. The experiment results revealed that the greedy firefly algorithm could insignificantly reduce the makespan makespan and execution times of the IoT grid scheduling process as compared to other evaluated scheduling methods. Furthermore, the proposed greedy firefly algorithm converges on large search spacefaster , making it suitable for large-scale IoT grid environments.

APA, Harvard, Vancouver, ISO, and other styles

46

G B, Ujwal. "Visualising Path Finding Algorithms Application Development and Implementing." International Journal for Research in Applied Science and Engineering Technology 11, no. 5 (May 31, 2023): 3317–21. http://dx.doi.org/10.22214/ijraset.2023.51795.

Full text

Abstract:

Abstract: The Dijkstra algorithm, A* Search, Greedy Best-first Search, Swarm Search, Breadth-first, and Depth-first Search are some of the common algorithms used today. The pathfinding algorithm is used in this study to provide an overview of algorithms and how they are implemented. The user will also learn more about how different algorithms and programming in general work. Knowing these tactics will give them a fundamental understanding of how to create different navigational tools. The visualizer is a grid page containing a "start node" and a "end node." In order to enhance the overall picture and better understand how these pathfinding algorithms deal with our everyday problems, the spectator can add new characteristics like a maze, walls, and weights. To build a visualizer, a programmer needs a solid grasp of front-end programming languages and pathfinding techniques.

APA, Harvard, Vancouver, ISO, and other styles

47

Li, Yangyang, Jianping Zhang, Guiling Sun, and Dongxue Lu. "The Sparsity Adaptive Reconstruction Algorithm Based on Simulated Annealing for Compressed Sensing." Journal of Electrical and Computer Engineering 2019 (July 14, 2019): 1–8. http://dx.doi.org/10.1155/2019/6950819.

Full text

Abstract:

This paper proposes a novel sparsity adaptive simulated annealing algorithm to solve the issue of sparse recovery. This algorithm combines the advantage of the sparsity adaptive matching pursuit (SAMP) algorithm and the simulated annealing method in global searching for the recovery of the sparse signal. First, we calculate the sparsity and the initial support collection as the initial search points of the proposed optimization algorithm by using the idea of SAMP. Then, we design a two-cycle reconstruction method to find the support sets efficiently and accurately by updating the optimization direction. Finally, we take advantage of the sparsity adaptive simulated annealing algorithm in global optimization to guide the sparse reconstruction. The proposed sparsity adaptive greedy pursuit model has a simple geometric structure, it can get the global optimal solution, and it is better than the greedy algorithm in terms of recovery quality. Our experimental results validate that the proposed algorithm outperforms existing state-of-the-art sparse reconstruction algorithms.

APA, Harvard, Vancouver, ISO, and other styles

48

Han, Jihee, Tansel Uras, and Sven Koenig. "Toward a String-Pulling Approach to Path Smoothing on Grid Graphs." Proceedings of the International Symposium on Combinatorial Search 11, no. 1 (September 1, 2021): 106–10. http://dx.doi.org/10.1609/socs.v11i1.18541.

Full text

Abstract:

Paths found on grid graphs are often unrealistic looking in the continuous environment that the grid graph represents and often need to be smoothed after a search. The well-known algorithm for path smoothing is greedy in nature and does not necessarily eliminate all heading changes in freespace. We present a new path-smoothing algorithm based on “string pulling” and show experimentally that it consistently finds shorter paths than the greedy algorithm and produces paths with no heading changes in freespace.

APA, Harvard, Vancouver, ISO, and other styles

49

Xie, Fan, Martin Müller, and Robert Holte. "Understanding and Improving Local Exploration for GBFS." Proceedings of the International Conference on Automated Planning and Scheduling 25 (April 8, 2015): 244–48. http://dx.doi.org/10.1609/icaps.v25i1.13704.

Full text

Abstract:

Greedy Best First Search (GBFS) is a powerful algorithm at the heart of many state-of-the-art satisficing planners. The Greedy Best First Search with Local Search (GBFS-LS) algorithm adds exploration using a local GBFS to a global GBFS. This substantially improves performancefor domains that contain large uninformative heuristic regions (UHR), such as plateaus or local minima. This paper analyzes, quantifies and improves the performance of GBFS-LS.Planning problems with a mix of small and large UHRs are shown to be hard for GBFS but easy for GBFS-LS. In three standard IPC planning instances analyzed in detail, adding exploration using local GBFS gives more than three orders of magnitude speedup. As a second contribution, the detailed analysis leads to an improvedGBFS-LS algorithm, which replaces larger-scale local GBFS explorations with a greater number of smaller explorations.

APA, Harvard, Vancouver, ISO, and other styles

50

Torres-Jimenez, Jose, and Idelfonso Izquierdo-Marquez. "A Simulated Annealing Algorithm to Construct Covering Perfect Hash Families." Mathematical Problems in Engineering 2018 (July 26, 2018): 1–14. http://dx.doi.org/10.1155/2018/1860673.

Full text

Abstract:

Covering perfect hash families (CPHFs) are combinatorial designs that represent certain covering arrays in a compact way. In previous works, CPHFs have been constructed using backtracking, tabu search, and greedy algorithms. Backtracking is convenient for small CPHFs, greedy algorithms are appropriate for large CPHFs, and metaheuristic algorithms provide a balance between execution time and quality of solution for small and medium-size CPHFs. This work explores the construction of CPHFs by means of a simulated annealing algorithm. The neighborhood function of this algorithm is composed of three perturbation operators which together provide exploration and exploitation capabilities to the algorithm. As main computational results we have the generation of 64 CPHFs whose derived covering arrays improve the best-known ones. In addition, we use the simulated annealing algorithm to construct quasi-CPHFs from which quasi covering arrays are derived that are then completed and postoptimized; in this case the number of new covering arrays is 183. Together, the 247 new covering arrays improved the upper bound of 683 covering array numbers.

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Greedy search algorithm'

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