کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1141500 957014 2011 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Using Markov chains to analyze the effectiveness of local search algorithms
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
Using Markov chains to analyze the effectiveness of local search algorithms
چکیده انگلیسی

This paper analyzes the performance of local search algorithms (guided by the best-to-date solution at each iteration) in visiting suboptimal solutions for hard discrete optimization problems. The ββ-acceptable solution concept is used to capture how effectively an algorithm has performed to date and how effectively an algorithm can be expected to perform in the future in visiting suboptimal solutions. By this concept, an algorithm run is deemed a success if it reaches the level ββ, where ββ denotes an objective function value close to but still worse than the globally optimal value. A Markov chain state space reduction technique, state pooling, is introduced and used to obtain an estimator for the expected number of iterations to visit a ββ-acceptable solution. Convergence results for this estimator are provided. Computational experiments with the Lin–Kernighan–Helsgaun algorithm applied to medium and large travelling salesman problem instances taken from TSPLIB (all with known optimal solutions) are reported to illustrate the application of this estimator.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 8, Issue 2, May 2011, Pages 160–173
نویسندگان
, ,