Поэтому, в последнее время больше склоняюсь к методологии waterfall. Так спокойно работается и каждый понимает свою зону ответственности. Лиды на своих местах, разрабы и другие на своих.
А еще классно, когда Master не может надовить на product owner'a))) Пример. Я, как разработчик вижу, что эту задачу могу сделать за 8 часов, но product owner считает, что тут можно и за 2 часа всё сделать, поэтому ставит своё время. Я смело могу с наглой рожей сказать, чтобы он сам задачу делал за 2 часа. А master стоит и хлопает глазами, потому что не понимает как работают процессы. Это его команда и он должен ей рулить, он должен диктовать правила, а не owner. Конечно, не стоит идти в штыки с owner'ом, а уметь взаимодействовать с ним. Поэтому, такой вот у нас бардак.
15 человек. Мастер у нас мёртвый, просто потому что опыта не было. Иной раз рявкать приходится, потому что невозможно это. Как по мне, ежедневные Stand Up'ы, Ретро — это пустая трата времени, если команда не умеет взаимодействовать друг с другом. За рабочую неделю — мы рабочий день, извините за выражение, пустословим (п**дим) ни о чём. Я бы лучше это время потратил на разработку или ещё какое-либо полезное занятие, но нет, ты обязан слушать о том, как дизайнер или контентмейкер мусолит свою задачу, посещать собрания на которых мы очередной раз профукали спринт, потому что кто-то чё-то тормозит и вообще команда ужасная и плохая.
Не спорю, Scrum идеально вписывается под сплоченную команду, которая готова включатся и бросаться на любую проблему. Но когда у тебя коллектив забитых интровертов, которые хотят реализовывать только тот объем задач, который на них висит, да ещё сверху добитых бюрократией — по такой схеме невозможно работать. Да, и как описал выше, нужно выбирать методологию под задачи, а не подгонять задачи под методологию. Со стороны это жесть как весело смотрится, а работать в этом безобразие — вообще одно удовольствие.
Хорошо, когда у нас есть пул задач и мы под них выбираем методологию разработки… Но в текущей компании (название умолчу) происходит всё наоборот — под методологию загоняется спринт и происходит чёрти что.
Ну и не хватает в этом тексте то, что Scrum master обязан контролировать эти миттинги, потому что всяко без лидера — все в команде начинают разглагольствовать и эти встречи затягиваются от 40 минут до 1 часу.
Идея данного метода в том, что поиск происходит в направлении покоординатного спуска во время новой итерации. Спуск осуществляется постепенно по каждой координате. Количество координат напрямую зависит от количества переменных.
Для демонстрации хода работы данного метода, для начала необходимо взять функцию z = f(x1, x2,…, xn) и выбрать любую точку M0(x10, x20,…, xn0) в n пространстве, которая зависит от числа характеристик функции. Следующим шагом идет фиксация всех точек функции в константу, кроме самой первой. Это делается для того, чтобы поиск многомерной оптимизации свести к решению поиска на определенном отрезке задачу одномерной оптимизации, то есть поиска аргумента x1.
Для нахождения значения данной переменной, необходимо производить спуск по этой координате до новой точки M1(x11, x21,…, xn1). Далее функция дифференцируется и тогда мы можем найти значение новой следующий точки с помощью данного выражения:
После нахождения значения переменной, необходимо повторить итерацию с фиксацией всех аргументов кроме x2 и начать производить спуск по новой координате до следующей новой точке M2(x11,x21,x30…,xn0). Теперь значение новой точки будет происходить по выражению:
И снова итерация с фиксацией будет повторяться до тех пор, пока все аргументы от xi до xn не закончатся. При последней итерации, мы последовательно пройдем по всем возможным координатам, в которых уже найдем локальные минимумы, поэтому целевая функция на последний координате дойдет до глобального минимума. Одним из преимуществ данного метода в том, что в любой момент времени есть возможность прервать спуск и последняя найденная точка будет являться точкой минимума. Это бывает полезно, когда метод уходит в бесконечный цикл и результатом этого поиска можно считать последнюю найденную координату. Однако, целевая установка поиска глобального минимума в области может быть так и не достигнута из-за того, что мы прервали поиск минимума (см. Рисунок 1).
Рисунок 1 – Отмена выполнения покоординатного спуска
Исследование данного метода показали, что каждая найденная вычисляемая точка в пространстве является точкой глобального минимума заданной функции, а функция z = f(x1, x2,…, xn) является выпуклой и дифференцируемой.
Отсюда можно сделать вывод, что функция z = f(x1, x2,…, xn) выпукла и дифференцируема в пространстве, а каждая найденная предельная точка в последовательности M0(x10, x20,…, xn0) будет являться точкой глобального минимума (см. Рисунок 2) данной функции по методу покоординатного спуска.
Рисунок 2 – Локальные точки минимума на оси координат
Можно сделать вывод о том, что данный алгоритм отлично справляется с простыми задачами многомерной оптимизации, путём последовательно решения n количества задач одномерной оптимизации, например, методом золотого сечения.
Ход выполнения метода покоординатного спуска происходит по алгоритму описанного в блок схеме (см. Рисунок 3). Итерации выполнения данного метода:
• Изначально необходимо ввести несколько параметров: точность Эпсилон, которая должна быть строго положительной, стартовая точка x1 с которой мы начнем выполнение нашего алгоритма и установить Лямбда j;
• Следующим шагом будет взять первую стартовую точку x1, после чего происходит решение обычного одномерного уравнения с одной переменной и формула для нахождения минимума будет, где k = 1, j=1:
• Теперь после вычисления точки экстремума, необходимо проверить количество аргументов в функции и если j будет меньше n, тогда необходимо повторить предыдущий шаг и переопределить аргумент j = j + 1. При всех иных случаях, переходим к следующему шагу.
• Теперь необходимо переопределить переменную x по формуле x (k + 1) = y (n + 1) и попытаться выполнить сходимость функции в заданной точности по выражению:
Теперь от данного выражения зависит нахождение точки экстремума. Если данное выражение истинно, тогда вычисление точки экстремума сводится к x*= xk + 1. Но часто необходимо выполнить дополнительные итерации, зависящие от точности, поэтому значения аргументов будет переопределено y(1) = x(k + 1), а значения индексов j =1, k = k + 1.
Рисунок 3 – Блок схема метода покоординатного спуска
Итого, у нас имеется отличный и многофункциональный алгоритм многомерной оптимизации, который способен разбивать сложную задачу, на несколько последовательно итерационных одномерных. Да, данный метод достаточно прост в реализации и имеет легкое определение точек в пространстве, потому что данной метод гарантирует сходимость к локальной точке минимума. Но даже при таких весомых достоинствах, метод способен уходить в бесконечные циклы из-за того, что может попасть в своего рода овраг.
Существуют овражные функции, в которых существуют впадины. Алгоритм, попав в одну из таких впадин, уже не может выбраться и точку минимума он обнаружит уже там. Так же большое число последовательных использований одного и того же метода одномерной оптимизации, может сильно отразиться на слабых вычислительных машинах. Мало того, что сходимость в данной функции очень медленная, поскольку необходимо вычислить все переменные и зачастую высокая заданная точность увеличивает в разы время решения задачи, так и главным недостатком данного алгоритма – ограниченная применимость.
Проводя исследование различных алгоритмов решения задач оптимизации, нельзя не отметить, что огромную роль играет качество данных алгоритмов. Так же не стоит забывать таких важных характеристик, как время и стабильность выполнения, способность находить наилучшие значения, минимизирующие или максимизирующие целевую функцию, простота реализации решения практических задач. Метод покоординатного спуска прост в использовании, но в задачах многомерной оптимизации, чаще всего, необходимо выполнять комплексные вычисления, а не разбиение целой задачи на подзадачи.
Метод Нелдера - Мида
Стоит отметить известность данного алгоритма среди исследователей методов многомерной оптимизации. Метод Нелдера – Мида один из немногих методов, который основанный на концепции последовательной трансформации деформируемого симплекса вокруг точки экстремума и не используют алгоритм движения в сторону глобального минимума.
Данный симплекс является регулярным, а представляется как многогранник с равностоящими вершинами симплекса в N-мерном пространстве. В различных пространствах, симплекс отображается в R2-равносторонний треугольник, а в R3 — правильный тетраэдр.
Как упоминалось выше, алгоритм является развитием метода симплексов Спендли, Хекста и Химсворта, но, в отличие от последнего, допускает использование неправильных симплексов. Чаще всего, под симплексом подразумевается выпуклый многогранник с числом вершин N+1, где N – количество параметров модели в n -мерном пространстве.
Для того, чтобы начать пользоваться данным методом, необходимо определиться с базовой вершиной всех имеющихся множества координат с помощью выражения:
Самым замечательным в этом методе то, что у симплекса существуют возможности самостоятельно выполнять определенные функции:
• Отражение через центр тяжести, отражение со сжатием или растяжением;
• Растяжение;
• Сжатие.
Преимуществу среди этих свойств отдают отражению, поскольку данный параметр является наиболее опционально – функциональным. От любой выбранной вершины возможно сделать отражение относительно центра тяжести симплекса по выражению:.
где xc — центр тяжести (см. Рисунок 1).
Рисунок 1 – Отражение через центр тяжести
Следующим шагом необходимо провести расчет аргументов целевой функции во всех вершинах отраженного симплекса. После этого, мы получим полную информацию о том, как симплекс будет вести себя в пространстве, а значит и информацию о поведении функции.
Для того чтобы совершить поиск точки минимума или максимума целевой функции с помощью методов использующих симплексы, необходимо придерживаться следующей последовательности:
• На каждом шаге строиться симплекс, в каждой точке которого, необходимо произвести расчет всех его вершин, после чего отсортировать полученные результаты по возрастанию;
• Следующий шаг – это отражение. Необходимо провести попытку получить значения нового симплекса, а путём отражения, у нас получиться избавиться от нежелательных значений, которые стараются двигать симплекс не в сторону глобального минимума;
• Чтобы получить значения нового симплекса, из полученных отсортированных результатов, мы берем две вершины с наихудшими значениями. Возможны такие случаи, что сразу подобрать подходящие значения не удастся, тогда придется вернуться к первому шагу и произвести сжатие симплекса к точке с самым наименьшим значением;
• Окончанием поиска точки экстремума является центр тяжести, при условии, что значение разности между функциями имеет наименьшие значения в точках симплекса.
Алгоритм Нелдера – Мида так же использует эти функции работы с симплексом по следующим формулам:
• Функция отражения через центр тяжести симплекса высчитывается по следующему выражению:
Данное отражение выполняется строго в сторону точки экстремума и только через центр тяжести (см. Рисунок 2).
Рисунок 2 – Отражение симплекса происходит через центр тяжести
• Функция сжатия вовнутрь симплекса высчитывается по следующему выражению:
Для того, чтобы провести сжатие, необходимо определить точку с наименьшим значением (см. Рисунок 3).
Рисунок 3 – Сжатие симплекса происходит к наименьшему аргументу.
• Функция отражения со сжатием симплекса высчитывается по следующему выражению:
Для того, чтобы провести отражение со сжатием (см. Рисунок 4), необходимо помнить работу двух отдельных функций – это отражение через центр тяжести и сжатие симплекса к наименьшему значению.
Рисунок 4 — Отражение со сжатие
• Функция отражения с растяжением симплекса (см. Рисунок 5) происходит с использованием двух функций – это отражение через центр тяжести и растяжение через наибольшее значение.
Рисунок 5 — Отражение с растяжением.
Чтобы продемонстрировать работу метода Нелдера – Мида, необходимо обратиться к блок схеме алгоритма (см. Рисунок 6).
Первостепенно, как и в предыдущих примерах, нужно задать параметр искаженности ε, которая должна быть строго больше нуля, а также задать необходмые параметры для вычисления α, β и a. Это нужно будет для вычисления функции f(x0), а также для построения самого симплекса.
Рисунок 6 — Первая часть метода Нелдера — Мида.
После построения симплекса необходимо произвести расчет всех значений целевой функции. Как и было описано выше про поиск экстремума с помощью симплекса, необходимо рассчитать функцию симплекса f(x) во всех его точках. Далее производим сортировку, где базовая точка будет находиться:
Теперь, когда базовая точка рассчитана, а также и все остальные отсортированы в списке, мы производим проверку условия достижимости по ранее заданной нами точности:
Как только данное условие станет истинным, тогда точка x(0) симплекса будет считаться искомой точкой экстремума. В другом случае, мы переходим на следующий шаг, где нужно определить новое значение центра тяжести по формуле:
Если данное условие выполняется, тогда точка x(0) будет являться точкой минимума, в противном случае, необходимо перейти на следующий шаг в котором необходимо произвести поиск наименьшего аргумента функции:
Из функции необходимо достать самую минимальное значение аргумента для того, что перейти к следующему шагу выполнения алгоритма. Иногда случается проблема того, что несколько аргументов сразу имеют одинаковое значение, вычисляемое из функции. Решением такой проблемы может стать повторное определение значения аргумента вплоть до десятитысячных.
После повторного вычисления минимального аргумента, необходимо заново сохранить новые полученные значения на n позициях аргументов.
Рисунок 7 — Вторая часть метода Нелдера — Мида.
Вычисленное из предыдущей функции значение необходимо подставить в условие fmin < f(xN). При истинном выполнении данного условия, точка x(N) будет являться минимальной из группы тех, которые хранятся в отсортированном списке и нужно вернуться к шагу, где мы рассчитывали центр тяжести, в противном случае, производим сжатие симплекса в 2 раза и возвращаемся к самому началу с новым набором точек.
Исследования данного алгоритма показывают, что методы с нерегулярными симплексами (см. Рисунок 8) еще достаточно слабо изучены, но это не мешает им отлично справляться с поставленными задачами.
Более глубокие тесты показывают, что экспериментальным образом можно подобрать наиболее подходящие для задачи параметры функций растяжения, сжатия и отражения, но можно пользоваться общепринятыми параметрами этих функций α = 1/2, β = 2, γ = 2 или α = 1/4, β = 5/2, γ = 2. Поэтому, перед тем как отбрасывать данный метод для решения поставленной задачи, необходимо понимать, что для каждого нового поиска безусловного экстремума, нужно пристально наблюдать за поведением симплекса во время его работы и отмечать нестандартные решения метода.
Рисунок 8 — Процесс нахождения минимума.
Статистика показала, что в работе данного алгоритма существует одна из наиболее распространенных проблем – это вырождение деформируемого симплекса. Это происходит, когда каждый раз, когда несколько вершин симплекса попадают в одно пространство, размерность которого не удовлетворяет поставленной задачи.
Таким образом, размерность во время работы и заданная размерность закидывают несколько вершин симплекса в одну прямую, запуская метод в бесконечный цикл. Алгоритм в данной модификации еще не оснащен способом выйти из такого положения и сместить одну вершину в сторону, поэтому приходится создать новый симплекс с новыми параметрами, чтобы такого в дальнейшем не происходило.
Еще одной особенностью обладает данный метод – это некорректной работой при шести и более вершинах симплекса. Однако, при модификации данного метода, можно избавиться от этой проблемы и даже не потерять при этом скорости выполнения, но значение выделяемой памяти заметно повысится. Данный метод можно считать циклическим, поскольку он полностью основан на циклах, поэтому и замечается некорректная работа при большом количестве вершин.
Алгоритм Нелдера – Мида по праву можно считать одним из наилучших методов нахождения точки экстремума с помощью симплекса и отлично подходит для использования его в различные рода инженерных и экономических задачах. Даже не смотря на цикличность, количество памяти он использует очень малое количество, по сравнение с тем же методом покоординатного спуска, а для нахождения самого экстремума требуется высчитывать только значения центра тяжести и функции. Небольшое, но достаточное, количество комплексных параметров дают этому методу широкое использование в сложных математических и актуальных производственных задачах.
Симплексные алгоритмы – это край, горизонты которого еще мы не скоро раскроем, но уже сейчас они значительно упрощают нашу жизнь своей визуальной составляющей.
P.S. Текст полностью мой. Надеюсь кому-нибудь данная информация будет полезной.
P.S.S. Сорри, за косяки в тексте и корявые формулы. Возможности скинуть нормально нет :(
Почему у меня не было такой школы?
Ааа, ну да… Я же с деревни…
На самом деле круто, что сейчас имеется такая возможность получить бесплатно знания в таком возрасте. Мне нравится современный подход того, что компании сами себе кадров выращивают, путём проведения таких курсов (не буду говорить о качестве, судите сами). И даже если не подходишь ты для этой компании после окончания, у тебя на руках остаётся багаж знаний, который ты можешь применить в другой компании, где на Junior-позицию приходишь изначально подготовленным.
Была бы у меня возможность, я бы с удовольствием пошел такую школу)
Мой совет — не теряйте возможности нахвататься знаний везде, где только возможно.
P.S. Тем более бесплатно
P.S.S. Тем более в востребованной специальности
Во-первых, спасибо автору. Хорошая статья, что-то для себя отметил и обязательно буду использовать.
Прошел нормальное количество собеседований, сам некоторое количество провёл сам и хочется добавить свои 5 копеек.
Мне кажется не хватает такого пункта, как наведение контактов. Часто бывает так, что кандидат волнуется, его трясёт, переживает. Представьте какого когда тебе 38 лет, а тебя собеседует пацан 23-х лет, да еще и глушит? Надо сразу настроить кандидата на благоприятную атмосферу (идею за 'smaltalk' лайк), расположить к себе человека, чтобы он психологически настроился. Да, со всеми бывает когда тебе очень нужна эта работа, но психологически тебя давят и ты не можешь уже выдать тот результат, который нужен, а ты понимаешь что ты способен на большее. Даже если человек чего-то не помнит, можно подтолкнуть его к правильному ответу, потому что информация имеет свойство вылетать из головы.
Мой личный опыт, когда я проходил собеседование и переезжал в Москву (конец апреля 2018).
2 недели, не включая выходные, каждый день по 4 собеседования.
Итого 40 компаний. Вакансия: Full-stack developer / Spark developer / Java developer
Прохождение собеседований Руководитель разработки
Количество — 16
Успешных — 9
Старший специалист / специалист
Количество — 10
Успешных — 2
PM — проекта
Количество — 7
Успешных — 5
HR
Количество — 7
Успешных — 2
За успешными я считаю свой субъективный взгляд + наличие офферов. Из общего числа получил 15 офферов (18 успешных). Откинул из успешных компании, которые хотели встретиться лично пообщаться, но у меня не было возможности всё бросить и ради компании ехать в другой город. Свои неудачные собеседования делятся на несколько категорий:
Задавили морально. Настолько в глубь капать под кандидата, я хз зачем это нужно. Одна мадам меня просто задавила вопросами, особенно бомбит до сих пор с: «Мне неважно, что вы понимайте как работает контракт между hashCode() и equals(), я хочу получить ответ как это написано в JLS». Мне просто трубку бросить хотелось, когда настолько идиотские вопросы спрашивают;
Каждое первое собеседование нового дня было слито. Хз не выспыпался я, потому что параллельно работал или просто не в настроении был, но этот факт за мной;
Личная встреча. Конечно, я всё понимаю, что рассчитывать на большую зарплату и доказать через Скайп, что ты реально тот, кто им нужен — непростая задача + многим необходимо посмотреть на человека в живую, чтобы окончательно составить портрет;
Не сошлись в стеке технологий. Зачастую видят одну технологию и считают, что ты в ней гуру. Мало того, что гуру, так еще и пытаются подсунуть свой стек, который тебе вообще никак не лежит. И есть обратная ситуация, когда я сам понимаю, что имею недостаточно практического опыта в конкретном направлении и нет смысла продолжать беседу.
Наверное это всё что хотел сказать) Главное — быть адекватным и стой, и с другой стороны. В остальном всё обязательно сложится и каждый найдет своё место :)
А нет.
Всё правильно писали:
При продолжении, получается так, что в барабане остается еще 3 пустых гнезда, которые нас устраивает, а только один следующий патрон ведёт нас к фаталу.
Соотвественно:
Поэтому, в последнее время больше склоняюсь к методологии waterfall. Так спокойно работается и каждый понимает свою зону ответственности. Лиды на своих местах, разрабы и другие на своих.
Не спорю, Scrum идеально вписывается под сплоченную команду, которая готова включатся и бросаться на любую проблему. Но когда у тебя коллектив забитых интровертов, которые хотят реализовывать только тот объем задач, который на них висит, да ещё сверху добитых бюрократией — по такой схеме невозможно работать. Да, и как описал выше, нужно выбирать методологию под задачи, а не подгонять задачи под методологию. Со стороны это жесть как весело смотрится, а работать в этом безобразие — вообще одно удовольствие.
Ну и не хватает в этом тексте то, что Scrum master обязан контролировать эти миттинги, потому что всяко без лидера — все в команде начинают разглагольствовать и эти встречи затягиваются от 40 минут до 1 часу.
Для демонстрации хода работы данного метода, для начала необходимо взять функцию z = f(x1, x2,…, xn) и выбрать любую точку M0(x10, x20,…, xn0) в n пространстве, которая зависит от числа характеристик функции. Следующим шагом идет фиксация всех точек функции в константу, кроме самой первой. Это делается для того, чтобы поиск многомерной оптимизации свести к решению поиска на определенном отрезке задачу одномерной оптимизации, то есть поиска аргумента x1.
Для нахождения значения данной переменной, необходимо производить спуск по этой координате до новой точки M1(x11, x21,…, xn1). Далее функция дифференцируется и тогда мы можем найти значение новой следующий точки с помощью данного выражения:
После нахождения значения переменной, необходимо повторить итерацию с фиксацией всех аргументов кроме x2 и начать производить спуск по новой координате до следующей новой точке M2(x11,x21,x30…,xn0). Теперь значение новой точки будет происходить по выражению:
И снова итерация с фиксацией будет повторяться до тех пор, пока все аргументы от xi до xn не закончатся. При последней итерации, мы последовательно пройдем по всем возможным координатам, в которых уже найдем локальные минимумы, поэтому целевая функция на последний координате дойдет до глобального минимума. Одним из преимуществ данного метода в том, что в любой момент времени есть возможность прервать спуск и последняя найденная точка будет являться точкой минимума. Это бывает полезно, когда метод уходит в бесконечный цикл и результатом этого поиска можно считать последнюю найденную координату. Однако, целевая установка поиска глобального минимума в области может быть так и не достигнута из-за того, что мы прервали поиск минимума (см. Рисунок 1).
Рисунок 1 – Отмена выполнения покоординатного спуска
Исследование данного метода показали, что каждая найденная вычисляемая точка в пространстве является точкой глобального минимума заданной функции, а функция z = f(x1, x2,…, xn) является выпуклой и дифференцируемой.
Отсюда можно сделать вывод, что функция z = f(x1, x2,…, xn) выпукла и дифференцируема в пространстве, а каждая найденная предельная точка в последовательности M0(x10, x20,…, xn0) будет являться точкой глобального минимума (см. Рисунок 2) данной функции по методу покоординатного спуска.
Рисунок 2 – Локальные точки минимума на оси координат
Можно сделать вывод о том, что данный алгоритм отлично справляется с простыми задачами многомерной оптимизации, путём последовательно решения n количества задач одномерной оптимизации, например, методом золотого сечения.
Ход выполнения метода покоординатного спуска происходит по алгоритму описанного в блок схеме (см. Рисунок 3). Итерации выполнения данного метода:
• Изначально необходимо ввести несколько параметров: точность Эпсилон, которая должна быть строго положительной, стартовая точка x1 с которой мы начнем выполнение нашего алгоритма и установить Лямбда j;
• Следующим шагом будет взять первую стартовую точку x1, после чего происходит решение обычного одномерного уравнения с одной переменной и формула для нахождения минимума будет, где k = 1, j=1:
• Теперь после вычисления точки экстремума, необходимо проверить количество аргументов в функции и если j будет меньше n, тогда необходимо повторить предыдущий шаг и переопределить аргумент j = j + 1. При всех иных случаях, переходим к следующему шагу.
• Теперь необходимо переопределить переменную x по формуле x (k + 1) = y (n + 1) и попытаться выполнить сходимость функции в заданной точности по выражению:
Теперь от данного выражения зависит нахождение точки экстремума. Если данное выражение истинно, тогда вычисление точки экстремума сводится к x*= xk + 1. Но часто необходимо выполнить дополнительные итерации, зависящие от точности, поэтому значения аргументов будет переопределено y(1) = x(k + 1), а значения индексов j =1, k = k + 1.
Рисунок 3 – Блок схема метода покоординатного спуска
Итого, у нас имеется отличный и многофункциональный алгоритм многомерной оптимизации, который способен разбивать сложную задачу, на несколько последовательно итерационных одномерных. Да, данный метод достаточно прост в реализации и имеет легкое определение точек в пространстве, потому что данной метод гарантирует сходимость к локальной точке минимума. Но даже при таких весомых достоинствах, метод способен уходить в бесконечные циклы из-за того, что может попасть в своего рода овраг.
Существуют овражные функции, в которых существуют впадины. Алгоритм, попав в одну из таких впадин, уже не может выбраться и точку минимума он обнаружит уже там. Так же большое число последовательных использований одного и того же метода одномерной оптимизации, может сильно отразиться на слабых вычислительных машинах. Мало того, что сходимость в данной функции очень медленная, поскольку необходимо вычислить все переменные и зачастую высокая заданная точность увеличивает в разы время решения задачи, так и главным недостатком данного алгоритма – ограниченная применимость.
Проводя исследование различных алгоритмов решения задач оптимизации, нельзя не отметить, что огромную роль играет качество данных алгоритмов. Так же не стоит забывать таких важных характеристик, как время и стабильность выполнения, способность находить наилучшие значения, минимизирующие или максимизирующие целевую функцию, простота реализации решения практических задач. Метод покоординатного спуска прост в использовании, но в задачах многомерной оптимизации, чаще всего, необходимо выполнять комплексные вычисления, а не разбиение целой задачи на подзадачи.
Данный симплекс является регулярным, а представляется как многогранник с равностоящими вершинами симплекса в N-мерном пространстве. В различных пространствах, симплекс отображается в R2-равносторонний треугольник, а в R3 — правильный тетраэдр.
Как упоминалось выше, алгоритм является развитием метода симплексов Спендли, Хекста и Химсворта, но, в отличие от последнего, допускает использование неправильных симплексов. Чаще всего, под симплексом подразумевается выпуклый многогранник с числом вершин N+1, где N – количество параметров модели в n -мерном пространстве.
Для того, чтобы начать пользоваться данным методом, необходимо определиться с базовой вершиной всех имеющихся множества координат с помощью выражения:
Самым замечательным в этом методе то, что у симплекса существуют возможности самостоятельно выполнять определенные функции:
• Отражение через центр тяжести, отражение со сжатием или растяжением;
• Растяжение;
• Сжатие.
Преимуществу среди этих свойств отдают отражению, поскольку данный параметр является наиболее опционально – функциональным. От любой выбранной вершины возможно сделать отражение относительно центра тяжести симплекса по выражению:.
где xc — центр тяжести (см. Рисунок 1).
Рисунок 1 – Отражение через центр тяжести
Следующим шагом необходимо провести расчет аргументов целевой функции во всех вершинах отраженного симплекса. После этого, мы получим полную информацию о том, как симплекс будет вести себя в пространстве, а значит и информацию о поведении функции.
Для того чтобы совершить поиск точки минимума или максимума целевой функции с помощью методов использующих симплексы, необходимо придерживаться следующей последовательности:
• На каждом шаге строиться симплекс, в каждой точке которого, необходимо произвести расчет всех его вершин, после чего отсортировать полученные результаты по возрастанию;
• Следующий шаг – это отражение. Необходимо провести попытку получить значения нового симплекса, а путём отражения, у нас получиться избавиться от нежелательных значений, которые стараются двигать симплекс не в сторону глобального минимума;
• Чтобы получить значения нового симплекса, из полученных отсортированных результатов, мы берем две вершины с наихудшими значениями. Возможны такие случаи, что сразу подобрать подходящие значения не удастся, тогда придется вернуться к первому шагу и произвести сжатие симплекса к точке с самым наименьшим значением;
• Окончанием поиска точки экстремума является центр тяжести, при условии, что значение разности между функциями имеет наименьшие значения в точках симплекса.
Алгоритм Нелдера – Мида так же использует эти функции работы с симплексом по следующим формулам:
• Функция отражения через центр тяжести симплекса высчитывается по следующему выражению:
Данное отражение выполняется строго в сторону точки экстремума и только через центр тяжести (см. Рисунок 2).
Рисунок 2 – Отражение симплекса происходит через центр тяжести
• Функция сжатия вовнутрь симплекса высчитывается по следующему выражению:
Для того, чтобы провести сжатие, необходимо определить точку с наименьшим значением (см. Рисунок 3).
Рисунок 3 – Сжатие симплекса происходит к наименьшему аргументу.
• Функция отражения со сжатием симплекса высчитывается по следующему выражению:
Для того, чтобы провести отражение со сжатием (см. Рисунок 4), необходимо помнить работу двух отдельных функций – это отражение через центр тяжести и сжатие симплекса к наименьшему значению.
Рисунок 4 — Отражение со сжатие
• Функция отражения с растяжением симплекса (см. Рисунок 5) происходит с использованием двух функций – это отражение через центр тяжести и растяжение через наибольшее значение.
Рисунок 5 — Отражение с растяжением.
Чтобы продемонстрировать работу метода Нелдера – Мида, необходимо обратиться к блок схеме алгоритма (см. Рисунок 6).
Первостепенно, как и в предыдущих примерах, нужно задать параметр искаженности ε, которая должна быть строго больше нуля, а также задать необходмые параметры для вычисления α, β и a. Это нужно будет для вычисления функции f(x0), а также для построения самого симплекса.
Рисунок 6 — Первая часть метода Нелдера — Мида.
После построения симплекса необходимо произвести расчет всех значений целевой функции. Как и было описано выше про поиск экстремума с помощью симплекса, необходимо рассчитать функцию симплекса f(x) во всех его точках. Далее производим сортировку, где базовая точка будет находиться:
Теперь, когда базовая точка рассчитана, а также и все остальные отсортированы в списке, мы производим проверку условия достижимости по ранее заданной нами точности:
Как только данное условие станет истинным, тогда точка x(0) симплекса будет считаться искомой точкой экстремума. В другом случае, мы переходим на следующий шаг, где нужно определить новое значение центра тяжести по формуле:
Если данное условие выполняется, тогда точка x(0) будет являться точкой минимума, в противном случае, необходимо перейти на следующий шаг в котором необходимо произвести поиск наименьшего аргумента функции:
Из функции необходимо достать самую минимальное значение аргумента для того, что перейти к следующему шагу выполнения алгоритма. Иногда случается проблема того, что несколько аргументов сразу имеют одинаковое значение, вычисляемое из функции. Решением такой проблемы может стать повторное определение значения аргумента вплоть до десятитысячных.
После повторного вычисления минимального аргумента, необходимо заново сохранить новые полученные значения на n позициях аргументов.
Рисунок 7 — Вторая часть метода Нелдера — Мида.
Вычисленное из предыдущей функции значение необходимо подставить в условие fmin < f(xN). При истинном выполнении данного условия, точка x(N) будет являться минимальной из группы тех, которые хранятся в отсортированном списке и нужно вернуться к шагу, где мы рассчитывали центр тяжести, в противном случае, производим сжатие симплекса в 2 раза и возвращаемся к самому началу с новым набором точек.
Исследования данного алгоритма показывают, что методы с нерегулярными симплексами (см. Рисунок 8) еще достаточно слабо изучены, но это не мешает им отлично справляться с поставленными задачами.
Более глубокие тесты показывают, что экспериментальным образом можно подобрать наиболее подходящие для задачи параметры функций растяжения, сжатия и отражения, но можно пользоваться общепринятыми параметрами этих функций α = 1/2, β = 2, γ = 2 или α = 1/4, β = 5/2, γ = 2. Поэтому, перед тем как отбрасывать данный метод для решения поставленной задачи, необходимо понимать, что для каждого нового поиска безусловного экстремума, нужно пристально наблюдать за поведением симплекса во время его работы и отмечать нестандартные решения метода.
Рисунок 8 — Процесс нахождения минимума.
Статистика показала, что в работе данного алгоритма существует одна из наиболее распространенных проблем – это вырождение деформируемого симплекса. Это происходит, когда каждый раз, когда несколько вершин симплекса попадают в одно пространство, размерность которого не удовлетворяет поставленной задачи.
Таким образом, размерность во время работы и заданная размерность закидывают несколько вершин симплекса в одну прямую, запуская метод в бесконечный цикл. Алгоритм в данной модификации еще не оснащен способом выйти из такого положения и сместить одну вершину в сторону, поэтому приходится создать новый симплекс с новыми параметрами, чтобы такого в дальнейшем не происходило.
Еще одной особенностью обладает данный метод – это некорректной работой при шести и более вершинах симплекса. Однако, при модификации данного метода, можно избавиться от этой проблемы и даже не потерять при этом скорости выполнения, но значение выделяемой памяти заметно повысится. Данный метод можно считать циклическим, поскольку он полностью основан на циклах, поэтому и замечается некорректная работа при большом количестве вершин.
Алгоритм Нелдера – Мида по праву можно считать одним из наилучших методов нахождения точки экстремума с помощью симплекса и отлично подходит для использования его в различные рода инженерных и экономических задачах. Даже не смотря на цикличность, количество памяти он использует очень малое количество, по сравнение с тем же методом покоординатного спуска, а для нахождения самого экстремума требуется высчитывать только значения центра тяжести и функции. Небольшое, но достаточное, количество комплексных параметров дают этому методу широкое использование в сложных математических и актуальных производственных задачах.
Симплексные алгоритмы – это край, горизонты которого еще мы не скоро раскроем, но уже сейчас они значительно упрощают нашу жизнь своей визуальной составляющей.
P.S. Текст полностью мой. Надеюсь кому-нибудь данная информация будет полезной.
P.S.S. Сорри, за косяки в тексте и корявые формулы. Возможности скинуть нормально нет :(
Ааа, ну да… Я же с деревни…
На самом деле круто, что сейчас имеется такая возможность получить бесплатно знания в таком возрасте. Мне нравится современный подход того, что компании сами себе кадров выращивают, путём проведения таких курсов (не буду говорить о качестве, судите сами). И даже если не подходишь ты для этой компании после окончания, у тебя на руках остаётся багаж знаний, который ты можешь применить в другой компании, где на Junior-позицию приходишь изначально подготовленным.
Была бы у меня возможность, я бы с удовольствием пошел такую школу)
Мой совет — не теряйте возможности нахвататься знаний везде, где только возможно.
P.S. Тем более бесплатно
P.S.S. Тем более в востребованной специальности
Спасибо Samsung за такую возможность и удачи :)
Прошел нормальное количество собеседований, сам некоторое количество провёл сам и хочется добавить свои 5 копеек.
Мне кажется не хватает такого пункта, как наведение контактов. Часто бывает так, что кандидат волнуется, его трясёт, переживает. Представьте какого когда тебе 38 лет, а тебя собеседует пацан 23-х лет, да еще и глушит? Надо сразу настроить кандидата на благоприятную атмосферу (идею за 'smaltalk' лайк), расположить к себе человека, чтобы он психологически настроился. Да, со всеми бывает когда тебе очень нужна эта работа, но психологически тебя давят и ты не можешь уже выдать тот результат, который нужен, а ты понимаешь что ты способен на большее. Даже если человек чего-то не помнит, можно подтолкнуть его к правильному ответу, потому что информация имеет свойство вылетать из головы.
Мой личный опыт, когда я проходил собеседование и переезжал в Москву (конец апреля 2018).
2 недели, не включая выходные, каждый день по 4 собеседования.
Итого 40 компаний. Вакансия: Full-stack developer / Spark developer / Java developer
Прохождение собеседований
Руководитель разработки
Старший специалист / специалист
PM — проекта
HR
За успешными я считаю свой субъективный взгляд + наличие офферов. Из общего числа получил 15 офферов (18 успешных). Откинул из успешных компании, которые хотели встретиться лично пообщаться, но у меня не было возможности всё бросить и ради компании ехать в другой город. Свои неудачные собеседования делятся на несколько категорий:
Наверное это всё что хотел сказать) Главное — быть адекватным и стой, и с другой стороны. В остальном всё обязательно сложится и каждый найдет своё место :)
Всё правильно писали:
При продолжении, получается так, что в барабане остается еще 3 пустых гнезда, которые нас устраивает, а только один следующий патрон ведёт нас к фаталу.
Соотвественно:
При прокрутке мы возвращаемся к вероятности:
Мне кажется это очевидны.
Просто включаем обратный перебор:
4 итерация:
3 итерация:
2 итерация:
1 итерация:
Ответ 15.
Не знаю как вы мистически больше получаете)
Про револьвер:
Сидим до выстрела = вероятность 2/6 = 1/3 шанс быть убитым;
Выживаем.
Просим еще раз стрелять = 2/5 шанс ~ 40%
Крутим повторно = 1/3 шанс ~ 33.3%