Реферат: Решение задачи одномерной упаковки с помощью параллельного генетического алго-ритма

В алгоритме использован также классический оператор инверсии.

1.5. Параллельный поиск

ПаГА работает следующим образом.

1^о .Формируется начальная популяция, разделенная на три субпопуляции..

2^о .В каждой субпопуляции происходит соответствующий кроссинговер.

3^о . В каждой субпопуляции происходят случайная и направленные мутации и инверсия.

4^о .По истечении 10 поколений происходит кроссинговер между субпопуляциями (соответствующий для каждой).

5^о . Окончание работы при достижении C=1 или предела введенного пользователем числа поколений.

Одним из мотивов разделения ГА является потенциальный рост быстродействия благодаря использованию процессора или многопроцессорной системы для обработки отдельной популяции. Однако, наиболее важным мотивом является то, что после некоторого числа поколений хромосомы в отдельной популяции становятся очень похожими. Разнообразие генетического материала будет потеряно, и рекомбинация в дальнейшем может быть неэффективной. Одним из способов преодоления этой проблемы и является независимая обработка отдельных популяций. Так как ГА включают в себя элементы случайного поиска, независимая эволюция отдельных популяций будет направлять процесс в различные области пространства решений. Если оптимизируемая в каждой субпопуляции функция одна и та же, каждая субпопуляция даст конкурентоспособное, но при этом значительно отличающееся по составу ГМ решение.

Число взаимодействий между популяциями может быть критическим фактором в определениии эффективности параллельного ГА. При наличии большого числа взаимодействий преимущества использования субпопуляций оказываются потерянными, так как хорошие хромосомы из одной субпопуляции быстро попадают в другие субпопуляции, и эволюция недолго остается независимой. Результаты, полученные в исследованиях [13,14] подтверждают это положение.

При определении эффективности ПаГА необходимо учитывать эффекты, произведенные на начальную популяцию операторами кроссинговера, мутации и селекции.

Благодаря применению трех типов кросинговера в каждой из субпопуляций формируется отдельный качественный фрагмент упаковки. Синтез этих фрагментов осуществляется в процессе коммуникации между субпопуляциями, при которой в кроссинговере участвуют лучшие хромосомы.

Таким образом, хорошие свойства субоптимальных решений, полученных в независимых субпопуляциях, наследуются во всей популяции и направляют процесс поиска.

Рассмотрим эффект произведенных генетических операций [8].

Эффект мутации. Обозначим p_m норму случайной мутации, одинаковую для каждого локального ГА. Тогда вероятность того, что схема S порядка n(S) во всей популяции подвергнется случайной мутации, будет равна p_m n(S). В стандартном последовательном ГА вероятность того, что схема выживет, равна: 1- p_m n(S). Таким образом, ПаГА в сравнении с ГА не изменяет эффект случайной мутации. Однако, учитывая, что при случайной мутации точки мутации выбираются случайно, эволюция в отдельных субпопуляциях пойдет разными путями. С ростом нормы мутации эффект, производимый ею в разных популяциях, сближается, но станет одинаковым, лишь если мутация осуществит полный перебор генов в хромосоме, что не допускается.

Эффект кроссинговера. Возьмем случайно выбранную хромосому. Вероятность того, что она подвергнется кроссинговеру, равна p_c . Характеристики потомков этой хромосомы зависят от того, какая хромосома будет выбрана в качестве второго родителя. В субпопуляции размером N у всякого другого индивида есть шансов быть выбранным в качестве второго родителя.

Эффективность ГА определяется нормой выживания схемы. Важно определить, какой эффект на выживаемость схемы имеет выбор индивида для кроссинговера. Вероятность выбора индивида в субпопуляции равна p_c , вероятность выбора индивида в начальной популяции - p_c . Тогда для локального ГА и ПаГА вероятность того, что схема S некоторой длины d(S) выживет после кроссинговера, равна , где L - длина схемы. Норма выживания схемы в ПаГА отличается от нормы выживания схемы в ГА, что определяется распределенной природой селекции и коммуникацией генетической информации. Средний или плохой по качеству для одной субпопуляции индивид может быть хорошим для другой субпопуляции.

2. Статистические исследования

2.1. План экспериментов

С использованием разработанного ПО исследовались следующие зависимости. Зависимость времени работы алгоритма от количества элементов, динамика качества решений в поколениях и зависимости этих показателей от весовых распределений элементов. Исследования проводились с доверительной вероятностью 75%, размер серии эксперимента 33, на IBM 486 DX/2 66.

Для исследования использовались наборы данных по 20, 50, 100, 150, 200 элементов при четырех весовых распределениях; вид весовых распределений элементов представлен ниже.

Вид тестов на 200 элементов.

3.2. Результаты экспериментов

Зависимости времени от числа элементов при разных типах данных (цвет означает соответствующее количество элементов).

Проведенные исследования показали, что зависимость времени от количества элементов при всех распределениях не достигает квадратной степени при размерах задачи до 200 элементов, что доказывает практическую ценность разработанного алгоритма.

Зависимости качества от числа поколений на разных тестах:(в скобках указаны количества элементов, цвет означает число поколений).

Результаты проведенных исследований показывают, что наиболее плотная упаковка при всех количествах элементов достигается при четвертом типе весового распределения. Второе и третье распределения дают приблизительно равные результаты.

3.3. Сравнение с известными результатами

Было проведено сравнеие разработанного ПаГА с простым ГА (ПГА). Результаты сравнения сведены в таблицу. Они показывают, что ПаГА на всех тестах достиг оптимума и, таким образом, имеет значительное превышение качества решения при незначительном превышении затраченного времени.