Случайно търсене () е семейство методи за стохастична оптимизация, които не изискват градиент на задачата, за да бъде оптимизирана. Случайното търсене може да бъде сътоветно използвано над функции, които не са непрекъснати или диференцируеми. Такива оптимизационни методи са известни и като методи за директно търсене (direct-search), методи от тип „черна кутия“ (black-box methods) или derivative-free.
Терминът „случайно търсене“ се приписва на Л. А. Растригин, който в статия от 1974 година прави най-ранното представяне на такъв алгоритъм, със съпътстващата го аналитична обосновка. Случайното търсене работи, като итеративно търси по-добри от текущите решения в пространството на търсене, избрани в съседство на текущото решение.
Алгоритъм Нека е фитнес функцията, т.е. целева функция, която подлежи на минимизация. Нека означава позицията на някое кандидат-решение в пространството на търсене, изразено като хиперсфера с даден радиус и център тази позиция. Базовият алгоритъм за случайно търсене следователно може да бъде описано така:
Инициализирай x със случайна позиция в пространството на търсене. Докато не се достигне условието за край (например, брой извършени итерации или постигане на желана адекватна стойност на фитнес функцията), повтори: Избери нова позиция y от хиперсферата с даден радиус с център дадена позиция (решение) x. Ако , то премини към новата позиция, като зададеш .
Варианти В литературата съществуват множество разновидности на алгоритъма за случайно търсене:
Случайно търсене с фиксиран размер на стъпката (Fixed Step Size Random Search, FSSRS) е основният алгоритъм, предложен от Растригин, който взима случайна стойност от хиперсфера с фиксиран радиус. Случайно търсене с оптимален размер на стъпката (Optimum Step Size Random Search, OSSRS) на Schumer и Steiglitz е най-вече теоретично изследване за това как оптимално да се определи радиуса на хиперсферата така, че да осигури бърза сходимост към оптимално решение. Реализацията на този алгоритъм трябва да апроксимира оптималния радиус с итеративна процедура и следователно е изчислително скъп за реализация алгоритъм. Случайно търсене с адаптивен размер на стъпката (Adaptive Step Size Random Search, ASSRS) на Schumer и Steiglitz прави опит евристично да адаптира радиуса на хиперсферата: генерират се две нови кандидат-решения, едно с текущата номинална стъпка и второ с по-голям размер на стъпката. По-голямата стъпка става на свой ред номинална тогава и само тогава, когато води до подобрено решение. Ако в рамките на няколко последователни итерации никой размер на стъпка на второто решение не води до подобряване, се процедира с намаляване на стъпката на първото (номиналното) решение. Случайно търсене с оптимизиран относителен размер на стъпката (Optimized Relative Step Size Random Search, ORSSRS) от Schrack и Choit апроксимира оптималния размер на стъпката с експоненциално намаление.
Вижте също Итеративно локално търсене Локално търсене Табу търсене
Източници
Категория:Метаевристични алгоритми