4.1. Технологии локального и генетического поиска

Рассмотрим инструментальные средства ЭМ, в которых используется ряд простейших, методов одномерного поиска, градиентного поиска, а также статистических методов оптимизации. На рис. 4.1 показана одна из возможных классификаций таких стратегий поиска.

К одномерному поиску относят методы: пассивный, последовательный. Пассивный поиск заключается в случайном выборе пар на заданном отрезке для нахождения оптимума ЦФ. Последовательный поиск выполняется путем перебора значений ЦФ для нахождения оптимального значения. Опишем один из возможных методов одномерного поиска — алгоритм поиска из начальной точки [112].

1.   Получить набор или одно альтернативное решение.

2.   Построить график зависимости ЦФ от времени (или числа элементов модели оптимизационной задачи).

3.   Ввести начальную точку ѴЬ, начальный шаг АѴ, точность е, вычислить ЦФ F(Vo).

4.   Положить Ѵ\ = Ѵо + АѴ, вычислить ЦФ F(Vi).

5.   При минимизации ЦФ: если F(Vi) > F(Vo), то АѴ := —АѴ и перейти к 4.

6.   Присвоить АѴ := 2АѴ.

7.   Считать Ѵ‘2 := Ѵ\ + АѴ, вычислить F(F2).

8.   Если F(F2) < F(Vi), то Vo = Vl, V± = F2, F(Vo) = F(Vi) и переход к

6,   иначе к 9.

9.   Положить а = Vo, b = ѴЬ, вывести [а, Ь] — интервал неопределенности.

10. Конец работы алгоритма.

К последовательному поиску относятся методы: дихотомии, Фибоначчи, золотого сечения, поиска в глубину, в ширину, с возвратом, горизонта и поиск на И-ИЛИ деревьях.

Метод дихотомии реализуется за счет механизма обычного перебора возможных точек разрыва. Он аналогичен методу деления отрезка пополам для нахождения точки, в которой ЦФ имеет локальный оптимум [110-113].

1 2 3 4 5 678

Например, на отрезке Л : a\b\c\d\e\f\g\i\h возможны максимально 8 точек разрыва. Очевидно, точность (живучесть, эффективность) такого процесса определяется количеством выбранных точек п, причем п = L — 1, где L — длина отрезка, т. е. количество выделенных дискретных точек. Дискретный интервал [1-8] обозначим L®. Реализованный интервал назовем интервалом неопределенности Ьц.

Эффективность поиска будет ^ , что приблизительно равно двум.

Такой метод деления отрезка пополам для нахождения точки, в которой ЦФ имеет локальный оптимум, называется дихотомическим методом. Равномерное распределение всех разрывов на интервале [а, Ь] не является наилучшим. Эффективность поиска можно улучшить, если все разрывы проводить последовательно и попарно, анализируя результаты после каждой пары экспериментов. Наиболее эффективные результаты — такое расположение пары разрывов, при котором текущий интервал неопределенности сокращается практически вдвое. Итак, после первого разбиения интервал

где 6 = 0,1,2,...в зависимости от решения ЛПР.

Приведем укрупненный алгоритм метода дихотомии.

1.   Получить набор или одно альтернативное решение.

2.   Ввести границы интервала, параметр 6.

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

4.   Вблизи точки деления (по разные стороны с наименьшим интервалом) 6 = 0,1, 2,... находим точки с экстремальным значением ЦФ.

5.   Каждую половину отрезка снова делим пополам и процесс расчета продолжаем по исходной схеме до тех пор, пока не будет получена ЦФ с наилучшим значением или ранее не будет закончено деление на основе заданной метки.

6.   Конец работы алгоритма.

Эффективность метода дихотомии экспоненциально растет с ростом п. Оптимальную стратегию последовательного поиска может дать метод Фибоначчи [109” 113]. Сущность алгоритма состоит в том, что выборки, проводимые последовательно, располагаются так, чтобы для соседних выборок выполнилось условие

здесь dj — номер дискретной точки на интервале [а, Ь]. Для любой (п — к)- выборки справедливо равенство

где ¥к — числа Фибоначчи.

В алгоритме используется то свойство чисел ряда Фибоначчи, что очередной член ряда равен сумме двух предыдущих, кроме первого и второго: F* = Fk-i + Fk-2, где F0 = 0, Fi = 1, fc = 2,3,... (например, числа Фибоначчи 0,1,1,2,3,5,8,13,21,34,55,...).

