Исследование эволюционных методов решения задач комбинаторной оптимизации

• Автор: Еремеев, Антон Валентинович
• Шифр специальности: 05.13.17
• Научная степень: Докторская
• Год защиты: 2013
• Место защиты: Омск
• Количество страниц: 300 с. : ил.

Оглавление
Введение

1 Постановки задач и схемы эволюционных алгоритмов

1.1 Задачи комбинаторной оптимизации

1.2 Эволюционные алгоритмы

2 Исследование эволюционных алгоритмов с позиций локальной оптимизации

2.1 Генетический алгоритм как метод локального поиска

2.2 Динамика численности особей с высокой приспособленностью в популяции генетического алгоритма

2.3 Сравнение эволюционных алгоритмов с эволюционной стратегией (1 + 1)-ЕЗ

2.4 Статистические оценки числа локальных оптимумов

3 Исследование сложности задачи оптимальной рекомбинации
3.1 Постановка задачи
3.2 Полиномиально разрешимые случаи
3.3 ИР-трудные случаи
4 Построение эволюционных алгоритмов со свойствами динамического программирования
4.1 Формализация метода динамического программирования
4.2 Эволюционные алгоритмы на основе динамического программирования

4.3 Вполне полиномиальная рандомизированная аппроксимаци-
онная схема
5 Применение оптимальной рекомбинации в генетических алгоритмах
5.1 Задана о наименьшем покрытии
5.2 Задача управления поставками продукции
5.3 Задача балансировки автоматизированной производственной линии
Заключение
Литература

Введение
Актуальность темы. Задачи комбинаторной оптимизации находят широкое применение в информатике, технике, экономике, планировании и других областях. В настоящее время в комбинаторной оптимизации интенсивно развивается подход, основанный на бионическом принципе моделирования эволюционных процессов адаптации в живой природе. Эволюционные методы успешно применяются в информационных технологиях проектирования, планирования, управления, распознавания образов и т.д. Этим методам посвящено большое число работ как отечественных авторов (Д.И. Батищев, И.Л. Букатова, Н.Г. Загоруйко, А.Г. Ивахненко, Ю.А. Кочетов, Г.С. Лбов, В.М. Курейчик, И.П. Норенков, Ю.И. Неймарк, Л.А. Рас-тригин, В.Г. Редько, Е.С. Семенкин и др.) [7,8,18,55,74,76,81,84,88,89,95], так и зарубежных (Э. Балаш, Д. Голдберг, Дж. Холланд, И. Реченберг, М. Шоно, П. Витани, М. Воз, И. Вегенер) 1122,132,197,213,266,288,2891.
Несмотря на большое количество результатов, полученных в области комбинаторной оптимизации, потребность в дальнейших исследованиях не уменьшается. Это связано как с постоянным притоком новых задач, так и со сложностью их решения. Многие задачи комбинаторной оптимизации являются NP-трудными, и построение оптимального решения требует значительных временных затрат даже при сравнительно низких размерностях исходных данных. В таких ситуациях возникает необходимость в более глубоком анализе задач с позиций теории вычислительной сложности, позволяющей оценить перспективы разработки алгоритмов с заданными характеристиками (время вычислений, требуемый объем памяти, точность и др.) и в итоге найти подход к решению задачи.
Важное место в комбинаторной оптимизации занимает проблема-

численных за все время работы ДП. Под обработкой состояния в ДП будем понимать итерацию внутреннего цикла, т. е. строки 5 и 6 алгоритма 4.1.
Теорема 4.1. Пусть задача П' разрешима алгоритмом ДП, условия С.1, С.2 выполнены, а обработка состояния в ДП им,еет трудоемкость 0(1). Тогда существует многокритериальный ЭА, где трудоемкость каждого оператора есть 0(1), и ПМА задачи П' вычисляется, в среднем за время 0(ТСРп1о§П/П1ах).
Подобный результат имеет место и в более общем случае, когда время обработки состояния ДП и трудоемкости операторов ЭА полиномиально ограничены. В этом случае верхняя оценка средней трудоемкости многокритериального ЭА отличается от трудоемкости алгоритма динамического программирования на множитель, ограниченный полиномом от длины входных данных и числа состояний ДП.
В разделе 4.3 установлено (теорема 4.2), что для класса задач, удовлетворяющих условиям существования вполне полиномиальной аппрокси-мационной схемы (РРТАБ) Г. Воегингера, на основе многокритериального ЭА может быть построено семейство алгоритмов, являющееся вполне полиномиальной рандомизированной аппроксимационной схемой (РРЯАЗ).
Результаты четвертой главы опубликованы в [35-37,155,156].
Глава 5 посвящена применению оптимальной рекомбинации в ГА.
В разделе 5.1 разработаны и исследованы генетический алгоритм и точный гибридный алгоритм для решения задачи наименьшего покрытия множества (ЗНП). Эта задача имеет следующую постановку. Пусть даны множество М = {1,..., т} и набор его подмножеств МС М, где j Е и = {1,...,те}. Подмножество б С и называется покрытием М, если = М. Каждому Mj приписан вес > 0. Требуется найти покрытие минимального суммарного веса. ЗНП ИР-трудна в сильном смысле и для нее не существовует полиномиального алгоритма, вычисляющего решение, не более чем в константу раз превышающее оптимум, если Р^ИР.