Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10 | Следующая страница реферата

Усредненное по всем реализациям значения совпадает с истинным направлением наискорейшего подъема, т. е.
Далее из точки совершается очередной рабочий шаг:

3.5. Метод “тяжелого шарика”.

Рассмотрим простейший вариант случайного поиска: пусть - произвольная точка. Из совершается движение с шагом в случайном направлении с равномерным распределением.

Движение представляющей точки описывается так:

Этот алгоритм без памяти может быть усовершенствован. Направление удачных проб запоминается и вероятность шага в этих направлениях возрастает. Для этого введем вектор памяти , проекции которого на координатные оси определяют вероятность выбора положительного направления по i - ой оси. - монотонная, неубывающая функция, тогда , а изменяется так:

где

- параметр запоминания, - характеризует скорость обучения,

.

Этот метод называется методом “тяжелого шарика”.

3.6. Формирование маршрутной матрицы.

Пусть поставлена задача (2.3) - (2.4). Для нахождения решения применим метод последовательной оптимизации.

Описание метода.
1. Начальный шаг к=0.
В качестве начального приближения выберем некоторую матрицу . Матрица должна удовлетворять условиям 2.4. Зададим точность .
Замечание. Выше было сказано, что для того, чтобы повысить вероятность нахождения глобального экстремума выбирают несколько начальных приближений. может быть выбрана случайно, либо область определения может быть разбита на интервалы и в качестве выбираются узлы полученной сетки. Методы выбора числа случайных проб или размерности сетки описаны в [3] - [7].
2. к-ый шаг. Выбор направления движения.
Для каждого элемента , где вычислим значения целевой функции , где

- матрица, в которой все элементы равны элементам матрицы , кроме одного этого элемента , который равен . Значение величины выбирается из соображений о точности, с которой ищется

. Методы выбора величины описаны в [3] - [7].
Таким образом получим множество значений целевой функции . ( может быть положительной и отрицательной). Для всех элементов .
Выберем теперь . Соответствующий элемент матрицы запоминаем. Пусть это будет .Выберем теперь в строке i1 элемент , такой, что

. Запомним также этот элемент.
Рассмотрим два возможных варианта: а) Если , то запоминаем компоненты , и переходим к 3. б) Если
, то , переходим к 4.
3. к-ый шаг. Движение в выбранном направлении.
Из точки переходим к следующим образом:
Если , то определяется следующим образом:

к:=к+1, переходим к 3.
Если , то , к:=к+1, переходим к 2.
4. Конечный шаг.

Если ( - величина, определяющая точность вычисления экстремума), то - искомая маршрутная матрица.

Если , то выбирают другое начальное приближение и переходят к 2. Если множество начальных приближений исчерпано, то полагают, что сформировать маршрутную матрицу невозможно.

4. Алгоритм программы, реализующий метод построения маршрутной матрицы.

Алгоритм состоит из 6 функциональных блоков, выполняемых в порядке, который схематично изображен на рисунке 2 “Схема алгоритма”. Ниже приведено назначение и содержание всех 6-ти функциональных блоков. Алгоритм реализует описанный выше метод.
Блок 1.

Назначение: Ввод данных, необходимых для построения маршрутной матрицы.

Содержание: Ввод данных, конкретизирующих решаемую задачу (т. е. задачу построения маршрутной матрицы виртуальной СеМО (2.3) - (2.4)). Эти данные должны содержать число СМО в сети и матрицу смежности исходной концептуальной виртуальной СеМО, а также концептуальный вектор .
Блок 2.

Назначение: Задание начального приближения.

Содержание: Матрица формируется путем присвоения случайных значений элементам таких, что , где I - множество номеров элементов матрицы смежности, таких что

При этом необходимо соблюдать стохастичность матрицы, т. е. условия
(2.4). Остальные элементы получают следующим образом:

Рекомендуем скачать другие рефераты по теме: реферат на тему наука, антикризисное управление.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10 | Следующая страница реферата