|
ГЛАВНАЯ
> Вернуться к содержанию
Программные системы и вычислительные методы
Правильная ссылка на статью:
Родзин С.И., Курейчик В.В.
Состояние, проблемы и перспективы развития биоэвристик
// Программные системы и вычислительные методы.
2016. № 2.
С. 158-172.
DOI: 10.7256/2454-0714.2016.2.18608 URL: https://nbpublish.com/library_read_article.php?id=18608
Состояние, проблемы и перспективы развития биоэвристик
Родзин Сергей Иванович
кандидат технических наук
профессор, Южный федеральный университет
347928, Россия, Ростовская область, г. Таганрог, ул. Чехова, 80-1
Rodzin Sergey Ivanovich
PhD in Technical Science
Professor, Department of Software and Computer Usage, Southern Federal University
347928, Russia, Rostovskaya oblast', g. Taganrog, ul. Chekhova, 80-1
|
srodzin@yandex.ru
|
|
 |
Другие публикации этого автора
|
|
|
Курейчик Владимир Викторович
доктор технических наук
профессор, Южный федеральный университет
347928, Россия, Ростовская область, г. Таганрог, пер. Некрасовский, 44, оф. Г-435
Kureichik Vladimir Viktorovich
Doctor of Technical Science
Professor, Department of Computer Aided Design, Southern Federal University
347928, Russia, Rostovskaya oblast', g. Taganrog, per. Nekrasovskii, 44, of. G-435
|
|
vkur@sfedu.ru
|
|
 |
