The simplex algorithm is a fairly effective method of solving linear programming problems though there are many linear programming problems for which an inexact solution with optimal utility is desirable. For problems in which we cannot produce exact solutions we need to use heuristics to get a best approximation of the optimal solution.
Metaheuristics can be used to produce solutions to mathematical problems under conditions of limited computational capacity. Hill climbing is a metaheuristic that can be used to find local optima by iteratively improving an arbitrary solution to a problem but it is not guaranteed to produce a global optima.
The hill climbing metaheuristic can be used for example to optimize a solution to the traveling salesman problem by first finding a basic feasible solution and then switching the order in which certain nodes are visited as long as that switch improves the solution. There are various other metaheuristics such as tabu search that can be used to solve mathematical optimization problems.
No comments:
Post a Comment