Разработка и исследование вероятностных эволюционных алгоритмов для моделирования и оптимизации сложных систем

РАЗРАБОТКА И ИССЛЕДОВАНИЕ ВЕРОЯТНОСТНЫХ ЭВОЛЮЦИОННЫХ АЛГОРИТМОВ ДЛЯ МОДЕЛИРОВАНИЯ И ОПТИМИЗАЦИИ СЛОЖНЫХ СИСТЕМ

Содержание:

Введение

Глава I. Разработка и исследование вероятностного генетического алгоритма для оптимизации сложных систем

.1 Основные свойства задач оптимизации сложных систем и возможные подходы к их решению

.1.1 Метод бинаризации

.1.2 Коды Грея

.1.3 Тестовые задачи

.2 Стандартный генетический алгоритм и исследование его работоспособности на тестовых задачах

.2.1 Представление решений в ГА

.2.2 Общая схема ГА

.2.3 Инициализация

.2.4 Селекция

.2.5 Скрещивание

.2.6 Мутация

.2.7 Пригодность индивидов (fitness-функция)

.2.8 Исследование работоспособности на тестовых задачах

.3 Метод изменяющихся вероятностей (МИВЕР) и исследование его работоспособности на тестовых задачах

.3.1 Общая схема МИВЕР

.3.2 Исследование работоспособности на тестовых задачах

.4 Основные идеи вероятностного генетического алгоритма и исследование его работоспособности на тестовых функциях

.4.1 Общая схема вероятностного генетического алгоритма

.4.2 Исследование работоспособности на тестовых задачах

.5 Алгоритм прогноза сходимости вероятностного генетического алгоритма

.6 Выводы

Глава II. Разработка и исследование метода вероятностного генетического программирования для моделирования сложных систем

.1 Методы решения задач аппроксимации в моделировании сложных систем

.2 Обычный метод генетического программирования для решения задачи символьной регрессии и его исследование

.2.1 Представление решений в методе генетического программирования

.2.2 Общая схема метода генетического программирования, применение основных генетических операторов

.2.3 Решение задачи символьной регрессии с помощью метода генетического программирования

.2.4 Исследование работоспособности на тестовых задачах

.3 Основные идеи вероятностного генетического программирования и его исследование

.3.1 Общая схема метода вероятностного генетического программирования

.3.2 Исследование работоспособности на тестовых задачах

.4 Выводы

Глава III. Практическая реализация разработанных алгоритмов

.1 Программная реализация обыкновенного и вероятностного генетического алгоритмов

.1.1 Программная система «GA lab»

.1.2 Программная система «ProbGA lab»

.2 Программная реализация методов обыкновенного и вероятностного генетического программирования

3.2.1 Программная система «GP: Symbolic Regression»

.2.2 Программная система «ProbGP: Symbolic Regression»

3.3 Постановка задачи оптимизации работы электростанции на топливных элементах в стационарном режиме

.3.1 Водородные топливные элементы - основные принципы

.3.2 Теплоэлектростанции на топливных элементах

.3.3 Математическая модель электростанции на топливных элементах

.3.4 Постановка задачи оптимизации

.4 Решение задачи оптимизации работы электростанции на топливных элементах в стационарном режиме с помощью вероятностного генетического алгоритма

.4.1 Исследование устойчивости решения

.5 Выводы

Заключение

Список использованных источников

Приложение 1. Общая схема конструирования многоэкстремальных функций непрерывных переменных

Приложение 2. Набор тестовых задач

Введение

Идея оптимальности является центральной идеей кибернетики. Понятие оптимальности получило строгое и точное представление в математических теориях, прочно вошло в практику проектирования и эксплуатирования технических систем, сыграло важную роль в формировании современных системных представлений. Оптимизация - один из способов выражения рационального поведения. Математически задача оптимизации формулируется как задача поиска экстремума некоторого функционала, выражающего зависимость выходных параметров исследуемого объекта (системы, процесса) от входных [11, 34].

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

За прошедшие годы было предложено много различных схем применения эволюционных алгоритмов для решения сложных задач оптимизации [35, 36, 58, 61, 62]. Генетические алгоритмы с бинарным представлением решений занимают особое место среди стохастических методов адаптивного поиска. Особая сложность разработки и исследования алгоритмов связана с тем, что большинство методов прямого поиска основано на различных эвристических идеях. Перспективным направлением является разработка методов комбинирующих эвристические идеи интеллектуальных информационных технологий и строгий формальный аппарат современной математики.

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

Символьная регрессия дает нам не только вычислительную процедуру, но и формулу (символьное математическое выражение), которую можно было бы подвергнуть содержательному анализу, упростить, а затем и уточнить. Однако на современном этапе методы символьной регрессии не разработаны достаточно хорошо, поэтому направление разработки и следования подобных методов является актуальным. Метод генетического программирования является наиболее перспективным направлением.

Цель работы: разработка и исследование комплексной системы моделирования и оптимизации сложных систем на основе алгоритма вероятностного генетического программирования (моделирование сложных систем путем решения задач символьной регрессии) и вероятностного генетического алгоритма (оптимизация сложных систем с применением построенной модели).

Для достижения поставленной цели необходимо решить следующие задачи:

1.     Провести анализ основных свойств задач оптимизации сложных систем и возможных подходов к их решению.

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

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

.        Провести анализ методов решения задачи символьной регрессии.

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

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

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

Научная новизна результатов диссертации:

1.     Разработан новый метод решения сложных задач оптимизации - вероятностный генетический алгоритм, и показана его работоспособность на тестовых и практических задачах.

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

.        Разработан новый метод решения задачи символьной регрессии - вероятностный алгоритм генетического программирования, и доказана его работоспособность на тестовых задачах.

Практическая значимость. Предложенный вероятностный генетический алгоритм использован при решении актуальной практической задачи - оптимизаций работы электростанции на топливных элементах в установившемся режиме. Полученные с помощью вероятностного генетического алгоритма параметры позволяют повысить эффективность работы станции на 6.5%, что подтверждено официальным сертификатом от Института прикладных исследований при Высшей технической школе г. Ульм (Германия).

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

Предложенные в диссертации алгоритмы и программные системы используются в учебном процессе при проведении занятий по специальным курсам «Системы искусственного интеллекта» и «Адаптивные и эволюционные методы принятия решений» в Сибирском государственном аэрокосмическом университете, а также по общему курсу «Методы оптимизации» и специальным курсам «Системный анализ и управление» и «Эволюционные алгоритмы оптимизации» в Красноярском государственном университете.

Основные защищаемые положения:

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

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

.        Полученные с помощью вероятностного генетического алгоритма значения параметров для задачи оптимизации работы электростанции на топливных элементах в стационарном режиме позволяют повысить КПД электростанции в 2 раза.

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

-        Межвузовская научно-практическая конференция «Молодежь Сибири - науке России», СИБУП, 2002.

-       40-я научно-практическая конференция студентов, аспирантов и молодых ученых посвященная дню космонавтики. САА. Красноярск, 2002.

-       Всероссийская научно-техническая конференция студентов, аспирантов и молодых ученых «Совершенствование методов поиска и разведки, технологий добычи и переработки полезных ископаемых», КрасГАЦиЗ, 2003.

-       Межвузовская научная конференция «Информатика и информационные технологии», КГТУ, 2003.

-       41-й студенческая конференция СибГАУ посвященная дню космонавтики. Красноярск, 2003.

-       XXVI Научная студенческая конференция по математике. КГУ, 2003.

-       Краевая выставка технических идей и разработок «Первый сибирский техносалон». Красноярск, 2003.

-       Х Юбилейная Международная научно-практическая конференция студентов, аспирантов и молодых ученых «Современные техника и технологии», Томск, 2004.

А также на научно-техническом семинаре института прикладных исследований при Высшей технической школе г. Ульм (Германия), научных семинарах экспериментальной лаборатории интеллектуальных технологий и адаптации СибГАУ и научном семинаре кафедры механики и процессов управления Красноярского государственного университета.

Программные системы, реализующие гибридный метод генетического программирования и вероятностный генетический алгоритм прошли экспертизу и зарегистрированы в отраслевом фонде алгоритмов и программ (ОФАП) Государственного координационного центра информационных технологий Министерства образования и науки (коды программ по ЕСПД: .03524577.00637-01 и .03524577.00638-01, номера государственной регистрации 50200400500 и 50200400501, номера свидетельств об отраслевой регистрации разработок 3507 и 3508).

Публикации. По результатам диссертационной работы опубликовано 12 печатных научных работ, список которых приведен в конце диссертации [19-29, 56].

Структура

Диссертационная работа состоит из введения, трех глав, заключения, списка литературы из 62 наименований и 2 приложений. Содержание работы изложено на 106 страницах основного текста, включая 4 таблицы и 54 рисунка.

Глава I. Разработка и исследование вероятностного генетического алгоритма для оптимизации сложных систем

1.1    Основные свойства задач оптимизации сложных систем и возможные подходы к их решению

Оптимизация (от лат. Optimum - наилучшее) - «процесс нахождения экстремума (глобального максимума или минимума) определенной функции или выбора наилучшего (оптимального) варианта из множества возможных» [13].

Оптимизация - «минимизация или максимизация определенным образом заданного критерия, который характеризует качество или эффективность принимаемого решения» [10].

Оптимизация - «итеративный процесс улучшения решения задачи, сформулированный в постановке поиска экстремума целевой функции» [8].

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

) указание на наличие моделирующего некоторую реальность целевого критерия (целевой функции/целевого функционала, критерия оптимизации, экстремальной характеристики, показателя экстремума, критерия качества и др.), экстремальное (максимальное или минимальное) значение которого необходимо либо однократно определить (если его положение не зависит от времени), либо перманентно отслеживать (в противном случае);

) указание на наличие соответствующих средств определения экстремума данного целевого критерия: при наличии достаточной информации о виде оптимизируемой функции вполне формальных, при ее отсутствии - поисковых [6].

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

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

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

