Оптимизация в среде MATLAB

д) порождает из родителей потомков путем случайных изменений у одного из родителей (мутация, mutation) или комбинируя гены пары родителей (скрещивание, crossover)

е) заменяет текущую популяцию потомками, формируя следующее поколение.

3. Завершение алгоритма при выполнении критерия останова. Рассмотрим более полно эти этапы и реализующие их функции.

Начальная популяция определяется ее размером (Population size), который по умолчанию равен 20, и диапазоном (Initial range), по умолчанию равным [0; 1]. Подробнее об этих и других параметрах сказано ниже.

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

(прил. 6).

Как следует из описания этапов, алгоритм использует три способа получения потомков: элитизм, скрещивание пар родителей и мутацию одного из родителей. При скрещивании по умолчанию в каждую позицию (локус) потомка переносится ген из той же позиции одного из родителей, выбранного случайно (равномерный кроссовер). Мутация по умолчанию выполняется добавлением к вектору родителя случайного вектора с гауссовским распределением.

В качестве критериев остановки применяются следующие условия:

–превышено заданное число поколений (параметр Generations),

–исчерпан лимит времени поиска (Time limit),

–значение фитнес в лучшей точке не больше Fitness limit,

–средневзвешенное изменение значения фитнеса на ряде поколений

(Stall generations) меньшедопустимости (Function tolerance),

–нет улучшения функции в течение интервала времени Stall time limit (с).

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

Direct search (The Augmented Lagrangian Genetic Algorithm (ALGA)), т.е. нелинейные ограничения вводятся в функцию Лагранжа, которая минимизируется ga при выполнении условий

101

по границам и линейным ограничениям. Нарушение нелинейных ограничений сопоставляется с параметром Nonlinear constraint tolerance (по умолчанию 1е-6).

Генетический алгоритм реализован в функции ga, а для задания параметров алгоритма используется функция gaoptimset. Если ввести в командную строку

options = gaoptimset(@ga),

то будет создана структура параметров, имеющих значения по умолчанию. Для изменения параметров каждый параметр указывается в виде пары «’имя’, значение» как аргументы функции gaoptimset. Все параметры генетического алгоритма, их смысл и значения по умолчанию приведены в прил. 6.

Важным параметром алгоритма является размер популяции (PopulationSize), его значением может быть целое положительное число или целочисленный вектор. Во втором случае будет создано столько подпопуляций, какова размерность вектора, а размер подпопуляций будет равен значениям компонент вектора.

Параметр PopulationType задает тип данных популяции, его значениями могут быть: 'bitstring', 'custom' (оба при отсутствии ограничений), 'doubleVector' (по умолчанию).

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

1)равномерная (@gacreationuniform), создающая случайную начальную популяцию с равномерным распределением, используется по умолчанию при отсутствии границ или ограничений;

2)допустимая популяция (@gacreationlinearfeasible), соз-

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

3)Custom (собственная), написанная пользователем и генерирующая данные, тип которых должен соответствовать определенному

вPopulationType.

Впоследнем случае функция задается в опциях как options = gaoptimset('CreationFcn', @mycreat)

102

где mycreat – имя собственной функции, первая строка определения которой имеет вид

function Population = mycreat(GenomeLength, FitnessFcn, options),

где GenomeLength – число независимых переменных, FitnessFcn – фитнес-функция. Можно задать начальную популяцию или ее часть, указав массив, ее содержащий, в параметре InitialPopulation. При этом число строк массива не должно превышать значение параметра PopulationSize, а число столбцов равно числу переменных. Недостающие особи будут созданы стандартной функцией. В параметре PopInitRange можно указать диапазон значений переменных в начальной популяции в виде вектор-столбца или матрицы с двумя строками и числом столбцов, равным числу переменных. По умолчанию этот параметр равен [0;1], т.е. длявсех переменныхустановлендиапазонот 0 до1.

