Жоғарылау алгоритмі: Математикалық оптимизация техникасы

Кіріспе

Оптимизация алгоритмі – математикалық алгоритм.

Сандық талдауда, дөңгелекке көтерілу – жергілікті іздеу отбасына жататын математикалық оптимизация техникасы. Бұл итеративтік алгоритм, ол проблеманың кез келген бастапқы шешімімен басталады, содан кейін шешімге инкременттік өзгеріс енгізу арқылы жақсырақ шешім табуға тырысады. Егер өзгеріс жақсырақ шешімге әкелсе, жаңа шешімге тағы бір инкременттік өзгеріс жасалады, және жақсартулар табылмайынша осылай жалғасады. Мысалы, дөңгелекке көтерілуді саяхатшы сатушы мәселесіне қолдануға болады. Барлық қалаларды аралап шығатын бастапқы шешімді табу оңай, бірақ ол оңтайлы шешіммен салыстырғанда өте нашар болуы мүмкін. Алгоритм осындай шешіммен басталады және оған шағын түзетулер енгізеді, мысалы, екі қалаға бару ретін ауыстыру. Соңында, әлдеқайда қысқа маршрут алуға болады. Дөңгелекке көтерілу дөңес мәселелер үшін оңтайлы шешімдерді табады – басқа мәселелер үшін ол тек жергілікті оптимамдарды (көрші конфигурациялармен жақсартуға болмайтын шешімдер) табады, олар барлық мүмкін шешімдердің ішіндегі ең жақсы шешім (глобал оптимам) болуы міндетті емес (іздеу кеңістігі). Дөңгелекке көтерілу арқылы дөңес емес мәселелерді шешетін алгоритмдердің мысалдары: сызықтық бағдарламалау үшін симплекс алгоритмі және екілік іздеу. Жергілікті оптимамдарда тұрып қалудан аулақ болу үшін қайта іске қосуды (яғни, қайталанатын жергілікті іздеуді) немесе итерацияларға негізделген күрделі схемаларды (мысалы, итерацияланған жергілікті іздеу), немесе жадты пайдаланатын схемаларды (мысалы, реактивті іздеуді оңтайландыру және табу іздеу), немесе жадты пайдаланбайтын стохастикалық өзгерістерді (мысалы, симуляцияланған қайнату) қолдануға болады. Алгоритмнің салыстырмалы қарапайымдылығы оны оптимизациялау алгоритмдерінің арасында кең таралған бастапқы таңдауға айналдырады. Ол жасанды интеллектте бастапқы нүктеден мақсатқа жету үшін кеңінен қолданылады. Байланысты алгоритмдерде келесі түйіндер мен бастапқы түйіндерді таңдау әртүрлі болуы мүмкін. Симуляцияланған қайнату немесе табу іздеу сияқты озық алгоритмдер жақсы нәтижелер беруі мүмкін болғанымен, кейбір жағдайларда дөңгелекке көтерілу де жақсы жұмыс істейді. Дөңгелекке көтерілу, іздеуді орындауға қол жетімді уақыт шектеулі болғанда, басқа алгоритмдерге қарағанда жақсы нәтижелер бере алады, мысалы, нақты уақыт жүйелерінде, егер шағын түзетулер әдетте жақсы шешімге (оңтайлы шешімге немесе оған жақын шамаға) тез жететін болса. Керісінше, көпіршік сұрыптауын дөңгелекке көтерілу алгоритмі ретінде қарастыруға болады (әрбір жақын элементтерді алмастыру ретсіз элементтер жұбының санын азайтады), бірақ бұл тәсіл тіпті шамалы N үшін де тиімді емес, себебі қажетті алмастырулардың саны квадраттық түрде өседі. Дөңгелекке көтерілу – кез келген уақытта тоқтатылса да, жарамды шешімді қайтаратын алгоритм.

In numerical analysis, hill climbing is a mathematical optimization technique which belongs to the family of local search. It is an iterative algorithm that starts with an arbitrary solution to a problem, then attempts to find a better solution by making an incremental change to the solution. If the change produces a better solution, another incremental change is made to the new solution, and so on until no further improvements can be found. For example, hill climbing can be applied to the travelling salesman problem. It is easy to find an initial solution that visits all the cities but will likely be very poor compared to the optimal solution. The algorithm starts with such a solution and makes small improvements to it, such as switching the order in which two cities are visited. Eventually, a much shorter route is likely to be obtained. Hill climbing finds optimal solutions for convex problems – for other problems it will find only local optima (solutions that cannot be improved upon by any neighboring configurations), which are not necessarily the best possible solution (the global optimum) out of all possible solutions (the search space). Examples of algorithms that solve convex problems by hill climbing include the simplex algorithm for linear programming and binary search. To attempt to avoid getting stuck in local optima, one could use restarts (i. e. repeated local search), or more complex schemes based on iterations (like iterated local search), or on memory (like reactive search optimization and tabu search), or on memory less stochastic modifications (like simulated annealing). The relative simplicity of the algorithm makes it a popular first choice amongst optimizing algorithms. It is used widely in artificial intelligence, for reaching a goal state from a starting node. Different choices for next nodes and starting nodes are used in related algorithms. Although more advanced algorithms such as simulated annealing or tabu search may give better results, in some situations hill climbing works just as well. Hill climbing can often produce a better result than other algorithms when the amount of time available to perform a search is limited, such as with real time systems, so long as a small number of increments typically converges on a good solution (the optimal solution or a close approximation). At the other extreme, bubble sort can be viewed as a hill climbing algorithm (every adjacent element exchange decreases the number of disordered element pairs), yet this approach is far from efficient for even modest N, as the number of exchanges required grows quadratically. Hill climbing is an anytime algorithm: it can return a valid solution even if it's interrupted at any time before it ends.

