В Камаев - Технологии программирования

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

В 1983 г. В.В. Костериным была успешно применена морфологическая таблица для синтеза идей построения алгоритма нелинейного программирования поиска глобального экстремума функций многих переменных на сетке кода Грея. Алгоритмы нелинейного программирования предназначены для поиска экстремумов функций многих переменных. В методах прямого поиска экстремум выявляется путем расчета множества точек функции при аргументах, определяемых самим алгоритмом поиска. В табл. 2.2 приведена данная морфологическая таблица, которая содержит классификационные признаки отдельных механизмов алгоритмов нелинейного программирования на уровне основных принципов. Приведенные классификационные признаки выделялись по основным функциональным признакам отдельных механизмов. Каждому классификационному признаку соответствует множество реализаций механизмов в виде значений классификационных признаков.

Интересно отметить, что число возможных реализаций алгоритмов нелинейного программирования по этой таблице составляет N = 5*6*8*5*7*7*6 = 352800, что значительно превышает число опубликованных методов (около 2000)!

Таблица 2.2

Морфологическая таблица принципов функционирования алгоритмов нелинейного программирования

Значения классификационных признаков классификационного признака "Механизм начальной точки поиска":

признак 1.1 — из точки, указанной пользователем;

признак 1.2 — из средней точки области определения;

признак 1.3 — из точки на границе области определения;

признак 1.4 — из случайной начальной точки поиска;

признак 1.5 — начальная точка поиска не задается.

Значения классификационных признаков классификационного признака "Первичное зондирование гиперповерхности":

признак 2.1 — в виде большого числа случайных точек, зондирующих всю гиперповерхность;

признак 2.2 — поочередные спуски из ряда случайных начальных точек;

признак 2.3 — конкурирующие спуски из добавляемых случайных точек;

признак 2.4 — зондирование гиперповерхности случайными точками с выявлением и более тщательным исследованием "подозрительных областей";

признак 2.5 — сканирование всей гиперповерхности с использованием различных разверток, например Пеано;

признак 2.6 — отдельный механизм начала поиска отсутствует.

Значения классификационных признаков классификационного признака "Стратегия шагов поиска":

признак 3.1 — один шаг;

признак 3.2 — последовательные шаги до выявления экстремума;

признак 3.3 — осуществлять все шаги по одному и тому же механизму;

признак 3.4 — переключать механизмы шагов от глобального метода до локального;

признак 3.5 — переключать механизмы шагов от глобальных далее до усредненных и до локальных;

признак 3.6 — переключать механизмы шагов по эвристическим правилам;

признак 3.7 — малое количество последовательных шагов из ограниченного ряда лидирующих конкурирующих начальных точек;

признак 3.8 — шаги поиска отсутствуют.

Значения классификационных признаков классификационного признака "Направление поиска на шаге":

признак 4.1 — новая точка в направлении аппроксимации градиента, построенного на основе данных текущей и предшествующей пробной точек;

признак 4.2 — по результатам обработки небольшого числа перспективных точек, полученных на предшествующих шагах;

признак 4.3 — по результатам анализа функции, аппроксимирующей случайные точки в перспективном направлении;

признак 4.4 — зондирование гиперповерхности большим количеством случайных точек и последующим построением аппроксимирующей функции;

признак 4.5 — вдоль границы области определения целевой функции;

признак 4.6 — механизм отсутствует.

Значения классификационных признаков классификационного признака "Механизм стратегии шага поиска":

признак 5.1 — пробные точки только на расстоянии предполагаемого экстремума;

признак 5.2 — пробные точки на большем расстоянии, чем предполагаемый экстремум;

признак 5.3 — пробные точки на расстоянии, несколько меньшем, чем у предполагаемого экстремума;

признак 5.4 — объединение признаков 5.1 и 5.2;

признак 5.5 — объединение признаков 5.1, 5.2 и 5.3;

признак 5.6 — совмещение поиска направления и расстояния до экстремума;

признак 5.7 — разделение поиска направления и расстояния до экстремума.

Значения классификационных признаков классификационного признака "Механизм самообучения":

признак 6.1 — сужение границ поиска по мере продвижения к экстремуму;

признак 6.2 — постепенное повышение точности поиска;

признак 6.3 — выявление формы гиперповерхности по результатам предшествующих шагов и переход на специальный механизм уточнения экстремума;

признак 6.4 — выявление формы гиперповерхности по результатам предшествующих шагов и переход на специальный механизм продвижения вдоль оврагов;

признак 6.5 — выявление формы гиперповерхности по результатам предшествующих шагов и отказ от текущего найденного экстремума;

признак 6.6 — изменение плотности вероятности случайных точек для разных зон поиска;

признак 6.7 — механизм отсутствует.

Значения классификационных признаков классификационного признака "Механизм завершения поиска":

признак 7.1 — не выявляется направление улучшения функции на следующем шаге;

признак 7.2 — израсходован ресурс времени;

признак 7.3 — достигнуто заранее заданное значение целевой функции;

признак 7.4 — исчерпаны возможности алгоритма поиска экстремума;

признак 7.5 — выполнено заранее заданное количество шагов поиска;

признак 7.6 — нет улучшений в "дальней" и "близкой" окрестностях.

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