Меню
Главная
Авторизация/Регистрация
 
Главная arrow Медицина arrow Применение генетических алгоритмов для решения оптимизационных задач

поиска наибольшего значения функции.

Приведем пример такой согласованности, когда генетический алгоритм может работать вполне успешно (проблему остановки алгоритма оставим в стороне). Рассмотрим решение задачи о поиске точки x0, в которой достигается наибольшее значение непрерывной на отрезке [0, 1] функции F(x).

Пространством поиска будем считать множество всех двоичных рациональных чисел вида 0,a1a2an (количество используемых разрядов определяется допустимой погрешностью). Назовем хромосомами последовательности длины n, состоящие из нулей и единиц. Любой такой последовательности соответствует некоторое число на отрезке [0, 1], что значительно облегчает применение генетических операторов, поскольку в этом случае все вновь построенные (потенциальные) решения окажутся допустимыми. алгоритм генетический кроссинговер хромосома

Проанализируем условия эффективной работы каждого оператора в соответствии с его ролью в «эволюционном процессе». На начальном этапе действие кроссинговера и мутации оказывается сходным, поскольку начальная популяция состоит из хромосом, выбранных случайным образом. Мутация изменяет значение одного из разрядов двоичного числа x, «мутировавшее» значение переменной отличается от исходного на величину 2- k (где k - номер измененного разряда), что обеспечивает возможность поиска больших значений F(x) на всем отрезке. В результате применения кроссинговера числа 0,a1ak+1an и 0,b1bk+1bn преобразуются в 0,a1akbk+1bn и 0,b1bkak+1an. Различие между старым и новым поколениями в этом случае также можно оценить величиной 2- k, однако разница может быть меньше, если хромосомы a1a2an и b1b2bn имеют совпадающие участки. В частности, начальные фрагменты хромосом, соответствующих близким по величине числам (близлежащим точкам), совпадают. Для таких хромосом мутация и кроссинговер существенно различаются по результатам.

Селекция хромосом приводит к изменению структуры популяции, так как на заключительном этапе появляется значительное количество решений, лежащих в окрестности точек максимума. В этих условиях остается неизменной роль оператора мутации, заключающаяся в выявлении новых направлений поиска. Однако при появлении перспективных решений данный оператор не способен действовать целенаправленно, уточняя случайно полученные результаты («шаг алгоритма» при мутации является случайной величиной, характеристики которой не изменяются при работе алгоритма). Появление значительного числа решений с относительно высоким значением целевой функции может означать, что алгоритм попал в окрестность искомой точки x0. В этом случае максимальное количество новых решений появится именно в указанной окрестности, и поиск будет сосредоточен на перспективном участке. Подобная «самонастройка» алгоритма в рассматриваемом примере осуществляется благодаря оператору кроссинговера. У близких по величине чисел несколько первых разрядов совпадают, пара таких чисел имеет вид 0,a1am+1an и 0,a1ambm+1bn, поэтому их потомки, порожденные при кроссинговере, не могут отличаться от родителей более чем на 2- m (в действительности не более 2- (m+1), в других случаях потомок совпадает с одним из родителей). Следовательно, при появлении нескольких близких к оптимальному решений действия кроссинговера сводятся к уточнению последних разрядов числа x0 (либо к копированию существующих хромосом, что приведет к замедлению поиска на последних этапах). Худшие решения, лежащие вне исследуемого промежутка, «вымирают» как менее приспособленные, в результате вероятность применения оператора к подходящим парам хромосом повышается. Если же исследуемый максимум функции оказывается локальным, алгоритм способен выйти из него при помощи мутации (обнаружив большие значения функции на другом промежутке).

Выполняются ли в разобранном примере сформулированные выше условия эффективной работы генетического алгоритма? Значения последних разрядов аргумента не оказывают существенного влияния на значение непрерывной функции F(x). Это означает, что начальный (достаточно длинный) отрезок хромосомы, соответствующей решению x0, оказывается тем самым «хорошим» фрагментом, участвующим в конструировании оптимального решения. Содержащие такую подстроку хромосомы обеспечивают большие значения целевой функции (роль которой выполняет непрерывная F(x)), поскольку соответствующие им числа находятся в малой окрестности числа x0.

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

 
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Предметы
Агропромышленность
Банковское дело
БЖД
Бухучет и аудит
География
Документоведение
Естествознание
Журналистика
Информатика
История
Культурология
Литература
Логика
Логистика
Маркетинг
Математика, химия, физика
Медицина
Менеджмент
Недвижимость
Педагогика
Политология
Право
Психология
Религиоведение
Социология
Статистика
Страховое дело
Техника
Товароведение
Туризм
Философия
Финансы
Экология
Экономика
Этика и эстетика
Прочее