Продолжаю цикл статей «Оптимизация на примере». В данной статье сравниваются два эвристических алгоритма на избитой симметричной задаче коммивояжера. Сегодня чуть углубимся в данную тему и разберем определенную модификацию муравьиного алгоритма.

Данная статья не доказывает какой метод лучше в общем, так как у обоих алгоритмов есть множество модификаций, а также множество потенциальных модификаций. Здесь всего лишь определяется победитель на определенной модификации и на определенных параметрах. Цель же данной статьи — расширение кругозора читателей в области дискретной оптимизации, и, надеюсь, предложения по улучшению работы обоих алгоритмов.

Модификация муравьиного алгоритма выбрана ACS (Ant Colony System), которую предложили Марко Дориго и Лука Гамбарделла в 1997 году. Главные отличия от AS (Ant System) это:

1) задается баланс между самым привлекательным городом, и выбором как в обычном AS

arg max{[τ(r,u)]^α*[ω(r,u)]^β} если q <= q0 (Формула 1)
u ϵ Jk«r»

В обратном случае выбираем переход по AS

, где [τ(r,u)] — уровень феромона на ребре (r,u), [ω(r,u)] — вес обратный расстоянию на ребре (r,u), β — регулируемый параметр, чем он выше, тем алгоритм будет склонен выбирать город, имеющий меньшее расстояние, α — равна 1, q — случайно выбранное число, q0 — вероятность выбора того, что переход из одной вершины в другую будет идти по формуле 1, u — города, еще не посещенные

2) помимо глобального обновления феромонов происходит еще и локальное. Уровень феромонов меняется при прохождении каждого муравья на итерации (тут ближе к естественной среде обитания муравьев)

τ(r,s)=(1-p)*τ(r,s)+p*τ0 (Формула 2)

, где p — уровень локального обновления, τ0 = значение начального феромона, который вычисляется следующим образом: τ0 = (n*Lnn)^-1, где Lnn — приблизительное оптимальное значение, которое может быть получено другим методом оптимизации.

3) при глобальном обновлении феромона, добавление происходит только к ребрам, либо лучших со времени начала работы алгоритма (глобальных лучших), либо к ребрам лучших на итерации (локальных лучших). Я применил на ребра глобальных лучших.

τ(r,s)=(1-e)*τ(r,s)+e*(Lbest^-1) (Формула 3)

, где e — уровень глобального обновления, Lbest — лучшая длина маршрута (самый короткий), либо на k-ой итерации, либо глобальный лучший.

Данные модификации дали значительную производительность алгоритму. Метод отжига оставил таким же, как и в прошлой статье, за исключением увеличения скорости. Спасибо читателю zartdinov за простое и очень эффективное предложение по увеличению скорости.

Теперь будем сравнивать задачи на известных координатах, таких как Oliver30, Eli51, Eli101, на которых найдено лучшее решение. Также выведем приближенные формулы временной зависимости двух алгоритмов от количества городов, и, наконец, попытаемся определить победителя на сегодня с учетом всех этих факторов.

Начнем с задачи Oliver30 лучшее решение — 423,7406

Параметры ACS:

• Количество итераций (поколений) — 2500*
• Количество муравьев в поколении — 7*
• Количество городов — 30*
• альфа (коэф. ориентации на феромоны) — 1
• бета (коэф. ориентации на длину пути) — 2
• p (коэф. обновления феромонов локальное) — 0,09
• e (коэф. обновления феромонов глобальное) — 0,09
• q (коэф. выбора самого привлекательного города) — 0,9
• начальное расположение муравьев — случайный

* — изменяемые параметры от размерности задачи

Пару слов о количестве муравьев. Ошибкой будет полагать, что чем больше муравьев, тем лучше. При большом количестве муравьев в колонии производительность значительно падает. Во-первых, сильно увеличивается время работы алгоритма. Во-вторых, происходит переизбыток феромонов, что приводит к аналогии в естественной среде, именуемой кругом смерти муравьев. Таким образом, алгоритм застревает на локальном оптимуме.

Точного определения количества муравьев в колонии пока нет, есть приблизительное вычисление как в [1]. Тут же я старался найти точку оптимума, при которой увеличение количества муравьев не улучшало решение, а их уменьшение снижало результат. Также, если упрощенно, экспериментировал с одной колонией муравьев на определенных итерациях. Как только средний уровень феромона начинал повышаться — брал это за основу оптимального количества муравьев.

Итак результаты задачи Oliver30:

Пара графиков:

Четвертый график показывает, что алгоритм продолжает искать альтернативные пути, не останавливаясь на достигнутом. При увеличении числа муравьев до 50-100 разброс средних дистанций поколения сокращается в пределах 20-30, что приводит к застреванию.

Полный перебор вариантов для симметричной задачи коммивояжера составляет (n-1)!/2 или
4 420 880 996 869 850 977 271 808 000 000 для данной задачи

100% результат, отличная работа ACS

Посмотрим на метод отжига.

Параметры:

• Количество городов — 30*
• Начальная температура — 35 000*
• Конечная температура — 0,1
• Формула температуры — начальную температуру / k-ую итерацию
• Число итераций — 350 000*
• Функция вероятности принятия — exp(-ΔE/T)
• Определение потенциального маршрута (порождающего семейства) — разворот части вектора (текущего маршрута) от двух случайно выбранных чисел равномерным распределением

* — изменяемые параметры от размерности задачи

Результаты:

Как по времени, так и по качеству на 30 городах выигрывает с большим отрывом ACS. Тестировал два алгоритма не только на данной задаче, но и на других 30 — ACS безусловно побеждает простой метод отжига.

Теперь задача на Eil51 на 51 город, лучшее решение 426, 7000 итераций, кол-во муравьев 9

Пара графиков:

На 4-ом графике добавлена линия регрессии. Вообще, задача Eil51 во многих зарубежных исследованиях тестировалась на куда большем числе итераций. Может быть поэтому глобальный оптимум не был найден, честно говоря, также тестировал на больших итерациях и максимум что был найден это 427.

