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

Пятая азиатская международная школа-семинар "Проблемы оптимизации сложных систем"

Кыргызская Республика, г.Бишкек, база "Эдельвейс" Иссык-Кульского Государственного Университета, 12 - 22 августа.
ВАЖНАЯ ИНФОРМАЦИЯ

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

Алгоритм имитации отжига для задачи о перестановке столбцов 0-1 матрицы

Сивых М.Г.

Новосибирский Государственный Университет (Новосибирск)

Задана 0-1матрица, каждой строке которой приписан неотрицательный вес. Вычислим для каждой строки число столбцов, находящихся между первой и последней единицей в этой строке. Взвешенная сумма этих величин по всем строкам является целевой функцией задачи. Эта величина зависит от перестановки столбцов. В задаче требуется найти такую перестановку, при которой значение целевой функции минимально. Известно, что эта задача является NP-трудной. Для её приближённого решения разработан алгоритм имитации отжига. В алгоритме используется идея чередующихся окрестностей разной мощности. В качестве стартового решения используется решение жадной конструктивной эвристики, что позволяет начинать поиск при малой начальной температуре. Для диверсификации поиска применяется принудительный переход по окрестности 3-Opt в случайно выбранном направлении. Приводятся результаты численных экспериментов на тестовых примерах с известным оптимальным решением. Проводится сравнение с другими метаэвристиками.

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

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

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

© 2009, Институт Вычислительной Математики и Математической Геофизики СО РАН, Новосибирск
© 1996-2009, Сибирское отделение Российской академии наук, Новосибирск
Дата последней модификации: 06-Jul-2012 (11:52:52)