Решебник_МО

МЕТОДЫ СЛУЧАЙНОГО ПОИСКА С САМООБУЧЕНИЕМ И С АДАПТАЦИЕЙ

Вметодах случайного поиска с самообучением единичный случайный вектор ζ перестаёт быть равновероятным в процессе поиска

иприобретает определённое преимущество в направлении наилучшего шага, причём в том случае, когда избранное направление больше не приводит к успеху, алгоритм с самообучением способен искать другое.

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

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

Вметоде с введением постоянного параметра памяти

(координатное самообучение) задаётся вероятность выбора удачного шага Pi, где i=1,…,n, которая определяется функцией некоторого

параметра i , называемого параметром памяти или просто «памятью». Алгоритм самообучения реализуется путем соответствующего изменения памяти: ik 1 = ik –δ∙sign(∆ xik ∆f( xik )), где δ шаг по

памяти (δ>0). При δ=0 самообучения нет.

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

алгоритм работает в режиме поощрения (∆f( xik )<0) и наказания

(∆f( xik )>0). При ∆f( xik )=0 обучения нет, параметр памяти вдоль i-й

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

Метод координатного самообучения с

реализуется следующим образом: ik 1 =N ik -δ*∆ xik ∆f( xik ), где N –

81

параметр «забывания» (0 N 1). При N=1 в памяти хранится весь предыдущий опыт работы, при N=0 в памяти хранится лишь результат

последнего шага. При ik = 0 численное значение вероятности должно быть равно 1/2. При отсутствии опыта (∆f( xik ) = 0) система с

«забыванием» вырождается в равновероятный поиск.

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

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

Методы случайного поиска можно сделать эффективнее за счет изменения параметров поиска в процессе оптимизации.

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

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

82

Структурная адаптация осуществляется за счет параметризации структуры алгоритма, т.е. вводятся параметры, которые определяют структуру алгоритма поиска.

Пример 25. Пусть задана целевая функция W=140x10,93+150x20,86. Требуется найти значения параметров х1>0 и х2>0, соответствующие минимальному ее значению. Переменные x1 и

х2 связаны системой неравенств: 5х10,9+10x20,85≤3200,

24х10,94+6х20,93≤16000, 8x10,88+14x20,89≤5050, x1+x2=1000.

Решение. Для решения поставленной задачи применим направленный случайный поиск с наказанием случайностью и адаптацией рабочего шага: будем двигаться в удачном направлении до первого неудачного результата, каждый неудачный шаг будем «наказывать» введением случайности, после трех неудачных шагов подряд длину рабочего шага будем уменьшать в 10 раз.

Зададим длину рабочего шага h=100, координаты начальной точки поиска Х0=(х10=990, x20=10). Значение целевой функции в начальной точке поиска W0=86625.

Для реализации метода направленного случайного поиска нужна последовательность случайных чисел ζ, равномерно распределенных в интервале (–1, 1): –0,6; –0,28; 0,48; 0,1; 0,98; –0,25).

Первый шаг поиска осуществляется в случайном направлении. Вычисляем координаты точки X1: х11=х10+h*ζ1= 990–100*0,6=930; х21=1000–930=70. После проверки полученной точки на выполнение ограничений (результат положительный) вычисляем значение целевой функции: W1=86482.

Поскольку ∆W=W1–W0 <0, шаг следует считать удачным. Поэтому следующие шаги делаются в том же направлении до первого неудачного шага. Результаты расчетов сведены в табл. 9.

83

Продолжение табл. 9

Неудачные шаги отмечены звездочкой. Наилучший результат получен в 8-м испытании: W8 = 80948, х18 = 650, x28 = 350.

ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ

1.В чем отличие методов случайного поиска от детерминированных методов?

2.Сформулируйте алгоритм слепого случайного поиска.

3.Сформулируйте алгоритм случайного поиска с возвратом.

4.Сформулируйте алгоритм поиска с наказанием случайностью.

5.Сформулируйте алгоритм поиска с поощрением случайностью.

6.Сформулируйте алгоритм случайного поиска с парными пробами.

7.Что понимают под термином «адаптация» и «самообучение» в алгоритмах случайного поиска?

8.Сформулируйте алгоритм поиска с обучением.

9.Сформулируйте идею метода с введением постоянного параметра памяти.

10.Какие задачи называют «задачами с риском»?

11.Сформулируйте идею «блуждающих» алгоритмов поиска оптимума.

12.Перечислите основные типы адаптации в алгоритмах случайного поиска.

84

ЭВОЛЮЦИОННЫЕ АЛГОРИТМЫ

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

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

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

генетическое программирование (ГП), эволюционные стратегии (ЭС) и эволюционное программирование (ЭП).

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

85

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

В общем виде структура программы эволюционного алгоритма может быть представлена в виде псевдокода:

procedure эволюционный алгоритм begin

t=0

инициализация начальной популяции P(t) оценивание приспособленности особей из P(t) while (not условие завершения) do

begin t=t+1