Пользуясь случаем давайте посмотрим «в реальном режиме» на изменение феромонов от числа итераций, мне данная картинка довольно понравилась.

Без глобального обновления и с добавлением общего коэффициента испаряемости как в AS, для большего эффекта.

Смотрим на метод отжига при 2 500 000 итераций

Довольно неплохой результат, но все же ACS еще впереди.

Теперь задача Eil101 на 101 город, лучшее расстояние 629, 9000 итераций, кол-во муравьев 11

Пара графиков:

Здесь 9000 итераций, довольно мало для 100-ой задачи, однако сравним данный результат с отжигом на том же временном интервале при 7 000 000 итераций.

Довольно стабильный результат, лучше чем показал ACS. Но ACS позволяет сделать поиск более управляемым, чем обычный отжиг (хотя в последнем как минимум можно было бы ввести критерий остановки, но об этом в следующих статьях). Поэтому сегодня до 100 вершин по всем параметрам выигрывает ACS. Более того, сильно ускорить метод отжига, скорее всего, больше не удастся, в то время как оптимизировать код ACS еще как возможно. (В данном случае код плохо оптимизирован).

Повторюсь, что главный плюс ACS (как и других модификаций муравьиного алгоритма), в поиске глобального оптимума, при бесконечном числе итераций вероятность нахождения глобального лучшего стремится к 1. Вопрос конечно же во времени. Быстро, но примерно, либо долго, но точно. Поэтому предлагаю построить зависимость времени (при одинаковых числах итерациях на каждом алгоритме) от количества городов.

Количество итераций ACS — 10 000, муравьев — 10;
Количество итераций SA — 7 000 000.

Ого! Видим, что метод отжига занимает константное время, вне зависимости от количества вершин. Построив регрессию, определяем временную сложность для ACS.

t = 0.0044939x^2 + 0.72097x + 3.8225 (Формула 4)

, где x — количество городов, t — время выполнения ACS

Если же два алгоритма до 100 вершин примерно шли вровень как по времени, так и по качеству (с небольшим опережением ACS), то совсем грубо можно предположить что на 1000 городах, в 10 000 итераций на ACS и в 7 000 000 итераций на SA результат должен быть схожем.

Проверим.

ACS 200 городов (случайные города), время — 311,54 с.

SA 200 городов (те же что и выше), время 103,19 с.

Запустил последовательно. Какова вероятность того, что оба покажут один результат? Интересный момент вышел, может и сотые доли совпали? Но этого уже не узнать ни Вам, ни мне)

Вообщем по серии тестов, и по 300 вершин выходит примерно одинаковый результат, с ростом же выше в плюс уходит метод отжига.

При временном ограничении и количеством вершин больше ста лучше проявляет себя простой метод отжига нежели ACS. Повторюсь, что именно ACS, а не MMAS, ACS local search, либо иная модификация.

Но иногда нужно найти именно глобальный оптимум, тут мало кто может потягаться с Муравьиными алгоритмами.

Теперь пару слов об ускорении метода имитации отжига.
Как подсказал читатель zartdinov, то, конечно же, не стоит пересчитывать на каждой итерации маршрут.

Есть условный маршрут:

1 2 3 4 5 6 7 8 9

Случайно отобрали два числа, пусть будет (2,5)

Теперь достаточно посчитать расстояние (1,2) и (5,6) и посчитать расстояние (1,5) и (2,6)

Однако на асимметричной задаче так не пройдет.

Благодаря этому количество городов не влияет на время выполнения алгоритма, плюс убрал функции fliplr, которые занимали приличное количество времени. Также были сформированы заранее массивы случайных чисел. Все это в разы увеличило скорость алгоритма с предыдущей статьей.

Также одному из читателей интересен был бы результат при перестановке двух вершин, а не инвертировании пути между ними. Давайте посмотрим результат на 101 городах Eil101 на 1 000 000 итераций.

Инверсия пути значительно лучше.

Много чего еще хотелось бы показать и рассказать, но и так статья выходит достаточно длинной. В следующих публикациях «наворотим» метод отжига, попытаемся сделать его более управляемым. Также, возможно, рассмотрим другие модификации муравьиного алгоритма, погрузимся чуть глубже, а потом уже перейдем к генетике.

Сейчас предлагаю посмотреть, как безусловный лидер (пока до 100 вершин) идет к глобальному лучшему пути.

Также, предлагаю посмотреть на лидера по времени и количеству вершин SA, который выдает приближенное решение 1000 вершин за 4 000 000 итераций в 34 секунды. Если в прошлой статье 2 000 000 итераций для 500 вершин составляло 90 секунд, то сейчас всего 14.6!

Как-то так. Исходники с комментариями прилагаю. Старался сохранять баланс между читаемостью кода и скоростью. Советую их просмотреть, даже тем кто совсем не знаком с MatLab-ом, так как это сильно поможет вникнуть в суть алгоритмов.

