Помощь студентам в учебе
Двухуровневое моделирование дискретных эволюционных процессов в условиях неопределенности
|
ВВЕДЕНИЕ 5
ГЛАВА 1. СОДЕРЖАТЕЛЬНАЯ ФОРМУЛИРОВКА ИССЛЕДУЕМЫХ ЗАДАЧ ЗЕМЛЕПОЛЬЗОВАНИЯ В КОНТЕКСТЕ 2-УРОВНЕВОГО МОДЕЛИРОВАНИЯ 25
1.1. Актуальность 2-уровневого моделирования 25
1.1.1. Фундаментальная научная проблема 25
1.1.2. Предлагаемые методы и подходы 26
1.1.3. Современное состояние науки в данной области исследования 28
1.2. Содержательное описание проблемы моделирования задач землепользования 29
1.3. Необходимость многокритериального подхода 32
ГЛАВА 2. КЛЕТОЧНО-АВТОМАТНАЯ ПРОГНОЗНАЯ МОДЕЛЬ ДЛЯ НИЖНЕГО УРОВНЯ 38
2.1. Необходимость разработки новых методов прогнозирования 38
2.2. Алгоритм R/S- анализа 40
2.3. Содержательная и качественная интерпретация результатов работы алгоритма R/S- анализа 41
2.4. Фрактальный анализ временного ряда озимой пшеницы по КБР
за период с 1952 по 2002 г 45
2.5. Инструментарий фазовых портретов для выявления циклов временного ряда и уточнения прогноза 49
2.6. Математический инструментарий линейных клеточных автоматов 55
2.7. Прогнозная модель урожайности на базе клеточных автоматов и нечетких множеств, на примере анализа и прогнозирования урожайности озимой пшеницы по КБР на 2003 год 57
2.7.1. Преобразование числового временного ряда в лингвистический временной ряд 57
2.7.2. Частотный анализ памяти лингвистического временного ряда 61
2.7.3. Получение лингвистических прогнозных значений урожайности, верификация и валидация прогнозной модели 72
2.7.4. Получение числового прогноза, и оценка его точности 76
ГЛАВА 3. ТЕОРЕТИКО-ГРАФОВЫЕ МОДЕЛИ ЗАДАЧ ЗЕМЛЕПОЛЬЗОВАНИЯ С НЕЧЕТКИМИ ДАННЫМИ 79
3.1. Общая постановка дискретной многокритериальной задачи в условиях неопределенности 79
3.2. Математическая постановка векторной задачи покрытия графа 4-циклами (паросочетаниями, звездами) 81
3.3. Анализ арифметических операций и отношения предпочтения
83
для задач с нечеткими данными
3.4. Новые определения операции суммирования и сравнения, адекватные математической модели задачи землепользования с нечеткими данными 87
3.4.1. Математическая постановка задачи 87
3.4.2. Новая операция суммирования Ф нечетких весов 89
3.4.3. Операция сравнения нечетких весов 95
ГЛАВА 4. ЗАДАЧИ ВЕРХНЕГО УРОВНЯ. ИССЛЕДОВАНИЕ ВЫЧИСИТЕЛЬНОЙ СЛОЖНОСТИ, РАЗРЕШИМОСТИ С ПОМОЩЬЮ АЛГОРИТМОВ ЛИНЕЙ¬НОЙ СВЕРТКИ И АЛГОРТИМЫ ЛИНЕЙНОЙ СВЕРТКИ ДЛЯ ЗАДАЧ ПОКРЫТИЯ ГРАФА 4- 100 ЦИКЛАМИ
4.1. Формулировка интервальной экстремальной задачи 101
4.2. Аппроксимация интервальной задачи покрытия графа 4-циклами векторной задачей 103
4.3. Исследование разрешимости с помощью алгоритмов линейной свертки критериев задачи с интервальными данными и критериями вида MAXSUM 105
4.4. Обоснование свойства полноты задачи покрытия графа 4¬циклами
4.5. Исследование вычислительной сложности 119
4.6. Оценки точности приближенных алгоритмов 126
4.7. Приближенный алгоритм покрытия графа 4-циклами 127
4.8. Обоснование достаточных условий статистической эффективности алгоритма а
ЗАКЛЮЧЕНИЕ 134
ЛИТЕРАТУРА 136
ПРИЛОЖЕНИЯ
ГЛАВА 1. СОДЕРЖАТЕЛЬНАЯ ФОРМУЛИРОВКА ИССЛЕДУЕМЫХ ЗАДАЧ ЗЕМЛЕПОЛЬЗОВАНИЯ В КОНТЕКСТЕ 2-УРОВНЕВОГО МОДЕЛИРОВАНИЯ 25
1.1. Актуальность 2-уровневого моделирования 25
1.1.1. Фундаментальная научная проблема 25
1.1.2. Предлагаемые методы и подходы 26
1.1.3. Современное состояние науки в данной области исследования 28
1.2. Содержательное описание проблемы моделирования задач землепользования 29
1.3. Необходимость многокритериального подхода 32
ГЛАВА 2. КЛЕТОЧНО-АВТОМАТНАЯ ПРОГНОЗНАЯ МОДЕЛЬ ДЛЯ НИЖНЕГО УРОВНЯ 38
2.1. Необходимость разработки новых методов прогнозирования 38
2.2. Алгоритм R/S- анализа 40
2.3. Содержательная и качественная интерпретация результатов работы алгоритма R/S- анализа 41
2.4. Фрактальный анализ временного ряда озимой пшеницы по КБР
за период с 1952 по 2002 г 45
2.5. Инструментарий фазовых портретов для выявления циклов временного ряда и уточнения прогноза 49
2.6. Математический инструментарий линейных клеточных автоматов 55
2.7. Прогнозная модель урожайности на базе клеточных автоматов и нечетких множеств, на примере анализа и прогнозирования урожайности озимой пшеницы по КБР на 2003 год 57
2.7.1. Преобразование числового временного ряда в лингвистический временной ряд 57
2.7.2. Частотный анализ памяти лингвистического временного ряда 61
2.7.3. Получение лингвистических прогнозных значений урожайности, верификация и валидация прогнозной модели 72
2.7.4. Получение числового прогноза, и оценка его точности 76
ГЛАВА 3. ТЕОРЕТИКО-ГРАФОВЫЕ МОДЕЛИ ЗАДАЧ ЗЕМЛЕПОЛЬЗОВАНИЯ С НЕЧЕТКИМИ ДАННЫМИ 79
3.1. Общая постановка дискретной многокритериальной задачи в условиях неопределенности 79
3.2. Математическая постановка векторной задачи покрытия графа 4-циклами (паросочетаниями, звездами) 81
3.3. Анализ арифметических операций и отношения предпочтения
83
для задач с нечеткими данными
3.4. Новые определения операции суммирования и сравнения, адекватные математической модели задачи землепользования с нечеткими данными 87
3.4.1. Математическая постановка задачи 87
3.4.2. Новая операция суммирования Ф нечетких весов 89
3.4.3. Операция сравнения нечетких весов 95
ГЛАВА 4. ЗАДАЧИ ВЕРХНЕГО УРОВНЯ. ИССЛЕДОВАНИЕ ВЫЧИСИТЕЛЬНОЙ СЛОЖНОСТИ, РАЗРЕШИМОСТИ С ПОМОЩЬЮ АЛГОРИТМОВ ЛИНЕЙ¬НОЙ СВЕРТКИ И АЛГОРТИМЫ ЛИНЕЙНОЙ СВЕРТКИ ДЛЯ ЗАДАЧ ПОКРЫТИЯ ГРАФА 4- 100 ЦИКЛАМИ
4.1. Формулировка интервальной экстремальной задачи 101
4.2. Аппроксимация интервальной задачи покрытия графа 4-циклами векторной задачей 103
4.3. Исследование разрешимости с помощью алгоритмов линейной свертки критериев задачи с интервальными данными и критериями вида MAXSUM 105
4.4. Обоснование свойства полноты задачи покрытия графа 4¬циклами
4.5. Исследование вычислительной сложности 119
4.6. Оценки точности приближенных алгоритмов 126
4.7. Приближенный алгоритм покрытия графа 4-циклами 127
4.8. Обоснование достаточных условий статистической эффективности алгоритма а
ЗАКЛЮЧЕНИЕ 134
ЛИТЕРАТУРА 136
ПРИЛОЖЕНИЯ
Актуальность проблемы. Диссертационная работа посвящена разработке методов математического моделирования дискретных слабо структурированных процессов, для которых характерны множественность критериев, стохастичность, интервальность или нечеткость значений исходных данных. Дальнейшее развитие каждого такого процесса существенным образом зависит от его состояния на предыдущих этапах эволюционирования.
Как часть этой проблемы в настоящей работе рассматриваются различные постановки задачи землепользования и предлагается двухуровневый подход к их моделированию. Классический подход к моделированию таких задач оказывается недостаточным по той причине, что представление пара¬метров этих задач четкими числовыми значениями оказывается в принципе неадекватным в силу их слабой структурированности, изменчивости во времени и неопределенности. Например, для выращиваемой в зоне рискового земледелия конкретной культуры можно отнести к неадекватному такое представление ее урожайности, как усреднение ее значения за определенный отрезок времени.
Авторская концепция двухуровневого моделирования задач землепользования состоит в том, что исходные данные для многокритериальных задач верхнего уровня должны базироваться на прогнозных данных, получаемых на нижнем уровне моделирования. В свою очередь исходными данными для нижнего уровня служат временные ряды, отражающие эволюцию основных показателей рассматриваемых процессов. Однако к настоящему времени математическое моделирование на нижнем уровне исходных данных (т.е. численных значений параметров, коэффициентов и т.п.) для классических оптимизационных моделей верхнего уровня находится еще в зачаточном состоянии. Вместе с тем уже появилась ясность того, что наиболее подходящим математическим аппаратом для моделирования задач верхнего уровня является инструментарий теории графов. При этом заслуживает внимания тот факт, что к настоящему времени отсутствуют достаточно эффективные, имеющие полиномиальную трудоемкость, алгоритмы практически для всех дискретных экстремальных задач. Поэтому актуальной является разработка малотрудоемких приближенных алгоритмов, которые всегда или почти всегда гарантируют нахождение приемлемых решений.
Цель и задачи диссертационного исследования. Основной целью на¬стоящей работы является разработка (на содержательном примере задач землепользования) двухуровневого подхода к математическому моделированию дискретных эволюционных процессов, числовые параметры которых являются слабо структурированными. Поставленная цель требует решения следующих задач:
- разработка общей структурной схемы двухуровневого моделирования и численных методов его реализации;
- разработка в качестве основной составляющей модели нижнего уровня новых методов прогнозирования эволюционных процессов на базе линейных клеточных автоматов, математического аппарата теории нечетких множеств и инструментария теории детерминированного хаоса;
- осуществление анализа известных теоретико-множественных определений операции суммирования нечетких множеств и вместе с тем представление нового обоснованного определения операций суммирования и сравнения нечетких весов для исследуемой задачи землепользования;
- исследование вычислительной сложности рассматриваемых задач на графах с нечеткими или интервально заданными весами ребер, представляющими урожайность;
- исследование разрешимости с помощью классических подходов (в частности, алгоритмов линейной свертки критериев) рассматриваемых экстремальных задач на графах с интервальными весами;
- разработка малотрудоемких алгоритмов для экстремальных задач покрытия графа типовыми подграфами (паросочетаниями, звездами, 4- циклами) и обоснование достаточных условий статистической эффективности предлагаемых алгоритмов.
Методы исследования. Для решения поставленных в работе научных задач использованы методы теории алгоритмов с оценками, теории графов, многокритериальной оптимизации, теории вероятностей и математической статистики, теории нечетких множеств и интервального исчисления, методы прогнозирования временных рядов.
Достоверность и обоснованность полученных в диссертационной работе теоретических результатов и формулировок обеспечивается корректным применением аппарата теории графов, математического программирования и теории вычислительной сложности алгоритмов, математической статистики,
математического аппарата нечеткой и интервальной математики, методов теории детерминированного хаоса. Информационную базу исследования составили аналитические и статистические материалы Госкомстата России, в частности по Ставропольскому краю и Кабардино-Балкарской республике (КБР). Эффективность предложенных методов подтверждается верификацией и валидацией результатов, полученных путем проведения численных расчетов.
На защиту выносятся следующие основные положения:
1. Концепция двухуровневого моделирования эволюционных дискретных процессов в условиях многокритериальности и неопределенности данных.
2. Конкретный алгоритм реализации фрактального анализа временных рядов урожайности с целью выявления в них наличия долговременной памяти как предпосылки для построения прогнозной модели.
3. Построенная для нижнего уровня на базе инструментария клеточных автоматов и теории нечетких множеств математическая модель и метод прогнозирования урожайности основных культур, выращиваемых в зонах рискового земледелия.
Как часть этой проблемы в настоящей работе рассматриваются различные постановки задачи землепользования и предлагается двухуровневый подход к их моделированию. Классический подход к моделированию таких задач оказывается недостаточным по той причине, что представление пара¬метров этих задач четкими числовыми значениями оказывается в принципе неадекватным в силу их слабой структурированности, изменчивости во времени и неопределенности. Например, для выращиваемой в зоне рискового земледелия конкретной культуры можно отнести к неадекватному такое представление ее урожайности, как усреднение ее значения за определенный отрезок времени.
Авторская концепция двухуровневого моделирования задач землепользования состоит в том, что исходные данные для многокритериальных задач верхнего уровня должны базироваться на прогнозных данных, получаемых на нижнем уровне моделирования. В свою очередь исходными данными для нижнего уровня служат временные ряды, отражающие эволюцию основных показателей рассматриваемых процессов. Однако к настоящему времени математическое моделирование на нижнем уровне исходных данных (т.е. численных значений параметров, коэффициентов и т.п.) для классических оптимизационных моделей верхнего уровня находится еще в зачаточном состоянии. Вместе с тем уже появилась ясность того, что наиболее подходящим математическим аппаратом для моделирования задач верхнего уровня является инструментарий теории графов. При этом заслуживает внимания тот факт, что к настоящему времени отсутствуют достаточно эффективные, имеющие полиномиальную трудоемкость, алгоритмы практически для всех дискретных экстремальных задач. Поэтому актуальной является разработка малотрудоемких приближенных алгоритмов, которые всегда или почти всегда гарантируют нахождение приемлемых решений.
Цель и задачи диссертационного исследования. Основной целью на¬стоящей работы является разработка (на содержательном примере задач землепользования) двухуровневого подхода к математическому моделированию дискретных эволюционных процессов, числовые параметры которых являются слабо структурированными. Поставленная цель требует решения следующих задач:
- разработка общей структурной схемы двухуровневого моделирования и численных методов его реализации;
- разработка в качестве основной составляющей модели нижнего уровня новых методов прогнозирования эволюционных процессов на базе линейных клеточных автоматов, математического аппарата теории нечетких множеств и инструментария теории детерминированного хаоса;
- осуществление анализа известных теоретико-множественных определений операции суммирования нечетких множеств и вместе с тем представление нового обоснованного определения операций суммирования и сравнения нечетких весов для исследуемой задачи землепользования;
- исследование вычислительной сложности рассматриваемых задач на графах с нечеткими или интервально заданными весами ребер, представляющими урожайность;
- исследование разрешимости с помощью классических подходов (в частности, алгоритмов линейной свертки критериев) рассматриваемых экстремальных задач на графах с интервальными весами;
- разработка малотрудоемких алгоритмов для экстремальных задач покрытия графа типовыми подграфами (паросочетаниями, звездами, 4- циклами) и обоснование достаточных условий статистической эффективности предлагаемых алгоритмов.
Методы исследования. Для решения поставленных в работе научных задач использованы методы теории алгоритмов с оценками, теории графов, многокритериальной оптимизации, теории вероятностей и математической статистики, теории нечетких множеств и интервального исчисления, методы прогнозирования временных рядов.
Достоверность и обоснованность полученных в диссертационной работе теоретических результатов и формулировок обеспечивается корректным применением аппарата теории графов, математического программирования и теории вычислительной сложности алгоритмов, математической статистики,
математического аппарата нечеткой и интервальной математики, методов теории детерминированного хаоса. Информационную базу исследования составили аналитические и статистические материалы Госкомстата России, в частности по Ставропольскому краю и Кабардино-Балкарской республике (КБР). Эффективность предложенных методов подтверждается верификацией и валидацией результатов, полученных путем проведения численных расчетов.
На защиту выносятся следующие основные положения:
1. Концепция двухуровневого моделирования эволюционных дискретных процессов в условиях многокритериальности и неопределенности данных.
2. Конкретный алгоритм реализации фрактального анализа временных рядов урожайности с целью выявления в них наличия долговременной памяти как предпосылки для построения прогнозной модели.
3. Построенная для нижнего уровня на базе инструментария клеточных автоматов и теории нечетких множеств математическая модель и метод прогнозирования урожайности основных культур, выращиваемых в зонах рискового земледелия.
1. Сформулирована автоматическая концепция 2-уровневого моделирования задач землепользования: математическая модель верхнего уровня - это модель теории оптимизации, на базе которой строится и обосновывается наиболее целесообразное управление рассматриваемой системой или процессом; на нижнем уровне осуществляется моделирование исходных данных для модели верхнего уровня; исходными данными для нижнего уровня служат временные ряды, отражающие эволюцию основных показателей рассматриваемых эволюционных процессов и систем; изложена необходимость многокритериального подхода и суть его реализации.
2. На базе инструментария фрактального анализа выявлены такие свойства временных рядов, как долговременная память с оценкой ее глубины, трендоустойчивость, квазицикличность; для обновления этих свойств разработан метод фазового анализа временных рядов; на базе инструментария линейных клеточных автоматов и нечетких множеств разработана новая прогнозная модель, включая ее верификацию, а также алгоритмы валидации и вычисления оценок точности прогнозирования.
3. В качестве конкретной реализации 2-уровневого моделирования представлена математическая постановка экстремальных задач покрытия графа 4-циклами (паросочетаниями, звездами); показана непригодность известных в научной литературе определений операции сложения и сравнения нечетких весов; разработано новое определение операции суммирования и сравнения нечетких весов, которые адекватны рассматриваемым задачам землепользования.
4. Исследована на разрешимость с помощью алгоритмов линейной свертки критериев (АЛСК) векторная задача покрытия графа 4-циклами с интервальными весами; осуществлено ее сведение к 2-критериальной задаче и установлена ее неразрешимость.
5. Разработан малотрудоемкий алгоритм покрытия графа 4-циклами и доказано достаточное условие, при которых он является статистически эффективным.
2. На базе инструментария фрактального анализа выявлены такие свойства временных рядов, как долговременная память с оценкой ее глубины, трендоустойчивость, квазицикличность; для обновления этих свойств разработан метод фазового анализа временных рядов; на базе инструментария линейных клеточных автоматов и нечетких множеств разработана новая прогнозная модель, включая ее верификацию, а также алгоритмы валидации и вычисления оценок точности прогнозирования.
3. В качестве конкретной реализации 2-уровневого моделирования представлена математическая постановка экстремальных задач покрытия графа 4-циклами (паросочетаниями, звездами); показана непригодность известных в научной литературе определений операции сложения и сравнения нечетких весов; разработано новое определение операции суммирования и сравнения нечетких весов, которые адекватны рассматриваемым задачам землепользования.
4. Исследована на разрешимость с помощью алгоритмов линейной свертки критериев (АЛСК) векторная задача покрытия графа 4-циклами с интервальными весами; осуществлено ее сведение к 2-критериальной задаче и установлена ее неразрешимость.
5. Разработан малотрудоемкий алгоритм покрытия графа 4-циклами и доказано достаточное условие, при которых он является статистически эффективным.