Вначале, исходя из заданной требуемой точности е, определяется F„ — наименьшее из чисел Фибоначчи, удовлетворяющее неравенству

Тогда (Ь — а) = ¥пА, т. е. весь интервал можно разделить на количество частей Fn, причем каждая часть будет иметь длину, меньшую 6 (А < е). При этом ¥п = Fn^i +Fn^2 = Fn^2 + Fn^3 + Fn^2 = 2Fn^2 + Fn^3. Точки деления x\ и ж2 определяются по формулам:

 

В найденных точках проверяются значения ЦФ. Если лучшие значения ЦФ достигнуты в точке хі, то в качестве интервала выбирается [а, ж^], в противном случае [ж^, b\. Для продолжения поиска точки следующего замера следует расположить симметрично имеющемуся разбиению. Далее поиск осуществляется аналогично. Согласно [110] точка искомого экстремума определяется с точностью 2Л ^ е, и для достижения этой точности требуется N — 2 вычислений.

Приведем модифицированный алгоритм поиска на основе чисел Фибоначчи для нахождения экстремума ЦФ:

1.   Получить набор или одно альтернативное решение.

2.   Ввести границы исследуемого интервала [а, Ь\.

3.   По заданной точности 5 рассчитать вспомогательное число N:

N =  -    -, где S — условный коэффициент (S ^ 1).

4.   Найти такое число Фибоначчи Fn, чтобы выполнялось неравенство ¥п~і < N ^ ¥п.

_    Ь — а

5.   Определить минимальный шаг поиска т = —-— , где [х\ — бли-

L J

жайшее меньшее целое х.

6.   Выбрать первую точку на отрезке и рассчитать ЦФ /(а).

7.   Перейти к следующей точке, в которой рассчитать /(жі), где точка определяется как х\ = ап + т¥п^2.

8.   Если (шаг удачный) для новой точки f(x\) > /(а), то следующая точка определяется как х2 = х\ + mFn_3; при неудачном шаге — f(xі) < f(a) имеем: х2 = х\ — mFn_3.

9.   Последующие шаги выполняются с уменьшающейся величиной шага, которое для г-го шага будет Ахі = ±т¥п-і^2.

10. Конец работы алгоритма.

Если при выполнении шага значение ЦФ в точке хі+і = Хі + Ах і лучше, то следующий (г +1) шаг выполняется из точки Хі+\ : х,і+2 = Хі+\ + + Ахі+1. Если г шаг неудачный, т. е. /(ж^+і) < f(xi), то следующий (г + 1) шаг выполняется из точки xf. Хі = Хі+\ — Ахі+\. Процесс продолжается, пока не рассмотрены все числа Фибоначчи в отрезке [а, Ь] в убывающей последовательности или по заданию ЛПР.

Рассмотрим поиск на основе метода золотого сечения [109-113].

Он применяется, когда необходимо найти не собственно экстремум, а то значение аргумента функции, при котором выполняется заданное условие, например, f (x) ^ у. Тогда оценить заранее требуемое число измерений невозможно, поэтому нельзя определить и условия первого эксперимента для поиска по методу Фибоначчи. Метод золотого сечения позволяет избавиться от этого недостатка. Здесь также сохраняется условие симметричности последовательных экспериментов, как и в методе Фибоначчи,

т. е. справедливо соотношение (4.1). Выполняется условие

которое означает постоянство отношения длин последовательных отрезков. При использовании метода золотого сечения первое измерение делается

на расстоянии d2 = — от любого края интервала неопределенности (d± =

= Ъ — а). Второе измерение делается симметричным первому. Поэтому места расположения точек поиска определяют по формулам:

Приведем обобщенный модифицированный нечеткий алгоритм метода Фибоначчи и метода золотого сечения:

1.   Получить набор или одно альтернативное решение.

2.   Ввести границы интервала [а, 6], число обращений к модели ср для метода Фибоначчи или гр для метода золотого сечения. Здесь гр = = 0,5(л/5 - 1) « 0,618, Fn = (b — а)/(ёѴі), Ѵі — точка интервала.

3.   Вычислить Ѵ2 = а + А(Ь — а), причем А = Fn_i/Fn для метода Фибоначчи или А = гр для метода золотого сечения.

4.   Вычислить F(V2).

5.   Вычислить Ѵі = а + Ъ — Ѵ2.

6.   Вычислить FiVi).

7.   Если F(Vi) > F(V2), то а := Ь,Ь := Ѵі.В противном случае b := Ѵ2, Ѵ2 = Pi, F(V2) = F(Vi).

8.   Если (b - a) < SVi, конец поиска, иначе вернуться к 5.

9.   Конец работы алгоритма.

Преимущество этих методов в том, что при их. использовании каждый новый эксперимент приводит к сокращению интервала неопределенности.

Рассмотрим ряд численных методов решения инженерных задач. Сущность всех численных методов оптимизации состоит в построении последовательности векторов {Xfe}, где к — шаг поиска, к = 0,1, 2,..., удовлетворяющих условию f(Xk+1) > f(Xk) (в случае поиска максимума) и f(Xk+1) < f(Xk) (в случае минимума). К ним относят методы, требующие для своей реализации вычисления первых производных ЦФ f(X). Известно, что градиент скалярной функции f(X) в некоторой точке Х^ направлен в сторону наискорейшеш возрастания функции. Вектор, противоположный градиенту, Ѵ/(Х&) — антиградиент и направлен в сторону наискорейшеш убывания функции f(X). Наиболее применимы на практике следующие методы:

•    релаксации;

•    градиента;

•    наискорейшеш спуска (подъема).

Метод релаксации наиболее прост. Он заключается в определении направления, вдоль которого ЦФ изменяется наиболее быстро. Для этого в начальной точке поиска определяются производные оптимизируемой f(X) по всем направлениям. Затем выбирается наибольшая по модулю производная и соответствующая ей переменная изменяется до достижения локального оптимума. В новой точке определяются производные по всем остальным переменным, и производится поиск нового локального оптимума и т. д. Скорость движения к локальному оптимуму зависит от выбора величины шага изменения независимых переменных. При «малом» шаге процесс сходится медленно, а при «большой» величине шага возможно блуждание, т. е. проскакивание оптимума. В теории поиск заканчивается, когда все частные производные ЦФ равны нулю. На практике в качестве критерия окончания поиска берется условие:

где S — заданное заранее малое число; т — максимальный шаг поиска.

В градиентном методе движение при поиске точки оптимума осуществляется в направлении наибыстрейшего возрастания ЦФ, т. е. в направлении градиента grad f(X) = Ѵ/(Х). Основное уравнение градиентного поиска оптимума имеет вид:

где hk — длина шага поиска.

Одним из вариантов градиентного метода является равномерный поиск при hk = ho = const. Он гарантирует приближение к экстремуму на расстояние не более /го, хотя затем вызывает блуждания в окрестности экстремума. Существует еще пропорциональный градиентный поиск, когда используют определенные значения коэффициента пропорциональности ak (к = 0,1,...). Применив в начале поиска произвольное или заданное значение а0 ^ 1, на каждом шаге его уменьшают вдвое, пока не получится f(Xk+1) < f(Xk ) (при поиске минимума). Схема такого поиска следующая [112]:

Процесс можно остановить, как только приращение Ак+і ^ До сравняется с заранее заданным. Отметим, что при использовании градиентного метода на каждом шаге меняется значение не одной, а всех независимых переменных. В каждой точке градиент вычисляется заново, а каждый шаг выполняется в направлении наискорейшеш возрастания функции в соответствующей точке.

Опишем модифицированный нечеткий алгоритм сопряженных градиентов (Флетчера-Ривса) [110-112]:

1.   Получить одно или набор альтернативных решений.

2.   Ввести начальный вектор поиска Vq, размерность п, точность е.

3.   Задать шаг поиска г = 1.

4.   Принять вектор Щ, пропорциональный вектору изменения внутренних параметров, Ni = 0. Вектор Ѵі = Ѵі-і - щЩ, где щ — коэффициент, определяющий длину шага на каждой итерации, подбирается экспериментально.

5.   Вычислить вектор gradF(Vi-i).

6.   Вычислить вектор Щ.

7.   Провести одномерный поиск по вектору Ni.

8.   Если і < п, то задать і = і + 1 и перейти к 5, иначе к 9.

9.   Если длина вектора Ni меньше е, конец поиска, иначе і = 1 и перейти к 4.

10. Конец работы алгоритма.

В методе наискорейшего подъема объединены основные идеи методов релаксации и градиента. После нахождения градиента анализируемой функции в начальной точке осуществляется продвижение, до тех пор пока функция f(X) не перестанет возрастать. При использовании метода наискорейшего подъема объем вычислений уменьшается и поиск ускоряется. Для окончания процесса используем выражение

где xj^a, £j,b — координаты начальной и конечной точек подъема.

Приведем модифицированный нечеткий алгоритм метода наискорейшего спуска или покоординатного спускаГаусса-Зейделя [110-113], когда направление шага на каждой итерации выбирается вдоль координатной оси и выполняется однопараметрическая оптимизация ЦФ поочередно по всем осям:

1.   Получить одно или набор альтернативных решений.

2.   Ввести Ѵо, размерность п, точность е.

3.   Присвоить і = 1 (і — номер итерации).

4.   Присвоить j = 1 (j—номер переменной функции F(V?)).

5.   Выполнить одномерный поиск ЦФ F (V}).

6.   Если j < п, то j = j + 1 и перейти к 5, иначе к 7.

7.   Если изменение координат меньше е, конец работы алгоритма, иначе і = і + 1 и перейти к 4.

8.   Конец работы алгоритма.

Теперь приведем нечеткий объединенный алгоритм метода наискорейшего спуска на основе вектора градиента и антиградиента [110-113]:

1.   Получить одно или набор альтернативных решений.

2.   Задать Vq, размерность п, точность е.

3.   Считать г = 1.

4.   Задать j = 1.

5.   Вычислить составляющую вектора градиента д¥(Ѵ)/дVj в точке Ц-1.

6.   Если j < п, задать j = j + 1 и перейти к 5, в противном случае к 7.

7.   Выполнить одномерный поиск по аншградиенту.

8.   Если изменение координат меньше е, конец поиска, иначе г = г + 1 и переход к 4.

9.   Конец работы алгоритма.

Для решения инженерных задач с большим числом переменных используют статисти ческие методы оптимизаци. Основным их отличием от детерминированных методов является введение элемента случайности в процесс поиска экстремума. Для характеристики статистических методов оптимизации используются понятия синергетики, накопления, адаптации, самообучения. Накопление — это выборка информации на основе пробных шагов о поведении ЦФ вблизи рассматриваемой точки для выбора направления поиска. Самообучение — это управляемый процесс изменения вероятностных свойств случайности поиска в интеллектуальных ИС. Выделяют следующие основные статистические методы оптимизации [110]: простые, с накоплением, с адаптацией, с самообучением.

Рассмотрим эти статистические методы оптимизации и покажем их взаимосвязь с ЭМ. В статистических методах оптимизации с накоплением с помощью пробных шагов собирается информация о поведении ЦФ в некоторой окрестности точки Затем находится направление для рабочего шага, близкого к антиградиеншому, причем степень близости зависит в основном от числа пробных попыток. Основной в этом классе — метод наилучшей пробы. Из точки х делается q случайных независимых попыток с заданным шагом. Для каждой пробы вычисляется ЦФ и шаг совершается в направлении той пробы, что привела к наилучшему значению ЦФ. Очевидно, что при q оо мы найдем оптимальное значение ЦФ. Важным отличием этого метода является возможность работы при q < п, где п — число переменных оптимизируемой функции.

В статистических методах оптимизации с адаптацией параметры поиска изменяются в процессе оптимизации. Введение автоматически изменяющегося масштаба поиска улучшает сходимость и точность метода. Масштаб поиска изменяется, чтобы на значительном расстоянии от экстремума шаг поиска увеличивался, а при приближении к нему уменьшался. Автоматическая настройка масштаба шага часто реализуется на использовании результатов последней итерации. Увеличение масштаба шага осуществляется умножением его на коэффициент роста d\, а уменьшение —

делением на d2, причем d\ ^ d2 ^ 1. Основное условие, которое необходимо соблюдать во всех случаях, это избыточность масштаба. При большом масштабе поиск становится менее чувствительным к погрешностям вычислений [110].

В статистических методах оптимизации с самообучением процесс случайного поиска состоит в перестройке вероятностных характеристик случайного вектора для увеличения числа эффективных итераций и уменьшения неэффективных. В таких алгоритмах единичный случайный вектор £ перестает быть равновероятным, а в процессе поиска получает определенное преимущество в направлении наилучшеш шага. Когда избранное направление не приводит к успеху, алгоритм с самообучением ищет другое. На начальных итерациях поиск эффективного направления начинается в равновероятной зоне, а затем с набором информации о характере ЦФ последовательно приобретает преимущество в выборе наилучшеш направления. В общем виде такой алгоритм описывается рекуррентной формулой [110]:

где Pfe (С) — распределение случайного вектора £ на к-м шаге. Оно является некоторой функцией распределения этого вектора на предыдущем шаге (Pfe_i) вместе с приращением Af(Xk-i).

Выделяют статистические методы оптимизации координатного и непрерывного самообучения. В первом методе вводится постоянный параметр памяти путем задания вероятности выбора удачного шага. Он определяется функцией некоторого параметра памяти Щ, причем:

Алгоритм самообучения реализуется путем изменения параметра памяти:

где S — шаг памяти (<5 > 0), отметим, что при <5 = 0 самообучения нет. Если шаг окажется неэффективным, то вероятность выбора этого направления при следующем шаге уменьшается, и наоборот. Алгоритмы такого типа, случайно определив удачное направление поиска, стараются его зафиксировать. Во втором статистическом методе оптимизации улучшается поиск при изменении градиентного направления функции. Направление случайного шага представляется в виде векторной функции / = W), где h — размер шага, £ — единичный случайный вектор, равномерно распределенный в пространстве параметров; ijj — некоторая непрерывная по модулю и направлению единичная функция двух параметров ей W, удовлетворяющая требованиям [110]:

