Общие сведения
При работе с оптимизационными задачами в непрерывных пространствах вполне естественно представлять гены напрямую вещественными числами. В этом случае хромосома есть вектор вещественных чисел. Их точность будет определяться исключительно разрядной сеткой той ЭВМ, на которой реализуется real-coded алгоритм. Длина хромосомы будет совпадать с длиной вектора-решения оптимизационной задачи, иначе говоря, каждый ген будет отвечать за одну переменную. Генотип объекта становится идентичным его фенотипу. Вышесказанное определяет список основных преимуществ real-coded алгоритмов:
1. Использование непрерывных генов делает возможным поиск в
больших пространствах (даже в неизвестных), что трудно делать в случае
двоичных генов, когда увеличение пространства поиска сокращает точ-
ность решения при неизменной длине хромосомы.
2. Одной из важных черт непрерывных ГА является их способность к
локальной настройке решений.
3. Использование RGA для представления решений удобно, поскольку
близко к постановке большинства прикладных задач. Кроме того, отсут-
ствие операций кодирования/декодирования, которые необходимы в BGA,
повышает скорость работы алгоритма.
Появление новых особей в популяции канонического ГА обеспечивают несколько биологических операторов: отбор, скрещивание и мутация. В качестве операторов отбора особей в родительскую пару здесь подходят любые известные из BGA: рулетка, турнирный, случайный. Однако операторы скрещивания и мутации в классических реализациях работают с битовыми строками. Необходимы реализации, учитывающие специфику realcoded алгоритмов.
Также рекомендуется использовать стратегию элитизма – лучшая особь сохраняется отдельно и не стирается при смене эпох, принимая при этом участие в отборе и рекомбинации
Цель работы
Модификация представления хромосомы и операторов рекомбинации ГА для оптимизации многомерных функций. Графическое отображение результатов оптимизации.
Задание на лабораторную работу
1. Создать программу, использующую ГА для нахождения оптимума функции согласно таблице вариантов, приведенной в приложении А. Для всех Benchmark-ов оптимумом является минимум. Программу выполнить на встроенном языке пакета Matlab.
2. Для n=2 вывести на экран график данной функции с указанием найденного экстремума, точек популяции. Для вывода графиков использовать стандартные возможности пакета Matlab. Предусмотреть возможность пошагового просмотра процесса поиска решения.
3. Повторить нахождение решения с использованием стандартного Genetic Algorithm toolbox. Сравнить полученные результаты.
4. Исследовать зависимость времени поиска, числа поколений (генераций), точности нахождения решения от основных параметров генетического алгоритма:
- число особей в популяции
- вероятность кроссинговера, мутации.
Критерий остановки вычислений – повторение лучшего результата заданное количество раз или достижение популяцией определенного возраста (например, 100 эпох).
5. Повторить процесс поиска решения для n=3, сравнить результаты,скорость работы программы.
Результат выполнения лабораторной работы
t2.m
function f=t2(x)
f=-cos(x(1))*cos(x(2))*exp(-((x(1)-pi)^2+(x(2)-pi)^2));
end
t3.m
function f=t3(x,y)
f=-cos(x).*cos(y).*exp(-((x-pi).^2+(y-pi).^2));
end
plotfun1.m
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
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
main2.m
[X,Y]=meshgrid(1.5:2*pi/100:5);
V=t3(X,Y);
mesh(Y,X,V)
xlabel('X1');
ylabel('X2');
zlabel('function');
title('-cos(x(1))*cos(x(2))*exp(-((x(1)-pi)^2+(x(2)-pi)^2))');
options= gaoptimset('PlotFcns',{@gaplotbestf,@plotfun1},'PopulationSize',10);
[x,fval,exit,output]=ga(@t2,2,[],[],[],[],[1.5 2],[5 5],[],options)
Z=t3(X,Y);
contour(X,Y,Z,20);
xlabel('X1');
ylabel('X2');
Красное-минимум
Желтое-20 поколений
Синее-10 поколений
Зленое-1 поколение
N= 3
x = 3.1777 3.0515
fval = -0.9860
exit = 1
output =
struct with fields:
problemtype: 'boundconstraints'
rngstate: [1×1 struct]
generations: 51
funccount: 156
N=50
x = 3.1416 3.1416
fval = -1.0000
exit = 1
output =
struct with fields:
problemtype: 'boundconstraints'
rngstate: [1×1 struct]
generations: 68
funccount: 3450
Optimization tool
Вывод: результаты совпали.