%% 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}