Содержание к диссертации
Введение
Глава 1. Постановки задач и методы их решения 11
1.1 Формулировки задач и некоторые приложения . 11
1.2 Генетические алгоритмы 17
1.3 Генетический алгоритм для задачи целочисленного линейного программирования 24
1.4 Алгоритм перебора L-классов для задачи целочисленного линейного программирования 26
1.5 Гибридный алгоритм для задачи целочисленного линейного программирования . 30
Глава 2. Генетический и гибридный алгоритмы для задачи о наименьшем покрытии множества 33
2.1 Представление решений и общая схема предлагаемого генетического алгоритма 34
2.2 Основные операторы генетического алгоритма с недвоичным представлением решений 36
2.3 Гибридный алгоритм 42
2.4 Вычислительный эксперимент 46
Глава 3. Приближенные алгоритмы для задачи вершинного покрытия 61
3.1 О сложности решения задачи о вершинном покрытии с априорной оценкой точности 62
3.2 Приближенное решение задачи о вершинном покрытии на графе с плотными весами 67
3.3 Генетический алгоритм для задачи о вершинном покрытии 70
3.4 Вычислительный эксперимент 75
Глава 4. Моделирование и анализ одного эволюционного процесса 83
4.1 Схема алгоритма и некоторые известные результаты . 83
4.2 Описание предлагаемой модели 85
4.3 Оценки доли особей с заданной пригодностью . 87
4.4 Примеры использования модели 95
4.5 Вычислительный эксперимент 99
Заключение 101
Список использованной литературы 103
Приложение 118
- Генетический алгоритм для задачи целочисленного линейного программирования
- Основные операторы генетического алгоритма с недвоичным представлением решений
- Приближенное решение задачи о вершинном покрытии на графе с плотными весами
- Оценки доли особей с заданной пригодностью
Введение к работе
Диссертация посвящена разработке и исследованию генетических алгоритмов для решения задач дискретной оптимизации, а также построению гибридных схем с использованием этих алгоритмов. Модели и методы дискретной оптимизации используются для решения многих задач, возникающих в экономике, информатике, планировании, технике и других областях. Условия дискретности позволяют учесть такие факторы, как наличие альтернатив, фиксированные доплаты, структурные ограничения и т.д.
В настоящее время подход, основанный на использовании эволюционного моделирования, представляет собой интенсивно развивающееся направление дискретной оптимизации. Этот подход охватывает такие вопросы, как поиск приближенных решений, вероятностный анализ сходимости алгоритмов, структура задач и сложность их решения, гибридные алгоритмы, экспериментальные исследования и др. (см., например, [3, 7, 20, 22, 43, 45, 50, 61, 66, 89, 95, 116, 123]).
Важное место в дискретной оптимизации занимает проблематика целочисленного программирования (ЦП), которая включает вопросы, связанные с теорией двойственности, устойчивостью решений, полиэдральным подходом, методами отсечения, ветвей и границ, декомпозиции, множителей Лагранжа, выпуклым и невыпуклым программированием и т.д. [4, 5, 18, 23, 21, 28, 30, 38, 42, 44, 47, 48, 49, 51, 101].
В ряде известных методов решения задач ЦП используется сведение исходной задачи к последовательности задач непрерывной оптимизации. На этом подходе основаны методы отсечения [8, 31, 51, 52], декомпозиции (например, с отсечениями Бендерса [36, 69]), ветвей и границ [38, 51], алгоритмы перебора L-классов [33] и др. Как правило, в этих методах используется релаксация условий целочисленности, позволяющая применять алгоритмы непрерывной оптимизации. Для исследова-
ния свойств задач ЦП, построения и анализа алгоритмов, основанных на релаксации условий целочисленности, А.А.Колоколовым предложен метод регулярных разбиений [31, 32, 33, 34]. С использованием этого подхода введены и исследованы новые классы отсечений, построены оценки числа итераций для ряда известных алгоритмов решения задач ЦП, разработаны новые алгоритмы. В последнее время найдены новые возможности применения данного подхода в вопросах устойчивости задач и алгоритмов [12, 35]. Значительное число результатов получено на основе L-разбиения, в частности, на основе этого разбиения предложен метод перебора L-классов для решения задач ЦП. Особенно продуктивным оказалось применение перебора L- классов в сочетании с эвристическими приближенными алгоритмами [24, 36], и в частности, генетическим алгоритмом (ГА) [89].
Эволюционные алгоритмы, к числу которых относятся генетические алгоритмы [95, 103], эволюционные стратегии [115], алгоритмы оптимизации коллективом адаптирующихся автоматов [43] и др., основаны на принципе моделирования процесса биологической эволюции. Методы эволюционного моделирования успешно применяются при решении задач распознавания образов, предсказания, проектирования сложных систем, систем управления и т.д. (см., например, [6, 7, 20, 22, 50, 95]). При решении задач большой размерности в ЦП хорошо зарекомендовали себя ГА [3, 61, 66, 76, 82, 89, 95, 116]. Характерными особенностями ГА являются групповой поиск с помощью популяции "особей", соответствующих точкам пространства решений, работа с символьным представлением решения, использование случайных операторов. В настоящее время возможности применения генетических алгоритмов в дискретной оптимизации исследованы далеко не полностью. Особенно актуальны вопросы моделирования работы ГА, исследования его поведения на заданном классе задач, использования
ГА в гибридных алгоритмах для поиска точного решения задач ЦП.
Целью данной работы является построение и анализ генетических алгоритмов для решения ряда важных классов задач дискретной оптимизации, разработка гибридных методов, в которых генетические алгоритмы комбинируются с методами перебора L-классов.
В диссертации разработаны генетические алгоритмы для задачи целочисленного линейного программирования (ЦЛП), а также для задач наименьшего покрытия множества (ЗНП) и вершинного покрытия на графе (ЗВП). Предложены гибридные точные алгоритмы на основе ГА и перебора L-классов для общей задачи ЦЛП и задачи наименьшего покрытия множества. Получена новая оценка трудности приближенного решения ЗВП, учитывающая плотность графа. Исследован приближенный алгоритм с гарантированной оценкой точности. Предложена новая модель для анализа ГА, основанного на турнирной селекции и мутации. С использованием данной модели построены оценки доли решений заданного качества в популяции ГА. Проведены экспериментальные исследования рассмотренных алгоритмов.
Диссертация состоит из введения, четырех глав, заключения и приложения. В первой главе приводятся постановки задачи целочисленного линейного программирования, задачи о наименьшем покрытии множества и задачи о вершинном покрытии на графе. Рассматриваемые задачи возникают в экономике, информатике, планировании, технике и других областях, (см., например, [4, 5, 30, 46]).
В частности, ЗНП находит применение при поиске оптимального размещения пунктов обслуживания [40, 117, 125], в проектировании конвейеров на производстве [70, 120], при выборе оптимальных способов доступа к информации в базе данных [77], при составлении расписаний на железной дороге [73], и т.д.
ЗВП возникает при проектировании систем контроля и наблюде-
ния [101], в разработке помехоустойчивых методов передачи информации [99], при составлении непротиворечивых расписаний [101], а также в генетике при построении филогенетического древа [108] и в других областях. Более подробное описание некоторых приложений этих задач излагается в гл.1.
В первой главе также приведен краткий обзор методов эволюционного моделирования и дано описание ГА. Предложен вариант ГА для задачи ЦЛП и гибридный алгоритм для этой задачи, представляющий собой комбинацию ГА и метода перебора L-классов. В предложенной гибридной схеме эти алгоритмы взаимно дополняют друг друга: с помощью ГА получаются приближенные решения, ускоряющие перебор L-классов, а последний предотвращает сходимость ГА к локальным экстремумам. Результаты автора, приведенные в этой главе, опубликованы в работах [14, 17, 83, 87, 88, 89].
Вторая глава посвящена разработке и исследованию генетического и гибридного алгоритмов решения ЗНП. Здесь описываются способы представления решений ЗНП в ГА и предлагается вариант алгоритма, использующего недвоичное представление решений и новый оператор кроссинговера, основанный на поиске оптимальной комбинации генотипов родителей. Используемое недвоичное представление решений рассматривалось, в частности, в работе J.E.Beasley и P.C.Chu [66], где было высказано предположение о его неперспективности. В проведенных нами вычислительных экспериментах на задачах библиотеки OR- Library [65] предложенный ГА с недвоичным представлением показал результаты, не уступающие полученным в работе [66]. В частности, для всех 50 тестовых задач со случайными данными и известным оптимумом при числе переменных от 1000 до 5000 и от 200 до 500 ограничений данным ГА найдены оптимальные решения. Кроме того, для трех случаев классических комбинаторных задач [80, 93] получены ре-
шения, улучшающие известные ранее оценки оптимума. Проведенные эксперименты показали, что предложенный ГА может эффективно применяться как метод нахождения начального приближения для точных алгоритмов, а также для быстрого поиска приближенных решений задач большой размерности.
В предлагаемой в этой главе гибридной схеме генетический алгоритм с недвоичным представлением комбинируется с алгоритмом перебора L-классов, разработанным Л.А.Заозерской для ЗНП [24, 25], и методом лагранжевой релаксации (см. [71, 72]). В данной схеме ГА используется для нахождения начального решения, а с помощью метода лагранжевой релаксации строятся нижние и верхние оценки целевой функции на подзадачах, возникающих в процессе пребора L-классов и на начальном этапе до использования ГА. Основные результаты данной главы приводятся в работах [13, 15, 81, 82, 107].
Третья глава посвящена приближенному решению задачи вершинного покрытия на графе. Здесь получена новая оценка границы NP-трудности приближенного решения ЗВП в зависимости от плотности графа (данный параметр плотности используется, например, в работах [51, 55, 75, 105, 106]). Рассматривается модификация приближенного алгоритма А.З.Зеликовского и M.Karpinski [105], для которой построена оценка точности, зависящая от нового параметра плотности графа с весами.
Далее в этой главе описывается новый вариант ГА для ЗВП, использующий жадную эвристику в качестве оператора кроссинговера и приводятся результаты вычислительного эксперимента, где ГА сравнивается с известными эвристиками на задачах библиотеки DIMACS [104] и некоторых других сериях тестовых примеров. В проведенных экспериментах предложенный нами ГА показал результаты, сравнимые с результатами эвристических алгоритмов [60, 61], разработанных
E.Balas и W.Niehaus: уступая на одних задачах, он находил лучшие решения на других. Результаты третьей главы опубликованы в работах
,* [16, 85, 86].
В последней главе предлагается математическая модель эволюционного процесса, возникающего при работе упрощенного варианта ГА, основанного на операторах мутации и турнирной селекции. С целью исследования ГА в литературе предложено несколько моделей, исполь-зующих аппарат цепей Маркова (см., например, [114, 119, 123, 124]). Основные трудности при практическом применении этих моделей вызваны необходимостью использования априорной информации о значении целевой функции в каждой точке пространства решений и большим числом состояний цепи Маркова. Предлагаемая нами модель, вообще говоря, не является цепью Маркова. В ней используется существенно меньше информации о решениях задачи по сравнению с упомяну-
* тыми моделями и отсутствует быстрый рост числа состояний. С ис-
пользованием данной модели в гл.4 построены оценки доли решений заданного качества в популяции ГА, приведены примеры их использования и сравнение с результатами вычислительного эксперимента. При помощи этих оценок получена нижняя граница вероятности попадания оптимальных решений в популяцию. Результаты четвертой
ф главы приводятся в [13] и [84].
Основные результаты диссертации опубликованы в работах [13,
14, 15, 16, 17, 24, 81, 82, 83, 84, 85, 86, 87, 89, 107] и докладывались
на XXXIV Международной научной студенческой конференции "Сту
дент и научно-технический прогресс" (Новосибирск, 1996), I Междуна
родной конференции по эволюционным вычислениям и их приложени-
*' ям "EvCA 96" (Москва, 1996), X Всероссийской конференции "Мате-
матическое программирование и приложения" (Екатеринбург, 1997), Международной конференции "Проблемы оптимизации и экономиче-
ские приложения" (Омск, 1997), Международной Сибирской конференции по исследованию операций (Новосибирск, 1998), XI международной
ф Байкальской школе-семинаре " Методы оптимизации и их приложения"
(Иркутск, 1998), International Conference on Operations Research "OR 98" (Цюрих, Швейцария, 1998), XI Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 1999), Symposium on Operations Research "SOR 99" (Магдебург, Германия,
jj 1999), 4-th Artificial Evolution Conference "AE 99" (Дункерк, Франция,
1999), а также на семинарах в Институте информационных технологий и прикладной математики СО РАН.
#
*
*
Генетический алгоритм для задачи целочисленного линейного программирования
Эта глава посвящена разработке и исследованию приближенных и точных алгоритмов решения задачи о наименьшем покрытии множе ства с использованием методов эволюционного моделирования и пере бора L-классов. В п. 2.1 описываются некоторые способы представле ния решений ЗНП в генетическом алгоритме и излагается общая схе ма предлагаемого ГА с недвоичным представлением решений. В п. 2.2 приводится описание нового оператора кроссинговера, основанного на поиске оптимальной комбинации генотипов родителей, а также опера тора мутации и эвристик жадного типа, применяемых для локальной корректировки решений. В п. 2.3 описывается гибридный алгоритм для решения ЗНП, который представляет собой комбинацию метода пере бора L-классов, ГА и метода лагранжевой релаксации. Описание вычи слительных экспериментов с предложенными алгоритмами на задачах со случайными данными и на сериях задач, имеющих комбинаторную " постановку приводится в п. 2.4. Используемые в этой главе обозначе ния, относящиеся к генетическому и гибридному алгоритмам, а также к задачам ЦЛП и ЗНП, соответствуют определениям гл. 1. Представление решений и общая схема предлагаемого генетического алгоритма
Достаточно эффективный вариант ГА для ЗНП предложен J.E. Beasley и P.C.Chu в работе [66]. Этот алгоритм использует двоичное представление решений в виде строк из нулей и единиц длины п. Столбец j при этом входит в покрытие х(д), если j-й бит генотипа д равен 1. Сложность использования данного представления связана с возможностью получения недопустимых решений после мутации и кроссинго-вера. Для восстановления допустимости в [66] применяется оператор "исправления", представляющий собой эвристику жадного типа.
Предлагаемый в этой главе ГА использует недвоичное представление решений, благодаря которому обеспечивается допустимость фенотипа х{д) при любом генотипе д. Обозначим через U{ множество номеров столбцов, покрывающих строку і. В ГА с недвоичным представлением (GANP) генотип д состоит из т генов д(1\д$\....,д(т\ причем д Є U{, где і = 1,2,..., m, т.е. каждый ген кодирует один из столбцов, покрывающих соответствующую строку. Генотипу д сопоставляется вектор покрытия х(д), где Xi(g) = 1 при условии, что столбец j представлен хотя бы в одном из генов д. В таком случае нет необходимости в операторе "исправления", однако для эффективной работы ГА требуется оператор локальной корректировки решений, исключающий после кроссинговера и мутации некоторые "лишние" столбцы. С этой целью в предложенном алгоритме используются жадные эвристики, находящие приближенное решение подзадачи наименьшего покрытия строк матрицы А посредством столбцов из множества J{g) = {j\xj(g) — 1}, где (/-полученный после мутации генотип.
Модифицированная особь добавляется в популяцию при условии, что там отсутствуют особи с тем же фенотипом, что и у нее. Гено- типы начальной популяции порождаются независимо, и каждый ген #W равномерно распределен на множестве "перспективных" столбцов Ui(a) С Ui. Здесь Ui(a) вводится по аналогии с подходом, изложенным в [66]. Пусть Wi,i = 1,...,т есть множество из а столбцов с наименьшей стоимостью среди покрывающих строку г. Полагаем ТП но, оно подбирается эмпирически с учетом свойств решаемой задачи. Функцию пригодности Ф(і,д) на итерации t предлагается задавать следующим образом: где l(t) - номер особи, имеющей наибольшую стоимость покрытия в популяции на данной итерации. Отбор родителей реализован по принципу пропорциональной селекции. Операторы кроссинговера, мутации и процедуры локальной корректировки решений Lmin, Grd и DGrd, используемые в предлагаемом алгоритме, будут описаны после общей схемы GANP. Алгоритм GANP Шаг 1. Пока не заполнена начальная популяция выполнять: 1.1. Построить случайным образом генотип д. 1.2. Применить эвристику Lmin для исключения "лишних" столбцов из д. 1.3. Полученную особь добавить в популяцию. Шаг 2. Для t от 1 до tmax выполнять: 2.1. Выбрать генотипы родителей ди, gw с помощью пропорциональной селекции. 2.2. Получить генотип д с помощью кроссинговера из ди и gw. 2.3. Применить к д оператор мутации. 2.4. Подать д на вход эвристик Grd и DGrd. Пусть д - лучший по пригодности генотип из полученных в Grd и DGrd. 2.5. Если в П нет особей с фенотипом х(д ), то заменить генотип с наименьшей пригодностью в П на д . 2.5.1. Иначе заменить генотип с наименьшей пригодностью генотипом д, полученным на шаге 2.3. Условие на шаге 2.5 предназначено для предотвращения преждевременной сходимости популяции к локальным оптимумам. Данная проверка отсутствует при добавлении особей на шагах 1.3 и 2.5.1. Как показал эксперимент, на этих шагах повторение уже имеющихся в популяции решений происходит редко.
Основные операторы генетического алгоритма с недвоичным представлением решений
Достаточно эффективный вариант ГА для ЗНП предложен J.E. Beasley и P.C.Chu в работе [66]. Этот алгоритм использует двоичное представление решений в виде строк из нулей и единиц длины п. Столбец j при этом входит в покрытие х(д), если j-й бит генотипа д равен 1. Сложность использования данного представления связана с возможностью получения недопустимых решений после мутации и кроссинго-вера. Для восстановления допустимости в [66] применяется оператор "исправления", представляющий собой эвристику жадного типа.
Предлагаемый в этой главе ГА использует недвоичное представление решений, благодаря которому обеспечивается допустимость фенотипа х{д) при любом генотипе д. Обозначим через U{ множество номеров столбцов, покрывающих строку і. В ГА с недвоичным представлением (GANP) генотип д состоит из т генов д(1\д$\....,д(т\ причем д Є U{, где і = 1,2,..., m, т.е. каждый ген кодирует один из столбцов, покрывающих соответствующую строку. Генотипу д сопоставляется вектор покрытия х(д), где Xi(g) = 1 при условии, что столбец j представлен хотя бы в одном из генов д. В таком случае нет необходимости в операторе "исправления", однако для эффективной работы ГА требуется оператор локальной корректировки решений, исключающий после кроссинговера и мутации некоторые "лишние" столбцы. С этой целью в предложенном алгоритме используются жадные эвристики, находящие приближенное решение подзадачи наименьшего покрытия строк матрицы А посредством столбцов из множества J{g) = {j\xj(g) — 1}, где (/-полученный после мутации генотип.
Модифицированная особь добавляется в популяцию при условии, что там отсутствуют особи с тем же фенотипом, что и у нее. Гено- типы начальной популяции порождаются независимо, и каждый ген #W равномерно распределен на множестве "перспективных" столбцов Ui(a) С Ui. Здесь Ui(a) вводится по аналогии с подходом, изложенным в [66]. Пусть Wi,i = 1,...,т есть множество из а столбцов с наименьшей стоимостью среди покрывающих строку г. Полагаем но, оно подбирается эмпирически с учетом свойств решаемой задачи. Функцию пригодности Ф(і,д) на итерации t предлагается задавать следующим образом: где l(t) - номер особи, имеющей наибольшую стоимость покрытия в популяции на данной итерации. Отбор родителей реализован по принципу пропорциональной селекции. Операторы кроссинговера, мутации и процедуры локальной корректировки решений Lmin, Grd и DGrd, используемые в предлагаемом алгоритме, будут описаны после общей схемы GANP. Алгоритм GANP Шаг 1. Пока не заполнена начальная популяция выполнять: 1.1. Построить случайным образом генотип д. 1.2. Применить эвристику Lmin для исключения "лишних" столбцов из д. 1.3. Полученную особь добавить в популяцию. Шаг 2. Для t от 1 до tmax выполнять: 2.1. Выбрать генотипы родителей ди, gw с помощью пропорциональной селекции. 2.2. Получить генотип д с помощью кроссинговера из ди и gw. 2.3. Применить к д оператор мутации. 2.4. Подать д на вход эвристик Grd и DGrd. Пусть д - лучший по пригодности генотип из полученных в Grd и DGrd. 2.5. Если в П нет особей с фенотипом х(д ), то заменить генотип с наименьшей пригодностью в П на д . 2.5.1. Иначе заменить генотип с наименьшей пригодностью генотипом д, полученным на шаге 2.3. Условие на шаге 2.5 предназначено для предотвращения преждевременной сходимости популяции к локальным оптимумам. Данная проверка отсутствует при добавлении особей на шагах 1.3 и 2.5.1. Как показал эксперимент, на этих шагах повторение уже имеющихся в популяции решений происходит редко. Нами рассматривались два варианта оператора кроссинговера: униформный кроссинговер (см. гл.1) и ЛП-кроссинговер, разработанный автором в [82] для ЗНП. Действие ЛП-кроссинговера основано на решении задачи поиска оптимальной комбинации генотипов родителей, которая решается с использованием методов линейного программирования. Для описания данного оператора сформулируем задачу оптимального кроссинговера (ЗОК), как подзадачу исходной ЗНП. Она состоит в отыскании наименьшего покрытия множества М посредством покрывающих подмножеств с индексами из U = J(gu)U J(gv): найти К ЗОК применяется следующая редукция. Обозначим S = {г Є М : \U{ C\U \ = 1}. Тогда каждая строка с индексом г Є в рассматриваемой подзадаче может быть покрыта единственным столбцом j(i). Пусть Q = {j : j = j(i),i Є S} - множество фиксированных столбцов. Каждому гену д г\ где і Є U Mj, назначается индекс некоторого столбца из Q, покрывающего строку і. Таким образом ЗОК сводится к задаче наименьшего покрытия нефиксированными столбцами всех строк из М\ U Mj. Обозначим редуцированную задачу через ЗОК .
Полученная подзадача может решаться любым точным или приближенным методом, разработанным для ЗНП. Наиболее эффективным из опробованных нами вариантов кроссинговера оказался описываемый ниже оператор, основанный на использовании симплекс-метода.
Рассмотрим линейную релаксацию ЗОК , где условия целочислен-ности заменены неравенствами Xj 0 для всех переменных подзадачи. Данная задача решается с помощью двойственного симплекс-метода. Если полученное решение х1 оказывается целочисленным, то на его основе назначаются оставшиеся неопределенными при редукции гены генотипа д, соответствующие строкам из М\ U Mj. В случае, если ре-шение х содержит дробные компоненты, кроссинговер не выполняется и оператор возвращает в качестве результата копию генотипа одного из родителей.
Необходимо отметить, что в случае дробного решения информация, содержащаяся в оптимальном решении ЛП-релаксации, может быть использована для приближенного решения ЗОК . С этой целью нами была опробована эвристика редуцированных стоимостей, успешно использованная в работе E.Balas и M.C.Carrera [71]. Как показал эксперимент, данная эвристика позволяет улучшить эффективность ГА на задачах относительно небольшой размерности, но не дает устойчивого повышения качества решений на задачах с большим числом переменных и ограничений. Далее в этой главе будет рассматриваться ЛП-кроссинговер, не учитывающий информации о дробных решениях.
С целью предотвращения больших вычислительных затрат поиск оптимума линейной задачи отменяется, если число ограничений в ЗОК превышает порог /J,, или если выполнено более установленного числа v итераций симплекс-метода (в наших экспериментах /г = 150, v = 300). В этих случаях оператор также возвращает копию генотипа одного из родителей.
Приближенное решение задачи о вершинном покрытии на графе с плотными весами
Как показано в [100], для ЗВП не существует полиномиального 6-приближенного алгоритма с 6 7/6 при условии что NP ф Р. С другой стороны, в [63] предложен 2-приближенный алгоритм линейной трудоемкости для этой задачи. Позднее было найдено значительное число полиномиальных алгоритмов с улучшенными оценками точности для различных частных случаев ЗВП (см., например [101]). В частности, выяснилось, что для невзвешенной ЗВП существуют полиномиальные алгоритмы с оценкой точности, зависящей от некоторых параметров плотности графа. Например, при ограничении max y deg(i ) d для ЗВП существует полиномиальный алгоритм [98] с оценкой 2 — щ . С другой стороны, в случае ЗВП на д-плотном графе, т.е. при условии, что для некоторого д Є (0,1) имеет место EVGF deg(v) g\V\2, в [106] предложен полиномиальный » \_ - при-ближенный алгоритм.
Кроме того, в [105, 106] рассмотрен случай, когда G - всюду плотный граф, т.е. степень любой вершины в G не меньше чем s\V\ для некоторого є Є (0,1). На таких графах для невзвешенной ЗВП в [105,106] предложен алгоритм с оценкой точности - - и трудоемкостью 0(1 1 V), который далее будет обозначаться DVC. Как показано в [55], на всюду -плотных графах многие известные iVP-трудные задачи (например, задача о максимальном разрезе) имеют полиномиальные приближенные схемы, т.е. для них за полиномиальное время удается найти приближенное решение с оценкой точности равной 8 при любом 8 1. К сожалению, предложенная в [55] техника оказалась неприменима для ЗВП. Более того, в [75] показано, что даже в случае невзвешенной ЗВП на всюду -плотном графе для любого є Є (0,1) существует такое Д(є) 1, для которого получение Д ( -приближенного решения является NP-трудной задачей. С целью уточнения функции Д(є) в [85] результат из [75] был дополнен новой оценкой из работы [100]. Для получения уточненной оценки нам потребуется рассмотреть вероятностную машину Тьюринга, работа которой описывается следующими определениями (см., например,[56, 68, 75]).
Рассмотрим многоленточную машину Тьюринга, имеющую ленту, где записано входное слово х, а также рабочую ленту, и доступную для чтения оракульную ленту, где содержится булева строка удостоверения 7г. Машина имеет прямой доступ к оракульной ленте. Для этого на рабочей ленте имеется специальный адресный участок, на котором машина записывает адрес ячейки оракульной ленты и читает из строки 7г адресованный бит. Дополним данную машину случайной лентой, на которой к началу работы машины записана строка R, элементы которой равны 0 или 1 с вероятностью 1/2.
Верификатором V будем называть машину Тьюринга указанного вида, которая сначала читает входное слово х и случайную строку R, записывает на рабочей ленте те адреса оракульной ленты, которые будут после этого просмотрены. Затем машина выполняет запросы к оракульной ленте по записанным адресам и на основании прочитанной информации со входной, случайной и оракульной лент, вычисляет принять или отвергнуть данное входное слово х. Время работы верификатора V должно быть полиномиально от длины входа х.
Вероятностью принятия 2 входного слова х называют максимум вероятности того, что верификатор примет х, где максимум взят по всевозможным строкам удостоверения 7Г. Предположим, что а - последовательность бит, прочитанных V с оракульной ленты в процессе вычислений при входе х и случайной строке R. В таком случае, если вычисление заканчивается принятием входа, то тройка (х, R, а) называется принимающей конфигурацией.
Рассмотрим следующий набор условий, устанавливающих дополнительные ограничения на работу верификатора. Будем говорить, что верификатор имеет сложность свободных бит? f, если для любого входа х и любой случайной строки R существует не более 2f возможных принимающих конфигураций (х, Л, а), и множество таких конфигураций (х, R, а) для произвольных х и R вычислимо за полиномиальное от длины входа время.
Для языка L верификатор имеет устойчивость 4 s, если для любого х L вероятность его принятия не превышает s. Будем говорить, что верификатор имеет полноту с, если для любого х Є L вероятность принятия - не меньше с.
Язык L относится к классу FPCPCjS[r(\x\), f], где 0 s c l,f О, если для него существует верификатор со сложностью свободных бит f, устойчивостью s и полнотой с, использующий строку случайных бит длиной 0(г(х)).
Доказательство. По условию леммы для произвольной индивидуальной задачи распознавания выполнимости набора дизъюнкций ф существует верификатор V, отвечающий заданным c,s,f, r(x) = log(x). Для набора дизъюнкций ф и верификатора V рассмотрим граф йф = (Уф, Еф), получивший название FGLSS-графа (см., например, [75, 90]).
Данная конструкция строится следующим образом. Каждой принимающей конфигурации (х, R, а) верификатора сопоставляется вершина множества Уф. Кроме того Уф дополняется при необходимости фиктивными вершинами, для которых не существует ни одной принимающей конфигурации. Число фиктивных вершин выбирается таким образом, чтобы \Уф\ = г 2f, где г = 2(log(lxM - число всевозможных случайных последовательностей, которые могут возникать на случайной ленте. Пара вершин графа Єф, соответствующих принимающим конфигурациям (x,R,a) и (x,R ,a ), соединяется ребром, если не существует такого удостоверения 7г, подстановка которого на оракульную ленту обеспечивала бы чтение в первом случае последовательности а, и во втором случае - последовательности а . То есть, для соединения пары вершин запрашиваемые части удостоверений, подходящих принимающим конфигурациям этих вершин, должны обязательно содержать различающиеся биты. Фиктивной вершине не подходит ни одно удостоверение и она соединяется со всеми остальными вершинами графа.
Оценки доли особей с заданной пригодностью
Этот параграф содержит несколько примеров оптимизационных задач, для которых достаточно просто получить пороговые вероятности перехода оператора мутации. Рассмотрим задачу максимизации числа единиц в булевой строке (без каких-либо ограничений). Несколько вариантов ГА для этой задачи исследовалось в работах [57, 113]. Вполне естественно в качестве генотипа в данном случае выбрать оптимизируемую булеву строку. Обозначим ее длину через п. Предположим, в ГА используется стандартный оператор мутации, изменяющий каждый элемент строки с вероятностью мутации рт. Пусть подмножества Ho,...,Hd определяются линиями уровня Фо = 0, Фі = 1,..., Ф(і = d и d = п. Легко видеть, что в таком случае рассматриваемый оператор мутации является ступенчатым. Матрицу пороговых переходных вероятностей этого оператора легко получить, используя, например, результат из [57], но здесь мы рассмотрим ее как частный случай в рамках более общей постановки задачи.
Предположим, что кодировка решений в ГА такова, что вектор генотипа состоит из d блоков, представляющих собой непересекающиеся участки, и значение функции пригодности Ф( ) равно числу блоков, для которых выполнено некоторое свойство К. Пусть т - число блоков, и К(д,Х) = 1, если свойство К имеет место для блока с номером Л генотипа д; в противном случае К(д,\) = 0.
В качестве примера рассмотрим семейство задач вершинного покрытия графа специального вида, когда граф G состоит из d трех-вершинных полных подграфов, не связанных между собой. Обозначим такой граф через Gd- Очевидно, каждый из треугольных подграфов оптимально покрывается двумя вершинами, а неоптимально - тремя. Несмотря на простоту данной задачи, как показано в [25], некоторые известные алгоритмы типа ветвей и границ имеют экспоненциально возрастающую трудоемкость с увеличением числа вершин графа.
Пусть к ЗВП применяется ГА, использующий недвоичное представление (см. гл.2). В таком случае каждому ребру графа будет сопоставлен ген, указывающий на одну из вершин, соединяемых данным ребром. Предположим, что нулевое значение гена соответствует вершине с меньшим порядковым номером, а значение 1 - вершине с большим номером. Генотипу д соответствует покрытие С(д), куда входят все вершины, на которые указывает хотя бы один из генов д. Пусть оператор мутации с вероятностью рт изменяет значение любого гена.
В качестве функции пригодности для ЗВП естественно выбрать Ф($0 — 1 1 — 1 ( )1- В таком случае значение Ф(д) совпадает с количеством треугольных подграфов, оптимально покрытых вершинами С(д). Пусть гены, соответствующие треугольному подграфу, составляют один блок, а свойство К означает оптимальное покрытие блока. Тогда, рассмотрев всевозможные варианты образования избыточных покрытий треугольного подграфа, нетрудно убедиться в том, (4.24) немедленно получаем все пороговые вероятности перехода данного оператора мутации. Кроме того, как нетрудно проверить, в этом случае неравенство г г также выполняется при любой вероятности мутации рт, и, следовательно, оператор является монотонным.
В этом параграфе приводятся результаты экспериментов в сопоставлении с теоретическими оценками, полученными выше. Здесь рассматривается ГА для ЗВП на графе Gd в том варианте, который был описан в п.4.4. На рис.5 представлены графики пропорции оптимальных генотипов в популяции ГА при различных размерах популяции. Здесь d = 8, Рт = 0.01, s = 2 и z = 0 (последнее условие означает, что начальная популяция состоит из генотипов, где каждый блок задает избыточное покрытие треугольного подграфа).
Результаты вычислительных экспериментов представлены пунктирной линией. Они получены путем усреднения величины zd по 1000 запускам ГА. Сплошные линии соответствуют нижним и верхним теоретическим оценкам, полученным по формулам (4.19) и (4.22). Эти графики показывают, что для данного набора параметров оценка сверху (4.22) близка к экспериментальным значениям величины zd уже при размере популяции около 100. Другие компоненты вектора z на рисунке не представлены, т.к. они показали аналогичную тенденцию. Следующая серия экспериментов проводилась с целью сравнить поведение ГА при различных размерах турнира s. Рис.6 показывает результаты для ГА с параметрами рт = 0.1, N = 100 и z = 0 при решении ЗВП на графе GQ. Как и ранее пунктирная линия здесь изображает усредненные результаты на основе 1000 запусков ГА.
Как видно из рис.6, увеличение размера турнира в данном случае приводит к росту численности особей с оптимальным генотипом, что и следовало ожидать на основании следствия 4.1 из теоремы 4.2.
Предложенная в этой главе модель может применяться для исследования поведения ГА при различных функциях пригодности и операторах мутации. Адекватность модели существенно зависит от точности монотонных оценок пороговых переходных вероятностей для используемого оператора мутации. Данные оценки могут быть получены посредством теоретического анализа взаимосвязи оператора мутации и функции пригодности, либо с помощью статистического оценивания параметров этого оператора для рассматриваемого класса функций.