Задание на лабораторную работу
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
Вывод: результаты совпали.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение
высшего образования
«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ»
ИНСТИТУТ НЕПРЕРЫВНОГО И ДИСТАНЦИОННОГО ОБРАЗОВАНИЯ
|
|
|
| КАФЕДРА 43 |
ОЦЕНКА
ПРЕПОДАВАТЕЛЬ
| Проф., доктор тех. наук | Скобцов Ю.А. | |||
| должность, уч. степень, звание | подпись, дата | инициалы, фамилия |
| ОТЧЕТ О ЛАБОРАТОРНОЙ РАБОТЕ №3 |
| Решение задачи коммивояжера с помощью генетических алгоритмов |
| по дисциплине: ЭВОЛЮЦИОННАЯ МЕТОДОЛОГИЯ В ПРОГРАММНОЙ ИНЖЕНЕРИИ |
РАБОТУ ВЫПОЛНИЛ(А)
| СТУДЕНТ(КА) ГР. | Z7430m | А.С. Хромцова | |||
| номер группы | подпись, дата | инициалы, фамилия | |||
| Студенческий билет № | 2017/2649 | ||||
Санкт-Петербург 2019
Общие сведения
Задача коммивояжера (ЗК) считается классической задачей генетиче-
ских алгоритмов. Она заключается в следующем: путешественник (или
коммивояжер) должен посетить каждый из базового набора городов и вер-
нуться к исходной точке. Имеется стоимость билетов из одного города в
другой. Необходимо составить план путешествия, чтобы сумма затрачен-
ных средств была минимальной. Поисковое пространство для ЗК- множе-
ство из N городов. Любая комбинация из N городов, где города не повто-
ряются, является решением. Оптимальное решение – такая комбинация,
|
|
|
стоимость которой (сумма из стоимостей переезда между каждыми из го-
родов в комбинации) является минимальной.
ЗК – достаточно стара, она была сформулирована еще в 1759 году
(под другим именем). Термин «Задача коммивояжера» был использован в
1932г. в немецкой книге «The traveling salesman, how and what he should to
get commissions and be successful in his business», написанную старым ком-
мивояжером.
Задача коммивояжера была отнесена к NP-сложным задачам. Суще-
ствуют строгие ограничения на последовательность, и количество городов
может быть очень большим (существуют тесты, включающие несколько
тысяч городов).
Кажется естественным, что представление тура – последовательность
(i1, i2, … , in), где (i1, i2, … , in) – числа из множества (1 … n), представляю-
щие определенный город. Двоичное представление городов неэффективно,
т.к. требует специального ремонтирующего алгоритма: изменение одиноч-
ного бита может повлечь неправильность тура.
37
В настоящее время существует три основных представления пути: со-
седское, порядковое и путевое. Каждое из этих представлений имеет соб-
ственные полностью различные операторы рекомбинации.
Цель работы
Решение задачи коммивояжера с помощью генетического алгоритма.
|
|
|
Дата добавления: 2019-03-09; просмотров: 608; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!