Данная статья является кратким обзором того, что представляют собой генетические алгоритмы. Будучи новичком в биоинформатике, начну с вещей, близких и понятных людям технических специальностей: алгоритмов сортировки, затем перейду к описанию одной из задач генетического программирования и того, что под алгоритмами понимают биологи.Сортировки
Думаю, что каждый программист подспудно считает, что знает на эту тему если не все, то почти все. Может быть, на данный момент так оно и есть, и читающий эти строки проштудировал третий том «Искусства программирования» Дональда Кнута. Но давайте проведем эксперимент: возьмите ваш любимый алгоритм и попытайтесь его реализовать карандашом на листе бумаги. Если любимого алгоритма нет, то предлагаю сортировку пузырьком. Получилось? Это задание мне неоднократно доводилось предлагать на собеседованиях, но рабочими из предложенных вариантов оказывались немногие, а «пузырьком» оказывались вообще единицы. Недавно мне довелось увидеть конспект лекций по по языку Python, где преподаватель под видом сортировки пузырьком приводит следующий код:
def bubble_sort(numbers):
for first in range(0, len(numbers)-1):
for second in range(first+1, len(numbers)):
if numbers[first] > numbers[second]:
numbers[first], numbers[second] = numbers[second], numbers[first]
Алгоритм рабочий, сортировать будет, но вот только это явно не «пузырек». С некоторой натяжкой его можно назвать сортировкой выборкой, но и тут допущена досадная оплошность: достоинством сортировки выборкой является минимизация количества замен, то есть количество раз, когда мы меняем местами элементы, должно быть ограничено O(n), чего не наблюдается в приведенном коде.
В беседе на тему алгоритмов бывает интересно перевернуть вопрос о быстрой сортировке. Как правило, люди с легкостью отвечают на вопрос о том, чем она хороша: это и хорошая алгоритмическая сложность в среднем, и отсутствие необходимости в дополнительной памяти (про стек, как правило, забывают). Но тогда интересно спросить, чем же она плоха, раз, кроме нее, существует еще множество других алгоритмов? На этот вопрос ответы гораздо более скудны и однообразны. А какие минусы у Quick Sort сможете назвать вы?
К моему удовольствию, иногда удается встретить эстетов, демонстрирующих знания экзотических методов, например, gnome sort.
Вывод:
1. Если хочешь на собеседовании прослыть эстетом, изучи пару малоизвестных методов сортировки;
2. Если ты сам принимаешь собеседования, умей отличать друг от друга различные методы, а то мало ли попадется кандидат, следующий пункту 1…
Блинная сортировка
Следуя советам выше, рассмотрим задачу, которая не имеет практического смысла, зато интересна с теоретической точки зрения: блинную сортировку. Непрактичность ее состоит в том, что в данном алгоритме вообще не учитывается количество сравнений элементов (считается, что эти операции очень дешевы и быстры), а единственной операцией, имеющей цену, является переворот верхушки стопки сортируемых «блинов». Разумеется, изначально они расположены в произвольном порядке, а желаемым результатом является некое подобие ханойской башни, когда блины большего диаметра лежат снизу, а меньшего располагаются сверху.
По поводу этой задачи хочется отметить два интересных факта. Во-первых, способ нахождения достаточно эффективного (хотя и неоптимального) решения был в свое время предложен небезызвестным Биллом Гейтсом, пока тот был еще студентом. Этот алгоритм, предложенный в 1979 году, оставался наиболее эффективным вплоть до 2008, когда результат был превзойден. Во-вторых, как было доказано впоследствии, задача нахождения оптимального решения относится к классу NP-полных. Также Гейтсом и его руководителем Христосом Пападимитриу был предложен усложненный вариант задачи, известный как задача о подгоревших блинах.
Задача о подгоревших блинах
В этой форме задачи каждый элемент, помимо размера, имеет еще и бинарный атрибут «направление», то есть у каждого «блина» одна сторона подгоревшая, а другая румяная; результатом решения задачи является стопка, упорядоченная по размеру, но, помимо этого, все «блины» лежат подгоревшей стороной вниз. Не вдаваясь в подробности, скажем, что и эта задача NP-полна, и что в общем случае известны ее достаточно эффективные, но неоптимальные решения. Тем не менее, существуют ограничения на данные, при выполнении которых задача становится полиномиальной. Для рассматриваемой задачи такими данными являются простые перестановки. Чтобы понять, что это такое, рассмотрим перестановку чисел от 1 до 7: 2647513. Заметим, что выделенная жирным шрифтом последовательность сама является перестановкой чисел от 4 до 7 (называется блоком). Простые перестановки — это те, где нет нетривиальных блоков (блоков длины 1 и n).
За образной постановкой задачи, когда элементы представлены подгоревшими блинами, сложно разглядеть тот факт, что она имеет биологическое значение. Тем не менее, распространенной мутацией является переворот в молекуле ДНК, и если посчитать минимальное количество переворотов, необходимое для преобразования одной молекулы в другую (без рассмотрения более мелких точечных мутаций), то можно примерно оценить родство организмов. Например, геном человека и мыши разделен всего лишь порядка 120 глобальными мутациями; признаюсь, я раньше полагал, что между этими видами разницы гораздо больше…
Генетический алгоритм решения задачи о подгоревших блинах
В сравнительной геномике алгоритм используется для аналитического нахождения количества мутаций, разделяющих организмы, но посмотрим на задачу в другой проекции. Теперь уже решение аналитической задачи объявим целью, а живые организмы и процессы, в них протекающие, сделаем инструментом для ее решения.
Как известно, бактерии в состоянии делиться обеспечивая экспоненциальный рост популяции, если им предоставлены необходимые условия; разумеется, через некоторое время колонии бактерий уже не будет хватать питательной среды, также появятся другие факторы, влияющие на рост колонии, но на это необходимо время. Экспериментальным путем мы можем выяснить среднее время, которое требуется бактериям данного вида на появление глобальной мутации, связанной с переворотом части ДНК.
Теперь поставим бактериям задачу. Генетически модифицируем одну из них (биологи любят в подобных экспериментах использовать кишечную палочку), где ген устойчивости к антибиотику разобьем на несколько частей и перемешаем между собой, меняя при этом не только порядок, но и направление некоторых кусков. Таким образом, каждый перевернутый и переставленный кусок гена в нашем случае будет представлять собой «подгоревший блин».
Задача бактерии поставлена, можно начинать эксперимент. Помещаем ее в питательную среду и ждем отведенное время, за которое ожидается появление одной мутации-переворота ДНК. Обращаю внимание на то, что мы считаем одной мутацией: она единственна не на всю колонию (как раз в колонии этих мутаций будет много); это всего лишь ожидаемое количество переворотов у каждой из ныне живущих бактерий по сравнению с их прародителем.
Достаточно ли одного переворота блина для решения задачи? Мы легко это можем проверить, поместив часть колонии в опасную для нее среду. Помещенные в антибиотик бактерии не выжили, и мы продолжаем наблюдать за оставшимися. Пройдет еще два-три периода, и, наконец, в группе бактерий, помещенных в антибиотик, останутся живые. «Коллективный разум» справился с задачей!
Итоги
Конечно, полезность решенной задачи нас вряд ли впечатлит: в реальных проведенных экспериментах количество сортируемых «блинов» не превышает четырех, а количество мутаций, происходящее за отведенное время, может быть оценено лишь вероятностно. И все же лично меня поразила фантазия тех биологов, которые смогли поставить эксперимент; не меньшей фантазией обладали и те, кто смог биологическим методом решить задачу коммивояжера (подробности этого эксперимента я оставлю за рамками данной статьи). Во многом сложность задач, решаемых генетическими алгоритмами, сравнима с квантовыми вычислениями, и хочется верить, что оба направления неклассических вычислений смогут дать результаты пока не достижимые в современных условиях.