• 0) = ё, т. е. при нулевом значении обучения поиск должен быть равновероятным;

•    математическое ожидание случайного шага совпадает с направлением вектора обучения;

•    дисперсия случайного шага Т)[ф(е,ѴѴ)\ = 1/\W\.

Отметим, что чем больше модуль вектора памяти \W\, тем меньше дисперсия распределения случайного шага. При выполнении указанных условий функция реализует пространственное распределение случайного шага, причем это направление по мере накопления опыта приближается к анти- градиентному.

Опишем кратко основной метод случайного поиска — метод Монте- Карло [110-113]. При этом необходимо найти экстремум V(F) в заданной области допустимых параметров Vmin ^ V ^ Утах с точностью интервала неопределенности е. Пусть допустимая область по одному из параметров D = 14іах — Vmin. В методе Монте-Карло вырабатывается псевдослучайный вектор параметров с равномерным распределением. Тогда вероятность непопадания в область экстремума за один шаг равна Рі (ММК) = І — е/D. Соответственно за п шагов алгоритма

а вероятность попадания в область минимума

Следовательно, число G генераций случайного вектора, необходимых для уточнения минимума с точностью е, с заданной вероятностью равно

В случае к внутренних, параметров ЦФ число генераций этого вектора увеличится в \/к раз и составит п\/к. А общее число обращений к модели метода Монте-Карло за G генераций составит

и определит условие применимости метода при одинаковом числе итераций. Метод Монте-Карло эффективен при большом числе испытаний G « « 1000. При повышенной точности е число испытаний резко возрастает и метод Монте-Карло неэкономичен. В практических инженерных задачах необходимо комбинировать ГА, статистические и детерминированные методы поиска.

Рассмотрим методы поиска в глубину, в ширину, с возвратом,, горизонта и поиск на И-ИЛИ деревьях. Эти методы основаны на анализе движений по дереву решений, пока это возможно. Отметим, что эти методы могут выполняться не только на основе случайного поиска, но и с использованием заданных эвристик.

При неудачном шаге метода поиска с возвратом в пространстве параметров выбирает точку ж0 и задает постоянный шаг h. Из этой точки

в случайном направлении, определенном случайным единичным вектором £ = (гі, £2, • • •, £п), осуществляется шаг h и вычисляется значение ЦФ в новой точке х\. Если при поиске минимума значение ЦФ в х\ уменьшилось, то новый шаг из х\ осуществляется в случайном направлении. При неудачном шаге (возрастании ЦФ) происходит возврат в начальную точку и осуществление нового пробного шага в случайном направлении. Метод поиска с возвратом можно представить в виде рекуррентного соотношения [110]

Метод поиска с возвратом может выполняться в двух направлениях, определенном случайным вектором и противоположным ему с заданным шагом Ь. Тогда значения ЦФ определяются в точках х± у2 = xq =Ь b и в сторону уменьшения осуществляется рабочий шаг на величину h. После удачного шага можно продолжать поиск в том же направлении, а после неудачного — обращаться к случайному вектору, т. е. «штрафовать случайность». В этом методе из-за введения случайности движение к экстремуму производится не только вдоль координат, но и вдоль любого направления.

Комбинаторная задача, к которой применим метод поиска с возвратом, может быть описана следующим образом.

Даны V линейно упорядоченных блоков В±, £>2, • • •, Bq и требуется построить вектор А = (жь х2і..., хп), где (жь ..., хі е В1, хі+1 ,...,хт £ Е В2} ..., хс,..., хп Е Bq), удовлетворяющий заданному множеству условий и ограничений. Предположим, что найдено распределение новых к — 1 блоков X = {жі, х2}..., Xk-iтогда заданное множество условно ограничивает выбор следующего к блока некоторым множеством St С X. Если St — непустое, то в качестве х^ выбирается наименьший элемент Sk и осуществляется переход к Sk+i и т.д. Если Sk = 0, то происходит возврат к предыдущему этапу и удаление элемента х^-і — того элемента из Sk-i, который непосредственно следует за удаленным.

