Диссертация (Интервальные методы оптимизации нелинейных детерминированных динамических систем при неполной информации о состоянии и параметрах объекта), страница 8

Решение, полученное с помощью инверсных методовоптимизации, является решением задачи интервальной  -минимизации. Действительно,процедурапостроенияпоследовательностиинвертируемыхинтерваловполностьюудовлетворяет условиям теоремы 1 вследствие того, что она получена путем постоянногодихотомического деления пополам, и при этом выбирается исключительно тот интервал, длякоторого инвертер выработал непустое множество (рис. 1.2). Аналогично по способупостроения множествоудовлетворяет условиям теоремы, т.к.

оно строится за счетрекурсивного применения процедуры бисекции.Теорема 2. Пустьx*  Arg min f ( x) , аxsp* - решение задачи интервальной -минимизации, удовлетворяющее условиям теоремы 1, тогда f ( x* )  f ( p* ) .Доказательство теоремы 2. Для доказательства теоремы требуется показать, чтодля бруса p* одновременно выполняются два неравенства: f ( x* )  f ( p* ) и f ( x* )  f ( p* ) .Докажем выполнение первого неравенства.

Пусть f ( x* )  f ( p* ) , тогда существует p– решение задачи интервальной  -минимизации, такой что f ( x* )  f ( p) . Тогда получаем,что [ f ]( p)  [ f ]( p* ) , что невозможно, так как p* так же является решением задачиинтервальной  -минимизации и при этом p*  Arg min[ f ]( p) , таким образом первоеpнеравенство выполнено.Докажем выполнение второго неравенства. Пусть f ( x* )  f ( p* ) , тогда f ( p* )   ,что невозможно, так как p*   , таким образом второе неравенство выполнено.Так как оба неравенства выполнены, теорема доказана.Следствие из теоремы 2.

В брусе p* , полученном инверсными методамиоптимизации, есть точка x , такая что f ( x)  f ( x* )  ( f ( p* )) .1.3. МЕТАЭВРИСТИЧЕСКИЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧИИНТЕРВАЛЬНОЙ ε-МИНИМИЗАЦИИВ данном разделе разработаны алгоритмы интервальной оптимизации, относящиеся кклассу метаэвристических алгоритмов оптимизации [89].

Целью их создания являетсяупрощение вычислительных процедур и, как следствие, сокращение вычислительных затратбез существенной потери точности.361.3.1. МЕТОД УСРЕДНЕННЫХ КОНЦОВ ПУТЕЙСтратегия поискаВ основе метода усредненных концов путей лежат следующие процедуры:1) построение случайной сетки (представляет собой разбиение бруса s на множество{ni }iN 1 непересекающихся брусов, таких что s Nni на области поиска);i12) выбор случайного бруса из сетки;3) поиск пути до «оптимального» решения (который рассматривается как последнийбрус) по сетке, начинающегося от выбранного бруса. Все последующие брусыдолжны иметь общую сторону с предыдущим интервальным вектором, а нижняяграница значения естественного интервального расширения минимизируемойфункции уменьшаться.Полученный в ходе выполнения описанной процедуры «оптимальный» брусзапоминается.

Процедура повторяется несколько раз. Из полученных брусов берутся ихсредние точки, на основе которых строится новый целевой брус (он рассматривается какнаиболее вероятное, среднее положение завершения пути, начатого из любой области), ккоторому снова применяется описанная ранее процедура. Так повторяется до тех пор, покаомега-характеристика целевого бруса не будет удовлетворять условию точности.АлгоритмШаг 1. Задать s – область поиска,  – параметр точности (отвечает за размер выходногобруса), w – «скорость» уменьшения бруса, pamount – количество точек для построенияслучайной сетки,pattempts – количество повторений, rmax – максимальное количествовозвращений (используется во время поиска пути до «оптимального» решения). Положитьцелевой брус t  s .Шаг 2. Если (t )   – закончить работу алгоритма, вернув брус t , в противном случаеположить множество концов путей  , перейти к шагу 3.Шаг 3.

Случайным образом, используя равномерное распределение, выбрать в целевом брусеpamount точек.Шаг 4. Операция разбиения относительно выбранных случайных точек. Разбить целевойбрус относительно выбранных на шаге 3 точек на множество брусов (так как любой брус посути является n -мерным параллелепипедом, то разбиение можно делать следующимобразом: в каждой точке строятся n гиперплоскостей, каждая из которых параллельна одной37паре сторон данного параллелепипеда; совокупность этих гиперплоскостей и делитисходный брус).Рис. 1.3.

