Heuristic algorithms: Difference between revisions

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search
VisualWikitext
No edit summary
 
(20 intermediate revisions by the same user not shown)
Line 1: Line 1:
Author: Zemin Mi (zm287), Boyu Yang (by274), Jinglin Wang (jw2745) (ChemE 6800 Fall 2024)
Author: Zemin Mi (zm287), Boyu Yang (by274) (ChemE 6800 Fall 2024)


Stewards: Nathan Preuss, Wei-Han Chen, Tianqi Xiao, Guoqing Hu
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>
''Introduction to Algorithms'' (Cormen, Leiserson, Rivest, and Stein) 2001, Chapter 16 "Greedy Algorithms".</ref> It is a technique used to solve the famous “traveling salesman problem” where the heuristic followed is: "At each step of the journey, visit the nearest unvisited city."


====Example: 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 a 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 L<sub>i</sub> and L<sub>j</sub> are included in our selection then the start time of j ≥ finish time of i or vice versa. The most optimal solution to this would be to consider the earliest finishing time first. We would sort the intervals according to the increasing order of their finishing times and then start selecting intervals from the very beginning.  
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]]


===Local Search methods===
=== '''Classic Example: Traveling Salesman Problem (TSP)''' ===
The Local Search method follows an iterative approach where we start with some initial solution, explore the neighborhood of the current solution, and then replace the current solution with a better solution.<ref> Eiselt, Horst A et al. Integer Programming and Network Models. Springer, 2011.</ref> For this method, the “traveling 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 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>


==== Example Problem  ====
* '''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.
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.
==Popular Heuristic Algorithms==


===Genetic Algorithm===
* '''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.
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>, https://doi.org/10.1016/B978-0-12-817894-2.00006-6.</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. https://doi.org/10.1007/978-1-4419-9863-7_412 </ref>:


1.     Choose an initial population of candidate solutions
== Popular Optimization Heuristics Algorithms ==


2.     Calculate the fitness, how well the solution is, of each individual
=== '''Heuristic Algorithms''' ===


3.     Perform crossover from the population. The operation is to randomly choose some pair of individuals like parents and exchange so parts from the parents to generate new individuals
==== '''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]]


4.     Mutation is to randomly change some individuals to create other new individuals
==== '''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]]


5.     Evaluate the fitness of the offspring
=== '''Metaheuristic Algorithms''' ===


6.     Select the survive individuals
==== '''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.<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>
[[File:Screenshot 2024-12-14 212340.png|center|thumb|400x400px|Figure 4. Tabu Search Algorithm Steps]]


7.    Proceed from 3 if the termination criteria have not been reached
==== '''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.<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]]


===Tabu Search Algorithm===
== Numerical Example: '''Traveling Salesman Problem (TSP)''' ==
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,https://doi.org/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 that 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>, https://doi.org/10.1016/B978-0-444-63428-3.50310-6.</ref>:
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.


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.
2.     Determine the neighborhood feasibility ''N''(''s<sub>k</sub>'') that excludes inferior members of the tabu list ''L<sub>k</sub>''.
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>
4.     Stop if a condition of termination is reached, else, ''k'' = ''k'' + 1 and return to 1
==== Example: The Classical Vehicle Routing Problem  ====
''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
2.     Each customer is visited exactly once by exactly one route
3.     The total demand of the customers assigned to each route does not exceed ''Q''
4.     The total duration of each route (including travel and service times) does not exceed a specified value ''L''
5.     The total cost of the routes is minimized
A feasible solution for the problem thus consists of 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''.
===Simulated Annealing Algorithm===
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 http://www.jstor.org/stable/1690046</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>, https://doi.org/10.1016/B978-0-08-102557-4.00001-3.</ref> :
1.    Fix initial temperature (''T''<sup>0</sup>)
2.    Generate starting point '''x'''<sup>0</sup> (this is the best point '''''X'''''<sup>*</sup> at present)
3.    Generate randomly point '''''X<sup>S</sup>''''' (neighboring point)
4.    Accept '''''X<sup>S</sup>''''' as '''''X'''''<sup>*</sup> (currently best solution) if an acceptance criterion is met. This must be such a condition that the probability of accepting a worse point is greater than zero, particularly at higher temperatures
5.    If an equilibrium condition is satisfied, go to (6), otherwise jump back to (3).
6.    If termination conditions are not met, decrease the temperature according to a certain cooling scheme and jump back to (1). If the termination conditions are satisfied, stop calculations accepting the current best value '''''X'''''<sup>*</sup> as the final (‘optimal’) solution. 
== 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.
'''<big>Example</big>'''
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. 
{| class="wikitable"
{| class="wikitable"
|+
|+Distance Matrix
!
!
Product (i)  
Product (i)  
Line 117: Line 75:
|0.5
|0.5
|}
|}
'''<big>Solution:</big>'''


'''(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:'''
'''<big><u>Simple Heuristic Algorithms: Greedy Algorithm</u></big>'''
 
'''Overview:'''
 
1)    Start at any city (A).
 
2)    At each step, move to the '''nearest unvisited city'''.


We can view the remaining capacity as states, so there are 14 states in each stage: 0,1, 2, 3, …13
3)    Repeat until all cities are visited.


'''(c) Possible decisions at each stage:'''
4)    Return to the starting city.


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/w<sub>n</sub>]


For each such action j, we can have an arc going from the state s in stage n to the state n – j*w<sub>n</sub> in stage n + 1. For each arc in the graph, there is a corresponding benefit j*v<sub>n</sub>. We are trying to find a maximum benefit path from state 13 in stage 1, to stage 6.
'''Step-by-Step Solution:'''


