Применение генетических алгоритмов

      В 1996 году московская компания "Тора-Центр" начинает беспрецедентную акцию - продажу  в России лицензионного пакета моделирования  нейронных сетей BrainMaker производства California Scientific Software. Пакет предназначался для моделирования многослойных нейронных сетей с полными последовательными связями, обучаемыми по методу обратного распространения ошибки (error backpropagation), оказался прост в использовании и предоставлял много возможностей по изменению топологии многослойной сети и алгоритма обучения, хотя и был несколько сложен для первого восприятия. В пакете не было предусмотрено защиты от копирования, он размещался на стандартной 3,5-дюймовой дискете. При этом разработчиком было особо оговорено, что BrainMaker ориентирован в первую очередь на решение финансовых задач, и основными его потребителями должны стать банки и крупные финансовые компании - сектор рынка, где в то время были сосредоточены основные отечественные финансовые ресурсы. Расчет оказался верным - благодаря мощной рекламной поддержке нейропакет BrainMaker приобрел в России небывалую популярность; спустя некоторое время он даже появился на пиратских компакт-дисках.

      В тот период появились и другие нейропакеты, например, AI Trilogy от Ward Systems Group и в продажу поступил нейрокомпьютерный ускоритель CNAPS компании Adaptive Solutions, представляющий собой аппаратный ускоритель, построенный на базе одного или нескольких нейрочипов того же производителя. По оценкам, для некоторых задач он может дать выигрыш в производительности до 1000 раз по сравнению с самым передовым на тот момент компьютером с процессором Pentium. Выпускался CNAPS до 1997-1998 годов, после чего был снят с производства, скорее всего, по причине нерентабельности.

      Слово "нейро" становится в России модным - почти каждый уважающий себя банк считает долгом купить лицензионный нейропакет и поставить красивую белую коробку на полку[21]. К сожалению, политика компании "Тора" не предусматривала дальнейшего информационного и методического сопровождения своего детища, а консультации по разработке нейросетевых алгоритмов с использованием этого нейропакета пропагандировались, в основном, на бумаге. Поэтому большое количество купленных нейропакетов так и осталось пылиться на полках. Несмотря на это и, невзирая на то, что отдельные пользователи восприняли нейропакет как "средство от всех бед", который сам по себе может решить любую задачу, а бездумное использование нейропакета привело к определенной дискретизации нейрокомпьютинга, проведенная акция стала громадным шагом на пути нейрокомпьютеризации страны, ибо массовый разработчик узнал, что существует новый класс алгоритмов под названием "нейронные сети" и что с их помощью можно эффективно решать различные задачи.

      Судьба  же аппаратного нейрокомпьютерного ускорителя CNAPS более печальна. Мощный нейроускоритель был нужен для  решения только суперзадач, которых  не так уж и много, а для решения  подавляющего большинства задач  достаточно ПК и пакета моделирования нейронных сетей, того же BrainMaker, например. Поэтому нейроускоритель оказался просто невостребован рынком, к тому же его цена в несколько тыс. долл. и необходимость освоения специфичного программного обеспечения отпугивала потенциальных потребителей[15;319]. Фактически вопрос был поставлен ребром - "а нужен ли нейроускоритель для решения обычных задач", и на него был получен отрицательный ответ. Количество проданных экземпляров нейроускорителя можно было пересчитать по пальцам. Правда, компания "ОГО", занимавшаяся зерновыми поставками, активно доказывала, как она эффективно использует нейроускоритель для решения своих задач, но, по всей видимости, это была в основном рекламная акция. Постепенно интерес к CNAPS затих. Когда позднее в Siemens попытались повторить этот путь и внедрить на российский рынок свой нейрокомпьютер Synaps-1 стоимостью 400 тыс. долл., то натолкнулась на ту же самую проблему - нейрокомпьютер оказался невостребованным.

      Это, конечно, не означает, что аппаратные нейроускорители и нейрокомпьютеры не нужны - просто они используются узким кругом коллективов, занимающихся решением именно суперзадач, а массовому пользователю они действительно ни к чему[10;225]. Для справки, в России ряд научных коллективов имеют в своем распоряжении и нейрокомпьютеры и супермашины для моделирования нейронных сетей, но их мало. 

 

     Выводы 

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

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

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

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

     Следует помнить, что применение ГА полезно  лишь в тех случаях, когда для  данной задачи нет подходящего специального алгоритма решения.

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

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

     Однако  нередки случаи, когда ГА работает не так эффективно, как ожидалось.

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

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

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

 

     Практическая  часть 

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

    Принцип работы программы

     Сразу при запуске программы еще  перед прорисовкой окна выполняется  процедура FormCreate в которой производится инициализация внутренних переменных, инициализация интерфейса и прорисовка изображения. Прорисовка изображения проходит в процедуре CreateImage в два этапа: сначала необходимо рассчитать образ на экране при помощи одной из трёх целевых функций; и только после этого производится прорисовка посредством пикселей канвы объекта.

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

     После выбора параметров нажатие на кнопку «Пуск алгоритма» приведет к запуску основной процедуры программы btnStartClick. В первые моменты выполнения программы происходит считывание установленных параметров в переменные и поля объекта GA1, который является прототипом класса TgeneticAlgorithm, тем самым этому объекту задаются основные параметры для дальнейшей работы методов объекта. Затем вызывается метод Init объекта GA1 в который производит начальную инициализацию особей, используемых в генетическом алгоритме, случайными значениями. Переменные xCnt и xMaxCnt предназначены для отслеживания ситуации останова алгоритма. Переменная xOldS содержит значение приспособленности предыдущей, лучшей особи популяции. Затем запускается основной цикл программы и в нем, после проверок возможных ситуаций останова алгоритма, вызывается процедура OneEpoch объекта frmMain, в которой вызывается метод OneEpoch объекта GA1. Вызов данного метода приводит к выполнению одного шага генетического алгоритма. При этом производится вычисление приспособленности всех особей из популяции, а на основании этих данных формируется новая популяция. Далее происходит сравнивание приспособленностей: лучшего индивида текущей и предыдущей популяций и в случае малого различия наращивается переменная xCnt, а в противном случае – обнуляется. Затем обновляется переменная xOldS и выводятся основные значения лучшей особи текущей популяции.

    Листинг программы

 

    unit fmMain; 

    interface 

    uses

      Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,

      ExtCtrls, StdCtrls, genetic, math; 

    type 

      TTargetFunction = function(X1,X2 : double):double; 

      TfrmMain = class(TForm)

        Panel1: TPanel;

        Panel2: TPanel;

        GroupBox1: TGroupBox;

        GA1: TGeneticAlgorithm;

        Label1: TLabel;

        edtChromosomeCount: TEdit;

        Label2: TLabel;

        cbxGeneDegree: TComboBox;

        Label3: TLabel;

        edtCrossoverP: TEdit;

        Label4: TLabel;

        edtMutationP: TEdit;

        Label5: TLabel;