Рус Eng Cn Перевести страницу на:  
Nota Bene. Books, journals, publishing technologies.
Please select your language to translate the article


You can just close the window to don't translate ☒
Библиотека
 ваш профиль
Creative Commons License CC-BY-NC Статья опубликована с лицензией Creative Commons Attribution-NonCommercial 4.0 International License (CC BY-NC 4.0) – Лицензия «С указанием авторства – Некоммерческая».
Вернуться к содержанию

Программные системы и вычислительные методы
Правильная ссылка на статью:

Родзин С.И., Курейчик В.В. Состояние, проблемы и перспективы развития биоэвристик

Аннотация: Предметом обзора является современное состояние, проблемные вопросы и перспективные области исследований биоэвристик для решения оптимизационных задач. Биоэвристики – это математические преобразования, трансформирующие входной поток информации в выходной и основанные на правилах имитации механизмов эволюции, природных аналогий, на статистическом подходе к исследованию ситуаций и итерационном приближении к искомому решению. В настоящее время биоэвристики превратились в важный инструмент поиска близких к оптимальным решений задач, которые до этого считались неразрешимыми. Методологической и теоретической основой обзорного исследования являлись методы оптимизации и поддержки принятия оптимальных решений, искусственный интеллект, теория эволюционных вычислений. В статье анализируются фундаментальные результаты, полученные в области биоэвристических алгоритмов оптимизации: теорема Холланда и NFL-теорема. Устанавливаются закономерности и структура биоэвристик, особенности кодирования решений, базовый цикл биоэвристических алгоритмов. Рассматривается перспективное направление в анализе времени работы когнитивных биоэвристических алгоритмов - анализ дрейфа.

Ключевые слова:

когнитивный биоинспирированный алгоритм, метаэвристика, оптимизация, эволюционные вычисления, эволюционный оператор, NFL-теорема, анализ дрейфа, функция приспособленности, моделирование, программирование

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:

evolution operator, evolutionary computation, optimization, metaheuristics, cognitive bioinspired algorithm, NFL-theorem, drift analysis, fitness function, programming, modeling


Эта статья может быть бесплатно загружена в формате PDF для чтения. Обращаем ваше внимание на необходимость соблюдения авторских прав, указания библиографической ссылки на статью при цитировании.

Скачать статью