Перед применением оператора выбора алгоритм масштабирует фитнес для удобства выполнения выбора. По умолчанию применяется ранговая функция масштабирования fitscalingrank, которая лучшим индивидуумам присваивает ранг 1, следующим 2 и т.д. Параметром FitnessScalingFcn можно задать другой вид масштабирования: пропорциональное (fitscalingprop), основанное на лучших особях

(fitscalingtop), смещенное линейное (fitscalingshiftlinear),

или написать собственную функцию.

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

Изменить функцию выбора можно заданием ее имени в значении параметра SelectionFcn. Дополнительно имеютсяследующиефункции:

– Функция остатка selectionremainder, которая число родителей от одной особи берет равным целой части масштабированной целевой функции, а недостающие родители выбираются стохастически с вероятностью, пропорциональной дробной части.

103

–Функция равномерности (однородности) selectionuniform, рекомендуется только на стадии отладки или испытаний.

–Функция рулетки selectionroulette, использующая модель рулетки, размер секторов которой пропорционален качеству особей. Выбирается родитель сектора, на который выпало случайное число.

–Турнирная функция selectiontournament, реализующая метод турниров. Случайно выбираются несколько особей, и родителем становится лучшая из них. По умолчанию число выбираемых особей, т.е. размер турнира, равно 4. Размер не должен быть меньше 2, а изменить его можно в опциях

options = gaoptimset('SelectionFcn',...

{@selecttournament,size}),

где size – размер турнира.

Кроме того, пользователь может написать собственную функцию выбора. При этом заголовок функции, например с именем myfun, должен иметь вид

function parents = myfun(expectation, nParents, options),

где expectation – ожидаемое число детей для каждой особи популяции, nParents – число выбираемых родителей. Функция выбора возвращает родителей в виде вектор-строки длиной nParents, содержащей индексы родителей.

Создание детей для нового поколения регулируется двумя параметрами:

EliteCount определяет число элитных особей, которые гарантированно переходят без изменений в новое поколение, по умолчанию оно равно 2;

CrossoverFraction устанавливает долю нового поколения, порождаемую кроссовером (по умолчанию 0,8).

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

– Mutationgaussian, устанавливаемая по умолчанию. Она к каждому гену родителя добавляет случайное число, взятое из распределения Гаусса со средним 0 и дисперсией, определяемой параметрами Scale и Shrink (по умолчанию они равны 1). Изменить их можно, задав конкретные значения в опциях:

options = gaoptimset('MutationFcn',...

{@mutationgaussian,scale,shrink}).

104

– Mutationuniform производит мутацию в два шага. Сначала выбирается часть генов особи, каждый ген которой может мутировать с вероятностью Rate, по умолчанию равной 0,01. На втором шаге выбранный ген заменяется случайным числом с равномерным распределением из диапазона значений данного гена. Изменить вероятность Rate можно в опциях

options = gaoptimset('MutationFcn', {@mutationuniform, rate}).

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

–Собственная функция мутации, заголовок описания которой имеет вид

function mutationChildren = myfun(parents, options, nvars, FitnessFcn, state, thisScore, thisPopulation),

где parents – вектор-строка родителей, отобранных функцией выбора; nvars – число переменных;

state – структура, содержащаяинформацию отекущем поколении; thisScore – вектор меток (фитнес) текущей популяции; thisPopulation – матрица особей текущей популяции.

Функции мутации возвращают потомство (детей) от мутации в виде матрицы, строки которой соответствуют детям, а столбцы переменным.

Теперь остановимся на функциях кроссовера. По умолчанию установлена функция crossoverscattered, соответствующая рассеянному кроссоверу. Она формирует случайный бинарный вектор (шаблон) с размерностью хромосомы, и если в его позиции стоит 1, то в эту же позицию потомка помещается соответствующий ген первого родителя, иначе берется ген второго родителя. Параметром CrossoverFcn можно установить следующие функции:

