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

Инициализация алгоритма.Шаг 2.1. Инициализация групп.Шаг 2.1.1. Положить P  { pi }   и i  1 .Шаг 2.1.2. Сгенерировать случайную точку m  (m1 , m2 ,..., mn )T , используяравномерный закон распределения на компонентах бруса s .Шаг2.1.3.Используясгенерированнуюточку,создатьбрусpi  [m1  w; m1  w]  ...  [mn  w; mn  w], w  winit  ( s) / 2 .Шаг 2.1.4. Выполнить процедуру восстановления бруса p i относительно брусаs (см. далее).53Шаг 2.1.5. Положить i  i  1 . Если i  N B  N A  NW , то перейти к шагу 2.1.2, впротивном случае – к шагу 2.1.6.Шаг 2.1.6.

Отсортировать множество P  { pi }iNB1  N A  NWпо возрастанию всоответствии с величиной f ( pi ) .NAii NB  N AШаг 2.1.7. Положить Gbest  { gbei st }iNB1  { pi }iNB1 , Gaverage  {gaverage }i 1  { p }i  N B 1 ,iGworst  {gworst}iNW1  { pi }iNBNBNANANW1 .Шаг 2.2. Инициализация коллективного знания.Шаг 2.2.1. Инициализация коллективного знания группы Best . ПоложитьZ B  {zBi }   .Шаг 2.2.2. Инициализация коллективного знания группы Average . ПоложитьZ A  {z iA }   .Шаг 2.2.3. Инициализация коллективного знания группы Worst . Положитьвеличину pri j  1 , где pri j – шанс выбора в i -й компоненте бруса s j -гоподынтервала,т.е.интервалаzij  [ si j 1j·( si ); si ·( si )] ,SpiSpii  1,..., n , j  1,..., Spi .Шаг 2.3. Обновление коллективного знания.Шаг2.3.1.ОбновитьколлективноезнаниегруппыBest спомощьюмножества P .Шаг 2.3.2.

Обновить коллективное знание группы Average с помощьюмножества P .Шаг 2.3.3. Обновить коллективное знание группы Worstс помощьюмножества P .Шаг 3. Положить iter  1 .Шаг 4. Обновление группы Best .Шаг 4.1. Положить i  1 ,iiШаг 4.2. Для бруса gbestс помощью коллективного знания сгенерировать брус gbest.iШаг 4.3.

Сжать брус gbestотносительно ширины wbest 1 n  ( g ij ,best ) .n j 1iiiiШаг 4.4. Если f ( gbestна gbest.)  f ( gbest) , то заменить брус gbest54Шаг 4.5. Положить i  i  1 . Если i  N B , то перейти к шагу 5, в противном случае – кшагу 4.2.Шаг 5. Обновление группы Average .Шаг 5.1. Положить i  1 ,Шаг 5.2. Для брусаigaverageс помощью коллективного знания сгенерироватьiбрус gaverage.1 niШаг 5.3. Сжать брус gaverageотносительно ширины waverage  · ( g ij ,average ) .n j 1iiiiШаг 5.4.

Если f ( gaverageна gaverage.)  f ( gaverage) , то заменить брус gaverageШаг 5.5. Положить i  i  1 . Если i  N A , то перейти к шагу 6, в противном случае – кшагу 5.2.Шаг 6. Обновление группы Worst .Шаг 6.1. Положить i  1 ,iiШаг 6.2. Для бруса gworstс помощью коллективного знания сгенерировать брус gworst.1 niШаг 6.3. Сжать брус gworstотносительно ширины wworst  · ( g ij , worst ) .n j 1iiiiШаг 6.4. Если f ( gworstна gworst.)  f ( gworst) , то заменить брус gworstШаг 6.5. Положить i  i  1 . Если i  NW , то перейти к шагу 7, в противном случае – кшагу 6.2.Шаг 7. Перегруппировка элементов групп Best , Average , Worst .Шаг 7.1. Положить P  { pi }  Gbest  Gaverage  Gworst .Шаг 7.2.

Отсортировать множество P  { pi }iNB1  N A  NW по возрастанию в соответствии свеличиной f ( pi ) .Шаг7.3.ПоложитьGbest  { gbei st }iNB1  { pi }iNB1 ,NAii NB  N AGaverage  {gaverage }i 1  { p }i  N B 1 ,iGworst  {gworst}iNW1  { pi }iNBNBNANANW1 .Шаг 8. Положить P  { pi }iNB1  N A  NW  Gbest  Gaverage  Gworst .Шаг 9. Обновление коллективного знания.Шаг 9.1. Обновить коллективное знание группы Best с помощью множества P .Шаг 9.2. Обновить коллективное знание группы Average с помощью множества P .Шаг 9.3. Обновить коллективное знание группы Worst с помощью множества P .55Шаг 10.

