Вопрос экономного кодирования информации в системах управления был поставлен в первой половине 1970-х годов, но не потерял актуальности и до сих пор. В связи с прогрессом компьютерных и инженерных разработок поток информации, получаемый из различных областей науки, и техники возрос в сотни и тысячи раз. С развитием глобализации и интеграции появились всемирные проекты и организации, которые стремились объединить общие знания в одно целое, а затем и использовать эти данные, максимально сохраняя и оптимально извлекая всю информацию. Таких областей изучения мировых процессов и явлений большое множество. Одна из них, наука о водной оболочке земли – гидрология. Основная работа по организации и осуществлению наблюдений, сбора и обработки информации о состоянии гидросферы выполняется национальными метеорологическими, гидрологическими, геологическими службами и водохозяйственными организациями стран земного шара. В настоящее время на земном шаре действуют около 9 тыс. станций на суше, производящих наблюдения за влажностью воздуха, облачностью, количеством выпадающих атмосферных осадков (из них 350 автоматизированы или частично автоматизированы). Около 700 морских судов производят наблюдения за различными параметрами состояния вод Мирового океана (температура, соленость и минеральный состав вод, направление течений). Эти данные дополняются наблюдениями с коммерческих самолетов (около 10 тыс. сводок в сутки).
В 2003 году Группа ученых из Японии, США и Европы подготовила программу глобального исследования океана. По всему миру распределили около 3 тысяч самопогружающихся датчиков. В течение 3-4 лет они будут собирать подробные данные о течениях, фиксировать колебания температуры, концентрацию соли и прочие параметры, которые, по мнению специалистов, помогут предсказывать изменения климата на планете. Эксперимент получил название "Арго-программа". Оборудованные специальной аппаратурой датчики цилиндрической формы погружаются на глубину 2-х километров и остаются там в течение десяти часов. После этого приборы длиной около метра и диаметром 20 сантиметров автоматически всплывают на поверхность, связываются с помощью антенн со спутниками и передают собранную информацию на наземные станции, а затем вновь уходят под воду. Для хранения и автоматизации обобщения информации создаются специальные банки данных. В странах с небольшой по площади территорией принято создавать единые банки для всех компонентов гидросферы или два-три банка, собирающие информацию по атмосферным компонентам гидросферы, водным объектам суши, Мирового океана (включая окраинные и внутренние моря, морские устья рек). Такой огромный объем информации, который нужно ежедневно обрабатывать (а главная проблема состоит в том, что их нужно хранить в течение несколько десятков лет для дальнейшего анализа) приводит к необходимости сжатия информации и дальнейшем ее восстановлении с минимальными потерями.
На сегодняшний день существует множество алгоритмов сжатия, которые имеют как свои достоинства, так и недостатки. Основными из них являются сжатие таблиц (экономия места достигается за счет удаления избыточных копий значений данных в таблице), упаковка битов (заключается в кодировании значения атрибута битовыми последовательностями фиксированной длины), арифметическое кодирование (Предполагаемая требуемая последовательность символов рассматривается как некоторая двоичная дробь из интервала [0, 1). Результат сжатия представляется как последовательность двоичных цифр из записи этой дроби) и др. Главными недостатками всех методов является то, что при сжатии происходит значительная потеря информации, которую нельзя восстановить. Обычно приводимые оценки степени сжатия баз данных составляют 2..5 раз, часто отмечается ускорение выполнения запросов за счет сжатия на несколько десятков процентов и больше, что все равно является недостаточным для очень больших систем и объемов информации
В качестве метода сжатия гидрологических данных в данной статье предлагается метод генетического программирования. Метод генетического программирования строится на основании концепции генетических алгоритмов. По этой концепции случайным методом генерируются 2 особи, которые на следующем шаге используются для репродукции новых пар, а затем генерации новых особей из этих пар. Новые особи подвергаются отбору и мутации, а затем, исходя из постановки задачи, выбираются новые особи, которые могут породить более оптимальное потомство.
В генетическом программировании хромосомами являются программы. Программы представлены как деревья с функциональными (промежуточные) и терминальными (конечные) элементами. Терминальными элементами являются константы, действия и функции без аргументов, функциональными - функции, использующие аргументы.
Для того чтобы применить генетическое программирование к какой-либо проблеме, необходимо определить:
· Множество терминальных элементов.
· Множество функциональных элементов.
· Меру приспособленности (fitness).
· Параметры, контролирующие эволюцию.
· Критерий останова эволюции.
Набор терминалов, представляет собой компоненты, из которых будет создаваться функция для полного или частичного решения проблемы.
Второй шаг заключается в определении функционального множества, элементы которого должны использоваться для генерации математических выражений.
Рассмотрим для примера функцию sqrt(arctg(x+3)*5). Ее можно представить в следующем виде:
Рис. 1 – Функция sqrt(arctg(x+3)*5), представленная в виде дерева
Для данного дерева терминалами будут являться – х, 3, 5, а функционалами – arctg, sqrt и ln. Рассмотрим 2 функцию, а затем взимодействие их:
Рис. 2 – Функция 8x*x, представленная в виде дерева
Если теперь подвергнуть 2 этих особи (дерева) операции кроссинговера, то в результате получим 2 новых особи:
Рис.3 – Генерация новых особей
Из приведенного рисунк видно, что деревья обменялись составными частями, в результате чего возникли новые функции 2 и 5*ln5, которая является константой. Далее особи подвергаеются мутации – замене какого-нибудь узла дерева на другой, наприме константа 8 изменится на переменную х. После этого вновь полученные особи участвуют в генерации новых.
Исходя из теории генетического программирования, цель его использования для сжатия данных состоит в том, чтобы для большого набора входящих данных (не имеет значение какого рода, т.е. это могут быть температура, давление, концентрация конкретных веществ или любые другие коэффициенты и параметры гидрологических исследований) подобрать функции, которые оптимально сворачивают эти данные и позволяют потом при имеющемся типе функции, а также ее коэффициентах получить эти данные для обработки.
Допустим, в течение 5 лет производится измерение скорости течения «Гольфстрим» на разной глубине. За один день производится 1000 измерений. Тогда метод сжатия будет заключаться в подборе методом генетического программирования (исходя из начальных функционалов и терминалов) 5-6 или более функций, с помощью объединения которых можно будет потом получить весь набор точек. Возможно, что скорость течения будет одинакова на всех точках, тогда функция будет одна и представлять собой константу. Также возможна ситуация, когда на какой-то точке измерения будет наблюдаться скачок. При этом не получится подобрать никакую функцию и придется хранить эту точку отдельно. В любом случае данных нужно будет хранить намного меньше.
Кроме самого результата сжатия такой метод предполагает одновременный анализ данных, который может прослеживаться на больших временных отрезках и при этом не обязательно раскодирование. Так например при анализе температуры, видя, что функция температуры имеет приблизительный вид прямой можно сократить измерения на данном участке объекта или сделать их более дискретными.
Разбивая задачу сжатия данных таким методом можно выделить следующие этапы:
· Одним из методов поиска определить диапазон, в котором будут находиться возможные терминалы
Действительно, для генерации функций нужно оперировать какими-то начальными константами. Взять их произвольно можно лишь в том случае, если на этапе мутации предоставить в алгоритме возможность замену константы на любую другую случайным образом из конкретного диапазона. Опять же, в данном случае нужно каким-то образом проанализировать диапазон (возможно, исходя из максимального и минимального значений полученных измерений). Вариантом поиска коэффициентов может быть метод Ньютона, с помощью которго можно будет решить систему уравнений для поиска коэффициентов.
· Задаться набором минифункций, на основании которых будет производиться поиск функции или набора функций, кодирующих заданную последовательность параметров
Такая последовательность может быть как определа пользователем в диалоге, так и использована непосредственно в алгоритме (станадртные наборы типа - +,-,*,/, ,cos, sin, log и.т.д)
· Определить параметры алгоритма, такие как способ мутации, способ селекции
Способ мутации может заключаться в произвольном выборе узла (на каждом шаге он определяется случайным образом) или в конкретном (номер узла задается как констата перед общим циклом генерации). Селекция обычно проводится методом рулетки, т.е. определяются вероятности выживаемости особей и выбираются те, у которых эта веротяность больше. После селекции “плохие” особи отбрасываются для того, чтобы не произошло “затухания потомства”.
· Реализовать алгоритм сжатия
Кроме создания методом генетического программирования функции, нужно будет проверить, какое количество точек эта функция может кодировать с заднной точностью. На первом этапе будет производиться поиск с одной функцией, потом с двумя и так далее. Таким образом, кроме программной реализации, задачи стоит анализ выбора максимального размера как общего количества функций, так и количества узлов в каждом дереве-функции. Т.е. после 2-3 запусков алгоритма нужно оперделить, когда уже не имеет смысла генерировать новые особи , т.к. это не приведет к искомому результату.
· Провести анализ алгоритма на разных наборах данных при различной точности
· Определить недостатки и достоинства данного метода
Два последних этапа носят сугубо аналитичный характер. Главной их задачей будет доказать, что используемый метод работает на больших выборках. Минимальный коэффициент сжатия данных планируется 5-7 единиц, что должно превысить существующие на данный момент коэффициенты среди методов сжатия числовой информации.