Разработка и исследование гибридного алгоритма решения сложных задач оптимизации
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?КУ абсолютно надежен), , , .
После того, как модель функционирования ТК построена, выбор состава структуры аппаратно программного комплекса КА, который определяет значения интенсивностей переходов между состояниями в соответствующем графе состояний, может быть формализован в виде задачи оптимизации на дискретной решетке с алгоритмически заданной целевой функцией. Это объясняется тем, что существует только конечное количество вариантов каждой подсистемы. Требуется решить задачу оптимизации показателей эффективности, изучить их свойства, выявить или разработать эффективные алгоритмы для решения подобных задач оптимизации.
1.2Алгоритмы целочисленной оптимизации
В силу того, что требуется решить задачу целочисленной оптимизации
,
где ,
необходимо привести основные термины и понятия данной теории и алгоритмы, которые используются в работе.
Определение 1. S - область поиска оптимизации. В нашем случае, S - множество целочисленных Z или булевых B переменных. В первом случае имеем задачу оптимизации на целочисленной решетке, во втором имеем так называемую задачу оптимизации на булевом гиперкубе (т.e. оптимизацию вещественно заданной функции для булевых переменных).
Определение 2. D - допустимая область определения целевой функции.
Главной идеей локального поиска является концепция соседства, выражаемая понятием "окрестность". Прежде всего, надо дать математическую формализацию концепции окрестности.
Пусть мы имеем допустимую точку X D для некоторой конкретной задачи оптимизации. Было бы весьма полезно определить некоторое множество точек, "близких", в некотором смысле, к этой точке X.
Определение 3. Пусть задана задача оптимизации (D, f), где D - допустимая область, f - целевая функция. Тогда системой окрестностей или окрестностной функцией называется отображение N : D 2D, определенное для каждой индивидуальной задачи (2D есть множество всех подмножеств множества D).
Для задачи оптимизации на дискретной решетке будут применяться следующие системы окрестностей:
N1(X) = ,(X) = ,
где n - длина целочисленного вектора (точки допустимой области определения).
Задача оптимизации вещественно-значной функции булевых переменных называется задаче псевдобулевой оптимизации. В пространстве булевых переменных система окрестностей задается следующим образом.
Определение 4. Две точки Х и Y из области D пространства булевых переменных будем называть k-соседними, если они отличаются друг от друга значениями k своих координат.
Примечание: множество точек, k-соседних к точке Х будем обозначать как Ok(X).
Определение 5. Пусть дана индивидуальная задача оптимизации (D,f) и система окрестностей N. Тогда некоторое допустимое решение Х* называется локально оптимальным или оптимальным относительно системы окрестностей N, если f(X*) < f(Y) " Y N(X*).
Определение 6. Решение X задачи (D, f) называется глобально оптимальным, если f(X) < f(Y) "Y D.
Определение 7. Если любая точка Х D, локально оптимальная относительно системы окрестностей N, является глобально оптимальной, то система окрестностей N называется точной.
Ниже приведены используемые в данной работе алгоритмы прямого локального поиска [4].
Неулучшаемый алгоритм локального поиска на целочисленной решетке
1. Выбираем X0 Dn произвольно.
. Поочередно просматриваем 1-соседние точки X0 и вычисляем значения функции в получаемых точках. Запоминаем изменение, приведшее к улучшению.
. Если ни одно улучшение не найдено, то X0 - точка минимума, остановиться и вывести ответ.
. Заменяем все координаты X0 на те, которые приводили к улучшению, и вычисляем значение функции в полученной точке. Обозначаем полученную точку через X0.
. Поочередно изменяем координаты точки X0 таким образом, который приводил к улучшению на предыдущем шаге и вычисляем значения функции в получаемых точках.
. Если ни одно улучшение не найдено, то проверяем остальные точки окрестности.
7.Перейти к шагу 3.
Алгоритм локального поиска на целочисленной решетке по системе окрестностей N2(X)
1. Стартовую точку выбрать произвольно.
. Увеличивать каждую координату по очереди на два и вычислять значения целевой функции. Если улучшения не произошло, то уменьшать ту же координату на два и вычислять значение функции. В случае улучшения значения функции переходить в точку, дающую такое улучшение, и продолжать со следующей координаты.
. Если изменение всех координат на два не дает улучшения функции, то начинать просмотр всех пар координат в порядке 1-2, 1-3, тАж , 2-3, 2-4, тАж, увеличивая и уменьшая каждую координату пары на единицу. Если получено улучшение целевой функции, то переходить в точку, дающую улучшение, и продолжать с шага 2.
. Если на втором и третьем шаге не получено улучшения, то увеличивать и уменьшать каждую координату на единицу, вычисляя значение функции и запоминая лучшее из них вместе с дающей его точкой.
. Вывести наилучшее значение целевой функции и точку, в которой это значение получено.
Неулучшаемый алгоритм псевдобулевой оптимизации
1. Произвольно выбираем точку X0D.
. Последовательно инвертируем координаты булева вектора, определяя все точки Xj Ol(X), j = 1, тАж, n, 1-соседние к X0 (n - длина битовой строки).
. Координаты оптимальной точки Х* получаем по правилу:
Примечание. Дан