При решении задач оптимизации сложных систем часто встречаются следующие ситуации:

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

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

-       С объектом нельзя активно экспериментировать, оптимизация производится по модели объекта.

-       Объект нестационарный - положение экстремума может меняться во времени.

-       Размерность задачи высока.

-       Переменные задачи выражены в различных шкалах измерения.

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

-       Допустимая область ограничена - наличие ограничений типа равенств и неравенств (ограничения также могут обладать выше перечисленными свойствами).

-       Оптимизация производится по многим экстремальным критериям одновременно - многокритериальная оптимизация.

Очевидно, что применение классических методов оптимизации в подобных задачах невозможно или крайне затруднено.

1.1.1 Метод бинаризации

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

,(1)

где  - область изменения метрических переменных,  - область изменения порядковых переменных,  - область изменения переменных наименований,  - область изменения переменных перестановок.

Предложенный Л.А. Растригиным метод бинаризации позволяет сводить задачи типа (1) к задачам псевдобулевой оптимизации (2). Следует отметить, что к задаче (2) сводятся любые задачи дискретного программирования, а также непрерывного, путем дискретизации пространства поиска [12, 15].

,

.(2)

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

Перевод порядковых переменных в булевы

Пусть дана порядковая переменная . Бинарным представлением переменной  будет вектор , где . Находим значение булевого вектора, переведя его в целое число . Тогда полагаем .

Перевод метрических переменных в булевы

Кодирование метрической шкалы начинается с перевода ее в порядковую. Для этого интервал  разбивается на  равных частей ( - точность решения задачи оптимизации). Теперь переменная  измеряется в порядковой шкале, , где . Далее порядковая переменная преобразуется в булеву аналогично.

Перевод переменных наименований и перестановок в булевы

Эффективных алгоритмов перевода порядковых переменных и переменных наименований до сих пор не предложено. Непосредственный перевод их в булевы переменные дает результат аналогичный полному перебору.

Предложено по мере накопления информации о функционале в процессе оптимизации, определять отношения порядка на множестве перестановок и наименований. Далее работать так же как и с порядковыми шкалами.

1.1.2 Коды Грея

Код Грея это бинарный код целого числа, такой, что для смежных целых чисел расстояние между их кодами в метрике Хемминга равно 1.

Стандартное рефлексивное Грей кодирование целого числа получается применением оператора исключающего ИЛИ к стандартному бинарному кодированию целого числа и к тому же бинарному коду, смещенному на одну позицию вправо, последний бит отсекается.

Кодирование и декодирование Грея можно выразить в виде операций с матрицами. Пусть x и y n-битовое бинарное и Грей кодирование целого числа соответственно, и G матрица трансформации, состоящая из 1 на главной диагонали и диагонали верхнего минора и 0 в других позициях. Грей кодирование и декодирование тогда можно представить как  и  соответственно. Можно показать, что любая перестановка столбца в матрице G приводит к другой матрице трансформации [54].

Можно использовать следующий алгоритм перевода бинарного кода в Грей-код и наоборот: начать со старшего (правого) бита для получения Грей кода и с левого для получения бинарного кода, последовательно заменять биты по правилу:

На каждом шаге заменяется два бита и производится смещение на один бит таким образом, что на последующем шаге заменяется один новый бит и один старый.

Для многих практических задач код Грея оказывается более эффективным, чем бинарное кодирование [39]. Код Грея сохраняет структуру окрестностей пространства поиска в бинаризованном пространстве. В результате, Грей код не может образовать оптимумов больше, чем у исходной целевой функции. Более того, т.к. у текущей точки в коде Грея соседних точек больше, чем в дискретной целевой функции, то в пространстве поиска Грей кода число оптимумов обычно меньше. В противоположность, бинарный код часто создает новые оптимумы, которых нет в целевой функции [59].

1.1.3 Тестовые задачи

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

- Задачи в тестовом наборе должны быть непохожи друг на друга, чтобы у создателя алгоритма было меньше возможностей настроить его на специальных примерах.

-       В тестовых задачах должны содержаться такие ситуации, которые обычно вызывают затруднения; процесс проверки алгоритма должен показать, что эти трудности преодолеваются. [4]

-       Тестовые задачи должны вызывать затруднения у локальных методов.

-       Тестовые задачи должны быть нелинейными и несепарабельными.

-       Тестовые задачи должны быть масштабируемыми. [60]

Наиболее часто для проверки эффективности адаптивных алгоритмов глобального поиска используются функции Розенброка, Шекеля, Растригина, Катникова, Griewank, De Jong. Общая схема проектирования многоэкстремальных тестовых функций предложена в [14, 16]. Подробно схема проектирования тестовых функций непрерывных переменных представлена в Приложении 1. Набор тестовых функций, используемых в диссертации, представлен в Приложении 2. Используемые тестовые функции реализуют многие свойства, затрудняющие оптимизацию: многоэкстремальность, несепарабельность, овражность, множества постоянства, значения функции в глобальном оптимуме слабо отличается от значений в локальных и др.

1.2    Стандартный генетический алгоритм и исследование его работоспособности на тестовых задачах

Эволюционные алгоритмы (ЭА), предложенные впервые для решения задач адаптации, в дальнейшем интенсивно развивались как методы решения сложных задач оптимизации. Генетические алгоритмы (ГА) представляют собой семейство ЭА, имеющих общую схему. На сегодняшний день ГА доказали свою конкурентоспособность при решении многих NP-трудных задач поиска и оптимизации и особенно в практических приложениях, где математические модели имеют сложную структуру и применение классических методов невозможно.

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

ЭА базируются на коллективном обучающем процессе внутри популяции индивидуумов, каждый из которых представляет собой поисковую точку в пространстве допустимых решений данной задачи. Популяция случайно инициализируется, и затем охватывает лучшие регионы поискового пространства посредством случайных процессов селекции, мутации и рекомбинации. Окружающая среда представляет качественную информацию (степень пригодности) о поисковых точках (индивидуумах), а процесс селекции отбирает тех индивидуумов, у которых значение пригодности выше. Отобранные потомки являются, в свою очередь, родителями в следующем поколении. Механизм рекомбинации перемешивает генетическую информацию родителей (тем самым рождается один или несколько потомков), и наконец, механизм мутации способствует в некоторой степени обновлению генетической информации потомков. [18]

В 1975 г. вышла основополагающая книга Дж. Холланда “Адаптация в естественных и искусственных системах”, в которой был предложен первый генетический алгоритм. Термин "генетические алгоритмы" ввел в 1975 г. Д. Голдберг [43]. Его книга содержит детальное обсуждение, как теоретических аспектов ГА, так и возможных областей их применения:

-      Искусственная жизнь,

-       Автоматическое обучение,

-       Извлечение данных (знаний),

-       Инженерное проектирование,

-       Планирование и управление,

-       Моделирование, идентификация,

-       Численная и комбинаторная оптимизация.

Итак, ГА базируются на теоретических достижениях синтетической теории эволюции, учитывающей микробиологические механизмы наследования признаков в природных и искусственных популяциях организмов, а также на накопленном человечеством опыте в селекции животных и растений.

Методологическая основа ГА зиждется на гипотезе селекции, которая в самом общем виде может быть сформулирована так: чем выше приспособленность особи, тем выше вероятность того, что в потомстве, полученном с ее участием, признаки, определяющие приспособленность, будут выражены еще сильнее [3].

Т.о. ГА заимствуют из биологии:

- понятийный аппарат;

-       идею коллективного поиска экстремума при помощи популяции особей;

-       способы представления генетической информации;

-       способы передачи генетической информации в череде поколений (генетические операторы);

-       идею о преимущественном размножении наиболее приспособленных особей.

1.2.1 Представление решений в ГА

Подобно тому, как природный хромосомный материал представляет собой линейную последовательность различных комбинаций четырех нуклеотидов, решения в ГА представляются в виде хромосом (генотипов). Генотип - строка конечной длины, состоящая из генов, представленных символами некоторого алфавита.

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

На практике наибольшее распространение получили ГА с бинарным представлением решений. Формально они решают задачу псевдобулевой оптимизации (2), т.е.

, где .

Как отмечалось в п.1.1., к задаче (2) сводятся практически любые задачи с дискретными переменными (возможно выраженные в разных шкалах), а также задачи с непрерывными переменными (заменяя непрерывные переменные дискретными с заданной точностью). Наиболее часто используются стандартное бинарное кодирование и бинарные коды Грея.

1.2.2 Общая схема ГА

В общем виде работу генетического алгоритма можно представить следующим образом:

.        Инициализировать случайным образом популяцию решений.

.        С помощью оператора селекции выбрать часть популяции (родителей) для порождения потомков.

.        Применить оператор скрещивания.

.        Новые решения (потомки) подвергаются мутации.

.        Формируется новая популяция: выбрать решения из родителей и потомков.

.        Повторять 2 - 5 пока не выполнится условие остановки.

1.2.3 Инициализация

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

1.2.4 Селекция

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

Предложено множество различных схем отбора в ГА. Конкретный тип оператора селекции (а также и др. генетических операторов) проектируется исходя из решаемой задачи (например, когда требуется контроль допустимости решений, учет ограничений, многокритериальности и т.д.), однако наиболее распространены следующие базовые типы селекции.

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

,

где  - размер популяции, , .

Пропорциональная селекция обладает следующими недостатками: преждевременная сходимость и стагнация.

Стагнация возникает, когда на определенном этапе поиска все индивиды получают относительно высокую и примерно равную пригодность, что приводит к очень низкому селективному давлению (наилучшее решение лишь немного предпочитается худшему).

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

При применении ранговой селекции индивиды популяции ранжируются в соответствии с их пригодностью:  если . Тогда

, где .

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

