Информационная система "Конференции"

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

вычислительная математика

Применение алгоритма мультистарт локального поиска при проектировании многопроцессорных вычислительных систем

При проектировании многопроцессорных вычислительных систем (МВС) мы сталкиваемся со смешанной многокритериальной задачей условной оптимизации [1]. При этом очевидны как минимум две группы противоречивых критериев – производительность и стоимость системы. Мощность пространства оптимизации в такой постановке настолько велика, что становится ясно, что никакие переборные алгоритмы не имеют практических перспектив для успешного решения задачи. Следовательно, в дальнейшем необходимо сосредоточиться на разработке эффективных непереборных методов решения таких задач оптимизации. В качестве приемлемого средства решения такой задачи был выбран алгоритм мультистарт локального поиска.

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

Алгоритм показал свою работоспособность, и в настоящее время результаты его работы сравниваются с результатами работы генетического алгоритма на этой же задаче.

Библиографический список

1. Ефимов С.Н., Панфилов И.А., Семенкин Е.С., Терсков В.А. Формализация задач выбора эффективного варианта МВК распределенных систем управления. - Вестник СибГАУ: Сб. науч. тр. / Под. ред. проф. Г.П. Белякова; СибГАУ. – Вып. 4. - Красноярск, 2003, с. 24-31

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

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

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

© 1996-2005, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2005, Сибирское отделение Российской академии наук, Новосибирск