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

Понятие оптимальности получило строгое и точное представление в математических теориях, прочно вошло в практику проектирования и эксплуатирования технических систем, сыграло важную роль в формировании современных системных представлений. Математически задача оптимизации формулируется как задача поиска экстремума некоторого функционала, выражающего зависимость выходных параметров исследуемого объекта (системы, процесса) от входных [11, 34]. При решении задач оптимизации сложных систем часто встречаются ситуации, которые затрудняют или делают невозможным применение классических методов. За прошедшие годы было предложено много различных схем применения эволюционных алгоритмов для решения сложных задач оптимизации [35, 36, 58, 61, 62]. В ситуациях, когда с объектом нельзя активно экспериментировать, оптимизация производится по модели объекта.Анализ приведенных выше и иных определений термина «оптимизация» позволяет выделить в этом термине две основные составляющие: 1) указание на наличие моделирующего некоторую реальность целевого критерия (целевой функции/целевого функционала, критерия оптимизации, экстремальной характеристики, показателя экстремума, критерия качества и др.), экстремальное (максимальное или минимальное) значение которого необходимо либо однократно определить (если его положение не зависит от времени), либо перманентно отслеживать (в противном случае); Можно использовать следующий алгоритм перевода бинарного кода в Грей-код и наоборот: начать со старшего (правого) бита для получения Грей кода и с левого для получения бинарного кода, последовательно заменять биты по правилу: На каждом шаге заменяется два бита и производится смещение на один бит таким образом, что на последующем шаге заменяется один новый бит и один старый. ГА работает с генотипом, фенотип служит для определения пригодности индивида (оценки качества решения поставленной задачи), поэтому для работы алгоритма необходимо определить некоторую функцию кодирования (, где - пространство поиска, - пространство представлений решений) и функцию декодирования (). Т.о. на самом деле ГА решают не задачу , где , а задачу , где и . Как отмечалось в п.1.1., к задаче (2) сводятся практически любые задачи с дискретными переменными (возможно выраженные в разных шкалах), а также задачи с непрерывными переменными (заменяя непрерывные переменные дискретными с заданной точностью). Код Грея Бинарный код Код Грея Бинарный код Код Грея Бинарный код Код Грея Бинарный кодВ первой главе рассмотрены основные свойства задач оптимизации сложных систем, затрудняющие или делающие невозможным применение классических методов оптимизации. Рассмотрен метод бинаризации, позволяющий сводить любые задачи дискретного программирования, в том числе и разношкальные, к задачам псевдобулевой оптимизации. Рассмотрены методы изменяющихся вероятностей, разработанный специально для решения задач псевдобулевой оптимизации и генетический алгоритм с бинарным представлением решений.Генетическое программирование достигает поставленной цели автоматического программирования или программного синтеза (automatic programming, program synthesis) путем выращивания популяций компьютерных программ, используя принцип естественного отбора Дарвина, и основанные на генетических принципах операторы, которые могут включать репродукцию, скрещивание и мутацию [48]. Настоящее развитие генетическое программирование получило после выхода в 1992 году книги Джона Козы «Genetic Programming: On the Programming of Computers by Means of Natural Selection & Genetics», в которой он продемонстрировал области применения метода, а также численные результаты экспериментов и некоторые практические рекомендации [50]. Вершины дерева являются элементами одного из двух множеств: Множество всех возможных внутренних вершин дерева называется функциональным множеством . Множество всех возможных внешних вершин дерева называется терминальным множеством . В вершины на глубине () случайным образом выбираются элементы из функционального множества или из терминального множества (в этом случае рост текущей ветви заканчивается).Во второй главе рассмотрены методы аппроксимации статистических данных в задаче моделирования сложных систем. Поставлена задача символьной регрессии. Разработан алгоритм решения задачи символьной регрессии с использованием метода генетического программирования.В качестве рабочей операционной системы (ОС) был выбрана Microsoft Windows, поскольку она является наиболее распространенной ОС, 32 битные приложения одинаково эффективно работают в различных версиях Windows: 9x, ME, 2000, NT, XP, ОС Windows обладает удобным и очень гибким интерфейсом [32]. Прямое обращение к системным функциям Windows 9x и NT дает возможность программистам, работающим в среде C Builder при необходимости воспользоваться всеми возможностями современных операционных систем [33]. Работа начинается с окна выбора режима работы: одинарный прогон ГА или набор статистики (рис. Далее появляется окно, содержащее настройки алгоритма, органы у

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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