Heuristic algorithms: Difference between revisions

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search
VisualWikitext
No edit summary
 
(50 intermediate revisions by 4 users not shown)
Line 1: Line 1:
Author: Anmol Singh (as2753)
Author: Zemin Mi (zm287), Boyu Yang (by274) (ChemE 6800 Fall 2024)


Steward: Fengqi You, Allen Yang
Stewards: Nathan Preuss, Wei-Han Chen, Tianqi Xiao, Guoqing Hu


== Introduction ==
== Introduction ==
In mathematical programming, a heuristic algorithm is a procedure that determines near-optimal solutions to an optimization problem. However, this is achieved by trading optimality, completeness, accuracy, or precision for speed. <ref> Eiselt, Horst A et al. Integer Programming And Network Models. Springer, 2011.</ref> Nevertheless, heuristics is a widely used technique for a variety of reasons:
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>Kokash, N. (2008). An introduction to heuristic algorithms. Department of Informatics and Telecommunications (2005): pages 1-8. https://www.researchgate.net/publication/228573156.  </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>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>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>


*Problems that do not have an exact solution or for which the formulation is unknown
== Methodology & Classic Example ==
*The computation of a problem is computationally intensive
Optimization heuristics can be categorized into two broad classes based on their approach, focus, and application: '''heuristics and metaheuristics'''.
*Calculation of bounds on the optimal solution in branch and bound solution processes
==Methodology==
Optimization heuristics can be categorized into two broad classes depending on the way the solution domain is organized:


===Construction methods (Greedy algorithms)===
=== Heuristics ===
The greedy algorithm works in phases, where the algorithm makes the optimal choice at each step as it attempts to find the overall optimal way to solve the entire problem. <ref>
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>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>
Moore, Karleigh et al. "Greedy Algorithms | Brilliant Math & Science Wiki". ''Brilliant.Org'', 2020, <nowiki>https://brilliant.org/wiki/greedy-algorithm/</nowiki>.</ref> It is a technique used to solve the famous “travelling salesman problem” where the heuristic followed is: "At each step of the journey, visit the nearest unvisited city."


====Example 1: Scheduling Problem====
=== '''Metaheuristics''' ===
''You are given a set of N schedules of lectures for a single day at a university. The schedule for a specific lecture is of the form (s time, f time) where s time represents the start time for that lecture and similarly, the f time represents the finishing time. Given a list of N lecture schedules, we need to select maximum set of lectures to be held out during the day such that none of the lectures overlaps with one another i.e. if lecture Li and Lj are included in our selection then the start time of j >= finish time of i or vice versa.<ref>"Greedy Algorithms Explained With Examples". Freecodecamp.Org, 2020, https://www.freecodecamp.org/news/what-is-a-greedy-algorithm/.</ref>''
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>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]]


Solution: The most optimal solution to this would be to consider the earliest finishing time first. We sort the intervals according to increasing order of their finishing times and then we start selecting intervals from the very beginning. The pseudo-code is as follows:
=== '''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>Xiao, N. (2009). Evolutionary Algorithms, International Encyclopedia of Human Geography, Elsevier, Pages 660-665. https://doi.org/10.1016/B978-008044910-4.00525-3.  </ref>


<code>function interval_scheduling_problem(requests)</code>
* '''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.


<code>schedule \gets \{\}</code>
* '''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.


<code>while requests is not yet empty</code>
== Popular Optimization Heuristics Algorithms ==


<code>choose a request i_r \in requests that has the lowest finishing time</code>
=== '''Heuristic Algorithms''' ===


<code>schedule \gets schedule \cup \{i_r\}</code>
==== '''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>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]]