Положить iter  iter  1 . Если iter  N max , то перейти к шагу 11, в противном случае –к шагу 4.1Шаг 11. В качестве ответа вернуть брус p*  gbest.Замечания. В приведенном пошаговом алгоритме используются некоторые операции,подробно описанные ниже.Алгоритм восстановления бруса a относительно бруса b (шаг 2.1.4).Шаг 1. Положить i  1 .Шаг 2.

Если ai  bi , то положить ai  bi , перейти к шагу 3.Шаг 3. Если ai  bi , то положить ai  bi , перейти к шагу 4.Шаг 4. Если ai  bi , то положить ai  bi , перейти к шагу 5.Шаг 5. Если ai > bi , то положить ai  bi , перейти к шагу 6.Шаг 6. Положить i  i  1 . Если i  n , то закончить алгоритм, в противном случае перейти кшагу 2.Алгоритм процедуры сжатия бруса a относительно ширины w (шаги 4.3, 5.3, 6.3).Шаг 1. Найти среднюю точку бруса a : m  (m1 ,..., mn )T  mid(a ) .Шаг2.Используянайденнуюсреднююточку,создатьбрусa  [m1  w; m1  w]  ...

 [mn  w; mn  w], w    w / 2 .Шаг 3. Восстановить полученный брус a относительно бруса a .Шаг 4. Заменить брус a на a .Алгоритм обновления коллективного знания группыBestс помощью множестваP  { pi }iNB1  N A  NW (шаг 3.3.1).Шаг 1. Положить Z B  {z Bi }Ci B1CB  P .Шаг 2. Отсортировать множество Z B по возрастанию в соответствии с величиной f ( z Bi ) .Шаг 3. Удалять из множества Z B случайно выбранные брусы, пока выполнено условиеZ B  CB  CB , где |  | – количество элементов множества.Алгоритм обновления коллективного знания группы Average с помощью множестваP  { pi }iNB1  N A  NW (шаг 3.3.2).Шаг 1.

Положить Z A  {z iA }Ci A1  P .Шаг 2. Отсортировать множество Z A по возрастанию в соответствии с величиной f ( z iA ) .56Шаг 3. Удалять из множества Z A случайно выбранные брусы, пока выполнено условиеZ A  C A , где |  | – количество элементов множества.Алгоритм обновления коллективного знания группы Worstс помощью множестваP  { pi }iNB1  N A  NW (шаг 3.3.3).Шаг 1. Учет хороших брусов.Шаг 1.1.

Положить id  1 .Шаг 1.2. Положить i  1 .Шаг 1.3. Положить j  1 .Шаг 1.4. Если pi  zij   , то положить pri j  pri j ·(1  Wid ) .Шаг 1.5. Положить j  j  1 . Если j  Spi , то перейти к шагу 1.6, в противном случае– к шагу 1.4.Шаг 1.6. Положить i  i  1 . Если i  n , то перейти к шагу 1.7, в противном случае – кшагу 1.3.Шаг 1.7. Положить id  id  1 . Если id  Agood , то перейти к шагу 2, в противномслучае – к шагу 1.2.Шаг 2. Учет плохих брусов.Шаг 2.1.

Положить id  1 .Шаг 2.2. Положить i  1 .Шаг 2.3. Положить j  1 .Шаг 2.4. Если p N B  N A  NW id 1  zij   , то положить pri j  pri j ·(1  Wid ) .Шаг 2.5. Положить j  j  1 . Если j  Spi , то перейти к шагу 2.6, в противном случае– к шагу 2.4.Шаг 2.6. Положить i  i  1 . Если i  n , то перейти к шагу 2.7, в противном случае – кшагу 2.3.Шаг 2.7. Положить id  id  1 . Если id  Agood , то завершить работу, в противномслучае перейти к шагу 2.2.iiАлгоритм генерации бруса gbestдля бруса gbestс помощью коллективного знания группыBest (шаг 4.2).1 niШаг 1.

Найти w  · ( g ij ,best ) и среднюю точку бруса gbest: m  (m1 ,..., mn )T  mid( gbei st ) .n j 157Шаг 2. Найти вектор случайного перемещения  R  (1R ,...,  nR )T  (1·r1B ,..., n ·rnB )T , где  j ,j  1,..., n – случайная величина, равномерно распределенная на интервале [1;1] .Шаг3.НайтивекторсмещениявсторонухорошихбрусовCBi  ( ,...,  )   q j ·(mid( z Bj )  mid( gbest)) .GG1G Tnj 1Шаг 4. Выполнить нормировку вектора сдвига: G  (max{1, max |  Gj | / rjB }) 1· G .j 1,..., nШаг5.НайтивекторCBсмещениявсторонуплохихбрусовi  ( ,...,  )   q j ·(mid( z BCB CB 1 j )  mid( gbest)) .BB1B Tnj 1Шаг 6. Выполнить нормировку вектора сдвига:  B  (max{1, max |  Bj | / rjB }) 1· B .j 1,..., niШаг 7. Создать брус gbest,j -я компонента которого рассчитывается по формуле:[m j  s   B ·w / 2; m j  s   B ·w / 2], s  (1   B   B )· Rj   B · Gj  b · Bj .iiШаг 8.

