Review of software for implementation of bionic algorithms

Abstract

The article discusses bionic algorithms and their types. An overview of software tools for the implementation of bionic algorithms is also presented. An example of one of the bionic methods is demonstrated - the genetic algorithm.

Full Text

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

На сегодняшний день учёные выделяют две группы бионических алгоритмов [1-3]. Первая группа содержит в себе алгоритмы роевого интеллекта (РИ). Это алгоритмы, которые были созданы при помощи коллективного интеллекта или методом анализа поведения группы особей (роя) сообществ животных.

Ко второй группе принадлежат эволюционные вычисления. Это алгоритмы, которые основаны на принципах «выживания сильнейших» (так называемом «естественном отборе»).

• Роевой интеллект. Под термином «рой» чаще всего понимается некоторое сообщество насекомых, объёдинённых какими-либо коллективными действиями (например, рой пчёл, ос, муравьём). Каждая особь роя двигается хаотично, т.е. каждая особь обладает непредсказуемым характером поведения. Простые правила, принятые внутри роя, которые имеют значение только внутри данного сообщества и не могут использоваться единичными особями вне роя послужили базисом для создания коллективного разума. Такое явление получило название «роевый интеллект». Такой способ мышления помогает рою максимально эффективно использовать имеющиеся ресурсы и богатства окружающей его природной среды.

Если алгоритм удовлетворяет следующим принципам, то его можно отнести к интеллектуальным алгоритмам:

• принцип разнообразия: рой хранит все свои ресурсы в нескольких рассредоточенных локациях, а не в одном месте.
• принцип адаптируемости: в случае необходимости, рой может скорректировать своё поведение;
• принцип приближения: рой может выполнять простые вычисления (пространственные и временные);
• принцип стабильности: рой после любого изменения окружающей среды никогда не отклоняться от своей линии поведения;
• принцип качества: рой всегда реагирует на различные факторы качества окружающей среды, такие как безопасность местоположения, качество пищи и тому подобные.

Главными парадигмами роевых алгоритмов являются:

• метод роя частиц;
• муравьиный алгоритм;
• алгоритм искусственного роя пчёл и другие.
  
  • Эволюционные алгоритмы. Данная группа бионических алгоритмов основывается на третьей эволюционной теории Чарльза Дарвина. Данная теория объясняет принцип естественного отбора. Её суть заключается в том, что в любом сообществе при условии ограниченности необходимых жизненно важных ресурсов неизбежно возникновение конкуренции, которая влечет за собой к преобладанию наилучших (более сильных) особей сообщества над худшими (слабыми). Результатом является то, что продолжают функционировать («выживают») наилучшие, то есть наиболее адаптированные особи. Эволюционное развитие такого сообщества методом естественного отбора позволяет поддерживать многообразие видов различных существ в живой природе и их адаптируемость к внешним условиям. Соответственно, эволюционные алгоритмы основываются на процессах и моделях естественной биологической эволюции животного и растительного миров.

Эволюционные алгоритмы распределяют свойства адаптации по средствам итерационного процесса. Этот метод является методом проб и ошибок, но для живых организмов он максимизирует качества особей в популяции, то есть в определенном смысле составляет перспективные наборы этих особей. Перспективными не всегда являются наилучшие варианты. Часто лучшее потомство дают «обыкновенные» особи.

В генетических алгоритмах вариации решения поставленной задачи можно представить с помощью некоторой виртуальной популяции, стремящейся к наилучшему значению фитнесс-функции (целевой функцией), аналогичной выживанию в живой природе.

Процесс повторяется многократно и соответствует смене поколений, то есть популяций особей в окружающем мире. Во многих случаях происходит не только улучшение популяции, но каждой отдельной особи.

На вышеописанных механизмах строятся генетические алгоритмы. Для их реализации наиболее часто используются соответствующие генетические операторы. Основными из них являются: мутация и рекомбинация.

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

Аналогичные рассуждения можно представить и для иммунных алгоритмов.

Бионические алгоритмы редки применяются «в чистом виде». Чаще всего для повышения продуктивности решения задачи и увеличения наглядности процесса решения их совмещают с какими-либо традиционными подходами решения оптимизационных задач (например: локальный поиск).

