Статья

Название статьи БИОМЕМЕТИКА − ИНТЕГРАЦИЯ МЕТОДОВ МАШИННОГО ОБУЧЕНИЯ И ЭВОЛЮЦИОННЫХ ВЫЧИСЛЕНИЙ
Автор С.И. Родзин
Рубрика РАЗДЕЛ I. ЭВОЛЮЦИОННОЕ МОДЕЛИРОВАНИЕ, ГЕНЕТИЧЕСКИЕ И БИОНИЧЕСКИЕ АЛГОРИТМЫ
Месяц, год 07, 2014
Индекс УДК 004.81
DOI
Аннотация Биомеметика – активно развивающаяся область эволюционных вычислений и методов оптимизации. Мем – это единица культурной информации, которая может быть передана от человека к человеку путём имитации или обучения. В биомеметике концепции из эволюционной теории (популяционной генетики) переносятся на человеческую культуру. Описываются метрические свойства мемов: распространение, живучесть, энтропия, влияние. С помощью метода анализа иерархий получена оценка приоритета каждого метрического свойства. Разработан алгоритм биомететики, построена его синтаксическая модель. Основными компонентами алгоритма биомеметики являются локальный поиск, кооперация, соревнование, критерий окончания поиска. Интеграция эволюционного алгоритма с машинным обучением заключается в том, что эволюционный алгоритм включает процедуру индивидуального обучения особей с использованием информации о структуре пространства возможных решений. Алгоритм биомеметики иллюстрируется на примере задачи составления расписания: задано множество требований и множество объектов на которых требования должны обслуживаться в соответствии с некоторым порядком, необходимо построить расписание, удовлетворяющее данным ограничениям. Приводятся результаты экспериментов. Качество найденных решений лучше, по сравнению с известными генетическими алгоритмами.

Скачать в PDF

Ключевые слова Эволюционные вычисления; биомеметика; задача расписания.
Библиографический список 1. Дарвин Ч. Происхождение видов путем естественного отбора или сохранение благоприятных рас в борьбе за жизнь. – СПб.: Наука, 1991. – 540 c.
2. Докинз Р. Эгоистичный ген. – М.: Мир, 1993. – http://modernlib.ru/books/dokinz_richard/.
3. Родзин С. . Метрика и алгоритмы меметики // Вестник РГУПС. – 2013. – № 4 (52). – С. 59-67.
4. Саати . Принятие решений. Метод анализа иерархий. – М.: Радио и связь, 1993. – 278 c.
5. Moscato P. Memetic algorithms // Handbook of Applied Optimization. – 2002. – P. 157-167.
6. Курейчик В.В., Курейчик В.М., Родзин С. . Теория эволюционных вычислений. – М.: Физматлит, 2012. – 260 c.
7. Reynolds R.G. An Introduction to cultural algorithms // Proc. of the third annual conf. on Evolutionary Programming. – 1994. – P. 131-139.
8. Merz P. Fitness landscapes, memetic algorithms and greedy operators for graph bi-partitioning // Evolutionary Computation. – 2000. – № 8. – P. 61-91.
9. Costa D. Embedding of a sequential procedure within an evolutionary algorithm for coloring problems in graphs // Journal of heuristics. – 1995. – № 1. – P. 105-112.
10. Beasley J. A genetic algorithm for the set covering problem // European journal of operational research. – 1996. – № 2 (94). – P. 393-404.
11. Beasley J. A genetic algorithm for the multidimensional knapsack problem // Journal of heuristics. – 1998. – № 4. – P. 63-86.
12. Merz P. Greedy and local search heuristics for the unconstrained binary quadratic programming problem // Journal of heuristics. – 2002. – № 2. – P. 197-213.
13. Krasnogor N., Smith J. A memetic algorithm with selfadaptive local search: TSP as a case study // Proc. of the Genetic and Evolutionary Computation Conference (GECCO-2000). Las Vegas, USA: Morgan Kaufmann. – P. 987-994.
14. Kureichik V.V., Kravchenko Y.A. Bioinspired algorithm applied to solve the travelling sales-man problem // World Applied Sciences Journal. – 2013. – Vol. 22, № 12. – P. 1789-1797.
15. Topchy A., Lebedko ., Miagkikh V. Fast learning in multilayered networks by means of hybrid evolutionary and gradient algorithms // Proc. of int. conf. on evolutionary computation and its applications. – 1996. – P. 390-398.
16. Areibi S. An integrated genetic algorithm with dynamic hill climbing for VLSI circuit partitioning // Proc. of int. conf. on DM&EA. – 2000. – P. 97-102.
17. Kureichik V.M., Rodzin S.I. Evolutionary algorithms: genetic programming // Journal of Computer and Systems Sciences International. – 2002. – Vol. 41, № 1. – С. 123-132.
18. Бартенев А.С. Обзор основных вопросов автоматизированного составления расписания занятий в вузе // Современные научные исследования и инновации. – 2011. – № 5 [Электронный ресурс]. URL: http://web.snauka.ru/issues/2011/09/2576 (дата обращения: 20.02.2014).
19. Qu R. et al. A survey of search methodologies and automated system development for examination timetabling // Journal of scheduling. – 2009. – № 12. – P. 55-89.

Comments are closed.