–Crossoversinglepoint, реализующую одноточечный кроссовер. По случайному числу находится точка разбиения хромосомы, и родители обмениваются подстроками генов.

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

105

– Crossoverintermediate создает потомков взятием взвешенного среднего родителей. Веса задаются параметром Ratio в виде скаляра или вектора с длиной, равной числу переменных (по умолчанию единичная вектор-строка). Функция образует детей по формуле

child = parent1 + rand * Ratio * ( parent2 - parent1).

Значение Ratio можно изменить при задании функции, указав его после ее имени.

– Crossoverheuristic возвращает потомка, образуемого по формуле

child = parent2 + R * (parent1 - parent2),

где parent1 – родитель с лучшей фитнес-функцией, R – параметр ratio определяет близость потомка к родителям. Чем ближе R к 1, тем ближе потомок к лучшему родителю. По умолчанию R = 1,2, а изменить его можно при задании кроссовера.

–Crossoverarithmetic создает детей, которые являются средним арифметическим двух родителей. При этом дети всегда удовлетворяют линейным ограничениям и границам.

–Собственная функция кроссовера (Custom). В 1-й строке ее оп-

ределения с именем myfun следует записать

xoverKids = myfun(parents, options, nvars,...

FitnessFcn, unused,thisPopulation),

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

Если популяция представлена подпопуляциями, то имеет место движение особей между ними (миграция). Лучшие особи из одной подпопуляции замещают худшие в другой путем копирования. Процесс миграции управляется тремя параметрами:

1)направлением (MigrationDirection), которое может иметь значение 'forward', определяющее движение от n-й к n + 1-й подпопуляции, и 'both', когда особи n-й подпопуляции мигрируют в n – 1-ю

ив n + 1-ю подпопуляции;

2)интервалом (MigrationInterval), которым задается число поколений, через которое происходит миграция;

3)долей мигрирующих особей (MigrationFraction), которая относится к меньшей подпопуляции (при размерах подпопуляций 20 и 50 и доле 0,1 число мигрантов составит 2).

106

При решении задачи с нелинейными ограничениями алгоритм использует значения двух параметров:

1)начальный штраф (InitialPenalty) устанавливает начальное значение параметра штрафа в функции Лагранжа;

2)коэффициент штрафа (PenaltyFactor) увеличивает параметр штрафа для достижения заданной точности и выполнения ограничений; оба параметра должны быть не меньше 1.

Параметры алгоритма 'Vectorized' и 'UseParallel' опре-

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

Для указания функций вывода и графики используются параметры outputfcns и plotfcns. Соответствующие стандартные функции приведены в прил. 6. При написании собственной функции графики первая строка должна быть следующей:

function state = plotfun(options, state, flag),

где state – структура состояния, содержащая поля: Population – популяция текущего поколения, Score – метки текущей популяции, Generation – номер текущего поколения, StartTime – время старта алгоритма, StopFlag – описание причины останова,

Selection – индексы особей элитных, полученных кроссовером и мутацией,

Expectation – ожидание выбора особей,

Best – векторс лучшимизначениямиметоквкаждом поколении, LastImprovement – поколение, на котором произошло последнее

улучшение фитнес-функции,

LastImprovementTime – время, на котором произошло последнее улучшение,

NonlinIneq – нелинейные неравенства, если они есть в задаче, NonlinEq – нелинейные равенства, если они есть в задаче;

flag – индикация текущего статуса алгоритма: 'init' – начальная стадия, 'iter' алгоритм работает, 'interrupt' – промежуточная стадия, 'done' – алгоритм завершен.

107

В описании функции вывода данных каждой итерации первая строка имеет вид

[state,options,optchanged] = outputfun(options,...

state,flag,interval),

где optchanged – флаг индикации изменения параметров, interval – факультативный параметр интервала.

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

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

x = ga(fitnessfcn,nvars)

x = ga(fitnessfcn,nvars,A,b)