В турнирной селекции для отбора индивида создается группа из t (t ³ 2) индивидов, выбранных случайным образом. Индивид с наибольшей пригодностью в группе отбирается, остальные - отбрасываются. Параметр t называется размером турнира. Наиболее популярным является бинарный турнир. Этот тип селекции не требует сортировки популяции и вычисления пригодности для всех индивидов. Недостатки: худший индивид никогда не выбирается.

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

Элитарная селекция. Как минимум одна копия лучшего индивида всегда переходит в следующее поколение. Преимущества: гарантия сходимости. Недостатки: большой риск захвата локальным оптимумом.

1.2.5 Скрещивание

Оператор скрещивания (рекомбинация) - генетический оператор поиска. При скрещивании отобранные индивиды (родители) по заданному правилу передают части своих хромосом. Потомок может унаследовать только те гены, которые есть у его родителей. Существуют различные схемы скрещивания: точечное, равномерное, скрещивание более чем двух родителей и другие. При точечном скрещивании для выбранных родителей выбираются точки разрыва хромосомы, родители определенным образом обмениваются соответствующими участками хромосом. При равномерном - соответствующий ген потомка может быть унаследован от любого родителя с равной вероятностью. Скрещивание осуществляется с вероятностью , иначе с вероятностью  родители клонируются в следующее поколение.

Наиболее популярным типом скрещивания является одноточечное скрещивание - случайно выбирается точка разрыва, родительские хромосомы разрываются в этой точке и обмениваются правыми частями (рис. 1).

Рис. 1. Одноточечное скрещивание.

При двухточечном скрещивании хромосома как бы замыкается в кольцо, выбираются 2 точки разрыва, родитель обмениваются частями (рис. 2).

Рис. 2. Двухточечное скрещивание.

При равномерном скрещивании потомок может унаследовать с равной вероятностью гены любого из родителей (рис. 3).

Рис. 3. Равномерное скрещивание.

Равномерное скрещивание по всей популяции (uniform gene pool recombination) получается применением равномерного скрещивание к всем членам популяции, т.е. потомок может унаследовать любой ген, имеющийся в популяции в заданной позиции хромосомы [53].

1.2.6 Мутация

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

Рис. 4. Пример мутации в ГА.

1.2.7 Пригодность индивидов (fitness - функция)

Пригодность индивида - это некоторая количественная оценка качества решения поставленной задачи. Функция пригодности может быть спроектирована с учетом особенностей решаемой задачи (что делает ГА довольно гибким, универсальным). Обычно функция пригодности принимает положительные значения, и значение пригодности максимизируют.

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

1.2.8 Исследование работоспособности на тестовых задачах

Для исследования работоспособности ГА была разработана программная система «GA lab», реализующая практически все основные параметры алгоритма. Эффективность алгоритма проверялась на тестовых функциях 1, 3, 4, 6-8, 15. Исследования проводились для ГА с одноточечным скрещиванием и ГА с равномерным скрещиванием по всей популяции. Реализованы пропорциональная, ранговая и турнирная (размер турнира - 2) селекции, низкая и высокая мутации. Использовалось стандартное бинарное и кодирование Грея. Размер популяции - 50. Количество прогонов алгоритма - 50.

Для оценки эффективности алгоритмов использованы два показателя: надежность и среднее число итераций. Надежность - процент успешных запусков (решение найдено) к общему числу запусков алгоритма. Среднее число итераций - номер итерации, когда найдено решение, усредненный по успешным прогонам. Алгоритм с наибольшей надежностью всегда считается лучшим. Среди алгоритмов с одинаковой надежностью - лучший тот, у которого наименьшее среднее число итераций.

Результаты тестирования представлены в таблице 1 (серым выделен алгоритм «победивший» на данной тестовой задаче). Из таблицы видно, что наиболее эффективным оказывается использование высокой мутации, которая помогает избежать локальной сходимости даже при использовании пропорциональной селекции (победители на Ф4, Ф6, Ф8). Код Грея в сочетании с представленными алгоритмами оказался не достаточно эффективным на Ф6 и Ф8, т.к. на этих функциях было бы лучше если соседние в бинаризованном пространстве точки оказались далекими в исходном - для Ф6 структура локальных оптимумов могла бы нарушиться, и оптимумов могло бы стать меньше; для Ф8 в новой системе окрестностей могли нарушиться множества постоянства.

Таблица 1. Сравнительный анализ эффективности генетических алгоритмов.

1.3    Метод изменяющихся вероятностей (МИВЕР) и исследование его работоспособности на тестовых задачах

1.3.1 Общая схема МИВЕР

Метод изменяющихся вероятностей представляет собой семейство стохастических алгоритмов псевдобулевой оптимизации, имеющих общую схему, в основе которой лежит алгоритм случайного поиска с адаптацией [1]. В самом общем виде эта схема (обозначим МИВЕР1) применительно к задаче (2) выглядит следующим образом:

1.       Задаются начальные значения компонент вектора вероятностей , .

.        Случайным образом (в соответствии с распределением вероятностей ), независимо выбираются  векторов .

.        Вычисляются соответствующие значения функционала .

.        Определяются  и . Значения  и  и соответствующие векторы  и  запоминаются.

.        По результатам п. 4 изменяются (в соответствии с правилом конкретного алгоритма) компоненты вектора вероятностей .

.        Пункты 2-5 повторяются  раз.

.        За решение задачи принимается вектор , определяемый из условия  ( при  повторении п. 4).

Начальное распределение вероятностей единичных значений компонент вектора  -  определяется на основе априорной информации о решаемой задаче. Если такая информация отсутствует, используется равновероятностное распределение, т.е. .

Пункт 5 соответствует получению апостериорного распределения вероятностей по результатам испытаний п. 2 и п. 3.

В [1] предложены следующие алгоритмы пересчета вектора вероятностей единичных компонент: СПА, МСПА1, МСПА2:

СПА :

 .

МСПА1 :

 ,

.

МСПА2 :

,

.

Первоначально метод был реализован для задачи условной псевдобулевой оптимизации, поэтому для безусловной оптимизации метод модифицирован так, что решение ищется во множестве . Множество . Общая схема (обозначим МИВЕР2) имеет вид:

.        Задаются начальные значения компонент вектора вероятностей , .

.        Случайным образом (в соответствии с распределением вероятностей ), независимо выбираются  векторов  и соответствующие значения  по правилу .

.        Вычисляются соответствующие значения функционала .

.        Из условий  и  находятся векторы  и . Значения  и  запоминаются. По правилу: ,  для ;

;

 ,

где  и  - число единичных компонент векторов  и  соответственно, определяются векторы  и , которые тоже запоминаются.

5.       По результатам п. 4 изменяются (в соответствии с правилом конкретного алгоритма (СПА, МСПА1, МСПА2)) компоненты вектора вероятностей .

.        Пункты 2-5 повторяются  раз.

.        За решение задачи принимается вектор , определяемый из условия  ( при  повторении п. 4).

СПА :

 , где .

МСПА1 и МСПА2меняются аналогично.

1.3.2 Исследование работоспособности на тестовых задачах

Методы МИВЕР1 и МИВЕР2 был программно реализованы. Исследование алгоритмов СПА, МСПА1 и МСПА2 проводилось на тестовых функциях: функция Растригина (первоначально бинаризуется) и многоэкстремальная псевдобулевая функция.

Задача 1. Дискретная функция Растригина:

, .

.

Задача 2. Задача псевдобулевой оптимизации:

, . .

Для исследования эффективности использовались показатели надежности и среднее число итераций. Показатели вычислялись по статистике набранной из 100 запусков алгоритмов. Для всех алгоритмов . Работа МИВЕР1 и МИВЕР2 сравнена с ГА. Результаты исследования эффективности представлены ниже. Результаты работы алгоритмов с наилучшими настройками представлены в таблице 2.

Задача 1.

ГА.

Надежность алгоритма (%):Среднее число итераций до определения минимума:

МИВЕР1.

Надежность алгоритма (%):Среднее число итераций до определения минимума:

МИВЕР2.

Алгоритм не находит глобальный оптимум задачи.

Задача 2.

ГА.

Надежность алгоритма (%):Среднее число итераций до определения минимума:

МИВЕР1.

Надежность алгоритма (%):Среднее число итераций до определения минимума:

МИВЕР2.

Надежность алгоритма (%):Среднее число итераций до определения минимума:

Таблица 2. Сравнительный анализ эффективности МИВЕР и ГА.

Из таблицы 2 видно, что ГА превосходит МИВЕР и по трудоемкости, и по надежности (МИВЕР2 не решил задачу 2).

1.4    Основные идеи вероятностного генетического алгоритма и исследование его работоспособности на тестовых функциях

Нетрудно понять, что ГА накапливают и обрабатывают некоторую статистическую информацию о пространстве поиска, однако эта статистика в явном виде отсутствует. Можно предложить следующий способ представления накопленной генетическими алгоритмами статистики - на текущей итерации в соответствие популяции решений ставить вектор вероятностей

,(3)

где - вероятность присвоения i-ой компоненте вектора решения  значения 1, k - номер итерации.

Для изучения работы алгоритмов изменения компонент вектора вероятностей будем представлять в виде графиков. Ниже представлены примеры типичного поведения компонент  для алгоритмов МИВЕР (рис. 5) и ГА (рис. 6).

Рис. 5. Пример изменения вероятностей в МИВЕР.

Рис. 6. Пример изменения вероятностей в ГА.

Из графиков видно, что в МИВЕР вероятности меняются линейно (в СПА, МСПА1 и МСПА2 «поощряющие» добавки прибавляются либо вычитаются), в ГА - нелинейно, т.к. новая популяция может значительно отличаться от предыдущей. Однако, в предельном случае (мутация отсутствует, пропорциональная селекция) изменение вероятностей близко линейному.

