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

• Автор: Горячев, Юрий Владимирович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Москва
• Количество страниц: 133 с. : ил

ОГЛАВЛЕНИЕ

СПИСОК СОКРАЩЕНИЙ

ВВЕДЕНИЕ.
Глава 1. Проблемы решения многокритериальных и теоретикоигровых задач эволюционный подход анализ состояния и постановка задачи исследования.

1.1. Существующие и возможные подходы в оптимизации сложных

систем газодобывающей отрасли

1.2. Технология генетического поиска в задачах векторной

оптимизации.

1.2.1. Методы векторной оптимизации

и эволюционные вычисления.

1.2.2. Классификация генетических алгоритмов

1.2.3. Обзор и анализ генетических алгоритмов
векторной оптимизации.
1.3. I енетичсскис алгоритм ы в теоретикош ровых м од елях
1.4. Постановка задачи исследования
Выводы по главе 1.
Глава 2. Построение генетических алгоритмов для решения
многокритериальных и теоретикоигровых задач.
2.1. Выбор принципа оптимальности при моделировании сложных
систем
2.2. Генетический алгоритм векторной оптимизации
2.2.1 Структура алгоритма и принципы построения.
2.2.2. Тестирование и анализ алгоритма
2.3. Гснетический алгоритм поиска равновесия по Нэшу
2.3.1. Структура алгоритма и принципы построения
2.3.2. Тестирование и анализ алгоритма
2.4. Генетический алгоритм поиска активного равновесия.
2.4.1. Геометрический метод отыскания активного равновесия,
основанный на технологии генетического поиска Парсто
оптимальных и равновесных по Нэшу решений.
2.4.2. Принципы построения генетического алгоритма поиска активного равновесия
2.4.3. Тестирование и анализ алгоритмов.
2.5. Алгоритмические подходы к решению многокритериальных и
теоретикоигровых задач со многими параметрами
2.5.1. Преимущества и недостатки методов сжатия битовых строк и целочисленного кодирования
2.5.2. Генетические операторы целочисленного кодирования
2.5.3. Тестирование и анализ алгоритмов целочисленного
кодирования
2.6. Сходимость разработанных алгоритмов
Выводы по главе 2.
Глава 3. Моделирование сети передачи данных автоматизированного технологического комплекса газодобычи и расчет оптимального распределения потоков данных на основе генегического алгоритма поиска активного равновесия
3.1. Постановка задачи
3.1.1. Потоковая модель сети автоматизированного технологического комплекса газодобычи
3.1.2. Теоретикоигровая модель.
3.2. Описание и тестирование алгоритма
3.3. Расчет оптимального распределения потоков данных по канчам
связи сети смешанной топологии.
3.4. Анализ результатов
Выводы по главе 3
ЗАКЛЮЧЕНИЕ.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК.
ПРИЛОЖЕНИЕ.
СПИСОК СОКРАЩЕНИЙ
АСУ ТП автоматизированная система управления технологическим процессом
АТКГД автоматизированный технологический комплекс газодобычи
ВО векторная оптимизация
ГА генетический алгоритм
ГАПАР генетический алгоритм поиска активного равновесия
ГАПРН генетический алгоритм поиска равновесия по Нэшу
ГП генетическое программирование
ДП диспетчерский пункт
ЕСГ единая система газоснабжения
МАСУ интегрированная автоматизированная система управления
ИУСДУ информационноуиравляющая система диспетчерского управления
КС классифицирующие системы
ЛПР лицо, принимающее решение
ОУ объект управления
ПГА простой генетический алгоритм
СП случайный поиск
спд сеть передачи данных
сс сложная система
тто тестовая точкаособь
щ целочисленное кодирование
эв эволюционные вычисления
ЭИ эволюционные игры
эп эволюционное программирование
эс эволюционные стратегии
эти эволюционная теория игр
vi iii диспетчерское
управление и сбор данных
ВВЕДЕНИЕ
Актуальность


Васильева отражают современный взгляд на представление о сетях передачи данных как сложных системах с конфликтными взаимодействиями отдельных абонентов или их классов. Значительное влияние на исследования по теме данной диссертации оказали работы зарубежных авторов а по генетическим алгоритмам для многокритериальных задач , , V Vi, , , i, . Научная новизна диссертации, главным образом, определяется тем, что в ней впервые генетические алгоритмы применяются для решения теоретикоигровых задач в соответствии с конкретным принципом оптимальности, выбранным ЛИР. В обширной литературе по генетическим алгоритмам и численным методам решения игровых задач этот подход ранее не применялся. Основные положения, выносимые на защиту. Генетический алгоритм многокритериальной оптимизации по конусу генетический алгоритм векторной оптимизации, являющийся результатом совместной разработки. Автору диссертации принадлежит детальная алгоритмическая реализация общей структуры алгоритма, а также его отладка, тестирование и анализ. Генетический алгоритм поиска равновесия по Нэшу. Программная реализация алгоритма, его тестирование и анализ. Генетический алгоритм поиска активного равновесия. Программная реализация алгоритма, его тестирование и анализ. Методика целочисленного кодирования для решения многопараметрических задач на основе разработанных алгоритмов. Анализ и тестирование целочисленных модификаций указанных алгоритмов. Теоретикоигровая потоковая модель сети передачи данных АТК Г Д. Решение задачи оптимального распределения потоков данных по каналам связи сети передачи данных АТК ГД смешанной топологии на основе предлагаемых алгоритмов. Практическая ценность диссертации заключается в том, что алгоритм оптимального распределения потоков данных может быть использован для расчета метрик маршрутов, он обладает высокой скоростью сходимости и точностью, достаточной для рассматриваемого класса задач. Теоретическое значение настоящего исследования состоит в разработке принципиально нового класса численных методов для решения многокритериальных и игровых задач, а также в создании моделей СПД, учитывающих конфликты при распределении трафика. Ценность предлагаемого подхода к моделированию СПД в его общности по отношению к различным типам СПД. Установление определенного равновесия в игровом смысле позволяет выявить равновесные режимы функционирования сети. Разработанные алгоритмы оптимального распределения потоков данных могут служить основой для построения интеллектуалыюго алгоритма маршрутизации, что значительно повысит уровень организации СПД АТК газодобычи в целом. Отметим также, что эти алгоритмы просты в реализации и являются универсальными по отношению к виду целевых функций, определяющих интересы абонентов СПД. Практика разработки АСУП И АСУ ТП в предыдущие годы показывает, что разработка этих систем на предприятии проводилась, как правило, изолировано. Это привело к тому, что хотя общее число решаемых задач в отдельных АСУ достаточно велико, но несогласованность технических, функциональных, алгоритмических и организационных решений существенно усложняла разработку и внедрение систем управления и организацию их совместного функционирования, что в конечном итоге снижало общий экономический эффект от функционирования АСУ на предприятии 2. Проблемы, указанные в цитате двадцать лег назад, во многом отражают современное состояние по внедрению интегрированных систем управления вообще и, в частности, ИАСУ газодобывающим производством. Необходимость единого системного подхода к организации газодобычи, осознается сегодня и руководителями Газпрома и предприятий разработчиков АСУ , . Очевидно, что автоматизированный технологический комплекс АТК газодобычи ГД, является многоуровневой сложной системой СС, сложность которой, выражается в многокомпоненгности и иерархичности ее структуры, многофункциональности систем и разнородности ее объектов, наличии горизонтальных и вертикальных связей между составляющими. Оптимальная организация подобной СС на основе современных методов прогнозирования, системного анализа, исследования операций, невозможна без разработки и применения эффективных вычислительных технологий.