Приведем один из возможных алгоритмов поиска с возвратом:

1.   Начало положить к = 1, S± = В±.

2.   Если Sk = 0, то перейти к 5. Иначе положить Хк равным наименьшему из элементов Sk.

3.   Проверка: закончен ли поиск. Если к < п, то перейти к 4. Если к = п, то записать £>i, B2j..., В к как решение. Если необходимо найти все решения, то к = к +1 и перейти к 5, иначе — конец работы алгоритма.

4.   Увеличить к на 1, вычислить Sk и переход к 2.

5.   Если к = 1, то дальнейшее передвижение назад невозможно; конец работы алгоритма. При этом найдены определенные решения, либо их нет. Если к > 1, то уменьшить к на 1, положить Sk = Sk — {хк} и перейти к 2.

6.   Конец работы алгоритма.

Двунаправленный поиск моделирует процесс, при котором поиск осуществляется одновременно из начальной и конечной точки. Направленность

поиска — это степень, в которой поиск является сфокусированным в направлении дели и не блуждает по бесперспективным направлениям. Она определяется выражением:

где L— длина найденного пути к дели (количество просмотренных объектов), Х! С X — общее число объектов, определенных в ходе поиска.

Идея метода поиска в глубину состоит в том, чтобы в каждой исследуемой вершине дерева решений выбирать один из возможных путей