Разбиение бруса случайными точкамиШаг 5. Из полученной сетки выбрать случайный брус p .Шаг 6. Процедура поиска пути от бруса p к «оптимальному» брусу:Шаг 6.1. Создать множество брусовl {ni }i1 , граничащих (имеющих общуюсторону) с брусом p . Задать список брусов, образующих путь, { p} ; количествоповторений r  0 .Шаг 6.2. Если r  rmax , перейти к шагу 6.3, в противном случае перейти к шагу 6.6.Шаг 6.3. Выбрать случайный брус n j .

Если f (n j )  f ( p) ,, удалить его изперейти к шагу 6.4, в противном случае перейти к шагу 6.5.Шаг 6.4. Если n j , то положить r  r  1 , если n j , то добавить n j в.Заменить p на n j и вернуться к шагу 6.1.  , то перейти к шагу 6.3, в противном случае перейти к шагу 6.6.Шаг 6.5. ЕслиШаг 6.6. Поиск пути заканчивается на брусе p , который добавляется в множествоконцов путей. Перейти к шагу 7.Шаг 7. Если в множествесодержится pattempts элементов, перейти к шагу 8, в противномслучае перейти к шагу 3.Шаг 8. Определить вектор m pattemptsmid(e i ) , где e i  . Заменить брус tна брусi 1[m1  w; m1  w]  [mn  w; mn  w]  t , w  w  (t ) / 2 . Перейти к шагу 2.Рекомендации по подбору параметровУменьшение параметра  и увеличение параметров w, pamount , pattempts , rmax приводит кодновременному увеличению точности и времени работы алгоритма.

Обратные действияприводят к общему ускорению, но за счет снижения точности работы алгоритма.38Следует обратить внимание, что на задачах большой размерности не рекомендуетсязадавать большие значения параметра pamount , так как при описанной реализации работыалгоритма это приведет к переполнению памяти компьютера.1.3.2. МЕТОД СТОХАСТИЧЕСКОЙ СЕТКИСтратегия поискаСтратегия данного метода заключается в построении сетки на брусе поискаслучайным образом. Она представляет собой разбиение бруса s на множество {ni }iN 1непересекающихся брусов, таких что s Nni . На каждом элементе сетки ищется значениеi1естественного интервального расширения минимизируемой функции (в этом заключаетсяосновное отличие от метода среднего пути, где значение естественного интервальногорасширения рассматривается не на всех элементах сетки). Такая процедура повторяетсянесколько раз.

В итоге исходная область поиска разбивается на подобласти, каждая изкоторых имеет свой вес, подсчитанный на основе полученных значений естественногоинтервального расширения минимизируемой функции. Из подобластей выбирается самаяперспективная (с большим весом), и алгоритм повторяется уже над ней.АлгоритмШаг 1. Задать s – область поиска,  – параметр точности (отвечает за размер выходногобруса), w – «скорость» уменьшения бруса, pamount – количество точек для построенияслучайной сетки, pattempts – количество повторений.

Положить целевой брус t  s .Шаг 2. Если (t )   – закончить работу алгоритма, вернув брус t , в противном случаеположить a  1 , множество брусов сеткиl { g i }i1  {t} , множество значений весов сетки {vi  0}li 1 , перейти к шагу 3.Шаг 3. Если a  pattempts , то перейти к шагу 4, в противном случае перейти к шагу 18.Шаг 4. Положить величину   f (t ) .Шаг 5.

Случайным образом, используя равномерное распределение, выбрать в целевом брусеpamount точек.Шаг 6. Операция разбиения относительно выбранных случайных точек. Разбить целевойбрус относительно выбранных на шаге 5 точек на множество брусовi {g }li1 (так каклюбой брус по сути является n -мерным параллелепипедом, то разбиение можно делатьследующим образом: в каждой точке строятся n гиперплоскостей, каждая из которых39параллельнаоднойпаресторонданногопараллелепипеда;совокупностьэтихгиперплоскостей и делит исходный брус), где l – число полученных брусов.iШаг 7.