x = ga(fitnessfcn,nvars,A,b,Aeq,beq)

x = ga(fitnessfcn,nvars,A,b,Aeq,beq,LB,UB)

x = ga(fitnessfcn,nvars,A,b,Aeq,beq,LB,UB,nonlcon)

x = ga(fitnessfcn,nvars,A,b,Aeq,beq,LB,UB, nonlcon,...

options)

x = ga(problem) [x,fval] = ga(...)

[x,fval,exitflag] = ga(...).

Здесь fitnessfcn – имя фитнес-функции, например @myobj, nvars – число переменных, exitflag равен целому от 1 до 4, когда останов происходит по достижении одной из заданных точностей, и от 0 до –5, когда исчерпывается один из заданных лимитов или не найдено допустимое решение; смысл остальных аргументов был приведен при описании других функций. Еще один вариант вызова функции

[x,fval,exitflag,output] = ga(...)

приводит к возвращению также и структуры output, содержащей поля: rngstate – состояние генератора случайных чисел непосредственно перед стартом алгоритма; для повторного воспроизведения ре-

зультата решения его можно восстановить; generations – число полученных поколений; funccount – число вычислений фитнес-функции; message – содержит причину останова алгоритма;

maxconstraint – значение максимальногонарушения ограничения.

108

Дополнительные выходные данные о решении можно получить, применив форму вызова

[x,fval,exitflag,output,population,scores] = ga(...),

при которой функция возвращает матрицу конечной популяции (population) и вектор ее оценок (scores).

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

[x,fval,exitflag,output,popfin]=ga(@fitnessfcn,nvars)

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

Пример 15.

Генетическим алгоритмом найти минимум функции

f = 3(1 – x1)2exp (– x12 –(x2 + 1)2) – 10( x1/5 – x13 – x25 )exp (– x12 – x12 ) – –1/3exp (– (x1 + 1)2 – x22 )

при условиях

–3 xj 3, j = 1, 2.

Эта функция ранее была представлена в файлах myfun и myfun1. Для наглядного представления нескольких поколений напишем собственную функцию графики plotfun1:

function state = plotfun1(options, state, flag) switch flag

case 'init' plot(state.Population(:,1),state.Population(:,2),...

'ko')hold on; case 'iter'

if state.Generation==1 plot(state.Population(:,1),state.Population(:,2),...

'g.'); end

if state.Generation==2 plot(state.Population(:,1),state.Population(:,2),...

'b.'); end

109

if state.Generation==20 plot(state.Population(:,1),state.Population(:,2),...

'c.'); end

case 'done' plot(state.Population(:,1),state.Population(:,2),...

'r*'); end

end

Примем размер популяции 10 и составим и исполним следующую программу:

>> options=gaoptimset('PlotFcns',@plotfun1,'PopulationSize',10); [x,fval,exit,output]=ga(@myfun,2,[],[],[],[],[-3 -3],[3 3],[],options) [X,Y]=meshgrid(-3:0.03:3);Z=myfun1(X,Y);contour(X,Y,Z,20); xlabel('X1');ylabel('X2');

Optimization terminated: average change in the fitness value less than options.TolFun.

x =

-1.3448 0.2054 fval =

-3.0498 exit =

1 output =

problemtype: 'boundconstraints' rngstate: [1x1 struct] generations: 51

funccount: 520 message: [1x86 char] maxconstraint: 0

Полученные результаты показывают, что за 51 итерацию, в течение которых целевая функция вычислялась 520 раз, найден минимум, оказавшийся локальным. На рис. 31 представлено расположение особей в четырех итерациях: черными кружками – начальная популяция, зелеными ромбиками – особи первого поколения, синими – второго поколения, лазурными – 20-го поколения и красными снежинками – финальная популяция. Видно, что уже 20-е поколение располагается близко к локальному минимуму, а особи конечной популяции настолько близки друг к другу, что слились в одну точку. На первых итераци-

110