Случайно търсене

Случайно търсене (на английски: Random search, RS) е семейство методи за стохастична оптимизация, които не изискват градиент на задачата, за да бъде оптимизирана. Случайното търсене може да бъде сътоветно използвано над функции, които не са непрекъснати или диференцируеми. Такива оптимизационни методи са известни и като методи за директно търсене (direct-search), методи от тип „черна кутия“ (black-box methods) или derivative-free.

Терминът „случайно търсене“ се приписва на Л. А. Растригин,^[1] който в статия от 1974 година прави най-ранното представяне на такъв алгоритъм, със съпътстващата го аналитична обосновка. Случайното търсене работи, като итеративно търси по-добри от текущите решения в пространството на търсене, избрани в съседство на текущото решение.

Алгоритъм

Нека f: ℝⁿ → ℝ е фитнес функцията, т.е. целева функция, която подлежи на минимизация. Нека x ∈ ℝⁿ означава позицията на някое кандидат-решение в пространството на търсене, изразено като хиперсфера с даден радиус и център тази позиция. Базовият алгоритъм за случайно търсене следователно може да бъде описано така:

Инициализирай x със случайна позиция в пространството на търсене.
Докато не се достигне условието за край (например, брой извършени итерации или постигане на желана адекватна стойност на фитнес функцията), повтори:
1. Избери нова позиция y от хиперсферата с даден радиус с център дадена позиция (решение) x.
2. Ако f(y) < f(x), то премини към новата позиция, като зададеш x = y.

Варианти

В литературата съществуват множество разновидности на алгоритъма за случайно търсене:

Случайно търсене с фиксиран размер на стъпката (Fixed Step Size Random Search, FSSRS) е ^[1] основният алгоритъм, предложен от Растригин, който взима случайна стойност от хиперсфера с фиксиран радиус.
Случайно търсене с оптимален размер на стъпката (Optimum Step Size Random Search, OSSRS) на Schumer и Steiglitz ^[2] е най-вече теоретично изследване за това как оптимално да се определи радиуса на хиперсферата така, че да осигури бърза сходимост към оптимално решение. Реализацията на този алгоритъм трябва да апроксимира оптималния радиус с итеративна процедура и следователно е изчислително скъп за реализация алгоритъм.
Случайно търсене с адаптивен размер на стъпката (Adaptive Step Size Random Search, ASSRS) на Schumer и Steiglitz ^[2] прави опит евристично да адаптира радиуса на хиперсферата: генерират се две нови кандидат-решения, едно с текущата номинална стъпка и второ с по-голям размер на стъпката. По-голямата стъпка става на свой ред номинална тогава и само тогава, когато води до подобрено решение. Ако в рамките на няколко последователни итерации никой размер на стъпка на второто решение не води до подобряване, се процедира с намаляване на стъпката на първото (номиналното) решение.
Случайно търсене с оптимизиран относителен размер на стъпката (Optimized Relative Step Size Random Search, ORSSRS) от Schrack и Choit ^[3] апроксимира оптималния размер на стъпката с експоненциално намаление.

Вижте също

Източници

↑ ^а ^б Rastrigin, L.A. The convergence of the random search method in the extremal control of a many parameter system // Automation and Remote Control 24. 1963. с. 1337 – 1342.
↑ ^а ^б Schumer, M.A. и др. Adaptive step size random search // IEEE Transactions on Automatic Control 13. 1968. DOI:10.1109/tac.1968.1098903. с. 270 – 276.
↑ Schrack, G. и др. Optimized relative step size random searches // Mathematical Programming 10. 1976. DOI:10.1007/bf01580669. с. 230 – 244.

Тази страница частично или изцяло представлява превод на страницата Random search в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите.

ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.

[rastrigin63convergence-1] а ^б Rastrigin, L.A. The convergence of the random search method in the extremal control of a many parameter system // Automation and Remote Control 24. 1963. с. 1337 – 1342.

[schumer68adaptive-2] а ^б Schumer, M.A. и др. Adaptive step size random search // IEEE Transactions on Automatic Control 13. 1968. DOI:10.1109/tac.1968.1098903. с. 270 – 276.

[schrack76optimized-3] Schrack, G. и др. Optimized relative step size random searches // Mathematical Programming 10. 1976. DOI:10.1007/bf01580669. с. 230 – 244.

[1]

[2]

[3]