Когда какая-либо компонента вектора вероятностей сходится к 0 или 1, поиск по этой компоненте прекращается, что может привести к «захвату» локальным минимумом. В ГА поиск не прекращается, т.к. оператор мутации «выкидывает» решения в новые регионы поискового пространства. Мутация вызывает скачкообразные изменения (скачки тем больше, чем выше мутация) компонент вектора вероятности даже после того, как компонента сходится к 0 или 1, что придает ГА глобальные свойства. Очевидно, вероятности в МИВЕРе тоже не должны обращаться в 0 или 1, иначе алгоритм станет локальным. Нелинейное изменение вероятностей в ГА позволяет алгоритму находить решение быстрее, чем МИВЕР (показано в численных экспериментах).

Попробуем проанализировать работу ГА с точки зрения теории псевдобулевой оптимизации, рассмотрим основные шаги ГА.

Инициализация. Если априорная информация о пространстве поиска отсутствует, то начальная популяция решений формируется случайно - точки распределяются равномерно в бинаризованном пространстве поиска, т.е. .

Оператор скрещивания - генетический оператор поиска, посредством которого из выбранных индивидов (родительские особи) получаются новые (потомки). Решение, представленное бинарным вектором является вершиной n-мерного гиперкуба в булевом пространстве. Оператор скрещивания будет генерировать точки из некоторого подмножества, размерность которого определяется числом совпадающих бит в соответствующих позициях родительских особей. Легко показать, что одноточечное или двухточечное скрещивание не может получить все точки полученного подпространства, равномерное - может.

Для примера рассмотрим действие оператора скрещивание при  и родителях  и . Потомок может унаследовать любые гены родителей, т.е. решение, полученное при скрещивании может содержать 0 или 1 в любой позиции. Однако, при применении одноточечного скрещивания будут получены решения: , , .

В общем случае, если даны  и , где  и , то с помощью равномерного скрещивания можно получить  различных точек. При одноточечном скрещивании мы имеем  «эффективных» точек разрыва, разрыв в остальных  точках не даст новых точек. При каждом «эффективном» скрещивании мы получим 2 потомка, т.е. при одноточечном скрещивании можно получить всего  новых точек.

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

Попробуем сформулировать равномерное скрещивание в «негенетических» терминах. Пусть для формирования потомка используется  родителей (), где  - размер популяции. Им соответствует статистика , где .

При  статистика  совпадает с . Потомок формируется в соответствии со статистикой . Такой оператор поиска соответствует теории генетических алгоритмов, содержит в себе свойства оператора скрещивания и имеет математически ясную формулировку.

Оператор мутации - оператор широкого поиска, т.к. в результате его применения возможно появление решений вне данной статистики. Если компонента вектора вероятностей  обращается в 0 или 1, то поиск по компоненте вектора решения  прекращается. Мутация предотвращает появление предельных значений компонент вектора вероятностей.

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

1.4.1 Общая схема вероятностного генетического алгоритма

Попробуем сформулировать в «негенетических» терминах алгоритм, имеющий общую с генетическим алгоритмом схему, сохраняющий свойства генетических операторов. Такой вероятностный генетический алгоритм (ВГА) применимо к задаче (2) имеет следующую схему:

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

.        На k-м шаге в соответствии с распределением  формируются  векторов .

.        Случайным образом формируются новые решения: с вероятностью  компоненты векторов  меняются на противоположные.

.        Вычисляются соответствующие значения функционала .

.        Выбираются  векторов  из  в соответствии с конкретным правилом отбора.

.        Пересчитывается распределениеединичных компонент .

.        Если не выполняется условие остановки, то , , повторить шаги 2 - 6.

Если априорная информация о пространстве поиска отсутствует, . На шаге 2 выполняется поиск в соответствии с имеющейся статистикой, аналогичный скрещиванию в ГА. На шаге 3 происходит поиск вне имеющейся статистики - оператор мутации. На шаге 5 происходит получение апостериорной информации, и происходит пересчет распределения вероятностей единичных компонент.

1.4.2 Исследование работоспособности на тестовых задачах

Предложенный ВГА был реализован в программной системе «ProbGA» и апробирован на функциях 1-15. Результаты работы ВГА были сравнены с результатами работы стандартного ГА (таблица 3). Использовались следующие настройки: размер популяции - 50, максимальное число итераций - 50, число прогонов алгоритма - 50, мутация - высокая, селекция - ранговая.

Из таблицы видно, что ВГА превосходит обычный ГА: ВГА победил в 11 из 15 случаев (Ф3, Ф4, Ф6-Ф11,Ф13-Ф15), на Ф12 одинаково эффективен с ГА. В тех случаях, когда ВГА оказывается эффективней, разница в надежности существенная, когда побеждает обыкновенный ГА - ВГА проигрывает не значительно.

Обычный ГА выигрывает на функциях Ф1, Ф2 (многоэкстремальные функции одной переменной) и Ф5 (унимодальная, овражного типа), Ф12 имеет большую зону притяжения глобального минимума, в Ф13 и Ф14 значение в глобальном оптимуме значительно отличается от значений в ближайших локальных.

Таким образом, численные эксперименты показывают, что ВГА превосходит обычный ГА на наиболее сложных для оптимизации функциях, и не менее эффективен на более простых.

Таблица 3. Сравнительный анализ эффективности ВГА и стандартного ГА.

1.5    Алгоритм прогноза сходимости вероятностного генетического алгоритма

В результате анализа графиков изменения компонент вектора вероятностей (3) в ВГА было замечено следующее свойство: изменения компонент вектора вероятностей в ВГА происходят целенаправленно, в среднем компоненты вектора вероятностей сходятся к истинным значениям, т.е.

. (4)

Если предположить, что свойство (4) справедливо для ВГА при решении задачи (2), то это свойство можно использовать для прогноза сходимости генетических алгоритмов.

Построен следующий алгоритм прогноза:

1.       Для данной задачи выбрать определенную схему ГА, определить число итераций  и число прогонов алгоритма .

.        Набрать статистику . Усреднить  по . Выявить тенденцию изменения компонент .

.        Считать .(5)

Однако, в результате частного прогона при малых  решение  может быть не найдено, и  может принимать значения отличные от . Тогда среднее значение компонент может сместиться в противоположную сторону, либо слабо отличаться от . Поэтому для обеспечения сходимости к оптимуму, было предложено придавать веса компонентам вектора вероятностей в соответствии с результатом прогона. Т.е. наилучшие прогоны вносят больший вклад в среднее значение, наихудшие - меньший. Для прогноза вместо (5) можно использовался следующий интегральный критерий:

.(6)

Т.о. решение о том, что  принимается, когда  чаще оказывается больше 0.5 (а также дальше от 0.5). Пример усреднения компонент вектора вероятностей в алгоритме прогноза показан на рисунке 7. Сплошная линия - с использованием критерия (5) и пунктирная - интегральный критерий (6).

Рис. 7. Пример усреднения компонент вектора вероятностей в алгоритме прогноза

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

Предложенный алгоритм прогноза сходимости вероятностного ГА был апробирован на тестовых задачах и показал достаточно высокую надежность при заданных вычислительных ресурсах [23, 28]. Алгоритм прогноза может быть использован для стандартного ГА, вероятностного ГА и других стохастических алгоритмов псебдобулевой оптимизации.

1.6    Выводы

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

Рассмотрены методы изменяющихся вероятностей, разработанный специально для решения задач псевдобулевой оптимизации и генетический алгоритм с бинарным представлением решений. Предложено представлять накапливаемую и обрабатываемую ГА статистику представлять в виде распределения вероятностей единичных компонент вектора решений. Проведен анализ МИВЕРА и ГА, представлены результаты численных экспериментов. Показано, что ГА превосходит МИВЕР как по надежности, так и по быстродействию.

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

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

Глава II. Разработка и исследование метода вероятностного генетического программирования для моделирования сложных систем

.1      Методы решения задач аппроксимации в моделировании сложных систем

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

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

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

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

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

Непараметрические методы не требуют дополнительной информации о структуре (параметрической) моделируемого объекта. Задача регрессии решается путем восстановления плотности вероятности [9, 17]:

,

,

где  - заданная колоколобразная функция,  - параметр размытости.

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

.

Функция активации нейрона  - некоторое нелинейное преобразование взвешенной суммы входных переменных. Задавая различные архитектуры сетей, состоящие из множества нейронов можно описывать сложные нелинейные зависимости [7, 30].

Недостаток численной модели, при всем ее удобстве для принятия решений, заключается в том, что она, по сути, является «черным ящиком» (моделью, в которой перечисляются входные и выходные связи системы со средой, а информация о внутренней структуре «ящика» полностью отсутствует). Решение задачи символьной регрессии могло бы значительно продвинуть ситуацию.

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

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

2.2    Обычный метод генетического программирования для решения задачи символьной регрессии и его исследование

Для решения многих практических задач наиболее естественным представлением решений являются компьютерные программы. Обычно компьютерные программы - иерархические композиции процедур и входных данных, отражающих состояние системы. Одна из центральных задач теории вычислительных систем (computer science) - научить компьютер решать поставленную задачу, не объясняя ему как это делать. Генетическое программирование позволяет сделать это путем создания работающих компьютерных программ исходя из высокоуровневой постановки задачи. Генетическое программирование достигает поставленной цели автоматического программирования или программного синтеза (automatic programming, program synthesis) путем выращивания популяций компьютерных программ, используя принцип естественного отбора Дарвина, и основанные на генетических принципах операторы, которые могут включать репродукцию, скрещивание и мутацию [48].

Каким образом генетические алгоритмы могут быть использованы для автоматического программирования?

В 1975 году Джон Холланд предложил некую модификацию генетического алгоритма известную как классификатор (classifier system), состоящий из IF…THEN правил. Например, бит равный 1 означает выполнение условия IF, бит равный 0 - не выполнение, последующие биты определяют действие при выполнении (невыполнении) условий [45].