'''(d) Optimization function:'''
* '''Start at City A:'''


Let f<sub>n</sub>(s) be the value of the maximum benefit possible with items of type n or greater using total capacity at most s
Unvisited: {B,C,D}


'''(e) Boundary conditions:'''
Minimal Distance: A → B (distance = 10)


The sixth stage should have all zeros, that is, f<sub>6</sub>(s) = 0 for each s = 0,1, … 13
Path: A → B


'''(f) Recurrence relation:'''
Total distance: 10


f<sub>n</sub>(s) = max {j*v<sub>n</sub> + f<sub>n+1</sub>(s – j*w<sub>n</sub>)}, j = 0, 1, …, [s/w<sub>n</sub>]
* '''Move to City B:'''


'''(g) Compute:'''
Unvisited: {C,D}


The solution will not show all the computations steps. Instead, only a few cases are given below to illustrate the idea.
Minimal Distance: B → D (distance = 25)


* For stage 5, f<sub>5</sub>(s) = max<sub>j=0, 1, …[s/1]</sub> {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.
Path: A → B → D
* For stage 4, state 7,


f<sub>4</sub>(7) = max<sub>j=0,1, …, [7/w4]</sub> = {j*v<sub>4</sub> + f<sub>5</sub>(7 - w<sub>4*</sub>j)}
Total distance: 35


= max {0 + 3.5; 2 + 2; 4 + 0.5}
* '''Move to City D:'''


= 4.5
Unvisited: {C}


Using the recurrence relation above, we get the following table:
Minimal Distance: D → C (distance = 30)
{| class="wikitable"
 
|+
Path: A → B → D → C
!Unused Capacity
 
s
Total distance: 65
!f<sub>1</sub>(s)
 
!Type 1
* '''Return to City A:'''
opt
 
!f<sub>2</sub>(s)
Path: A → B → D → C → A
!Type 2
 
opt
Total distance: 80
!f<sub>3</sub>(s)
 
!Type 3
 
opt
 
!f<sub>4</sub>(s)
'''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.'''
!Type 4
 
opt
 
!f<sub>5</sub>(s)
'''<big><u>Meta-Heuristic Algorithms: Tabu Search</u></big>'''
!Type 5
 
opt
'''Overview:'''
!f<sub>6</sub>(s)
 
|-
1)    Generating '''neighborhood solutions'''.
|13
 
|13.5
2)    Selecting the best neighbor that is not in the '''Tabu List'''.
|1
 
|10
3)    Updating the '''Tabu List''' to prevent cycling.
|2
 
|9.5
4)    Repeating until a stopping criterion is met.
|3
 
|8.5
 
|4
 
|6.5
'''Step-by-Step Solution:'''
|13
 
|0
* '''Initialization:'''
|-
 
|12
Initial Path: A → B → C → D → A
|13
 
|1
Initial Distance: d = 10 + 35 + 30 + 20 = 95
|9
 
|2
Tabu List: [ ] (empty)
|9
 
|3
* '''Generating neighborhood solutions:'''
|8
 
|4
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:
|6
 
|12
1.     Swap B and C  d = 95
|0
 
|-
2.     Swap B and D  d = 95
|11
 
|12
3.     Swap C and D  d = 80 (Best)
|1
 
|8.5
* '''Select the best Neighbor that not in the Tabu List'''
|2
 
|8
Swap C and D is the best Neighbor solution
|2
 
|7
New Tabu List: [(C,D)]
|3
 
|5.5
* '''Repeat Process:'''
|11
 
|0
New Path: A → B → D → C → A
|-
 
|10
New Distance: 80
|11
 
|1
Tabu List: [(C,D)]
|8
 
|2
* '''Generating neighborhood solutions'''
|7
 
|2
Notice (C,D) is in Tabu List, so swapping C and D is not a viable option here.
|6.5
 
|3
1.     Swap B and C  d = 80 (Best)
|5
 
|10
2.     Swap B and D  d = 95
|0
 
|-
* '''Select the best Neighbor that not in the Tabu List'''
|9
 
|10
1.     Swap B and C is the best Neighbor solution
|1
 
|7
2.     New Tabu List: [(C,D), (B,C)]
|1
 
|6.5
…
|2
 
|6
 
|3
'''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.'''
|4.5
 
|9
 
|0
<big>'''<u>Simplified approach: Hill Climbing</u>'''</big>
|-
 
|8
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.
|9.5
 
|1
 
|6
 
|1
'''Overview:'''
|6
 
|2
1)    Generating '''neighborhood solutions'''.
|5
 
|2
2)    Selecting the best neighbor that '''improves the objective'''. If there's none, terminate.
|4
 
|8
3)    Repeating until a stopping criterion is met.
|0
 
|-
 
|7
 
|9
'''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.'''
|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 f<sub>1</sub>(1) is 1, therefore we should pack 1 unit of type 1. After that we have 6 capacity remaining, so look at f<sub>2</sub>(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 f<sub>3</sub>(1) = f<sub>4</sub>(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 f<sub>5</sub>(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:
{| class="wikitable"
|+
! colspan="2" |Optimal solution
|-
!Product (i)
!Number of units
|-
|1
|1
|-
|2
|1
|-
|5
|1
|}


==Applications==
==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<ref> 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</ref> to groundwater pumping simulation models<ref> 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.</ref>. 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.<ref>Matott, L. Shawn, et al. “Application of Heuristic Optimization Techniques and Algorithm Tuning to Multilayered Sorptive Barrier Design.” Environmental Science &amp; Technology, vol. 40, no. 20, 2006, pp. 6354–6360., https://doi.org/10.1021/es052560+.</ref> Heuristic algorithms have also 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>
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==
==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.
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"