Кіріспе
Сандық оңтайландыру алгоритмі
Нельдер–Мид әдісі (сонымен қатар, төменгі симплекс әдісі, амеба әдісі немесе политоп әдісі) – көп өлшемді кеңістікте объективті функцияның минимум немесе максимум мәнін табуға қолданылатын сандық әдіс. Бұл тікелей іздеу әдісі (функцияларды салыстыру негізінде) және көбінесе туындылары белгісіз болатын сызықтық емес оптимизациялық есептерге қолданылады. Дегенмен, Нельдер–Мид техникасы – бұл эвристикалық іздеу әдісі болып табылады, ол балама әдістермен шешілетін есептерде стационарлық емес нүктелерге жақындауы мүмкін. Нельдер–Мид техникасын Джон Нельдер және Роджер Мид 1965 жылы Спендли және авторлардың әдісін дамыту ретінде ұсынды.
Шолу
Әдіс simplex тұжырымын қолданады, бұл n өлшемдегі n+1 төбесі бар ерекше политоп. Simplex-тердің мысалдары: бір өлшемді кеңістіктегі сызық сегменті, екі өлшемді кеңістіктегі үшбұрыш, үш өлшемді кеңістіктегі төртбұрышты пирамида және т.б. Әдіс n айнымалысы бар проблеманың жергілікті оптимумын табуға шамамен келтіреді, егер мақсаттық функция тегіс өзгеріп, унимодальды болса. Типтік іске асырулар функцияларды азайтуға бағытталған, ал біз барынша арттыру үшін азайтамыз. Мысалы, аспалы көпір инженері әрбір тіреудің, кабельдің және іргетастың қалыңдығын анықтауы керек. Бұл элементтер бір-біріне тәуелді, бірақ кез келген элементті өзгертудің әсерін көру қиын. Мұндай күрделі құрылымдарды модельдеу едәуір есептеу шығындарына байланысты болуы мүмкін, бір орындалуға бірнеше сағат уақыт қажет болуы мүмкін. Нельдер-Мед әдісі бастапқы нұсқасында, кейінірек сипатталатын қысқарту операциясын есепке алмай, әр итерацияда екі бағалаудан аспайды, бұл басқа тікелей іздеу оңтайландыру әдістерімен салыстырғанда тиімді. Дегенмен, ұсынылған оптимумға жетуге қажетті итерациялардың жалпы саны жоғары болуы мүмкін. Nelder-Mead n өлшемде n+1 сынақ нүктесінен тұратын симплекс жиынын қолдайды. Содан кейін ол жаңа сынақ нүктесін табу және ескі нүктелердің біреуін жаңасына алмастыру үшін әр сынақ нүктесінде өлшенген мақсаттық функцияның мінез-құлқын экстраполяциялайды, осылайша техника дамиды. Ең қарапайым тәсіл – ең нашар нүктесін қалған n нүктелердің ауданының центрі арқылы шағылыстырылған нүктемен ауыстыру. Егер бұл нүкте қазіргі ең жақсы нүктеден жақсырақ болса, онда біз осы түзу бойымен экспоненциалды түрде созуға тырысамыз. Керісінше, егер жаңа нүкте бұрынғы мәннен айтарлықтай жақсырақ болмаса, онда біз аңғардан өтіп жатырмыз, сондықтан симплексті жақсырақ нүктеге қарай қысқартамыз. "Сандық рецептуралар" еңбегінен алынған алгоритмнің интуитивті түсіндірмесі:
For example, a suspension bridge engineer has to choose how thick each strut, cable, and pier must be. These elements are interdependent, but it is not easy to visualize the impact of changing any specific element. Simulation of such complicated structures is often extremely computationally expensive to run, possibly taking upwards of hours per execution. The Nelder–Mead method requires, in the original variant, no more than two evaluations per iteration, except for the shrink operation described later, which is attractive compared to some other direct search optimization methods. However, the overall number of iterations to proposed optimum may be high. Nelder–Mead in n dimensions maintains a set of n + 1 test points arranged as a simplex. It then extrapolates the behavior of the objective function measured at each test point in order to find a new test point and to replace one of the old test points with the new one, and so the technique progresses. The simplest approach is to replace the worst point with a point reflected through the centroid of the remaining n points. If this point is better than the best current point, then we can try stretching exponentially out along this line. On the other hand, if this new point isn't much better than the previous value, then we are stepping across a valley, so we shrink the simplex towards a better point. An intuitive explanation of the algorithm from "Numerical Recipes":
Төменгі симплекс әдісі бірнеше қадамдардан тұрады, көбінесе қадамдар функциясы ең үлкен (ең жоғары нүкте) симплекстің қарама-қарсы жағынан төменгі нүктеге дейін жылжиды. Бұл қадамдар шағылысу деп аталады және олар симплекстің көлемін сақтау үшін (осылайша оның дегенерациясыздығын сақтау үшін) құрылады. Мүмкіндігі болған кезде, әдіс симплексті үлкен қадамдар жасау үшін бір немесе басқа бағытта кеңейтеді. Ол "тасқа" жеткенде, көлденең бағытта жиырылып, аңғардан төмен сырғуға тырысады. Егер симплекс "ине тілігінен өтуге" тырысса, ол барлық бағытта өзіне-өзі тартылады, ең төменгі (ең жақсы) нүктесінің айналасына жиырылады. Қазіргі заманғы оңтайландыру әдістерінен айырмашылығы, Нельдер-Мед эвристикасы мәселе қазіргі заманғы әдістерге қажетті шарттардан гөрі күшті шарттарды қанағаттандырмаса, тұрақсыз нүктеге жиналуы мүмкін.
Бастапқы симплекс
Бастапқы симплекс маңызды. Шындығында, тым кішкентай бастапқы симплекс жергілікті іздеуге алып келуі мүмкін, нәтижесінде NM оңай тұрып қалуы мүмкін. Сондықтан бұл симплекс проблеманың ерекшеліктеріне байланысты болуы керек. Дегенмен, түпнұсқа мақалада бастапқы нүктесі берілген, ал қалғандары әрбір өлшем бойынша белгілі бір қадаммен жасалған симплекс ұсынылған. Осылайша, әдіс құрамындағы айнымалылардың масштабталуына сезімтал.
Аяқтау
Итерациялық циклды тоқтату үшін критерийлер қажет. Нельдер және Мид ағымдағы симплекстің функциялық мәндерінің үлгілік стандартты қатесін пайдаланды. Егер бұл мәндер белгілі бір төзімділіктен төмен болса, цикл тоқтатылады және симплекстің ең төмен нүктесі ұсынылған оптимум ретінде қайтарылады. Қатысты мәселе, өте "жазық" функция кең доменде шамамен бірдей функциялық мәндерге ие болуы мүмкін, сондықтан шешім төзімділікке сезімтал болады. Нэш қосымша тоқтату критерийі ретінде қысқару тестін қосады. Бағдарламалар аяқталады, ал итерациялар жинақталуы мүмкін екенін ескеріңіз.