В 1985 году Н. Крамер предложил вычислять непосредственно код компьютерных программ и продемонстрировал эволюцию простых арифметических выражений. Он также предложил представление решений в виде деревьев [40].

Джон Коза (John R. Koza) в 1987 продемонстрировал эволюцию выражений языка программирования LISP (LISP S-expression), которые по сути являются компьютерными программами. Он впервые использовал термин «генетическое программирование». В 1989 году Коза показал применение генетического программирования для решения различных задач [49].

Настоящее развитие генетическое программирование получило после выхода в 1992 году книги Джона Козы «Genetic Programming: On the Programming of Computers by Means of Natural Selection & Genetics», в которой он продемонстрировал области применения метода, а также численные результаты экспериментов и некоторые практические рекомендации [50].

2.2.1 Представление решений в методе генетического программирования

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

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

Множество всех возможных внутренних вершин дерева называется функциональным множеством .

Множество всех возможных внешних вершин дерева называется терминальным множеством .

Элементы функционального множества обычно являются рабочими блоками программы (процедурами, функциями), элементы терминального множества - входными данными (переменными и константами). Пример дерева в методе ГП представлен на рис. 8.

Рис. 8. Пример решения в методе ГП.

Объединение функционального и терминального множеств назовем универсальным множеством .

Для решения поставленной задачи методом генетического программирования множества  и  должны удовлетворять следующим требованиям:

Замкнутость. Для обеспечения замкнутости любой элемент из множества  должен принимать в качестве аргумента любой элемент множества .

Например, множество  не является замкнутым, так может привести к делению на нуль.

Достаточность. Для обеспечения достаточности элементы множества  должны быть выбраны таким образом, чтобы можно было бы решить поставленную задачу.

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

2.2.2 Общая схема метода генетического программирования, применение основных генетических операторов

Общая схема метода генетического программирования представлена ниже:

1.       Генерируем начальную популяцию  одним из методов выращивания, использую элементы множеств  и .

.        На шаге  вычисляем пригодность решений в популяции .

.        Применяем операторы селекции, клонирования, скрещивания и мутации к поколению  и формируем новую популяцию .

.        Стоп, если допустимое решение найдено, иначе  и переходим к шагу 2.

Рассмотрим шаги алгоритма подробней.

Для инициализации популяции используются следующие методы выращивания деревьев (решений в пространстве поиска):

Полный метод (full method).

Задается глубина дерева . В вершины на глубине  () случайным образом выбираются элементы из функционального множества . На глубине  выбираются элементы из терминального множества . Т.о. получается полное дерево глубины .

Метод выращивания (grow method).

Задается глубина дерева . В вершины на глубине  () случайным образом выбираются элементы из функционального множества  или из терминального множества  (в этом случае рост текущей ветви заканчивается). На глубине  выбираются элементы из терминального множества . Т.о. выращивается дерево глубины не больше, чем .

Комбинированный метод (ramped half and half).

Часть популяции выращивается полным методом, другая - методом
роста [51].

Функция пригодности (fitness function) является оценкой приспособленности индивида к окружающей среде. Пригодность является движущей силой в естественном отборе Дарвина. Аналогично, функция пригодности в генетическом программировании является основанием для создания следующих поколений решений. Более приспособленные решения должны иметь большее значение функции пригодности, менее приспособленные - меньшее значение. Обычно функция пригодности принимает положительные значения.

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

Существует две схемы скрещивания в методе генетического программирования: стандартное скрещивание (standard crossover) и одноточечное скрещивание (one-point crossover).

Стандартное скрещивание осуществляется следующим образом. Выбираются родительская пара. У каждого из родителей выбирается точка скрещивания (дуга в графе). Родители обмениваются генами (поддеревьями), находящимися ниже точки скрещивания. Полученная пара является потомками.

Пример стандартного скрещивания (рис. 9):

Рис. 9. Пример стандартного скрещивания в методе генетического программирования.

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

Пример одноточечного скрещивания (рис. 10). Жирной линией отмечены связи, которые могут быть выбраны в качестве общей точки скрещивания:

Рис. 10. Пример одноточечного скрещивания в методе генетического программирования.

Мутация состоит из выполнения (обычно небольших) изменений в значениях одного или нескольких генов в хромосоме. Мутация применяется с очень низкой вероятностью . Однако существует ряд задач, решаемых с помощью метода генетического программирования, где допустимое решение может быть найдено экстенсивным использованием оператора мутации [37].

Существует две схемы применения оператора мутации в генетическом программировании.

При использовании первой схемы (точечная мутация), случайно выбранный узел в дереве меняется на случайно выбранный элемент того же типа. Т.е. выбранный ген заменяется случайно выбранным элементом терминального множества, если этот ген принадлежит терминальному множеству, или элементом функционального, если ген - элемент функционального множества (рис. 11).

Рис. 11. Пример мутации по схеме 1

При использовании второй схемы, выбранное поддерево заменяется поддеревом, выращенным методом роста, новое поддерево имеет глубину не больше, чем глубина выбранного поддерева (рис. 12).

Рис. 12. Пример мутации по схеме 2

программный оптимизация генетический символьный регрессия

2.2.3 Решение задачи символьной регрессии с помощью метода генетического программирования

Для решения задачи символьной регрессии с помощью генетического программирования необходимо выполнить следующие подготовительные шаги, а именно определить:

.        терминальное множество,

.        функциональное множество,

.        функцию пригодности,

.        параметры, контролирующие работу алгоритма,

.        критерий остановки.

Первый этап определяет множество термов, из которых будет строиться решение. В задаче символьной регрессии терминальное множество содержит набор переменных  (где  - размерность поставленной задачи) и набор констант, т.е.

.

На втором этапе пользователь метода должен определить множество функций, которые будут использованы для построения решений. Пользователь должен априори предполагать некоторую комбинацию функций, которые могли бы содержаться в решении задачи. Функциональное множество может содержать:

         арифметические операции (),

         математические функции (и т.д.),

         булевы операции (),

         специальные предопределенные функции (Automatically Defined Functions - ADFs).

Необходимо помнить, что заданное универсальное множество  должно удовлетворять условию замкнутости. Например, для исключения деления на нуль вводят «защищенное деление», которое возвращает единицу, когда знаменатель равен нулю.

Третий этап - определить функцию пригодности, вычисляемую по заданной обучающей выборке. Для решения задачи символьной регрессии предложена следующая функция пригодности (7)

(7)

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

Параметры, контролирующие работу алгоритма обычно включают:

-        размер популяции,

-        метод роста,

         максимальную начальную глубину деревьев,

         метод селекции и его параметры (например, размер турнира для турнирной селекции),

         вероятность и тип мутации.

В качестве критерия остановки работы алгоритма можно выбрать один из следующих:

-        достигнуто заданное число поколений (итераций),

-        достигнута заданная точность аппроксимации,

         относительное изменение средней пригодности не превышает заданной величины.

Общая схема алгоритма для решения поставленной задачи следующая:

1.       Инициализировать популяцию  случайным образом одним из методов роста.

.        Оценить популяцию, используя критерий (7).

.        Если выполняется критерий остановки, то КОНЕЦ, иначе шаг 4.

.        На итерации  произвести селекцию одним из предложенных методов для поколения .

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

.        В поколение  попадает часть особей из популяции  и часть из промежуточной популяции.

.        Переход к шагу 2.

2.2.4 Исследование работоспособности на тестовых задачах

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

1.       Функция: , . Выборка: случайная, объем - 200 точек. Условие достаточности не выполняется, т.е. функциональное множество не содержит тригонометрических функций.

Терминальное множество: , где .

Функциональное множество: .

Размер популяции: 100. Метод роста: полный. Начальная глубина деревьев: 9. Селекция: ранговая. Вероятность мутации: 0.001.

«Идеальным» решением было бы выражение, соответствующее разложению функции  в ряд. Для отрезка  разложение выглядит следующим образом

Найденное выражение:

.

Поколение: 3050.

Сложность дерева (число вершин): 197.

Ошибка аппроксимации (квадратичный критерий): 0.00505.

После упрощения полученного выражения получим:

Т.о. алгоритм смог восстановить первых 2 члена с точностью до знака и коэффициента.

.        Функция: . Выборка: случайная, объем - 2000 точек.

Терминальное множество: , где .

Функциональное множество: .

Размер популяции: 100. Метод роста: полный. Начальная глубина деревьев: 6. Селекция: ранговая. Вероятность мутации: 0.001.

Найдено точное решение: .

Поколение: 13.

Сложность дерева (число вершин): 7.

.        Функция Растригина: . Выборка: случайная, объем - 4000 точек.

Терминальное множество: , где .

Функциональное множество: .

Размер популяции: 100. Метод роста: полный. Начальная глубина деревьев: 6. Селекция: ранговая. Вероятность мутации: 0.05.

Найдено точное решение: .

Поколение: 178.

Сложность дерева (число вершин): 13.

.        Функция: . Выборка: случайная, объем - 2000 точек.

Терминальное множество: , где .

Функциональное множество: .

Размер популяции: 100. Метод роста: полный. Начальная глубина деревьев: 5. Селекция: ранговая. Вероятность мутации: 0.01.

Найдено точное решение:

.

Поколение: 72.

Сложность дерева (число вершин): 18.

.        Функция: . Выборка: случайная, объем - 3000 точек.

Терминальное множество: , где .

Функциональное множество: .

Размер популяции: 100. Метод роста: полный. Начальная глубина деревьев: 7. Селекция: ранговая. Вероятность мутации: 0.001.

Найдено решение:

.

Поколение: 42.

Сложность дерева (число вершин): 43.

Ошибка аппроксимации (квадратичный критерий): 0.036.

.        Функция: . Выборка: случайная, объем - 5000 точек.

Терминальное множество: , где .

Функциональное множество: .

Размер популяции: 100. Метод роста: полный. Начальная глубина деревьев: 7. Селекция: ранговая. Вероятность мутации: 0.001.

