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

Содержание.

Введение.

Актуальность темы исследований.

Цель работы.

Теоретические и практические результаты.

Краткое содержание работы.

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

1.1. Генетический алгоритм: основные генетические операторы и схема

1.1.1. Общие принципы ГА.

1.1.2. Кодировка хромосом.

1.1.3. Вид генетических операторов.

1.1.4. Структура и параметры алгоритма.

1.1.5. Вид функции соответствия.

1.2. Генетический алгоритм: история появления и развития.

1.3. Применение генетического алгоритма.

1.4. Выводы по главе 1.

Глава 2. Система поддержки принятия решений на основе нечетких продукционных правил: объект параметрической настройки.

2.1. Организации СППР и построение базы правил на основе лингвистических термов.

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

2.3. Кодирование и оценка хромосом при параметрической настройке СППР.

2.3.1. Кодирование хромосом.

2.3.2. Обучающая выборка и оценивание хромосом.

2.4. Пример реализации СППР: система автоматизации технического анализа в области валютного дилинга.

2.5. Выводы по главе 2.

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

3.1. Теорема шим: принципы функционирования ГА и методы оценки эффективности.

3.1.1. Шима.

3.2. Модифицированный оператор мутации: разработка и исследование.

3.2.1. Линейная генетическая мутация (ЛГМ+).

3.2.2. Нормальная генетическая мутация (НГМ+).

3.2.3. Показательная генетическая мутация.

3.3. Модифицированный оператор скрещивания: разработка и исследование.

3.4. Модифицированный оператор селекции: разработка и исследование.

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

3.4.2. Разработка алгоритма формирования пар: инбридинг и аутбридинг по генотипу и фенотипу.

3.5. Выводы по главе 3.

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

4.1. Адаптационные механизмы: динамически изменяемые параметры, макромутации,.

4.1.1. Виды адаптационных механизмов.

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

4.1.3. Макромутация.

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

4.2.1. Параллельный ГА: причины возникновения и использования

4.2.2. Схема многопопуляционного параллельного ГА.

4.2.3. Алгоритм организации миграции хромосом между популяциями.

4.3. Выводы по главе 4.

Глава 5. Программная реализация.

5.1. Программная реализация разработанных модификаций ГА: модуль «Генетический конструктор».

5.1.1. Основные функции модуля.

5.1.2. Работа с модулем: интерфейс, основные формы.

5.2. Программная реализация средства построения СППР с генетической параметрической настройкой: модуль «Генетическая СППР».

5.2.1. Основные функции модуля.

5.2.2. Работа с модулем: интерфейс, основные формы.

5.3. Пример построения и параметрической настройки СППР.

5.4. БД: хранение сформированных моделей.

5.5. Разработанные функции и программные модули.

5.6. Выводы по главе 5.

Результаты.

Использующиеся сокращения.

Актуальность темы исследований

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

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

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

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

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

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

Цель работы

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

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

- разработки модифицированных генетических операторов,

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

- реализации программных средств для построения СППР на основе нечетких продукционных правил и их настройки при помощи ГА

Теоретические и практические результаты

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

Предложены две методики обмена хромосомами между популяциями.

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

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

4. В рамках разработки ГА для параметрической настройки СППР . реализован ряд механизмов адаптации, в частности механизма макромутаций, механизм циклических изменений параметров и ряд других.

5. Исследованные и разработанные алгоритмы реализованы в виде Цг программных модулей; проведено практическое тестирование полученных программных средств при помощи специальных тестовых функций.

Краткое содержание работы

Работа состоит из введения, 5 глав и заключения. Общий объем работы составляет 148 страниц. Список литературы составляет 21 наименование.

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

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

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

В главе 3 рассматриваются варианты алгоритмов с точки зрения применения в них различных генетических операторов. Проанализировано влияние на эффективность алгоритма различных видов операторов скрещивания, мутации и селекции. Реализованы различные варианты алгоритма, с разными генетическими операторами и различной вероятностью их выполнения. Тестирование проводилось при помощи типовых тестовых функций (DeJong's function, Rastrigin's function и т.п.). Также в главе 3 рассмотрен вопрос эффективности функционирования генетических алгоритмов и рассмотрена теорема шим.

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

