Разработка и исследование вероятностных эволюционных алгоритмов для моделирования и оптимизации сложных систем
Диссертация - Менеджмент
Другие диссертации по предмету Менеджмент
? вообще, либо целевой функционал вычисляется математически (точнее, на компьютере) как последовательность сложных нелинейных математических преобразований.
-Неопределенность - априорные сведения о свойствах целевого функционала отсутствуют. Оптимизация производится только по измерениям функционала в фиксированных точках.
-С объектом нельзя активно экспериментировать, оптимизация производится по модели объекта.
-Объект нестационарный - положение экстремума может меняться во времени.
-Размерность задачи высока.
-Переменные задачи выражены в различных шкалах измерения.
-Оптимизируемый функционал крайне нелинеен и многоэкстремален, в допустимой области существуют множества постоянства.
-Допустимая область ограничена - наличие ограничений типа равенств и неравенств (ограничения также могут обладать выше перечисленными свойствами).
-Оптимизация производится по многим экстремальным критериям одновременно - многокритериальная оптимизация.
Очевидно, что применение классических методов оптимизации в подобных задачах невозможно или крайне затруднено.
1.1.1Метод бинаризации
В общем виде задачу безусловной оптимизации можно представить в виде (1), где переменные могут быть выражены в различных шкалах измерений.
,(1)
где - область изменения метрических переменных, - область изменения порядковых переменных, - область изменения переменных наименований, - область изменения переменных перестановок.
Предложенный Л.А. Растригиным метод бинаризации позволяет сводить задачи типа (1) к задачам псевдобулевой оптимизации (2). Следует отметить, что к задаче (2) сводятся любые задачи дискретного программирования, а также непрерывного, путем дискретизации пространства поиска [12, 15].
,
.(2)
Основная идея бинарного кодирования заключается в следующем. Булев вектор компонент, может принимать - значений. Необходимо каким-либо образом установить соответствие между значениями переменных исходной задачи и значениями булевого вектора (задать алгоритм кодирования). В случае, если число значений переменных исходной задачи не равно , то либо переопределяют область изменения исходных переменных, либо одному значению исходной переменной ставят в соответствие несколько значений булевого вектора.
Перевод порядковых переменных в булевы
Пусть дана порядковая переменная . Бинарным представлением переменной будет вектор , где . Находим значение булевого вектора, переведя его в целое число . Тогда полагаем .
Перевод метрических переменных в булевы
Кодирование метрической шкалы начинается с перевода ее в порядковую. Для этого интервал разбивается на равных частей ( - точность решения задачи оптимизации). Теперь переменная измеряется в порядковой шкале, , где . Далее порядковая переменная преобразуется в булеву аналогично.
Перевод переменных наименований и перестановок в булевы
Эффективных алгоритмов перевода порядковых переменных и переменных наименований до сих пор не предложено. Непосредственный перевод их в булевы переменные дает результат аналогичный полному перебору.
Предложено по мере накопления информации о функционале в процессе оптимизации, определять отношения порядка на множестве перестановок и наименований. Далее работать так же как и с порядковыми шкалами.
1.1.2Коды Грея
Код Грея это бинарный код целого числа, такой, что для смежных целых чисел расстояние между их кодами в метрике Хемминга равно 1.
Стандартное рефлексивное Грей кодирование целого числа получается применением оператора исключающего ИЛИ к стандартному бинарному кодированию целого числа и к тому же бинарному коду, смещенному на одну позицию вправо, последний бит отсекается.
Кодирование и декодирование Грея можно выразить в виде операций с матрицами. Пусть x и y n-битовое бинарное и Грей кодирование целого числа соответственно, и G матрица трансформации, состоящая из 1 на главной диагонали и диагонали верхнего минора и 0 в других позициях. Грей кодирование и декодирование тогда можно представить как и соответственно. Можно показать, что любая перестановка столбца в матрице G приводит к другой матрице трансформации [54].
Можно использовать следующий алгоритм перевода бинарного кода в Грей-код и наоборот: начать со старшего (правого) бита для получения Грей кода и с левого для получения бинарного кода, последовательно заменять биты по правилу:
На каждом шаге заменяется два бита и производится смещение на один бит таким образом, что на последующем шаге заменяется один новый бит и один старый.
Для многих практических задач код Грея оказывается более эффективным, чем бинарное кодирование [39]. Код Грея сохраняет структуру окрестностей пространства поиска в бинаризованном пространстве. В результате, Грей код не может образовать оптимумов больше, чем у исходной целевой функции. Более того, т.к. у текущей точки в коде Грея соседних точек больше, чем в дискретной целевой функции, то в пространстве поиска Грей кода число оптимумов обычно меньше. В противоположность, бинарный код часто создает новые оптимумы, которых нет в целевой функции [59].
1.1.3Тестовые задачи
Вопрос об определении адекватного множества тестовых задач для конкретного типа алгоритмов совсем не прост, хотя некоторые необходимые принципы кажутся очевидными.
-Зад