Разработка и исследование вероятностных эволюционных алгоритмов для моделирования и оптимизации сложных систем
Диссертация - Менеджмент
Другие диссертации по предмету Менеджмент
ого типа), Ф12 имеет большую зону притяжения глобального минимума, в Ф13 и Ф14 значение в глобальном оптимуме значительно отличается от значений в ближайших локальных.
Таким образом, численные эксперименты показывают, что ВГА превосходит обычный ГА на наиболее сложных для оптимизации функциях, и не менее эффективен на более простых.
Таблица 3. Сравнительный анализ эффективности ВГА и стандартного ГА.
Вероятностный ГАГАКод ГреяБинарный кодОптимальные параметрыНадежностьСр. число итер.НадежностьСр. число итер.НадежностьСр. число итер.Ф18896100Ф296600Ф31006485Ф4785244Ф5848100Ф6566028Ф782207Ф81009286Ф91005076Ф101003236Ф111003228Ф1210010000%8Ф131000000%8Ф141000000%6Ф1510010098
1.5Алгоритм прогноза сходимости вероятностного генетического алгоритма
В результате анализа графиков изменения компонент вектора вероятностей (3) в ВГА было замечено следующее свойство: изменения компонент вектора вероятностей в ВГА происходят целенаправленно, в среднем компоненты вектора вероятностей сходятся к истинным значениям, т.е.
. (4)
Если предположить, что свойство (4) справедливо для ВГА при решении задачи (2), то это свойство можно использовать для прогноза сходимости генетических алгоритмов.
Построен следующий алгоритм прогноза:
1.Для данной задачи выбрать определенную схему ГА, определить число итераций и число прогонов алгоритма .
.Набрать статистику . Усреднить по . Выявить тенденцию изменения компонент .
.Считать .(5)
Однако, в результате частного прогона при малых решение может быть не найдено, и может принимать значения отличные от . Тогда среднее значение компонент может сместиться в противоположную сторону, либо слабо отличаться от . Поэтому для обеспечения сходимости к оптимуму, было предложено придавать веса компонентам вектора вероятностей в соответствии с результатом прогона. Т.е. наилучшие прогоны вносят больший вклад в среднее значение, наихудшие - меньший. Для прогноза вместо (5) можно использовался следующий интегральный критерий:
.(6)
Т.о. решение о том, что принимается, когда чаще оказывается больше 0.5 (а также дальше от 0.5). Пример усреднения компонент вектора вероятностей в алгоритме прогноза показан на рисунке 7. Сплошная линия - с использованием критерия (5) и пунктирная - интегральный критерий (6).
Рис. 7. Пример усреднения компонент вектора вероятностей в алгоритме прогноза
Из графиков видно, что взвешенное усреднение с интегральным критерием позволяет выявить тенденцию изменения компонент вектора вероятностей за меньшее число итераций, т.к. уменьшает вклад неудачных прогонов.
Предложенный алгоритм прогноза сходимости вероятностного ГА был апробирован на тестовых задачах и показал достаточно высокую надежность при заданных вычислительных ресурсах [23, 28]. Алгоритм прогноза может быть использован для стандартного ГА, вероятностного ГА и других стохастических алгоритмов псебдобулевой оптимизации.
1.6Выводы
В первой главе рассмотрены основные свойства задач оптимизации сложных систем, затрудняющие или делающие невозможным применение классических методов оптимизации. Рассмотрен метод бинаризации, позволяющий сводить любые задачи дискретного программирования, в том числе и разношкальные, к задачам псевдобулевой оптимизации.
Рассмотрены методы изменяющихся вероятностей, разработанный специально для решения задач псевдобулевой оптимизации и генетический алгоритм с бинарным представлением решений. Предложено представлять накапливаемую и обрабатываемую ГА статистику представлять в виде распределения вероятностей единичных компонент вектора решений. Проведен анализ МИВЕРА и ГА, представлены результаты численных экспериментов. Показано, что ГА превосходит МИВЕР как по надежности, так и по быстродействию.
Предложен новый алгоритм - вероятностный генетический алгоритм, комбинирующий эвристические идеи интеллектуальных информационных технологий и строгий формальный аппарат современной математики. Показано, что ВГА эффективно решает сложные задачи оптимизации и превосходит стандартный ГА по надежности и быстродействию на наиболее сложных задачах.
Предложенный алгоритм прогноза сходимости ВГА эффективно выявлять тенденции изменения компонент вектора вероятностей и использовать полученную информацию для ускорения сходимости алгоритма.
Глава II. Разработка и исследование метода вероятностного генетического программирования для моделирования сложных систем
.1Методы решения задач аппроксимации в моделировании сложных систем
В ситуациях, когда активный эксперимент с объектом невозможен, приходится работать с его моделью. Исследования с помощью математических моделей зачастую являются единственно возможным способом изучения и решения важнейших практических задач управления в сложных системах.
Математические модели значительно облегчают понимание исследуемой системы, позволяют производить исследования в абстрактном плане, упрощать изучаемые задачи и т.д. Они позволяют воспроизводить и исследовать реальные процессы, их структуру, свойства и поведение. С помощью моделей можно получить параметры и характеристики системы и ее отдельных подсистем значительно проще, быстрее и экономичней, чем при исследовании реальной системы.
Однако на практике подчас сложно зафиксировать свойства фу