О убийце по прозвищу Zodiac, биоинформатике и генетических алгоритмах.

Пожалуй, одна из самых загадочная фигура среди тех серийных убийц, чьи личности и преступления остались нераскрытыми. Собственно говоря, легенда Зодиака основана не на числе убитых — в сравнении с другими серийными убийцами, список его жертв небольшой, официально «всего лишь» 5 человек (сам Зодиак заявил в своем письме о гораздо большем числе жертв). Гораздо интереснее способ коммуникации Зодиака с общественностью — он присылал письма, которые содержали в себе намеки на личность преступники. Причем эти намеки либо были закодированы, либо представлены в виде текстовых или графических шарад.

Наиболее интересной частью посланий являются 4 закодированных сообщений. Это «408», «340» и 2 коротких закодированных посланий в конце обычных писем. (одно их которых якобы содержало имя убийцы).
Код «408» был расшифрован любителями — семьей учителей из Калифорнии за один день. Короткие сообщения в силу своей краткости (небольшого числа (10-13) символов) вряд ли когда-либо получат однозначную расшифровку. На настоящий день известны десятки тысяч вариантов прочтения, и множество имен подходящих под паттерн предполагаемого кодированного имени. Но все они под вопросам.

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

Три шифровки были, в конце концов, прочитаны. Помогло предположение, что в подобный текст не мог обойтись без слов «убить» и «убийство». Когда полученные результаты сложили вместе, получилось одно длинное письмо, в котором убийца подробно описывал удовольствие, которое получал, совершая то, что совершал. Никаких намёков на его или её личность не было и в помине.

Вполне возможно, имя убийцы скрывает четвёртая шифровка, датированная ноябрём 1969-го года, которую Зодиак прислал в редакцию местной газеты. В ней 340 символов, это меньше, чем в трёх предыдущих, и методы шифрования в ней использованы абсолютно другие. Начальник отдела криптоанализа ФБР Дэн Олсон как-то заявил, что для его команды эта криптограмма, известная как Z-340 – «приоритет номер один в горячей десятке нерасшифрованных кодов». Он утверждает, что каждый год от 20 до 30 дешифровщиков-любителей предлагают ему свою помощь в решении этой загадки, но никакого положительного результата добиться пока не удалось.

Команда профессионалов проанализировала распределение символов в тексте, чтобы выяснить, не является ли послание «пустышкой». Если никакого решения нет, или текст был изменён до полной неузнаваемости, тогда распределение знаков в строке должно было совпасть с распределением знаков в столбцах, но этого не произошло.

В 2009 году ученый Райан Гарлик, работающий в области компьютерных наук в Университете Северного Техаса в Дантоне, попытался вместе со своими студентами «вывести» решение, используя так называемый генетический алгоритм (Класс алгоритмов, базирующийся на генетике и естественном отборе. Его суть заключается в перемешивании наиболее перспективных вариантов решений из первоначального случайного набора вариантов, совмещённом с процессом отбора лучших вариантов; прим. mixednews).

Сначала ученики Гарлика составляли возможные пары английских букв с символами из закодированного текста. После этого они анализировали полученные с их помощью последовательности из двух-трёх букв, отбирая те, которые могли бы содержаться в потенциальном решении, например цепочки букв «th» или «es», характерные для английского.

Самые подходящие пары принимались для дальнейшего отбора и комбинирования. Используя этот метод, они сумели найти ключ к первой криптограмме Зодиака, но с Z-340 серьёзного успеха не добились.

Гарлик предположил, что в этом случае нужна некая перегруппировка символов в тексте. Но, в этом случае, количество возможных действий с текстом бесконечно. Это обескураживает. Учёный уверен, что никакие компьютерные программы не помогут приблизиться к разгадке, пока не удастся разгадать сам принцип, по которому текст был зашифрован.

Сравнительно недавно программист-любитель Дан Умановскис написал дополнительный модуль к известной среди любителей криптографии программы zkdecrypto-lite (c помощью этой программы код Z-408 дешифруется меньше чем за минуту):

time ./zkdecrypto-lite cipher/408.zodiac.solved.txt -s 44000
44027,ITIKEKILTINGPEOPLEBECAUSEITISSOMUCHFUNITIUMORERUNTHAN
KILLINGWITDGAMEINTHEFORHESTBECAUSEMANISTHEMOATDANGERTUEANAM
ALORALLTOKILLSOMETHINGGIVESMETHEMOATTHRILLINGECPEHENCEITISE
VENBETTERTHANGETTINGYOURHOCKSOFRWITHAGIRTTHEBESTPARTOFITIAT
HAEWHENIDIEIWILLBEHEBORNINPARADICEUNDATTTHEIHAVEKITTEDWILLB
ECOMEMYSLAVESIWILTNOTGIVEYOUMYNAMEBECAUSEYOUWITLTRYTOSLOIDO
WNOHUTOPMYCOLLECTINGORSTAVESFORMYAFTERLIREEBEORIETEMETHHPITI