В главе 5 представлена программная реализация разработанных и исследованных алгоритмов. Представлен модуль «Генетический конструктор», который позволяет пользователю строить различные варианты генетических алгоритмов, устанавливать различные параметры ГА, тестировать их при помощи специальных тестовых функций. В рамках модуля реализована возможность на каждой итерации просматривать изменение функции соответствия, параметров и кодировки каждой из популяций многопопуляционного параллельного алгоритма. Также есть возможность строить классические последовательные алгоритмы. Параметры разработанных алгоритмов сохраняются в специальную базу данных; структура БД также приведена в данной главе.

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

5.6. Выводы по главе 5

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

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

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

Результаты

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

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

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

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

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

Использующиеся сокращения о ГА - генетический алгоритм о СППР - система поддержки принятия решений о МПГА - многопопуляционный параллельный генетический алгоритм о БД - база данных о ФС (ЯЯ) - функция соответствия о РГМ - равномерная генная мутация о РХМ - равномерная хромосомная мутация о ЛГМ+ - линейная генетическая мутация о НГМ+ - нормальная генетическая мутация о ПГМ + - показательная генетическая мутация о МС+ - модифицированный оператор скрещивания о ОМ (1М) - «островная модель», модификация параллельного ГА ФП -функция принадлежности

1. Deb К., Goldberg D. A comparative analysis of selection schemes used in genetic algorithms. In G. J. Rawlins, editor, Foundations of Genetic Algorithms. San Mateo: Morgan Kaufman, 1991 - C. 69-93

2. Курейчик B.M. Генетические алгоритмы. -Таганрог: Изд-во ТРТУ, 1998

3. Holland J.H. Adaptation in Natural and Artificial Systems. Ann Arbor: The University of Michigan Press, 1975

4. Schwefel H.P., Numerical Optimization of Computer Models. -Chichester: John Wiley & Sons Ltd, 1977

5. Букатова И.Л. Эволюционное моделирование и его приложения. -М.: Наука, 1979

6. Ротштейн А.П. Интеллектуальные технологии идентификации -Винница: Изд. ВДУ, 1999

7. Spears W.M., DeJong К.А. An analysis of the interacting roles of population size and crossover in genetic algorithms//Proceedings of the Int'l Workshop Parallel Problem Solving from Nature, 1990 C.38-47

8. Spears W.M., DeJong K.A. A formal analysis of the role of multi-point crossover in genetic algorithms//Annals of Mathematics and Artificial Intelligence, 1992, Volume 5, #1 C.1-26.

9. Schaffer J., Morishima A. An adaptive crossover distribution mechanism for genetic algorithms//Proc of the 2nd Int. Conf. on Genetic Algorithms and Their Applications, 1987 -C. 36-40

10. Батищев Д.И., Исаев С.А. Оптимизация многоэкстремальных функций с помощью генетических алгоритмов. В: Изд-во ВГТУ. 1997

11. Божич В.И., Лебедев О.Б., Шницер Ю.Л. Разработка генетического алгоритма обучения нейронных сетей//Перспективные информационные технологии и интеллектуальные системы. №1. 2001 С. 21-24.

12. Лебедев Б.К. Методы поисковой адаптации в задачах автоматизированного проектирования СБИС//Монография Таганрог: Изд-во ТРТУ, 2000.

13. Маркин М.И., Смелянский Р.Л. Синтез архитектуры нейронной сети для прикладной задач ^/Перспективные информационные технологии и интеллектуальные системы М: 2001 г.

14. Herrera F., Lozano М., Verdegay J. Adaptation of Genetic Algorithm Parameters Based on Fuzzy Logic Controllers, in Herrera F. and Verdegay J.L. (Eds), Genetic Algorithms and Soft Computing. -Rhysica-Verlag, 1996 -C. 95-125

15. Muhlenbein H. Parallel Genetic Algorithms, Population Genetics and Combinatorial Optimization//Proc. of the Third International Conference on Genetic Algorithms. San Mateo: Morgan Kaufmann, 1989.

16. Филиппов С.Ж. Статистические методы анализа технических индикаторов в области валютного дилинга//Вестник Северо-Западногоотделения Метрологической академии. Сб. научн. тр. СПб., Изд-во ВНИИМ им. Д.И.Менделеева, 2000. - Вып. 4 - С.63-66

17. Куприянов М.С., Матвиенко Н.И. Использование эволюционных алгоритмов для решения оптимизационных задач//Тезисы докладов научно-технической конференции «Диагностика, информатика, метрология и экология» СПб: 1997.