В 1859 году был опубликован труд английского естествоиспытателя Чарльза Дарвина под названием "Происхождение видов путем естественного отбора", который перевернул представления человечества о жизни на земном шаре. Через сто с небольшим лет профессор психологии и компьютерных наук из Университета Мичиган Джон Голланд (Holland), вдохновленный эволюционной теорией великого ученого, совершил прорыв в области проектирования и построения вычислительных систем. Его книга под названием "Адаптация в естественных и искусственных системах", опубликованная в 1975 году, была посвящена новым мощным методам поиска наилучшего решения, которые получили название генетических алгоритмов.

Необходимость использования новых методов оптимизации

С появлением первых компьютеров на них было возложено решение многочисленных сложных финансовых и научных задач. Поначалу в программные продукты зашивались классические математические методы, которые оказались не очень эффективными для применения на финансовых рынках, т.к. для решения задач об определении оптимальной комбинации инвестиций требовались большие временные затраты, исчисляемые в днях и неделях. Поскольку ситуация на рынке ценных бумаг может меняться очень быстро, назрела необходимость разработки новых, более совершенных методов и алгоритмов для решения сложных финансовых задач. Одним из таких методов стали генетические алгоритмы (ГА), позволяющие получить ответ за считанные минуты.

Эволюционная теория как основная идея ГА

Генетические алгоритмы - это современные эффективные методы решения сложных многопараметрических задач оптимизации, которые находят применение во многих областях деятельности человека. Принцип работы генетических алгоритмов удобно иллюстрировать, проводя аналогии с эволюционной теорией Чарльза Дарвина. Ведь эволюция является, по сути, длительной оптимизацией биологических видов. Ученые, подметив сходство этого хорошо изученного природного явления с процессом поиска наилучшего ответа, попытались смоделировать его на компьютере и применить в ходе решения сложных задач. Тогда были получены прекрасные результаты, что явилось отправной точкой проникновения ГА в жизнь человека.

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

Как же действует компьютер? В начале генерируется популяция исходных решений. Далее с помощью обозначенных операций (скрещивания и мутации) на свет производится новое поколение. Определенный процент этих решений, в меньшей степени улучшающих целевую функцию, отсеивается, а остальные продолжают участвовать в эволюционном процессе. Остановив его в некоторый момент, можно получить наилучшее или близкое к нему решение. Так выглядит основная мысль ГА, изложенная в свое время Джоном Голландом. Нужно отметить, что эффективность генетических алгоритмов сильно зависит от таких деталей, как метод кодирования решений, определение операций и критериев останова вычислительного процесса. Сейчас существует множество способов реализации ГА, но в каждом из них заложена описанная выше идея (различные модели смотри на сайте gai.narod.ru).

Области применения генетических алгоритмов

Как я уже говорил, генетические алгоритмы были созданы и широко используются для того, чтобы быстро решать сложнейшие оптимизационные задачи в бизнесе и финансах. Но этим сфера их применения не ограничивается. Многочисленные варианты ГА употребляются при исследовании разнообразных научных и технических проблем. К примеру, инженеры компании General Electric с успехом используют генетические алгоритмы для создания реактивных двигателей, а военно-морские силы США - для повышения эффективности обслуживания самолетов авианосцами. ГА используются также для создания вычислительных структур, применяются при проектировании нейронных сетей и при управлении роботами. Кроме этого, они приносят неоценимую помощь при моделировании процессов развития в биологических, социальных и других системах.

Исходя из сказанного, генетические алгоритмы совсем не являются просто умозрительной теорией, а широко используются на практике. Об этом говорят и многочисленные программные комплексы, которые доступны не только юридическим лицам, но и обычным пользователям. Одним из таких приложений является программный комплекс GeneHunter, разработанный российской компанией "НейроПроект", и программный пакет Auto2Fit от CPC-X Software, обновившийся 20 мая этого года до третьей версии. Рассмотрим их поближе.

GeneHunter 2.0

Мощный программный комплекс под названием GeneHunter предназначен для решения оптимизационных задач любой сложности с помощью генетических алгоритмов и состоит из следующих трех частей: надстройки для MS Excel, динамической библиотеки функций GALIB и примеров задач, решенных на пакете.

Исходные данные вводятся в GeneHunter посредством рабочего листа Excel. В диалоговом окне программы следует указать ячейки, использующиеся при решении, задать список ограничений, которые должны выполняться, и определить целевую функцию, направив ее на максимум, на минимум или на указанное значение. Для написания целевой функции можно также использовать макросы Excel или функции Excel Visual Basic. В целом, работа с GeneHunter в Excel не многим отличается от решения задач при помощи надстройки "Поиск решения" (Solver), о которой я рассказывал в "КВ" №21/2005.

Чтобы каждый пользователь мог применить ГА в своих собственных приложениях, в пакет GeneHunter включена динамическая библиотека функций GALIB.DLL. В нее входят функции создания популяции, определения параметров эволюции (вероятности скрещивания, мутации, разнообразия) и значений целевой функции особей, а также следующие генетические операторы: оператор скрещивания, мутации, разнообразия и вымирания.

В GeneHunter присутствует целый ряд обучающих примеров задач с решениями, что, несомненно, удобно для людей, ранее не сталкивавшихся с подобными программами. Среди примеров можно найти такие распространенные проблемы, как анализ портфеля акций, оптимизация инвестиционного портфеля, задача коммивояжера, создание оптимального графика работ и другое. Кроме этого, в пакет включены исходники программ, написанных на Visual Basic, Delphi и Visual C++ и использующих библиотеку GALIB.DLL. Полную информацию о программных ограничениях и о GeneHunter можно посмотреть на странице www.neuroproject.ru.

Auto2Fit 3

Данный программный комплекс представляет собой мощный и в то же время легкий в использовании инструмент, предназначенный для решения оптимизационных задач и проведения сложных инженерных расчетов. Программа Auto2Fit располагает восемью оптимизационными алгоритмами, включая генетические, и их многочисленными модификациями. Если говорить о ГА, то пакет позволяет кодировать решения для большей эффективности, имеет шесть типов операторов скрещивания (кроссинговера) и семь возможных вариантов отбора.

Программа может работать в одном из следующих режимов: быстром и программном. Из дополнительных возможностей Auto2Fit можно отметить удобную навигацию по файлам, реализуемую с помощью дерева каталогов, рабочую область, представленную в виде таблиц Excel, построение 3D-графиков и другое. В комплект также включены многочисленные примеры, в том числе и классические примеры задач оптимизации. Программа обладает не очень большими системными требованиями. Скачать новую версию или найти подробную информацию о продукте можно на страничке www.geocities.com/neuralpower/introduction_af.htm.

Заключение

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

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

Виталий КРАСИЛЬНИКОВ,
[email protected]