Раздел 3. Некоторые алгоритмы решения задач оптимизации

3.1 Поисковые (прямые) алгоритмы оптимизации

Поисковые алгоритмы классифицируются следующим образом:

Поисковые алгоритмы:
Вероятностные (опираются на случайные числа, выбираемы в соответствии с заданным законом распределения вероятностей)	Детерминированные
Случайный перебор	Алгоритмы полного перебора	Алгоритмы направленного поиска

Рассмотрим конкретные примеры поисковых алгоритмов.

1. Алгоритм полного перебора (алгоритм сеток)

Рассмотрим задачу.

Дано:

1) Исходное пространство R_x

2) Вектор искомых переменных

3) Критерий оптимальности

4) Ограничения:

Требуется:

Найти удовлетворяющие критериям.

Пример:

В итоге получаем множество точек и будим искать среди них оптимальное значение (например, перебором).

Алгоритм:

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

Недостаток: быстро растущие затраты времени на поиск оптимума с ростом числа вариантов решения.

3.1.2 Алгоритм покоординатного поиска

Поочередный подбор решений конкретных координат пространства искомых переменных

Данный метод гарантирует нахождение оптимума только в 1 случае, когда критерий оптимальности сепарабельный.

Формула сепарабельного критерия:

Для отыскания приближенного решения этот метод также можно применять.

Достоинства по отношения к предыдущему алгоритму: можно достигнуть оптимума без полного перебора

3.1.3 Градиентный алгоритм поиска оптимума с использование реверса (возврата назад)

Процедура опирается на следующие соотношения:

Алгоритм:

3.1.4 Поиск оптимума в многокритериальном пространстве.

Рассмотрим данный алгоритм на примере задачи проектирования технического объекта.

Дано:

1) Материальная модель системы, имеющая n параметров:

2) Ограничения на параметры:

3) Функциональные ограничения:

(рисунок)

4) Критерий качества проектируемой системы:

5) Критериальные ограничения:

Требуется:

Найти такое A, которое удовлетворяет всем ограничениям.

Рассмотрим укрупненную диалоговую процедуру решения данной задачи:

2 – 4 блоки — первый этап

5 блок – второй этап

Остальное - третий этап

Краткая характеристика первого этапа.

Он состоит в составлении таблиц испытаний для пространства D. Последовательно выбирается N-пробных точек, которые мы обозначили А₁, А₂,...,А_n . Эти точки равномерно распределены в пространстве G. В каждой точке A_i рассчитывается значения всех критериев оптимальности Ф_v(A₁), Ф_v(А₂)...Ф_v(А_n) (- таблица Δ). По каждому критерию составляется таблица испытаний, в которой записаны значения критериев в порядке возрастания: Ф_v(A_i1) <= Ф_v(A_ik) <= .... <= Ф_v(A_in), где i₁, i₂, ,.., i_n — номера пробных точек.

Кратка характеристика 2 этапа

ЛПР просматривает строки таблицы Δ и назначает (изменяет) ограничения по критериям.

Краткая характеристика 3 этапа

Проверка не пустоты множества D, если ....