Кіріспе
Математиканың саласы. Глобалды оңтайландыру – берілген жиынтықтағы функцияның немесе функциялар жиынтығының жаһандық минимум немесе максимумдарын табуға бағытталған қолданбалы математика мен сандық талдаудың бір саласы. Бұл көбінесе минимизациялау мәселесі ретінде сипатталады, себебі нақты мәнді функцияның максимизациясы сол функцияның минимизациясына балама болады. Мүмкін, сызықтық емес және дөңес емес үздіксіз функцияны және оның жаһандық минимумдарын анықтайтын барлық жаһандық минимизаторлар жиынын ескере отырып, стандартты минимизациялау мәселесін былай қоюға болады:
Global optimization is a branch of applied mathematics and numerical analysis that attempts to find the global minima or maxima of a function or a set of functions on a given set. It is usually described as a minimization problem because the maximization of the real valued function is equivalent to the minimization of the function
Given a possibly nonlinear and non convex continuous function with the global minima and the set of all global minimizers in , the standard minimization problem can be given as
that is, finding and a global minimizer in ; where is a (not necessarily convex) compact set defined by inequalities
Global optimization is distinguished from local optimization by its focus on finding the minimum or maximum over the given set, as opposed to finding local minima or maxima. Finding an arbitrary local minimum is relatively straightforward by using classical local optimization methods. Finding the global minimum of a function is far more difficult: analytical methods are frequently not applicable, and the use of numerical solution strategies often leads to very hard challenges.
яғни, жаһандық минимизаторды табу; мұнда – теңсіздіктермен анықталған (қажетті түрде дөңес емес) компакт жиынтық. Глобалды оңтайландыру жергілікті оңтайландырудан берілген жиынтықта минимум немесе максимумды табуға бағытталғандығымен ерекшеленеді, жергілікті минимумдарды немесе максимумдарды табудан өзгеше. Кез келген жергілікті минимумды табу классикалық жергілікті оңтайландыру әдістерін қолдану арқылы салыстырмалы түрде оңай. Бірақ функцияның жаһандық минимумын табу әлдеқайда қиын: аналитикалық әдістер көбінесе қолданылмайды, ал сандық шешімдерді қолдану көбінесе өте күрделі мәселелерге әкеледі.
Global optimization is a branch of applied mathematics and numerical analysis that attempts to find the global minima or maxima of a function or a set of functions on a given set. It is usually described as a minimization problem because the maximization of the real valued function is equivalent to the minimization of the function
Given a possibly nonlinear and non convex continuous function with the global minima and the set of all global minimizers in , the standard minimization problem can be given as
that is, finding and a global minimizer in ; where is a (not necessarily convex) compact set defined by inequalities
Global optimization is distinguished from local optimization by its focus on finding the minimum or maximum over the given set, as opposed to finding local minima or maxima. Finding an arbitrary local minimum is relatively straightforward by using classical local optimization methods. Finding the global minimum of a function is far more difficult: analytical methods are frequently not applicable, and the use of numerical solution strategies often leads to very hard challenges.
Ішкі және сыртқы шамалау
Бұл екі стратегияда да функцияны оңтайландыруға арналған жиын полиэдрлер арқылы жуықталады. Ішкі жуықтауда полиэдрлер жиынның ішінде орналасады, ал сыртқы жуықтауда жиын полиэдрлердің ішінде болады.
Кесу тетігі әдістері
Кесу жазықтығы әдісі – сызықтық теңсіздіктер түріндегі "кесулер" арқылы мүмкін болатын жиынтықты немесе мақсаттық функцияны итеративті түрде жетілдіретін оптимизация әдістерінің жалпы атауы. Бұл процедуралар жиі аралас бүтін сандық сызықтық бағдарламалау (MILP) мәселелеріне бүтін сандық шешімдер табу үшін, сондай-ақ жалпы, міндетті түрде туындысы бар емес дөңес оптимизация мәселелерін шешу үшін қолданылады. MILP мәселелерін шешу үшін кесу жазықтықтарын қолдануды Ральф Э. Гомори және Вацлав Хватал енгізді.
Бранч және байланған әдістер
Бранч және бойнд (BB немесе B&B) – дискретті және комбинаторлық оңтайландыру мәселелері үшін алгоритмдік жобалау үлгісі. Бранч және бойнд алгоритмі күй кеңістігін іздеу арқылы кандидаттық шешімдерді жүйелі түрде тізімдеуден тұрады: кандидаттық шешімдер жиыны толық жиынтығымен түбірленген ағаш құрайды деп есептеледі. Алгоритм осы ағаштың тармақтарын зерттейді, олар шешім жиынтығының ішкі жиынтығын көрсетеді. Тармақтың кандидаттық шешімдерін тізімдеуден бұрын, тармақ оңтайлы шешімге арналған жоғарғы және төменгі бағаланған шектемелермен тексеріледі және егер ол алгоритмге дейін табылған ең жақсы шешімнен жақсы шешім бере алмаса, алынып тасталады.
Интервалдық әдістер
Интервалдық арифметика, интервалдық математика, интервалдық талдау немесе интервалдық есептеу – 1950-1960 жылдардан бері математиктердің математикалық есептеулердегі дөңгелектеу және өлшеу қателіктеріне шектеу қою мақсатымен әзірлеген әдіс, соның нәтижесінде сенімді нәтижелер беретін сандық әдістерді құруға мүмкіндік береді. Интервалдық арифметика теңдеулер мен оптимизациялау мәселелеріне сенімді және кепілді шешімдер табуға көмектеседі.
Нақты алгебралық геометрияға негізделген әдістер
Нақты алгебра — алгебраның нақты алгебралық (және жартылай алгебралық) геометрияға қатысты бөлігі. Ол басты назарды реттелген өрістер мен реттелген сақиналарды (әсіресе нақты жабық өрістерді) зерттеуге, сондай-ақ оларды оң көпмүшелерді және көпмүшелердің квадраттарының қосындыларын зерттеуде қолдануға бөледі. Оны дөңгелек оптимизацияда қолдануға болады.
Монте-Карло әдісі бойынша тікелей іріктеме
Бұл әдісте шамамен шешім табу үшін кездейсоқ симуляциялар қолданылады. Мысал: Саудагердің саяхат мәселесі – бұл дәстүрлі оңтайландыру мәселесі. Яғни, ең жақсы маршрутты анықтау үшін қажетті барлық мәліметтер (әрбір пункт арасындағы қашықтықтар) белгілі және мақсат – ең аз жалпы қашықтықты табу үшін барлық мүмкін маршруттарды қарастыру. Бірақ, егер әрбір қалаған пунктке бару үшін жүрілген жалпы қашықтықты ең азайтудың орнына, әрбір пунктке жетуге қажетті жалпы уақытты азайтуды қаласақ не болады? Бұл дәстүрлі оңтайландырудан асып түседі, себебі жол жүру уақыты белгісіз болады (көлік кептелісі, тәуліктің уақыты және т.б.). Осылайша, ең жақсы маршрутымызды анықтау үшін біз симуляциялық оңтайландыруды қолданып, алдымен бір пункттен екінші пунктке жетуге кеткен ықтимал уақыттың диапазонын түсінуіміз керек (бұл жағдайда нақты қашықтық емес, ықтималдық таралымымен көрсетіледі), содан кейін осы белгісіздікті ескере отырып, ең жақсы маршрутты таңдау үшін саяхат шешімдерін оңтайландыру қажет.
Стохастикалық туннельдеу
Стохастикалық туннельдеу (STUN) – нысаналы түрде азайтылатын функцияны Монте-Карло әдісімен сынап, жаһандық оңтайландыруға қолданылатын тәсіл. Бұл тәсілде функция, функцияның минимумдары бар аймақтар арасында туннельдеуді жеңілдету үшін сызықтық емес түрлендіріледі. Жеңілдетілген туннельдеу үлгі кеңістігін жылдам зерттеуге және жақсы шешімге жылдам жақындасуға мүмкіндік береді.
Параллельді қатаю
Параллельді қатаю, сонымен қатар реплика алмасу MCMC үлгілеуі деп те аталады, физикалық жүйелердің Монте-Карло әдісімен модельдеуінің және жалпы алғанда Марков тізбегі Монте-Карло (MCMC) үлгілеу әдістерінің динамикалық қасиеттерін жақсартуға бағытталған модельдеу әдісі. Реплика алмасу әдісін бастапқыда Свендсен ойлап тапты, кейін Гайер оны кеңейтті, ал Джорджио Паризи және басқалар оны одан әрі дамытты. Сугита мен Окамото параллельді қатаюдың молекулалық динамика нұсқасын құрды: бұл әдетте реплика алмасу молекулалық динамикасы немесе REMD деп аталады. Ең бастысы, әртүрлі температураларда кездейсоқ бастамаланған жүйенің N көшірмесі іске қосылады. Содан кейін, Метрополис критерийіне сәйкес, әртүрлі температуралардағы конфигурациялар алмастырылады. Бұл әдістің мақсаты – жоғары температурадағы конфигурацияларды төмен температурадағы модельдеуге және керісінше қолжетімді ету. Бұл төмен және жоғары энергиялық конфигурацияларды үлгілеуге қабілетті өте сенімді жиынтыққа әкеледі. Осылайша, канондық жиынтықта жақсы есептелмейтін нақты жылу сияқты термодинамикалық қасиеттерді жоғары дәлдікпен есептеуге болады.
Sugita and Okamoto formulated a molecular dynamics version of parallel tempering: this is usually known as replica exchange molecular dynamics or REMD. Essentially, one runs N copies of the system, randomly initialized, at different temperatures. Then, based on the Metropolis criterion one exchanges configurations at different temperatures. The idea of this method
is to make configurations at high temperatures available to the simulations at low temperatures and vice versa. This results in a very robust ensemble which is able to sample both low and high energy configurations. In this way, thermodynamical properties such as the specific heat, which is in general not well computed in the canonical ensemble, can be computed with great precision.