real 0m1.241s
user 0m1.167s
sys 0m0.028s

Умановскис добавил интересное описание своего подхода:

Во-первых, несколько простых определений для GP.

Индивид — это один из вариантов решения  проблемы. С точки зрения биологической аналогии, он соответствует одному отдельному индивиду — представителю вида (класса), отсюда и название.
Геном — это описание индивида. В качестве простого примера , если нашей задачей является нахождение формулы объема пирамиды , то геном по своей сути будет представлять формулу.
Поколение — большее количество » синхронно рассматриваемых» индивидов.
Кроссовер(рекомбинация) — аналогия полового размножения в биологии, то есть процесс, в котором новые индивиды создается с помощью двух других индивидов предыдущего поколения. Геном нового индивида представляет собой смесь из родительских геномов .
Мутации — случайные изменения генома индивида.
Приспособленность — это показатель того, насколько «приспособленным» является отдельно взятый индивид. В нашем случае, насколько приспособленной является полученная расшифровка с точки зрения семантики и грамматики связанного текста, иными словами, насколько приемлемо расшифрованное сообщение с точки зрения семантики связанного и грамматически оформленного текста.

Без углубления в технические детали, и используя только вышеприведенные определения, объяснение принципов работы GP можно озвучить примерно так:

1. Создается набор индивидов , со случайно генерируемыми геномами. Это поколение 0 .
2 . Производится оценка пригодности каждого отдельного индивида (с использование ZKD -Lite) .
3 . Значительное число индивидов поколения 0 воспроизводят потомство через кроссовер , которое заменяет популяцию индивидов поколения 0. Это следующее поколение.
4 . В популяцию вносятся мутации, которые случайным образом вносят изменения в геномы индивидов этого поколения .
5 . Возвращение к точке № 2.

Мне нравится применение генетических алгоритмов, формализующих основные биологические и биохимические явления, в областях имеющих к биологии и генетики далекое отношение (например, в криптоанализе). Тут наверное необходимо пояснить, почему эти алгоритмы называются генетическими.

В принципе, в Интернете сторонниками и противниками применения генетических алгоритмов для решения небиологических проблем  размещено немало материала на эту тему (например см. работу о применение генетических алгоритмов в криптоанализе). Одно из лучших описаний сути и принципов генетических алгоритмов можно найти на форуме Хабрахабра. Внизу приведена выдержка с этого форума.

Щепотка истории

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

Где это используют

Поскольку алгоритм самообучающийся, то спектр применения крайне широк:

  • Задачи на графы
  • Задачи компоновки
  • Составление расписаний
  • Создание «Искусственного интеллекта»

Принцип действия

Генетический алгоритм — это в первую очередь эволюционный алгоритм, другими словами, основная фишка алгоритма — скрещивание (комбинирование). Как несложно догадаться идея алгоритма наглым образом взята у природы, благо она не подаст на это в суд. Так вот, путем перебора и самое главное отбора получается правильная «комбинация». 
Алгоритм делится на три этапа:

  • Скрещивание
  • Селекция (отбор)
  • Формирования нового поколения

Если результат нас не устраивает, эти шаги повторяются до тех пор, пока результат нас не начнет удовлетворять или произойдет одно из ниже перечисленных условий:

  • Количество поколений (циклов) достигнет заранее выбранного максимума
  • Исчерпано время на мутацию
Более подробно о шагах

Создание новой популяции. На этом шаге создается начальная популяция, которая, вполне возможно, окажется не кошерной, однако велика вероятность, что алгоритм эту проблему исправит. Главное, чтобы они соответствовали «формату» и были «приспособлены к размножению». 
Размножение. Ну тут все как у людей, для получения потомка требуется два родителя. Главное, чтобы потомок (ребенок) мог унаследовать у родителей их черты. При это размножаются все, а не только выжившие (эта фраза особенно абсурдна, но так как у нас все в сферическом вакууме, то можно все), в противном случае выделится один альфа самец, гены которого перекроют всех остальных, а нам это принципиально не приемлемо.
Мутации. Мутации схожи с размножением, из мутантов выбирают некое количество особей и изменяют их в соответствии с заранее определенными операциями.
Отбор. Тут начинается самое сладкое, мы начинаем выбирать из популяции долю тех, кто «пойдет дальше». При этом долю «выживших» после нашего отбора мы определяем заранее руками, указывая в виде параметра. Как ни печально, остальные особи должны погибнуть.