Математикалық сипаттама

Hill climbing мақсатты функцияны барынша көбейтуге (немесе азайтуға) тырысады, мұнда үнемі және/немесе дискретті мәндердің векторы болып табылады. Әрбір итерацияда hill climbing векторының бір элементін өзгертпейді және бұл өзгеріс мақсатты функцияның мәнін жақсартатынын анықтайды (Бұл градиенттік төмендеу әдістерінен өзгеше, олар hill-дің градиентіне сәйкес әрбір итерацияда векторының барлық мәндерін реттейді). Hill climbing кезінде мақсатты функцияның мәнін жақсартатын кез келген өзгеріс қабылданады, ал процесс мәнін жақсартуға болатын өзгеріс табылмайынша жалғасады. Осы кезде вектор "жергілікті оңтайлы" деп есептеледі. Дискретті векторлық кеңістіктерде векторының әрбір мүмкін мәнін графтың түйіні ретінде қарастыруға болады. Hill climbing граф бойынша түйінден түйінге өтеді, әрқашан мақсатты функцияның мәнін жергілікті түрде арттырады (немесе азайтады), жергілікті максимумға (немесе жергілікті минимумға) жеткенше.

Нұсқалар

Қарапайым дөңгелекке көтерілуде ең жақын түйін таңдалады, ал ең тік дөңгелекке көтерілуде барлық ұрпақтар салыстырылады және шешімге ең жақын түйін таңдалады. Егер жақын түйін болмаса, екі түр де сәтсіз аяқталады, бұл іздеу кеңістігінде шешім емес, жергілікті максимумдар болған жағдайда мүмкін болады. Ең тік дөңгелекке көтерілу, барлық мүмкін кеңейтулерді тек бір жолдың орнына сынап көретін ең жақсы бірінші іздеуге ұқсас. Стохастикалық дөңгелекке көтерілу, қалай жылжуға шешім қабылдамас бұрын барлық көршілерді тексермейді. Оның орнына, ол кездейсоқ көршіні таңдайды және сол көршіге көшуді немесе басқасын қарастыруды (көршідегі жақсарту мөлшеріне байланысты) шешеді. Координаталық түсу, әр итерациядағы ағымдағы нүктеде бір координаталық бағыт бойынша сызықтық іздеуді жүргізеді. Координаталық түсудің кейбір нұсқалары әр итерацияда әртүрлі координаталық бағытты кездейсоқ таңдайды. Кездейсоқ қайта іске қосу дөңгелекке көтерілу – дөңгелекке көтерілу алгоритміне негізделген мета-алгоритм. Бұл әдіс "Оқпандармен дөңгелекке көтерілу" деп те аталады. Ол үзіліссіз дөңгелекке көтерілуді жүзеге асырады, әр жолы кездейсоқ бастапқы шарттармен. Ең жақсы нәтиже сақталады: егер дөңгелекке көтерілудің жаңа кезеңі сақталған күйден жақсы нәтиже берсе, ол сақталған күйді алмастырады. Кездейсоқ қайта іске қосу дөңгелекке көтерілу көп жағдайда таңқаларлықтай тиімді алгоритм болып табылады. Көбінесе бастапқы шарттардан мұқият оңтайландыруға қарағанда, кеңістікті зерттеуге процессор уақытын жұмсау артық екені анықталды.

Жергілікті максималдар

Тау биігінен өрлеу әрқашан жалпы максимумды таба бермейді, оның орнына жергілікті максимумға ұмтылуы мүмкін. Эвристика дөңгелек болса, бұл мәселе туындамайды. Бірақ көптеген функциялар дөңгелек емес болғандықтан, тау биігінен өрлеу жиі жаһандық максимумға жете алмайды. Бұл мәселені шешу үшін, мысалы, стохастикалық тау биігінен өрлеу, кездейсоқ іздеу және симуляцияланған қайнату сияқты басқа жергілікті іздеу алгоритмдері қолданылады.

Қабырғалар мен аллеялар

Қырлар үздіксіз кеңістікте оңтайландыруды жүзеге асыратын тау-кеншілер үшін қиын мәселе болып табылады. Тау-кеншілер вектордағы бір ғана элементті реттейтіндіктен, әр қадам оське сәйкес бағытта жылжиды. Егер мақсатты функция оське сәйкес емес бағытта көтерілетін тар қырды (немесе мақсат азайту болса, оське сәйкес емес бағытта төмендейтін тар жолшықты) құрса, онда тау-кенші тек зигзаг тәрізді қозғалу арқылы ғана қырға көтеріле алады (немесе жолшықтан төмен түсе алады). Егер қырдың (немесе жолшықтың) беткейлері өте тік болса, онда тау-кенші жақсырақ позицияға қарай зигзагмен жылжу кезінде өте кішкентай қадамдар жасауға мәжбүр болуы мүмкін. Осылайша, оның қырға көтерілуіне (немесе жолшықтан төмен түсуіне) қанағаттандырмас уақыт кетіп, тиімсіз болуы мүмкін. Керісінше, градиенттік түсу әдістері қырдың немесе жолшықтың көтерілуі немесе төмендеуі мүмкін кез келген бағытта қозғала алады. Сондықтан, мақсатты функция егер дифференциалданатын болса, градиенттік түсу немесе конъюгатты градиент әдісі тау-кеншіліктен әлдеқайда артық қолданылады. Дегенмен, тау-кеншілердің мақсатты функцияның дифференциалдануын қажет етпеу артықшылығы бар, сондықтан мақсатты функция күрделі болған жағдайда тау-кеншілерге көбірек сенуге болады.