<code>delete all requests in requests that are not compatible with i_r</code>
==== '''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>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]]


<code>end</code>
=== '''Metaheuristic Algorithms''' ===


<code>return schedule</code>
==== '''Tabu Search Algorithm''' ====
[[File: The Minimum Spanning Tree.jpg|thumb|<ref>“Minimum Spanning Tree Tutorials & Notes: Algorithms.” ''HackerEarth'', www.hackerearth.com/practice/algorithms/graphs/minimum-spanning-tree/tutorial/.</ref>Minimum spanning tree is the spanning tree where the cost is minimum among all the spanning trees.]]
'''Tabu Search (TS)''' is an advanced metaheuristic optimization technique designed to navigate complex search spaces and escape local optima using adaptive memory structures. Introduced by Fred Glover in 1986, TS systematically explores neighborhoods of solutions, employing a tabu list to record recently visited solutions or attributes, thereby preventing the search from cycling back to them. This strategic use of memory enables TS to traverse regions of the solution space that traditional local search methods might overlook, enhancing its capability to find near-optimal solutions across various combinatorial optimization problems.<ref>Glover, F., Laguna, M. (1998). Tabu Search. In: Du, DZ., Pardalos, P.M. (eds) Handbook of Combinatorial Optimization. Springer, Boston, MA. https://doi.org/10.1007/978-1-4613-0303-9_33. </ref>
<code>end</code>
[[File:Screenshot 2024-12-14 212340.png|center|thumb|400x400px|Figure 4. Tabu Search Algorithm Steps]]


====Example 2: The Minimum Spanning Tree ====
==== '''Simulated Annealing Algorithm''' ====
A spanning tree of the graph G=(V, E) is a tree that spans G (that is, it includes every vertex of  G) and is a subgraph of G (every edge in the tree belongs to G). The cost of the spanning tree is the sum of the weights of all the edges in the tree. There can be many spanning trees, however, the minimum spanning tree is the spanning tree where the cost is minimum among all the spanning trees. Minimum spanning tree has direct application in the design of networks.  
'''Simulated Annealing (SA)''' is a probabilistic optimization technique inspired by the annealing process in metallurgy, where controlled cooling of a material allows it to reach a minimum energy state. This algorithm was introduced by Kirkpatrick, Gelatt, and Vecchi in 1983 as a metaheuristic for solving global optimization problems. SA is particularly effective for complex issues with numerous local optima. The algorithm explores the solution space by accepting improvements and, with decreasing probability, worse solutions to escape local minima. This acceptance probability decreases over time according to a predefined cooling schedule, balancing exploration and exploitation. Due to its simplicity and robustness, SA has been successfully applied across various domains, including combinatorial optimization, scheduling, and machine learning.<ref>Delahaye, D., Chaimatanan, S., Mongeau, M. (2019). Simulated Annealing: From Basics to Applications. In: Gendreau, M., Potvin, JY. (eds) Handbook of Metaheuristics. International Series in Operations Research & Management Science, vol 272. Springer, Cham. https://doi.org/10.1007/978-3-319-91086-4_1. </ref>
[[File:Screenshot 2024-12-14 213250.png|center|thumb|400x400px|Figure 5. Simulated Annealing Algorithm Steps]]


===Local Search methods===
== Numerical Example: '''Traveling Salesman Problem (TSP)''' ==
Local Search method follows an iterative approach where we start with some initial solution, explore the neighbourhood of the current solution, and then replace the current solution with a better solution. For this method, the “travelling salesman problem” would follow the heuristic in which a solution is a cycle containing all nodes of the graph and the target is to minimize the total length of the cycle.
The table below show the distance between 4 cities. The algorithm aims to find a near-optimal path that visits all cities exactly once and returns to the starting city with minimal total distance.


==== Example Problem  ====
{| class="wikitable"
Suppose that the problem P is to find an optimal ordering of N jobs in a manufacturing system. A solution to this problem can be described as an N-vector of job numbers, in which the position of each job in the vector defines the order in which the job will be processed. For example, [3, 4, 1, 6, 5, 2] is a possible ordering of 6 jobs, where job 3 is processed first, followed by job 4, then job 1, and so on, finishing with job 2. Define now M as the set of moves that produce new orderings by the swapping of any two jobs. For example, [3, 1, 4, 6, 5, 2] is obtained by swapping the positions of jobs 4 and 1.<ref> Eiselt, Horst A et al. Integer Programming And Network Models. Springer, 2011.</ref>
|+Distance Matrix
==Popular Heuristic Algorithms==
!
Product (i)
!Weight per unit (w<sub>i</sub>)
!Value per unit (v<sub>i</sub>)
|-
|1
|7
|9
|-
|2
|5
|4
|-
|3
|4
|3
|-
|4
|3
|2
|-
|5
|1
|0.5
|}


===Genetic Algorithm===
The term Genetic Algorithm was first used by John Holland <ref>J.H. Holland (1975) ''Adaptation in Natural and Artificial Systems,'' University of Michigan Press, Ann Arbor, Michigan; re-issued by MIT Press (1992).</ref> They are designed to mimic the Darwinian theory of evolution, which states that populations of species evolve to produce more complex organisms and fitter for survival on Earth. Genetic algorithms operate on string structures, like biological structures, which are evolving in time according to the rule of survival of the fittest by using a randomized yet structured information exchange. Thus, in every generation, a new set of strings is created, using parts of the fittest members of the old set. <ref>Optimal design of heat exchanger networks, Editor(s): Wilfried Roetzel, Xing Luo, Dezhen Chen, Design and Operation of Heat Exchangers and their Networks, Academic Press, 2020, Pages 231-317, <nowiki>ISBN 9780128178942</nowiki>, <nowiki>https://doi.org/10.1016/B978-0-12-817894-2.00006-6</nowiki>.</ref> The algorithm terminates when the satisfactory fitness level has been reached for the population or the maximum generations have been reached. The typical steps are <ref>Wang FS., Chen LH. (2013) Genetic Algorithms. In: Dubitzky W., Wolkenhauer O., Cho KH., Yokota H. (eds) Encyclopedia of Systems Biology. Springer, New York, NY. <nowiki>https://doi.org/10.1007/978-1-4419-9863-7_412</nowiki> </ref>:


1.     Choose an initial population of candidate solutions


2.     Calculate the fitness, how well the solution is, of each individual
'''<big><u>Simple Heuristic Algorithms: Greedy Algorithm</u></big>'''


3.     Perform crossover from the population. The operation is to randomly choose some pair of individuals as parents and exchange so parts from the parents to generate new individuals
'''Overview:'''


4.     Mutation is to randomly change some individuals to create other new individuals
1)    Start at any city (A).


5.     Evaluate the fitness of the offspring
2)    At each step, move to the '''nearest unvisited city'''.


6.     Select the survive individuals
3)    Repeat until all cities are visited.


7.    Proceed from 3 if the termination criteria have not been reached
4)    Return to the starting city.  


Genetic algorithms have been applied in the fields of bioinformatics, computational biology, and systems biology. <ref>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 </ref>


===Tabu Search Algorithm===
Tabu search (TS) is a heuristic algorithm created by Fred Glover <ref>Fred Glover (1986). "Future Paths for Integer Programming and Links to Artificial Intelligence". Computers and Operations Research. '''13''' (5): 533–549. doi:10.1016/0305-0548(86)90048-1)</ref> using a gradient-descent search with memory techniques to avoid cycling for determining an optimal solution. It does so by forbidding or penalizing moves which take the solution, in the next iteration, to points in the solution space previously visited. The algorithm spends some memory to keep a Tabu list of forbidden moves, which are the moves of the previous iterations or moves that might be considered unwanted. A general algorithm is as follows <ref>Optimization of Preventive Maintenance Program for Imaging Equipment in Hospitals, Editor(s): Zdravko Kravanja, Miloš Bogataj, Computer-Aided Chemical Engineering, Elsevier, Volume 38, 2016, Pages 1833-1838, ISSN 1570-7946, <nowiki>ISBN 9780444634283</nowiki>, <nowiki>https://doi.org/10.1016/B978-0-444-63428-3.50310-6</nowiki>.</ref>:


1.     Select an initial solution ''s''<sub>0</sub> ∈ ''S''. Initialize the Tabu List ''L''<sub>0</sub> = ∅ and select a list tabu size. Establish ''k'' = 0.
'''Step-by-Step Solution:'''


2.     Determine the neighborhood feasibility ''N''(''s<sub>k</sub>'') that excludes inferior members of the tabu list ''L<sub>k</sub>''.
* '''Start at City A:'''


3.     Select the next movement ''s<sub>k</sub>'' <sub>+ 1</sub> from ''N''(''S<sub>k</sub>'') or ''L<sub>k</sub>'' if there is a better solution and update ''L<sub>k</sub>'' <sub>+ 1</sub>
Unvisited: {B,C,D}


4.     Stop if a condition of termination is reached, else, ''k'' = ''k'' + 1 and return to 1
Minimal Distance: A → B (distance = 10)


==== Example: The Classical Vehicle Routing Problem  ====
Path: A → B
''Vehicle Routing Problems'' have very important applications in distribution management and have become some of the most studied problems in the combinatorial optimization literature. These include several Tabu Search implementations that currently rank among the most effective. The ''Classical Vehicle Routing Problem'' (CVRP) is the basic variant in that class of problems. It can formally be defined as follows. Let ''G'' = (''V, A'') be a graph where ''V'' is the vertex set and ''A'' is the arc set. One of the vertices represents the ''depot'' at which a fleet of identical vehicles of capacity ''Q'' is based, and the other vertices customers that need to be serviced. With each customer vertex v<sub>i</sub> are associated a demand q<sub>i</sub> and a service time t<sub>i</sub>. With each arc (v<sub>i</sub>, v<sub>j</sub>) of ''A'' are associated a cost c<sub>ij</sub> and a travel time t<sub>ij</sub>.<ref>Glover, Fred, and Gary A Kochenberger. Handbook Of Metaheuristics. Kluwer Academic Publishers, 2003.</ref> The CVRP consists of finding a set of routes such that:


1.     Each route begins and ends at the depot
Total distance: 10


2.     Each customer is visited exactly once by exactly one route
* '''Move to City B:'''


3.     The total demand of the customers assigned to each route does not exceed ''Q''
Unvisited: {C,D}


4.     The total duration of each route (including travel and service times) does not exceed a specified value ''L''
Minimal Distance: B → D (distance = 25)


5.     The total cost of the routes is minimized
Path: A → B → D


A feasible solution for the problem thus consists in a partition of the customers into m groups, each of total demand no larger than ''Q'', that are sequenced to yield routes (starting and ending at the depot) of duration no larger than ''L''.
Total distance: 35


===Simulated Annealing Algorithm===
* '''Move to City D:'''
The Simulated Annealing Algorithm was developed by Kirkpatrick et. al. in 1983 <ref>Kirkpatrick, S., Gelatt, C., & Vecchi, M. (1983). Optimization by Simulated Annealing. ''Science,'' ''220''(4598), 671-680. Retrieved November 25, 2020, from <nowiki>http://www.jstor.org/stable/1690046</nowiki></ref> and is based on the analogy of ideal crystals in thermodynamics. The annealing process in metallurgy can make particles arrange themselves in the position with minima potential as the temperature is slowly decreased. The Simulation Annealing algorithm mimics this mechanism and uses the objective function of an optimization problem instead of the energy of a material to arrive at a solution. A general algorithm is as follows <ref>Brief review of static optimization methods, Editor(s): Stanisław Sieniutycz, Jacek Jeżowski, Energy Optimization in Process Systems and Fuel Cells (Third Edition), Elsevier, 2018, Pages 1-41, <nowiki>ISBN 9780081025574</nowiki>, <nowiki>https://doi.org/10.1016/B978-0-08-102557-4.00001-3</nowiki>.</ref> :


1.    Fix initial temperature (''T''<sup>0</sup>)
Unvisited: {C}


2.    Generate starting point '''x'''<sup>0</sup> (this is the best point '''''X'''''<sup>*</sup> at present)
Minimal Distance: D → C (distance = 30)


3.    Generate randomly point '''''X<sup>S</sup>''''' (neighboring point)
Path: A → B → D → C


4.    Accept '''''X<sup>S</sup>''''' as '''''X'''''<sup>*</sup> (currently best solution) if an acceptance criterion is met. This must be such condition that the probability of accepting a worse point is greater than zero, particularly at higher temperatures
Total distance: 65


5.    If an equilibrium condition is satisfied, go to (6), otherwise jump back to (3).
* '''Return to City A:'''


6.    If termination conditions are not met, decrease temperature according to certain cooling scheme and jump back to (1). If termination conditions are satisfied, stop calculations accepting current best value '''''X'''''<sup>*</sup> as final (‘optimal’) solution.  
Path: A → B → D → C → A
 
Total distance: 80
 
 
 
'''The greedy algorithm gives us a feasible solution quickly by choosing the nearest neighbor at each step. While it doesn't always guarantee the optimal solution, it's computationally efficient and provides a good starting point for more complex algorithms.'''
 
 
'''<big><u>Meta-Heuristic Algorithms: Tabu Search</u></big>'''
 
'''Overview:'''
 
1)    Generating '''neighborhood solutions'''.
 
2)    Selecting the best neighbor that is not in the '''Tabu List'''.
 
3)    Updating the '''Tabu List''' to prevent cycling.
 
4)    Repeating until a stopping criterion is met.
 
 
 
'''Step-by-Step Solution:'''
 
* '''Initialization:'''
 
Initial Path: A → B → C → D → A
 
Initial Distance: d = 10 + 35 + 30 + 20 = 95
 
Tabu List: [ ] (empty)
 
* '''Generating neighborhood solutions:'''
 
Neighborhood solutions are created by swapping the order of two cities in the current path (excluding A, the starting city). For the initial path A→B→C→D→A, the possible swaps are:
 
1.     Swap B and C  d = 95
 
2.     Swap B and D  d = 95
 
3.     Swap C and D  d = 80 (Best)
 
* '''Select the best Neighbor that not in the Tabu List'''
 
Swap C and D is the best Neighbor solution
 
New Tabu List: [(C,D)]
 
* '''Repeat Process:'''
 
New Path: A → B → D → C → A
 
New Distance: 80
 
Tabu List: [(C,D)]
 
* '''Generating neighborhood solutions'''
 
Notice (C,D) is in Tabu List, so swapping C and D is not a viable option here.
 
1.     Swap B and C  d = 80 (Best)
 
2.     Swap B and D  d = 95
 
* '''Select the best Neighbor that not in the Tabu List'''
 
1.     Swap B and C is the best Neighbor solution
 
2.     New Tabu List: [(C,D), (B,C)]
 
…
 
 
'''By using a Tabu List, Tabu Search avoids revisiting the same solutions and explores the solution space systematically, and reach the final solution which is 80.'''
 
 
<big>'''<u>Simplified approach: Hill Climbing</u>'''</big>
 
The tabu list above has two impacts on the algorithm. First, it prevents the algorithm from making any choice already chosen, which leads into cycling. Second, it makes the algorithms "flexible" to not always choose the optimal neighborhood solution, which allow exploring the suboptimal space. It is suitable for large and complex problems, but it is more computationally intensive and requires careful parameter tuning. For small and scalable problem, '''Hill Climbing''' is a simpler version.
 
 
 
'''Overview:'''
 
1)    Generating '''neighborhood solutions'''.
 
2)    Selecting the best neighbor that '''improves the objective'''. If there's none, terminate.
 
3)    Repeating until a stopping criterion is met.
 
 
 
'''Notice the process will stop if the current choice is better than any neighborhood solution, which means it will often get stuck in local optima and cannot escape.'''
 
==Applications==
Heuristic algorithms are extensively applied to optimize processes and solve computationally problems in IT field. They are used in network design and routing, where algorithms like A-star and Dijkstra help determine the most efficient paths for data transmission in communication networks. Cloud computing benefits from heuristics for resource allocation and load balancing, ensuring optimal distribution of tasks.<ref>Guo, Lizheng, et al. "Task scheduling optimization in cloud computing based on heuristic algorithm." ''Journal of networks'' 7.3 (2012): 547.</ref> Moreover, heuristic algorithms also thrive in numerous domains. In biology, heuristics approaches, like asBLAST and FASTA, are used to solve problems such as DNA and specific protein comparing.<ref>Chauhan, Shubhendra Singh, and Shikha Mittal. "Exact, Heuristics and Other Algorithms in Computational Biology." ''Bioinformatics and Computational Biology''. Chapman and Hall/CRC, 2023. 38-51.</ref> Heuristic algorithms are also instrumental in finance, optimizing the portfolios to balance risk and payback. <ref>Gilli, Manfred, Dietmar Maringer, and Peter Winker. "Applications of heuristics in finance." ''Handbook on information technology in finance'' (2008): 635-653.</ref>
 
==Conclusion==
Heuristic algorithms are widely applied in solving complex optimization problems where finding an exact solution is computationally infeasible. These algorithms use problem-specific strategies to explore the solution space efficiently, often arriving at near-optimal solutions in a fraction of the time required by exact methods. While heuristic algorithms may not always guarantee the optimal solution, their efficiency, scalability, and flexibility make them an important tool for those challenges in real world. These options allow us to make a call of compromise between computational feasibility and solution quality. As technology advances and problems grow in complexity, heuristic algorithms will continue to evolve to delve and improvise more potential in optimization.


==References==
==References==
<references />
<references />

Latest revision as of 17:44, 15 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.

Figure 1. Simple TSP Demonstration

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 Optimization Heuristics Algorithms

Heuristic Algorithms

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]

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.[8]

Figure 3. Local Search Algorithm (Hill-Climbing) Steps

Metaheuristic Algorithms

Tabu Search Algorithm

Tabu Search (TS) is an advanced metaheuristic optimization technique designed to navigate complex search spaces and escape local optima using adaptive memory structures. Introduced by Fred Glover in 1986, TS systematically explores neighborhoods of solutions, employing a tabu list to record recently visited solutions or attributes, thereby preventing the search from cycling back to them. This strategic use of memory enables TS to traverse regions of the solution space that traditional local search methods might overlook, enhancing its capability to find near-optimal solutions across various combinatorial optimization problems.[9]

Figure 4. Tabu Search Algorithm Steps

Simulated Annealing Algorithm

Simulated Annealing (SA) is a probabilistic optimization technique inspired by the annealing process in metallurgy, where controlled cooling of a material allows it to reach a minimum energy state. This algorithm was introduced by Kirkpatrick, Gelatt, and Vecchi in 1983 as a metaheuristic for solving global optimization problems. SA is particularly effective for complex issues with numerous local optima. The algorithm explores the solution space by accepting improvements and, with decreasing probability, worse solutions to escape local minima. This acceptance probability decreases over time according to a predefined cooling schedule, balancing exploration and exploitation. Due to its simplicity and robustness, SA has been successfully applied across various domains, including combinatorial optimization, scheduling, and machine learning.[10]

Figure 5. Simulated Annealing Algorithm Steps

Numerical Example: Traveling Salesman Problem (TSP)

The table below show the distance between 4 cities. The algorithm aims to find a near-optimal path that visits all cities exactly once and returns to the starting city with minimal total distance.

Distance Matrix

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


Simple Heuristic Algorithms: Greedy Algorithm

Overview:

1)    Start at any city (A).

2)    At each step, move to the nearest unvisited city.

3)    Repeat until all cities are visited.

4)    Return to the starting city.


Step-by-Step Solution:

  • Start at City A:

Unvisited: {B,C,D}

Minimal Distance: A → B (distance = 10)

Path: A → B

Total distance: 10

  • Move to City B:

Unvisited: {C,D}

Minimal Distance: B → D (distance = 25)

Path: A → B → D

Total distance: 35

  • Move to City D:

Unvisited: {C}

Minimal Distance: D → C (distance = 30)

Path: A → B → D → C

Total distance: 65

  • Return to City A:

Path: A → B → D → C → A

Total distance: 80


The greedy algorithm gives us a feasible solution quickly by choosing the nearest neighbor at each step. While it doesn't always guarantee the optimal solution, it's computationally efficient and provides a good starting point for more complex algorithms.


Meta-Heuristic Algorithms: Tabu Search

Overview:

1)    Generating neighborhood solutions.

2)    Selecting the best neighbor that is not in the Tabu List.

3)    Updating the Tabu List to prevent cycling.

4)    Repeating until a stopping criterion is met.


Step-by-Step Solution:

  • Initialization:

Initial Path: A → B → C → D → A

Initial Distance: d = 10 + 35 + 30 + 20 = 95

Tabu List: [ ] (empty)

  • Generating neighborhood solutions:

Neighborhood solutions are created by swapping the order of two cities in the current path (excluding A, the starting city). For the initial path A→B→C→D→A, the possible swaps are:

1.     Swap B and C  d = 95

2.     Swap B and D  d = 95

3.     Swap C and D  d = 80 (Best)

  • Select the best Neighbor that not in the Tabu List

Swap C and D is the best Neighbor solution

New Tabu List: [(C,D)]

  • Repeat Process:

New Path: A → B → D → C → A

New Distance: 80

Tabu List: [(C,D)]

  • Generating neighborhood solutions

Notice (C,D) is in Tabu List, so swapping C and D is not a viable option here.

1.     Swap B and C  d = 80 (Best)

2.     Swap B and D  d = 95

  • Select the best Neighbor that not in the Tabu List

1.     Swap B and C is the best Neighbor solution

2.     New Tabu List: [(C,D), (B,C)]

…


By using a Tabu List, Tabu Search avoids revisiting the same solutions and explores the solution space systematically, and reach the final solution which is 80.


Simplified approach: Hill Climbing

The tabu list above has two impacts on the algorithm. First, it prevents the algorithm from making any choice already chosen, which leads into cycling. Second, it makes the algorithms "flexible" to not always choose the optimal neighborhood solution, which allow exploring the suboptimal space. It is suitable for large and complex problems, but it is more computationally intensive and requires careful parameter tuning. For small and scalable problem, Hill Climbing is a simpler version.


Overview:

1)    Generating neighborhood solutions.

2)    Selecting the best neighbor that improves the objective. If there's none, terminate.

3)    Repeating until a stopping criterion is met.


Notice the process will stop if the current choice is better than any neighborhood solution, which means it will often get stuck in local optima and cannot escape.

Applications

Heuristic algorithms are extensively applied to optimize processes and solve computationally problems in IT field. They are used in network design and routing, where algorithms like A-star and Dijkstra help determine the most efficient paths for data transmission in communication networks. Cloud computing benefits from heuristics for resource allocation and load balancing, ensuring optimal distribution of tasks.[11] Moreover, heuristic algorithms also thrive in numerous domains. In biology, heuristics approaches, like asBLAST and FASTA, are used to solve problems such as DNA and specific protein comparing.[12] Heuristic algorithms are also instrumental in finance, optimizing the portfolios to balance risk and payback. [13]

Conclusion

Heuristic algorithms are widely applied in solving complex optimization problems where finding an exact solution is computationally infeasible. These algorithms use problem-specific strategies to explore the solution space efficiently, often arriving at near-optimal solutions in a fraction of the time required by exact methods. While heuristic algorithms may not always guarantee the optimal solution, their efficiency, scalability, and flexibility make them an important tool for those challenges in real world. These options allow us to make a call of compromise between computational feasibility and solution quality. As technology advances and problems grow in complexity, heuristic algorithms will continue to evolve to delve and improvise more potential in optimization.

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.
  9. ↑ Glover, F., Laguna, M. (1998). Tabu Search. In: Du, DZ., Pardalos, P.M. (eds) Handbook of Combinatorial Optimization. Springer, Boston, MA. https://doi.org/10.1007/978-1-4613-0303-9_33.
  10. ↑ Delahaye, D., Chaimatanan, S., Mongeau, M. (2019). Simulated Annealing: From Basics to Applications. In: Gendreau, M., Potvin, JY. (eds) Handbook of Metaheuristics. International Series in Operations Research & Management Science, vol 272. Springer, Cham. https://doi.org/10.1007/978-3-319-91086-4_1.
  11. ↑ Guo, Lizheng, et al. "Task scheduling optimization in cloud computing based on heuristic algorithm." Journal of networks 7.3 (2012): 547.
  12. ↑ Chauhan, Shubhendra Singh, and Shikha Mittal. "Exact, Heuristics and Other Algorithms in Computational Biology." Bioinformatics and Computational Biology. Chapman and Hall/CRC, 2023. 38-51.
  13. ↑ Gilli, Manfred, Dietmar Maringer, and Peter Winker. "Applications of heuristics in finance." Handbook on information technology in finance (2008): 635-653.
Retrieved from "https://optimization.cbe.cornell.edu/index.php?title=Heuristic_algorithms&oldid=7657"