% метод отжига ( на примере задачи коммивояжера )  %-------------------------------------------------------------------------- tic  % clearvars -except cities clearvars  % -----------------------------ИТЕРАЦИИ------------------------------------ % кол-во итераций m = 1000000; % -----------------------------ПАРАМЕТРЫ----------------------------------- % начальная температура Tstart = 100000;  % конечная температура Tend = 0.1;  % начальная температура для вычислений T = Tstart;  % расстояние S = inf;  % количество городов n = 500;  % рисовать графику? g = 1;  % --------------------------------ПАМЯТЬ-----------------------------------  % матрица расстояний dist = zeros(n,n);   % -------------------------------------------------------------------------  % генерация городов (x,y) cities = rand(n,2)*100;  % формируем заранее список случайных чисел RANDONE = rand(m,1);  % формируем два случайных города заранее D = randi(n,m,2);  % задаем случайный маршрут ROUTE = randperm(n);  % создаем матрицу расстояний for i = 1:n          for j = 1:n                  % dist ( расстояния )         dist(i,j) = sqrt((cities(i,1) - cities(j,1))^2 + ...            (cities(i,2) - cities(j,2))^2);                         end      end   % поехали оптимизировать, время от кол-ва итераций for k = 1:m               % сбрасываем потенциальное расстояние     Sp = 0;          % здесь условие создания потенциальных маршрутов, ROUTEp -     % потенциальный маршрут          % потенциальный маршрут     ROUTEp = ROUTE;      % два случайных города     transp = D(k,[1,2]);          % если тут не понятно, посмотрите код из первой части статьи.          if transp(1) < transp(2)                  if transp(1) ~= 1 && transp(2) ~= n                          S = dist(ROUTE(transp(1)-1),ROUTE(transp(1))) + ...                 dist(ROUTE(transp(2)),ROUTE(transp(2)+1));                      elseif transp(1) ~= 1 && transp(2) == n                          S = dist(ROUTE(transp(1)-1),ROUTE(transp(1))) + ...                 dist(ROUTE(transp(2)),ROUTE(1));                      elseif transp(1) == 1 && transp(2) ~= n                          S = dist(ROUTE(end),ROUTE(transp(1))) + ...                  dist(ROUTE(transp(2)),ROUTE(transp(2)+1));                       end                             else                        if transp(2) ~= 1 && transp(1) ~= n                          S = dist(ROUTE(transp(2)-1),ROUTE(transp(2))) + ...                  dist(ROUTE(transp(1)),ROUTE(transp(1)+1));                      elseif transp(2) ~= 1 && transp(1) == n                          S = dist(ROUTE(transp(2)-1),ROUTE(transp(2))) + ...                  dist(ROUTE(transp(1)),ROUTE(1));                      elseif transp(2) == 1 && transp(1) ~= n                          S = dist(ROUTE(end),ROUTE(transp(2))) + ...                  dist(ROUTE(transp(1)),ROUTE(transp(1)+1));                       end             end       %-------------------------------------------------------------------------           if transp(1) < transp(2)         ROUTEp(transp(1):transp(2)) = ROUTEp(transp(2):-1:transp(1));                  if transp(1) ~= 1 && transp(2) ~= n                          Sp = dist(ROUTEp(transp(1)-1),ROUTEp(transp(1))) + ...                 dist(ROUTEp(transp(2)),ROUTEp(transp(2)+1));                      elseif transp(1) ~= 1 && transp(2) == n                          Sp = dist(ROUTEp(transp(1)-1),ROUTEp(transp(1))) + ...                 dist(ROUTEp(transp(2)),ROUTEp(1));                      elseif transp(1) == 1 && transp(2) ~= n                          Sp = dist(ROUTEp(end),ROUTEp(transp(1))) + ...                  dist(ROUTEp(transp(2)),ROUTEp(transp(2)+1));                                          end                             else                  ROUTEp(transp(2):transp(1)) = ROUTEp(transp(1):-1:transp(2));                  if transp(2) ~= 1 && transp(1) ~= n                          Sp = dist(ROUTEp(transp(2)-1),ROUTEp(transp(2))) + ...                  dist(ROUTEp(transp(1)),ROUTEp(transp(1)+1));                      elseif transp(2) ~= 1 && transp(1) == n                          Sp = dist(ROUTEp(transp(2)-1),ROUTEp(transp(2))) + ...                  dist(ROUTEp(transp(1)),ROUTEp(1));                      elseif transp(2) == 1 && transp(1) ~= n                          Sp = dist(ROUTEp(end),ROUTEp(transp(2))) + ...                  dist(ROUTEp(transp(1)),ROUTEp(transp(1)+1));                                   end              end      %--------------------------------------------------------------------------         if Sp < S         ROUTE = ROUTEp;         iter = k;                               else          % вычисляем вероятность перехода         P = exp((-(Sp - S)) / T);                     if RANDONE(k) <= P                 ROUTE = ROUTEp;                                       end              end          	% уменьшаем температуру         T = Tstart / k;          % проверяем условие выхода         if T < Tend             break;         end;       end  % рисуем графику citiesOP(:,[1,2]) = cities(ROUTE(:),[1,2]); plot([citiesOP(:,1);citiesOP(1,1)],[citiesOP(:,2);citiesOP(1,2)],'-r.')  msgbox ('Выполнено!')  % очищаем переменые clearvars -except cities ROUTE S iter  % смотрим время toc 

