Метод деформируемого многогранника Нелдера-Мида

Ме­тод Нел­де­ра-Ми­да (J. A. Nelder, R. Mead; 1965 г.) яв­ля­ет­ся раз­ви­ти­ем ши­ро­ко из­ве­ст­но­го сим­п­лекс-ме­то­да, пред­ло­жен­но­го Спенд­ли, Хек­стом и Хим­су­ор­том (W. Spendley, G. R. Hext, F. R. Himsworth) в 1962 г. Рас­смо­т­рим вначале клас­сичес­кий ва­ри­ант ме­то­да.

Сим­п­ле­к­сом в N-мер­ном про­стран­с­т­ве на­зы­ва­ет­ся пра­виль­ный мно­го­гран­ник с N+1 вер­ши­на­ми. На­при­мер, сим­п­лекс на пря­мой — от­ре­зок, на пло­с­ко­сти — пра­виль­ный тре­у­го­ль­ник, в 3-мер­ном про­стран­с­т­ве — те­т­ра­эдр и т. д.

От­прав­ной точкой ал­го­рит­ма яв­ля­ет­ся за­да­ние не­ко­то­ро­го началь­но­го сим­п­ле­к­са в про­стран­с­т­ве N пе­ре­мен­ных. Обоз­начим вер­ши­ны сим­п­ле­к­са x₀, x₁, ¼, x_N. Вычис­лим значения ми­ни­ми­зи­ру­е­мой функ­ции в вер­ши­нах сим­п­ле­к­са и обоз­начим их F₀, F₁, ¼, F_N, со­от­вет­ст­вен­но. Вы­бе­рем наи­боль­шее (худ­шее) из значений F₀, F₁, ¼, F_N; пусть это бу­дет F_h, а со­от­вет­ст­ву­ю­щая вер­ши­на — x_h. Возь­мем грань сим­п­ле­к­са, про­ти­во­ле­жа­щую вер­ши­не x_h, и оп­ре­де­лим ее центр как , т. е. как сред­нюю точку для N вер­шин, при­на­д­ле­жа­щих этой гра­ни. Бу­дем ис­кать точку, лучшую, чем x_h, в на­пра­в­ле­нии от x_h к цен­т­ру про­ти­во­ле­жа­щей гра­ни. Для это­го вы­пол­ним опе­ра­цию от­ра­же­ния, т. е. най­дем точку x_r, зер­каль­но сим­мет­ричную x_h от­но­си­тель­но про­ти­во­ле­жа­щей гра­ни сим­п­ле­к­са. Очевид­но, x_r=x_c+(x_c-x_h). Ес­ли значение функ­ции в но­вой точке F(x_r)<F_h, за­ме­ним вер­ши­ну x_h на x_r и по­лучим но­вый сим­п­лекс, в вер­ши­нах ко­то­ро­го сре­д­нее значение функ­ции улучшилось. Ес­ли же от­ра­же­ние не по­з­во­ля­ет добиться улуч­ше­ния худ­шей вер­ши­ны, то, очевид­но, раз­ме­ры сим­п­ле­к­са слиш­ком ве­ли­ки по срав­не­нию с рас­сто­я­ни­ем до ми­ни­му­ма. В этом случае про­из­во­дит­ся сокращение сим­п­ле­к­са: вер­ши­на x_h со­хра­ня­ет­ся, а ос­таль­ные вер­ши­ны заменяются се­ре­ди­нами ре­бер, со­еди­ня­ю­щих их с x_h, так что рас­сто­я­ния ме­ж­ду все­ми вер­ши­на­ми со­кра­ща­ют­ся в 2 раза. По­с­ле это­го вновь де­ла­ет­ся опе­ра­ция от­ра­же­ния и т. д. По­иск за­канчива­ет­ся, ко­г­да раз­ме­ры сим­п­ле­к­са ста­нут до­с­та­точно ма­лы­ми; в качес­т­ве окончатель­но­го ре­зуль­та­та мо­ж­но при­нять по­с­лед­нюю точ­ку x_c ли­бо центр сим­п­ле­к­са.

