Искусственный интелект. Генетические алгоритмы

    Введение.

    Природа поражает своей сложностью и богатством проявлений. Среди примеров можно  назвать сложные социальные системы, иммунные и нейронные системы, сложные  взаимосвязи между видами. Они - всего  лишь некоторые из чудес, ставшие  очевидными при глубоком исследовании природы вокруг нас. Наука - это одна из систем, которая объясняет окружающее и помогает приспособиться к новой  информации, получаемой из внешней  среды. Многое из того, что мы видим  и наблюдаем, можно объяснить  теорией эволюции через наследственность, изменение и отбор.

    На  мировоззрение людей сильно повлияла теория эволюции Чарльза Дарвина, представленная в работе "Происхождение Видов", в 1859 году. Множество областей научного знания многим обязана революции, вызванной теорией эволюции и развития. Но Дарвин, подобно многим современникам, предполагающим, что в основе развития лежит естественный отбор, не мог не ошибаться. Например, он не смог показать механизм наследования, при котором поддерживается изменчивость. Однако Дарвин обнаружил главный механизм развития: отбор в соединении с изменчивостью. Во многих случаях, специфические особенности развития через изменчивость и отбор все еще не бесспорные, однако, основные механизмы объясняют невероятно широкий спектр явлений, наблюдаемые в Природе.  Поэтому не удивительно, что ученые, занимающиеся компьютерными исследованиями, в поисках вдохновения обратились к теории эволюции. Возможность того, что вычислительная система, наделенная простыми механизмами изменчивости и отбора, могла бы функционировать по аналогии с законами эволюции в естественных системах, была очень привлекательной. Эта надежда является причиной появления ряда вычислительных систем, построенных на принципах естественного отбора.  
Итак, в природе постоянно происходит процесс решения задач оптимизации. Задачи оптимизации — наиболее распространенный и важный для практики класс задач. Их приходится решать каждому из нас либо в быту, распределяя свое время между различными делами, либо на работе, добиваясь максимальной скорости работы программы или максимальной доходности компании — в зависимости от должности.    

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

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

     Генетические  Алгоритмы - адаптивные методы поиска, которые в последнее время  часто используются для решения  задач функциональной оптимизации. Они основаны на генетических процессах  биологических организмов: биологические  популяции развиваются в течении нескольких поколений, подчиняясь законам естественного отбора и по принципу "выживает наиболее приспособленный" (survival of the fittest), открытому Чарльзом Дарвином. Подражая этому процессу генетические алгоритмы способны "развивать" решения реальных задач, если те соответствующим образом закодированы. Например, ГА могут использоваться, чтобы проектировать структуры моста, для поиска максимального отношения прочности/веса, или определять наименее расточительное размещение для нарезки форм из ткани. Они могут также использоваться для интерактивного управления процессом, например на химическом заводе, или балансировании загрузки на многопроцессорном компьютере. Вполне реальный пример: израильская компания Schema разработала программный продукт Channeling для оптимизации работы сотовой связи путем выбора оптимальной частоты, на которой будет вестись разговор. В основе этого программного продукта и используются генетические алгоритмы.

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

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

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

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

     Имеются много способов реализации идеи биологической  эволюции в рамках ГА. Традиционным считается ГА, представленный на схеме.

     НАЧАЛО /* генетический алгоритм */

     Создать начальную популяцию

     Оценить приспособленность каждой особи

     останов := FALSE

     ПОКА  НЕ останов ВЫПОЛНЯТЬ

     НАЧАЛО /* создать популяцию нового поколения */

     ПОВТОРИТЬ (размер_популяции/2) РАЗ

     НАЧАЛО /* цикл воспроизводства */

     Выбрать две особи  с высокой приспособленностью из предыдущего поколения для скрещивания

     Скрестить выбранные  особи и получить двух потомков

     Оценить приспособленности  потомков

     Поместить потомков в новое поколение 

     КОНЕЦ

     ЕСЛИ популяция  сошлась ТО останов := TRUE

     КОНЕЦ

     КОНЕЦ

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

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

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

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

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

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

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