Другие публикации этого автора
|
|
|
DOI: 10.7256/2454-0714.2016.2.18608
Дата направления статьи в редакцию:
02-04-2016
Дата публикации:
20-06-2016
Аннотация:
Предметом обзора является современное состояние, проблемные вопросы и перспективные области исследований биоэвристик для решения оптимизационных задач. Биоэвристики – это математические преобразования, трансформирующие входной поток информации в выходной и основанные на правилах имитации механизмов эволюции, природных аналогий, на статистическом подходе к исследованию ситуаций и итерационном приближении к искомому решению. В настоящее время биоэвристики превратились в важный инструмент поиска близких к оптимальным решений задач, которые до этого считались неразрешимыми. Методологической и теоретической основой обзорного исследования являлись методы оптимизации и поддержки принятия оптимальных решений, искусственный интеллект, теория эволюционных вычислений. В статье анализируются фундаментальные результаты, полученные в области биоэвристических алгоритмов оптимизации: теорема Холланда и NFL-теорема. Устанавливаются закономерности и структура биоэвристик, особенности кодирования решений, базовый цикл биоэвристических алгоритмов. Рассматривается перспективное направление в анализе времени работы когнитивных биоэвристических алгоритмов - анализ дрейфа.
Ключевые слова:
когнитивный биоинспирированный алгоритм, метаэвристика, оптимизация, эволюционные вычисления, эволюционный оператор, NFL-теорема, анализ дрейфа, функция приспособленности, моделирование, программирование
Исследование выполнено при финансовой поддержке государственного задания (проектная часть) в сфере научной деятельности Министерства образования и науки Российской Федерации (проект № 8.823.2014/K) в Южном федеральном университете.
Abstract: The subject of the article is the current state, problematic issues and promising field of research of bio heuristics for solving optimization problems. Bio heuristics are mathematical transformations of the input stream to the output data based on simulation mechanisms of evolution, natural analogies, on a statistical approach to the study of situations and iterative approximation to the desired solution. Currently, bio heuristics have become an important tool for finding close to optimal solutions of problems which earlier were considered unsolvable. The methodological and theoretical bases of the scoping study are optimization techniques and decision making support methods, artificial intelligence, evolutionary computation theory. The article analyzes the fundamental results obtained in the field of bio-heuristic optimization algorithms: Holland theorem and TAD-theorem. The article establishes patterns and structure of bio heuristics, especially coding solutions, basic cycle of bio heuristics algorithms. The study reviews a promising direction in the analysis time of the biological cognitive heuristics - drift analysis.
Keywords: cognitive bioinspired algorithm, metaheuristics, optimization, evolutionary computation, evolution operator, NFL-theorem, drift analysis, fitness function, programming, modeling
Библиография
1. Rastrigin L.A. The convergence of the random search method in the extremal control of a many parameter system // Automation and remote control. 1963. no. 24(10). pp. 1337–1342.
2. Nelder J.A., Mead R. A simplex method for function minimization // Computer journal. 1965. no. 7. pp. 308–313.
3. Fogel L., Owens A.J., Walsh M.J. Artificial intelligence through simulated evolution. Wiley, 1966. 452 р.
4. Kernighan B.W., Lin S. An efficient heuristic procedure for partitioning graphs // Bell system technical journal. 1970. no. 49. pp. 291–307.
5. Holland J.H. Adaptation in natural and artificial systems. Uni of Michigan press, 1975. P. 45.
6. Smith S.F. A Learning system based on genetic adaptive algorithms. PhD thesis, Uni of Pittsburgh, 1980. P. 21.
7. Kirkpatrick S., Gelatt Jr. C.D., Vecchi M.P. Optimization by simulated annealing // Science. 1983. no. 220. pp. 671–680.
8. Glover F. Future paths for integer programming and links to artificial intelligence // Computers and operations research. 1986. no. 13. pp.533–549.
9. Moscato P. On evolution, search, optimization, genetic algorithms and martial arts: towards memetic algorithms // Caltech concurrent computation program, 1989. Report 826.
10. Dorigo M. Optimization, learning and natural algorithms. PhD thesis, Politecnico di Milano, Italy, 1992. 152 р.
11. Wolpert D.H., Macready W.G. The no free lunch theorems for optimization // IEEE Trans. evol. comp. 1997. no. 1. pp.67–82.
12. Курейчик В.В., Курейчик В.М., Родзин С.И. Теория эволюционных вычислений. М.: Физматлит, 2012. 260 с.
13. Goldberg D.E. Genetic algorithms in search, optimization, and machine learning. USA: Addison–Wesley publishing company, inc., 1989. 432 р.
14. Гладков Л.А., Курейчик В.В., Курейчик В.М., Сорокалетов П.В. Биоинспирированные методы в оптимизации. М.: Физматлит, 2009. 380 с.
15. Курейчик В.М., Родзин С.И. Эволюционные алгоритмы: генетическое программирование (обзор) // Известия РАН. Теория и системы управления. 2002. № 1. С. 127–137.
16. Rodzin S. Smart dispatching and metaheuristic swarm flow algorithm // Jour. of computer and systems sciences international. 2014. Vol. 53. no. 1. pp. 109–115.
17. Eberhart R., Shi Yu., Kennedy J. Swarm intelligence. Morgan Kaufmann, 2010. 512 р.
18. He J., Yao X. Drift analysis and average time complexity of evolutionary algorithms // Artificial intelligence. 2001. Vol. 127. no. 1. pp. 57–85.
19. Jansen T. Fixed budget computations: why, how and what? // Proc. of Dagstuhl seminar on theory of evolutionary algorithms, 2013. pp. 1325–1332.
20. Doerr B., Goldberg L. Adaptive drift analysis // Algorithmica. 2013. Vol. 65, no. 1. pp. 224–250.
21. Rodzin S., Rodzina L. Theory of bionic optimization and its application to evolutionary synthesis of digital devices // Proc. of the 14th IEEE east-west design & test symposium (EWDTS'14), 2014. pp. 147–152.
References
1. Rastrigin L.A. The convergence of the random search method in the extremal control of a many parameter system // Automation and remote control. 1963. no. 24(10). pp. 1337–1342.
2. Nelder J.A., Mead R. A simplex method for function minimization // Computer journal. 1965. no. 7. pp. 308–313.
3. Fogel L., Owens A.J., Walsh M.J. Artificial intelligence through simulated evolution. Wiley, 1966. 452 r.
4. Kernighan B.W., Lin S. An efficient heuristic procedure for partitioning graphs // Bell system technical journal. 1970. no. 49. pp. 291–307.
5. Holland J.H. Adaptation in natural and artificial systems. Uni of Michigan press, 1975. P. 45.
6. Smith S.F. A Learning system based on genetic adaptive algorithms. PhD thesis, Uni of Pittsburgh, 1980. P. 21.
7. Kirkpatrick S., Gelatt Jr. C.D., Vecchi M.P. Optimization by simulated annealing // Science. 1983. no. 220. pp. 671–680.
8. Glover F. Future paths for integer programming and links to artificial intelligence // Computers and operations research. 1986. no. 13. pp.533–549.
9. Moscato P. On evolution, search, optimization, genetic algorithms and martial arts: towards memetic algorithms // Caltech concurrent computation program, 1989. Report 826.
10. Dorigo M. Optimization, learning and natural algorithms. PhD thesis, Politecnico di Milano, Italy, 1992. 152 r.
11. Wolpert D.H., Macready W.G. The no free lunch theorems for optimization // IEEE Trans. evol. comp. 1997. no. 1. pp.67–82.
12. Kureichik V.V., Kureichik V.M., Rodzin S.I. Teoriya evolyutsionnykh vychislenii. M.: Fizmatlit, 2012. 260 s.
13. Goldberg D.E. Genetic algorithms in search, optimization, and machine learning. USA: Addison–Wesley publishing company, inc., 1989. 432 r.
14. Gladkov L.A., Kureichik V.V., Kureichik V.M., Sorokaletov P.V. Bioinspirirovannye metody v optimizatsii. M.: Fizmatlit, 2009. 380 s.
15. Kureichik V.M., Rodzin S.I. Evolyutsionnye algoritmy: geneticheskoe programmirovanie (obzor) // Izvestiya RAN. Teoriya i sistemy upravleniya. 2002. № 1. S. 127–137.
16. Rodzin S. Smart dispatching and metaheuristic swarm flow algorithm // Jour. of computer and systems sciences international. 2014. Vol. 53. no. 1. pp. 109–115.
17. Eberhart R., Shi Yu., Kennedy J. Swarm intelligence. Morgan Kaufmann, 2010. 512 r.
18. He J., Yao X. Drift analysis and average time complexity of evolutionary algorithms // Artificial intelligence. 2001. Vol. 127. no. 1. pp. 57–85.
19. Jansen T. Fixed budget computations: why, how and what? // Proc. of Dagstuhl seminar on theory of evolutionary algorithms, 2013. pp. 1325–1332.
20. Doerr B., Goldberg L. Adaptive drift analysis // Algorithmica. 2013. Vol. 65, no. 1. pp. 224–250.
21. Rodzin S., Rodzina L. Theory of bionic optimization and its application to evolutionary synthesis of digital devices // Proc. of the 14th IEEE east-west design & test symposium (EWDTS'14), 2014. pp. 147–152.
Ссылка на эту статью
Просто выделите и скопируйте ссылку на эту статью в буфер обмена. Вы можете также
попробовать найти похожие
статьи
|
|