Сим­п­лекс-ме­тод Спенд­ли, Хек­ста и Хим­су­ор­та обес­печива­ет ус­тойчивость про­цес­са по­ис­ка и его схо­ди­мость к точке ми­ни­му­ма. Од­на­ко, его не­до­с­тат­ком яв­ля­ет­ся низ­кая ско­рость, так как ве­личина пе­ре­ме­ще­ния на ка­ж­дом ша­ге оп­ре­де­ля­ет­ся те­ку­щим раз­ме­ром сим­п­ле­к­са и ни­как не свя­за­на с по­ве­де­ни­ем ми­ни­ми­зи­ру­е­мой функ­ции. Нел­дер и Мид пред­ло­жи­ли значитель­но бо­лее эф­фе­к­тив­ный ва­ри­ант ал­го­рит­ма, от­ка­зав­шись от со­хра­не­ния оди­на­ко­вых рас­сто­я­ний ме­ж­ду вер­ши­на­ми. По­сколь­ку не­пра­виль­ный мно­го­гран­ник уже не под­хо­дит под оп­ре­де­ле­ние сим­п­ле­к­са, ме­тод по­лучил на­зва­ние по­ис­ка по де­фор­ми­ру­е­мо­му мно­го­гран­ни­ку.

Опе­ра­ция от­ра­же­ния у Нел­дера и Мида ста­ла бо­лее об­щей: x_r=x_c+a·(x_c-x_h), где a – про­из­воль­ный ко­эф­фи­ци­ент от­ра­же­ния (a>0). Кро­ме то­го, до­ба­в­ле­ны опе­ра­ции рас­тя­же­ния и сжа­тия мно­го­гран­ни­ка. Рас­тя­же­ние ис­поль­зу­ет­ся ана­ло­гично по­ис­ку по об­раз­цу в ме­то­де Ху­ка-Джив­са — ес­ли от­ра­же­ние при­ве­ло к зна­чи­тель­но­му улуч­ше­нию (значение в точке x_r ока­за­лось мень­ше, чем во всех вер­ши­нах), то про­из­во­дит­ся до­по­л­ни­тель­ное сме­ще­ние от x_r в том же на­пра­в­ле­нии: x_e=x_c+g·(x_r-x_c), где g>1 – ко­эф­фи­ци­ент рас­тя­же­ния. Сжа­тие за­к­лю­ча­ет­ся в за­ме­не x_r на точ­ку, ле­жа­щую по дру­гую сто­ро­ну гра­ни (т. е. вну­т­ри мно­го­гран­ни­ка): x_r=x_c+b·(x_h-x_c), где 0<b<1 – ко­эф­фи­ци­ент сжа­тия. Сжа­тие при­ме­ня­ет­ся, ес­ли от­ра­же­ние при­ве­ло к ухуд­ше­нию зна­че­ния функ­ции по срав­не­нию с F_h.

На ка­ж­дом ша­ге вы­де­ля­ют­ся три вер­ши­ны мно­го­гран­ни­ка: x_h, как и рань­ше — вер­ши­на, в ко­то­рой зна­че­ние функ­ции ма­к­си­маль­но («наи­худ­шая» вер­ши­на), x_l — вер­ши­на, в ко­то­рой зна­че­ние функ­ции ми­ни­маль­но («наи­луч­шая» вер­ши­на), и x_g — вер­ши­на, в ко­то­рой зна­че­ние функ­ции боль­ше, чем во всех дру­гих, за ис­к­лю­че­ни­ем x_h (т. е. бли­жай­шая к x_h по сте­пе­ни «пло­хо­с­ти»). Ком­би­на­ция опе­ра­ций от­ра­же­ния, рас­тя­же­ния, сжа­тия и со­кра­ще­ния для по­лу­че­ния сле­ду­ю­ще­го мно­го­гран­ни­ка за­ви­сит от срав­не­ния зна­че­ний функ­ции в вер­ши­нах x_h, x_g, x_l и в но­вых точках x_r и x_e. Ло­ги­чес­кая схе­ма вы­бо­ра луч­шей точ­ки до­с­та­точно сло­ж­на, и мы не бу­дем рас­сма­т­ри­вать ее во всех де­та­лях (под­роб­но­сти мо­ж­но най­ти в кни­гах [[1], [2]]). В про­цес­се по­ис­ка ми­ни­му­ма мно­го­гран­ник вы­тя­ги­ва­ет­ся в на­пра­в­ле­нии ус­пеш­ных ша­гов и сжи­ма­ет­ся в «не­пер­с­пек­тив­ных» на­пра­в­ле­ни­ях, что при­во­дит к ус­ко­рен­но­му дви­же­нию в сто­ро­ну об­ще­го по­ни­же­ния значений функ­ции. Пе­ре­ме­ще­ние мно­го­гран­ни­ка на­по­ми­на­ет по­ве­де­ние аме­бы; по этой при­чи­не про­це­ду­ра, ре­а­ли­зу­ю­щая ме­тод Нел­де­ра-Ми­да, по­лу­чи­ла на­з­ва­ние Amoeba.

Поиск по сайту: