Heuristic algorithms: Difference between revisions
No edit summary |
|||
| Line 4: | Line 4: | ||
== Introduction == | == Introduction == | ||
Heuristic algorithms are strategies designed to efficiently tackle complex optimization problems by providing approximate solutions when exact methods are impractical. This approach is particularly beneficial in scenarios where traditional algorithms may be computationally prohibitive.<ref>1. Kokash, N. (2008). An introduction to heuristic algorithms. Department of Informatics and Telecommunications (2005): pages 1-8. <nowiki>https://www.researchgate.net/publication/228573156</nowiki>.</ref> Heuristics are widely used because they excel in handling uncertainty, incomplete information, and large-scale optimization tasks. Their adaptability, scalability, and integration with other techniques make them valuable across fields like artificial intelligence, logistics, and operations research. Balancing speed and solution quality makes heuristics indispensable for tackling real-world challenges where optimal solutions are often infeasible.<ref>2. Ezugwu, A.E., Shukla, A.K., Nath, R. et al. (2021). Metaheuristics: a comprehensive overview and classification along with bibliometric analysis. Artif Intell Rev 54, 4237–4316. | Heuristic algorithms are strategies designed to efficiently tackle complex optimization problems by providing approximate solutions when exact methods are impractical. This approach is particularly beneficial in scenarios where traditional algorithms may be computationally prohibitive.<ref>1. Kokash, N. (2008). An introduction to heuristic algorithms. Department of Informatics and Telecommunications (2005): pages 1-8. <nowiki>https://www.researchgate.net/publication/228573156</nowiki>. </ref> Heuristics are widely used because they excel in handling uncertainty, incomplete information, and large-scale optimization tasks. Their adaptability, scalability, and integration with other techniques make them valuable across fields like artificial intelligence, logistics, and operations research. Balancing speed and solution quality makes heuristics indispensable for tackling real-world challenges where optimal solutions are often infeasible.<ref>2. Ezugwu, A.E., Shukla, A.K., Nath, R. et al. (2021). Metaheuristics: a comprehensive overview and classification along with bibliometric analysis. Artif Intell Rev 54, 4237–4316. https://doi.org/10.1007/s10462-020-09952-0. </ref> | ||
A prominent category within heuristic methods is metaheuristics, which are higher-level strategies that effectively guide the search process to explore the solution space. These include genetic algorithms, simulated annealing, and particle swarm optimization. Metaheuristics are designed to balance exploration and exploitation, thereby enhancing the likelihood of identifying near-optimal solutions across diverse problem domains.<ref>3. Salhi, S., Thompson, J. (2022). An Overview of Heuristics and Metaheuristics. In: Salhi, S., Boylan, J. (eds) The Palgrave Handbook of Operations Research. Palgrave Macmillan, Cham. | A prominent category within heuristic methods is metaheuristics, which are higher-level strategies that effectively guide the search process to explore the solution space. These include genetic algorithms, simulated annealing, and particle swarm optimization. Metaheuristics are designed to balance exploration and exploitation, thereby enhancing the likelihood of identifying near-optimal solutions across diverse problem domains.<ref>3. Salhi, S., Thompson, J. (2022). An Overview of Heuristics and Metaheuristics. In: Salhi, S., Boylan, J. (eds) The Palgrave Handbook of Operations Research. Palgrave Macmillan, Cham. https://doi.org/10.1007/978-3-030-96935-6_11. </ref> | ||
==Methodology & Classic Example== | ==Methodology & Classic Example== | ||
| Line 12: | Line 12: | ||
=== Heuristics === | === Heuristics === | ||
Heuristics are problem-solving methods that employ practical techniques to produce satisfactory solutions within a reasonable timeframe, especially when exact methods are impractical due to computational constraints. These algorithms utilize rules of thumb, educated guesses, and intuitive judgments to navigate complex search spaces efficiently. By focusing on the most promising areas of the search space, heuristics can quickly find good enough solutions without guaranteeing optimality.<ref>4. Silver, E. (2004). An overview of heuristic solution methods. J Oper Res Soc 55, 936–956. | Heuristics are problem-solving methods that employ practical techniques to produce satisfactory solutions within a reasonable timeframe, especially when exact methods are impractical due to computational constraints. These algorithms utilize rules of thumb, educated guesses, and intuitive judgments to navigate complex search spaces efficiently. By focusing on the most promising areas of the search space, heuristics can quickly find good enough solutions without guaranteeing optimality.<ref>4. Silver, E. (2004). An overview of heuristic solution methods. J Oper Res Soc 55, 936–956. https://doi.org/10.1057/palgrave.jors.2601758. </ref> | ||
=== '''Metaheuristics''' === | === '''Metaheuristics''' === | ||
Metaheuristics are high-level optimization strategies designed to efficiently explore large and complex search spaces to find near-optimal solutions for challenging problems. They guide subordinate heuristics using concepts derived from artificial intelligence, biology, mathematics, and physical sciences to enhance performance.<ref>5. Osman, I.H., Kelly, J.P. (1996). Meta-Heuristics: An Overview. In: Osman, I.H., Kelly, J.P. (eds) Meta-Heuristics. Springer, Boston, MA. | Metaheuristics are high-level optimization strategies designed to efficiently explore large and complex search spaces to find near-optimal solutions for challenging problems. They guide subordinate heuristics using concepts derived from artificial intelligence, biology, mathematics, and physical sciences to enhance performance.<ref>5. Osman, I.H., Kelly, J.P. (1996). Meta-Heuristics: An Overview. In: Osman, I.H., Kelly, J.P. (eds) Meta-Heuristics. Springer, Boston, MA. https://doi.org/10.1007/978-1-4613-1361-8_1. </ref> Unlike problem-specific algorithms, metaheuristics are flexible and can be applied across various domains, making them valuable tools for solving real-world optimization challenges. By balancing the global search space exploration with the exploitation of promising local regions, metaheuristics effectively navigate complex landscapes to identify high-quality solutions. | ||
[[File:0.png|thumb|428x428px|Figure 1. Simple TSP Demonstration]] | [[File:0.png|thumb|428x428px|Figure 1. Simple TSP Demonstration]] | ||
=== '''Classic Example: Traveling Salesman Problem (TSP)''' === | === '''Classic Example: Traveling Salesman Problem (TSP)''' === | ||
The traveling salesman problem states that given a set of n cities and the distances between each pair of cities, the objective is to find the shortest possible tour that starts and ends in the same city and visits each city exactly once.<ref>6. Xiao, N. (2009). Evolutionary Algorithms, International Encyclopedia of Human Geography, Elsevier, Pages 660-665. <nowiki>https://doi.org/10.1016/B978-008044910-4.00525-3</nowiki>.</ref> | The traveling salesman problem states that given a set of n cities and the distances between each pair of cities, the objective is to find the shortest possible tour that starts and ends in the same city and visits each city exactly once.<ref>6. Xiao, N. (2009). Evolutionary Algorithms, International Encyclopedia of Human Geography, Elsevier, Pages 660-665. <nowiki>https://doi.org/10.1016/B978-008044910-4.00525-3</nowiki>. </ref> | ||
* Heuristics solve the TSP by providing efficient and practical approaches to finding approximate solutions, especially for large instances where exact algorithms are computationally infeasible. Instead of exhaustively exploring all possible tours, heuristics focus on simplifying the problem using strategies like incremental solution building, iterative improvement, or probabilistic exploration. For example, constructive heuristics can create a feasible tour by starting at a city and iteratively adding the nearest unvisited city until all cities are covered. To reduce the total travel distance, local search heuristics refine an initial solution by making minor adjustments, such as swapping the order of cities. | * Heuristics solve the TSP by providing efficient and practical approaches to finding approximate solutions, especially for large instances where exact algorithms are computationally infeasible. Instead of exhaustively exploring all possible tours, heuristics focus on simplifying the problem using strategies like incremental solution building, iterative improvement, or probabilistic exploration. For example, constructive heuristics can create a feasible tour by starting at a city and iteratively adding the nearest unvisited city until all cities are covered. To reduce the total travel distance, local search heuristics refine an initial solution by making minor adjustments, such as swapping the order of cities. | ||
| Line 37: | Line 37: | ||
* '''Tabu Search Algorithm''' | * '''Tabu Search Algorithm''' | ||
* '''Simulated Annealing Algorithm''' | * '''Simulated Annealing Algorithm''' | ||
=== '''Constructive Algorithm (Greedy)''' === | |||
Constructive heuristics are algorithmic strategies that build solutions incrementally, starting from an empty set and adding elements sequentially until a complete and feasible solution is formed (greedy algorithms). This approach is particularly advantageous due to its simplicity in design, analysis, implementation and limited computational complexity. However, the quality of solutions produced by constructive heuristics heavily depends on the criteria used for adding elements, and they may only sometimes yield optimal results.<ref>7. Aringhieri, R., Cordone, R., Guastalla, A., Grosso, A. (2023). Constructive and Destructive Methods in Heuristic Search. In: Martí, R., Martínez-Gavara, A. (eds) Discrete Diversity and Dispersion Maximization. Springer Optimization and Its Applications, vol 204. Springer, Cham. https://doi.org/10.1007/978-3-031-38310-6_4.</ref> | |||
[[File:Screenshot 2024-12-14 210730.png|center|thumb|400x400px|Figure 2. Constructive Algorithm (Greedy) Steps]] | |||
=== '''Local Search Algorithm (Hill-Climbing)''' === | |||
Local search heuristics are optimization techniques that iteratively refine a single solution by exploring its immediate neighborhood to find improved solutions. Starting from an initial solution, these methods make incremental changes to enhance the objective function with each iteration. This approach is particularly effective for complex combinatorial problems where an exhaustive search is impractical. However, local search heuristics can become trapped in local optima, focusing on immediate improvements without considering the global solution space. Various strategies, such as random restarts or memory-based enhancements, are employed to escape local optima and explore the solution space more broadly.<ref>8. Michiels, W., Aarts, E.H.L., Korst, J. (2018). Theory of Local Search. In: Martí, R., Pardalos, P., Resende, M. (eds) Handbook of Heuristics. Springer, Cham. https://doi.org/10.1007/978-3-319-07124-4_6. </ref> | |||
[[File:Screenshot 2024-12-14 211444.png|center|thumb|400x400px|Figure 3. Local Search Algorithm (Hill-Climbing) Steps]] | |||
== Numerical Example: Knapsack Problem == | == Numerical Example: Knapsack Problem == | ||
Revision as of 21:16, 14 December 2024
Author: Zemin Mi (zm287), Boyu Yang (by274) (ChemE 6800 Fall 2024)
Stewards: Nathan Preuss, Wei-Han Chen, Tianqi Xiao, Guoqing Hu
Introduction
Heuristic algorithms are strategies designed to efficiently tackle complex optimization problems by providing approximate solutions when exact methods are impractical. This approach is particularly beneficial in scenarios where traditional algorithms may be computationally prohibitive.[1] Heuristics are widely used because they excel in handling uncertainty, incomplete information, and large-scale optimization tasks. Their adaptability, scalability, and integration with other techniques make them valuable across fields like artificial intelligence, logistics, and operations research. Balancing speed and solution quality makes heuristics indispensable for tackling real-world challenges where optimal solutions are often infeasible.[2]
A prominent category within heuristic methods is metaheuristics, which are higher-level strategies that effectively guide the search process to explore the solution space. These include genetic algorithms, simulated annealing, and particle swarm optimization. Metaheuristics are designed to balance exploration and exploitation, thereby enhancing the likelihood of identifying near-optimal solutions across diverse problem domains.[3]
Methodology & Classic Example
Optimization heuristics can be categorized into two broad classes based on their approach, focus, and application: heuristics and metaheuristics.
Heuristics
Heuristics are problem-solving methods that employ practical techniques to produce satisfactory solutions within a reasonable timeframe, especially when exact methods are impractical due to computational constraints. These algorithms utilize rules of thumb, educated guesses, and intuitive judgments to navigate complex search spaces efficiently. By focusing on the most promising areas of the search space, heuristics can quickly find good enough solutions without guaranteeing optimality.[4]
Metaheuristics
Metaheuristics are high-level optimization strategies designed to efficiently explore large and complex search spaces to find near-optimal solutions for challenging problems. They guide subordinate heuristics using concepts derived from artificial intelligence, biology, mathematics, and physical sciences to enhance performance.[5] Unlike problem-specific algorithms, metaheuristics are flexible and can be applied across various domains, making them valuable tools for solving real-world optimization challenges. By balancing the global search space exploration with the exploitation of promising local regions, metaheuristics effectively navigate complex landscapes to identify high-quality solutions.
Classic Example: Traveling Salesman Problem (TSP)
The traveling salesman problem states that given a set of n cities and the distances between each pair of cities, the objective is to find the shortest possible tour that starts and ends in the same city and visits each city exactly once.[6]
- Heuristics solve the TSP by providing efficient and practical approaches to finding approximate solutions, especially for large instances where exact algorithms are computationally infeasible. Instead of exhaustively exploring all possible tours, heuristics focus on simplifying the problem using strategies like incremental solution building, iterative improvement, or probabilistic exploration. For example, constructive heuristics can create a feasible tour by starting at a city and iteratively adding the nearest unvisited city until all cities are covered. To reduce the total travel distance, local search heuristics refine an initial solution by making minor adjustments, such as swapping the order of cities.
- Metaheuristics, such as simulated annealing or genetic algorithms, tackle the TSP by employing high-level strategies to explore the solution space more broadly and escape local optima. These methods balance global search space exploration with local exploitation of promising regions, allowing for a more thorough search for better solutions. They iteratively improve the solution while occasionally considering less favorable configurations to avoid being confined to suboptimal areas. By guiding the search process intelligently, metaheuristics adapt dynamically and effectively solve the TSP, often producing near-optimal solutions even for large-scale or complex problem instances.
Popular Heuristic Algorithms
The popular heuristic algorithms can be categorized as below:
Heuristic Algorithm
- Constructive Algorithm (Greedy)
- Local Search Algorithm (Hill-Climbing)
Metaheuristic Algorithms
- Tabu Search Algorithm
- Simulated Annealing Algorithm
Constructive Algorithm (Greedy)
Constructive heuristics are algorithmic strategies that build solutions incrementally, starting from an empty set and adding elements sequentially until a complete and feasible solution is formed (greedy algorithms). This approach is particularly advantageous due to its simplicity in design, analysis, implementation and limited computational complexity. However, the quality of solutions produced by constructive heuristics heavily depends on the criteria used for adding elements, and they may only sometimes yield optimal results.[7]
Local Search Algorithm (Hill-Climbing)
Local search heuristics are optimization techniques that iteratively refine a single solution by exploring its immediate neighborhood to find improved solutions. Starting from an initial solution, these methods make incremental changes to enhance the objective function with each iteration. This approach is particularly effective for complex combinatorial problems where an exhaustive search is impractical. However, local search heuristics can become trapped in local optima, focusing on immediate improvements without considering the global solution space. Various strategies, such as random restarts or memory-based enhancements, are employed to escape local optima and explore the solution space more broadly.[8]
Numerical Example: Knapsack Problem
One of the most common applications of the heuristic algorithm is the Knapsack Problem, in which a given set of items (each with a mass and a value) are grouped to have a maximum value while being under a certain mass limit. It uses the Greedy Approximation Algorithm to sort the items based on their value per unit mass and then includes the items with the highest value per unit mass if there is still space remaining.
Example
The following table specifies the weights and values per unit of five different products held in storage. The quantity of each product is unlimited. A plane with a weight capacity of 13 is to be used, for one trip only, to transport the products. We would like to know how many units of each product should be loaded onto the plane to maximize the value of goods shipped.
|
Product (i) |
Weight per unit (wi) | Value per unit (vi) |
|---|---|---|
| 1 | 7 | 9 |
| 2 | 5 | 4 |
| 3 | 4 | 3 |
| 4 | 3 | 2 |
| 5 | 1 | 0.5 |
Solution:
(a) Stages:
We view each type of product as a stage, so there are 5 stages. We can also add a sixth stage representing the endpoint after deciding
(b) States:
We can view the remaining capacity as states, so there are 14 states in each stage: 0,1, 2, 3, …13
(c) Possible decisions at each stage:
Suppose we are in state s in stage n (n < 6), hence there are s capacity remaining. Then the possible number of items we can pack is:
j = 0, 1, …[s/wn]
For each such action j, we can have an arc going from the state s in stage n to the state n – j*wn in stage n + 1. For each arc in the graph, there is a corresponding benefit j*vn. We are trying to find a maximum benefit path from state 13 in stage 1, to stage 6.
(d) Optimization function:
Let fn(s) be the value of the maximum benefit possible with items of type n or greater using total capacity at most s
(e) Boundary conditions:
The sixth stage should have all zeros, that is, f6(s) = 0 for each s = 0,1, … 13
(f) Recurrence relation:
fn(s) = max {j*vn + fn+1(s – j*wn)}, j = 0, 1, …, [s/wn]
(g) Compute:
The solution will not show all the computations steps. Instead, only a few cases are given below to illustrate the idea.
- For stage 5, f5(s) = maxj=0, 1, …[s/1] {j*0.5 + 0} = 0.5s because given the all zero states in stage 6, the maximum possible value is to use up all the remaining s capacity.
- For stage 4, state 7,
f4(7) = maxj=0,1, …, [7/w4] = {j*v4 + f5(7 - w4*j)}
= max {0 + 3.5; 2 + 2; 4 + 0.5}
= 4.5
Using the recurrence relation above, we get the following table:
| Unused Capacity
s |
f1(s) | Type 1
opt |
f2(s) | Type 2
opt |
f3(s) | Type 3
opt |
f4(s) | Type 4
opt |
f5(s) | Type 5
opt |
f6(s) |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 13 | 13.5 | 1 | 10 | 2 | 9.5 | 3 | 8.5 | 4 | 6.5 | 13 | 0 |
| 12 | 13 | 1 | 9 | 2 | 9 | 3 | 8 | 4 | 6 | 12 | 0 |
| 11 | 12 | 1 | 8.5 | 2 | 8 | 2 | 7 | 3 | 5.5 | 11 | 0 |
| 10 | 11 | 1 | 8 | 2 | 7 | 2 | 6.5 | 3 | 5 | 10 | 0 |
| 9 | 10 | 1 | 7 | 1 | 6.5 | 2 | 6 | 3 | 4.5 | 9 | 0 |
| 8 | 9.5 | 1 | 6 | 1 | 6 | 2 | 5 | 2 | 4 | 8 | 0 |
| 7 | 9 | 1 | 5 | 1 | 5 | 1 | 4.5 | 2 | 3.5 | 7 | 0 |
| 6 | 4.5 | 0 | 4.5 | 1 | 4 | 1 | 4 | 2 | 3 | 6 | 0 |
| 5 | 4 | 0 | 4 | 1 | 3.5 | 1 | 3 | 1 | 2.5 | 5 | 0 |
| 4 | 3 | 0 | 3 | 0 | 3 | 1 | 2.5 | 1 | 2 | 4 | 0 |
| 3 | 2 | 0 | 2 | 0 | 2 | 0 | 2 | 1 | 1.5 | 3 | 0 |
| 2 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 2 | 0 |
| 1 | 0.5 | 0 | 0.5 | 0 | 0.5 | 0 | 0.5 | 0 | 0.5 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Optimal solution: The maximum benefit possible is 13.5. Tracing forward to get the optimal solution: the optimal decision corresponding to the entry 13.5 for f1(1) is 1, therefore we should pack 1 unit of type 1. After that we have 6 capacity remaining, so look at f2(6) which is 4.5, corresponding to the optimal decision of packing 1 unit of type 2. After this, we have 6-5 = 1 capacity remaining, and f3(1) = f4(1) = 0, which means we are not able to pack any type 3 or type 4. Hence we go to stage 5 and find that f5(1) = 1, so we should pack 1 unit of type 5. This gives the entire optimal solution as can be seen in the table below:
| Optimal solution | |
|---|---|
| Product (i) | Number of units |
| 1 | 1 |
| 2 | 1 |
| 5 | 1 |
Applications
Heuristic algorithms have become an important technique in solving current real-world problems. Its applications can range from optimizing the power flow in modern power systems[9] to groundwater pumping simulation models[10]. Heuristic optimization techniques are increasingly applied in environmental engineering applications as well such as the design of a multilayer sorptive barrier system for landfill liner.[11] Heuristic algorithms have also been applied in the fields of bioinformatics, computational biology, and systems biology.[12]
Conclusion
Heuristic algorithms are not a panacea, but they are handy tools to be used when the use of exact methods cannot be implemented. Heuristics can provide flexible techniques to solve hard problems with the advantage of simple implementation and low computational cost. Over the years, we have seen a progression in heuristics with the development of hybrid systems that combine selected features from various types of heuristic algorithms such as tabu search, simulated annealing, and genetic or evolutionary computing. Future research will continue to expand the capabilities of existing heuristics to solve complex real-world problems.
References
- ↑ 1. Kokash, N. (2008). An introduction to heuristic algorithms. Department of Informatics and Telecommunications (2005): pages 1-8. https://www.researchgate.net/publication/228573156.
- ↑ 2. Ezugwu, A.E., Shukla, A.K., Nath, R. et al. (2021). Metaheuristics: a comprehensive overview and classification along with bibliometric analysis. Artif Intell Rev 54, 4237–4316. https://doi.org/10.1007/s10462-020-09952-0.
- ↑ 3. Salhi, S., Thompson, J. (2022). An Overview of Heuristics and Metaheuristics. In: Salhi, S., Boylan, J. (eds) The Palgrave Handbook of Operations Research. Palgrave Macmillan, Cham. https://doi.org/10.1007/978-3-030-96935-6_11.
- ↑ 4. Silver, E. (2004). An overview of heuristic solution methods. J Oper Res Soc 55, 936–956. https://doi.org/10.1057/palgrave.jors.2601758.
- ↑ 5. Osman, I.H., Kelly, J.P. (1996). Meta-Heuristics: An Overview. In: Osman, I.H., Kelly, J.P. (eds) Meta-Heuristics. Springer, Boston, MA. https://doi.org/10.1007/978-1-4613-1361-8_1.
- ↑ 6. Xiao, N. (2009). Evolutionary Algorithms, International Encyclopedia of Human Geography, Elsevier, Pages 660-665. https://doi.org/10.1016/B978-008044910-4.00525-3.
- ↑ 7. Aringhieri, R., Cordone, R., Guastalla, A., Grosso, A. (2023). Constructive and Destructive Methods in Heuristic Search. In: Martí, R., Martínez-Gavara, A. (eds) Discrete Diversity and Dispersion Maximization. Springer Optimization and Its Applications, vol 204. Springer, Cham. https://doi.org/10.1007/978-3-031-38310-6_4.
- ↑ 8. Michiels, W., Aarts, E.H.L., Korst, J. (2018). Theory of Local Search. In: Martí, R., Pardalos, P., Resende, M. (eds) Handbook of Heuristics. Springer, Cham. https://doi.org/10.1007/978-3-319-07124-4_6.
- ↑ NIU, M., WAN, C. & Xu, Z. A review on applications of heuristic optimization algorithms for optimal power flow in modern power systems. J. Mod. Power Syst. Clean Energy 2, 289–297 (2014), https://doi.org/10.1007/s40565-014-0089-4
- ↑ J. L. Wang, Y. H. Lin and M. D. Lin, "Application of heuristic algorithms on groundwater pumping source identification problems," 2015 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM), Singapore, 2015, pp. 858-862, https://doi.org/10.1109/IEEM.2015.7385770.
- ↑ Matott, L. Shawn, et al. “Application of Heuristic Optimization Techniques and Algorithm Tuning to Multilayered Sorptive Barrier Design.” Environmental Science & Technology, vol. 40, no. 20, 2006, pp. 6354–6360., https://doi.org/10.1021/es052560+.
- ↑ Larranaga P, Calvo B, Santana R, Bielza C, Galdiano J, Inza I, Lozano JA, Armananzas R, Santafe G, Perez A, Robles V (2006) Machine learning in bioinformatics. Brief Bioinform 7(1):86–112