и исследовать его до конца. Другие пути при этом не рассматриваются, пока сохраняется возможность получить локальный оптимум, исследуя выбранное направление. Пример схемы поиска в глубину показан на рис. 4.2. Здесь знак (*) означает, что задача поиска решена; где 0,..., 9 — исследуемые вершины дерева решений.

 

Основной недостаток метода поиска в глубину заключается в том, что при исследовании дерева решений с большой вероятностью можно пройти мимо той ветви, на которой раньше всего появляется локальный оптимум. Временная сложность алгоритма метода поиска в глубину « 0(п)^г0(п2).

При использовании метода поиска в ширину ветвление происходит от уровня к уровню. Причем если на первом уровне начальная задача разбивается на подзадачи, то каждая из них исследуется раньше, чем задачи 2-го уровня. Задачи первого уровня, которые трудны для разрешения, разбиваются на подзадачи уровня 2, и процесс продолжается аналогично. Примерный вид дерева решений при методе поиска в ширину показан на рис. 4.3. Временная сложность алгоритма метода поиска в ширину « О (п2) Ч- О (п4).

Рассмотрим метод горизонта [114]. Это метод поиска квазиоптималь- ных решений, заключающийся в ограничении глубины просмотра в каждой

точке дерева решений. Он позволяет достигать промежуточной дели, а затем оценивает дальнейшие возможности и продолжает или усовершенствует процесс поиска. Рассмотрим на примере основную идею реализации метода. Пусть в блоках разбиения расположено несколько вершин графа и требуется разместить еще заданное подмножество вершин. На рис. 4.4 показан граф G = (X, 17), |Х| = 9, который необходимо разбить на три части, причем, частичное разбиение уже выполнено. Если для помещения в блок выбирается претендент, наиболее связанный с ранее размещенными, то нет смысла пробовать размещать его во все свободные блоки. Имеет смысл определять для размещения «перспективные» блоки и анализировать только процесс расположения в них вершин графа. Соответственно определение перспективных блоков зависит от целевой функции. При минимизации суммарного количества внешних связей можно, например, ограничить «горизонт видимости» путями длины два, три или четыре с ранее установленными вершинами.

