Представить непредставимое

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

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

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

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

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

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

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

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

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

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

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

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

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