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

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

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

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

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

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

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

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