Генетические алгоритмы

Искусственный интеллект (ИИ), как раздел технической кибернетики, ведёт свою историю с конца 40-х годов прошлого века.

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

При этом в исследованиях по ИИ всегда выделялись две равнозначные цели.

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

Конструкция таких систем, их принцип действия совершенно не важен.

Делают системы ИИ это так, как человек, или как-то по-другому, значения не имеет. Исследователям в этом абсолютно не интересно. Главное тут обеспечить тот же результат при решении задачи, что получает живой человеческий интеллект.

Вторая цель, обычно её называют бионической, направлена на создание систем ИИ, для объяснения процессов, реально существующих в системах живых существ. И тут главное корректно и достоверно моделировать/имитировать сам процесс, в интересах постижения «механики» этих процессов. Сможем мы с помощью таких систем ИИ решить реальные прикладные задачи не столь важно. Однако существует ряд методов в сфере систем ИИ, которые неплохо решают задачи по достижению этих двух целей.

Один их таких методов - это генетические алгоритмы (ГА).

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

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

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

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

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

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

История создания и активного использования генетических алгоритмов началась с создания нескольких независимых моделей. Так, в 70-ых годах Растригин Л. А. предложил алгоритмы, в которых учитывались идеи бионического поведения особей. Эти идеи развивались Букатовой И. Л. в цикле работ по эволюционному моделированию. Советским и российским математиком Неймарком Ю. И. была предложена методика осуществления поиска глобального экстремума, базирующийся на основе коллектива независимых автоматов, которые моделировали различные процессы развития особей, а также их элиминации. Далее Букатова И.Л. развила эти идеи в цикле работ по эволюционному моделированию. Советский и российский математик Неймарк Ю.И. предложил осуществлять поиск глобального экстремума на основе коллектива независимых автоматов, моделирующих процессы развития и элиминации особей. Немалый вклад в появление и развитие генетических алгоритмов внес американский ученый Лоуренс Дж. Фогель, который представил Конгрессу США доклад на тему эволюционного программирования. В 1964 году немецким ученым Инго Рехенбергом была разработана идея эволюционных стратегий, а в 1965 году опубликована статья «Путь кибернетического решения экспериментальной проблемы». Его идеи были развиты Ханс–Полом Швефелом. Наконец, в 1975 году вышла книга американского ученого Джона Холланда  «Адаптация в естественных и искусственных системах» («Adaptation in Natural and Artificial Systems»), в которой были даны теоретические основы генетических алгоритмов. Несмотря на разницу в подходах, каждый из ученых внес большой вклад, изучив ряд принципов, существующих в природе, и упростив их до такой степени, чтобы их можно было реализовать на компьютере.

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

Генетические алгоритмы работают с популяцией, т.е. совокупностью особей, где каждая особь - возможное решение данной задачи. Происходит оценка приспособленности особи, посредством проверки того, насколько «хорошо» соответствующее ей решение задачи. Если проводить параллель с природой, то это то же самое, что и оценка того, насколько эффективен организм при конкуренции за ресурсы. Наиболее адаптированные особи получают возможность «воспроизводить» потомство с другими особями популяции. Благодаря «перекрестному скрещиванию» появляются новые особи, которые имеют некоторые характеристики, от обоих родителей. Плохо приспособленные особи с меньшей вероятностью смогут воспроизвести потомков, поэтому те признаки, которыми они обладали, будут постепенно пропадать из популяции. Иногда происходят мутации, или спонтанные изменения в генах.

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

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

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

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

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

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

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

Если же пространство поиска достаточно маленькое, то метод полного перебора будет более эффективным, в то время, как ГА не будет являться рациональным методом.

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

Если о пространстве поиска есть какая-то дополнительная информация, методы поиска, определяемые пространством, часто превосходят большинство методов, включая ГА.

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

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

Таким образом, можно сделать следующие выводы:

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

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

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

ГА не единственный метод оптимизации, созданный на принципах моделирования природных процессов в живых организмах.

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

Важное достоинство ГА является то, что они на множестве примеров показали свою высокую эффективность при решении задач, которые весьма плохо решаются классическими методами.