Библиография
1. 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.
2. Jansen T. Fixed budget computations: why, how and what? // Proc. of Dagstuhl seminar on theory of evolutionary algorithms, 2013. pp. 1325–1332.
3. He J., Yao X. Drift analysis and average time complexity of evolutionary algorithms // Artificial intelligence. 2001. Vol. 127. no. 1. pp. 57–85.
4. Eberhart R., Shi Yu., Kennedy J. Swarm intelligence. Morgan Kaufmann, 2010. 512 р.
5. Rodzin S. Smart dispatching and metaheuristic swarm flow algorithm // Jour. of computer and systems sciences international. 2014. Vol. 53. no. 1. pp. 109–115.
6. Wolpert D.H., Macready W.G. The no free lunch theorems for optimization // IEEE Trans. evol. comp. 1997. no. 1. pp.67–82.
7. Курейчик В.В., Курейчик В.М., Родзин С.И. Теория эволюционных вычислений. М.: Физматлит, 2012. 260 с.
8. Goldberg D.E. Genetic algorithms in search, optimization, and machine learning. USA: Addison–Wesley publishing company, inc., 1989. 432 р.
9. Гладков Л.А., Курейчик В.В., Курейчик В.М., Сорокалетов П.В. Биоинспирированные методы в оптимизации. М.: Физматлит, 2009. 380 с.
10. Курейчик В.М., Родзин С.И. Эволюционные алгоритмы: генетическое программирование (обзор) // Известия РАН. Теория и системы управления. 2002. № 1. С. 127–137.
11. Dorigo M. Optimization, learning and natural algorithms. PhD thesis, Politecnico di Milano, Italy, 1992. 152 р.
12. Moscato P. On evolution, search, optimization, genetic algorithms and martial arts: towards memetic algorithms // Caltech concurrent computation program, 1989. Report 826.
13. Glover F. Future paths for integer programming and links to artificial intelligence // Computers and operations research. 1986. no. 13. pp.533–549.
14. Holland J.H. Adaptation in natural and artificial systems. Uni of Michigan press, 1975. P. 45.
15. Smith S.F. A Learning system based on genetic adaptive algorithms. PhD thesis, Uni of Pittsburgh, 1980. P. 21.
16. Kirkpatrick S., Gelatt Jr. C.D., Vecchi M.P. Optimization by simulated annealing // Science. 1983. no. 220. pp. 671–680.
17. Nelder J.A., Mead R. A simplex method for function minimization // Computer journal. 1965. no. 7. pp. 308–313.
18. Kernighan B.W., Lin S. An efficient heuristic procedure for partitioning graphs // Bell system technical journal. 1970. no. 49. pp. 291–307.
19. Fogel L., Owens A.J., Walsh M.J. Artificial intelligence through simulated evolution. Wiley, 1966. 452 р.
20. 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.
21. Doerr B., Goldberg L. Adaptive drift analysis // Algorithmica. 2013. Vol. 65, no. 1. pp. 224–250.
References
1. 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.
2. Jansen T. Fixed budget computations: why, how and what? // Proc. of Dagstuhl seminar on theory of evolutionary algorithms, 2013. pp. 1325–1332.
3. He J., Yao X. Drift analysis and average time complexity of evolutionary algorithms // Artificial intelligence. 2001. Vol. 127. no. 1. pp. 57–85.
4. Eberhart R., Shi Yu., Kennedy J. Swarm intelligence. Morgan Kaufmann, 2010. 512 r.
5. Rodzin S. Smart dispatching and metaheuristic swarm flow algorithm // Jour. of computer and systems sciences international. 2014. Vol. 53. no. 1. pp. 109–115.
6. Wolpert D.H., Macready W.G. The no free lunch theorems for optimization // IEEE Trans. evol. comp. 1997. no. 1. pp.67–82.
7. Kureychik V.V., Kureychik V.M., Rodzin S.I. Teoriya evolyutsionnykh vychisleniy. M.: Fizmatlit, 2012. 260 s.
8. Goldberg D.E. Genetic algorithms in search, optimization, and machine learning. USA: Addison–Wesley publishing company, inc., 1989. 432 r.
9. Gladkov L.A., Kureychik V.V., Kureychik V.M., Sorokaletov P.V. Bioinspirirovannye metody v optimizatsii. M.: Fizmatlit, 2009. 380 s.
10. Kureychik V.M., Rodzin S.I. Evolyutsionnye algoritmy: geneticheskoe programmirovanie (obzor) // Izvestiya RAN. Teoriya i sistemy upravleniya. 2002. № 1. S. 127–137.
11. Dorigo M. Optimization, learning and natural algorithms. PhD thesis, Politecnico di Milano, Italy, 1992. 152 r.
12. Moscato P. On evolution, search, optimization, genetic algorithms and martial arts: towards memetic algorithms // Caltech concurrent computation program, 1989. Report 826.
13. Glover F. Future paths for integer programming and links to artificial intelligence // Computers and operations research. 1986. no. 13. pp.533–549.
14. Holland J.H. Adaptation in natural and artificial systems. Uni of Michigan press, 1975. P. 45.
15. Smith S.F. A Learning system based on genetic adaptive algorithms. PhD thesis, Uni of Pittsburgh, 1980. P. 21.
16. Kirkpatrick S., Gelatt Jr. C.D., Vecchi M.P. Optimization by simulated annealing // Science. 1983. no. 220. pp. 671–680.
17. Nelder J.A., Mead R. A simplex method for function minimization // Computer journal. 1965. no. 7. pp. 308–313.
18. Kernighan B.W., Lin S. An efficient heuristic procedure for partitioning graphs // Bell system technical journal. 1970. no. 49. pp. 291–307.
19. Fogel L., Owens A.J., Walsh M.J. Artificial intelligence through simulated evolution. Wiley, 1966. 452 r.
20. 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.
21. Doerr B., Goldberg L. Adaptive drift analysis // Algorithmica. 2013. Vol. 65, no. 1. pp. 224–250.
Издательство
 
Авторам
 
Услуги
 
Разное
 
Наши сайты

© 1998 – 2024 Nota Bene. Publishing Technologies. NB-Media Ltd.