% муравьиный алгоритм ( на примере задачи коммивояжера )  % ------------------------------------------------------------------------- tic  % clearvars -except cities clearvars   % ------------------------------ИТЕРАЦИИ-----------------------------------  % кол-во итераций ( поколений ) age = 2000;  % кол-во муравьев в поколении countage = 10;  % кол-во городов n = 50;  % ------------------------------ПАРМЕТРЫ-----------------------------------  % альфа - коэффициент запаха, при 0 будем ориентироваться только на % кратчайший путь  a = 1;   % бета - коэффициент расстояния, при 0 будем % ориентироваться только на оставляемый запах b = 2;  % коэффициент обновления, глобальное e = 0.1;  % коэффициент обновления, локальное p = 0.1;  % количество выпускаемых феромонов  Q = 1;  % баланс между лучшим городом и как в AS q = 0.9;  % начальный феромон  ph = Q/(n*2000);  % -------------------------------ПАМЯТЬ------------------------------------ % матрица расстояний dist = zeros(n,n);   % матрица обратных расстояний returndist = zeros(n,n);   % матрица маршрута муравьев в одном поколении ROUTEant = zeros(countage,n);  % вектор расстояний муравьев в одном поколении DISTant = zeros(countage,1);   % вектор лучших дистанций на каждой итерации bestDistVec = zeros(age,1);  % лучший начальный маршрут bestDIST = inf;   % оптимальные маршруты ROUTE = zeros(1,n+1);  % перестановка городов без повторений ( для выхода муравьев ) RANDperm = randperm(n);  % матрица вероятностей P = zeros(1,n);  % максимальное значение вероятности val = zeros(1);  % присваем номер города getcity = zeros(1);  % индекс максимального значения вероятности indexP = zeros(1);  % максимальное minDISTiterration = zeros(1);  % -------------------------------------------------------------------------  % генерация городов (x,y) cities = rand(n,2)*100;  % матрица начальных феромонов tao = ph*(ones(n,n)); tao(logical(eye(size(tao)))) = 0;  % создаем матрицу расстояний и матрицу обратных расстояний for i = 1:n          for j = 1:n                  % dist ( расстояния )         dist(i,j) = sqrt((cities(i,1) - cities(j,1))^2 + ...            (cities(i,2) - cities(j,2))^2);                      % nn ( обратные расстояния )             if i ~= j             returndist(i,j) = 1/sqrt((cities(i,1) - cities(j,1))^2 + ...                 (cities(i,2) - cities(j,2))^2);              end                  end      end  % итерации for iterration = 1:age               % муравьи ( одно поколение)     for k = 1:countage              % ****************** НАЧАЛЬНОЕ РАСПОЛОЖЕНИЕ МУРАВЬЕВ ******************     % выбирайте какой нужно          % каждый муравей располагается случайно           ROUTEant(k,1) = randi([1 n]);          % с каждого города выходит один муравей ( без совпадений ), кол-во     % городов и кол-во муравьев в поколении должны быть равны %       ROUTEant(k,1) = RANDperm(k);          % с конкретного города выходят все муравьи в данном случа с 1-ого %       ROUTEant(k,1) = 1;  % тут маршрут первому поколению задаем либо произвольный, либо с каждого % города разный, либо с одного города все, а следующее поколение выходит по % концам первых  %     if iterration == 1 %       ROUTEant(k,1) = randi([1 n]); % %       ROUTEant(k,1) = RANDperm(k); % %     ROUTEant(k,1) = 1; %     else %       ROUTEant(k,1) = lastROUTEant(k);   %     end          % *********************************************************************          % путь каждого муравья, начиная со второго, так как первый выбран     for s = 2:n            % полуаем индекс выбранного города         ir = ROUTEant(k,s-1);           % вероятность посещения городов ( числитель ) , в числителе у нас         % следующее: tao^a*(1/S)^b          % 1/S -это returndist.                   % поскольку данное значение будет повторяться (кол-во муравьев * на         % колонию * кол-во городов) раз, то еще один цикл писать не выгодно,         % скорость работы при таких вычислениях падает. Поэтому написал в          % этом моменте векторно. На обычном языке будет так:           %         for c = 1:n              %             P(1,c) = tao(ir,c).^a * returndist(ir,c).^b;           %         end          P = tao(ir,:).^a .* returndist(ir,:).^b;         % получили числители (в формуле вероятности перехода к k-ому городу)         % для n городов, однако в некоторых мы уже побывали, нужно исключить         % их                  % проставляем нули в числитель туда, где уже были, чтобы         % вероятность перехода была 0, следовательно в сумме знаменателя         % формулы данный город учитываться не будет             P(ROUTEant(k,1:s-1)) = 0;                  % смотрим в какой город осуществляется переход         RANDONE = rand;                  if RANDONE <= q             [val, getcity] = max(P);         else             % получаем вероятности перехода ( сумма строк должна быть = 1 )             P = P ./ sum(P);             getcity = find(cumsum(P) >= RANDONE, 1, 'first');         end                  % присваем s-ый город в путь k-ому муравью         ROUTEant(k,s) = getcity;      end              % получаем маршрут k-ого муравья     ROUTE = [ROUTEant(k,1:end),ROUTEant(k,1)];          % сброс длины     S = 0;          % вычисляем маршрут k-ого муравья     for i = 1:n         S = S + dist(ROUTE(i),ROUTE(i+1));     end          % путь k-ого муравья, массив дистанций k-ых муравьев age-ого поколения     DISTant(k) = S;          % присваевыем лучший маршрут и S          if DISTant(k) < bestDIST         bestDIST = DISTant(k);         bestROUTE = ROUTEant(k,[1:end,1]);          iter = iterration;     end          % вектор "последних" городов k-ых муравьев ( выбирается для старта     % муравьев нового поколения с тех городов, где закончили путь     % предыдущее поколение)          % lastROUTEant = ROUTEant(1:end,end);          % локальное обновление феромона, после  каждого муравья     for tL = 1:n          xL = ROUTE(tL);         yL = ROUTE(tL+1);          % считаем новый феромон         tao(xL,yL) = (1-p)*tao(xL,yL) + p*ph;         tao(yL,xL) = (1-p)*tao(yL,xL) + p*ph;              end             end % --------------------------ГЛОБАЛЬНОЕ ОБНОВЛЕНИЕ--------------------------      % Испаряем феромоны "старого" пути е - коэффициент испарения          tao(tao < 2.500000000000000e-150) = 2.500000000000000e-150;              % для каждого города         for t = 1:n                          xG = bestROUTE(t);             yG = bestROUTE(t+1);                          % считаем новый феромон             tao(xG,yG) = tao(xG,yG) + e*(Q/bestDIST);              tao(yG,xG) = tao(yG,xG) + e*(Q/bestDIST);                      end          end   % строим графику citiesOP(:,[1,2]) = cities(bestROUTE(:),[1,2]); plot([citiesOP(:,1);citiesOP(1,1)],[citiesOP(:,2);citiesOP(1,2)],'.r-')  disp (num2str(bestDIST))  msgbox ('Выполнено!')  clearvars -except cities bestDIST bestROUTE iter  toc 

Спасибо за внимание. До новых встреч.

Статьи зарубежных авторов:

[1] — M. Dorigo, L. M. Gambardella, Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem // IEEE Transactions on Evolutionary Computation Vol. 1, 1, стр. 53-66, 1997 г.

[2] T. Stützle, H. Hoos, “MAX-MIN Ant System and local search for the traveling salesman problem” // IEEE International Conference on Evolutionary Computation, стр. 309-314, 1997 г.

[3] T. Stützle, M. López-Ibáñez, P. Pellegrini, M. Maur, M. de Oca, M. Birattari, Michael Maur, M. Dorigo, “Parameter Adaptation in Ant Colony Optimization” // Technical Report, IRIDIA, Université Libre de Bruxelles, 2010 г.
ссылка на оригинал статьи https://habrahabr.ru/post/314056/

