Курс Алгоритмы оптимизации, основанные на методе проб и ошибок (1121255), страница 7
Текст из файла (страница 7)
Алгоритм с законом понижения температуры T T0ln(1 x ),1 x30также подвержен, хотя и в меньшей степени, возможности “зависания” в локальныхоптимумах. Однако число итераций хоть и существенно меньше, чем при использованиизакона Больцмана, но значительно превышает число итераций алгоритма, использующегозакон Коши при сохранении качества решений.3.3. Модификация закона понижения температуры, позволяющаяускорить выход из локальных оптимумовВ работе [Костенко В.А., Калашников А.В. Исследование различных модификаций алгоритмовимитации отжига для решения задачи построения многопроцессорных расписаний// Дискретные модели втеории управляющих систем.
Труды VII Международной конференции. М.: МАКС Пресс, 2006. - С.179184.] предлагается временно повышать температурупри попадании алгоритма в локальныйоптимум для повышения вероятности выхода из него. В качестве критерия попадания влокальный оптимум, используется количество итераций, в течение которых решение неулучшается.
В работе предложен следующий закон изменения температуры:T min(T0 , f (T0 , x) max(0, ct (k k t ))) , гдеf (T0 , x)- стандартная функция понижения температуры, например функцияБольцмана или Коши,k - количество итераций алгоритма без улучшения решения,kt - количество итераций алгоритма без улучшения решений после которых начинаетсяповышение температуры (этот параметр подбирается таким образом, чтобы ktитераций хватало для нахождения локального оптимума с достаточной точностью),ct - коэффициент, характеризующий скорость увеличения температуры.3.4.
Методы распараллеливания алгоритмов имитации отжигаМногие лучшие решения NP-трудных задач были получены алгоритмами имитацииотжига. Все эти алгоритмы выполнялись на многопроцессорных вычислительныхсистемах. В этом разделе рассмотрим известные методы распараллеливания алгоритмовимитации отжига.3.4.1. Асинхронный параллельный алгоритмДанный метод подробно рассмотрен в работе [Z. J.
Czech. Parallel Simulated Annealing forthe Delivery Problem. // Ninth Euromicro Workshop on Parallel and Distributed Processing. 2001. Mantova Italy. P219-226.]для задачи коммивояжера. Параллельные процессы независимо выполняюталгоритм имитации отжига, стартуя с различных начальных приближений. По окончании31работы алгоритма процессы отсылают наилучшее решение координатору, которыйвыбирает среди них оптимальное. На рисунке 3.2. схематично показана работаасинхронного параллельного алгоритма имитации отжига.Initial_solution1...Initial_solutioni...Initial_solutionnNew_localsolution1New_localsolutioniNew_localsolutionnBest_localsolution1Best_localsolutioniBest_localsolutionnBest_globalsolutionРисунок 3.2. Схема параллельного асинхронного алгоритма.Основными достоинствами данного метода являются простота распараллеливанияна любое число процессоров и низкие требования к среде обмена.
В работе [Z. J. Czech.Parallel Simulated Annealing for the Delivery Problem. // Ninth Euromicro Workshop on Parallel and DistributedProcessing. 2001. Mantova Italy. P 219-226.]показано, что скорость поиска решений и качествополучаемых решений практически не отличаются от классического последовательногоалгоритма.Техника распараллеливания с помощью асинхронного параллельного алгоритмаявляется универсальной и может быть использована для любых приложений алгоритмаимитации отжига.3.4.2. Параллельный алгоритм с синхронизациейВ работах1.Z.
J. Czech. Parallel Simulated Annealing for the Delivery Problem. // Ninth Euromicro Workshop onParallel and Distributed Processing. 2001. Mantova Italy. P 219-226.2.Schmid, M., Schneider, R. Parallel Simulated Annealing Techniques for Scheduling and Mapping DSPApplications onto Multi-DSP Platforms // In Proceedings of the International Conference on SignalProcessing Applications & Technology. 1999. Orlando, U.S.A.: Miller Freeman, Inc.http://citeseer.ist.psu.edu/schmid99parallel.htm.3.J.M.Varanelli. On the Acceleration of Simulated Annealing // PhD thesis, University of Virginia, USA.1996.
P 77-81.324. Low Chinyao, Simulated annealing heuristic for flow shop scheduling problems with unrelated parallelmachines // Computers and operations research. 2005. 32. №8. P 2013-2025.рассматриваются различные подходы к распараллеливанию алгоритма имитации отжига,объединенные общей идей. Параллельные процессы начинают поиск решения с одногоисходного приближения. Через фиксированное число итераций процессы обмениваютсясвоими решениями и корректируют свое текущее приближение.
На рисунке 3.3.схематично показана работа асинхронного параллельного алгоритма имитации отжига.Существуют различные способы обмена полученными решениями и стратегиипринятия решения в качестве текущего.Например:Процесс i посылает процессу i+1 своё текущее решение. Процесс i+1принимает это решение в качестве текущего, если F(Xi) < F(Xi+1). Где F(Xi) –значение целевой функции текущего решения i-ого процесса.Широковещательный обмен решениями. Принятие j-ым процессом решения отi-ого процесса в качестве текущего, если F(Xi) < F(Xj) и i < j.Отправка текущих решений координатору, выбор из них произвольного(возможно с разными вероятностями, в зависимости от значений целевойфункции) и принятие его в качестве текущего всеми процессами.Initial_solution...Initial_solution...Initial_solutionNew_localsolution1New_localsolutioniNew_localsolutionnBest_localsolution1Best_localsolutioniBest_localsolutionnGather bestsolutionsStopconditionyesBestsolutionnoBroadcast bestsolutionРисунок 3.3.
Схема параллельного алгоритма с синхронизацией33Похожая техника распараллеливания рассмотрена в работе [J.C.Gomez. A GeneralInterface for Distributed and Sequential Simulated Annealing [HTML] (http://citeseer.ist.psu.edu/110625.html).].На разных процессорах алгоритм имитации отжига работает при различных температурахи режимах понижения температуры.
Процесс с номером i+1 отвечает за локализациюрешения, полученного процессом с номером i, алгоритм имитации отжига процесса i+1работает при меньшей температуре и более медленном режиме понижения температуры.Если процесс i получает решение Xi лучше, чем текущее решение Xi+1 процесса i+1, торешение Xi принимается в качестве текущего для процесса i+1.Среди достоинств данного подхода стоит отметить хорошую масштабируемость иуниверсальность, из недостатков высокие требования к среде обмена, обусловленныебольшим числом обменов (особенно на начальной стадии работы алгоритма, при высокихтемпературах) и несущественное уменьшение времени работы алгоритма с ростом числапроцессоров.3.4.3.
Алгоритм, основанный на декомпозиции целевой функцииБольшую часть времени алгоритм имитации отжига затрачивает на вычислениецелевой функции. Если целевая функция является декомпозируемой F(x1, x2, … , xi, … , xn)= F(x1) + F(x2) + … + F(xi) + … +F(xn), то возможно параллельное её вычисление на m(m≤n) процессорах.В работах1.R. Azencott, Ed., Simulated Annealing: Parallelization Techniques. New York: John Wiley and Sons.1992. P 47-79.2.S.A. Kravitz and R.A. Rutenbar. Placement by Simulated Annealing on a Multiprocessor // IEEE Trans.CADICS.
1987. №6. P 534-549.3.Stefka Fidanova, Simulated Annealing for Grid Scheduling Problem //. IEEE John Vincent Atanasoff 2006International Symposium on Modern Computing (JVA'06). 2006. P 41-45.рассмотрены задачи, для которых удается существенно повысить скорость работыалгоритма имитации отжига благодаря использованию декомпозиции целевой функции.Одной из таких задач является задача размещения транзисторов на интегральной схеме.Если в качестве целевой функции рассматривать количество перекрывающихсяэлементов, то оно может быть посчитано, как сумма перекрывающихся элементовотдельных участков интегральной схемы.Несомненным достоинством данного метода является практически линейный ростпроизводительности с ростом числа процессоров, тем не менее, возможности помасштабированию ограничены видом целевой функции.
Главным недостатком является34узкая направленность метода, возможность его применения только для задач сдекомпозируемой целевой функцией.3.4.4. Подходы, основанные на декомпозиции пространства решенийВ некоторых случаях возможно разбить все пространство решений на области[D.Janaki Ram, T.H.Sreenivas, K.Ganapathy Subramaniam. Parallel Simulated Annealing Algorithms // Journal ofparallel and distributed computing. 1996. №37.
P 207-212.], [J.Allwright, D.Carpenter. A distributedimplementation of simulated annealing for traveling salesman problem // Parallel Computing. 1989. 3. №9-10. P.335-338.].В таком случае возможна параллельная работа алгоритма имитации отжига вразличных областях. Для каждой конкретной задачи разбиение на области осуществляетсяиндивидуальносучётоминдивидуальныхособенностейпространстваS.Прииспользовании такого способа распараллеливания необходимо обеспечивать полноепокрытие пространства решений непересекающимися областями. Следует позаботитьсяоб изменении операций преобразования расписания таким образом, чтобы полученное наследующем шаге решение не выходило за рамки области. Итоговое решение получаетсякак наилучшее среди решений, полученных во всех областях.На рисунке 3.4.
схематично показана работа параллельного алгоритма имитацииотжига, основанного на декомпозиции пространства решений.Декомпозиция наобластиО1О2ОnОiРаспределениеобластей попроцессамПоискрешения в О1,О2…Поискрешения в Оi,Оi+1…Поискрешения в Оn1, ОnВыборнаилучшегорешения35Рисунок3.4.Схемапараллельногоалгоритма,использующегодекомпозициюпространства решений.К преимуществам данного подхода следует отнести: сужения пространства поискарешений, значительное уменьшение времени работы алгоритма и хорошие возможностипо масштабированию (при увеличении количества процессоров необходимо лишьувеличить количество областей разбиения, или иначе распределять области междупроцессорами). Основным недостатком является узкая направленность подхода (длякаждого приложения алгоритма имитации отжига надо разрабатывать свою схемуразбиения на области и соответствующим образом менять операцию преобразованиятекущего решения).3.5.
Алгоритм имитации отжига для решения задачи построениястатических многопроцессорных расписаний с минимальным временемвыполнения на заданном числе процессоровНапомним, что для построения алгоритма имитации отжига для решенияконкретной задачи условной оптимизации требуется решить следующие задачи:6. Разработать способ представления решения X и операций преобразования текущегорешения.7. Разработать стратегию применения операций преобразования текущего решения:какую операцию применять, к какому элементу X, как его изменять.8. Выбрать закон понижения температуры.9. Определить функционал F ( f ( X ), g i ( X )) , используемый для оценки качестватекущего решения.10.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