Например, на рис. 4.4 вершины х\, ж5 размещены в G\, — в G2, — в G3. В первом блоке должно быть 4 вершины, во втором—2, в третьем—3. Горизонт здесь будет состоять из путей длины 2. Работу алгоритма начинаем с анализа вершин х^, ж*4, которые связаны с ж 5. Если горизонт состоит из пути длины 1, то более предпочтительна для помещения в блок вершина х^.

При увеличении горизонта до двух в блок Gі помещаем х± и х®. Продолжая аналогично, получим, что в G2 попала вершина х$, а в G3 — х2, хд, при этом К = 18. Окончательное разбиение графа G на три части показано на рис. 4.5.

Временная сложность алгоритма « 0(п)-і-0(п4). Как видно, временная сложность алгоритма и точность получения результата находятся как бы

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

При решении инженерных задач большой размерности часто применяется разбиение задачи на составляющие части. В этом случае выделяют три способа ветвления дерева решений: И; ИЛИ; комбинация И-ИЛИ [37]. Пусть у нас имеется задача <5, подлежащая разбиению на подзадачи <3і, <52, Qз (рис. 4.6). Если для решения <5 необходимо решить все подзадачи <3і, <52, Qз, Q4, то это — ветвление И. Если решение <5з возможно через решения <3б или <57, то это — ветвление ИЛИ. Примером ветвления (поиска) И является одновременное решение всех подзадач. Примером поиска ИЛИ является решение одной или другой подзадачи.

