Биоинспирированные алгоритмы

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Биоинспирированные алгоритмы — алгоритмы, область исследования которых свободно объединяет подразделы, относящиеся к темам связности, социального поведения и возникновения[1]. Они часто тесно сопряжены с областью искусственного интеллекта, поскольку их занятия могут быть связаны с машинным обучением. Они опираются в основном на области биологии, информатики и математики. Если говорить кратко, использование компьютеров для моделирования живых явлений и одновременное изучение жизни для улучшения использования компьютеров.

История[править | править код]

Первые работы по симуляции эволюции были проведены в 1954 году Нильсом Баричелли на компьютере, установленном в Институте перспективных исследований Принстонского университета.[2][3] Его работа, опубликованная в том же году, привлекла широкое внимание общественности. С 1957 года,[4] австралийский генетик Алекс Фразер опубликовал серию работ по симуляции искусственного отбора среди организмов с множественным контролем измеримых характеристик. Положенное начало позволило компьютерной симуляции эволюционных процессов и методам, описанным в книгах Фразера и Барнелла(1970)[5] и Кросби (1973)[6], с 1960-х годов стать более распространенным видом деятельности среди биологов. Симуляции Фразера включали все важнейшие элементы современных генетических алгоритмов. Вдобавок к этому, Ганс-Иоахим Бремерманн в 1960-х опубликовал серию работ, которые также принимали подход использования популяции решений, подвергаемой рекомбинации, мутации и отбору, в проблемах оптимизации. Исследования Бремерманна также включали элементы современных генетических алгоритмов.[7] Среди прочих пионеров следует отметить Ричарда Фридберга, Джорджа Фридмана и Майкла Конрада. Множество ранних работ были переизданы Давидом Б. Фогелем (1998).[8]

Хотя Баричелли в своей работе 1963 года симулировал способности машины играть в простую игру,[9] искусственная эволюция стала общепризнанным методом оптимизации после работы Инго Рехенберга и Ханса-Пауля Швефеля в 1960-х и начале 1970-х годов двадцатого века — группа Рехенсберга смогла решить сложные инженерные проблемы согласно стратегиям эволюции.[10][11][12][13] Другим подходом была техника эволюционного программирования Лоренса Дж. Фогеля, которая была предложена для создания искусственного интеллекта. Эволюционное программирование, первоначально использовавшее конечные автоматы для предсказывания обстоятельств, и использовавшее разнообразие и отбор для оптимизации логики предсказания. Генетические алгоритмы стали особенно популярны благодаря работе Джона Холланда в начале 70-х годов и его книге «Адаптация в естественных и искусственных системах» (1975)[14]. Его исследование основывалось на экспериментах с клеточными автоматами, проводившимися Холландом и на его трудах написанных в университете Мичигана. Холланд ввел формализованный подход для предсказывания качества следующего поколения, известный как Теорема схем. Исследования в области генетических алгоритмов оставались в основном теоретическими до середины 80-х годов, когда была, наконец, проведена Первая международная конференция по генетическим алгоритмам в Питтсбурге, Пенсильвания (США).

С ростом исследовательского интереса существенно выросла и вычислительная мощь настольных компьютеров, это позволило использовать новую вычислительную технику на практике. В конце 80-х, компания General Electric начала продажу первого в мире продукта, работавшего с использованием генетического алгоритма. Им стал набор промышленных вычислительных средств. В 1989, другая компания Axcelis, Inc. выпустила Evolver — первый в мире коммерческий продукт на генетическом алгоритме для настольных компьютеров. Журналист The New York Times в технологической сфере Джон Маркофф писал[15] об Evolver в 1990 году.

Описание алгоритмов[править | править код]

  1. Одним из биоинспирированных подходов является метод роевого интеллекта включающий в себя муравьиные алгоритмы, пчелиные алгоритмы, метод роя частиц, алгоритм капель воды и др. Роевой интеллект описывает коллективное поведение децентрализованной самоорганизующейся системы, которая состоит из множества агентов, локально взаимодействующих между собой и с окружающей средой. Агенты обычно довольно просты, но, локально взаимодействуя, вместе создают, так называемый, роевой интеллект.
  2. Пчелиный алгоритм − это оптимизационный алгоритм, в основе которого лежит поведение пчёл в живой природе. Применительно к задаче оптимизации в пчелином алгоритме каждое решение представляется в виде пчелы, которая знает (хранит) расположение (координаты или параметры многомерной функции) какого-то участка.
  3. Алгоритм пастушьей собаки[16] — предлагает решение проблемы выпаса. С помощью набора простых эвристик пастух может пасти автономных, взаимодействующих между собой агентов в направлении к пункту назначения. Эвристика пастуха основана на адаптивном переключении между сбором агентов, когда они слишком рассредоточены, и их вождением, как только они агрегируют. Эти правила действуют для уменьшения вероятности того, что группа распадается, и позволяют пастуху вести группу в направлении целевого местоположения. Движение пастуха из стороны в сторону также является следствием этих правил, в отличие от других моделей, где такое поведение было жестко закодировано в правилах движения управляющего объекта для повышения эффективности работы[17][18][19].

