Исследование применения одноточечного кроссовера при решении неоднородной минимаксной задачи

Размещено на http://www.allbest.ru/

Исследование применения одноточечного кроссовера при решении неоднородной минимаксной задачи

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

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

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

В терминах теории расписаний распределительная задача может быть сформулирована следующим образом. Имеется система обслуживания, состоящая из независимых устройств . На обслуживание поступает конечный поток - множество независимых параллельных заданий (функциональных операторов) . - длительность обслуживания задания устройством , определяется матрицей . Приборы в общем случае не идентичны, задание может быть обслужено любым из устройств, и устройство может обрабатывать одновременно не более одного задания. Необходимо определить такое распределение заданий по устройствам без прерываний, чтобы время выполнения всей совокупности заданий было минимальным. Критерий минимизации времени завершения обслуживания заданий, является минимаксным критерием и определяется в следующем виде: , где - время завершения работы процессора [1, 4].

Для решения поставленной задачи используются различные алгоритмы, позволяющие получить точное или приближенное решение. В данной работе в качестве базового алгоритма для решения неоднородной минимаксной задачи возьмем модифицированную модель Голдберга [2, 3], являющеюся одним из видов моделей генетических алгоритмов (далее ГА). Модифицированная модель Голдберга отличается от классической модели Холланда [5, 6, 7], тем, что использует турнирный отбор особей в новое поколение, который позволяет улучшить результаты работы алгоритма с различными модификациями мутации при одноточечном кроссовере.

Модифицированную модель Голдберга можно описать в виде последовательности следующих шагов:

Шаг 1. Формируется начальное поколение, состоящее из заданного числа особей.

Шаг 2. Турнирный отбор особей и применение ГА операторов кроссовера и мутации с заданной вероятностью для создания нового поколения.

Шаг 3. Проверка условия конца работы алгоритма, которая обычно заключается в неизменности лучшего решения в течение заданного числа поколений. Если проверка прошла неуспешно, то переход на шаг 2.

Шаг 4. Лучшая особь выбирается как найденное решение [8,9,10].

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

Рис. 1. Схема функционирования модифицированной модели Голдберга.

В данной работе для исследования рассматривается классический одноточечный кроссовер, изображенный на рис.2.

Рис. 2. Классический одноточечный кроссовер

В работе [3, 9, 10] были исследованы различные модификации мутаций, из всего спектра которых были выбраны для исследований следующие:

1. Простая мутация. Для выбранной особи A случайно выбирается номер задачи i. Генерируется случайное число z в диапазоне от 1 до количества возможных устройств. Проверяется, что полученное число z не совпадает со значением A[i], если совпадает, то z генерируется заново, иначе A[i] присваивается значение z. Пример простой мутации изображен на рис.3.

Рис. 3 Пример простой мутации

2. Простая мутация с возможным повтором. Аналогична простой мутации, но отличается тем что в данной мутации отсутствует проверка совпадения значения z со значением A[i].

3. Раздельная двухбитная мутация. Выбранной особи A случайно выбирается номер задачи i. Значение A[i] рассматривается как массив из 8 бит. Случайно выбираются два бита значения которых инвертируется. В результате получается новое значение A[i]. Проверка того, на каком устройстве должна исполняться задача A[i], выполняется следующим образом: диапазон значений 0.255 разбивается на равные интервалы, количество которых равно количеству устройств; порядковый номер интервала соответствует номеру устройства; проверяется какому интервалу принадлежит значение A[i]. Пример двухбитной мутации изображен на рис.4.

Рис. 4 Пример раздельной двухбитной мутации

В данной работе рассмотрим зависимость того как влияет вероятность кроссовера (важнейший параметр генетического алгоритма) на точность решения неоднородной минимаксной задачи.

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

Для проведения вычислительного эксперимента было написано программное средство на современном языке программирования C# в среде разработки Microsoft Visual Studio 2017.

Данное программное средство позволяет автоматизировать процесс получения сравнительных характеристик результатов работы генетического алгоритма при различных параметрах.

