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


Первая Азиатская Международная Школа-семинар
'Проблемы оптимизации сложных систем'

19-26 июня 2005 г., Новосибирск, Россия

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

Вероятностный поиск с запретами для задач двумерной прямоугольной упаковки

Ревякина О.В.

Институт математики им С.Л.Соболева СО РАН (Новосибирск)

В работе рассматривается задача упаковки конечного множества прямоугольных предметов в положительном ортанте двумерной плоскости. Повороты и наложения предметов запрещены. Требуется найти упаковку с минимальной площадью окаймляющего прямоугольника. Для решения данной задачи разработан вероятностный алгоритм поиска с запретами, использующий кодировку решений в виде двух перестановок. Алгоритм использует четыре окрестности квадратичной и кубической мощности. Для каждой из них применяется процедура рандомизации, которая сокращает трудоемкость одного шага и повышает эффективность поиска. Окрестности чередуются, замещая друг друга через определенное число итераций. Начальная упаковка выбирается случайным образом. Для диверсификации поиска применяется процедура зеркального отображения упаковки. Разработанный алгоритм запрограммирован на языке ПАСКАЛЬ (Delphi 6.0) и тестировался на примерах из электронной библиотеки MCNC. Численные эксперименты показали высокую эффективность разработанного алгоритма.

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

Ваши комментарии
Обратная связь
[ICMMG SBRAS]
[Головная страница]
[Конференции]

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