В соответствии с вышесказанным можно условно выделить три типа поисковых методов [17, 19, 89]:

•    вычислительные — подразделяются на два основных класса:

A)   непрямые методы — они находят локальные экстремумы, решая обычно множество линейных или нелинейных уравнений. Данные

методы находят экстремум функции, анализируя ограниченное пространство точек во всех направлениях;

B)   прямые методы — осуществляют поиск оптимума путем градиентных алгоритмов. Уже для двух локальных оптимумов это большая проблема — найти лучшее решение, а для многоэкстремальных схем применение этих, методов затруднительно. Сейчас применяются методы линейного, нелинейного и динамического программирования;

•    невычислительные;

•    случайные:

C)   чисто случайный поиск;

D)   генетические алгоритмы.

Опишем модифицированный алгоритм общей нечеткой стратегии решения инженерных задач на основе комбинированного поиска:

1.   Выбрать начальное приближение (решение инженерной задачи).

2.   Определить динамику ЦФ от времени или числа элементов математической модели.

3.   Определить вектор направления движения.

4.   Выполнить оптимальный шаг по выбранному направлению — одномерный поиск.

5.   Если ЦФ —» min (при минимизации), то перейти к 3. Иначе перейти к 6.

6.   Если выходные параметры задачи удовлетворяют заданным требованиям, то окончить оптимизацию. В противном случае изменить ЦФ, весовые коэффициенты, параметры, ввести несколько уровней адаптации и перейти к 3.

7.   Конец работы алгоритма.

Для определения глобального минимума ЦФ в многоэкстремальных задачах предлагается:

•    использовать возможности ЭМ;

•    реализовать совместные схемы поиска с ГА;

•    учитывать знания о решаемых задачах, позволяющие связать возможности значения ЦФ с известными значениями в точках реализованных испытаний;

•    изменять начальную точку спуска методом проб и ошибок, градиентными методами, совместными методами ЭМ и локального поиска;

•    использовать различные архитектуры совместной эволюции и статистические методы поиска, позволяющие находить несколько областей локальных экстремумов.

Предлагается ряд основных стратегий взаимодействия методов поиска и эволюционного моделирования:

•    стратегия «поиск-эволюция»;

•    стратегия «эволюция-поиск»;

•    стратегия «поиск-эволюция-поиск»;

•    стратегия «эволюция-поиск-эволюция».

Заметим, что иерархически можно строить стратегии такого типа любого уровня сложности. Например, «эволюция-поиск-эволюция-поиск- эволюция-поиск» и т.д. Отметим, что такое иерархическое наращивание зависит от наличия вычислительных ресурсов и времени, заданного на получение окончательного решения.

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

Во втором случае конструируется популяция и реализуется одна из схем эволюции. Лучшее решение анализируется и улучшается (если это возможно) одним из алгоритмов поиска. Далее процесс выполняется, как в первом случае. В остальных случаях процесс поиска результатов выполняется аналогично.

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