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

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

В качестве метода оптимизации может быть предложен перебор всех возможных вариантов математических моделей на данном множестве признаков и выбор из них оптимального (в заданном смысле) набора. Однако, очевидно, что с возрастанием исходного количества входных признаков возрастает объем вычислений. Так, например, для выбора оптимального набора из 50 исходных признаков потребуется построение 2⁵⁰~10¹⁵ моделей. Даже при мощности современных компьютеров построение такого количества моделей и их анализ является нереальной задачей. Для того, чтобы уменьшить число переборов и, в то же время выйти на решение близкое к оптимальному существует множество различных подходов, более или менее эффективно работающих в каждом отдельном случае. В то же время, согласованность и эффективность работы элементов биологических систем, состоящих из большого числа отдельных блоков, наводит на мысль – можно ли использовать принципы биологической эволюции для оптимизации практически важных для человека систем? В нескольких модификациях подобные идеи возникали у ряда авторов. В 1966 году Л. Фогель, А. Оуэнс, М. Уолш предложили схему эволюции логических автоматов, решающих задачи прогноза. В 1975 г. вышла основополагающая книга Дж. Холланда “Адаптация в естественных и искусственных системах”, в которой был предложен генетический алгоритм, исследованный в дальнейшем учениками и коллегами Дж. Холланда в Мичиганском университете. Примерно в это же время группа немецких ученых (И. Рехенберг, Г.-П. Швефель и др.) начала разработку так называемой эволюционной стратегии. Эти работы заложили основы прикладного эволюционного моделирования или эволюционных алгоритмов.

В общем виде эволюционный алгоритм – это оптимизационный метод, базирующийся на эволюции популяции “особей”. Каждая особь характеризуется «приспособленностью» – многомерной функцией ее генов. Задача оптимизации состоит в максимизации функции приспособленности. В процессе эволюции в результате отбора, рекомбинаций и мутаций геномов особей происходит поиск особей с высокой «приспособляемостью». Эволюция - это процесс постоянной оптимизации биологических видов. Естественный отбор гарантирует, что наиболее приспособленные особи дадут достаточно большое потомство, а благодаря генетическому наследованию мы можем быть уверены, что часть этого потомства не только сохранит высокую приспособленность родителей, но будет обладать и некоторыми новыми свойствами. Если эти новые свойства окажутся полезными, то с большой вероятностью они перейдут и в следующее поколение. Таким образом, происходит накопление полезных качеств и постепенное повышение приспособляемости биологического вида в целом. Зная, как решается задача оптимизации видов в природе, можно теперь применить похожий метод для решения различных реальных задач.

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

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

f(x1, x2, x3, …, xN)

Для того чтобы заработал ГА, нам необходимо представить независимые переменные в виде хромосом. Как это делается?

Как создать хромосомы?

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

Как работает генетический алгоритм?

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

Репродукция состоит из четырех шагов:

селекции

и трех генетических операторов (порядок применения не важен)

кроссовер

мутация

инверсия

Роль и значение селекции мы уже рассмотрели в обзоре эволюционных алгоритмов.

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

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

Инверсия инвертирует (изменяет) порядок бит в хромосоме путем циклической перестановки (случайное количество раз). Многие модификации ГА обходятся без данного генетического оператора.

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

Применение такого алгоритма позволяет существенно уменьшить количество переборов. Так, по некоторым грубым оценкам количество итераций растет как N ² – где N – число признаков. В этом случае для решения задачи, поставленной в начале раздела потребуется построение всего лишь 50² = 2500 моделей. Однако не следует забывать, что, проведя решение оптимизационной задачи с использованием генетического алгоритма можно только утверждать, что найденное решение более оптимально, чем начальные "особи", но утверждать, насколько и как далеко или близко к локальному (глобальному) экстремуму лежит полученный ответ нет возможности. Другой проблемой является "правильный" выбор начальных "особей" и их количества для эволюционного поиска.