Явная расовая сегрегация в США уже как несколько десятков лет была преодолена, а многочисленные правозащитники и борцы с расовой дискриминацией почти стерли грань между «белыми» и «цветными».

Но не в Facebook. Ads-система социальной сети предлагает рекламодателю настроить таргетинг не только по общепринятым параметрам пола, возраста, места жительства или интересов, но еще и по расовой принадлежности потенциального клиента.

Расовые разграничения в Facebook спрятаны за политкорректным термином «Этническая принадлежность», которая, исходя из слов представителей компании, формируется исходя из активности, предпочтений и прочей информации со страницы пользователя.

Согласно Ads-площадке Facebook, «этническая принадлежность» работает только в случае с США. При указании другого региона или страны настройки детального таргетинга не изменятся.

Всего предлагается фильтровать потребителей по комбинированному расово-языковому признаку. При этом в списке представлены только «цветные» этнические группы. По всей видимости, белый человек является целевой аудиторией по умолчанию.

На удивление, точнее всего рекламу можно настроить для латиносов — испаноязычные мигранты разделены на три категории: англоязычные, испаноязычные и билингвисты.

И, на первый взгляд, ничего расистского в подобных настройках таргетинга нет. Однако, журналист ресурса propublica наткнулась на объявление о продаже охотничьего дома на Facebook, в настройках которого была полностью исключена вся «цветная» аудитория:

Проблема в том, что согласно законодательству США ограничивать в возможности покупки жилья по расовому признаку запрещается. Акт о гражданских правах за 1968 год гласит:

запрещается создавать, печатать публиковать или призывать изготовить, распечатать или опубликовать любое уведомление, заявление или рекламу в отношении продажи или сдачи в аренду жилого помещения, в котором указывается любое предпочтение, ограничение или дискриминация по признаку расы, цвета кожи, религии, пола, инвалидности, семейного статуса или национального происхождения.

Нарушение данного закона может повлечь за собой крупные штрафы. Кроме этого Facebook рискует стать целью SJW (Social Justice Warriors) — агрессивно настроенной категории людей, которые под видом борьбы с неравенством и социальной несправедливостью устраивают массовые «травли» отдельных людей и целых компаний, если они, по их мнению, как-то связаны с расизмом или дискриминацией по какому-либо признаку.

Facebook утверждает, что их система таргетинга не может использоваться как инструмент дискриминации или притеснения кого-либо.

«Мы принимаем оперативные меры, когда определяем, что объявления нарушают нашу политику», заявил Стив Саттерфилд, менеджер по вопросам неприкосновенности частной жизни и соблюдения государственной политики в Facebook. Но комментировать факт того, что объявление, скриншот которого приложен выше, было одобрено в течение всего пятнадцати минут, социальная сеть отказалась.
ссылка на оригинал статьи https://geektimes.ru/post/282076/

    Добрый день, Хабр! 8 октября 2016 года в Москве (а 9 октября в Санкт-Петербурге) проходило весьма любопытное событие под названием «Testathon». Организаторы рекламировали его как «первый в России международный хакатон для тестировщиков». Несмотря на изначально настороженное отношение (до этого я был только на одном real-life хакатоне по геймдеву, и было это достаточно плохо), я все-таки решился посетить московский этап «Тестатона». В итоге — поучаствовал во всех этапах соревнований (и даже кое-что выиграл) и я хочу сказать, что оно того действительно стоило.
    Сегодня я подробно расскажу о том, как здорово все это было (соблюдая все подписанные NDA, конечно), чтобы в случае возвращения этих замечательных ребят в Россию больше людей смогли победить свой здравый скептицизм. Если вы принципиально не участвуете в хакатонах (то есть ваш девиз по жизни «поспешишь — людей насмешишь»), то можете просто оценить историю об одном необычном и крайне запоминающемся дне моей жизни.

