Институт вычислительной математики и математической геофизики СО РАН

Тезисы докладов

В работе рассматривается известная $NP$-трудная задача упаковки прямоугольных предметов без поворотов и пересечений в прямоугольник минимальной площади. При решении таких задач важную роль играют кодировки решений. В данной работе использовались две кодировки: $TSG$ представляющая допустимую упаковку в виде двух транзитивно-замкнутых орграфов и $PC$, которая при помощи двух интервальных графов задает множество эквивалентных друг другу допустимых упаковок. Первая кодировка удобна для методов локального поиска. Вторая кодировка дает широкие возможности для операторов скрещивания. На основе кодировки $PC$ разработан новый оператор скрещивания двух упаковок, который использовался в генетическом алгоритме для обновления популяции. Результатом скрещивания является допустимая упаковка, которая используется как начальное решение для методов локального спуска. Проведено исследование эффективности различных стратегий спуска для трех окрестностей: смена ориентации дуги, перенос дуги из одного графа в другой и смена расположения двух предметов в вершинах графов. Алгоритм запрограммирован на языке ПАСКАЛЬ (Delphi6.0) и тестировался на примерах из электронной библиотеки GSRC. Результаты расчетов свидетельствуют о высокой эффективности нового генетического алгоритма.

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

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 2005, Институт Вычислительной Математики и Математической Геофизики СО РАН, Новосибирск
© 2005, Сибирское отделение Российской академии наук, Новосибирск
Администратор страницы: sojconf@sscc.ru