Наиболее простой процедурой случайного поиска является прямая выборочная процедура, заключающаяся в разыгрывании на ЭВМ последовательности точек с координатами
xi = xiL +ri (xiU - xiL), i=1,2,...,N,
где
ri - случайная величина, равномерно распределенная на интервале [0,1].
После проверки каждой точки на допустимость вычисляются значения целевой функции, которые сравниваются с наилучшим значением, полученным к данному моменту. Если текущая точка дает лучшее значение, то она запоминается, в противном - отбрасывается. Процесс прекращается после заданного числа итераций N или по исчерпанию заданного машинного времени. Для получения 90% доверительного интервала величиной e i (xiU - xiL), где 0<e <1, для переменной xi совместный случайный поиск требует
испытаний. При N=5, e i=0,01 число испытаний оценивается в 2,3 1010, что исключает возможность непосредственного использования метода.
Значительного увеличения эффективности процедуры случайного поиска можно достигнуть путем группировки выборок в серии. При этом наилучшая точка в каждой серии используется как начальная точка следующей серии, точки которой уже выбираются из интервала меньшей величины. Данная процедура получила название выборки со сжатием пространства поиска. Рассмотрим более подробно ее алгоритм.
|
|
Заданы границы значений всех переменных xiL, xiU, i=1,2,..., N (размерность задачи), начальные допустимая точка xo и интервал поиска D xo = xiU - xiL, количество серий Q, количество точек в серии P и параметр окончания вычислений e. Для каждой из серий, начиная с q = 1, необходимо выполнить следующие действия.
Шаг 1. Для i = 1,2,...,N вычислить
xip = xiq-1 +ri D xq-1,
где
ri - случайная величина, равномерно распределенная на интервале [-0,5;0,5].
Шаг 2.
o Если xp - недопустимая точка и p < P, то повторить шаг 1.
- Если xp - допустимая точка, то запомнить xp и W(xp) и
§ если p < P, то повторить шаг 1.
- если p = P, то найти среди всех допустимых точек xp точку с наименьшим значением W(xp) и положить ее равной xq.
Шаг 3. Уменьшить интервал поиска, полагая D xiq = e i D xiq-1.
Шаг 4.
· Если q > Q, то закончить вычисления.
- В противном случае увеличить q = q + 1 и продолжить вычисления, начиная с шага 1.