селекция особей из P(t-1) в P(t) применение генетических операторов

оценивание приспособленности особей из P(t) end

end

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

Под начальной популяцией понимается некоторое количество получаемых, обычно случайным путем, объектов. В ГА такими объектами выступают вектора («генотипы») генов, где каждый ген может быть битом, числом или неким другим объектом. Алгоритмы ЭС оперируют векторами действительных чисел. В алгоритмах ГП и

86

ЭП роль объектов играют программы, всё лучше и лучше (в соответствии с определенной функцией приспособленности) решающие поставленную оптимизационную или поисковую задачу.

Основными генетическими операторами являются скрещивание и мутация. Мутация – это случайное изменение генотипа. В ГА и ЭС оператор мутации может быть реализован простым добавлением нормально распределенной случайной величины к каждой компоненте вектора. В ГП и ЭП эта операция сильно зависит от способа кодирования выращиваемых программ. Например при древовидном кодировании она может быть осуществлена случайным изменением информации в узле или добавлением, удалением узла или поддерева. Оператор скрещивания производит рекомбинацию решений-кандидатов, роль которых аналогична роли скрещивания в живой природе. Размножение в разных ЭА определяется по-разному – оно зависит от представления данных. Главное требование к размножению – чтобы потомки имели возможность унаследовать черты обоих родителей, «смешав» их каким-либо способом. На этапе отбора нужно из всей популяции выбрать определённую её долю, которая останется «в живых» на этом этапе эволюции. Есть разные способы проводить отбор. Вероятность выживания особи должна зависеть от значения функции приспособленности. Эта функция должна быть задана так, чтобы по ее значению на данном генотипе можно было судить о степени его «успешности». По итогам селекции из множества особей популяции должно остаться лишь определенное число особей, которые войдут в новую популяцию. Остальные особи погибают.

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

87

не менее L = 5 бит. Числу u = 1 будет соответствовать стринг 00000, числу u = 2 – стринг 11111, а стрингу а1а2а3а4а5 = 11001 будет соответствовать декодируемое значение:

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

Простейший ГА включает следующие шаги.

Ш а г 1. Инициализация. Случайно генерируется исходная популяция Р(t = 0), состоящая из μ хромосом āi (i = 1, 2, , μ), где обычно 30≤ μ ≤500. Это означает, что двоичные значения битов отдельных хромосом, входящих в популяцию, устанавливаются равновероятно и независимо друг от друга.

Ша г 2. Оценка хромосом, которая необходима для оценки качества хромосом, входящих в популяцию и последующей их селекции. Хромосомы декодируются, и оценивается их функция качества (фитнесс-функция) Ф, исходя из целевой функции F и функции декодирования Г: Ф(āi) = F◦Г(āi).

Ша г 3.Стохастическая селекция и репликация. Вычисляется

вероятность селекции хромосомы āi Р:

pS (ai ) (ai ) / (a j ).

j 1

Это пропорциональная (не дискриминационная или рулеточная) селекция, так как все родительские хромосомы имеют отличную от 0 вероятность потенциального участия в производстве потомков. Выбранная таким образом хромосома копируется в первоначально пустой список родителей, предназначенных для производства потомства. Селекция проводится μ раз, при этом математическое ожидание того, как часто хромосома āi выбирается в качестве родительской хромосомы, равно μ◦ps(āi). Результатом является список родительских хромосом.

Ш а г 4. Генерация потомков, когда, например μ/2 раз производятся следующие действия:

89

случайный выбор с вероятностью 1/μ пары партнеров ā1 и ā2 для кроссинговера (скрещивания) и мутации;

кроссинговер. В ГА обычно применяется одноточечный

оператор кроссинговера с вероятностью рк. Например, из двух родителей вида 00│000 и 11│111 образуются два потомка вида 00111 и 11000, где символ «│» обозначает точку скрещивания;

мутация. В ГА обычно применяется оператор мутации с

вероятностью рm от 0,01 до 0,001. Например, из родителя вида 01│011 образуется потомок вида 00111;

оценка потомков Ф(āi') = F(Г(āi')) и формирование новой популяции путем выбора μ лучших хромосом.

Ш а г 5. Переход на шаг 3 до тех пор, пока не будет

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

Существует много возможных вариаций селекции – от вычислительно трудоемких подходов до сравнительно простых схем: метод рулетки, турнирная селекция, ранжированная селекция, элитные виды селекции. Существует также множество разновидностей оператора скрещиваний: N-точечный, универсальный, смешанный кроссинговер и т.д.

некоторые положительные целые числа. Найдите только целые решения (a, b, c, d) этого уравнения, используя ГА.

Решение. Для поиска решения в данном случае можно использовать метод грубой силы, подставив все возможные значения a, b, c, d с учетом очевидных ограничений (1 ≤ a, b, c, d ≤ 30). Однако ГА позволяет найти решение быстрее за счет более «осмысленного» перебора.

Вначале согласно ГА случайно, но с учетом ограничений, выберем начальное поколение хромосом из 5 решений:

90