Lib.ru/Современная:
[Регистрация]
[Найти]
[Рейтинги]
[Обсуждения]
[Новинки]
[Помощь]
Второе пришествие бионики
Примерно на середину прошлого века пришелся расцвет бионики. Согласно словарю, это направление кибернетики, изучающее структуру и жизнедеятельность организмов с целью использования... ну и так далее. На самом же деле, в реальном словоупотреблении это было вот что: потрошим мышь и говорим - о, блин, как здорово устроено. А ну-ка, паяльники наизготовку, канифоль товсь! Сейчас из болтов и гаек склепаем такое - ни одному империалистическому коту не поймать!
Понять, как устроена природа, не просто. Учебник Вилли и Детье толще Тимошенко и Гере, но дело даже не в толщине, а в другом языке. Причем те, для которых "Биология" - настольная книга, не бежали к читателям "Механики материалов" со своими советами. Поэтому технари, наморщив лобик, учили незнакомые слова и пытались понять, как устроено живое. Разумеется, не для бескорыстного восхищения красотой и мудростью устройства мира, а чтобы слямзить. И немало в этом преуспели, а попутно создали протезы сердечного клапана, коленного сустава и много других, очевидно полезных вещей. Но со временем данный метод, как и должно было произойти, нашел свое стабильное место среди всех других методов и страсти поутихли. На некоторое время...
Локальный оптимум и почему он не глобальный
Вот на поверхность земли упал шарик и покатился в сторону понижения рельефа. Если трение будет не слишком велико и не слишком мало, через какое-то время он найдет минимум, ямку, и останется в ней. ("Оценка трения предоставляется читателю в качестве легкого домашнего упражнения.") Будет ли эта ямка самым низким местом на земле? Посреди двора - колодец, у колодца ограждение, на одном из кирпичей - ямка. Шарик попадает в эту ямку и с тоской глядит на двор, который весь ниже дна ямки. А уж про колодец и говорить нечего. Как отправить шарик в дальнейшее путешествие? Очень просто - щелкнуть по нему.
Изложенная детская картинка иллюстрирует большую и важную для практики часть прикладной математики - поиск экстремума. Высота земли - это функция двух переменных, двух координат - широты и долготы, и нам надо найти минимум, причем обычно не локальный, а глобальный - в пределах всего двора. Методов много, но все они так или иначе включают механизм обработки ситуаций попадания в локальный минимум, и многие из них сводятся к "щелчку" - выходу из локального минимума в произвольном направлении. Кибернетики называют такое воздействие "шумом", случайной помехой. Биолог, если бы его попутал бес заглянуть в толстую книгу с мрачным названием "Поиск экстремума", сказал бы, что это похоже на мутацию.
О мелькании в глазах
То, что кибернетики называют "шумом", применяется и в более сложных ситуациях. В середине прошлого века американский математик Ф.Розенблатт придумал перцептрон. Очень похоже, что дело происходило так - листал он однажды учебник биологии, наткнулся на чертеж многослойной клеточной структуры сетчатки лягушки и его немедленно настигло сатори. Вот почему зеленая так ловко ловит комаров! - подумал Фрэнк - потому что клетки первого слоя воспринимают свет, а дальше - каждая клетка в каждом слое суммирует сигналы от нескольких клеток предыдущего слоя и если сумма входных сигналов больше порога, возбуждается и передает сигнал в следующий слой. Причем сеть обучается, то есть пороги возбуждения и схема передачи сигнала может изменяться. Так вот, когда зеленая ловит комаров, идет процесс обучения - сетчатка "обучается" так, чтобы безошибочно находить вожделенного камара в окружающем пространстве. И действительно, в сетчатке лягушки нашли группы клеток, "заточенные" на обнаружение черной точки на светлом фоне. Кстати, вы можете легко придумать, как должен обрабатываться сигнал от такой специализированной группы. Нашли там и другие специализированные группы, так сказать "аппаратно реализованные" алгоритмы.
Оказалось, что конкретные перцептроны или, как их обычно (и неправильно) называют, "нейронные сети" в процессе обучения находят именно локальный оптимум. То есть комара они ловят, и другие задачи распознавания решают, и даже курс акций предсказывают, но часто можно показать, что существует другое решение, то есть другие значения порогов и другая схема передачи сигнала между слоями клеток, которая будет решать эту же задачу лучше. А перейти от одного решения к другому нельзя, потому что система находит локальный оптимум, и любое маленькое изменение ухудшает ситуацию. Остается прыгать неизвестно куда в надежде перескочить хребет и там, в другой долине, найти другой локальный минимум, который может оказаться лучше. Случайный прыжок... похоже на случайную мутацию.
Много-много ноликов и единичек
Любой алгоритм можно представить в виде последовательности нулей и единиц. Ну хотя бы так: описание - это последовательность символов, символы можно пронумеровать, числа записать двоичным кодом. Тогда минимальная мутация - это замена нуля единицей или наоборот, вставление цифры или ее потеря. А не минимальная? Это может быть потеря куска или заимствование куска кода из другого алгоритма. Но ведь коды могут взаимодействовать и как в правильной природе, без мутаций - составляя генетический код законным способом из кодов папы и мамы, то есть из частей двух алгоритмов. Все это безобразие и называют нынче генетическими алгоритмами, а мы назвали вторым пришествием бионики.
Замена нулей на единицы и обратно - не самый умный способ обращения с алгоритмами и уж во всяком случае не единственный. Кажется более разумным переставлять, заимствовать, вводить и исключать осмысленные части алгоритмов, то есть такие элементарные части, которые делают что-то осмысленное. Например, во многих задачах алгоритм записывается в виде логической функции, и можно попробовать взять какой-то осмысленный кусок из одного алгоритма, и вставить его в другой алгоритм. Даже с перцептроном можно поступить подобным образом. Например, обучить неронную сеть распознавать буквы. Другую сеть научить распознавать цифры. Теперь "вырезать" из одной сети кусок (например, несколько слоев) и вставить в другую. Как будет работать эта сеть? Как она будет обучаться? Например, если в одной сети сформировались специализированные группы клеток, как у охотницы на комаров, то они, скорее всего, будут делать свое дело и в комбинированной сети.
Работа по правилам
Конструктор не может соединять части как попало - для работоспособности получившегося устройства должно соблюдаться множество условий (еще до рассмотрения вопроса об эффективности). Части не должны, например, вывести из строя друг друга. В некоторых областях техники эта задача осмыслена, в некоторых решается ad hoc, конкретно для каждого случая. Например, в электронике и в медицине есть понятие совместимости материалов, а у радиотехников есть даже специальная дисциплина (этак, примерно, семестровый курс) - "электромагнитная совместимость".
При использовании генетических методов создания алгоритмов тоже должны соблюдаться некоторые правила. Например, если мы пытаемся соорудить этим способом маршрут обхода некоторого графа (так называемая "задача коммивояжера") заменяемые части маршрута должны начинаться и кончаться в одних и тех же вершинах. Поскольку "нуль-транспортировка" пока не вышла из стен лабораторий. Осознание этих правил может увеличить эффективность работы, а само осознание скорее происходит не тогда, когда инструменты валяются случайной кучей, а когда они осознаны и аккуратно разложены. Можно придумать и другие способы комбинирования алгоритмов, но... но разве мы не всегда это делаем, когда решаем какие-либо задачи - и научные, и технические?
Новое или старое, причем вовсе не забытое
Что такое автомобиль? Это такие-то атомы, находящиеся в таких-то точках пространства. Но конструктор, создавая автомобиль, не располагает в пространстве отдельные атомы - он мыслит более крупными деталями, которые, между прочим, тоже кто-то придумал. Вряд ли правильно говорить, что конструктор использовал болт и гайку из другого автомобиля, но если он в каком-то одном своем проекте придумал и использовал целый узел, то кто мешает ему использовать его в другом?
Далее, конструктор, глядя на кульман или экран, вполне может размышлять - а что, если мы вот эту перегородочку подвинем на пару миллиметров влево... или вправо... Ну чем не мутации? Создание устройства форменным "скрещиванием" двух устройств - тоже не редкость. Когда встраивают калькулятор в часы, то получаются часы с игрушечным калькулятором, а не полноценный гибрид, но, например, комбинация приемника и магнитофона вполне жизнеспособна. Получается, что все эти приемы давно известны и успешно применяются. В чем же тогда новизна? Только в том, что конструктры делали все это, не придумывая новых слов, а разработчики алгоритмов просто заглянули в учебник биологии, слямзили оттуда словечко и радуются?
Зачем нужно осознание
Употребление новых для данной области слов часто (хотя и не всегда) означает определенную стадию осознания, возникновения модели явления или метода, понимание его структуры и в некоторых случаях - механизма действия. Это влечет за собой возможность оптимизации. Как только мы представляем явление в виде модели, мы вводим какие-то параметры. Значит, возникает вопрос о выборе их значений и возможность оптимизации.
При применении генетических методов синтеза алгоритмов этих параметров несколько. Например, чстота мутаций, размер и частота заимствования кусков генетического кода и другие. В биологии, например, существует оптимальная частота мутаций (при фиксированном темпе изменений условий среды). Цивилизация планеты Земля пошла по технологическому пути, и от ледникового периода мы будем защищаться теплоизоляторами, но "биологическая цивилизация" при наступлении глобального похолодания могла бы увеличить частоту мутаций, чтобы приспособиться, а не вымереть. Для этого ее представителям пришлось бы переселиться поближе к "естественному реактору Окло" или начать сознательно принимать мутагены. Увеличивать частоту мутаций мы умеем, и поставить задачу нахождения оптимальной частоты мутаций при тех или иных изменениях окружающей среды можно уже сейчас. Для начала на дрозофилах.
Возникновение понятия, модели означает такую стадию осмысления, при которой модель начинает втягивать в себя "рядом лежащие" решения. При этом выявляются какие-то новые решения, до этого таившиеся в куче лежащих вместе. Представьте себе тысячу цветных шариков, раскрашенных во все цвета "цветового треугольника". Классифицировать и вообще как-то разобраться в этой куче не просто. Но если мы сумеем создать модель аддитивного сложения цветов, вытащим из кучи все шарики цвета "спектральный + белый" и посмотрим на то, что останется, мы немедленно осознаем, что такое "пурпурный" (смесь синего и красного).
Поэтому осознание того, что такое "генетический алгоритм" (правильнее было бы говорить "генетический метод построения алгоритмов, но это очень длинно), позволит не только оптимизировать их, но и понять, есть ли в этой куче еще что-то новенькое. Потому что область эта вообще очень нова.
А раз так...
... то мы можем позволить себе небольшой экскурс именно что в "кучу" - то есть в область рядом с генетическими алгоритмами. Эволюционировать неким квазибиологическим способом могут не только алгоритмы, но и "железки". Причем сами.
Берем интегральную схему, которая называется Field Programmable Gate Array или электрически программируемая матрица вентилей. Схема состоит из множества ячеек, способных выполнять простейшие функции, но не имеющих между собой фиксированных связей. Связи устанавливаются программой, по командам управляющего микропроцессора, и могут изменяться в процессе работы схемы. Эволюцию на таком устройстве нетрудно организовать при помощи генетического алгоритма. Для этого создается некая "популяция" конструкций, то есть схем соединения элементарных ячеек. Каждая "особь" поочередно испытывается на приспособленность к выполнению поставленной задачи, причем задача может быть какой угодно, например, различать два сигнала разных частот или амплитуд. Схемы, которые это делают плохо - наименее приспособленные - отсеиваются, хорошие скрещиваются, мутируют и так далее, как это принято в генетических алгоритмах. В некоторых случаях таким способом удается создать схемы, которые неплохо решают поставленную задачу. Слова "удается создать" кажутся в этой ситуации несколько притянутыми за уши. Лучше было бы сказать - "схемы создаются".
В этом направлении получены самые-самые первые результаты, и они выглядят довольно странно. Схемы действительно работают, но они оказались не термостабильны. Это первая странность, а вторая вот какая - работа схем в некоторых случаях зависит от того, подано ли питание на часть схемы, вообще не соединенную цепями передачи сигнала с основной схемой. Авторы никак не комментируют эту дважды забавную ситуацию, но напрашивается гипотеза - схема каким-то образом "использует" утечки (они как раз сильно зависят от температуры) и, может быть, паразитные емкости.
Любая схема может быть описана некоторыми алгоритмом обработки сигнала. Поэтому (если пренебречь утечками и емкостями) нет принципиальной разницы - применять генетические методы к схемам или алгоритмам. Однако разработка путем оптимизирующей эволюции схемы "в железе" может оказаться более быстрым процессом, чем разработка алгоритма обработки и лишь затем реализация его в железе (то есть в кремнии). Но важнее другое - применение генетических алгоритмов в железе автоматически приводит к выполнению важного условия - мы переставляем, заменяем и т.д. уже осмысленные части, которые сами умеют что-то делать. А не случайно выбранные участки длиной-длиной цепи нулей и единиц.
Некоторые биологи считают, что оценки так называемой "вероятности возникновения живого" неверны потому, что не учитывается обмен генами, который эту "вероятность" сильно увеличивает. (На самом деле, понятие вероятности здесь неприменимо, но сейчас речь не об этом.) Возможно, что эту вероятность еще более увеличивает некоторый механизм контроля процесса обмена участками кода, позволяющий переставляться только законченным, осмысленным участкам. Фразам, а не отдельным буквам.
Кстати, замена букв обычно порождает довольно плоские шутки, а слов или тем паче, фраз - порождает афоризмы.
Связаться с программистом сайта.
