Математика жизни и смерти. 7 математических принципов, формирующих нашу жизнь — страница 43 из 54

Генетический алгоритм начинается с генерации заданного числа потенциальных решений проблемы. Эти решения являются родительским поколением. Для задачи о рюкзаке это родительское поколение создает списки пакетов – наборы предметов, которые могут поместиться в рюкзак. Алгоритм ранжирует решения по тому, насколько хорошо они решают проблему. В задаче о рюкзаке критерием ранжирования становится прибыль, которую может принести каждый набор предметов, помещающийся в рюкзак. Затем выбираются два лучших решения – наборы, приносящие наибольшую прибыль. Некоторые наборы из одного хорошего решения отбрасываются, а остальные комбинируются с некоторыми наборами из другого хорошего решения. Существует также возможность «мутации» – случайно выбранный набор может быть удален из рюкзака и заменен другим. Как только в новом поколении создано первое дочернее решение, выбираются еще два наиболее эффективных родительских, которые будут воспроизводиться. Таким образом, лучшие решения в родительском поколении передают свои характеристики бóльшему количеству дочерних решений в следующем поколении. Этот комбинированный процесс повторяется до тех пор, пока не возникнет достаточно «дочек», чтобы заменить все оригинальные решения в родительском поколении. Сделавшие свое дело родительские решения уничтожаются, а дочерние переходят в статус родительских и весь цикл «отбор – комбинация – мутация» начинается заново.

Дочерним решениям присущ случайный характер, поэтому алгоритм не гарантирует, что все «дочки» будут лучше своих «родителей». Вообще-то, многие окажутся даже хуже. Однако, выбирая, какие из дочерних решений станут воспроизводиться – это можно назвать виртуальным дарвинизмом, – алгоритм отбрасывает неполноценные решения и позволяет передать свои характеристики следующему поколению только лучшим. Как и в случае с другими алгоритмами оптимизации, в результате мы можем получить локальный оптимум, любое изменение которого приведет к снижению качества, но не достичь наилучшего из возможных решений. К счастью, случайные процессы комбинирования и мутации позволяют отойти от этих локальных пиков и двигаться в сторону еще более совершенных решений.

Случайность, являющаяся столь важной особенностью генетических алгоритмов, играет определенную роль и в нашей повседневной жизни. Когда вам надоест прежний плейлист, постоянно прокручивающий одни и те же песни одних и тех же групп, вы можете нажать на кнопку Shuffle. В своей чистой форме функция просто выберет для вас случайную песню. Это как генетический алгоритм без стадий отбора и комбинации, но с высокой степенью мутации. Возможно, это один из способов найти новую группу, которая вам понравится, но, возможно, вам придется пробираться через кучу песен Джастина Бибера или One Direction, чтобы найти что-то стоящее.

Многие музыкальные стриминговые сервисы сегодня предлагают гораздо более сложные алгоритмы, чтобы разнообразить ваш плейлист. Если в последнее время вы часто слушали Beatles и Боба Дилана, генетический алгоритм может предложить вам попробовать группу, которая сочетает в себе некоторые характеристики этих двух исполнителей, – например, Traveling Wilburys (супергруппа Боба Дилана и Джорджа Харрисона). Пропуская песни или прослушивая их целиком, вы сигнализируете о том, насколько они вам подходят, давая алгоритму понять, из каких решений он должен исходить впредь.

Плагины Netflix также предлагают вам случайные фильмы или сериалы, исходя из ваших предыдущих предпочтений. Недавно появилось множество компаний, советующих вам – при помощи похожих алгоритмов – разнообразить свой стол, посылая случайные подборки своих продуктов от сыров и вин до фруктов и овощей. Вы можете начать оптимизировать свой гастрономический опыт, исследуя вкусы, о существовании которых, возможно, даже не подозревали; при этом поставщики продуктов питания, ориентируясь на ваши отзывы, узнаю́т, что еще могут вам предложить. От моды до художественной литературы, компании используют инструменты эволюционных алгоритмов, настойчиво пытаясь разнообразить наш повседневный потребительский опыт.

Время сказать: «Стоп!»

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

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

