Difference between revisions of "Heuristic algorithms"

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search
(Created page with "Author: Anmol Singh (as2753)")
 
Line 1: Line 1:
 
Author: Anmol Singh (as2753)
 
Author: Anmol Singh (as2753)
 +
 +
Instructor: Fengqi You
 +
 +
== 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.''' Nevertheless, heuristics is a widely used technique for a variety of reasons:
 +
 +
·      Problems that do not have an exact solution or for which the formulation is unknown
 +
 +
·      The computation of a problem is computationally intensive
 +
 +
·      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:
 +
 +
1.    Construction methods (Greedy algorithms)
 +
 +
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. 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."
 +
 +
2.    Local Search methods
 +
 +
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. 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.
 +
 +
 +
== Applications ==
 +
 +
=== Genetic Algorithm ===
 +
 +
=== Tabu Search Algorithm ===
 +
 +
=== Simulated Annealing Algorithm ===
 +
 +
=== Particle Swarm Optimization ===
 +
 +
== Example: The Knapsack Problem ==
 +
 +
 +
== References ==
 +
·       Eiselt, Horst A et al. ''Integer Programming And Network Models''. Springer, 2011.
 +
 +
·       Moore, Karleigh et al. "Greedy Algorithms | Brilliant Math & Science Wiki". ''Brilliant.Org'', 2020, <nowiki>https://brilliant.org/wiki/greedy-algorithm/</nowiki>.

Revision as of 01:01, 23 November 2020

Author: Anmol Singh (as2753)

Instructor: Fengqi You

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. Nevertheless, heuristics is a widely used technique for a variety of reasons:

·      Problems that do not have an exact solution or for which the formulation is unknown

·      The computation of a problem is computationally intensive

·      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:

1.    Construction methods (Greedy algorithms)

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. 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."

2.    Local Search methods

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. 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.


Applications

Genetic Algorithm

Tabu Search Algorithm

Simulated Annealing Algorithm

Particle Swarm Optimization

Example: The Knapsack Problem

References

·       Eiselt, Horst A et al. Integer Programming And Network Models. Springer, 2011.

·       Moore, Karleigh et al. "Greedy Algorithms | Brilliant Math & Science Wiki". Brilliant.Org, 2020, https://brilliant.org/wiki/greedy-algorithm/.