Применение генетического алгоритма с регуляцией вероятностей генетических операторов при решении задачи упаковки в контейнеры

 Аннотация

Описано решение частной задачи одномерной упаковки в контейнеры генетическим алгоритмом с регуляцией вероятностей генетических операторов. Проводится статистическое сравнение указанного алгоритма с простым генетическим алгоритмом.

  Введение

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

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

FF(I)<=17/10*OPT(I)+2

Дальнейшие попытки получить приближенные алгоритмы с более высокими оценками не привели к существенным результатам [3 – 7]. Не удалось превысить оценку алгоритма RFF [3, 4]:

RFF(I)<=5/3*OPT(I)+5

Для повышения качества решения применяются методы комбинаторной оптимизации, обладающие механизмами выхода из локальных экстремумов и способные находить близкие к оптимальному решения. Перспективными в этом смысле являются алгоритмы, основанные на методе имитации отжига и генетические алгоритмы (ГА). ГА позволяют получать близкие к оптимальному решения значительно быстрее, чем метод отжига [8]. Это происходит за счет сочетания в них элементов случайного и направленного поиска. Существует несколько ГА одномерной упаковки [9 – 11].

  Постановка задачи

 Задано конечное множество предметов P = { p₁ , p₂ , ... , p_n } и множество размеров { } i S = s( p _i) , где i=0, s( p _i) 1, i = 1, n Требуется найти такое разбиение множества P на непересекающиеся множества P ₁, P ₂, ... , P_m , чтобы сумма размеров предметов в каждом множестве P_i была меньше 1, а m – наименьшем. Считается, что все предметы из множества P_i упаковываются в один контейнер размером 1. Задача состоит в упаковке всех предметов из множества P в наименьшее количество контейнеров.

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

s(p_i)=i/n, n-четное

 При таком разбиении всегда найдется пара предметов, суммарный объем которых будет равен 1. Очевидно, тогда точное решение будет следующим:

P₁ ={p₁, p_n-1 }, P₂ {p₂ , p_n-2 }, …, P_i {p_i, p_n-i }, … , P_n/2 = { P _n}.
Число использованных при этом контейнеров будет m =n/2 [12].

  Решение задачи

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

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

P_k(z)=-z/ V+1,  (1)
где V – максимальное число эпох без изменения наилучшей приспособленности, при достижении которого происходит останов алгоритма.

 Вероятность мутации определяется следующем выражением [13]:

P_m(z)=z/ V,  (2)

 Другим отличием ГА с РВГО от ПГА является отсутствие оператора инверсии, его функцию внесения нового генетического материала в популяцию выполняет оператор мутации при высоких значениях вероятности мутации. Чтобы предупредить разрушение накопленного на протяжении многих эпох генетического материала, вероятность мутации остается низкой в фазе спуска к экстремуму, когда наилучшая приспособленность популяции растет с каждой эпохой. Счётчик z будет на каждой эпохе равен 0. Из (1) следует, что вероятность кроссинговера будет равна 1, из (2) – что вероятность мутации равна 0. В фазе выхода из локального экстремума, значение счётчика z будет расти, что приведет к снижению вероятности кроссинговера и росту вероятности мутации. В этой ситуации с дальнейшим увеличением эпох генетический материал будет обновляться, и, чтобы не произошло ухудшение решения в ГА с РВГО, используется стратегия элитизма.

 Кодирование фенотипа осуществляется по принципу минимальной избыточности: каждый элемент области поиска (в данном случае области всех легальных подмножеств) должен быть представлен минимальным (идеально – одной) числом хромосом, чтобы сократить размер области поиска ГА. Областью поиска в случае задачи одномерной упаковки является множество всех легальных (т. е. не допускающих переполнение какого-либо блока) распределений элементов в блоки.

 В алгоритме использовано линейное кодирование, при котором фенотип представляет собой список элементов, где позиция элемента в списке означает очередь его на размещение в блоках. Элемент размещается в блок, если в блоке есть достаточное для этого место. При переполнении контейнера происходит переход к следующему свободному контейнеру (рис. 1).

 В качестве функции приспособленности используется F=n-m+1/(m-V₂+V₁) (3).

 где 1 V₁ – суммарный размер предметов в контейнере m, V₂ – суммарный размер предметов, находящихся в контейнерах 1, … , m – 1.

 Третье слагаемое введено в функцию приспособленности для устранения проблемы, известной как «golf course problem», когда имеется большая плоскость и на ней одна «лунка» – решение задачи. Отсутствие рельефа приводит к тому, что генетический алгоритм не может найти направление поиска решения [12]. В выражении (3) первая часть функции приспособленности F = n, m может принимать лишь n значений. Это означает, что область определения функции можно разбить на n гиперплоскостей состояний. Для нормального функционирования генетического алгоритма необходима возможность отличать приспособленность как можно большего числа особей.

 

  Статистическое исследование алгоритмов

 Для сравнения основных модификаций ПГА и ГА с РВГО разработано программное обеспечение в среде Delphi 7. Тестируемые алгоритмы 1000 раз решают описанную выше частную задачу одномерной упаковки c n = 32 . Размер популяции – 100 особей. Критерий останова V = 100 эпох. Для ПГА вероятность кроссинговера P_K = 0.9 , вероятность мутации P_М = 0.1 , вероятность инверсии P_И = 0.05 .

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

