Введение
Глава 1. О концентрации локальных оптимумов 28
1.1. Окрестности 28
1.1.1. Окрестность Ni(S) 29
1.1.2. Окрестность N^S) 31
1.1.3. Окрестность N3(S) 32
1.1.4. Задача о многомерном рюкзаке 37
1.2. Библиотека тестовых задач 38
1.3. Экспериментальные исследования 40
1.3.1 Исследование зависимости числа локальных оптимумов от входных данных задачи 40
1.3.2. Исследование концентрации локальных оптимумов 42
Глава 2. Новые жадные алгоритмы 47
2.1. Метод параллельного составления расписаний 49
2.2. Вероятностные жадные стратегии ...50
2.2.1. Сортировка по временным задержкам 51
2.2.2. Использование решения задачи на узкое место 53
2.2.3. Использование решения задачи о многомерном рюкзаке 55
2.3. Локальные улучшения 55
2.4. Экспериментальные исследования 56
2.4.1. Сравнение жадных стратегий 56
2.4.2. Внесение рандомизации 58
2.4.3. Локальный спуск 59
2.4.4. Сравнение с другими алгоритмами 64
Глава 3. Поиск с запретами и чередованием окрестностей 67
3.1. Окрестности 67
3.2. Общая схема 68
3.2.1. Построение начального решения 68
3.2.2. Вероятностный поиск с запретами 70
3.3. Экспериментальные исследования 72
3.3.1. Эффект чередующихся окрестностей 72
3.3.2. Размер окрестности и ее рандомизация 74
3.3.3. Влияние списка запретов 76
3.3.4. Выбор начального решения 77
3.3.5. Интенсификация поиска 78
3.3.6. Сравнение с другими алгоритмами 80
Глава 4. Эволюционные алгоритмы 83
4.1. Стратегия связывающих путей 85
4.2. Построение связывающего пути 86
4.3. Экспериментальные исследования 88
4.3.1. Свойства оператора скрещивания 88
4.3.2. Выбор порождающей пары 90
4.3.3. Выбор начальной популяции 91
4.3.4. Комбинация с локальным поиском 93
4.3.5. Сравнение алгоритмов локального поиска 95
4.3.6. Сравнение с мировым уровнем 97
Заключение 103
Список литературы 104
Приложение 115