Найдено точное решение:

.

Поколение: 26.

Сложность дерева (число вершин): 21.

.        Функция Растригина: . Выборка: случайная, объем - 5000 точек.

Терминальное множество: , где .

Функциональное множество: .

Размер популяции: 100. Метод роста: полный. Начальная глубина деревьев: 9. Селекция: ранговая. Вероятность мутации: 0.01.

Найдено решение:

.

Поколение: 1500.

Сложность дерева (число вершин): 65.

Ошибка аппроксимации (квадратичный критерий): 2.986.

2.3    Основные идеи вероятностного генетического программирования и его исследование

Как упоминалось ранее, в основе метода ГП лежит генетический алгоритм предложенный Холландом [45]. Попробуем вместо стандартного ГА использовать вероятностный ГА, который активнее использует статистическую информацию о пространстве поиска.

Решения в ВГА - это бинарные строки конечной длины. Решения в методе ГП - деревья, которые могут иметь произвольную форму и размер. Поэтому для представления деревьев решений в виде булевых векторов мы зафиксируем форму и размер решений - будем работать только с полными деревьями заданной глубины (рис. 13).

Рис. 13. Пример полного дерева глубины 3.

Вершины дерева нумеруются сверху вниз и слева направо (рис. 14). Далее каждая вершина кодируется одним из методов бинаризации: внутренние вершины дерева - на основе функционального множества, внешние - на основе терминального, бинарные коды вершин составляются в строку.

, где

Рис. 14. Нумерация вершин полного дерева.

При вычислении выражения полного дерева, построенного из бинарной строки, может оказаться, что в какой-то из вершин появится функция одного аргумента (рис. 15). Тогда при интерпретации символьного выражения будем учитывать только левое поддерево данной вершины. При таком способе вычисления решения функция пригодности будет определена однозначно, однако в пространстве поиска будет появляться множества постоянства. Как показывают численные эксперименты, ВГА эффективно решает задачи содержащие множества постоянства (Ф7, Ф8, Ф14).

Рис. 15. Вычисление символьного выражения дерева, содержащего унарные функции

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

Рис. 16. Пример использования функции ADF1.

Если какой-либо элемент терминального множества должен встречаться в решении не во внешней вершине, а на каком-то промежуточном уровне, можно предложить использовать предопределенную функцию (обозначим ADF2), обнуляющую все функции, содержащиеся в пути: вершина ADF2 - терм (рис. 17). Как и раньше, функция ADF2 одного аргумента игнорирует поддерево справа.

Рис. 17. Пример использования функции ADF2.

В случае, когда предопределенные функции ADF1 и ADF2 не используются, точное решение все равно может быть найдено. Это возможно за счет появления в деревьях так называемого неэффективного кода (non-effective code) - поддеревьев не несущих никакой информации (например,  и др.). В [38] показано, что неэффективные коды защищают решения от разрушительного скрещивания (destructive crossover) - скрещивания, которое дает потомков с пригодностью ниже, чем у родителей.

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

1.       Задать небольшую начальную глубину деревьев.

2.       Запустить метод ГП.

.        Если в результате длительного времени приемлемое решение не найдено, и весь код деревьев эффективный, то увеличить глубину деревьев на 1. Исходные деревья становятся левыми поддеревьями корня.

4.     Если приемлемое решение найдено, то СТОП, иначе повторить
шаги 2 - 4.

Рис. 18. Пример наращивания деревьев.

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

2.3.1 Общая схема метода вероятностного генетического программирования

На основе предложенного выше способа кодирования и интерпретации полных деревьев построена схема метода ГП, основанная на механизме ВГП. Такая схема получила название вероятностное генетическое программирование (ВГП):

1.       Случайным образом формируются  векторов . Вычисляется распределение , .

.        На k-м шаге в соответствии с распределением  формируются  векторов .

.        Случайным образом формируются новые решения: с вероятностью  компоненты векторов  меняются на противоположные.

.        На основе векторов  формируются полные деревья решений, интерпретируются решения, решения оцениваются.

.        Выбираются  векторов  из  в соответствии с конкретным правилом отбора.

.        Пересчитывается распределение  единичных компонент .

.        Если не выполняется условие остановки, то , , повторить
шаги 2 - 6.

Оценивание деревьев в п. 4 происходит по критерию (7), аналогично обычному ГП.

2.3.2 Исследование работоспособности на тестовых задачах

1. Функция: . Выборка: случайная, объем - 1000 точек.

Терминальное множество: , где .

Функциональное множество: .

Размер популяции: 100. Глубина деревьев: 5. Селекция: ранговая. Вероятность мутации: 0.01.

Найдено точное решение: .

Поколение: 89.

. Функция Растригина: . Выборка: случайная, объем - 1000 точек.

Терминальное множество: , где .

Функциональное множество: .

Размер популяции: 100. Глубина деревьев: 5. Селекция: ранговая. Вероятность мутации: 0.01.

Найдено решение: .

Ошибка (квадратичный критерий): 2.28.

Поколение: 1000.

. Функция: . Выборка: случайная, объем - 100 точек.

Терминальное множество: , где .

Функциональное множество: .

Размер популяции: 100. Глубина деревьев: 5. Селекция: ранговая. Вероятность мутации: 0.01.

Найдено решение: .

Ошибка (квадратичный критерий): 1.15.

Поколение: 180.

2.4 Выводы

Во второй главе рассмотрены методы аппроксимации статистических данных в задаче моделирования сложных систем. Поставлена задача символьной регрессии.

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

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

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

Глава III. Практическая реализация разработанных алгоритмов

.1      Программная реализация обыкновенного и вероятностного генетического алгоритмов

На основе рассмотренного в п. 1.2. стандартного ГА и предложенного ВГА разработаны программные системы: «GA lab» и «ProbGA lab».

В качестве рабочей операционной системы (ОС) был выбрана Microsoft Windows, поскольку она является наиболее распространенной ОС, 32 битные приложения одинаково эффективно работают в различных версиях Windows: 9x, ME, 2000, NT, XP, ОС Windows обладает удобным и очень гибким интерфейсом [32].

В качестве среды программирования был выбран Borland C++ Builder, т.к. он обладает следующими свойствами:

-   Язык C++ объектно-ориентированный, обеспечивает наследование, полиморфизм, абстракцию данных.

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

-       Инкрементальный линкер осуществляет быструю и надежную сборку приложений в формате ЕХЕ файлов сравнительно меньшего размера [2, 31].

-       Чистый и доступный код приложений, которые C++ Builder строит на основе предоставляемых разработчику компонентных свойств, событий и методов, исключает скрытые и трудные в отладке макросы.

-       Создание DLL, LIB, и ЕХЕ файлов предоставляет свободу выбора формата целевого приложения в соответствии с требованиями конкретного проекта.

-       Прямое обращение к системным функциям Windows 9x и NT дает возможность программистам, работающим в среде C++ Builder при необходимости воспользоваться всеми возможностями современных операционных систем [33].

3.1.1 Программная система «GA lab»

Программная система «GA lab», реализует работу стандартного ГА с возможностью выбора различных параметров алгоритма. В качестве тестовых задач использованы функции, описанные в п.1.1. (см. приложение 1).

Приложение имеет следующие опции:

-   Выбор одинарного прогона или набора статистики;

-       Стандартное бинарное кодирование или рефлексивный код Грея с возможностью выбора точности кодирования (шага дискретизации);

-       Вероятность мутации: высокая, равномерная, низкая или отсутствует;

-       Селекция: турнирная, пропорциональная или ранговая;

-       15 тестовых задач;

-       Визуализация изменения пригодности: средней по популяции, лучшего и худшего индивидов;

Приложение разработано в среде визуального программирования Borland Builder C++ 5.0. Системные требования: IBM PC Pentium совместимый, 1Мб дискового пространства, 32 Мб ОЗУ, ОС Windows 9x, Me, 2000, NT, XP.

Работа начинается с окна выбора режима работы: одинарный прогон ГА или набор статистики (рис. 19). В обоих режимах предоставляется одинаковый выбор параметров за исключением выбора количества прогонов в режиме статистики.

Рис. 19. Стартовый диалог в приложении «GA lab».

Далее появляется окно, содержащее настройки алгоритма, органы управления и слежения за динамикой алгоритма (рис. 20).

Рис. 20. Главное окно приложения «GA lab».

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

3.1.2 Программная система «ProbGA lab»

Программная система «ProbGA lab» реализует работу вероятностного ГА с возможностью выбора различных параметров алгоритма. В качестве тестовых задач использованы функции, представленные в приложении 1.

Приложение имеет следующие опции:

-   Выбор одинарного прогона или набора статистики;

-       Стандартное бинарное кодирование или рефлексивный код Грея с возможностью выбора точности кодирования (шага дискретизации);

-       Вероятность мутации: высокая, равномерная, низкая или отсутствует;

-       Тип мутации: новая популяция, старая популяция или обе популяции;

-       Селекция: пропорциональная, элитарная, ранговая или турнирная с выбором размера турнира;

-       Схема формирования новой популяции: из объединения новой и старой, 50% из новой и 50% из старой;

-       15 тестовых задач;

-       Слежение за динамикой алгоритма: размерность бинарного вектора, текущий вектор вероятностей, текущее лучшее решение.

Приложение разработано в среде визуального программирования Borland Builder C++ 5.0. Системные требования: IBM PC Pentium совместимый, 1Мб дискового пространства, 32 Мб ОЗУ, ОС Windows 9x, Me, 2000, NT, XP.

Работа приложения начинается с окна выбора режима работы: одинарный прогон или набор статистики (рис. 21):

Рис. 21. Стартовый диалог в приложении «ProbGA lab».

Главное окно приложения содержит настройки алгоритма, органы управления и слежения за динамикой алгоритма (рис. 22).

Рис. 22. Главное окно приложения «ProbGA lab».

