Введение
Глава 1. Современное состояние развития алгоритмов автоматической группировки объектов с большим объемом входных данных 14
1.1 Общая постановка задач автоматической группировки объектов и сферы их применения 14
1.2 Основные подходы к решению задач группировки объектов и данных 18
1.3 Задачи автоматической группировки объектов и теория размещения 31
1.4 Эволюционные и иные стратегии глобального поиска 39
1.5 Жадные эвристические процедуры в эволюционных алгоритмах 45
Выводы к Главе 1. 48
Глава 2. Применение жадных эвристических алгоритмов к дискретным задачам автоматической группировки объектов и монотонной псевдобулевой оптимизации
2.1 Постановка задачи автоматической группировки на сети 51
2.2 Известные алгоритмы группировки узлов сети 54
2.3 Алгоритм метода изменяющихся вероятностей 59
2.4 Результаты метода изменяющихся вероятностей, настройка параметров 66
2.5 Сравненительные результаты метода изменяющихся вероятностей 69
2.6 Результаты комбинированных методов 71
2.7 Паралельная версия алгоритма метода изменяющихся вероятностей 76
2.8 Жадная агломеративная эвристическая процедура для задач псевдобулевой оптимизации и некоторые свойства задач размещения 79
2.9 Постановка задачи составления расписаний загрузки производственных мощностей литейно-прокатного и химического производства 85
2.10 Алгоритм с жадной эвристической процедурой для задачи о составлении расписания 92
2.11 Результаты вычислительных экспериментов для задачи о составлении расписания 100
Результаты и выводы к Главе 2. 105
Глава 3. Метод жадных эвристик для непрерывных и дискретных задач автоматической группировки объектов 107
3.1 Общая постановка непрерывных задач автоматической группировки объектов 107
3.2 Известные методы
3.3 Модификация жадной эвристической процедуры – частичное объединенное решение 121
3.4 Дальнейшие модификации жадной эвристики 126
3.5 Вычислительные эксперименты с модификациями жадных эвристик в составе генетического алгоритма 133
3.6 Применение новых модификаций жадных эвристических процедур к дискретным задачам размещения 138
3.7 Детерминированный алгоритм с жадной эвристической процедурой 148
3.8 Адаптивный метод жадных эвристик 153
3.9 Комбинация жадных эвристических алгоритмов с альтернативными алгоритмами локального поиска 160
3.10 Модификации для решения серии задач 165
3.11 Общая схема метода жадных эвристик 168
Результаты и выводы к Главе 3. 175
Глава 4. Алгоритм и система автоматической группировки электрорадиоизделий космического применения по производственным партиям 178
4.1 Общая постановка задачи 178
4.2 Типы испытаний электрорадиоизделий 181
4.3 Особенности комплектации космических аппаратов электрорадиоизделиями зарубежного производства 185
4.4 Проблема создания специальных партий ЭРИ 188
4.5 Методы машинного обучения и анализа данных для задачи автоматической группировки объектов электрорадиоизделий 194
4.6 Проблема сопоставимости точности входных данных и результата 197
4.7 Влияние выбора меры расстояния на оценку состава производственных партий 202
4.8 Способы оценки числа групп и обоснования результатов группировки ЭРИ 204 4.9 Проблема нестабильности испытаний ЭРИ и проверка результатов
автоматической группировки 211
4.10 Экспериментальные исследования 216
4.11 Общая схема метода принятия решений по комплектации электронных узлов КА 222
Заключение к Главе 4 230
Глава 5. Задачи автоматической группировки и размещения со специальными метриками и мерами расстояния 232
5.1 Теория размещения и функции расстояний 233
5.2 Классы функций расстояния 238
5.3 Свойства задачи Вебера с прямоугольной метрикой 247
5.4 Алгоритм для задачи с метрикой лифта 252
5.5 Алгоритм для задачи с метрикой французской столицы (French Metro) 256
5.6 Применение и примеры для моделей размещения с метриками лифта и French metro, оценка вычислительной сложности алгоритмов 263
5.7 Обобщение метрик лифта и французской столицы, алгоритм для множественной задачи Вебера 268
5.8 Алгоритм для простейшей множественной задачи размещения 274
5.9 Задачи размещения с метриками, основанными на угловых расстояниях
5.10 Алгоритм для задачи Вебера с метрикой подъемного крана 284
5.11 Алгоритм для задачи Вебера с метрикой Москвы 290
5.12 Алгоритм для задачи размещения с метрикой британской железной догроги 296
5.13 Задача Вебера с мерой расстояния, включающей минимальную стоимость транспортировки 297
5.14 Задача Вебера на области, ограниченной дугами 310
Выводы к Главе 5 318
Глава 6. Задачи автоматической группировки и размещения с произвольной мерой расстояния 320
6.1 Постановка задач 320
6.2 Существующие методы 323
6.3 Постановка задачи в дискретных координатах 324
6.4 Последовательная реализация алгоритма и его OpenMP-параллелизация 326
6.5 Результаты экспериментов 330
6.6 Практический пример: задача размещения точек доступа беспроводной сети 332
6.7 Математическая модель размещения точек доступа 336
6.8 Настройка параметров модели, результаты 343
Выводы к Главе 6 346
Заключение 348
Список литературы 351
