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

И.В. Мухлаева

Введение

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

  .           [1]

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

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

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

              [2].

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

              [3, 4].

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

ГА позволяют получать близкие к оптимальному решения значительно быстрее, чем метод отжига [8]. Это происходит за счет сочетания в них элементов случайного и направленного поиска. ГА работают одновременно с несколькими решениями и синтезируют новые субоптимальные решения на основе свойств достигнутых. ГА обладают механизмами избежания локальных оптимумом за счет элементов случайности.

Разработаны несколько ГА одномерной упаковки [9-11].

Разработка параллельных ГА является перспективной, поскольку распараллеливание процесса поиска позволяет сократить время решения [12].

Известны несколько параллельных генетических алгоритмов [12-14], предназначенных для решения различных оптимизационных задач.

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

Для исследования предложенного алгоритма разработано ПО на языке С++ для IBM PC. Проведены статистические исследования, подтверждающие эффективность ПаГА.

1. Параллельный генетический алгоритм

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

Рассмотрим задачу одномерной упаковки в следующей постановке.

Дано: множество элементов E={e1, e2 , ... , en }, имеющих размеры S(E)={s(e1), s(e2), ... , s(en)}, и множество блоков B={b1, b2, ... , bm}, имеющих размеры S(B)={s(b1), s(b2), ... , s(bm)}.

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

1.2. Функция стоимости

Для работы ГА необходимо определить функцию стоимости, в соответствии с которой будут оцениваться решения. Целью решения определена минимизация площади, занятой размещенными в блоках элементами. Соответственно, необходимо найти способ ее оценки. Будем считать, что в идеальном случае (верхняя оценка) площадь, занятая элементами, равна сумме их размеров:

Площадь, занятая элементами при каждом конкретном размещении, определяется следующим образом:

PS=SB* + Sr ,

где SB* - сумма размеров блоков, занятых элементами, кроме последнего занятого блока, Sr - сумма размеров элементов в последнем блоке. Оценкой решения в таком случае будет коэффициент  Целью решения задачи становится максимизация коэффициента C.

Рекомендуем скачать другие рефераты по теме: класс, скачать реферат бесплатно на тему.





1  2  3  4  5  6 | Следующая страница реферата