После завершения одинарного прогона в поле «Результат» выводится лучшее решение, значение выбранной функции в этой точке и номер итерации, когда было найдено решение (рис. 23). В режиме набора статистики после выполнения заданного числа прогонов выводится оценка надежности и среднего числа итерации.

Рис. 23. Вывод результатов в приложении «ProbGA lab».

3.2    Программная реализация методов обыкновенного и вероятностного генетического программирования

Рабочим языком программирования был выбран Borland C++, поскольку он предоставляет возможности гибкого объектно-ориентированного программирования, а также является мощнейшим инструментом для реализации программ под Win32.

Для представления деревьев решений в памяти компьютера был выбран связанный список классов, описывающих вершины дерева (рис. 24):

Рис. 24. Пример представления дерева в памяти компьютера.

3.2.1
Программная система «GP: Symbolic Regression»

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

Приложение разработано в среде визуального программирования Borland Builder C++ 5.0. Системные требования: IBM PC Pentium совместимый, 1Мб дискового пространства, 32 Мб ОЗУ, ОС Windows 9x, Me, 2000, NT, XP Среднее время вычислений (зависит от сложности структур деревьев, от размера популяции и объема выборки): до 100 поколений в минуту.

Ниже представлено главное окно приложения:

Рис. 25. Рабочее окно приложения «GP: Symbolic Regression».

Меню 1 состоит из элементов File , Options, Help. При входе в меню Options появляется окно настроек (рис. 26), в котором задается размер популяции, максимальная начальная глубина деревьев, метод выращивания, вероятность мутации, тип селекции и параметры. При выборе пункта Help появляется окно с информацией о данном программном продукте (рис. 27).

Рис. 26. Окно настроек.

Рис. 27. Окно Help.

В окне отображения лучшего решения в поколении 2 представлены: номер текущего поколения, пригодность лучшего решения и его выражение.

Текущие настройки параметров алгоритма 3 отражают текущие настройки (также сохраняются в файле «GP.ini»).

Кнопки управления работой приложения 4 включают Start, Stop, Exit.

Параметры, контролирующие работу алгоритма 5, включают номер текущего поколения, сложность лучшего решения и его ошибку.

При достижении заданной точности (по умолчанию равной 0.001) программа выдает сообщение (рис. 28) и продолжает работу. При равенстве ошибки нулю во всех точках выборки программа выдает сообщение в окне 2 и прекращает работу.

Рис. 28. Сообщение

По окончании работы алгоритма, программа создает (либо переписывает) файлы «Fitness.dat», содержащий изменение значений функции пригодности и «GentnBest.dat», содержащий решения последнего поколения и их пригодности.

3.2.2 Программная система «ProbGP: Symbolic Regression»

Программная система «ProbGP: Symbolic Regression» реализует работу алгоритма решения задачи символьной регрессии с использованием метода вероятностного ГП.

Приложение разработано в среде визуального программирования Borland Builder C++ 5.0. Системные требования: IBM PC Pentium совместимый, 1Мб дискового пространства, 32 Мб ОЗУ, ОС Windows 9x, Me, 2000, NT, XP.

Главное окно приложения показано на рис. 29:

Рис. 29. Главное окно приложения «ProbGP: Symbolic Regression».

В окне отображаются: лучшее решение на текущей итерации (рис. 30), график найденного решения для функции одной переменной (рис. 31) и график изменения пригодности (рис. 32).

Рис. 30. Просмотр текущего лучшего решения.

Рис. 31. График лучшего решения.

Рис. 32. График изменения пригодности.

В меню настроек алгоритма (рис. 33) имеется возможность выбора следующих параметров:

-   Размер популяции;

-       Глубина полного дерева;

-       Схема селекции: ранговая, пропорциональная, элитарная, турнирная с выбором размера турнира;

-       Вероятность мутации: низкая, равномерная, высокая или задается в ручную;

-       Схема мутации: новая, старая или новая и старая популяции;

-       Схема формирования новой популяции: селекция по объединению новой и старой популяции, 50% из старой и 50% из новой;

-       Стандартное бинарное кодирование или код Грея;

-       Критерий остановки: вручную, заданное число итераций.

Рис. 33. Окно настроек алгоритма.

В окне выбора функций и термов (рис. 34) пользователь может определить базовый набор элементов функционального и терминального множеств, которые будут использоваться при построении деревьев, среди них:

- Арифметические операции: сложение, вычитание, умножение и защищенное деление (возвращает 1, если знаменатель равен нулю);

-       Математические функции: , ,  (модуль), , , ;

-       Переменные: , константы: 0.1, 0.2, …, 0.9, 1.0;

-       Предопределенные функции: функция, обнуляющая поддерево, вершиной которого она является.

Рис. 34. Окно выбора функций и термов.

3.3    Постановка задачи оптимизации работы электростанции на топливных элементах в стационарном режиме

Эффект Fuel Cell (топливный элемент) был открыт в 1839 году Уильямом Грувом. Топливные элементы относятся к химическим источникам тока. Они осуществляют прямое превращение энергии топлива в электричество, минуя малоэффективные, идущие с большими потерями, процессы горения. Это электрохимическое устройство в результате высокоэффективного окисления топлива непосредственно вырабатывает электроэнергию.

Топливные элементы являются наиболее перспективным источником электрической энергии. Их преимущества:

-       Топливные элементы имеют высокий КПД при очень низких температурах, достигающий 80% (у обычных энергоустановок - 35%);

-       Цена одного киловатта энергии, вырабатываемой одним топливным элементом, ниже, чем у его конкурентов;

-       Энергия вырабатывается непрерывно при наличии в элементе топлива (в отличие от аккумуляторов, которые требуют периодической замены электролита);

-       Топливный элемент и продукты его работы экологически чисты;

-       Топливный элемент работает бесшумно;

-       Топливный элемент практически “всеяден”, т.е. в качестве топлива может использоваться практически любое водородосодержащее топливо;

-       Топливные элементы могут использоваться практически в любых условиях, включая загрязненную среду, низкие температуры и т.д.

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

3.3.1 Водородные топливные элементы - основные принципы

Конструктивно топливный элемент состоит из двух электродов - анода и катода - и разделяющего их электролита (рис. 35). На аноде окисляется, т.е. отдает электроны, восстановитель (топливо  или ), свободные электроны с анода поступают во внешнюю цепь, а положительные ионы удерживаются на границе анод-электролит (,). С другого конца цепи электроны подходят к катоду, на котором идет реакция восстановления (присоединение электронов окислителем ). Затем ионы окислителя переносятся электролитом к катоду (рис. 36) [55].

Рис. 35. Простейшая конструкция топливного элемента.

Рис. 36. Схема реакций в топливном элементе.

Для повышения выходного напряжения топливные элементы объединяются в группы - стеки (рис. 37).

Рис. 37. Пример объединения 3х топливных элементов.

Существуют различные типы топливных элементов, в основном различающиеся типом электролита. В последнее время большое распространение получили топливные элементы с полимерными мембранами, которые также содержат свободные протоны и могут быть использованы для перемещения ионов . Основные типы и области их применения представлены на таблице 4 и рисунке 38 [44, 52].

Таблица 4. Основные типы топливных элементов.

Рис. 38. Преимущества и области применения различных типов топливных элементов.

3.3.2 Теплоэлектростанции на топливных элементах

Теплоэлектростанции на топливных элементах являются сложными нелинейными системами. Проблема их оптимального управления до сих пор не решена.

Основной объект данного исследования - малогабаритная ТЭЦ на топливных элементах для бытового энергообеспечения, исследуемая в институте прикладных исследований при Высшей технической школе города Ульм (рис. 39). ТЭЦ имеет типичную для PEMFC (топливо - природный газ) структуру, основные элементы которой представлены на рисунке 40.

Рис. 39. Малогабаритная ТЭЦ исследуемая в высшей технической школе г. Ульм.

Рис. 40. Основные элементы ТЭЦ.

Вода и пригодный газ поступают в преобразователь (реформер), где образуется водород и одноокись углерода. Далее часть одноокиси углерода преобразуется в двуокись в реакторе высокой температуры (HT shift, 260-320), оставшаяся часть - в реакторе низкой температуры (LT shift, 200-260). Далее газ поступает в реактор-окислитель (PROX - Preferential Oxidation Reactor), увлажняется и подается в топливные элементы (в исследуемой ТЭЦ - 40 ячеек, ~5кВт). Отработавший газ сжигается. Вырабатываемое электричество через преобразователь поступает в электрическую сеть [42, 46].

3.3.3 Математическая модель электростанции на топливных элементах

Ранее для исследуемой электростанции была построена математическая модель, основанная на физико-химической теории процессов, протекающих в топливных элементах, и экспериментальных статистических данных о функционировании подсистем объекта [47]. Библиотека компонентов модели содержит все элементы ТЭЦ. Модель реализует практически все возможные режимы функционирования станции, а также содержит применяемую на электростанции систему управления. Модель была реализована в среде MatLab Simulink (рис. 41). Параметры системы управления и подсистем ТЭЦ выбраны в соответствии с техническими ограничениями.

Рис. 41. Структура Simulink - модели ТЭЦ.

3.3.4 Постановка задачи оптимизации

Поставлена следующая задача оптимизации - максимизация электрической производительности (выход тепла в рассмотрение не берется) для установившегося (стационарного) режима работы. Были выбраны 12 параметров, которые устанавливаются перед запуском электростанции и которые должны оказывать существенное влияние на эффективность работы ТЭЦ.

Математически критерий оптимальности выглядит следующим образом:

.

, где  - полученная электроэнергия,  - суммарное потребление энергии для обеспечения нормального функционирования ТЭЦ.

 - подводимая к системе энергия пропорциональная количеству используемого топлива, где   - константа, связанная с физикой процесса (теплота сгорания),  - интенсивность расхода природного газа. Т.о. критерий оптимальности имеет вид:

.

