ПОИСК Статьи Рисунки Таблицы Отыскание начальной точки спуска и коррекция нарушений ограничений J в процессе поиска из "Методы оптимизации в химической технологии издание 2" При реализации методов случайного поиска нужно иметь возможность получать наборы случайных чисел, равномерно распределенных на некотором числовом интервале. [c.523] Наиболее простым способом получения случайных чисел является выборка их из специальных таблиц, которые при расчетах на цифровых вычислительных машинах должны быть предварительно введены в запоминающее устройство машины. Недостаток данного способа заключается в том, что при решении сложных задач в машину необходимо вводить большие массивы случайных чисел. С одной стороны, это требует соответствующего времени, а с другой, — что, пожалуй, важнее, приводит к излишней загрузке памяти вычислительной машины. [c.523] Другой способ получения последовательностей случайных чисел состоит в использовании специальных датчиков случайных чисел, действие которых основано на физических явлениях, обладающих соответствующими случайными характеристиками, например шумах радиоэлектронных ламп, радиоактивном распаде и т. д. Основной недостаток этого способа — необходимость применения специального оборудования, которое должно работать согласованно с вычислительной машиной. [c.523] Поэтому наибольшее распространение при решении различных задач методами случайного поиска нашли программные способы получения последовательностей случайных чисел [10], основанные на использовании определенных алгоритмов. Найденные алгоритмически последовательности случайных чисел на самом деле не являются случайными, так как не удовлетворяют необходимым статистическим оценкам [10]. Однако при решении практических задач программно получаемую последовательность чисел часто все же можно рассматривать как случайную при условии, что объем выборки случайных чисел не слишком велик. В связи с этим-для случайных чисел, найденных программным путем, часто применяется название псевдослучайные числа. [c.523] Обычно для программных способов получения случайных чисел используется рекуррентное соотношение, с помощью которого каждое последующее число образуется из предыдущего в соот-ветствии с правилом, задаваемым в виде набора арифметических и логических операций, выполняемых вычислительной машиной. [c.523] Ниже приведены различные алгоритмы получения последовательностей случайных чисел, которые можно применять для решения оптимальных задач методами случайного поиска на цифровых вычислительных машинах [10]. [c.524] Метод произведений. Произвольно выбираются два числа р0 и Рь имеющие одинаковое число значащих цифр т, и находится их произведение q2 = рорь Если т 1, то число значащих цифр в произведении q2 будет больше, чем т. Тогда из всех значащих цифр произведения q2 выбираются m цифр, расположенных в середине числа 2, и эти цифры используются как случайное число р2. Следующее случайное число РЗ получается аналогично из произведения р1р2 и т. д. [c.524] Недостатком этого метода является возможность вырождения последовательности находимых псевдослучайных чисел, т. е. возможность получения на некотором этапе случайного числа, равного нулю, после чего все остальные числа, определяемые с помощью изложенного правила, оказываются равными нулю. [c.524] Очевидно, что остаток от деления на N в общем случае имеет такую же разрядность, как и число N, т. е. выбором числа N по существу определяется разрядность получаемых случайных чисел. [c.524] Первая из формул (IX, 133а) является записью алгоритма Г(1Х, 133), вторая применяется для того, чтобы привести случайные числа к интервалу [0,1]. Период последовательности псевдослучайных чисел, получаемых с помощью формулы (IX, 133а), примерно равен 1012. [c.524] Фигурные скобки в выражении (IX, 135) означают, что из произведения kz берется только дробная часть, которая должна вычисляться с необходимой степенью точности, характеризующей разрядность находимых псевдослучайных чисел. [c.525] Следует иметь в виду, что при использовании случайных чисел для решения задач на вычислительных машинах получаемые программным способом случайные числа всегда имеют определенную конечную разрядность. Большинство алгоритмов получения случайных чисел на вычислительных машинах с двоичной системой счисления предназначены для нахождения таких чисел, у которых с равной вероятностью в каждом разряде может получиться как 1, так и 0. [c.525] Таким образом, если разрядность псевдослучайных чисел выбрана малой, то это может сказаться на степени приближения псевдослучайной последовательности к случайной. [c.525] При т-+оо дисперсия (dm)2 стремится к а2. Скорость приближения для нескольких значений m иллюстрируется табл. 15. [c.526] Заметим, что использование последовательностей псевдослучайных чисел, резко отличающихся по вероятностным оценкам от идеальной последовательности равномерно распределенных случайных чисел, в некоторых случаях может существенно увеличить время решения оптимальной задачи методом случайного поиска. [c.526] Решение задач с ограничениями типа неравенств рассмотрено в следующем разделе, поэтому ниже всегда предполагается, что ограничения типа равенств исходной оптимальной задачи (IX, 2а) нельзя записать в форме соотношений (IX, 142). [c.527] Если вид функции fi(x) известен в явной форме, то условие (IX, 161) позволяет найти также в явном виде уравнение относительно одной неизвестной h, которое может быть решено любым численным методом. При этом решение существенно облегчается тем, что не обязательно определять все без исключения корни уравнения (IX, 151), так как для выбора величины шага используется лишь наименьший положительный корень указанного уравнения. [c.528] В некоторых случаях хорошие результаты можно получить при применении приближенного метода расчета значения заключающегося в следующем. [c.528] Сумма квадратов компонентов вектора Г будет скалярным произведением данного вектора на самого себя, и, следовательно, в знаменателе выражения (IX, 154) стоит скалярный квадрат вектора Y. [c.530] Нетрудно также видеть, что вектор VU(x можно представить в виде удвоенного произведения вектора-функции f(x ) (IX, 158) на транспонированную матрицу W( W) (IX, 155), т. е. [c.530] Вернуться к основной статье