Contents
Academic literature on the topic 'Greedy heuristic algorithms'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Greedy heuristic algorithms.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Journal articles on the topic "Greedy heuristic algorithms"
1
Wilt, Christopher, and Wheeler Ruml. "Building a Heuristic for Greedy Search." Proceedings of the International Symposium on Combinatorial Search 6, no. 1 (2021): 131–40. http://dx.doi.org/10.1609/socs.v6i1.18352.
Full textAbstract:
Suboptimal heuristic search algorithms such as greedy best-first search allow us to find solutions when constraints of either time, memory, or both prevent the application of optimal algorithms such as A*. Guidelines for building an effective heuristic for A* are well established in the literature, but we show that if those rules are applied for greedy best-first search, performance can actually degrade. Observing what went wrong for greedy best-first search leads us to a quantitative metric appropriate for greedy heuristics, called Goal Distance Rank Correlation (GDRC). We demonstrate that GDRC can be used to build effective heuristics for greedy best-first search automatically.
2
Wilt, Christopher, and Wheeler Ruml. "Effective Heuristics for Suboptimal Best-First Search." Journal of Artificial Intelligence Research 57 (October 31, 2016): 273–306. http://dx.doi.org/10.1613/jair.5036.
Full textAbstract:
Suboptimal heuristic search algorithms such as weighted A* and greedy best-first search are widely used to solve problems for which guaranteed optimal solutions are too expensive to obtain. These algorithms crucially rely on a heuristic function to guide their search. However, most research on building heuristics addresses optimal solving. In this paper, we illustrate how established wisdom for constructing heuristics for optimal search can fail when considering suboptimal search. We consider the behavior of greedy best-first search in detail and we test several hypotheses for predicting when a heuristic will be effective for it. Our results suggest that a predictive characteristic is a heuristic's goal distance rank correlation (GDRC), a robust measure of whether it orders nodes according to distance to a goal. We demonstrate that GDRC can be used to automatically construct abstraction-based heuristics for greedy best-first search that are more effective than those built by methods oriented toward optimal search. These results reinforce the point that suboptimal search deserves sustained attention and specialized methods of its own.
3
Hignasari, L. Virginayoga. "Komparasi Algoritma Cheapest Insertion Heuristic (CIH) Dan Greedy Dalam Optimasi Rute Pendistribusian Barang." Jurnal Ilmiah Vastuwidya 2, no. 2 (2020): 31–39. http://dx.doi.org/10.47532/jiv.v2i2.87.
Full textAbstract:
This study was aimed to compare algorithms that can effectively provide better solutions related to the problem of determining the shortest route in the distribution of goods. This research was a qualitative research. The object of research was the route of shipping goods of a business that is engaged in printing and convection. The algorithms compared in this study were Cheapest Insertion Heuristic (CIH) and Greedy algorithms. Both algorithms have advantages and disadvantages in finding the shortest route. From the results of the analysis using these two algorithms, the Cheapest Insertion Heuristic (CIH) and Greedy algorithm can provide almost the same optimization results. The difference was only the selection of the journey. The strength of the Greedy algorithm was that the calculation steps are simpler than the Cheapest Insertion Heuristic (CIH) algorithm. While the disadvantage of the Greedy algorithm was that it is inappropriate to find the shortest route with a relatively large number of places visited. The advantage of the Cheapest Insertion Heuristic (CIH) algorithm was that this algorithm is still stable, used for the relatively large number of places visited. While the lack of Cheapest Insertion Heuristic (CIH) algorithm was a complicated principle of calculation and was relatively longer than the Greedy algorithm.
4
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 (2020): 779–92. http://dx.doi.org/10.1177/1748006x20914498.
Full textAbstract:
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.
5
Panggabean, Jonas Franky R. "Hybrid Ant Colony Optimization-Genetics Algorithm to Minimize Makespan Flow Shop Scheduling." International Journal of Engineering & Technology 7, no. 2.2 (2018): 40. http://dx.doi.org/10.14419/ijet.v7i2.2.11868.
Full textAbstract:
Flow shop scheduling is a scheduling model in which the job to be processed entirely flows in the same product direction / path. In other words, jobs have routing work together. Scheduling problems often arise if there is n jobs to be processed on the machine m, which must be specified which must be done first and how to allocate jobs on the machine to obtain a scheduled production process. In research of Zini, H and ElBernoussi, S. (2016) NEH Heuristic and Stochastic Greedy Heuristic (SG) algorithms. This paper presents modified harmony search (HS) for flow shop scheduling problems with the aim of minimizing the maximum completion time of all jobs (makespan). To validate the proposed algorithm this computational test was performed using a sample dataset of 60 from the Taillard Benchmark. The HS algorithm is compared with two constructive heuristics of the literature namely the NEH heuristic and stochastic greedy heuristic (SG). The experimental results were obtained on average for the dataset size of 20 x 5 to 50 x 10, that the ACO-GA algorithm has a smaller makespan than the other two algorithms, but for large-size datasets the ACO-GA algorithm has a greater makespan of both algorithms with difference of 1.4 units of time.
6
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 textAbstract:
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.
7
Selvi, V. "Clustering Analysis of Greedy Heuristic Method in Zero_One Knapsack Problem." International Journal of Emerging Research in Management and Technology 6, no. 7 (2018): 39. http://dx.doi.org/10.23956/ijermt.v6i7.181.
Full textAbstract:
Knapsack problem is a surely understood class of optimization problems, which tries to expand the profit of items in a knapsack without surpassing its capacity, Knapsack can be solved by several algorithms such like Greedy, dynamic programming, Branch & bound etc. The solution to the zero_one knapsack problem (KP) can be viewed as the result of a sequence of decision. Clustering is the process of resolving that type of applications. Different clustering application for grouping elements with equal priority. In this paper we are introducing greedy heuristic algorithm for solving zero_one knapsack problem. We will exhibit a relative investigation of the Greedy, dynamic programming, B&B and Genetic algorithms regarding of the complexity of time requirements, and the required programming efforts and compare the total value for each of them. Greedy and Genetic algorithms can be used to solve the 0-1 Knapsack problem within a reasonable time complexity. The worst-case time complexity (Big-O) of both algorithms is O(N). Using the greedy method, the algorithm can produce high quality clusters while reduce time the best partioning avoid the memory confinement problem during the process.
8
Silva Arantes, Jesimar da, Márcio da Silva Arantes, Claudio Fabiano Motta Toledo, Onofre Trindade Júnior, and Brian Charles Williams. "Heuristic and Genetic Algorithm Approaches for UAV Path Planning under Critical Situation." International Journal on Artificial Intelligence Tools 26, no. 01 (2017): 1760008. http://dx.doi.org/10.1142/s0218213017600089.
Full textAbstract:
The present paper applies a heuristic and genetic algorithms approaches to the path planning problem for Unmanned Aerial Vehicles (UAVs), during an emergency landing, without putting at risk people and properties. The path re-planning can be caused by critical situations such as equipment failures or extreme environmental events, which lead the current UAV mission to be aborted by executing an emergency landing. This path planning problem is introduced through a mathematical formulation, where all problem constraints are properly described. Planner algorithms must define a new path to land the UAV following problem constraints. Three path planning approaches are introduced: greedy heuristic, genetic algorithm and multi-population genetic algorithm. The greedy heuristic aims at quickly find feasible paths, while the genetic algorithms are able to return better quality solutions within a reasonable computational time. These methods are evaluated over a large set of scenarios with different levels of diffculty. Simulations are also conducted by using FlightGear simulator, where the UAV’s behaviour is evaluated for different wind velocities and wind directions. Statistical analysis reveal that combining the greedy heuristic with the genetic algorithms is a good strategy for this problem.
9
K, Gayathri Devi. "A Hybrid Firefly Algorithm Approach for Job Shop Scheduling Problem." International Journal for Research in Applied Science and Engineering Technology 9, no. 12 (2021): 1436–44. http://dx.doi.org/10.22214/ijraset.2021.39536.
Full textAbstract:
Abstract: Job shop scheduling has always been one of the most sought out research problems in Combinatorial optimization. Job Shop Scheduling problems (JSSP) are categorized under NP hard problems. In recent years the meta heuristic algorithms have been proved effective to solve hardcore NP problem. Firefly Algorithm is one of such meta heuristic techniques which is nature inspired from firefly characteristic. Its potential can be enhanced further by hybridizing it with other known evolutionary algorithms and thereby getting improved results in less computational time. In this paper we have proposed a new hybrid technique christened as HyFA, by hybridizing Firefly algorithm(FA) with simulated annealing (SA) and Greedy heuristics approach (GHA). The hybrid technique has the advantages of all three algorithms and are combined in such a way that a quicker and better optimal solution is obtained. Our proposed HyFA is coded in Matlab with an objective to minimize the makespan (Cm). The novel hybrid technique is then used to evaluate 1-25 Lawrence problems taken from literature. The results show the proposed technique is more effective not only in getting optimal results but has significantly reduced computational time. Keywords: Scheduling, Optimisation, Job shop scheduling, Meta-heuristics, Firefly, Simulated Annealing, Greedy heuristics Approach.
10
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 textAbstract:
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.