Категория
Информатика
Тип
реферат
Страницы
1 стр.
Дата
20.02.2010
Формат файла
.rtf — Rich Text Format (Wordpad)
Архив
18279.zip — 40.68 kb
  • reshenie-zadachi-odnomernoj-upakovki-s-pomoshhju-parallelnogo-geneticheskogo-algo-ritma_18279_1.rtf — 351.06 Kb
  • Readme_docus.me.txt — 125 Bytes
Рейтинг
10  из 10
Оценок
1
Оцените работу
Хорошо  или  Плохо


Текст работы

Решение задачи одномерной упаковки с помощью параллельн о
го генетического алг о ритма
И.В. Мухлаева
Введение
В работе представлен паралелльный генетический алгоритм (ПаГА) для решения зад а
чи одномерной упаковки. В целом эта задача является задачей разбиения множества объе к
тов на непересекающиеся подмножес т ва:
. [1]
В большинстве задач разбиения их решение связано с определенными налагаемыми ограничениями, в противном случае решение будет нелегальным. Вот почему элемент, как правило, не может быть объединен в одно подмножество со всеми возможными
подмнож е ствами
оста ю щихся элементов. Цель разбиения состоит в оптимизации функции стоимости, определенной на множестве всех л е гальных подмножеств.
Задача одномерной упаковки является широко применяемой в качестве модели ра с пределения ресурсов разного рода.
В вычислительной технике это могут быть назначение
заданий на процессоры, локация п а мяти, форматирование таблиц и т.д. Браун [1] приводит дополнительно приложения задачи в индустрии и бизн е се.
Как известно, задача одномерной упаковки является задачей комбинаторной оптим и зации и относится к классу NP-полных [2]. Поэтому для ее решения разрабатываются ра з личные аппроксимационные, эвристические алгоритмы, позволяющие получать приемл



Ваше мнение



CAPTCHA