Практика

Вы успешно прослушали «сказку» про чудо-алгоритм и вполне возможно заждались, когда мы его начнем эксплуатировать наконец, хочу вас обрадовать, время настало.
Давайте рассмотрим на примере моих любимых Диофантовых уравнений (Уравнения с целочисленными корнями).
Наше уравнение: a+2b+3c+4d=30
Вы наверно уже подозреваете, что корни данного уравнения лежат на отрезке [1;30], поэтому мы берем 5 
случайных значений a,b,c,d. (Ограничение в 30 взято специально для упрощения задачи)
И так, у нас есть первое поколение:

  1. (1,28,15,3)
  2. (14,9,2,4)
  3. (13,5,7,3)
  4. (23,8,16,19)
  5. (9,13,5,2)

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

  1. |114-30|=84
  2. |54-30|=24
  3. |56-30|=26
  4. |163-30|=133
  5. |58-30|=28

Меньшие значения ближе к 30, соответственно они более желанны. Получается, что большие значения будут иметь меньший коэффициент выживаемости. Для создания системы вычислим вероятность выбора каждой (хромосомы). Но решение заключается в том, чтобы взять сумму обратных значений коэффициентов, и исходя из этого вычислять проценты. (P.S. 0.135266 — сумма обратных коэффициентов)

  1. (1/84)/0.135266 = 8.80%
  2. (1/24)/0.135266 = 30.8%
  3. (1/26)/0.135266 = 28.4%
  4. (1/133)/0.135266 = 5.56%
  5. (1/28)/0.135266 = 26.4%

Далее будем выбирать пять пар родителей, у которых будет ровно по одному ребенку. Давать волю случаю мы будем давать ровно пять раз, каждый раз шанс стать родителем будет одинаковым и будет равен шансу на выживание.
3-1, 5-2, 3-5, 2-5, 5-3
Как было сказано ранее, потомок содержит информацию о генах отца и матери. Это можно обеспечить различными способами, но в данном случае будет использоваться «кроссовер». (| = разделительная линия)

  • Х.-отец: a1 | b1,c1,d1 Х.-мать: a2 | b2,c2,d2 Х.-потомок: a1,b2,c2,d2 or a2,b1,c1,d1
  • Х.-отец: a1,b1 | c1,d1 Х.-мать: a2,b2 | c2,d2 Х.-потомок: a1,b1,c2,d2 or a2,b2,c1,d1
  • Х.-отец: a1,b1,c1 | d1 Х.-мать: a2,b2,c2 | d2 Х.-потомок: a1,b1,c1,d2 or a2,b2,c2,d1

Есть очень много путей передачи информации потомку, а кросс-овер — только один из множества. Расположение разделителя может быть абсолютно произвольным, как и то, отец или мать будут слева от черты. 
А теперь сделаем тоже самое с потомками:

  • Х.-отец: (13 | 5,7,3) Х.-мать: (1 | 28,15,3) Х.-потомок: (13,28,15,3)
  • Х.-отец: (9,13 | 5,2) Х.-мать: (14,9 | 2,4) Х.-потомок: (9,13,2,4)
  • Х.-отец: (13,5,7 | 3) Х.-мать: (9,13,5 | 2) Х.-потомок: (13,5,7,2)
  • Х.-отец: (14 | 9,2,4) Х.-мать: (9 | 13,5,2) Х.-потомок: (14,13,5,2)
  • Х.-отец: (13,5 | 7, 3) Х.-мать: (9,13 | 5, 2) Х.-потомок: (13,5,5,2)

Теперь вычислим коэффициенты выживаемости потомков.

  • (13,28,15,3) — |126-30|=96(9,13,2,4) — |57-30|=27
    (13,5,7,2) — |57-30|=22
    (14,13,5,2) — |63-30|=33
    (13,5,5,2) — |46-30|=16

    Печально так как средняя приспособленность (fitness) потомков оказалась 38.8, а у родителей этот коэффициент равнялся 59.4. Именно в этот момент целесообразнее использовать мутацию, для этого заменим один или более значений на случайное число от 1 до 30. 
    Алгоритм будет работать до тех, пор, пока коэффициент выживаемости не будет равен нулю. Т.е. будет решением уравнения.
    Системы с большей популяцией (например, 50 вместо 5-и сходятся к желаемому уровню (0) более быстро и стабильно.


Реклама

Добавить комментарий

Please log in using one of these methods to post your comment:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s