Таблица 1 – Результаты статистических испытаний

  Выводы

 При решении задачи одномерной упаковки ГА с РВГО выигрывает у ПГА в скорости и в вероятности нахождения глобального экстремума.

  Список использованной литературы

  1. Brown A. R. Optimal Packing and Depletion // American Elsevier. New York, 1971.
  2. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.: Мир, 1982. – 416 с.
  3. Yao A. C. New algorithms for bin packing. Report N. STAN-CS-78-662 // Computer Science Dept. Stanford. CA: Stanford University, 1978.
  4. Chi-Chin Yao. A new algorithm for bin packing // J. of the ACM. V. 27. №. 2, 1980.
  5. Johnson D. S., Demers A., Ullmans J. D. Worts-case performance bounds for simple onedimensional packing algorithms // SIAM J. Comput., V. 3. №. 4. 1974.
  6. Kao C.-Y., Lin F.-T. A statistic approach for the one-dimensional bin-packing problems / In Proceedings of the 1992 IEEE International Conference on Systems, Man and Cybernetics, V. 2. P. 1545 – 1551. Chicago. IL, 1992.
  7. Resource constrained scheduling as generalized bin packing / M. R. Garey, R. L. Graham, D. S. Johnson, A. C. Yao // J. Combinatorial Theory Ser. A21. P. 257 – 298.
  8. Goldberg D. E. Genetic Algorithms in Search, Optimization and Machine Larning. Addison-Wesley Publishing Company Inc., 1989. – 354 p.
  9. Falkenauer E., Delchambre A. A Genetic Algorithm for Bin Packing and Time Balancing / In Proc. of the IEEE 1992 International Conference on Robotics and Automation (RA92). Nice, 1992.
  10. Kroger B. Genetic algorithms for bin packing problems // In Stender J. (Ed.) Parallel Genetic Algorithms. Amsterdam: IOS Press, 1993.
  11. Goodman E. D., Tetelbaum A. Y., Kureichik V. M. Genetic Algorithm Approach to Compaction, Bin Packing and Nesting Problems. Technical Report № 940502, MSU. East lansing. USA, 1994.
  12. Применение распределённого генетического алгоритма при решении задачи об упаковке в контейнеры / Ю. А. Бюргер, В. Й. Гнатюк, В. И. Литвиненко, А. А. Ткачук // Перспективные информационные технологии и интеллектуальные системы, 2003.
  13. Петров Ю. Ю. Регуляция вероятностей кроссинговера и мутации / Инфотелекоммуникационные технологии в науке, производстве и образовании // Первая международная научно-техническая конференция. Ставрополь: СевКавГТУ, 2004.