Программирование с экспрессией генов: способы кодирования и создания синтаксических деревьев

Программирование с экспрессией генов: способы кодирования и создания синтаксических деревьев

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

Повний опис

Збережено в:
Бібліографічні деталі
Дата:2015
Автори: Руденко, О.Г., Мирошниченко, С.В., Бессонов, А.А.
Формат: Стаття
Мова:Russian
Опубліковано: Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2015
Назва видання:Управляющие системы и машины
Теми:
Приложения. Опыт разработки и внедрения
Онлайн доступ:http://dspace.nbuv.gov.ua/handle/123456789/87231
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Программирование с экспрессией генов: способы кодирования и создания синтаксических деревьев / О.Г. Руденко, С.В. Мирошниченко, А.А. Бессонов // Управляющие системы и машины. — 2015. — № 3. — С. 82–92. — Бібліогр.: 14 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-87231
record_format dspace
spelling irk-123456789-872312015-10-15T03:02:17Z Программирование с экспрессией генов: способы кодирования и создания синтаксических деревьев Руденко, О.Г. Мирошниченко, С.В. Бессонов, А.А. Приложения. Опыт разработки и внедрения Проанализированы алгоритм программирования с экспрессией генов, различные схемы кодирования синтаксических деревьев для их последующей линеаризации и хранения, описана процедура создания начальной популяции. Разработана универсальная методика, позволяющая определить производительность модификаций алгоритма по любым метрикам. Сравнение схем кодирования позволило определить область их эффективного применения. The gene expression programming algorithm is analyzed, various coding schemes of syntax trees for subsequent linearization and storage are considered, the procedure for creating the initial population is described. A universal method allowing to determine the algorithm modifications performance on any metrics is developed. The comparison of the coding schemes allows to determine the area of their effective application. Проаналізовано алгоритм програмування з експресією генів, різні схеми кодування синтаксичних дерев для їх подальшої лінеаризації та зберігання, описано процедуру створення початкової популяції. Розроблено універсальну методику, яка дозволяє визначити продуктивність модифікацій алгоритму за будь-якими метриками. Порівняння схем кодування дозволяє визначити галузь їх ефективного застосування. 2015 Article Программирование с экспрессией генов: способы кодирования и создания синтаксических деревьев / О.Г. Руденко, С.В. Мирошниченко, А.А. Бессонов // Управляющие системы и машины. — 2015. — № 3. — С. 82–92. — Бібліогр.: 14 назв. — рос. 0130-5395 http://dspace.nbuv.gov.ua/handle/123456789/87231 519.71 ru Управляющие системы и машины Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Russian
topic Приложения. Опыт разработки и внедрения
Приложения. Опыт разработки и внедрения
spellingShingle Приложения. Опыт разработки и внедрения
Приложения. Опыт разработки и внедрения
Руденко, О.Г.
Мирошниченко, С.В.
Бессонов, А.А.
Программирование с экспрессией генов: способы кодирования и создания синтаксических деревьев
Управляющие системы и машины
description Проанализированы алгоритм программирования с экспрессией генов, различные схемы кодирования синтаксических деревьев для их последующей линеаризации и хранения, описана процедура создания начальной популяции. Разработана универсальная методика, позволяющая определить производительность модификаций алгоритма по любым метрикам. Сравнение схем кодирования позволило определить область их эффективного применения.
format Article
author Руденко, О.Г.
Мирошниченко, С.В.
Бессонов, А.А.
author_facet Руденко, О.Г.
Мирошниченко, С.В.
Бессонов, А.А.
author_sort Руденко, О.Г.
title Программирование с экспрессией генов: способы кодирования и создания синтаксических деревьев
title_short Программирование с экспрессией генов: способы кодирования и создания синтаксических деревьев
title_full Программирование с экспрессией генов: способы кодирования и создания синтаксических деревьев
title_fullStr Программирование с экспрессией генов: способы кодирования и создания синтаксических деревьев
title_full_unstemmed Программирование с экспрессией генов: способы кодирования и создания синтаксических деревьев
title_sort программирование с экспрессией генов: способы кодирования и создания синтаксических деревьев
publisher Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
publishDate 2015
topic_facet Приложения. Опыт разработки и внедрения
url http://dspace.nbuv.gov.ua/handle/123456789/87231
citation_txt Программирование с экспрессией генов: способы кодирования и создания синтаксических деревьев / О.Г. Руденко, С.В. Мирошниченко, А.А. Бессонов // Управляющие системы и машины. — 2015. — № 3. — С. 82–92. — Бібліогр.: 14 назв. — рос.
series Управляющие системы и машины
work_keys_str_mv AT rudenkoog programmirovaniesékspressiejgenovsposobykodirovaniâisozdaniâsintaksičeskihderevʹev
AT mirošničenkosv programmirovaniesékspressiejgenovsposobykodirovaniâisozdaniâsintaksičeskihderevʹev
AT bessonovaa programmirovaniesékspressiejgenovsposobykodirovaniâisozdaniâsintaksičeskihderevʹev
first_indexed 2025-07-06T14:49:39Z
last_indexed 2025-07-06T14:49:39Z
_version_ 1836909467208253440
fulltext 82 УСиМ, 2015, № 3 УДК 519.71 О.Г. Руденко, С.В. Мирошниченко, А.А. Бессонов Программирование с экспрессией генов: способы кодирования и создания синтаксических деревьев Проанализированы алгоритм программирования с экспрессией генов, различные схемы кодирования синтаксических деревьев для их последующей линеаризации и хранения, описана процедура создания начальной популяции. Разработана универсаль- ная методика, позволяющая определить производительность модификаций алгоритма по любым метрикам. Сравнение схем кодирования позволило определить область их эффективного применения. The gene expression programming algorithm is analyzed, various coding schemes of syntax trees for subsequent linearization and storage are considered, the procedure for creating the initial population is described. A universal method allowing to determine the algorithm modifications performance on any metrics is developed. The comparison of the coding schemes allows to determine the area of their effective application. Проаналізовано алгоритм програмування з експресією генів, різні схеми кодування синтаксичних дерев для їх подальшої ліне- аризації та зберігання, описано процедуру створення початкової популяції. Розроблено універсальну методику, яка дозволяє визначити продуктивність модифікацій алгоритму за будь-якими метриками. Порівняння схем кодування дозволяє визначити галузь їх ефективного застосування. Введение. Эволюционные вычисления – тер- мин, применяемый к техникам глобальной оп- тимизации, характерной особенностью кото- рых является подобие их процессов биологи- ческой эволюции. Вместо работы с одним оп- ределенным вариантом решения, эволюцион- ные техники начинают процесс поиска с попу- ляции вариантов решения, созданных случай- ным образом. Начальная популяция эволю- ционирует в набор улучшенных решений, ите- ративно проходя три этапа: отбор, рекомбина- цию и мутацию. Наиболее приспособленные решения отбираются для участия в рекомби- нации с целью создания нового поколения, а оператор мутации вносит в него разнообразие. В ходе этого процесса лучшие особи передают свои характеристики следующим поколениям. При достаточном количестве итераций эволю- ционные алгоритмы способны находить реше- ния многих сложных задач. В качестве функции, определяющей коли- чественную оценку особи – степень соответст- вия построенной модели условию задачи – и называемой функцией фитнеса (fitness function), чаще всего применяется значение среднеквад- ратичного отклонения (СКО). При таком под- ходе генетическое программирование и другие эволюционные техники могут за короткое вре- мя находить оптимальные либо околооптималь- ные решения задач и ситуаций. Использование этих техник не требует индивидуального руч- ного поиска оптимального решения каждой за- дачи – описанный процесс автоматизирован и выполняется компьютером, однако для этого необходимы значительные вычислительные ресурсы [1]. Генетические алгоритмы (ГА) были созда- ны в 1960 годы, когда Джон Холланд приме- нил теорию биологической эволюции к ком- пьютерным системам [2]. Как и все эволюци- онные компьютерные системы, ГА представ- ляет собой упрощенную модель биологичес- кой эволюции. При таком подходе варианты решения задач кодируются символьными стро- ками (обычно состоящими из нулей и единиц), и популяция этих вариантов решения участву- ет в процессе эволюции, цель которой – полу- чение наилучшего решения. Развитие идеи кодирования нелинейных структур разных размеров и форм Джоном Ко- зой привело к появлению в 1992 г. генетиче- ского программирования (ГП) [3]. Программирование с экспрессией генов (ПЭГ), как в целом и ГА и ГП, – это генетиче- ский алгоритм с такими характерными черта- ми, как популяция особей, их отбор на основе приспособленности (фитнеса) и изменчивость на основе генетических операторов [4]. Фун- даментальное отличие этих трех алгоритмов заключается в природе особей: в ГА это строки УСиМ, 2015, № 3 83 фиксированной длины (хромосомы); в ГП – нелинейные сущности переменной длины и формы (синтаксические деревья). В ПЭГ особи кодируются в виде строк фиксированной дли- ны (называемых геномом, либо хромосомами [5]), которые затем декодируются для получе- ния синтаксических деревьев. Различие между ГА и ГП выражено не силь- но: обе системы используют один вид объек- тов, который служит как генотипом, так и фе- нотипом. Такой подход имеет одно из двух ог- раничений: простота применения генетических операторов к объектам означает их недоста- точную выразительность и сложность этих объектов (в случае ГА), а их сложность ведет к трудностям при воспроизводстве и модифика- ции (в случае ГП). ПЭГ лишено указанных ограничений и об- ладает следующими преимуществами:  простота хромосом: линейность, компакт- ность, относительно небольшой размер, про- стота применения операторов, таких как реп- ликация, мутация, рекомбинация, перенос и пр.;  экспрессия (декодирование компактной структуры) генома порождает фенотип – син- таксическое дерево, которое может представ- лять математическую формулу либо програм- му. Значения вычисленной формулы, выпол- ненной программы служат для численной оцен- ки приспособленности особи с помощью функции фитнеса. Таким образом, участие хромосомы в про- цессе воспроизведения зависит от фитнеса де- рева, которое она кодирует. Для этого требует- ся универсальная система перевода формата генома в формат дерева и обратно, при кото- рой любое изменение хромосомы с помощью операторов всегда приводит к синтаксически корректному дереву, обеспечивая приспосаб- ливаемость и эволюционирование. Исходный алгоритм ПЭГ На рис. 1 показана блок-схема алгоритма ПЭГ [4]. Процесс начинается с конструирования по- пуляции случайным образом созданных хромо- сом. После экспрессии (декодирования) хромо- сом каждая особь выполняется на заданном на- боре входных данных (в виде координат точек для математических задач, таблиц истинности при поиске булевых выражений, наборов при- знаков при решении задач классификации и т.д.). На основе результатов выполнения особей вы- числяется фитнес каждой из них, позволяющий отобрать и подвергнуть изменениям особи, на- целенные на получение потомства – популяции с новыми характеристиками. С этой популяцией проводятся те же операции: декодирование ге- нома, отбор, воспроизведение с модификациями. Процесс повторяется заданное количество ите- раций либо до получения решения. Рис. 1 Воспроизведение включает в себя не только репликацию, но и выполнение генетических опе- раторов, вносящих разнообразие. Во время реп- ликации геном особи в точности, без изменений копируется и переносится в новое поколение. Очевидно, этот оператор не способен вносить разнообразие, потому требуется вмешательство оставшихся операторов, случайным образом вы- бирающих особи, к которым они будут приме- нены. Так, в ПЭГ особь может быть модифици- рована сразу несколькими операторами, а может оказаться и не измененной [5]. 84 УСиМ, 2015, № 3 Открытые рамки считывания. Структур- ная организация генома в ПЭГ более понятна в биологической терминологии открытых рамок считывания (open reading frames – ORF) – по- следовательностей генома, начинающихся стар- товым кодоном, завершающихся стоповым ко- доном и содержащих кодирующие элементы между ними. В ПЭГ последовательность все- гда начинается с первого элемента гена, но ее конец не всегда совпадает с последним эле- ментом. Таким образом, в ПЭГ нередка ситуа- ция, когда участок от последнего элемента по- следовательности до конца гена не участвует в построении дерева, такие участки называют некодирующими, либо нитронами. В качестве примера рассмотрим следующее алгебраическое выражение:    a b c d   . (1) Выразить формулу (1) можно в виде син- таксического дерева (рис. 2). Рис. 2. Количество ответвлений (дочерних узлов) у узлов, представляющих функцию, равно коли- честву аргументов этой функции. Узлы, соот- ветствующие терминалам (переменным кон- стантам), не имеют дочерних узлов. Изобра- женное дерево и есть фенотипом особи в ПЭГ, в то время как генотип записывается следую- щим образом (в верхнем ряду показаны индек- сы узлов, в нижнем – значения закодирован- ных символов): 01234567 Q* + –аbсd, где очередность элементов обусловлена обхо- дом графа в ширину. Это выражение – откры- тая рамка считывания, в ПЭГ такие записи на- зываются К-выражениями, а язык преобразо- вания К-выражения в дерево и обратно – язы- ком KARVA. Построение дерева из генома за- вершается, когда каждому ответвлению узла- функции поставлен в соответствие дочерний узел. Листья дерева, следовательно, – это тер- миналы. Такая структура генома ПЭГ позволяет ко- дировать деревья различных размеров и форм, оперируя генами фиксированной длины, каж- дый из которых состоит из рамки считывания переменной длины и, при необходимости, не- кодирующего участка для заполнения про- странства между концом кодирующей после- довательности и концом гена. Хромосома осо- би состоит из одного или нескольких таких ге- нов. Функция некодирующих участков, таким образом, состоит в обеспечении того, что дли- на рамки считывания всегда будет меньше или равна длине гена. Это позволяет гарантировать декодирование синтаксически правильного де- рева после любых модификаций генома без ограничений и необходимости проведения слож- ных процедур проверки и редактирования. От- сутствие множества ограничений на генетиче- ские операторы есть коренным отличием ПЭГ от ГП. Геном в ПЭГ. Каждый ген ПЭГ состоит из головы и хвоста. Голова содержит символы как функций, так и терминалов. Хвост содер- жит исключительно терминалы. Для каждой конкретной задачи подбирается длина головы гена h. Обозначим максимальное количество аргументов среди всех функций функциональ- ного множества как n (для большинства ариф- метических функций n = 2; для оператора «ЕСЛИ ТО ИНАЧЕ» n = 3). Тогда минимальную возможную длину хво- ста гена t можно вычислить по следующей формуле: t(h, n) = h  (n – 1) + 1. Следует отметить, что такая структура со- ответствует схеме кодирования путем обхода дерева в ширину, принятого в оригинальном алгоритме ПЭГ. Другие схемы кодирования, которые будут описаны, не требуют условного деления генома на голову и хвост. Еще один параметр, требующий подбора под каждую задачу – количество генов (участ- УСиМ, 2015, № 3 85 ков кода фиксированной длины, содержащих одно дерево) в хромосоме. Обычно использу- ется больше одного гена, и такие хромосомы называют мультигенными. Длина всех генов устанавливается равной для простоты приме- нения операторов. Хромосома представляет со- бой символьную строку, полученную путем конкатенации всех генов. Таким образом, ген – объект, состоящий из пяти атрибутов: G = (Е, Т, F, Op, S), где Е – ге- нотип, Т – терминальное множество, F – функ- циональное множество, Ор – множество опе- раторов, S – значение фитнеса на определен- ном элементе данных. Пример полной записи гена таков: («*++–aabcd», «abcd», «+–*/», 0). Хромосома – объект, состоящий из четырех атрибутов: С = (G, L, Op, S), где G – набор ге- нов, L – связующий оператор. Пример полной записи хромосомы: C1 = ({G0, Gl, G2}, «ab», +,«+ –*/», 0,7). Пример символьной записи хромосомы: 012345678 012345678 012345678 –b*babbab *Qb + abbba –*Qabbaba. Данная хромосома содержит три гена, каж- дый из которых начинается с позиций, обозна- ченных индексом ноль. Окончание рамки счи- тывания каждого гена можно определить лишь после построения закодированного в нем син- таксического дерева; в приведенном примере декодирование первого гена завершается на по- зиции 4 (последний элемент), второго и треть- его – на позиции 5. Каждое дерево может использоваться как в отдельности, с расчетом фитнеса для каждого гена, так и в совокупности, формируя более сложное дерево, фитнес которого и отражает приспособленность особи. Во втором случае каждое субдерево есть отдельной сущностью, компонентом иерархической структуры, пред- ставляющей большую ценность, чем сумма ее частей. Независимая друг от друга эволюция генов хромосомы как отдельных блоков ие- рархической системы при мультигенном под- ходе позволяет более эффективно решать слож- ные задачи. Взаимодействие субдеревьев происходит с помощью связующих функций, для алгебраи- ческих выражений это, как правило, функция арифметического суммирования, для булевых – логическое ИЛИ. Обычно связующая функция устанавливается априори, однако может также быть добавлена в геном и выбираться в про- цессе эволюции. На рис. 3 показано синтакси- ческое дерево, декодированное из рассматри- ваемой трехгенной хромосомы с априорно за- данной связью с помощью функции суммиро- вания. Рис. 3 Такой простой способ кодирования синтак- сических деревьев в виде линейных структур может быть использован и в других видах эво- люционных алгоритмов, например в иммун- ных сетях [6]. Сведение к ГА. Простейшим представле- нием генома в ПЭГ является ген из одного тер- минала. Организация хромосомы, состоящей из одноэлементных генов делает ПЭГ эквивалент- ным ГА. Однако для решения комбинаторных задач требуются особые связывающие функ- ции, отличные от простых арифметических и булевых. Например, для задачи коммивояжера связь отображает расстояние между городами, представленными соответствующими генами. Если обозначить каждый город из девяти от- дельным символом, то следующая хромосома из девяти элементов представит один из воз- можных путей обхода: САDЕВНFIG. Если оптимизационная задача содержит N классов терминалов, хромосома может состо- ять из N групп одноэлементных генов, назы- ваемых мультигенными группами (МГГ – 86 УСиМ, 2015, № 3 multigene family, MGF) [7]. Например, при ото- бражении одного шестиэлементного множест- ва {1, 2, 3, 4, 5, 6} в другое {А, В, С, D, Е, F} хромосома будет состоять из двух шестиэле- ментных групп: 012345 012345 632451 EDFCBA Особенность МГГ – то, что она не содержит повторяющихся элементов, а отображает пере- становку элементов некоторого конечного мно- жества. Потому операторы мутации и реком- бинации к такой структуре генома непримени- мы в силу вероятности некорректных последо- вательностей с повторяющимися и отсутству- ющими элементами. Следовательно, для вне- сения генетического разнообразия должны быть созданы новые операторы, порождающие кор- ректные структуры. Один из таких операторов – инверсия, впер- вые описанная в [1], суть которой состоит в изменении порядка следования элементов в слу- чайным образом выбранного участка МГГ. Так, например, результатом применения к хромо- соме из предыдущего примера может стать следующий геном: 012345 012345 632451 ECFDBA Из проведенных экспериментов следует, что оператор инверсии обладает более сильной из- меняющей способностью и, следовательно, наи- более способствует скорейшему обнаружению решения. Оператор перемещения гена распо- лагает случайным образом выбранный ген по другой позиции, сохраняя порядок следования остальных генов группы. Использование дан- ного оператора вместе с более мощными, та- кими как инверсия, может быть полезно для точной подстройки решения. Однако экспери- менты показали [7], что инверсия, используе- мая в одиночку, более эффективна. Оператор перестановки генов меняет мес- тами два случайным образом выбранных гена в пределах МГГ. Исследование оператора пе- ремещения участков гена показало его край- нюю неэффективность – особи-потомки имели, как правило, худший фитнес, чем родитель- ские особи. Иерархическая структура дерева. В ис- ходном алгоритме ПЭГ гены мультигенной хро- мосомы – это не связанные между собой суб- деревья, объединяемые связующим оператором (например, арифметическим сложением). Каж- дый из генов задает свою собственную функ- цию, обнаруженную эволюционным алгорит- мом. В терминологии ПЭГ эти функции назы- ваются автоматически определенными (ADF – automatically defined function). Такие обособлен- ные функции могут использоваться как закон- ченный блок при построении итогового синтак- сического дерева. Для этого требуется услож- нить структуру хромосомы – выстроить иерар- хию генов. В такой сложной хромосоме пер- вые N генов задают функции, а следующие М генов представляют собой клетки – деревья, тер- минальное множество которых состоит из N терминальных символов, обозначающих функ- ции первых N генов хромосомы. Каждая клет- ка – это отдельный способ комбинации генов- функций. Рассмотрим хромосому, состоящую из трех генов-функций и двух клеток (рис. 4): 0123456 0123456 0123456 012345678 012345678 *Q-bbab Q*baabb -/abbab *+21Q1102 /*21+1011 Рис. 4 Многоклеточные хромосомы могут быть по- разному использованы при решении задач: ли- бо как отдельные выходы (например, отража- ющие различные классы в задаче многоклас- совой классификации), либо как задействова- ние какой-либо одной (обычно лучшей) из них в качестве единственного выхода. В ходе экспериментов [8] выяснено, что при решении простых задач наиболее эффективной показала себя структура хромосомы, состоящая всего из одного гена-функции и одной клетки. УСиМ, 2015, № 3 87 Для повышения выразительной силы муль- тигенной хромосомы можно применить другой, более простой вариант иерархической струк- туры: любой ген (кроме первого по порядку) может использовать значения генов, предше- ствующих им в хромосоме [9]. Для этого также используются терминальные символы, соот- ветствующие индексу гена, на значение кото- рого указывает ссылка. Продемонстрировать преимущества такого подхода можно на при- мере функции 2n a при функциональном мно- жестве {+, –, ×, /}. Традиционное кодирование ПЭГ требует в этом случае 2n +1 – 1 символов 2n символа а и 2n – 1 символов *, строка генома выглядит так: *******аааааааа. При подходе MERGE (Multi ExpRession GEne programming – ПЭГ с несколькими выражениями) для этого требуется всего 3×п символов и хромосома из трех генов: 0: *аа 1: *00 2: *11, где 0, 1 – терминальные символы, кодирующие ссылки на гены с индексами ноль и единица. Для гарантии отсутствия циклических ссылок ген ноль не может ссылаться на другие, ген еди- ница может ссылаться на ген ноль, ген два – на гены ноль и единица, ген три – на гены ноль, единица, два и т.д. Кроме того, такая структура мультигенной хромосомы позволяет использовать значения каждого из своих генов как самостоятельный геном особи, имеющий собственное значение фитнеса. Максимальный из фитнесов генов выбирается фитнесом всей хромосомы. Экспериментальная проверка подхода ПЭГ с несколькими выражениями показала его успешность в решении задач даже короткими генами с длиной головы в один–два элемента. Помимо этого, выяснилось, что установка длины гена выше оптимальной не ведет к па- дению производительности алгоритма, в то время как чрезмерная сложность особей, ко- дируемых длинным геномом в исходном ПЭГ, не позволяла быстро находить приемлемые решения. В работе [10] предложена другая модифи- кация автоматически определяемых функций, описанных в [8]. Символ ссылки на ген пред- ставляет собой уже не терминал, отображаю- щий значение запрашиваемого гена для этого набора данных, а элемент особого функцио- нального множества, декодируемого как узел дерева с дочерними узлами-аргументами фун- кции. Отличие состоит в том, что запрашивае- мый ген оперирует аргументами, подаваемыми геном-клеткой, а не переменными выборки данных. Модификация позволила [10] на треть ускорить сходимость. Схемы кодирования дерева Префиксное кодирование. В исходном ал- горитме ПЭГ декодирование дерева выполня- ется путем линейного извлечения элементов генома и установки в узлы формируемого де- рева при его обходе в ширину. При замене об- хода дерева в ширину обходом в глубину по- вышается связность генома – уменьшается рас- стояние между элементами, соответствующи- ми соседним узлам дерева, а субдерево коди- руется непрерывной строкой в геноме. Такой подход способствует сохранению субструктур, что делает менее разрушительным применение операторов скрещивания [11]. Сохранение в популяции субструктур (субдеревьев) лучших особей и их рекомбинация позволяет ускорить сходимость алгоритма: оптимальное решение обнаруживается на более ранних поколениях, т.е. в несколько раз быстрее, качество опти- мального решения зачастую выше, чем резуль- тат работы оригинального алгоритма ПЭГ. От- дельные поддеревья лучших особей можно со- хранять в отдельной, так называемой элитной группе [12], кодируя их дополнительными тер- минальными символами. Поскольку при таком подходе нарушается гарантия получения синтаксически корректно- го дерева из любого генома, сформированного согласно правилам, требуется ввести процеду- ру динамической валидации дерева. К участию в эволюционном процессе допускаются только те особи, декодирование которых порождает корректное дерево. Такая система получила на- звание Р-ДЕР. 88 УСиМ, 2015, № 3 Для взаимодействия между особями и элит- ной группой были введены два новых генети- ческих оператора: оператор сжатия, заменяю- щий последовательность в геноме особи соот- ветствующим терминальным символом из элит- ной группы, и оператор раскрытия, выполня- ющий обратную операцию – замену терминаль- ного символа на соответствующую последова- тельность из элитной группы. Внесение дан- ной модификации в Р-ДЕР привело к обнару- жению решений, имеющих значительно мень- шую погрешность. Кодирование с наложениями. В работе [13] рассматривается разновидность декодирования генома путем обхода дерева в глубину, когда последовательно идущие субдеревья наклады- ваются друг на друга. Элементы генома после- довательно считываются:  если текущий символ принадлежит к тер- минальному множеству – поместить его в син- таксическое дерево как листовой узел;  если текущий символ принадлежит к функ- циональному множеству – поместить его в син- таксическое дерево как узел с количеством до- черних узлов, равным количеству аргументов помещаемой функции; первый дочерний узел – следующий в геноме за текущим, второй – следующий за ним и т.д.; дочерние субдеревья заполняются, следуя этой же процедуре;  при выходе за пределы генома в качестве текущего символа берется первый элемент тер- минального множества. Коренное отличие описанного способа де- кодирования от методов обхода в ширину и в глубину заключается в том, что элементы ге- нома могут быть задействованы в построении дерева неоднократно, и размер получаемого дерева, как правило, бывает больше при рав- ном размере генома. Рассмотрим на примере строки **а+*bс, син- таксическое дерево, образующееся при ее де- кодировании (рис. 5). При использовании традиционного метода декодирования, принятого в ПЭГ, данному де- реву соответствует строка **аа + *bbс, содер- жащая на два символа больше. Выразительная сила генома при декодиро- вании с наложениями значительно выше, что показано в табл. 1, отражающей соответствие максимального возможного размера (количе- ства узлов) синтаксического дерева при рав- ных размерах гена. Рис. 5 Т а б л и ц а 1. Сравнение выразительной силы ПЭГ с нало- жениями Размер гена ПЭГ ПЭГ с наложениями 3 3 9 5 5 25 7 7 67 9 9 177 11 11 465 13 13 1219 15 15 3193 17 17 8361 Повышение выразительной силы генома по- зволяет использовать более короткие хромо- сомы, что, в свою очередь, значительно пони- жает вычислительную сложность алгоритма: разница в скорости обработки экспоненциаль- но растет, при длине хромосомы в 23 элемента ускорение достигает 10 раз. Алгоритм, осно- ванный на таком подходе, получил название EAOGE – Evolutionary Algorithm based on Overlapped Gene expression – эволюционный алгоритм на основе ПЭГ с наложениями. Нейтральные гены После декодирования хромосомы ПЭГ и конструирования синтаксического дерева ко- личество узлов полученного дерева в предель- ном случае будет равно размеру хромосомы, однако в большинстве случаев будет меньшим. Те элементы в хвостах генов, которые не были использованы при построении дерева, называ- ются некодирующими участками. Кроме того, полученное дерево может содержать выраже- УСиМ, 2015, № 3 89 ния вида (а – а), (а × 0), (а – 0) и другие, кото- рые при семантическом анализе упрощаются, устраняя данные интроны и образуя более ком- пактное дерево. Множество подобных участ- ков – часто повторяющихся последовательно- стей, интронов, псевдогенов и прочего – встречается в природе в ДНК живых существ. Потому логично предположить, что и в искус- ственном геноме нейтральные участки могут быть полезны. Среднее количество нейтраль- ных последовательностей в популяции растет с увеличением как количества генов в хромосо- ме, так и размера каждого из них. Исследования работы алгоритма с различной длиной генома показали [14], что эволюциони- рование особей с высокой степенью избыточно- сти генома происходит эффективней. Это связа- но с тем, что у каждого решения, представлен- ного в наиболее компактной форме, существует множество менее компактных вариантов пред- ставления, увеличенных в размерах посредством интронов. Кроме того, накапливаемые в некоди- рующих участках мутации могут быть исполь- зованы в дальнейшем, если изменения в голове гена (добавление функциональных узлов) при- ведут к увеличению размера дерева. Методика тестирования Создание начальной популяции. В изу- ченных работах о ПЭГ не уделяется внимания процедуре создания начальной популяции, а именно конструированию случайной особи. Указано, что строка хромосомы обходится с начала и по порядку, и каждый символ задает- ся случайным образом: тип узла может быть равновероятно задан как функциональный элемент, как переменная (подаваемая на вход модели) и как числовая константа. Очевидно, что размер дерева определяется количеством подряд (близко) идущих функциональных уз- лов, начиная с корневого узла (первого симво- ла хромосомы): из условия равновероятности типов узлов (три типа – 33,333 процента каж- дый) следует, что вероятность создания дерева, состоящего всего из одного элемента (терми- нала: переменной либо константы), составляет 66,67 процента. При этом можно заметить, что средняя длина получаемых деревьев не зави- сит от задаваемой длины хромосомы, но опре- деляется установленной вероятностью появле- ния того или иного типа. При оригинальном кодировании элементов путем обхода узлов дерева в ширину логично предположить, что вероятность появления функ- циональных узлов в головной части хромосо- мы следует повысить, в то время как в хвосто- вой части могут быть помещены исключитель- но терминальные узлы. В таком случае опре- деление оптимальных численных значений ве- роятностей представляет собой отдельную за- дачу для исследования. Кроме того, данный подход не применим к другим способам коди- рования, поскольку не обладает должной уни- версальностью. Для решения указанной проблемы и закреп- ления взаимосвязи между размером дерева и длиной генома была разработана следующая процедура инициализации. Обход строки так же выполняется посимвольно, начиная с ее на- чала (независимо от способа кодирования). При этом не составляет трудности определить ме- стонахождение кодируемого символом узла в дереве, а именно его глубину: первый символ – это корневой узел, далее – в соответствии со способом кодирования. Вырожденное дерево, состоящее из одного терминала, как правило, не представляет инте- реса, так как решаемая таким образом задача не требует применения ПЭГ. В таком случае вероятность задания функционального типа корневому узлу устанавливается равным 100 процентам. В то же время для ограничения размера дерева заданным значением (несмотря на способность префиксного кодирования и ПЭГ с наложениями создания деревьев, пре- вышающих в размере длину генома) в целях удобства пользования уместно ограничить уз- лы максимальной возможной глубины листо- выми. Следовательно, вероятность появления функционала в указанных местах равна нулю. Требует решения задача распределения веро- ятности функциональных узлов в зависимости от глубины вложенности. 90 УСиМ, 2015, № 3 Предлагается использование следующей формулы:   21, 1 1funk levelP level maxlevel maxlevel       , где level – глубина узла, maxlevel – максималь- но возможная глубина дерева (рис 6). Рис. 6 Таким образом, процедура инициализации задает узлу глубины level тип функции при выполнении условия random(0... 1) < Pfunc(level, maxlevel), обеспечивая сбалансированную на- чальную популяцию особей прогнозируемого размера. Данный метод конструирования но- вой особи случайным образом показал свою эффективность и был использован во всех экс- периментах. Методы оценки производительности. Для проведения экспериментов была реализована система ПЭГ на языке программирования С, принимающая в качестве аргумента файл с на- бором точек (заданных координатами) и вы- дающая лучшую обнаруженную формулу, на- бор точек – модель, полученную с использова- нием этой формулы, – и динамику СКО луч- шей особи с течением времени. В исходный алгоритм затем поочередно добавлялись опи- санные далее модификации, с возможностью включения и исключения каждой из них в лю- бых комбинациях. Так, например, при каждом запуске можно выбрать оператор селекции (ру- летку, отбор по плотности либо турнир), веро- ятность мутации, способ кодирования и др. Рандомизированная природа алгоритма ПЭГ приводит к необходимости использовать ста- тистические методы для оценки его эффектив- ности. Для этого каждая исследуемая комби- нация модификаций алгоритма запускалась множество раз (обычно 100), анализу подвер- гались значения CKO лучших моделей, полу- ченных в ходе каждого запуска. Наиболее ин- тересные показатели – СКО наилучшей моде- ли среди всех запусков еb и доля успешных за- пусков, т.е. таких запусков, в ходе которых была получена модель с приемлемой для дан- ной задачи точностью rf . Обнаружено, что в большинстве случаев подбор комбинаций параметров и модифика- ций позволяет добиться улучшения какой-либо одной из характеристик еb и rf, но не обеих од- новременно. Направленность на снижение еb наиболее оправдана в тех случаях, когда про- цесс поиска модели не стеснен во времени, а целью является получение наиболее точной модели. Повышение доли успешных запусков rf есть целью при поиске оптимального алго- ритма решения задач, требующих быстрого построения моделей с приемлемой заданной точностью. Таким образом, еb отражает способность ал- горитма к обнаружению лучшей из возможных моделей, а rf – вероятность получения модели достаточной точности при очередном запуске алгоритма. Сравнение систем, собранных с различными параметрами, проводилось на трех задачах по- иска формул, описывающих такие модели:  у(х) = sin х,  5, 4.6x  ;  Функция Розенброка: z(x, у) = (1 – х)2 + + 100(у – х2)2,    3,3 , 3,3x y    ;  Сумма четырех сигмоид: 2 2 2 2 1 (9 2) (9 2)( , ) exp 2 4 3 (9 1) (9 1)exp 4 49 10 x yf x y x y                     2 2 2 2 1 (9x 7) (9 3)exp 2 4 1 exp (9 4) (9 7) , 5 y x y                  УСиМ, 2015, № 3 91    2,2 , 2, 2 .x y    При моделировании функций синуса и Ро- зенброка использовано функциональное мно- жество, состоящее из четырех арифметических действий, в последнем случае – полное множе- ство, в состав которого входят арифметические (сложение, вычитание, умножение, деление), тригонометрические (sin, cos, tan, sinh, cosh, tanh), степенные (возведение в степень, извле- чение квадратного корня, экспонента, лога- рифм). Полученные с применением этих фор- мул модели изображены на рис. 7. Значения приемлемых СКО моделей, при которых зада- ча будет считаться решенной, составляют для этих задач, соответственно, 0,08; 0,05 и 0,06. y = sin(x) z = Rosenbrock(х, у) z = sigmoids(х, у) Рис. 7 Результаты экспериментов. Сравнение эффективности реализованной системы ПЭГ с рассмотренными модификациями способа ко- дирования с исходным алгоритмом приведено в табл. 2, для возможности сопоставления про- изводительности алгоритмов было зафиксиро- вано время, выделяемое каждому запуску. Т а б л и ц а 2. Эффективность алгоритма при разной глубине синтаксического дерева Sin Rosen Sigmas Эксперимент. Глубина еb rf еb rf еb rf 3 (фер.) 0,369 0 0,081 0 0,132 0 4 (фер.) 0,075 2 0,034 6 0,064 0 5 (фер.) 0,022 39 0,001 12 0,053 2 6 (фер.) 0,013 22 0,042 2 0,051 1 7 (фер.) 0,034 4 0,079 0 0,108 0 3 (префикс.) 0,369 0 0,087 0 0,132 0 4 (префикс.) 0,076 2 0,000 6 0,072 0 5 (префикс.) 0,011 45 0,033 10 0,047 2 6 (префикс.) 0,011 22 0,035 2 0,070 0 7 (префикс.) 0,042 10 0,081 0 0,086 0 3 (налож.) 0,369 0 0,081 0 0,132 0 4 (налож.) 0,075 2 0,029 И 0,050 6 5 (налож.) 0,030 39 0,017 8 0,038 2 6 (налож.) 0,045 13 0,004 3 0,049 1 7 (налож.) 0,063 2 0,035 1 0,054 1 При небольшой длине генома ПЭГ с нало- жениями существенно превосходит конкури- рующие модификации в способности обнару- живать отличные решения. Дальнейшее увели- чение максимально возможного размера дере- ва до глубины в четыре узла несколько меняет картину: префиксное ПЭГ значительно выиг- рывает в вероятности успешного обнаружения решения, тогда как выходом ПЭГ с наложе- ниями будет лучшая модель. При допущении деревьев глубиной в пять узлов наилучшие по- казатели имеет префиксное ПЭГ, показатели всех алгоритмов достигают своего максимума. Таким образом, обе модификации превос- ходят исходный алгоритм в производительно- сти, однако каждая из них занимает свою нишу, потому выбор одной из них определяется в за- висимости от нужд исследователя. Из таблицы также следует, что удлинение генома ведет к возрастанию пространства по- иска, появлению деревьев большего размера, следовательно, ведет к более длительному рас- чету популяции. Целесообразно сравнивать мо- дели, на построение которых было затрачено равное время. Из таблицы видно, что для каж- дой задачи имеется некая оптимальная длина 92 УСиМ, 2015, № 3 генома. Меньший размер генов не позволяет выразить деревья достаточной сложности, а при большем – требуется на порядки больше вычислительного времени. Заключение. Итак, проанализирован алго- ритм ПЭГ, рассмотрены различные схемы ко- дирования синтаксических деревьев для их по- следующей линеаризации и хранения, описана детальная процедура создания начальной по- пуляции, которой не было уделено внимания в изученных работах. Разработана универсаль- ная методика, позволяющая определить произ- водительность модификаций алгоритма по лю- бым метрикам, две из которых отобраны как представляющие наибольший интерес. Срав- нение схем кодирования позволило определить область их эффективного применения. 1. High Performance Evolutionary Computation / E. Nunez, E. Banks, P. Agarwal et al. – HPCMP Users Group Conf., Nashville, TN, 2006. – P. 354–359. 2. Holland J.H. Adaptation in Natural and Artificial Sys- tems // The MIT Press, 1992. – 228 p. 3. Koza J.R. Genetic Programming: On the Programming of Computers by Means of Natural Selection, Cam- bridge, MA, USA: Ibid, 1992. – 840 p. 4. Ferreira C. Gene Expression Programming: a New Adaptive Algorithm for Solving Problems // Complex Systems. – 2001. – 13, N 2. – P. 87–129. 5. Ferreira C. Gene Expression Programming in Problem Solving // Soft Comp. and Industry Recent Appl. – Germany: Springer-Verlag, 2001. – P. 635–654. 6. Karakasis V.K., Stafylopatis A. Efficient evolution of accurate classification rules using a combination of gene expression programming and clonal selection // IEEE Transactions on Evolutionary Computation. – 2008. – 12, N 6. – P. 662–678. 7. Ferreira C. Combinatorial Optimization by Gene Ex- pression Programming: Inversion Revisited // Proc. of the Argentine Symp.on Artificial Intel. – Santa Fe, Ar- gentina, 2002. – P. 160–174. 8. Ferreira C. Automatically Defined Functions in Gene Expression Programming // Genetic Systems Program- ming: Theory and Experiences. – Germany: Springer, 2006. – 13. – P. 21–56. 9. MERGE: A Novel Evolutionary Algorithm Based on Multi Expression Gene Programming / S. Dai, C. Tang, M. Zhu et al. // Proc. of the 4th Int. Conf. on Natural Computation (ICNC’08), Washington, DC, USA // IEEE Comp. Society, 2008. – 01. – P. 320–324. 10. GEP-NFM: Nested Function Mining Based on Gene Expression Programming / T. Li, C. Tang, J. Wu et al. // Ibid. – 06. – P. 283–287. 11. Prefix Gene Expression Programming / X. Li, C. Zhou, W. Xiao et al. // Proc. of Genetic and Evolutionary Computation Conf. (GECCO’2005). – Washington, D.C, USA. – 2005. – P. 25–31. 12. Direct Evolution of Hierarchical Solutions with Self- Emergent Substructures / X. Li, C. Zhou, W. Xiao et al. // Proc. of the 4-th Int. Conf. on Machine Learning and Applications (ICMLA’05). – Los Angeles, Calif. // IEEE press, 2005. – P. 337–342. 13. Evolutionary Algorithm Based on Overlapped Gene Expression / J. Peng, C. Tang, J. Zhang et al. // Lect. Notes in Comp. Science. – Springer, 2005. – 3612. – P. 194-204. 14. Ferreira C. Genetic Representation and Genetic neu- trality in gene Expression Programming // Advances in Complex Syst., 2002. – 5, N 4. – P. 389–408. Поступила 02.03.2015 Тел. для справок: +38 057 70-50-862, 70-21-354 (Харьков) E-mail: o.bezsonov@gmail.com, S.Miroshnichenko@gmail.com © О.Г. Руденко, С.В. Мирошниченко, А.А. Бессонов, 2015  Внимание! Требования к оформлению статей размещены на сайте журнала: http://usim.irtc.org.ua Для соответствия журнала современным научно-метрическим базам, авторы должны подать на анг- лийском языке: – расширенную аннотацию на 1–1,5 с. с выделением рубрик: Introduction, Purpose, Methods, Results, Conclusion); – фамилию и инициалы автора, – название статьи; – ключевые слова (Keywords); – место работы, должность и адрес; – ученая степень, звание; – пристатейный список литературы на латинице (для русскоязычных ссылок – транслитерация Ф.И.О. авторов и названия журнала, название статьи – перевод на англ.). << /ASCII85EncodePages false /AllowTransparency false /AutoPositionEPSFiles true /AutoRotatePages /None /Binding /Left /CalGrayProfile (Dot Gain 20%) /CalRGBProfile (sRGB IEC61966-2.1) /CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2) /sRGBProfile (sRGB IEC61966-2.1) /CannotEmbedFontPolicy /Error /CompatibilityLevel 1.4 /CompressObjects /Tags /CompressPages true /ConvertImagesToIndexed true /PassThroughJPEGImages true /CreateJobTicket false /DefaultRenderingIntent /Default /DetectBlends true /DetectCurves 0.0000 /ColorConversionStrategy /CMYK /DoThumbnails false /EmbedAllFonts true /EmbedOpenType false /ParseICCProfilesInComments true /EmbedJobOptions true /DSCReportingLevel 0 /EmitDSCWarnings false /EndPage -1 /ImageMemory 1048576 /LockDistillerParams false /MaxSubsetPct 100 /Optimize true /OPM 1 /ParseDSCComments true /ParseDSCCommentsForDocInfo true /PreserveCopyPage true /PreserveDICMYKValues true /PreserveEPSInfo true /PreserveFlatness true /PreserveHalftoneInfo false /PreserveOPIComments true /PreserveOverprintSettings true /StartPage 1 /SubsetFonts true /TransferFunctionInfo /Apply /UCRandBGInfo /Preserve /UsePrologue false /ColorSettingsFile () /AlwaysEmbed [ true ] /NeverEmbed [ true ] /AntiAliasColorImages false /CropColorImages true /ColorImageMinResolution 300 /ColorImageMinResolutionPolicy /OK /DownsampleColorImages true /ColorImageDownsampleType /Bicubic /ColorImageResolution 300 /ColorImageDepth -1 /ColorImageMinDownsampleDepth 1 /ColorImageDownsampleThreshold 1.50000 /EncodeColorImages true /ColorImageFilter /DCTEncode /AutoFilterColorImages true /ColorImageAutoFilterStrategy /JPEG /ColorACSImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /ColorImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000ColorACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000ColorImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasGrayImages false /CropGrayImages true /GrayImageMinResolution 300 /GrayImageMinResolutionPolicy /OK /DownsampleGrayImages true /GrayImageDownsampleType /Bicubic /GrayImageResolution 300 /GrayImageDepth -1 /GrayImageMinDownsampleDepth 2 /GrayImageDownsampleThreshold 1.50000 /EncodeGrayImages true /GrayImageFilter /DCTEncode /AutoFilterGrayImages true /GrayImageAutoFilterStrategy /JPEG /GrayACSImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /GrayImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000GrayACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000GrayImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasMonoImages false /CropMonoImages true /MonoImageMinResolution 1200 /MonoImageMinResolutionPolicy /OK /DownsampleMonoImages true /MonoImageDownsampleType /Bicubic /MonoImageResolution 1200 /MonoImageDepth -1 /MonoImageDownsampleThreshold 1.50000 /EncodeMonoImages true /MonoImageFilter /CCITTFaxEncode /MonoImageDict << /K -1 >> /AllowPSXObjects false /CheckCompliance [ /None ] /PDFX1aCheck false /PDFX3Check false /PDFXCompliantPDFOnly false /PDFXNoTrimBoxError true /PDFXTrimBoxToMediaBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXSetBleedBoxToMediaBox true /PDFXBleedBoxToTrimBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXOutputIntentProfile () /PDFXOutputConditionIdentifier () /PDFXOutputCondition () /PDFXRegistryName () /PDFXTrapped /False /CreateJDFFile false /Description << /ARA <FEFF06270633062A062E062F0645002006470630064700200627064406250639062F0627062F0627062A002006440625064606340627062100200648062B062706260642002000410064006F00620065002000500044004600200645062A064806270641064206290020064406440637062806270639062900200641064A00200627064406450637062706280639002006300627062A0020062F0631062C0627062A002006270644062C0648062F0629002006270644063906270644064A0629061B0020064A06450643064600200641062A062D00200648062B0627062606420020005000440046002006270644064506460634062306290020062806270633062A062E062F062706450020004100630072006F0062006100740020064800410064006F006200650020005200650061006400650072002006250635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E0635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E> /BGR <FEFF04180437043f043e043b043704320430043904420435002004420435043704380020043d0430044104420440043e0439043a0438002c00200437043000200434043000200441044a0437043404300432043004420435002000410064006f00620065002000500044004600200434043e043a0443043c0435043d04420438002c0020043c0430043a04410438043c0430043b043d043e0020043f044004380433043e04340435043d04380020043704300020043204380441043e043a043e043a0430044704350441044204320435043d0020043f04350447043004420020043704300020043f044004350434043f0435044704300442043d04300020043f043e04340433043e0442043e0432043a0430002e002000200421044a04370434043004340435043d043804420435002000500044004600200434043e043a0443043c0435043d044204380020043c043e0433043004420020043404300020044104350020043e0442043204300440044f0442002004410020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200441043b0435043404320430044904380020043204350440044104380438002e> /CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000410064006f006200650020005000440046002065876863900275284e8e9ad88d2891cf76845370524d53705237300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002> /CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef69069752865bc9ad854c18cea76845370524d5370523786557406300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002> /CZE <FEFF005400610074006f0020006e006100730074006100760065006e00ed00200070006f0075017e0069006a007400650020006b0020007600790074007600e101590065006e00ed00200064006f006b0075006d0065006e0074016f002000410064006f006200650020005000440046002c0020006b00740065007200e90020007300650020006e0065006a006c00e90070006500200068006f006400ed002000700072006f0020006b00760061006c00690074006e00ed0020007400690073006b00200061002000700072006500700072006500730073002e002000200056007900740076006f01590065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f007400650076015900ed007400200076002000700072006f006700720061006d0065006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076011b006a016100ed00630068002e> /DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002c0020006400650072002000620065006400730074002000650067006e006500720020007300690067002000740069006c002000700072006500700072006500730073002d007500640073006b007200690076006e0069006e00670020006100660020006800f8006a0020006b00760061006c0069007400650074002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e> /DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0065006e00200076006f006e002000410064006f006200650020005000440046002d0044006f006b0075006d0065006e00740065006e002c00200076006f006e002000640065006e0065006e002000530069006500200068006f006300680077006500720074006900670065002000500072006500700072006500730073002d0044007200750063006b0065002000650072007a0065007500670065006e0020006d00f60063006800740065006e002e002000450072007300740065006c006c007400650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f00620061007400200075006e0064002000410064006f00620065002000520065006100640065007200200035002e00300020006f0064006500720020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e> /ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f00730020005000440046002000640065002000410064006f0062006500200061006400650063007500610064006f00730020007000610072006100200069006d0070007200650073006900f3006e0020007000720065002d0065006400690074006f007200690061006c00200064006500200061006c00740061002000630061006c0069006400610064002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e> /ETI <FEFF004b00610073007500740061006700650020006e0065006900640020007300e4007400740065006900640020006b00760061006c006900740065006500740073006500200074007200fc006b006900650065006c007300650020007000720069006e00740069006d0069007300650020006a0061006f006b007300200073006f00620069006c0069006b0065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740069006400650020006c006f006f006d006900730065006b0073002e00200020004c006f006f0064007500640020005000440046002d0064006f006b0075006d0065006e00740065002000730061006100740065002000610076006100640061002000700072006f006700720061006d006d006900640065006700610020004100630072006f0062006100740020006e0069006e0067002000410064006f00620065002000520065006100640065007200200035002e00300020006a00610020007500750065006d006100740065002000760065007200730069006f006f006e00690064006500670061002e000d000a> /FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f0075007200200075006e00650020007100750061006c0069007400e90020006400270069006d007000720065007300730069006f006e00200070007200e9007000720065007300730065002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e> /GRE <FEFF03a703c103b703c303b903bc03bf03c003bf03b903ae03c303c403b5002003b103c503c403ad03c2002003c403b903c2002003c103c503b803bc03af03c303b503b903c2002003b303b903b1002003bd03b1002003b403b703bc03b903bf03c503c103b303ae03c303b503c403b5002003ad03b303b303c103b103c603b1002000410064006f006200650020005000440046002003c003bf03c5002003b503af03bd03b103b9002003ba03b103c42019002003b503be03bf03c703ae03bd002003ba03b103c403ac03bb03bb03b703bb03b1002003b303b903b1002003c003c103bf002d03b503ba03c403c503c003c903c403b903ba03ad03c2002003b503c103b303b103c303af03b503c2002003c503c803b703bb03ae03c2002003c003bf03b903cc03c403b703c403b103c2002e0020002003a403b10020005000440046002003ad03b303b303c103b103c603b1002003c003bf03c5002003ad03c703b503c403b5002003b403b703bc03b903bf03c503c103b303ae03c303b503b9002003bc03c003bf03c103bf03cd03bd002003bd03b1002003b103bd03bf03b903c703c403bf03cd03bd002003bc03b5002003c403bf0020004100630072006f006200610074002c002003c403bf002000410064006f00620065002000520065006100640065007200200035002e0030002003ba03b103b9002003bc03b503c403b103b303b503bd03ad03c303c403b503c103b503c2002003b503ba03b403cc03c303b503b903c2002e> /HEB <FEFF05D405E905EA05DE05E905D5002005D105D405D205D305E805D505EA002005D005DC05D4002005DB05D305D9002005DC05D905E605D505E8002005DE05E105DE05DB05D9002000410064006F006200650020005000440046002005D405DE05D505EA05D005DE05D905DD002005DC05D405D305E405E105EA002005E705D305DD002D05D305E405D505E1002005D005D905DB05D505EA05D905EA002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E05D005DE05D905DD002005DC002D005000440046002F0058002D0033002C002005E205D905D905E005D5002005D105DE05D305E805D905DA002005DC05DE05E905EA05DE05E9002005E905DC0020004100630072006F006200610074002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E> /HRV (Za stvaranje Adobe PDF dokumenata najpogodnijih za visokokvalitetni ispis prije tiskanja koristite ove postavke. Stvoreni PDF dokumenti mogu se otvoriti Acrobat i Adobe Reader 5.0 i kasnijim verzijama.) /HUN <FEFF004b0069007600e1006c00f30020006d0069006e0151007300e9006701710020006e0079006f006d00640061006900200065006c0151006b00e90073007a00ed007401510020006e0079006f006d00740061007400e100730068006f007a0020006c006500670069006e006b00e1006200620020006d0065006700660065006c0065006c0151002000410064006f00620065002000500044004600200064006f006b0075006d0065006e00740075006d006f006b0061007400200065007a0065006b006b0065006c0020006100200062006500e1006c006c00ed007400e10073006f006b006b0061006c0020006b00e90073007a00ed0074006800650074002e0020002000410020006c00e90074007200650068006f007a006f00740074002000500044004600200064006f006b0075006d0065006e00740075006d006f006b00200061007a0020004100630072006f006200610074002000e9007300200061007a002000410064006f00620065002000520065006100640065007200200035002e0030002c0020007600610067007900200061007a002000610074007400f3006c0020006b00e9007301510062006200690020007600650072007a006900f3006b006b0061006c0020006e00790069007400680061007400f3006b0020006d00650067002e> /ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f00620065002000500044004600200070006900f900200061006400610074007400690020006100200075006e00610020007000720065007300740061006d0070006100200064006900200061006c007400610020007100750061006c0069007400e0002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e> /JPN <FEFF9ad854c18cea306a30d730ea30d730ec30b951fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e305930023053306e8a2d5b9a306b306f30d530a930f330c8306e57cb30818fbc307f304c5fc59808306730593002> /KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020ace0d488c9c80020c2dcd5d80020c778c1c4c5d00020ac00c7a50020c801d569d55c002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e> /LTH <FEFF004e006100750064006f006b0069007400650020016100690075006f007300200070006100720061006d006500740072007500730020006e006f0072011700640061006d00690020006b0075007200740069002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b00750072006900650020006c0061006200690061007500730069006100690020007000720069007400610069006b007900740069002000610075006b01610074006f00730020006b006f006b007900620117007300200070006100720065006e006700740069006e00690061006d00200073007000610075007300640069006e0069006d00750069002e0020002000530075006b0075007200740069002000500044004600200064006f006b0075006d0065006e007400610069002000670061006c006900200062016b007400690020006100740069006400610072006f006d00690020004100630072006f006200610074002000690072002000410064006f00620065002000520065006100640065007200200035002e0030002000610072002000760117006c00650073006e0117006d00690073002000760065007200730069006a006f006d00690073002e> /LVI <FEFF0049007a006d0061006e0074006f006a00690065007400200161006f00730020006900650073007400610074012b006a0075006d00750073002c0020006c0061006900200076006500690064006f00740075002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006100730020006900720020012b00700061016100690020007000690065006d01130072006f00740069002000610075006700730074006100730020006b00760061006c0069007401010074006500730020007000690072006d007300690065007300700069006501610061006e006100730020006400720075006b00610069002e00200049007a0076006500690064006f006a006900650074002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006f002000760061007200200061007400760113007200740020006100720020004100630072006f00620061007400200075006e002000410064006f00620065002000520065006100640065007200200035002e0030002c0020006b0101002000610072012b00200074006f0020006a00610075006e0101006b0101006d002000760065007200730069006a0101006d002e> /NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken die zijn geoptimaliseerd voor prepress-afdrukken van hoge kwaliteit. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.) /NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200073006f006d00200065007200200062006500730074002000650067006e0065007400200066006f00720020006600f80072007400720079006b006b0073007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c0069007400650074002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e> /POL <FEFF0055007300740061007700690065006e0069006100200064006f002000740077006f0072007a0065006e0069006100200064006f006b0075006d0065006e007400f300770020005000440046002000700072007a0065007a006e00610063007a006f006e00790063006800200064006f002000770079006400720075006b00f30077002000770020007700790073006f006b00690065006a0020006a0061006b006f015b00630069002e002000200044006f006b0075006d0065006e0074007900200050004400460020006d006f017c006e00610020006f007400770069006500720061010700200077002000700072006f006700720061006d006900650020004100630072006f00620061007400200069002000410064006f00620065002000520065006100640065007200200035002e0030002000690020006e006f00770073007a0079006d002e> /PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020006d00610069007300200061006400650071007500610064006f00730020007000610072006100200070007200e9002d0069006d0070007200650073007300f50065007300200064006500200061006c007400610020007100750061006c00690064006100640065002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e> /RUM <FEFF005500740069006c0069007a00610163006900200061006300650073007400650020007300650074010300720069002000700065006e007400720075002000610020006300720065006100200064006f00630075006d0065006e00740065002000410064006f006200650020005000440046002000610064006500630076006100740065002000700065006e0074007200750020007400690070010300720069007200650061002000700072006500700072006500730073002000640065002000630061006c006900740061007400650020007300750070006500720069006f006100720103002e002000200044006f00630075006d0065006e00740065006c00650020005000440046002000630072006500610074006500200070006f00740020006600690020006400650073006300680069007300650020006300750020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e00300020015f00690020007600650072007300690075006e0069006c006500200075006c0074006500720069006f006100720065002e> /RUS <FEFF04180441043f043e043b044c04370443043904420435002004340430043d043d044b04350020043d0430044104420440043e0439043a043800200434043b044f00200441043e043704340430043d0438044f00200434043e043a0443043c0435043d0442043e0432002000410064006f006200650020005000440046002c0020043c0430043a04410438043c0430043b044c043d043e0020043f043e04340445043e0434044f04490438044500200434043b044f00200432044b0441043e043a043e043a0430044704350441044204320435043d043d043e0433043e00200434043e043f0435044704300442043d043e0433043e00200432044b0432043e04340430002e002000200421043e043704340430043d043d044b04350020005000440046002d0434043e043a0443043c0435043d0442044b0020043c043e0436043d043e0020043e0442043a0440044b043204300442044c002004410020043f043e043c043e0449044c044e0020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200431043e043b043504350020043f043e04370434043d043804450020043204350440044104380439002e> /SKY <FEFF0054006900650074006f0020006e006100730074006100760065006e0069006100200070006f0075017e0069007400650020006e00610020007600790074007600e100720061006e0069006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b0074006f007200e90020007300610020006e0061006a006c0065007001610069006500200068006f0064006900610020006e00610020006b00760061006c00690074006e00fa00200074006c0061010d00200061002000700072006500700072006500730073002e00200056007900740076006f00720065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f00740076006f00720069016500200076002000700072006f006700720061006d006f006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076016100ed00630068002e> /SLV <FEFF005400650020006e006100730074006100760069007400760065002000750070006f0072006100620069007400650020007a00610020007500730074007600610072006a0061006e006a006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b006900200073006f0020006e0061006a007000720069006d00650072006e0065006a016100690020007a00610020006b0061006b006f0076006f00730074006e006f0020007400690073006b0061006e006a00650020007300200070007200690070007200610076006f0020006e00610020007400690073006b002e00200020005500730074007600610072006a0065006e006500200064006f006b0075006d0065006e0074006500200050004400460020006a00650020006d006f0067006f010d00650020006f0064007000720065007400690020007a0020004100630072006f00620061007400200069006e002000410064006f00620065002000520065006100640065007200200035002e003000200069006e0020006e006f00760065006a01610069006d002e> /SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f00740020006c00e400680069006e006e00e4002000760061006100740069007600610061006e0020007000610069006e006100740075006b00730065006e002000760061006c006d0069007300740065006c00750074007900f6006800f6006e00200073006f00700069007600690061002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a0061002e0020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e> /SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400200073006f006d002000e400720020006c00e4006d0070006c0069006700610020006600f60072002000700072006500700072006500730073002d007500740073006b00720069006600740020006d006500640020006800f600670020006b00760061006c0069007400650074002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e> /TUR <FEFF005900fc006b00730065006b0020006b0061006c006900740065006c0069002000f6006e002000790061007a006401310072006d00610020006200610073006b013100730131006e006100200065006e0020006900790069002000750079006100620069006c006500630065006b002000410064006f006200650020005000440046002000620065006c00670065006c0065007200690020006f006c0075015f007400750072006d0061006b0020006900e70069006e00200062007500200061007900610072006c0061007201310020006b0075006c006c0061006e0131006e002e00200020004f006c0075015f0074007500720075006c0061006e0020005000440046002000620065006c00670065006c0065007200690020004100630072006f006200610074002000760065002000410064006f00620065002000520065006100640065007200200035002e003000200076006500200073006f006e0072006100730131006e00640061006b00690020007300fc007200fc006d006c00650072006c00650020006100e70131006c006100620069006c00690072002e> /UKR <FEFF04120438043a043e0440043804410442043e043204430439044204350020044604560020043f043004400430043c043504420440043800200434043b044f0020044104420432043e04400435043d043d044f00200434043e043a0443043c0435043d044204560432002000410064006f006200650020005000440046002c0020044f043a04560020043d04300439043a04400430044904350020043f045604340445043e0434044f0442044c00200434043b044f0020043204380441043e043a043e044f043a04560441043d043e0433043e0020043f0435044004350434043404400443043a043e0432043e0433043e0020043404400443043a0443002e00200020042104420432043e04400435043d045600200434043e043a0443043c0435043d0442043800200050004400460020043c043e0436043d04300020043204560434043a0440043804420438002004430020004100630072006f006200610074002004420430002000410064006f00620065002000520065006100640065007200200035002e0030002004300431043e0020043f04560437043d04560448043e04570020043204350440044104560457002e> /ENU (Use these settings to create Adobe PDF documents best suited for high-quality prepress printing. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.) >> /Namespace [ (Adobe) (Common) (1.0) ] /OtherNamespaces [ << /AsReaderSpreads false /CropImagesToFrames true /ErrorControl /WarnAndContinue /FlattenerIgnoreSpreadOverrides false /IncludeGuidesGrids false /IncludeNonPrinting false /IncludeSlug false /Namespace [ (Adobe) (InDesign) (4.0) ] /OmitPlacedBitmaps false /OmitPlacedEPS false /OmitPlacedPDF false /SimulateOverprint /Legacy >> << /AddBleedMarks false /AddColorBars false /AddCropMarks false /AddPageInfo false /AddRegMarks false /ConvertColors /ConvertToCMYK /DestinationProfileName () /DestinationProfileSelector /DocumentCMYK /Downsample16BitImages true /FlattenerPreset << /PresetSelector /MediumResolution >> /FormElements false /GenerateStructure false /IncludeBookmarks false /IncludeHyperlinks false /IncludeInteractive false /IncludeLayers false /IncludeProfiles false /MultimediaHandling /UseObjectSettings /Namespace [ (Adobe) (CreativeSuite) (2.0) ] /PDFXOutputIntentProfileSelector /DocumentCMYK /PreserveEditing true /UntaggedCMYKHandling /LeaveUntagged /UntaggedRGBHandling /UseDocumentProfile /UseDocumentBleed false >> ] >> setdistillerparams << /HWResolution [2400 2400] /PageSize [612.000 792.000] >> setpagedevice

Схожі ресурси