Выполнить процедуру восстановления бруса gbestотносительно бруса gbest.iiАлгоритм генерации бруса gaverageдля бруса gaverageс помощью коллективного знания группыAverage (шаг 5.2).1 nШаг 1. Найти w  · ( g ij ,average ) и положить T  {t i }   и id  1 .n j 1ii)Шаг 2. Найти среднюю точку бруса gaverage: m  (m1 ,..., mn )T  mid( gaverageШаг3.Используянайденнуюранеесреднююточку,создатьt id  [m1  1·r1A  w; m1  1·r1A  w]  ...

 [mn   n ·rnA  w; mn   n ·rnA  w], w   A·w / 2 ,гдебрусj ,j  1,..., n – случайная величина, равномерно распределенная на интервале [–1;1] .iШаг 4. Выполнить процедуру восстановления бруса t id относительно бруса gaverage.Шаг 5. Добавить брус t id в T и положить id  id  1 . Если id  Amax , то перейти к шагу 3, впротивном случае – к шагу 6.i Arg max d e (mid(t i ), mid( z iA )) , где d e (·,·) – расстояние междуШаг 6. Создать брус gaverageid 1,..., Amaxточками, |·| – количество элементов множества.iiАлгоритм генерации бруса gworstдля бруса gworstс помощью коллективного знания группыWorst (шаг 6.2):Шаг 1.

Положить j  1 .58Шаг 2. Случайным образом выбрать один из интервалов z kj , k  1,..., Sp j , вероятность выбораSp jкоторого вычисляется как pr /  prjk и сгенерировать случайную величину mi , равномерноkjk 1распределенную на нем.Шаг 3. Положить j  j  1 . Если j  n , то перейти к шагу 4, в противном случае – к шагу 2.1 nШаг 4. Найти w  · ( g ij , worst ) .n j 1iШаг 5.

Создать брус gworst [m1  w; m1  w]  ...  [mn  w; mn  w], w  W ·w / 2 .iiШаг 6. Выполнить процедуру восстановления бруса gworstотносительно бруса gworst.Рекомендации по подбору параметровУвеличение численных параметров алгоритма, отвечающих за размеры групп,приводит к повышению точности работы за счет снижения скорости работы. Влияниеостальных параметров сложно формализовать, так как их действие зависит от особенностейоптимизируемой функции.1.3.7. САМООРГАНИЗУЮЩИЙСЯ ИНТЕРВАЛЬНЫЙ АЛГОРИТМ ИМИТАЦИИЭВОЛЮЦИИ КОЛОНИИ БАКТЕРИЙСтратегия поискаПредлагаемый алгоритм является самоорганизующимся интервальным алгоритмомглобальной условной оптимизации. В ходе своей работы он имитирует процесс эволюцииколонии бактерий (каждая бактерия представляется брусом, описывающим область ееобитания), цель которого заключается в обеспечении всем особям колонии наилучшегоместа обитания (чем место лучше, тем меньше нижняя граница естественного интервальногорасширения минимизируемой функции).Каждая бактерия отличается следующими параметрами: способом передвижения; реализованы следующий типы передвижений:o «пирамидальный»59o «зональный»o «звезда» стратегией передвижения (жадная стратегия, когда бактерия перемещается в первуюобласть, которая лучше; умная, когда бактерия выбирает наилучшую из возможныхобластей; цепная стратегия, когда возможно несколько перемещений), параметрами, описывающими возможную область перемещения, текущим направлением движения, областью (местом) обитания, описываемой брусом.Каждая итерация работы алгоритма представляет собой реализацию одногоэволюционного цикла, в процессе которого бактерии колонии находят наилучшее местообитания и, заканчивая свой жизненный цикл, дают потомство (следующее поколениеколонии).В ходе процесса построения новой колонии используются следующий правила: 30% новой популяции составляют абсолютно случайные, заново сгенерированныебактерии, 30% новой популяции составляют бактерии, расположенные в областях обитания,найденных прошлым поколением, 30% новой популяции составляют бактерии, расположенные в той же начальнойточке, что и прошлое поколение, но направление поиска противоположное, 10% новой популяции составляют бактерии, расположенные в наилучшем месте,найденном за все время работы алгоритма.Для оценки места обитания применяется естественной интервальное расширениеминимизируемой функции.