См. также[править | править код]

Примечания[править | править код]

  1. ↑ Котенко И. В., Шоров А. В., Нестерук Ф. Г. «Анализ биоинспирированных подходов для защиты компьютерных систем и сетей» // М.: Труды СПИИРАН. 2011. № 3 (18). С. 19-73
  2. ↑ Barricelli, Nils Aall  (англ.) (рус.. Esempi numerici di processi di evoluzione (итал.) // Methodos. — 1954. — P. 45—68.
  3. ↑ Barricelli, Nils Aall  (англ.) (рус.. Symbiogenetic evolution processes realized by artificial methods (англ.) // Methodos : journal. — 1957. — P. 143—182.
  4. ↑ Fraser, Alex  (англ.) (рус.. Simulation of genetic systems by automatic digital computers. I. Introduction (англ.) // Aust. J. Biol. Sci. : journal. — 1957. — Vol. 10. — P. 484—491.
  5. ↑ Fraser, Alex  (англ.) (рус.; Donald Burnell. Computer Models in Genetics (англ.). — New York: McGraw-Hill Education, 1970. — ISBN 0-07-021904-4.
  6. ↑ Crosby, Jack L. Computer Simulation in Genetics (англ.). — London: John Wiley & Sons, 1973. — ISBN 0-471-18880-8.
  7. ↑ 02.27.96 — UC Berkeley’s Hans Bremermann, professor emeritus and pioneer in mathematical biology, has died at 69. Дата обращения: 22 ноября 2017. Архивировано 23 марта 2012 года.
  8. ↑ Fogel, David B. (editor). Evolutionary Computation: The Fossil Record (англ.). — New York: Institute of Electrical and Electronics Engineers, 1998. — ISBN 0-7803-3481-7.
  9. ↑ Barricelli, Nils Aall. Numerical testing of evolution theories. Part II. Preliminary tests of performance, symbiogenesis and terrestrial life (англ.) // Acta Biotheoretica  (англ.) (рус. : journal. — 1963. — No. 16. — P. 99—126.
  10. ↑ Rechenberg, Ingo. Evolutionsstrategie (нем.). — Stuttgart: Holzmann-Froboog, 1973. — ISBN 3-7728-0373-3.
  11. ↑ Schwefel, Hans-Paul. Numerische Optimierung von Computer-Modellen (PhD thesis) (нем.). — 1974.
  12. ↑ Schwefel, Hans-Paul. Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie : mit einer vergleichenden Einführung in die Hill-Climbing- und Zufallsstrategie (нем.). — Basel; Stuttgart: Birkhäuser  (англ.) (рус., 1977. — ISBN 3-7643-0876-1.
  13. ↑ Schwefel, Hans-Paul. Numerical optimization of computer models (Translation of 1977 Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie (англ.). — Chichester ; New York: Wiley, 1981. — ISBN 0-471-09988-0.
  14. ↑ J. H. Holland. Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor, 1975.
  15. ↑ Markoff, John (1990-08-29). "What's the Best Answer? It's Survival of the Fittest". New York Times. Архивировано 2 декабря 2010. Дата обращения: 9 августа 2009. {{cite news}}: Проверьте значение даты: |year= / |date= mismatch (справка)
  16. ↑ Евдокимов И. В., Кулаков Е. Д. Применение метода наискорейшего спуска в одном биоинспирированном алгоритме // Приборы и системы. Управление, контроль, диагностика. 2017. № 8. С. 10-13
  17. ↑ Lien J, Bayazit OB, Sowell RT, Rodriguez S, Amato AM. Shepherding behaviors // In Proc. IEEE Int. Conf. on Robotics and Automation. — 2004. — pp. 4159-4164
  18. ↑ Bennett B, Trafankowski M. 2012 A Comparative investigation of herding algorithms. In Proc. Symp. on Understanding and Modelling Collective Phenomena // UMoCoP, Birmingham, UK. — 2-6 July 2012. — pp. 33-38.
  19. ↑ Lien JM, Pratt E. 2009 Interactive planning for shepherd motion // In Proc. AAAI Spring Symp., Palo, Alto, CA. — 23-25 March 2009. — pp. 95-102. -Menlo Park, CA: AAAI Press.
Источник — https://ru.wikipedia.org/w/index.php?title=Биоинспирированные_алгоритмы&oldid=130644261