Что это такое?

    «Тестатон» (http://testathon.co) — это мероприятие формата хакатон, организуемое крауд-тестинг компанией Global App Testing (https://globalapptesting.com/) в партнерстве с крупными компаниями-разработчиками софта, в числе которых Spotify, Dropbox, Facebook, Uber и другие. Как можно догадаться из названия, особенностью этого хакатона является то, что вместо скоростной разработки софта здесь проводится его скоростное тестирование. Московский этап именовался Chapter 9, из чего следовало, что определенный опыт в проведении таких мероприятий у них уже есть. Ранее «Тестатоны» проходили в Великобритании, Нигерии, ЮАР и других странах, т.е. ребята явно подходят к своей «международности» очень основательно.

Регистрация

    Узнал о я «Тестатоне» от друга-тестировщика благодаря маленькой заметке на Хабре. Нигде больше информации о нем я не заметил (только в паре небольших QA-сообществ, и то уже достаточно поздно), поэтому изначально заподозрил мелкокалиберность этого мероприятия. Но мы с товарищем «за любую движуху», поэтому решили зарегистрироваться.
    Форма регистрации достаточно подробно расспрашивала об опыте работы и соответствующих навыках, а это означало, что участников будут отбирать — это был хороший знак. Помимо всего прочего форма интересовалась, сколько мобильных устройств я принесу с собой (сами организаторы никаких девайсов не предоставляют) и сообщала, что участнику, который принесет больше всего девайсов (а также тому, кто принесет самый древний работающий девайс), полагается отдельный приз. Будто бы совсем не относится к теме мероприятия, зато необычно.
    Через несколько дней регистрация закрылась, и мне пришло подтверждение об участии. Товарищу сначала пришло письмо о занесении в waiting list (на самом мероприятии нам сообщили, что в нём осталось более 150 человек), но достаточно быстро его перенесли в основной состав.
    За несколько дней до начала пришло информационное письмо, которое, что удивительно, практически не несло полезной информации. Оно содержало в себе «советы» победителей прошлых Тестатонов, которые выглядели художественным перепечатыванием самых основ работы тестировщика: «Рассматривайте приложение с разных точек зрения, заготовьте в своей голове несколько персонажей и подумайте, как бы они пользовались этим приложением…» После его прочтения осталось странное чувство неопределенности: ведь мы действительно собирались пойти на ивент, не имея ни малейшего представления о том, что будет там происходить. К тому же подобный «метафизический» подход к тестированию я люблю не больше, чем строго методологический. Единственный действительно важный пункт говорил о том, что тестировать мы будем исключительно мобильные приложения, а ноутбуки нам будут нужны только для использования баг-трекера.

Начало

    И вот, одолжив несколько тестовых телефонов на работе (спасибо, Саша), мы отправились в путь. Тестатон проходил в крупном бизнес-центре Silver City на Серебрянической набережной, очень комфортной и уютной площадке. Почти без задержек, в 9 часов утра началась регистрация c проверкой документов и подписанием NDA. Внутри нам предложили разделиться на команды (11 команд по 5 человек) в вольном порядке и занять соответствующие столы. Здесь некоторых участников ожидал сюрприз — основным языком мероприятия является английский. То есть никто из организаторов не владеет русским языком, ведущий говорит на английском, баг-репорты нужно заводить на английском… Напрямую об этом нигде не сообщалось (хоть и во всех материалах и письмах, приходивших участником перед началом Тестатона не было ни слова по-русски), но без должного знания технического английского языка участие в этом мероприятии становится затруднительным.
    А потом СОТНИ девайсов начали коннектиться к несчастному вайфаю бизнес-центра… и он умер.
    Веселый и заводной ведущий (а по совместительству соорганизатор «Тестатона» и сооснователь Global App Testing Рональд Каммингс-Джон (англ. Ronald Cummings-John) призвал нас не паниковать (это не сработало) и подождать решения проблемы. Это и последующая задержка процесса на полчаса остались единственными провалами организации.
    После вступительных слов от организаторов было объявлено начало первого тура. Между командами поделили области тестирования, а уже между собой участники команды делили платформы, девайсы и все, что им приходило в голову. На практике же деление вышло весьма условным, так как от каждого участника принимались любые баги: скорее всего организаторы хотели таким образом максимально уменьшить вероятность дублирования.
    Здесь мог бы быть занимательный рассказ о найденных багах, обсуждении дефектов с организаторами и фантастических идеях участников, но NDA. Простите.
    Каждый найденный баг участник мог зарепортить в собственную баг-трекинговую систему Global Apps Testing (насколько я понял, эта же система используется и в коммерческой деятельности компании). Группа модераторов, расположенная в Румынии, воспроизводила каждый кейс, оценивала критичность дефекта и выставляла тикету одну из трех резолюций: Rejected, Accepted или Shortlisted (тикет с такой резолюцией начинал участвовать в конкурсе на лучший баг). Каждый проверенный тикет добавлял (или отнимал, в случае Rejected) определенное количество очков, сумма которых позволяла определить победителей в номинации Best QA. Помимо проверки воспроизводимости и серьёзности бага, модераторы так же оценивали качество баг-репортов (за это полагался отдельный приз).
    По итогам полутора часов первого тура командам поручили дать суммарный фидбек. В нем мы описывали, какие паттерны тестирования мы использовали, какие командные thinking frameworks применяли и т.д. Я так и не понял, зачем это было нужно, потому что лучшая команда определялась исключительно по максимальной сумме очков, набранной каждым участником.

Обед

    Рассказывая о любом публичном ивенте, длящемся целый день, нельзя не упомянуть о питании. Тут с ним было все в порядке (: Вкусный борщ (прилагающаяся к нему пампушка ВНЕЗАПНО оказалась пирожком с мясом), куриный или мясной шашлык (правда, найти место его выдачи оказалось нетривиально), пара неплохих салатов, десерт и на удивление приличные чай и кофе. Хвала за старания бизнес-центру, благо участников было не так много, чтоб обед в маленьком кафе превратился в ад.
    Организаторы тут решили сделать упор на одну из главных целей мероприятия — общение между участниками. А потому у всех было задание на время обеда: сесть с незнакомыми людьми и постараться поближе познакомиться. Мне с товарищем повезло разделить стол со вторым соорганизатором «Тестатона» Owais Peer. Он рассказывал нам про работу Global App Testing, организацию «Тестатонов» в разных странах и впечатления от Москвы. Мы тоже поделились своей реакцией на мероприятие (включая изначальное недоверие, которое его откровенно удивило; надеемся, в дальнейшем они смогут быть более «открытыми»). А еще он впервые в жизни попробовал борщ, и ему понравилось (хоть он и не хотел нам верить, что цвет блюду придает вовсе не обилие помидоров).
    В преддверии второго тура мы натолкнулись на новое условие: нужно было иначе распределиться по командам так, чтобы не пересекаться ни с кем из первой команды. Так мы с моим товарищем стали противниками. Team F(at) for the win!

Завершение

    2 и 3 раунды прошли на одном дыхании. Их процесс существенно отличался от первого, потому ни скучно, ни рутинно не было (впрочем, само наличие третьего тура оказалось для нас новостью, так как в изначально разосланному всем участником расписанию туров было только два).
    В перерыве был небольшой кофе-брейк, заполнение фидбек-форм и голосование за участника в номинации Most Talkative. Я ожидал «саморекламного» галдежа и общего веселья, но было достаточно спокойно. Все-таки айтишники не самый легкий на подъем народ 🙁
    К моменту завершения третьего тура организаторы уже были готовы к началу церемонии награждения. Каждый победитель получал симпатичный именной сертификат и приз (Рональд просил нас при упоминании этого слова дружно издавать восторженное «У-у-у-у-у!»). Номинаций было достаточно много, среди них и призы за лучший баг, и за самые понятные баг-репорты, и уже вышеупомянутый приз самому разговорчивому человеку. Ваш покорный слуга победил в номинации Best Participation During Feedback. Да, можете считать это утешительным призом просто за то, что я больше всех остальных приставал к организаторам с вопросами и советами 🙂 Больше всего девайсов принесла девушка с ошеломляющим набором в ВОСЕМНАДЦАТЬ штук. А вот какой девайс стал самым древним я так и не узнал. Но мой ветеран HTC Hero помог мне обнаружить немало интересных кейсов.
    В конечном счете я не пожалел ни минуты проведённого на «Тестатоне» времени. Кое-какие вещи, конечно, ребятам еще стоит отполировать: например, немного странное впечатление оставило то, что из-за обилия номинаций призы получила чуть ли не половина участников, а остальные должны были чувствовать себя от этого весьма неловко. Но все равно впечатления остались по большей части положительными. Буду настоятельно рекомендовать Badoo сотрудничать с этими замечательными ребятами, чтобы провести очередной «Тестатон» под нашим флагом!

    К сожалению, кроме достаточно интересных фото с Питерского этапа Тестатона у меня нет больше никакого фидбека о том, как проходило мероприятие в северной столице. Если на Хабре есть его счастливые участники — буду очень рад услышать ваши впечатления!

    И еще раз отдельное спасибо Рональду за то, что самоотверженно развлекал нас всех во время этого крайне серьезного мероприятия и позволил «Тестатону» стать одним из самых запоминающихся дней моей жизни.

    Кудинов Илья, Sr. QA Engineer, Badoo Development
ссылка на оригинал статьи https://habrahabr.ru/post/314046/

Как-то раз я собирался в Грецию и решил узнать, будут ли с меня брать комиссию при оплате рублевой картой. Я не люблю звонить в банк, поэтому отправил свой вопрос на почту техподдержки. Через пару дней мне пришел вот такой ответ:

Я так и не понял, идет ли речь о дополнительной комиссии или о конвертации по курсу банка. О том, что было бы неплохо заехать в банк и написать заявление, до меня дошло только с третьего раза.

Давайте попробуем сделать лучше.

Пишем простым языком

Хороший банк должен быть на одной волне с клиентами. Общение должно вестись непринужденно, без лишнего официоза и непонятных терминов. Будь проще и люди к тебе потянутся.

Перепишем наше письмо так, чтобы стало понятно и студенту-первокурснику, и бабушке-пенсионерке:

Добавляем пользу

После того, как мы сделали текст проще, всплыла главная проблема. Это письмо должно было быть о дополнительной комиссии, а не о курсе конвертации. Мы проигнорировали вопрос клиента, а значит наше письмо не попало в цель. Исправляемся:

При оплате за рубежом мы не возьмем с вас дополнительной комиссии.

Проявляем заботу

Проявление заботы — это плюс в карму и доверие клиента.

Человек, который интересуется дополнительными комиссиями, навряд ли захочет тратить деньги впустую. Нужно посоветовать ему что-то, что обезопасит его средства и поможет сэкономить. Например, можно написать о валютных картах:

Зарубежные банкоматы могут брать дополнительную комиссию за снятие средств. Чтобы этого не случилось, рекомендуем вам выпустить валютную карту. Это можно сделать бесплатно в любом офисе банка.

Наводим красоту

Соберем весь текст вместе:

При оплате за рубежом мы не возьмем с вас дополнительной комиссии.

Если вы будете расплачиваться рублевой картой, банк спишет средства по своему внутреннему курсу.

Узнать текущий курс можно здесь: ссылка.

Зарубежные банкоматы могут брать дополнительную комиссию за снятие средств. Чтобы этого не случилось, рекомендуем вам выпустить валютную карту. Это можно сделать бесплатно в любом офисе банка.

Во время поездки банк может заблокировать вашу карту, т.к. у вас установлен лимит на покупки за рубежом. Чтобы этого не случилось, вам нужно написать заявление в свободной форме. Это можно сделать по телефону (номер телефона) или в офисе банка. Не забудьте паспорт.

Получилась бесформенная куча. Придадим ей форму: разобьем на абзацы, добавим подзаголовки и немного поиграем с формулировками:

При оплате за рубежом мы не возьмем с вас дополнительной комиссий. Если вы будете расплачиваться рублевой картой, банк спишет средства по своему внутреннему курсу. Узнать текущий курс можно здесь: (ссылка).

Также перед началом путешествия рекомендуем:

Оформить валютную карту
Мы с вас комиссию не возьмем, а вот зарубежные банкоматы — могут. Чтобы этого не случилось, рекомендуем выпустить валютную карту. Это поможет сэкономить на конвертации. Оформить карту можно бесплатно в любом офисе банка.

Сообщить банку о своей поездке
Во время поездки банк может заблокировать вашу рублевую карту, т.к. у вас установлен лимит на покупки за рубежом. Чтобы этого не случилось, вам нужно написать заявление в свободной форме. Это можно сделать по телефону (номер телефона) или в офисе банка. Не забудьте паспорт.

Последний штрих

Общение всегда начинается с приветствия. В оригинале письма используется слово «Уважаемый». Но настоящее уважение проявляется в заботе, а не в красивых словах. А написать можно всё, что угодно:

Уважаемый Кирилл Сергеевич!
Ваша статья — !@#%.

С уважением,
сотрудники банка.

Заменим на нейтральное «Здравствуйте».

Резюме

Письмо нашего банка было тяжелым и непонятным, а стало простым и воздушным:

Пишите проще, пишите о полезных вещах. Людям это нравится.

ссылка на оригинал статьи https://habrahabr.ru/post/314054/

Технологический Центр Дойче Банка известен своими Java-спикерами: Руслан Черёмин и Алексей Рагозин давно выступают на конференциях, выбирая для докладов далеко не самые доступные темы, и оба ведут по техническому блогу. Дойче Банк поучаствовал в Joker 2016, и мы использовали это как повод задать Черёмину с Рагозиным по несколько вопросов.

Руслан Черёмин (senior developer)

— О вас обычно знают просто «он из Дойче» — а можете ли рассказать о том, чем именно там занимаетесь и как именно (например, какие инструменты используете)?

— Мы занимаемся валютным рынком. В частности, команда, в которой я работаю, занимается генерацией цен на валютные инструменты — мы собираем информацию со многих рынков, применяем к ней особую магию, и решаем, по какой цене сейчас готов торговать этой конкретной валютой со своими клиентами Дойче Банк.

Ничего сильно необычного из инструментов у нас тут нет: у Дойче Банка лицензия на IDEA, хотя некоторые специалисты ещё по привычке разрабатывают в Eclipse. Для сборки используем Maven и Ant, соседние команды используют Gradle.

— В «Без слайдов» вы говорили «оказалось, что Дойче Банку как раз был нужен такой специалист, как я» — а что именно означало «такой, как вы», в чём именно было соответствие роли?

— В тот момент моя нынешняя команда собиралась переписывать с нуля сервер генерации цен — с Disruptor, и прочими фокусами. У них была вакансия для человека, который будет основным разработчиком этого нового сервера, и добьётся с его помощью новых красивых цифр latency. А тут я с докладом про Disruptor, и как раз собираюсь уходить из Яндекса, и очень интересуюсь возможностью поработать в домене low latency. В процессе подготовки к конференции мы познакомились с Володей Долженко, через которого я, в итоге, оказался в Дойче.

— Расскажите для тех, кто далёк от банковского сектора: в чём специфика Java-разработки в таком месте, как ТехЦентр Дойче Банка, отличающая её от Java-разработки в целом? Повышенные требования к надёжности?

— Конечно, требования к надёжности у нас повыше, чем в среднем энтерпрайзе, но все-таки мы не шаттлы тут запускаем — чего-то заоблачного нет. Надёжность, в основном, обеспечивается избыточностью: например, из двух десятков источников данных, которые слушает наш сервер, только штук пять реально используются в каждый конкретный момент — очевидно, самые качественные. Остальные просто в обойме на замену, если вдруг качественный источник замолчит — у нас есть менее качественный, но все же рабочий. И такая избыточность на многих уровнях.

Особенность банковского сектора — то, что он очень регулируемый и проверяемый. Поэтому немалая часть бизнес-требований состоит в том, чтобы соответствовать запросам аудиторов. Например: мы сохраняем массу информации о том, что в наших системах происходит, и храним её чуть ли не вечно. Например: заметная часть требований к надёжности происходит не непосредственно от нашего бизнеса, а исходит изначально от аудиторов/регуляторов (иногда эти требования довольно странно выглядят в контексте конкретного приложения).

— На JPoint 2016 вы рассказывали про escape analysis — а можете ли привести из опыта работы какой-либо конкретный пример того, как его знание помогало справиться с конкретной рабочей задачей?

— Нет, не могу 🙂 Это довольно свежее исследование, и какого-то заметного применения в моей работе ему пока не нашлось. Наши самые критичные в отношении производительности приложения были написаны еще во времена довольно старых версий Java, и там применены гораздо более дубовые методы оптимизации. А переписывать прямолинейное и надёжное на модное и молодёжное только потому, что оно модное и молодёжное… Я жду новых проектов — возможно, там это пригодится больше.

— Хорошо, это слишком свежее — а в случае с темами вроде Java Memory Model, о которой делали доклад в 2013-м, конкретные случаи «вот здесь это помогло» есть?

— Да, те же самые weak caches у нас в коде много где используются и помогают уменьшить нагрузку на GC. В горячих местах у нас есть специализированные под конкретный сценарий concurrent map-ы или буфера.

Вообще, знание JMM — это вспомогательный навык, основное применение для него — это отфильтровывать заведомо некорректные решения. В большинстве случаев я ищу решение, подходящее по функциональности, дизайну, производительности, — а модель памяти выступает как фильтр, отбраковывающий идеи, сложно реализуемые в многопоточных условиях, и наоборот, подсказывающий проверенные многопоточные паттерны.

Таких трюков, как с benign race, совсем немного. Большая часть практического применения JMM состоит в том, чтобы не делать глупостей и быть проще.

Алексей Рагозин (solution architect)

— Вы довольно «хардкорный» специалист. Дойче Банк подходит вам тем, что там много подходящих задач?

— По его меркам на «хардкорность» я не тяну. В RTC есть команды, которые решают задачи из разряда ultra low latency, вот там «хардкор». Но Дойче действительно привлекает меня тем, что очень часто приходится решать задачи, которые ещё не имеют «типовых» решений в индустрии. Я бы сказал, что если вам интересно заниматься определёнными технологиями (например, in-memory data grid), ТехЦентр Дойче Банка — это чуть ли не единственное место.

— У вас довольно активная публичная деятельность: многократно выступали на конференциях, ведёте англоязычный блог. В чём ваша главная мотивация для этого?

— Помимо блога и конференций, я длительное время преподавал на курсах второго высшего образования в МГТУ им. Баумана, а сейчас веду два курса в Java-школе нашего технологического центра.

Но возвращаясь к вопросу, основная цель — это расширение круга общения, обмен мнениями. Выступления и статьи в блоге вызывают отклик от читателей/cлушателей, очень часто я узнаю что-то новое.

— Про Java-школу любопытно: а какие два курса?

— Один о профилировании Java-приложений, другой о сборке мусора. Перекликается с двумя моими докладами на JPoint.

— Порой считается, что самообразования достаточно: мол, на StackOverflow уже любой ответ найти можно. А зачем Java-школа — что она даёт, чего в гугле не получишь?

— Школа даёт очень много. Грубо говоря, до тех пор, пока человек не понимает проблему, он не может корректно задать вопрос. А соответственно, не может найти ответ на StackOverflow. Это замкнутый круг. Поэтому многие инженерные задачи требуют некоторой «академической» базы, прежде чем человек сможет самостоятельно искать решение конкретной проблемы, используя общедоступные ресурсы. И это справедливо не только для узких технических тем вроде тюнинга JVM, а для очень разных. Никакой StackOverflow не научит правильно использовать сложный фреймворк или проектировать архитектуру приложения.

Напоследок — доклады, которые Черёмин и Рагозин делали в последние годы на конференциях JUG.ru Group:

ссылка на оригинал статьи https://habrahabr.ru/post/313846/