Computer Science – Neural and Evolutionary Computing
Scientific paper
2012-02-08
Computer Science
Neural and Evolutionary Computing
Scientific paper
Nowadays hybrid evolutionary algorithms, i.e, heuristic search algorithms combining several mutation operators some of which are meant to implement stochastically a well known technique designed for the specific problem in question while some others playing the role of random search, have become rather popular for tackling various NP-hard optimization problems. While empirical studies demonstrate that hybrid evolutionary algorithms are frequently successful at finding solutions having fitness sufficiently close to the optimal, many fewer articles address the computational complexity in a mathematically rigorous fashion. This paper is devoted to a mathematically motivated design and analysis of a parameterized family of evolutionary algorithms which provides a polynomial time approximation scheme for one of the well-known NP-hard combinatorial optimization problems, namely the "single machine scheduling problem without precedence constraints". The authors hope that the techniques and ideas developed in this article may be applied in many other situations.
He Jun
Mitavskiy Boris
No associations
LandOfFree
A Polynomial Time Approximation Scheme for a Single Machine Scheduling Problem Using a Hybrid Evolutionary Algorithm does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Polynomial Time Approximation Scheme for a Single Machine Scheduling Problem Using a Hybrid Evolutionary Algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Polynomial Time Approximation Scheme for a Single Machine Scheduling Problem Using a Hybrid Evolutionary Algorithm will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-64795