(no subject)
Перефразируя сказанное Тайлераном ("война слишком серьезное дело, чтобы доверять ее военным") я бы сказал, так: эволюция слишком серьезное дело, чтобы доверять его биологам (которые, как мы знаем из манифеста Юрия Лазебника ( англ.), не могли бы починить и транзисторного приемника!).
Если без шуток, я действительно полагаю, что только математика (computer science) может целостно охватить такое глубокое явление как эволюция. Биологи (пускай не обижаются) всегда тонут в частностях. Они за деревьями никогда не видят леса.
Особенно любят обобщать эволюцию программисты, пользующиеся генетическими алгоритмами. Как утверждает расхожий мем, абсолютная власть - развращает абсолютно. Тогда не удивительно, что для программистов, избалованных абсолютной властью над универсальным вычислителем, нет ничего невозможного. Объяснить все в этом мире как эволюционную оптимизацию? Да ради бога! Яркий образчик такого глобального подхода - перед вами. Предлагаю вашему вниманию доклад Владислава Голощапова прозвучавший в начале 2013-го года на семинаре SETI в ГАИШ.
Владислав Игоревич
Голощапов
"Научно-технический прогресс человечества,
теоретические ограничения и пути дальнейшего развития"
Конспект доклада на Заседании Ученого совета НКЦ SETI,
состоявшегося 8 февраля 2013 года в конференц-зале ГАИШ.
Выполнил А. Семенов по аудиозаписи,
взятой на сайте НКЦ SETI
(сам доклат на данной записи начинается с 18:15)
Как на мой личный взгляд - это лучший доклад, из всех услышанных мною в аудиозаписях заседаний НКЦ SETI. Эволюция "от" и "до", эволюция "в" и эволюция "на". От эволюционных методов программирования, до будущего человечества и внеземных цивилизаций. Советую непременно послушать аудиозапись заседания.
Хотя концу доклада в зале осталось всего 5 человек, лично для меня все услышанное стал настолько созвучным многому смутно бродившему в моей голове, что я сразу же решил сделать конспект этого доклада "на слух", сопроводив это своей, явно недостающей, графикой (авторскую я же не видел!). Однако, и этого мне показалось мало. Я дополнил все это развернутыми (порой чересчур, грешен) комментариями еще одного программиста... Себя, любимого... :)
Не удивляйтесь тому, что конспект очень сильно отличается по структуре от хода заседания. Часть разъяснений докладчика, возникших уже в ходе обсуждения, я вставил в тело конспекта как часть доклада, тем самым четко разделяя вступительную теорию и приложение ее к цивилизациям. Я посчитал такое перемещение более чем уместным, разделив весь доклад на две части. Эта первая (как по мне - самая захватывающая). Она делает введение в суть вопроса "сильное обобщение", а судьбы человечества пока не касается.
НАПИСАННОЕ МЕЛКИМ ШРИФТОМ МОЖНО НЕ ЧИТАТЬ! Часть I
Эволюция кода
Любая программа - это конечная цепочка символов в некотором алфавите, которую можно в конечном итоге записать как конечную цепочку единиц и нулей. То есть, представить, как цепочку из N бит (в двоичном коде).
Рассмотрим все возможные бинарные цепочки длиной N:
N =1: 0, 1 (два варианта)
N=2: 00, 01, 10, 11 (четыре варианта)
N=3: 000, 001, 010, 011, 100, 101, 110, 111 (восемь вариантов)
N=4: 0000, 0001, 0010, . . . , 1001, 1111 (шестнадцать вариантов)
и т.д.
Количество всех возможных цепочек (потенциальных программ) длиной N будет 2N.
Рассмотрим все это множество возможных битовых цепочек длиной N, как N-мерное дискретное пространство. Так, однобитовое пространство - прямая, двухбитовое - плоский квадрат, трехбитовое - куб, четырехбитовое - гиперкуб и т.д.
Если у нас есть К программ (длиной N) то каждая из этих программ находится в некоторой точке такого N-мерного дискретного пространства. Если в любой такой программе, скажем, в программе 001…10 поменять какой-нибудь один байт, например, сделаем из нее 011…10, то она переместится в другую (смежную) точку этого пространства (у каждой программы длиной N есть N смежных точек в таком пространстве). Назовем такое преобразование однократной МУТАЦИЕЙ.
Панов (один из организаторов семинара) спросил, может ли меняться размерность пространства?
Если программа удлинилась, то может, уточнил докладчик. То есть можно не просто гулять по одному пространству, но и перемещаться в пространство большей размерности. При этом более короткая программа - частный случай более длиной.
Здесь и далее синим курсивом - мои комментарии, А. Семенова.
Данное пространство в принципе бесконечномерное и не все измерения в нем обязаны быть дискретными, если ввести в программу аналоговую величину (???!). Но непрерывность некоторых измерений, нам не принципиальна (и даже может оказаться полезной).
Теперь над данным пространством всех возможных бинарных цепочек зададим некую функцию (целевую функцию), которая для каждой точки этого пространства определяет ее эффективность (ставит ей некий оценочный коэффициент). Таким образом, возникает пространство с заданной над ним оценочной функцией.
Врезка 1 А.Семенова.
Можно сказать, что к N-мерному пространству мы добавляем еще одно измерение (как правило, не дискретное!) и тогда N-мерное пространство возможных программ предстанет некой ПОВЕРХНОСТЬЮ в N+1 мерном пространстве. И эта "некая функция", по сути, определяет ландшафт данной поверхности. Примеры двумерного (N=2) ландшафта в трехмерном пространстве, N+1=3:
Так как наше трехмерное воображение все равно не может вообразить N-мерное пространство при N>3,то иногда проще, представлять такое пространство как двумерный "срез", например:
Этого, как правило, достаточно чтобы сделать нужные обобщения без потери общности на пространства высших размерностей.
Панов тут же попросил уточнить: эффективность с чьей точки зрения оценивается?
Докладчик сказал: "С точки зрения внешнего оценщика". Как мне показалось, эта тонкость была в итоге быстро "замята". Можно подумать на Бога, но подразумевается, естественно эволюция. Однако, я думаю, тут все еще шире, когда речь идет о задаче оптимизации. Понятие "оценочная функция" для людей, знакомых с идеей генетического алгоритма в частности, и с задачей оптимизации вообще - вещь более чем очевидная.
Суть тут в том, что оценить эффективность уже существующей у вас точки пространства возможных решений - процедура, как правило, МНОГО ПРОЩЕ чем процедура НАХОЖДЕНИЯ экстремальной точки ландшафта из множества всех возможных (в чем и состоит суть задачи оптимизации). То есть, "внешний оценщик" это обычно достаточно простой и ясный для нас алгоритм заданный изначально. И этот алгоритм не надо искать в процессе решения задачи оптимизации, он задается как часть ПОСТАНОВКИ задачи. Когда мы что-то хотим оптимизировать, мы уже четко понимаем КРИТЕРИЙ этой оптимизации, механизм построения всех точек ландшафта. Механизм их сравнения. Этот механизм и есть та самая "функция оценки" или "целевая функция". И кстати, такая функция не обязана быть непрерывной. Например, она может быть дискретной (выжил -не выжил, да-нет, 0-1).
Наша задача теперь, с помощью эволюции найти на этом ландшафте (из всех возможных бинарных цепочек) максимум. Конкретно - найти наиболее эффективную (с точки зрения заданной оценочной функции) программу.
Все алгоритмы поиска по деревьям очень сильно тратят память (заявил Голощапов). Если мы возьмем программу разумной длины, то поймем, что никаких мыслимых объемов памяти нам не хватит для систематического перебора и…
Задача поиска оптимального решения резко усложняется
Первое, что мы можем сделать для уменьшения затрачиваемых вычислительных ресурсов - не сохранять весь предыдущий путь поиска. Но каким способом можно сохранить информацию о том, что какие-то точки мы уже проверили? Лучший способ - сохранять один экземпляр программы в некоторой окрестности, которую мы уже просмотрели.
То есть сохранить не точку, а популяцию точек. Группу точек, для которых известна их эффективность.
Простейший способ эволюционного поиска - организовать единичную мутацию (случайный переход в соседнюю точку) и оценить эффективность новой программы (речь идет о эволюционно программировании, то есть генерацию программного кода эволюционным методом) по сравнению с предыдущей. Если эффективность ухудшилась - отходим назад. Получаем эволюцию в простейшей форме.
Врезка 2 А.Семенова.
Здесь речь пошла уже о тонкостях именно генетических методов оптимизации (или верней генетического программирования) и нужен обширный комментарий, в том числе и о преимуществе генетических (вероятностных) методов оптимизации над любыми регулярными. Хотя бы потому, что эти преимущества не столь уж и очевидны и все еще являются предметом обширных математических дискуссий.
Как я думаю, Голощапов явно не прав, заявляя, что регулярный метод нуждается в сохранении всех предыдущих вариантов. Отнюдь! Возьмите простейший рекурсивный алгоритм регулярного перебора (перечисления) ВСЕХ бинарных цепочек по дереву:
Применяйте к каждой очередной бинарной цепочке вашу оценочную функцию и сохраняйте ее результат (с экземпляром цепочки) как единственный текущий максимум, если для очередной цепочки ее значение больше сохраненного ранее (на схеме в качестве примера помечены красным). В итоге, даже при таком тупом решении "в лоб" вам нужно помнить только пару значений. Текущий максимум оценочной функции и код кандидата. Никаких запредельных ресурсов памяти!
Что будет действительно запредельным - ВРЕМЯ решения задачи таким образом. Количество вычислительных шагов. Оно растет экспоненциально 2N от размерности пространства N. Так, всех "программ" длиной всего в 1000 бинарных символов (1/8 килобайта) будет уже около 10301 штук! Хотя алгоритм существует и он прост, перебрать вот так, "в лоб", все варианты - нет никакой практической возможности. Поэтому поиск разумных методов оптимизации, по сути, сводится к отысканию приемов, резкого сокращения числа шагов вычислений и является целым разделом математики.
Существует ряд регулярных (детерминированных) методов поиска максимума на ландшафте, за разумное число шагов. Например, градиентный метод (вы пробуете окрестность на один шаг и всегда движетесь туда где "подъем" больше). Но все эти методы не гарантируют результат (например, на определенных ландшафтах они находят локальный максимум, не находя глобальный). Говорят, они теряют в общности, универсальности.
В чем реальное преимущество вероятностных, (в частности генетических) методов оптимизации? В чем волшебное действие случайных мутаций?
Я выскажу свое (и только свое!) мнение.
Здесь надо, как мне кажется, подойти с другой стороны.
Легко доказывается, что класс задач, решаемых детерминированными, недетерминированными и вероятностными алгоритмами (соответствующими машинами Тьюринга) совпадают. То есть, задача, решаемая вероятностным методом, непременно решается и остальными. Нет такой задачи, которая бы решалась детерминированным способом и не решалась бы другим (скажем, случайным). Если решается - то всеми методами. Если не решается - то ни каким не решается.
В случае задачи оптимизации известно, что задача гарантированно имеет универсальный детерминированный алгоритм решения (выше мы его описали). Вопрос лишь в количестве шагов. Их можно резко уменьшить и для детерминированной машины, расплатившись общностью решения (универсальностью). Например, градиентный метод прекрасно себя показывает на ряде ландшафтов. Но не на всех.
Выше я показал УНИВЕРСАЛЬНОЕ, но неприемлемо-длинное решение задачи оптимизации.
Идеальным выходом была бы недетерминированная машина. Она решила бы универсальную задачу оптимизации "в лоб" за приемлемое (говорят, за полиноминальное) время. Для нее и не надо искать боле быстрые алгоритмы. Она изначально быстрая для таких трудных задач. Но такая машина физически неосуществима (по крайней мере, пока, квантовые компьютеры все еще считают детские задачи типа 2+2=4).
Что с вероятностной машины Тьюринга (вероятностным алгоритмом)? Вот именно для них известно, что случайным способом некоторый класс "вычислительно сложных" или "медленных" задача может решаться за "полиноминальное" число шагов, если заплатить за это … точностью решения. Ответ в этом случае верен не наверняка, а с некоторой вероятностью. И вероятность того, что решение верно можно повышать, расплачиваясь за это быстрым ростом числа шагов. Это так называемый класс BPP-алгоритмов (bounded-error, probabilistic, polynomial).
Для задач оптимизации, такой подход (точность в обмен на время) часто более чем приемлемая расплата, что, скорей всего, и реализуют генетические алгоритмы. Нам часто не нужен точный экстремум, нам достаточно оказаться в его окрестности. Около вершины (или на дне впадины).
Что с общностью? Являются ли генетические алгоритмы оптимизации универсальными? Это как раз предмет дискуссии.
Докладчик, как я понял, не стал углубляться в разъяснения того, что такое генетический алгоритм, что такое генетическое программирование, считая это всем очевидно, и, в последствии, поплатился тем, что "высокое жюри" "не поняло его языка". :)
Что такое генетический алгоритм здесь описывать видимо, тоже, нет смысла. Читатель конспекта может сам погуглить. Вот пример работы такого алгоритма в виде gif-анимации (черные точки - это как раз популяция на неком адаптивном рельефе):
Что бы понять, как широко подобные методы могут применяться (далеко за пределами биологии) вот пример успешного использования генетических алгоритмов для решения конкретного класса проблем в теории твердого тела при поиске новых материалов:
Aртем Оганов, Как научить компьютер открывать новые материалы
В генетике так же говорят об адаптивном рельефе. Каждая буковка алфавита генетического кода {A, G, С, T} - два бита: -log2(1/4)=2 и там адаптивное пространство - пространство всех возможных генотипов.
Иными словами. В терминах биологии адаптивное пространство - фазовое пространство всех возможных значений генетического кода, в котором сопоставлена эволюционная приспособленность данной особи, по сути, сколько потомков она оставит дошедших до репродуктивного возраста.
Любую эволюционную активность определяет не стремление как можно больше размножить число особей, а стремление найти место с наилучшим параметром приспособленности на адаптивном рельефе.
И это обобщение позволяет нам взглянуть на эволюцию как на чуть более осмысленный процесс, чем случайное блуждание. Мы можем, посмотреть на адаптивный рельеф и сказать, что в данном случае эволюция этой популяции протекает в некотором направлении. Например, позвоночные часто эволюционируют в направлении некого "озера" или "плато" (минимума, если "озеро" или максимума, если "плато"; все зависит от того как задана оценочная функция), которое имеется в область двуногости. Причем, мы знаем, что в область двуногости с удовольствием "стекаются" принципиально разные популяции. Птицы, динозавры и т.д.
Введение таких категорий дает возможность обсуждать эволюцию через некоторые качественные категории, которые позволяют некоторые очень сложные процессы объяснить простыми словами (добавлю, интуитивно понятные для нас, привыкших пользоваться зрительными ассоциациями).
И так, еще раз. Имеется адаптивный рельеф. Представим себе теперь неких абстрактных существ, которые "ползают" (их геномы претерпевают мутации) по адаптивному рельефу в поиске локальных максимумов (другая версия - минимумов). Это, по сути то, что совершают все генетические алгоритмы.
Еще ряд ключевых понятий, которые тут потребуются:
Расстояние на адаптивном рельефе - расстояние от той точки, в которой мы находимся до точки, в которую хотим попасть в единицах, элементарных мутаций ("шагов" эволюции).
Летальные области рельефа - "низинные" области (если мы ищем максимумы-пики), где значение оценочной функции ниже порога выживания (особь попавшая в данную точку умирает не оставляя потомство, выбраковывается отбором).
Связанность и несвязанность точек рельефа.
Представим, что все области, которые ниже зеленого на схеме ниже (можно условно сказать "уровня моря") уже летальны. У вас есть ряд максимумов: А, B и точка C. Нельзя попасть из А в В или из C в B одиночными шагами-мутациями не опускаясь до летального уровня. Проще говоря - точка B оказалась "на острове" и такие пары точек (А,Б и B,С) называются - несвязанными. В противоположном случае - точки рельефа связанные (например С и А):
В связи с этим, видимо, следует ввести и понятие расстояния связанности и несвязанности, которые докладчик не ввел, полагая это очевидным. Он очень спешил. Но раз начали давать определения, то будем последовательны.
Расстояние несвязанности - это кратчайшее расстояние от данной точки к ближайшей несвязанной.
Расстояние связанности - расстояние до самой дальней связанной точки.
Связанная область пространства - это область решений, к которым можно дойти, не имея ни одной летальной мутации.
Адаптивный рельеф может быть очень плохим, что определяется очень коротким расстояние несвязанности для всех точек (пример такой области на рельефе выделен красным на рисунке ниже, хотя на этом ландшафте есть еще ряд очень плохих областей).
Так, в нашем пространстве всех алгоритмов может быть много алгоритмов, которые, по сути, похожи, но перейти из одного в другой одной мутацией невозможно.
Например, пускай в программе есть возрастающий цикл:
(что он писал на доске я не видел и приведу придуманный мною пример)
. . . For (int i=1; i<=5; ++i) {. . .} . . .
Допустим, убывающий цикл будет для адаптации (эволюции) программы более выгоден.
. . . For (int i=5; i>0; --i) {. . .} . . .
Но нельзя заменой одного знака (единичной мутацией) поменять прямой цикл на обратный в данной версии языка программировании (С+).
Любая одиночная мутация (даже не бита, а буквы!) станет для этого цикла летальной. Здесь нужно минимум четыре правильных мутации (в терминах ландшафта - переместится на 4-ре шага по адаптивному пространству). Но каждая из трех первых правильных мутаций (в правильном направлении) - летальна. Код на этих шагах эволюции не будет работать вообще (компилятор, например, выдаст синтаксическую ошибку).
В итоге на ландшафте получаем множество несвязанных решений на малом расстоянии. Если мы возьмем реальные алгоритмы и посмотрим, сколько реально работающих алгоритмов окажется на расстоянии 4-5 мутаций, то обнаружим таких в огромном количестве. Одна мутация "между" - убивает любой. Получается гребенка пиков на малых расстояниях:
При этом группа похожих алгоритмов (выполняющих одно и то же) может быть рядом, а может быть далеко. И если мы теперь возьмем некоторую исходную популяцию таких алгоритмов, то увидим, что эволюционировать они "не хотят". Потому что пространство очень сильно "порублено". Алгоритмы не выживают.
Появляется желание перейти в другую систему координат.
Далее были примеры на доске (как я понял) и мне пришлось развивать его мысль самому. Например, развивая пример с циклом выше, можно представить себе язык, синтаксис оператора цикла в котором был, например, таким:
. . . For(0;5;+i){. . . } . . .
При этом, порядок следования первых двух переменных для компилятора не важен. Компилятор сам определяет большее из двух чисел. И если третий параметр начинается с плюс, значит надо считать i от меньшего к большему, если с минус - от большего к меньшему. Тогда МУТАЦИЯ в один шаг, при замена знака "+" на "-" даст желаемый результат.
Тогда гребенка сложится в один крупный, пологий пик (или плато).
То есть. При одной форме записи решения могут быть очень сильно разделены, при другой - пространство может оказаться сильно связанным.
В чем разница? Более сложная операция (из множество отдельных мутаций) стала одиночной одношаговой мутацией и такие переходы мы будем называть СИЛЬНЫМИ ОБОБЩЕНИЯМИ. (насколько я понял, этот термин ввел сам Голощапов)
Сильные обобщения позволяют представить сложную (многошаговую) мутацию как простую и резко повысить связанность пространства.
Более формально:
Обобщение - это освоение особью (появление у особи) некоторого алгоритма, который позволяет совершать сложную поисковую активность из нескольких шагов так, как будто это одиночная мутация.
Не могу не заметить, что концепция сильного обобщения для эволюционного поиска сама по себе является примером сильного обобщения в когнитивном смысле. Опираясь на нашу богатую пространственную интуицию, мы обобщаем, упрощаем, сжимаем сложное понятие, явление, преодолевая "пропасть непонимания" одним шагом.
Реакция докладчика на вопрос из зала:
Сильное обобщение это не свертывание (сжатие, архивирование) информации ибо обобщения НЕТОЧНЫ.
и в этом смысле сразу вспоминаются эвристики в ИИ.
Далее Голощапов заявляет крайне заинтересовавшее меня:
Пенроуз в своей теореме доказал, что пространство нельзя покрыть только точными обобщениями!
(Гм… я хотел бы уточнить, о чем тут речь более конкретно! О какой теореме идет речь?)
Продолжение
I-й части конспекта