Создать множество {vi  f ( g )}li 1 .Шаг 8. Создать множество {di  0}li 1 .Шаг 8.1. Положить j  1 .Шаг 8.2. Положить k  1 .Шаг 8.3. Если vk  v j  0 , то d j  d j  vk  v j .Шаг 8.4. Положить k  k  1 . Если k  l  1 , то d j  d j    v j* , где j *  Arg max v j , иjперейти к шагу 8.4.

Если k  l  2 , то перейти к шагу 8.5. Если ни одно изпредыдущих условий не выполнено, то перейти к шагу 8.3.Шаг 8.5. Положить j  j  1 . Если j  l  1 , то перейти к шагу 9, в противном случаеперейти к шагу 8.2.Шаг 9. Создать множество брусов  и множество значений  . Положить id  1 .Шаг 10.

Положить j  1 .Шаг 11. Положить k  1 .Шаг 12. Добавить в множествоkg j  g , в множествобрусзначениеlnvid  v j  d k /  d k , положить id  id  1 .k 1Шаг 13. Положить k  k  1 . Если k  l  1 , то перейти к шагу 14, в противном случае – кшагу 12.Шаг 14. Положить j  j  1 .

Если j  l  1 , то перейти к шагу 15, в противном случае - кшагу 12.Шаг 15. Положить интервал m ]  ; [ .Шаг 16. Для каждого из брусов n j выполнить: если f (ni )  m , то положить множества {ni }, {nvi } и m  f (ni ) ; если f (ni )  m , то продолжить перебор; если ни одно из предыдущих условий не выполнено, то добавить ni вположить m  m  f (ni ) .Шаг 17. Положить a  a  1 .

Перейти к шагу 3.40и nvi в,Шаг 18. Положить t  [m1  w; m1  w]  [mn  w; mn  w]  t , m  mid( g i ) , w  v (t ) / 2 ,*i*  Arg max vi , перейти к шагу 2.iРекомендации по подбору параметровУменьшение параметра  и увеличение параметров w, pamount , pattempts приводит кодновременному увеличению точности и времени работы алгоритма. Обратные действияприводят к общему ускорению за счет снижения точности работы алгоритма.Следует обратить внимание, что на задачах большой размерности не рекомендуетсязадавать большие значения параметра pamount , т.к. при описанной реализации работыалгоритма это приведет к переполнению памяти.1.3.3.

МЕТОД ИНТЕРВАЛЬНОГО РАЗБРОСАННОГО ПОИСКАСтратегия поискаВ основе метода интервального разбросанного поиска лежат пять операций: метод генерации разнообразных решений (diversification generation method) –генерирует множество разнообразных решений; метод улучшения решений (improvement method) – преобразование решения внесколько других решений; метод обновления множества элементарных исходов (reference set update method) –обновлениемножестваэлементарныхисходовновымисгенерированнымирешениями; метод генерации подмножеств (subset generation method) – генерация подмножеств измножества элементарных исходов; метод комбинации решений (solution combination method) – преобразованиеподмножества элементарных исходов в несколько комбинированных решений.Метод работает следующим образом: генерируются начальные решения (брусы), изкоторых создается множество элементарных исходов.

Далее начинается итеративная часть(образующая цикл): генерация подмножеств, комбинация решений, улучшение полученныхрешений, обновление множества элементарных исходов. Итерации заканчиваются, когда зацикл множество элементарных исходов не обновилось ни одним новым элементом.41Рис. 1.4. Схема метода интервального разбросанного поискаАлгоритмШаг 1. Задать брус поиска s , параметр точности  (отвечает за размер выходного бруса),размер множества начальных решенийpsize , долю шириныw , размер множестваэлементарных исходов rssize , доля лучших брусов b , размер подмножества subsize , параметрспособа разбиения   0 или   1 .Шаг 2.

Метод генерации разнообразных решений.Шаг2.1.Наполнитьмножествобрусами[m1  w; m1  w]  [mn  w; mn  w]  s, w  w  ( s) / 2 , где mi – случайная точка из i -йкомпоненты бруса s .Шаг 2.2. Отсортироватьпо возрастанию величины f ( pi ) , где pi .Шаг 3. Метод конструирования множества элементарных исходов.b  psizeШаг 3.1. Добавить в множествопервых элементов множества, где psize – размер множестваэлементы убираются из множестваШаг 3.2. Создать множествооставшихся вмножества(  – означает целую часть от числа). Добавленные. {di b psizej 1psize – количествоh ( pi , rs j )}ipsize1 , гдеэлементов, rs j – элементы множествапо убыванию.42.