Abstract/Description
Over the past few decades, a wide variety of classes of combinatorial problems (e.g. the assignment problem, the knapsack problem, the vehicle routing problem, etc.) have emerged - from such areas as management science, telecommunication, AI, VLSI design and many others. Many large combinatorial problems are NP-hard problems because of the combinatorial growth of their solution search space with the problem size. Such problems are commonly solved by some version of a prominent metaheuristic (e.g. Genetic Algorithms, Tabu Search, Simulated Annealing and etc.). These heuristics seek good but approximate solutions at a reasonable computational cost. These heuristics are of stochastic nature. Heuristic researchers often make claims about the relative performance of metaheuristics without considering their stochastic nature and consequently their claims are not reliable. This paper discusses how to make an effective application of these metaheuristics to any NP-hard problem and to assess their solution quality in an acceptable way.
Keywords
NP-hard problem, Stochastic processes, Vehicles, Routing, Artificial intelligence, Very large scale integration, Genetic algorithms, Computational modeling
Location
Crystal Ball Room A, Hotel Pearl Continental, Karachi, Pakistan
Session Theme
Algorithms, Tools and Applications [ALGO-2]
Session Type
Other
Session Chair
Dr. Ashraf Iqbal
Start Date
27-8-2005 5:05 PM
End Date
27-8-2005 5:30 PM
Recommended Citation
Hussain, D. (2005). Metaheuristic Applications and Their Solutions Quality. International Conference on Information and Communication Technologies. Retrieved from https://ir.iba.edu.pk/icict/2005/2005/36
Included in
Biotechnology Commons, Computational Biology Commons, Genetics Commons, Technology and Innovation Commons
Metaheuristic Applications and Their Solutions Quality
Crystal Ball Room A, Hotel Pearl Continental, Karachi, Pakistan
Over the past few decades, a wide variety of classes of combinatorial problems (e.g. the assignment problem, the knapsack problem, the vehicle routing problem, etc.) have emerged - from such areas as management science, telecommunication, AI, VLSI design and many others. Many large combinatorial problems are NP-hard problems because of the combinatorial growth of their solution search space with the problem size. Such problems are commonly solved by some version of a prominent metaheuristic (e.g. Genetic Algorithms, Tabu Search, Simulated Annealing and etc.). These heuristics seek good but approximate solutions at a reasonable computational cost. These heuristics are of stochastic nature. Heuristic researchers often make claims about the relative performance of metaheuristics without considering their stochastic nature and consequently their claims are not reliable. This paper discusses how to make an effective application of these metaheuristics to any NP-hard problem and to assess their solution quality in an acceptable way.