Бионические методы чаще всего используются для гибридных задач – задач, решение которых включает совокупность нескольких разнообразных и разнотипных подзадач. Например, одни из них могут быть на нахождение локального оптимума, другие – содержат динамические ограничений так далее.

Эволюционных методы базируются на следующих основополагающих парадигмах:

• генетические алгоритмы;
• генетическое программирование;
• эволюционное программирование;
• дифференциальная эволюция.

2. Обзор программных средств реализации бионический алгоритмов. Сделаем обзор различных средств реализации бионических алгоритмов. Рассмотрим несколько самых популярных на сегодняшний день языков программирования: С++, С# и Python.

• Язык С++. C++ – алгоритмический, компилируемый, статически типизированный язык программирования общего назначения. Он основывается на следующих парадигмах программирования: процедурное программирование, объектно- ориентированное программирование, обобщённое программирование. С++ поддерживает обширную стандартную библиотеку, включающую такие возможности как: распространённые контейнеры и алгоритмы, ввод-вывод, регулярные выражения, поддержку многопоточности и многие другие особенности. C++ поддерживает свойства высокоуровневых и низкоуровневых языков программирования.

C++ широко применяется для разработки программного обеспечения. Он является самым универсальным и качественным языком программирования. Существует множество реализаций языка C++, как бесплатных, так и коммерческих. Он используется написания программного обеспечения для различных платформ (например: на платформе x86 – GCC, Visual C++, Intel C++ Compiler, Embarcadero (Borland) C++ Builder и пр.).

• Язык С#. C# – объектно-ориентированный язык программирования семейства языков с C-подобным синтаксисом. Его синтаксис наиболее близок к синтаксису алгоритмических языков программирования C++ и Java. C# поддерживает статическую типизацию, поддерживает полиморфизм, перегрузку операторов и ещё большое количество полезных функции.

Переняв многое от С++, С#, опираясь на практику использования С++, исключил многие проблематичные модели при разработке программных комплексов. Например: C# в отличие от C++ не поддерживает множественное наследование классов, но допускает множественную реализацию интерфейсов.

• Язык Python. Python – высокоуровневый алгоритмический язык программирования общего назначения с динамической строгой типизацией и автоматическим управлением памятью, ориентированный на повышение производительности разработчика, читаемости кода и его качества, а также на обеспечение переносимости написанных на нём программ. Python является полностью объектно- ориентированным, то есть в нем всё является объектами. Синтаксис ядра языка Python минималистичен, за счёт чего на практике редко возникает необходимость обращаться к документации. Python является интерпретируемым языком программирования. Часто он применяется для написания скриптов.

Python является мультипарадигмальным языком программирования, поддерживающим императивное, процедурное, структурное, объектно-ориентированное программирование, метапрограммирование и функциональное программирование. Задачи обобщённого программирования часто решаются за счёт динамической типизации.

Основные архитектурные черты языка – динамическая типизация, автоматическое управление памятью, полная интроспекция, механизм обработки исключений, поддержка многопоточных вычислений с глобальной блокировкой интерпретатора (GIL), высокоуровневые структуры данных. Поддерживается разбиение программ на модули, которые, в свою очередь, могут объединяться в пакеты.

Стандартная библиотека включает большой набор полезных переносимых функций, начиная от функционала для работы с текстом и заканчивая средствами для написания сетевых приложений. Дополнительные возможности могут реализовываться посредством обширного количества сторонних библиотек, а также интеграцией библиотек, написанных на Си или C++.

3. Пример реализации генетического алгоритма на языке программирования Python. Наиболее подходящим инструментом для реализации бионического алгоритма является язык программирования Python. На листинге 1 представлен пример программного кода, реализующий обобщённый генетический алгоритм.

Листинг 1. Реализация генетического алгоритма на языке Pythоn

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

Заключение.

Бионические алгоритмы являются достаточно мощным инструментом современных учёных и практиков. В результате выполнения данного проекта была изучена предметная область использования алгоритмов оптимизации, основанных на принципах живой природы и процессе эволюции: рассмотрены общие принципы, лежащие в основе эволюционных вычислений и методов роевого интеллекта; выполнен обзор и проанализированы основные языки программирования для реализации бионических алгоритмов; программно реализованы бионические алгоритмы с демонстрацией на листинге основной части генетического алгоритма на оптимальном для него языке Python.