Бөлшектік шоғырландыру әдісі: ішкі және сыртқы іздеу стратегиялары
Particle swarm optimization
Бөлшектік сарысу оптимизациясы (PSO) – ең жақсы шешімді табуға бағытталған итеративті әдіс. Қарапайым алгоритм, математикалық функцияларды оптимизациялауға көмектеседі.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Итеративті модельдеу әдісі
Iterative simulation method
Есептеу ғылымында бөлшектер үйіршігін оңтайландыру (PSO) бөлшектердің қозғалысын іздеу кеңістігіндегі олардың жеке ең жақсы белгілі орнымен, сондай-ақ бүкіл үйіршіктің ең жақсы белгілі орнымен басқарады. Жақсырақ орналасулар табылғанда, олар үйіршіктің қозғалысына бағыт береді. Бұл процесс қайталанады және осылайша қанағаттанарлық шешім табылуы мүмкін деген үміт туады, бірақ кепілдік жоқ. Формальды түрде, f: ℝⁿ → ℝ функциясын шығын функциясы деп атаймыз, оны азайту қажет. Функция кандидат шешімді нақты сандар векторы түрінде аргумент ретінде қабылдайды және берілген кандидат шешімнің мақсаттық функциялық мәнін көрсететін нақты санды шығарады. f функциясының градиенті белгісіз. Мақсат – іздеу кеңістігіндегі барлық b үшін f(a) ≤ f(b) болатын a шешімін табу, яғни a – жаһандық минимум. S – үйіршіктегі бөлшектердің саны болсын, әрқайсысының іздеу кеңістігіндегі орны xi ∈ ℝⁿ және жылдамдығы vi ∈ ℝⁿ. pi – i-ші бөлшектің ең жақсы белгілі орны, ал g – бүкіл үйіршіктің ең жақсы белгілі орны болсын. Шығын функциясын азайту үшін негізгі PSO алгоритмі: осылайша бөлшектер арасындағы ақпарат ағынын басқару үшін әртүрлі топологиялар қолданылған. Мысалы, жергілікті топологияларда бөлшектер тек бөлшектердің кіші жиынтығымен ғана ақпарат бөліседі, мысалы, «m жақын бөлшектер» немесе көбінесе, әлеуметтік жиын – кез келген қашықтыққа тәуелді емес бөлшектер жиынтығы. Мұндай жағдайларда PSO нұсқасы жергілікті ең жақсы деп аталады (негізгі PSO-ның жаһандық ең жақсы нұсқасына қарағанда). Көбінесе қолданылатын үйірме топологиясы – сақина, онда әр бөлшектің тек екі көршісі бар, бірақ одан да көп түрлері бар. APSO, стохастикалық жұлдыз, TRIBES, Кибер-үйірме және C PSO.
In computational science, particle swarm optimization (PSO) The movements of the particles are guided by their own best known position in the search space as well as the entire swarm's best known position. When improved positions are being discovered these will then come to guide the movements of the swarm. The process is repeated and by doing so it is hoped, but not guaranteed, that a satisfactory solution will eventually be discovered. Formally, let f: ℝn → ℝ be the cost function which must be minimized. The function takes a candidate solution as an argument in the form of a vector of real numbers and produces a real number as output which indicates the objective function value of the given candidate solution. The gradient of f is not known. The goal is to find a solution a for which f(a) ≤ f(b) for all b in the search space, which would mean a is the global minimum. Let S be the number of particles in the swarm, each having a position xi ∈ ℝn in the search space and a velocity vi ∈ ℝn. Let pi be the best known position of particle i and let g be the best known position of the entire swarm. A basic PSO algorithm to minimize the cost function is then: thus different topologies have been used to control the flow of information among particles. For instance, in local topologies, particles only share information with a subset of particles. – for example "the m nearest particles" – or, more often, a social one, i. e. a set of particles that is not depending on any distance. In such cases, the PSO variant is said to be local best (vs global best for the basic PSO). A commonly used swarm topology is the ring, in which each particle has just two neighbours, but there are many others. APSO, stochastic star, TRIBES, Cyber Swarm, and C PSO
Ішкі жұмыс
PSO алгоритмінің оптимизациялау қабілетіне неліктен және қалай қол жеткізілетіні туралы бірнеше пікір бар. Зерттеушілер арасындағы кең таралған түсінік – үйірмелік мінез-құлық іздеу кеңістігінің кең аймағын қарастыратын зерттеуші мінез-құлық пен, (мүмкін жергілікті) оптималдыққа жақындау үшін жергілікті бағытта іздеуді қамтитын пайдаланушы мінез-құлық арасында ауыспалы болады. Бұл көзқарас PSO әзірленген сәттен бері басым болып келді. Сонымен қатар, бұл қарапайымдастырулар үйірмелік жинақтың конвергенциясы үшін параметрлердің шектерін анықтаған зерттеулердің нәтижелеріне әсер етпейді. PSO тұрақтылығын талдау кезінде қолданылған модельдеу шарттарын жеңілдетуге соңғы жылдары көп күш жұмсалды.
There are several schools of thought as to why and how the PSO algorithm can perform optimization. A common belief amongst researchers is that the swarm behaviour varies between exploratory behaviour, that is, searching a broader region of the search space, and exploitative behaviour, that is, a locally oriented search so as to get closer to a (possibly local) optimum. This school of thought has been prevalent since the inception of PSO. that these simplifications do not affect the boundaries found by these studies for parameter where the swarm is convergent. Considerable effort has been made in recent years to weaken the modeling assumption utilized during the stability analysis of PSO, and.
Жетекші бөлшектер тобын оңтайландыру
Тағы бір қарапайым нұсқа – үдетілген бөлшектер тобын оңтайландыру (APSO), ол да жылдамдық қолдануды қажет етпейді және көптеген қолданбаларда жинақталуды (конвергенцияны) жылдамдатуға мүмкіндік береді. APSO-ның қарапайым демонстрациялық коды қолжетімді. Бұл PSO нұсқасында бөлшектің жылдамдығы да, бөлшектің ең жақсы орны да қолданылмайды. Бөлшектің орны келесі ереже бойынша жаңартылады,
Another simpler variant is the accelerated particle swarm optimization (APSO), which also does not need to use velocity and can speed up the convergence in many applications. A simple demo code of APSO is available. In this variant of PSO one dispences with both the particle's velocity and the particle's best position. The particle position is updated according to the following rule,
мұнда – бірқалыпты үлестірілген кездейсоқ вектор, – аталған мәселенің типолық өлшемі, ал – әдістің параметрлері. Әдісті жетілдіру үшін әр итерацияда -ны азайтуға болады, мұнда – итерация нөмірі, ал – азайту бақылау параметрі.
where is a random uniformly distributed vector, is the typical length of the problem at hand, and and are the parameters of the method. As a refinement of the method one can decrease with each iteration, , where is the number of the iteration and is the decrease control parameter.