Представить непредставимое
 
08.12.2003
Михаил Бурцев

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

Компьютерная революция дала возможность строить модели сложных систем и решать сложные задачи. Но она же привела к возникновению парадокса калькулятора: нужно ли учить детей делить в столбик, даже если они никогда не будут этого делать? В науке есть похожая проблема: построив сложный алгоритм, который генерирует ряд чисел, являющихся решением поставленной задачи, ученый зачастую не может ясно представить, почему числа оказались именно такими. Ему необходим инструмент для облегчения понимания задачи и процесса ее решения, чтобы эффективнее находить ошибки и лучше контролировать процесс. Один из таких инструментов — компьютерная визуализация.

В современной компьютерной науке модны «мягкие вычисления» — нечеткие логики, нейронные сети, эволюционные алгоритмы. Поговорим о визуализации последних.

Наиболее широко эволюционные алгоритмы используются в задачах оптимизации. Для поиска наилучшего решения создается популяция пробных решений, которая затем эволюционирует. В процессе эволюции отдельные решения смешиваются и слегка изменяются случайным образом, а затем проверяются получившиеся решения; те из них, которые лучше соответствуют выбранному критерию, «выживают» и используются для формирования следующего поколения, худшие решения отбрасываются. Обычно, чтобы добиться требуемой эффективности от эволюционного алгоритма, с легкостью пожирающего вычислительные ресурсы, необходимо настроить большое количество параметров. Тут-то и появляется потребность в визуализации (рисунки к статье взяты с alife8.alife.org/workshops.html).

Эволюцию популяции решений можно представить как движение облака точек в многомерном параметрическом пространстве, где каждой точке соответствует некоторая величина, являющаяся оценкой качества решения — его приспособленности. Таким образом, мы получаем ландшафт приспособленности (fitness landscape), по которому движется популяция. Движение решения по ландшафту приспособленности похоже на движение частицы в потенциальном поле, только частица стремится к минимуму потенциальной энергии, а решение — к максимуму приспособленности (см. врезку «Визуализация эволюции нейронной сети»).

Визуализация эволюции нейронной сети

123

Лионель Барнет (Lionel Barnett) из Университета Сассекса (Великобритания) исследовал задачу эволюционной оптимизации весов нейронной сети для получения функции исключающего ИЛИ. Сеть состояла из двух входных нейронов и одного выходного, соединенных девятью рекуррентными связями. Оптимальность («приспособленность») характеризовалась максимально быстрым срабатыванием (переходом в нужное состояние после получения входных сигналов) и максимально долгим нахождением в этом состоянии после отключения входов.

456

7

Вид двумерных срезов девятимерного ландшафта приспособленности для этой задачи показан на рис. 1, 2. Срезы позволяют нам сразу же обнаружить достаточно высокие «ложные» максимумы приспособленности, которые затрудняют решение задачи. На таких срезах можно отображать и процесс решения задачи (рис. 3, 4) — ход эволюции показывает извилистая белая линия. Видно, как после длительного блуждания по очередному плато эволюция нащупывает путь к резкому повышению приспособленности — траектория скачком переходит на более высокое плато. Помимо визуализации ландшафта приспособленности, Барнет построил фазовые портреты оптимизированной системы (рис. 5, 6, 7). Такое наглядное представление не только демонстрирует качественную картину поведения нейронной сети, но и помогает выявить слабые места эволюционного алгоритма и в конечном счете повысить его эффективность.

 

Визуализация пространства поиска при помощи графа

Если для задач с малой размерностью визуализация ландшафта приспособленности в виде набора трехмерных картинок (два параметра и приспособленность) оправданна, то при высокой размерности возникает вопрос: какие сечения из всех возможных будут наиболее информативны? Выходит, нужен метод, позволяющий так «свернуть» ландшафт приспособленности, чтобы изобразить его на «плоскости», не потеряв при этом важную информацию. Это можно попытаться сделать, представив пространство решений в виде графа специального вида.

Пол Лейзел (Paul Layzell), сотрудник бристольской лаборатории Hewlett-Packard, занимается исследованиями использования эволюционных алгоритмов при разработке электронных схем. Он предложил визуализировать пространство поиска при помощи графа.

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

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

Результаты визуализации для первой схемы кодирования приведены на рис. 8. Вершины графа распались на кластеры, одни из которых вообще не связаны с соседними, а остальные связаны слабо. Это говорит о том, что использование первой схемы кодирования приводит к сложной задаче для генетического алгоритма. Для второй схемы кодирования все вершины попали в два больших сильно связанных кластера (рис. 9). Кроме того, кластеры имеют достаточно соединяющих их связей, и решить задачу, получившуюся в результате применения второго варианта кодирования, будет гораздо легче.

89

Визуализация ландшафта приспособленности очень трудоемка; ведь чтобы построить ландшафт, мы просто решаем задачу во всех точках выбранной области пространства. Если такая визуализация требует неприемлемых затрат времени, можно использовать данные, сгенерированные алгоритмом в процессе оптимизации. Например, можно построить граф, отражающий связь решений от поколения к поколению (см. врезку «Сети Tierr’ы»). Такой граф хоть и не несет исчерпывающую информацию обо всей области пространства решений, но может дать полезные сведения для понимания динамики самого алгоритма (в данном случае — процесса эволюции программ).

 

 

Сети Tierr’ы

10Более десяти лет назад Том Рэй (Tom Ray) создал модель под названием Tierra. Tierra — это область памяти компьютера, в которой эволюционируют самовоспроизводящиеся программы на ассемблере. Память, однако, ограничена, и выживают лишь те программы, чей код короче и кто размножается быстрее.
Исследователи из Австралии, участвующие в разработке коммерческого продукта NetMap (www.altaanalytics.com), предназначенного для визуализации в виде сетей сложных взаимоотношений между объектами, применили его для визуализации сети «родственных» отношений между программами для одной из реализаций эволюции в Tierr’е.
NetMap представляет сеть в виде набора окружностей. На рис. 10 совокупность всех «генотипов» программ, хотя бы раз появившихся в ходе эволюции, упорядочена по частоте встречаемости и выстроена в форме большой центральной окружности. Эта окружность разбита на интервалы — кластеры генотипов по частоте встречаемости. Чтобы увидеть, как связана такая кластеризация с кластеризацией по родственным связям, к каждому интервалу пристроены извне окружности поменьше — на них расположены генотипы из данного интервала и показаны родственные связи между ними. Центральная окружность плотно заполнена зелеными отрезками — они показывают все родственные связи между генотипами, и усмотреть там какую-либо структуру очень трудно. Анализ же внешних окружностей позволяет обнаружить любопытные эффекты. Например, есть очень большие кластеры генотипов, возникающих примерно с одинаковой частотой, но не связанных отношениями родства; в то же время самый большой кластер встречаемости имеет и самую большую плотность внутренних связей. Видно, что и сами внешние окружности распадаются на два больших кластера. Изучение таких явлений может пролить свет на качественные параметры сложных комбинаторных процессов, порождаемых правилами эволюции.


<<Нефритовое оружие пролетариата
Все материалы номера
Что мы мечтаем увидеть? >>