3.4    Решение задачи оптимизации работы электростанции на топливных элементах в стационарном режиме с помощью вероятностного генетического алгоритма

Сложность задачи оптимизации состоит в следующем: априорная информация о пространстве поиска в явном виде отсутствует (является ли функционал непрерывным, выпуклым, квадратичным), зависимость выходных переменных от входных сложная и нелинейная. Возможна многоэкстремальность. Получение оценок производных затруднено. Существуют значения параметров (области в пространстве поиска), где функционал не определен - объект не выходит на стационарный режим работы. Очевидно, что использование стохастических методов прямого поиска в данной задаче более предпочтительно, чем использование классических методов оптимизации. Будем использовать ВГА, предложенный в п. 1.4.

Для взаимодействия с Simulink-моделью, ВГА был реализован на языке программирования Matlab.

Как известно вычисления критерия оптимальности могут быть дорогими (в смысле времени, вычислительных затрат и т.д.), поэтому необходимо избегать повторного вычисления критерия в уже исследованных точках. Данная модель ТЭЦ требует до 20 минут реального времени (в худшем случае) для достижения установившегося режима, поэтому исследованные алгоритмом точки заносятся в базу данных, реализованную с помощью средств Matlab. Если ВГА генерирует точку, имеющуюся в базе, то критерий не вычисляется, а берется известное значение эффективности. Также реализована опция сохранения/загрузки результатов поиска на предыдущих итерациях.

Для слежения за динамикой работы ВГА изменение пригодности лучшего и среднего по популяции решения выводятся на экран.

Поскольку ГА являются эвристическими методами случайного поиска, строгой теории позволяющей оптимально выбирать параметры алгоритма, нет. Однако многолетний опыт использования ГА дает нам следующие практические советы [41, 57]:

-   Соотношение размер популяции - число итераций должно быть примерно равным. Соотношения 100-10 или 10-100 хуже, чем 25-40 или 40-25.

-       Следует использовать высокую мутацию, чтобы избежать захвата локальными оптимумами.

-       Следует использовать ранговую или турнирную селекцию, чтобы избежать стагнации.

Были выбраны следующие параметры ВГА:

-   Число переменных задачи - 12.

-       Интервалы изменения переменных: [0.034,0.3; 3.7,10; 17,50; 1123,1223; 1.2,2; 323,343; 473,723; 413,513; 1.3,4; 0.1,1; 0.1,2.5; 0.1,2.5].

-       Точность поиска: [0.01; 0.1; 3; 10; 0.1; 1; 10; 10; 0.1; 0.1; 0.1; 0.1].

-       Размерность задачи после бинаризации - 55.

-       Размер популяции - 25.

-       Селекция - турнирная (размер равен 2).

-       Мутация - высокая.

Ниже представлен график изменения пригодности (значения критерия оптимальности) для лучшего решения - сплошная линия и среднего значения по популяции - пунктирная (рис. 42).

Рис. 42. График изменения пригодности.

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

Полученный набор параметров дает значение электрической производительности равное 11.5%. Значение производительности, полученное для известных параметров используемых на исследуемой ТЭЦ - 5.5%. Следовательно, полученное решение позволяет повысить эффективность (на модели) в 2 раза.

3.4.1 Исследование устойчивости решения

Поскольку найденное решение должно быть реализовано на реальной ТЭЦ, необходимо проверить является ли решение устойчивым. Т.е. определить, как меняется значение электрической производительности, при отклонении параметров от оптимального значения.

Каждый параметр варьировался в пределах 20% от его значения при фиксированных значениях остальных параметров. Следующие графики показывают изменения значения критерия (рис. 43 - 54) :

Рис. 43. Расход воздуха в топливном элементе. BZ_np_Luft=0.12839. Допустимый интервал: [0.034, 0.3]. Точность: 0.01.

Рис. 44. Расход воды на реформере газа. PM2_Qsoll =7.3e-07. Допустимый интервал:[3.7e-07, 10e-07]. Точность: 0.1.

Рис. 45. Расход природного газа. Verdichter_f =22. Допустимый интервал: [17, 50]. Точность: 2.2.

Рис. 46. Температура в реформере. T_Ref_Br_soll =1223. Допустимый интервал: [1123, 1223]. Точность: 6,67.

Рис. 47. Давление в топливном элементе. BZ_p_soll =1.4286. Допустимый интервал: [1.2, 2]. Точность = 0.1.

Рис. 48. Температура воды в топливном элементе. st_Tsoll_BZ_Wasser=323. Допустимый интервал: [323, 343]. Точность: 0.65.

Рис. 49. Температура высокотемпературного реактора. st_Tsoll_HT_Kuehlung =522. Допустимый интервал: [473, 723]. Точность: 8.1.

Рис. 50. Температура низкотемпературного реактора. st_Tsoll_NT_Kuehlung=420. Допустимый интервал: [413, 513]. Точность: 6.67.

Рис. 51. Давление газа в реформере. V23.psoll=2.9548. Допустимый интервал: [1.3, 4]. Точность: 0.08.

Рис. 52. Отношение количества воздуха подводимого до/после блока PROX. X_luft=0.16. Допустимый интервал: [0, 1]. Точность: 0.06.

Рис. 53. Расход воды в увлажнителе (блок 1). Bef_A.Q_ein=0.87419e-05. Допустимый интервал: [0, 2.5e-05]. Точность: 0.078.

Рис. 54. Расход воды в увлажнителе (блок 2). Bef_K.Q_ein=1.2613e-05. Допустимый интервал: [0, 2.5e-05]. Точность: 0.078.

Очевидно, что найденное решение достаточно устойчивое. Небольшие изменения параметров не приводят к существенным изменениям в значении производительности. Исключение лишь параметр расхода природного газа - можно увеличить значение этого параметра для смещения в область устойчивости.

Из графиков видно, что найденное решение может быть улучшено. После запуска алгоритма покоординатного спуска из найденной точки, было найдено решение, дающее значение производительности - 11.9%.

Найденный с помощью ВГА набор параметров был реализован на реальной ТЭЦ, исследуемой в институте прикладных исследований Высшей Технической школы г. Ульм, Германия. Полученное значение электрической производительности оказалось меньше полученного на модели (предположительно из-за некачественных топливных элементов, используемых на ТЭЦ), но существенно больше, чем значение производительности при ранее известных параметрах.

3.5    Выводы

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

Использование объектно-ориентированного языка программирования позволяет легко адаптировать приложения для решения новых задач, менять схемы алгоритмов, добавлять новые типы операторов поиска.

Использование ВГА в задаче оптимизации работы электростанции на топливных элементах в стационарном режиме позволяет повысить эффективность исследуемой ТЭЦ в 2 раза. Практическое применение подтверждает высокую эффективность предложенного ВГА.

Заключение

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

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

Совместное использование предложенных вероятностных эволюционных алгоритмов позволяет в рамках единого подхода решать задачи моделирования и оптимизации сложных систем (моделирование путем решения задачи символьной регрессии, оптимизация - на основе полученной модели).

Список использованных источников:

1.         Антамошкин А.Н. Оптимизация функционалов с булевыми переменными. - Томск: Изд-во Том. ун-та, 1987, - 104 с.

2.       Бабэ Б. Просто и ясно о Borland C++. - М.: БИНОМ, 1994. - 400 с.

.        Вороновский Г.К., и др. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности. Х.: ОСНОВА, 1997.

4.       Гилл Ф., Мюррэй У. Численные методы условной оптимизации. М.: МИР, 1977.

5.       Гмурман В.Е. Теория вероятностей и математическая статистика. - Учеб. пособие. М.: Высш. шк., 2000, - 479 с.

6.       Гринченко С.Н. Метод «проб и ошибок» и поисковая оптимизация: анализ, классификация, трактовка понятия «естественный отбор». Электронный журнал «Исследовано в России», 2003.

7.       Заенцев И.В. Нейронные сети: основные модели. - Учеб. пособие к курсу «Нейронные сети», ВГУ, Воронеж, 1999.

.        Карманов В.Г. Математическое программирование // БСЭ, т.15. М.: Советская энциклопедия, 1974.

9.       Медведев А.В. Непараметрические системы адаптации. - Новосибирск: Наука, 1983, - 174 с.

.        Оптимизация - #"518306.files/image341.gif">

А - Простейшие степенные функции:

Функции одноэкстремальные с минимумом в точке . Если , то в точке минимума по j-ой координате функция не дифференцируема; точка является угловой.

А - Многоэкстремальные степенные функции:

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

Б - Простые гармонические (многоэкстремальные) функции:

Минимум функций равен нулю в начале координат. Функции имеют симметрию относительно точки . Каждая функция  может принимать значения z, либо 1.

В - Гармонические много экстремальные функции:

Глобальный минимум - в точке .

Г1 - Простейшая гиперболическая потенциальная функция:

Минимумы в точках , глубина минимума определяется коэффициентом .

Г2 - Простейшая экспоненциальная потенциальная функция:

Минимумы в точках , глубина минимума определяется коэффициентом . Чем больше величина , тем уже область минимума (круче функция).

Д - Другие комбинированные функции:

Приложение 2

Набор тестовых задач

Функция 1.

,

Функция 2.

,

Функция 3. Функция Растригина.

,

Функция 4. Функция Растригина овражная с поворотом осей.

,

где , ,  - растяжение/сжатие по ,

 - угол поворота

,

Функция 5. Функция Розенброка.

,

Функция 6. Функция Griewank.

,

Функция 7. Функция De Jong 2.

,

Функция 8. Функция «Сомбреро».

,

Функция 9. Функция Катникова.

,

Функция 10. Функция Катникова

,

Функция 11.

,

Функция 12.

,

Функция 13. Мультипликативная потенциальная функция

,

,

Функция 14. Аддитивная потенциальная функция

,

,

Функция 15. "Лисьи норы" Шекеля.

,

K=500, cj = j, , .