It is just an empty TeX file Write your code here TEX encoding UTF-8 U

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
%% It is just an empty TeX file.
%% Write your code here.
% !TEX encoding = UTF-8 Unicode
\documentclass[a4paper, 12pt]{article} % use "amsart" instead of "article" for AMSLaTeX format
\usepackage[left=20mm, top=15mm, right=10mm, bottom=15mm]{geometry}
\usepackage[parfill]{parskip} % Activate to begin paragraphs with an empty line rather than an indent
\usepackage{graphicx} % Use pdf, png, jpg, or eps§ with pdflatex; use eps in DVI mode
\usepackage[14pt]{extsizes}
\usepackage{setspace,amsmath}
\usepackage{mathtools}
\usepackage{ dsfont }
\usepackage{amsmath,amssymb}
\usepackage[unicode]{hyperref}
\usepackage{xcolor}
\usepackage{color}
\usepackage{minted}
\usepackage{caption}
\usepackage{array}
\newcolumntype{P}[1]{>{\centering\arraybackslash}p{#1}}
\usepackage{cmap} % Улучшенный поиск русских слов в полученном pdf-файле
\usepackage[T2A]{fontenc} % Поддержка русских букв
\usepackage[utf8]{inputenc} % Кодировка utf8
\usepackage[english, russian]{babel} % Языки: русский, английский
% TeX will automatically convert eps --> pdf in pdflatex
\usepackage{amssymb}
\begin{document}
\begin{titlepage}
\thispagestyle{empty}
\begin{center}
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Московский государственный технический университет имени Н.Э. Баумана
\end{center}
\vfill
\centerline{\large{Лабораторная работа №7. Вариант 6.}}
\centerline{\large{«Методы решения задач многокритериальной и}}
\centerline{\large{многоэкстремальной оптимизации»}}
\centerline{\large{по курсу}}
\centerline{\large{«Методы оптимизации»}}
\vfill
Студент группы ИУ9-81 \hfill Климов С.В.
Преподаватель \hfill Каганов Ю.T.
\vfill
\centerline{Москва, 2019}
\clearpage
\end{titlepage}
\newpage
\setcounter{page}{2}
\tableofcontents
\newpage
\section{Цель работы}
\begin{enumerate}
\item Изучение методов решения задач многоэкстремальной и многокритериальной оптимизации.
\item Разработка программ реализации алгоритмов мультистарта (метода ближайшего соседа, метода конкурирующих точек), генетического алгоритма, алгоритмом многокритериальной оптимизации.
\item Решение задачи:
\begin{enumerate}
\item многоэкстремальной оптимизации для функции Шекеля;
\item многоэкстремальной оптимизации для заданных многоэкстремальных функций;
\item многокритериальной оптимизации.
\end{enumerate}
\end{enumerate}
\newpage
\section{Постановка задачи}
\subsection{Задача 7.1}
\textbf {Дано}: 6 Вариант. Функция Шекеля:
\begin{multline}
f(x) = -\sum_{i=1}^3 \frac{a}{f_i^0 + b \sum_{j=1}^{3} (x_j - x_{ij}^0)^2}, \\ \sum_{i=1}^3 \frac{1}{f_i^0} = f^0 = c, x_{ij}^0 \in [\alpha, \beta]^3,
\end{multline}
где $a=1$, $b=1$, $c=2$, $\alpha = 0$, $\beta = 8$.
\begin{enumerate}
\item Реализовать алгоритмы многоэкстремальной оптимизации методом мультистарта на одном из языков высокого уровня.
\item Решить задачу многоэкстремальной оптимизации с помощью метода мультистарта.
\end{enumerate}
\textbf {Дано}: 6 Вариант. Функция:
\begin{equation}
f(x) = \sum_{i=1}^n[x_i^2-10 cos⁡(2\pi x_i)+10],x\in[\alpha,\beta]^n
\end{equation}
где $n=3$,$\alpha = 0$, $\beta = 20$.
\begin{enumerate}
\item Реализовать генетический алгоритм многоэкстремальной оптимизации на одном из языков высокого уровня.
\item Решить задачу многоэкстремальной оптимизации с помощью генетического алгоритма.
\end{enumerate}
\subsection{Задача 7.2}
\textbf {Дано}: 6 Вариант.
\begin{equation}
\begin{cases}
f_1(x) = 2x_1^2 +x_1x_3 + x_2^2 - 6x_1 - 5x_2 \rightarrow min, \\
f_2(x) = 3(x_1 - 2)^2 + 2(x_2 - 5)^2 + 5x_3 \rightarrow min, \\
g_1(x) = 3x_1 + x_2 + x_3 - 8 \leq 0, \\
g_2(x) = -x_1 + 5x_2 - 10 \leq 0.
\end{cases}
\end{equation}
\begin{enumerate}
\item Реализовать метод свертки критериев (метод «идеальной точки») многокритериальной оптимизации на одном из языков высокого уровня.
\item Требуется найти множества сильно эффективных решений (оптимальных по Парето) и слабо эффективных решений (оптимальных по Слейтеру) для (2).
\item Исследовать полученное представление решений в пространстве критериев с учетом заданных ограничений для (2).
\item Реализовать алгоритмы программированием на C++ и Python
\end{enumerate}
\newpage
\section{Исследование}
\subsection{Задача 7.1}
\subsubsection{Алгоритм метода ближайшего соседа}
\begin{enumerate}
\item Генерируются $K$ точек $(z_1, z_2,..., z_k)$ случайным образом с помощью, например, алгоритма Монте-Карло. Считается, что все они принадлежат различным кластерам (кластер ассоциируется с окрестностью локального минимума).
\item Находится ближайшая пара точек $(z_i, z_j)$, т.е. такая пара, для которой $\rho_{ij} = arg min_{k, l = 1,...,K} \rho_{kl}$.
\item Если расстояние $\rho_{ij} = \rho(z_i, z_j)$ между ближайшими соседями не превосходит некоторое достаточно малое число $\sigma > 0$, то точки $z_i$ и $z_j$, а также соответствующие им кластеры объединяются и число кластеров $K$ уменьшается на единицу. После этого происходит переход на Ш.2.
\item Остановка алгоритма происходит, либо если расстояние между ближайшеми соседями превосходит $\sigma$, либо если остается лишь один кластер.
\end{enumerate}
В качестве метрики $\rho(z_i, z_j)$ обычно выбирается евклидова метрика. Качество алгоритма как процедуры кластеризации существенно зависит от того, насколько удачно выбрано число $\sigma$. Это число должно быть достаточно малым, во всяком случае меньше расстояний между соседними точками локальных минимумов.
\subsubsection{Алгоритм метода конкурирующих точек}
\begin{enumerate}
\item Моделируется равномерное на $X$ распределение. В результате получается $N$ точек ${x_1, x_2,..., x_N}$.
\item Используя точки ${x_1, x_2,..., x_N}$ в качестве начальных, проводится одна или несколько итераций какого либо алгоритма локальной оптимизации. Получаем точки $(z_1, z_2,..., z_N)$.
\item Применяется какой либо метод кластеризации к точкам $(z_1, z_2,..., z_N)$. Пусть $m$ - число получившихся кластеров. Если $m=1$, то переход на Ш.5. Иначе переход на Ш.4.
\item Выбираются представители $x_1, x_2,..., x_m$ от всех кластеров (естественно выбирать в кластерах с наименьшим значением целевой функции). Положим $N=m$ и переход на Ш.2.
\item Считаем, что находимся в окрестности точки глобального минимума. Выбрать представителя от единственного кластера. Используя его в качестве начальной точки для алгоритма локальной оптимизации, обладающего высокой скоростью сходимости в окрестности точки экстремума.
\end{enumerate}
\subsubsection{Генетический алгоритм}
\textbf{Генетический алгортим} - это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, аналогичных естественному отбору в природе.
В нем используется основных 5 принципов:
\begin{enumerate}
\item \textbf{Формирование исходной популяции} - в зависимости от поставленной задачи генерируются $N$ особей $x^k = (x_1^k,..., x_n^k)^T$, для которой вычисляется функция фитнеса;
\item \textbf{Отбор (селекция)} - операция, которая осуществляет отбор особей (хромосом) $x^k$ в соответствии со значениями функции фитнеса $\mu(x^k)$ для последующего их скрещивания.
\item \textbf{Кроссинговер (скрещивание)} – это операция, при которой из нескольких, обычно двух хромосом (особей) $(x_i, x_j), \quad i \neq j$, называемых родителями, порождается одна или несколько новых, называемых потомками.
\item \textbf{Мутация} - это преобразование хромосомы, случайно изменяющее один или несколько из её генов. Оператор мутации предназначен для того, чтобы поддерживать разнообразие особей в популяции. Необходимо определить параметр $Pm \in (0, 1]$ - вероятность мутации.
\item \textbf{Формирование новой популяции}
\begin{enumerate}
\item С равной вероятностью из потомков мутантов предыдущего шага выбирается один $x^m = (x_1, x_2,..., x_p^M,..., x_n)$.
\item Выбранный потомок добавляется в популяцию вместо хромосомы, которой соответствует наименьшее значение функции фитнеса (наихудшее из допустимых значений).
\item Вычисляется значение функции фитнеса для мутантного потомка $\mu_M = \mu(x^M)$.
\end{enumerate}
\item \textbf{Проверка условия останова генетического алгоритма} - условием окончания работы генетического алгоритма является формирование заданного количества популяций $t = Np$.
\end{enumerate}
\subsection{Задача 7.2}
\subsubsection{Методы свертки критериев (метод «идеальной точки»)}
\begin{enumerate}
\item Решение оптимизационных задач для каждого из критериев отдельно и получение «идеальной точки» c учетом ограничений.
\item Выбор весовых коэффициентов. Величины весовых коэффициентов - подбираются исходя из предварительно обусловленных соображений, которые могут быть выражены в виде дополнительных неформализуемых критериев. Чаще всего весовые коэффициенты выбираются путём бинарных сравнений и построения обратно симметричной матрицы. Далее вычисляются собственные значения и, для максимального собственного значения, выбирается соответствующий собственный вектор, элементы которого используются как весовые коэффициенты (метод Т. Саати). В данном случае весовые коэффициенты могут варьироваться различным образом для исследования пространства эффективных точек.
\item Получение оптимальных по Парето и Слейтеру решений. Для решения задачи можно использовать методы штрафных функций или метод модифицированных функций Лагранжа.
\end{enumerate}
\newpage
\section{Практическая реализация}
Все методы были реализованы на языке программирования \textbf{Python}. Для алгоритмов с кластеризацией использовались следующие классы:
\textbf{Листинг 1.} Вспомогательные классы для кластеризации.
\begin{minted}[frame=single, framesep=10pt, fontsize = \footnotesize, linenos=true, breaklines]{python}
def minimize(f, x0):
return lab5.penalty_functions(x0, f, cons=[])[0]
def dist(x1, x2):
return math.sqrt(sum(map(lambda v: (v[0] - v[1]) ** 2, zip(x1, x2))))
class Cluster:
def __init__(self, point):
self.points = [point]
self.id = uuid.uuid4()
self.main_point = point
self.metric = dist
def __hash__(self):
return self.id.int
def add_point(self, point):
self.points.append(point)
def add_points(self, points):
for p in points:
self.points.append(p)
def dist(self, cluster):
point_pairs = list(product(self.points, cluster.points))
d = min(map(lambda pair: dist(pair[0], pair[1]), point_pairs))
return d
def get_delegate(self, func):
return min(self.points, key=func)
def union(self, cluster):
points = self.points + cluster.points
new_cluster = Cluster(points[0])
new_cluster.add_points(points[1:])
return new_cluster
def __repr__(self):
return "{}".format(self.main_point)
def shekel(a, b, c, A, f):
def func(x):
res = 0
for i in range(A.shape[0]):
loc_res = 0
for j in range(len(x)):
loc_res += (x[j] - A[i][j]) ** 2
loc_res = b * loc_res + f[i]
res += a / loc_res
return -res
return func
\end{minted}
\textbf{Листинг 2.} Метод ближайшего соседа.
\begin{minted}[frame=single, framesep=10pt, fontsize = \footnotesize, linenos=true, breaklines]{python}
def k_nearest(points, eps):
clusters = list(map(lambda p: Cluster(p), points))
while True:
pairs = []
for i, c in enumerate(clusters):
pairs += list(product([c], clusters[:i] + clusters[i + 1:]))
if len(pairs) == 0:
return clusters
c1, c2 = min(pairs, key=lambda pair: pair[0].dist(pair[1]))
if c1.dist(c2) < eps:
new_cluster = c1.union(c2)
clusters.remove(c1)
clusters.remove(c2)
clusters.append(new_cluster)
else:
return clusters
if len(clusters) == 1:
return clusters
\end{minted}
\textbf{Листинг 3.} Метод конкурирующих точек
\begin{minted}[frame=single, framesep=10pt, fontsize = \footnotesize, linenos=true, breaklines]{python}
def f(x):
return sum(map(lambda v: v ** 2 - 10 * math.cos(2 * v * math.pi) + 10, x))
def cross(ind1, ind2):
c = np.random.rand()
ch1 = c * ind1 + (1 - c) * ind2
ch2 = c * ind2 + (1 - c) * ind1
return ch1, ch2
def selection(population, cropsize):
return population[:cropsize // 4]
def mutate_function(alpha, beta):
def f(individual):
pow_factor = 12
new_ind = np.copy(individual)
for i in range(len(individual)):
factor = np.random.rand()
if np.random.randint(0, 2) == 0:
new_ind[i] -= (new_ind[i] - alpha) * factor ** pow_factor
else:
new_ind[i] += (beta - new_ind[i]) * factor ** pow_factor
return new_ind
return f
def ga(fit, crossover=cross, mutation=mutate_function(0, 20), selection=selection, n=3, crop=100, epoch=1000, alpha=0,
beta=20):
initial_individuals = np.random.uniform(low=alpha, high=beta, size=(crop-1, n))
population = [(x, fit(x)) for x in initial_individuals]
population.sort(key=operator.itemgetter(1))
pcross = 0.5
pmut = 0.2
iter = 0
while iter < epoch:
iter += 1
# selection
if len(population) >= crop:
population = selection(population, crop)
pop_len = len(population)
# cross
parents = list(filter(lambda individual: np.random.rand() < pcross, population[:int(pop_len * pcross)]))
parent_pairs = []
for i, p in enumerate(parents):
parent_pairs += list(product([p], parents[:i] + parents[i + 1:]))
childs = []
for p1, p2 in parent_pairs:
ch1, ch2 = crossover(p1[0], p2[0])
childs.append((ch1, fit(ch1)))
childs.append((ch2, fit(ch2)))
# mutation
mutation_list = list(filter(lambda individual: np.random.rand() < pmut, population[:int(pop_len * pmut)]))
for i, individual in enumerate(mutation_list):
mutated = mutation(individual[0])
mutation_list[i] = (mutated, fit(mutated))
population += mutation_list + childs
population.sort(key=operator.itemgetter(1))
return population[0]
\end{minted}
\textbf{Листинг 5.} Метод "идеальной точки".
\begin{minted}[frame=single, framesep=10pt, fontsize = \footnotesize, linenos=true, breaklines]{python}
def f1(x):
x1, x2, x3 = x
return 2 * x1 ** 2 + 2 * x1 + x2 ** 2 - 6 * x1 - 5 * x2
def f2(x):
x1, x2, x3 = x
return 3 * (x1 - 2) ** 2 + 2 * (x2 - 5) ** 2
def c1(x):
x1, x2, x3 = x
return 3 * x1 + x2 + x3 - 8
def c2(x):
x1, x2, x3 = x
return 5 * x2 - x1 - 10
def constraints():
return [c1, c2]
def main():
x0 = np.array([1, 1, 0])
xf1 = lab5.barier_functions(x0, func=f1, cons=constraints())[0]
xf2 = lab5.barier_functions(x0, func=f2, cons=constraints())[0]
f_star = np.array([f1(xf1), f2(xf2)])
fs = [f1, f2]
f1s = []
f2s = []
n = 50
for i in range(1, n):
w = [i/n, 1 - i/n]
new_f = lambda x: sum([w[j] * (fs[j](x) - f_star[j]) for j in range(len(w))])
x = lab5.barier_functions(x0, func=new_f, cons=constraints())[0]
f1s.append(f1(x))
f2s.append(f2(x))
plt.scatter(f1s, f2s, color='lightblue', linewidth=3)
plt.show()
\end{minted}
\newpage
\section{Результаты.}
Были получены следующие результаты:
\textbf{Листинг 5.} Результаты выполнения программ.
\begin{minted}[frame=single, framesep=10pt, fontsize = \footnotesize, linenos=true, breaklines]{text}
Метод конкурирующих точек:
X = [
[0, 2, 5],
[2, 3, 5],
[1, 6, 7]
]
f_i = [2/6, 4/6, 6/6]
f([0.00722005 2.00441463 5.00045978]) = -3.2225654562543364
Генетический алгоритм:
f([2.17271386e-08, 1.21251123e-07, 3.49018091e-06]) = 2.419694666855321e-09
\end{minted}
Для метода эффективных точек использовались следующие весовые коэффициенты:
$$wi_1 = i/n,wi_2 = 1 - i/n, n=50 , i=1,...,49$$
В результате получилось следующее множество эффективных решений.
\includegraphics[]{lab72.png}
\end{document}