Лучшая стратегия для решения проблем такого рода заключается в том, чтобы посмотреть и сразу отвергнуть некоторые рестораны, чтобы почувствовать общую атмосферу. Вы можете просто выбрать первый ресторан, в который пришли, но, учитывая, что у вас нет абсолютно никакой информации, что это за заведение, есть только один шанс из десяти, что вы случайно выберете лучший. Так что стоит немного подождать и составить мнение о нескольких ресторанах, а потом выбрать первый из тех, что будет лучше, чем все те, в которые вы заходили прежде. Эта стратегия выбора ресторана проиллюстрирована на рис. 21. Первые три ресторана оцениваются, а затем отклоняются. Седьмой ресторан лучше всех предыдущих, поэтому на нем вы и останавливаетесь. Приятного аппетита! Но достаточно ли посетить три ресторана, чтобы получить надежные основания для отказа? Стратегия оптимальной остановки задается вопросом, сколько ресторанов нужно посмотреть и отклонить, чтобы получить представление о том, какой у вас выбор? Если посетите слишком мало ресторанов, вы не поймете, что предлагается к рассмотрению, но если вы исключите из списка слишком много, оставшийся выбор будет ограничен.


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


Математика, стоящая за этой проблемой, сложна, но оказывается, что следует оценить и отвергнуть примерно первые 37 % ресторанов (округленные до трех, если их всего 10), прежде чем выбрать следующий, который лучше всех предыдущих. Точнее, нужно отвергнуть 1/e долю всех доступных вариантов, где e – математическое обозначение числа Эйлера [158]. Число Эйлера составляет приблизительно 2,718, таким образом, 1/e – примерно 0,368 или, в процентном соотношении, 37 %. Рис. 22 иллюстрирует, как меняется вероятность выбора лучшего из 100 ресторанов по мере того, как вы варьируете количество ресторанов, которые отвергаете сразу. Если вы поспешите с решением, оно, по сути, сведется к слепому гаданию, поэтому неудивительно, что при слишком раннем выборе вероятность наткнуться на лучший ресторан низка. Аналогично, если вы выбираете слишком долго, то, скорее всего, вы уже пропустили лучший вариант. Вероятность наилучшего выбора максимальна, когда вы отклоняете первые 37 вариантов.


Рис. 22. Вероятность выбора наилучшего варианта максимальна, когда мы оцениваем и отклоняем 37 % вариантов, прежде чем принять следующий, который оценим выше, чем все, что видели прежде. В этом сценарии вероятность выбора лучшего ресторана составляет 0,37, или 37%


Но что, если лучший ресторан был в первых 37 %? В таком случае, вам не повезло. Правило 37 % работает не каждый раз – оно вероятностное. Вообще алгоритм гарантированно работает только в 37 % случаев. Это лучшее, что вы можете сделать в данных обстоятельствах, но это выгоднее, чем 10-процентный шанс на успех, если бы вы выбирали один из 10 ресторанов наугад, и намного выгоднее, чем 1-процентный, если бы вам пришлось выбирать между 100 ресторанами. Чем выше относительная вероятность успеха, тем шире ваш выбор.

Стратегия оптимальной остановки работает не только для ресторанов. На самом деле изначально математики окрестили ее «проблемой найма»[159]. Если вы должны по очереди провести собеседование с конечным количеством кандидатов на должность, в конце каждого собеседования сообщив претенденту, получил ли он работу, используйте правило 37 %. Проведите собеседование с 37 % кандидатов и используйте их в качестве ориентира. Возьмите после этого первого кандидата, который окажется лучше всех тех, кого вы видели до него, и откажите остальным.

Когда я подхожу к кассам в моем местном супермаркете, я прохожу мимо первых 37 % (4 из 11), отмечая длину очереди в каждую из них, а затем встаю в первую же очередь, которая короче, чем все остальные, которые я видел. Если я вместе с группой друзей пытаюсь сесть в забитый пассажирами последний поезд после затянувшейся гулянки – да еще так, чтобы мы сели все вместе, мы используем правило 37 %. Мы пробегаем мимо первых трех вагонов состава, который состоит из восьми вагонов, запоминая, сколько в них народу, а затем садимся в первый же вагон, в котором больше свободных мест, чем в любом из первых трех.

Некоторые из этих сценариев несколько надуманны – хотя и навеяны реальным опытом. Но их можно сделать более прагматичными. Что произойдет, если в половине ресторанов, которые вы проверите, не будет свободных мест? В таком случае логично будет сократить время на предварительный отсев ресторанов. Вместо того чтобы проверять первые 37 %, проверьте только первые 25 %, прежде чем выбирать тот, что будет лучше всех остальных, которые вы уже видели.