При проведении вычислительного эксперимента был использован персональный компьютер под управлением Windows 10 Pro x64. В качестве аппаратного обеспечения использовался компьютер со следующей конфигурацией: четырех ядерный процессор Intel Core i7-7700k, 16 гигабайт оперативной памяти формата DDR4. Данная аппаратная система была выбрана в связи с тем, что процессор поддерживает одновременно 8 потоков обработки данных и в связи с этим появляется возможность проводить параллельные вычисления для задач больших размерностей.

Во время проведения вычислительного эксперимента рассматривалась задача со следующими параметрами: 3 устройства, 101 задача, вероятность мутации 100%, количество экспериментов 50. Эксперименты проводились в двух вариантах, при использовании одной элитной особи и без нее. Решение данной задачи стандартными методами является чрезвычайно времязатратным.

Оценивались такие параметры как среднее и минимальное значения, полученные в ходе эксперимента.

Результаты эксперимента при 500 особях и 500 повторах приведены в таблице №1.

Таблица 1. Сравнение полученных результатов при 500 особях и 500 повторов

Результаты эксперимента при 1000 особях и 1000 повторах приведены в таблице №2.

Таблица 2. Сравнение полученных результатов при 1000 особях и 1000 повторов

Результаты эксперимента при 1500 особях и 1500 повторах приведены в таблице №3.

Таблица 3. Сравнение полученных результатов при 1500 особях и 1500 повторов

Таким образом, проанализировав результаты, приведенные в таблицах 1-3, можно сделать несколько выводов:

1) Чем выше вероятность кроссовера, тем более качественными поучаются как средние результаты, так и лучшие решения.

2) Базовые параметры генетического алгоритма (количество особей и количество повторов наилучшего решения) влияют на качество решения при использовании модифицированной модели Голдберга. Чем большие значения они принимают, тем более ближе к оптимуму получаются как средние результаты, так и лучшие решения.

3) При малых значениях кроссовера использование элитной особи дает положительный эффект, но при больших значениях кроссовера результаты практически одинаковы.

Литература

неоднородный минимаксный задача

1.Головкин Б.А. Расчет характеристик и планирование параллельных вычислительных процессов. Москва: Радио и связь, 1983. С. 216.

2.Кобак В.Г., Титов Д.В. Исследование турнирного отбора в генетическом алгоритме для решения однородной минимаксной задачи // Математические методы в технике и технологиях -- ММТТ -- 21: сб. трудов Междунар. науч. конф. -- Саратов. 2008. №.2. С. 12.

3.Кобак В.Г., Поркшеян В.М., Кузин А.П. Использование различных вариантов мутации при решении неоднородной минимаксной задачи модифицированной моделью Голдберга // Научно практический журнал «Аспирант». 2017. №10. С. 26-29.

4.Аль-Хулайди А.А., Чернышев Ю.О. Разработка параллельного алгоритма нахождения оптимального решения транспортной задачи на кластере // Инженерный вестник Дона. 2011. №2. URL: ivdon.ru/ru/magazine/archive/n2y2011/445/.

5.Нетёсов А.С. Эволюционно-генетический подход к решению задач оптимизации. Сравнительный анализ генетических алгоритмов с традиционными методами оптимизации // Инженерный вестник Дона. 2011. №3 URL: ivdon.ru/ru/magazine/archive/n3y2011/459/.

6.Курейчик В. М., Кныш Д. С. Параллельный генетический алгоритм. Модели и проблемы построения // Интегрированные модели и мягкие вычисления в искусственном интеллекте: сб. науч. тр. V Междунар. науч.- практ. конф., Москва: Физматлит, 2009. С. 41-51.

7.Goldberg D. Genetic Algorithms In Search, Optimization, and Machine Learning. USA: Addison-Wesley Publishing Company, Inc., 1989. pp. 28-33.

8.Affenzeller M., Wagner S., Winkler S., Beham A. Genetic Algorithms and Genetic Programming: Modern Concepts and Practical Applications. USA: CRC Press, 2009. P. 364.

9.Каширина И.Л. Введение в эволюционное моделирование. Воронеж, 2007. С. 40.

10.Панченко Т. В. Генетические алгоритмы. Астрахань: Астраханский университет, 2007. С. 87.

Размещено на Allbest.ru