Мифы о звукоизоляции Как построить дом из пеноблоков Как построить лестницы на садовом участке Подбираем краску для ремонта Каркасные дома из дерева |
Главная » Метод проб 1 2 3 4 5 В результате анализа вышеприведенных определений и разнообразных точек зрения на МПиО, как представляется, можно сделать следующие предварительные выводы: а) в литературе удалось найти лишь единственное формальное определение МПиО (Л.А.Растригиным), определяющее его как слепой поиск; б) достаточно многочисленные вербальные определения и трактовки МПиО неоднозначны - в них, как правило, не рассматривается его внутренняя структура, в частности, не конкретизируется и не учитывается фактор фундаментального значения: наличие либо отсутствие памяти в процедуре генерации пробы; таким образом, в значительном числе интерпретаций не делается различия между вариантами МПиО без памяти ( слепого поиска) и с памятью ( направленного поиска), тогда как во многих других случаях МПиО рассматривается конкретно как слепой (т.е. МПиО в узком смысле / в узкой трактовке) либо как направленный (т.е. МПиО в расширенном смысле / в расширенной трактовке); в) указанная многозначность трактовок термина МПиО приводит к многочисленным недоразумениям при его использовании в различных отраслях знания, в частности - к суждениям о его эффективности в диапазоне от резко отрицательных до весьма положительных (что можно объяснить именно различной интерпретацией МПиО, подразумеваемой тем или иным автором); г) поскольку в работах У.Р.Эшби, Л. А.Растригина и других показано, что МПиО является элементом более широкой отрасли знания: теории управления и, конкретнее, ее важных составляющих - технической кибернетики, теории оптимизации, теории поисковой оптимизации и теории случайного поиска, следует сравнить его с соответствующими методами, предложенными в их рамках. Для этого рассмотрим последние несколько подробнее, имея в виду, что, развитые в области технической кибернетики, эти методы оказались сравнительно мало известными и почти не использующимися в биологических областях естественных наук. 3. Оптимизация, поисковая оптимизация и случайный поиск 3.1. Оптимизация [79] Оптимизация (от лат. optimum - наилучшее) - процесс нахождения экстремума (глобального максимума или минимума) определенной функции или выбора наилучшего (оптимального) варианта из множества возможных [80]. Оптимизация - минимизация или максимизация определенным образом заданного критерия, который характеризует качество или эффективность принимаемого решения [5]. Оптимизация - итеративный процесс улучшения решения задачи, сформулированный в постановке поиска экстремума целевой функции [81]. Данные определения отражают наиболее широко распространенные представления об этом понятии. Иногда после слов функции добавляют или функционала (переменной величины, заданной на множестве функций), что несколько расширяет определение, не меняя по существу его смысла. Анализ приведенных выше и иных определений термина оптимизация позволяет выделить в этом термине две основные составляющие: 1) указание на наличие моделирующего некоторую реальность целевого критерия (целевой функции / целевого функционала, критерия оптимизации, экстремальной характеристики, показателя экстремума, критерия качества и др.), экстремальное (максимальное или минимальное) значение которого необходимо либо однократно определить (если его положение не зависит от времени), либо перманентно отслеживать (в противном случае); 2) указание на наличие соответствующих средств определения экстремума данного целевого критерия: при наличии достаточной информации о виде оптимизируемой функции вполне формальных, при ее отсутствии - поисковых. Подобная структура термина оптимизация задает целый спектр возможных комбинаций- двоек : конкретные свойства целевого критерия - конкретные свойства алгоритма определения экстремума . Так, целевая функция оптимизируемого объекта либо может быть выражена математически, либо может и не иметь математического представления (в этом случае она лишь должна быть измерима). Целевая функция может зависеть от одной либо от многих переменных. При этом переменные могут относиться как к множеству целых чисел, так и к множеству действительных чисел. Целевая функция может иметь либо единственный локальный экстремум на заданном множестве переменных (который в этом случае совпадает с глобальным экстремумом), либо множество локальных экстремумов (в этом случае она называется многоэкстремальной, и возникает дополнительная задача нахождения среди последних глобального экстремума). Целевая функция может быть не только экстремального типа: возможно наличие функциональных ограничений а) типа равенств и б) типа неравенств. Необходимо также отметить, что и допустимое множество значений переменных в общем случае также ограничено. Кроме того, целевая функция и ограничения типа равенств и типа неравенств могут быть как статическими, так и динамическими (зависящими от времени). Наконец, существуют задачи оптимизации, в которых задаются сразу несколько критериев экстремального типа - это многокритериальные задачи, требующие для своего решения использования специальных методов. В простейшем случае формальная постановка задачи оптимизации записывается следующим образом. Критерий оптимизации обычно означают буквой Q, а его зависимость от принимаемого решения - в виде скалярной функции Q(x), где x = (x1,..., xixn) - вектор оптимизационных переменных, характеризующий принимаемое решение. Это решение всегда как-то ограничено различными внешними обстоятельствами (например, ресурсами), в результате чего возникает понятие множества допустимых решений S , каждый элемент x которого приемлем для решения задачи оптимизации, т.е. x е S. Тогда задачу оптимизации (конкретно - минимизации) можно записать в виде: Q(x) => min , т.е. функцию Q(x) следует (знак == в формуле) минимизировать (для максимизации используется знак max ), варьируя вектор x в пределах множества S (x е S). Решение этой задачи называют оптимальным и обозначают x . Это решение обладает следующим очевидным свойством: Q(x ) = min Q(x). Исходя из характера и особенностей представления целевого критерия, и выбирается соответствующий алгоритм решения задачи оптимизации. Для случаев, когда существует математическое выражение целевой функции и ограничения отсутствуют, - это методы спуска (последовательные итерационные шаги в направлении градиента/антиградиента оптимизируемой функции): градиентный метод, обобщенный метод Ньютона, методы сопряженных направлений и т. п. Если ограничения имеются, возникает задача нахождения условного экстремума, которая решается как методами, непосредственно обобщающими методы нахождения безусловного экстремума, так и специальными методами. Эти последние развиты в группе смежных научных дисциплин, которую исторически принято называть математическим программированием (данное название связано с тем, что целью решения задач является выбор программы действий: не путать с технологией написания компьютерных программ). В состав этой группы входят выпуклое, линейное, кусочно-линейное, квадратичное, дискретное или целочисленное, динамическое, стохастическое, нелинейное и т. п. программирование [82]. Если же необходимо найти глобальный экстремум многоэкстремальной целевой функции, чаще всего используют сочетание стохастического метода Монте-Карло и какого-либо метода спуска. Случаи, когда математическое выражение целевой функции либо отсутствует вообще (и можно ее только каким-то образом измерять), либо целевая функция вычисляется математически (точнее, на компьютере) как последовательность сложных нелинейных математических преобразований, требуют использования поисковых оптимизационных методов (см. ниже, подраздел 3.2). В последние годы усилился интерес к построению оптимизационных моделей различных сложных процессов и явлений реального мира, как природных, так и антропогенных, имманентными элементами которых являются механизмы, реализующие процессы оптимизации тех или иных целевых критериев [83,84,7]. Включение этих элементов в состав указанных моделей отражает наиболее глубинные закономерности адаптивного поведения сложных систем в Природе и Обществе. 3.2. Поисковая оптимизация и случайный поиск [85] Поисковая оптимизация - последовательность действий, реализующих неизвестную a priori траекторию движения к экстремуму оптимизируемой функции: класс итеративных процессов оптимизации, использующийся в тех случаях, когда аналитическая зависимость целевой функции от оптимизационных переменных либо неизвестна, либо ее вычисление представляет собой сложную задачу [86,87]. В обоих случаях от целевой функции Q(x) требуется только возможность измерения (вычисления) в области определения ее переменных x . Поисковый метод описывается итеративным процессом (рекуррентным выражением), определяющим переход от (N-1)-ro шага к N-му: xN = xN-1 + AxN, причем шаг AxN зависит от ситуации в точке xN-1; в простейшем случае AxN = <р(xN-1), где <р - алгоритм поискового процесса оптимизации. В более сложном случае адаптивной поисковой оптимизации сам вид и параметры функции < зависят от более глубокой предыстории поиска [88,89]. Таким образом, когда количество начальной информации об объекте недостаточно для достижения цели управления, естественный путь восполнения - определение её в процессе поиска. Поисковая оптимизация применяется для решения как статических задач (целевая функция в которых не зависит от времени), где ее целесообразно называть собственно поисковой оптимизацией, так и динамических (в последнем случае ее традиционно называют экстремальным управлением объектом, характеристики которого от времени зависят). Теория поисковой оптимизации была разработана в 1960-1980-х гг. рядом отечественных и зарубежных ученых, среди которых можно выделить Д.И.Батищева, Р.Буша, Ч.С.Дрейпера, Ю.М.Ермольева, А.Г.Ивахненко, В.В.Казакевича, А.А.Красовского, И.Т.Ли, Ф.Мостеллера, Ю.И.Неймарка, А.А.Первозванского, Л.А.Растригина, Р.Г.Стронгина, А.А.Фельдбаума, Я.З.Цыпкина, У.Р.Эшби, Д.Б.Юдина и др. (см., например, [90-98,87,99-102]). Начиная с 70-х гг. получило довольно широкое распространение одно из ее направлений, связанное с методологией синтеза новых алгоритмов на базе бионических представлений. В частности, использования для этого моделей эволюции живой природы: эволюционного подхода (Г.Бремерманн [103]), эволюционного моделирования (Л.Фогель, А.Оуэнс, М.Уолш [104], И.Л.Букатова [105,106]), эволюционного формообразования (А.И.Половинкин [107]), эволюционной глобальной оптимизации (Э.М.Куссуль, А.Лук [108,109]; Р.Джарвис [110]), эволюционной адаптации коллективом вероятностных автоматов (Ю.И.Неймарк с соавт. [111-113]), эволюционной стратегии (И.Рехенберг, Г.-П.Швефель, К.Беллман, Дж.Борн [114-116]), генетической адаптации (У.Петерзон, К.Восс, К.Вебер [117,118]), генетических алгоритмов (Дж.Холланд, D.E.Goldberg, Д.И.Батищев, В. М. Курейчик, С. А.Исаев и др. [119-123]) и тому подобных. Использование именно эволюционной и генетической терминологии оказалось удобным языком при синтезе широкого спектра новых разновидностей алгоритмов поисковой оптимизации. Среди авторов бионических работ в области поисковой оптимизации, опирающихся на аналогии с иными биологическими объектами, следует упомянуть В.Ф.Коропа, Л.Н.Фицнера, Л.А.Растригина, Н.П.Дидиченко и др. (см., напр., [124-132]). Методы собственно поисковой оптимизации подразделяют на две основные группы: 1) методы, использующие как пробные, так и рабочие шаги поиска; 2) методы, в которых пробные и рабочие шаги совмещены. При экстремальном управлении пробные и рабочие шаги совмещены всегда. Кроме того, методы поисковой оптимизации различаются по способу определения направления движения к экстремуму. Здесь можно выделить два основных подкласса: методы регулярного поиска (Гаусса-Зейделя, градиентный, наискорейшего спуска и т.п.) и методы случайного поиска. Эффективность каждого из них зависит от конкретных условий: формы поверхности целевой функции (наличия гребней, оврагов и т.д.), погрешности ее вычисления/измерения и др. Процесс оптимизации по методу градиента разбивается на два этапа. На первом этапе с помощью пробных шагов производится определение составляющих градиента, т. е. частных производных критерия качества по оптимизируемым переменным. Во время второго этапа совершается рабочий шаг, т.е. производится смещение в направлении обратном градиенту. Новое значение функции качества на каждом шаге поисковой оптимизации находится после определения всех очередных новых значений варьируемых переменных, и после проверки выполнения ограничений по каждой переменной. Метод случайного поиска использует для выявления предпочтительных состояний пробные смещения от текущей точки в случайных направлениях. Простейший алгоритм случайного поиска с линейной тактикой использует только два оператора: случайного шага (£) и повторения предыдущего шага. Действие каждого из этих операторов может привести к одному из двух результатов: минимизируемая функция на N-м шаге поиска QN либо уменьшится, либо не уменьшится. В зависимости от результата включается тот или другой оператор (в первом случае - повторить шаг , во втором - £). В более сложных случаях алгоритмы случайного поиска обладают свойством адаптивности, реализуемом с помощью запоминания как траектории поискового процесса (значений поисковых переменных и целевых функций, а также соответствующих ограничений), так и параметров самого алгоритма (величины и направления поискового шага, глубины памяти и т. п.) [4]. При собственно поисковой оптимизации существует задача определения момента, когда поиск следует завершить. Поскольку значение экстремума целевой функции a priori неизвестно, определять этот момент с помощью задания величины допустимого отклонения от цели невозможно. Но это можно делать по достижению числом последовательных неудачных поисковых шагов (или проб) некоторого заранее определенного предела. Последнее можно интерпретировать как признак того, что поиск производится вблизи экстремального значения целевого критерия. Указанная задача отсутствует в системах экстремального управления, отслеживающих экстремум оптимизируемого критерия перманентно. Но здесь возникает новая проблема выбора наилучшего соотношения между двумя противоречивыми требованиями: минимизации времени переходного процесса в область экстремума из произвольной точки (так называемых потерь на поиск) и минимизации отклонения оптимизируемой величины от экстремального значения в установившемся режиме (так называемых потерь на рысканье). Потери на поиск уменьшаются с ростом величины поискового шага. Однако потери на поиск характеризуют работу алгоритма лишь на подходе к экстремуму. Алгоритм, имеющий наименьшие потери на поиск, быстро выведет систему в район экстремума. Но на этом не заканчивается экстремальное управление: от алгоритмов поиска требуется надежная работа в районе экстремума, позволяющая отслеживать его блуждание или уплывание . Потери на рысканье существенно зависят от величины поисковых шагов, поэтому для снижения этих потерь размеры поисковых шагов следует уменьшать. Это находится в противоречии с требованием быстродействия (для повышения которого величину рабочего шага нужно, наоборот, увеличивать). Отсюда следует, что выбор компромиссных значений величин шагов на всей траектории поиска следует проводить адаптивно, с учетом особенностей поведения оптимизируемого объекта в процессе поиска [133]. Таким образом, экстремальное управление осуществляют в условиях неопределенности в отношении поведения объекта управления, решая в общем случае как задачу поиска -реализации перемещения к области экстремума в пространстве регулируемых координат (при наличии помех, возмущений и инерционности объекта оптимизации), так и задачу организации устойчивого движения ( рысканий ) системы вблизи точки экстремума. При теоретических исследованиях и практических разработках систем экстремального управления - преимущественно в области технической кибернетики и ее приложений -выявлен ряд результатов, относящихся к особенностям структуры и соотношений параметров в таких системах. Эти результаты позволяют свое перенесение и на иные отрасли знания, модели процессов в которых могут быть интерпретированы как поисковые оптимизационные и адаптивные [134-136,6-10]. 3.3. Адаптивный случайный поиск Простейший пример метода случайного поиска рассмотрен выше. В более сложных вариантах этот алгоритм обладает свойством адаптивности, реализуемом с помощью запоминания как траектории поискового процесса (значений поисковых переменных и целевых функций, а также соответствующих ограничений), так и параметров самого алгоритма (величины и направления поискового шага, глубины памяти и т.п.). Именно это свойство делает его весьма эффективным средством решения сложных экстремальных задач самого различного типа. Более того, именно механизм адаптивного случайного поиска является средством - причем, по моему мнению, единственно адекватным - моделирования поведения сложных природных систем. Действительно, довольно трудно представить себе некоторый живой объект, параметры адаптивного поведения которого (например, значение градиента целевой функции) рассчитывались бы в каком-то гипотетическом вычислительном блоке (что необходимо для любого регулярного метода оптимизации). Применительно же к адаптивному случайному поиску - это вполне реально, поскольку он не требует никаких подобных вычислений, а оценивает искомый градиент на базе нескольких имеющихся конкретных реализаций целевой функции (экстремального вида). Добавлю для читателя, знакомого с теорией автоматов, что алгоритм случайного поиска легко формулируется на языке вероятностных автоматов - это просто два разных языка описания одной и той же сущности. Адаптивный случайный поиск по определению всегда содержит, помимо вероятностной, существенную регулярную составляющую. Это может, в частности, выражаться в различии вероятностей выбора величин приращений по каждой из координат поискового пространства Е, (т.е. поиск осуществляется не в гипершаре, а в гиперконусе), в ненулевой глубине памяти алгоритма адаптации и т. п. 3.4. Память алгоритма как основа классификации методов поисковой оптимизации Любая схема поисковой оптимизации представляет собой контур, содержащий, как минимум, два элемента: блок вычисления целевой функции оптимизации и блок генерирования поисковой переменной (т. е. собственно оптимизатор , в свою очередь, включающий два основных субблока: селектор и генератор ), и связи между ними. Оптимизатор, в соответствии с алгоритмом A (ориентированным на поиск экстремума -например, минимума - целевой функции Q ), вырабатывает (в соответствии с оценкой селектором ©(Q) тенденции изменения Q) на выходе генератора величину (в общем случае векторную) поисковой переменной X . Выходом блока вычисления целевой функции является ее (скалярная) величина Q (X). В зависимости от тенденции изменения последней селектор ©(Q) получаемого результата принимает одно из двух значений: удача либо ошибка - см. рис. 2а. Внешнее дополнение (задание показателя селекции извне, со стороны внешней среды) а) классический контур оптимизации Примечания: Х - вектор поисковых селекции: удача / ошибка б) контур полуоптимизации нных; Q(X) - целевая функция; в (в) - показатель Рис. 2. Схемы поисковой оптимизации: а) типовая и б) полуоптимизации с внешним дополнением . В контуре поисковой оптимизации эти процессы многократно ( по кругу ) повторяются, перманентно отслеживая тем самым минимум целевой функции Q (X). Для удобства поисковые шаги обычно нумеруют, интерпретируя их как дискретное время хода процесса оптимизации. При модельных расчетах в технических приложениях этот процесс останавливают извне, когда считают, что достигнут достаточно успешный результат. При экстремальном управлении натурными техническими объектами этот процесс происходит перманентно. Таким образом, в соответствии с [89], можно записать: где 4я (X)=-0; 1 G (X ) = 0. min: область допустимых значений поисковой переменной X , определяемая системой целевых требований Я (X) и G(X), A - поисковый алгоритм, X* - значение переменной X, соответствующее экстремуму целевой функции Q(X) . Очевидно, что проблема построения зависимостей Q(X) для конкретных приложений выходит за рамки теории поисковой оптимизации, и решается всегда средствами соответствующих прикладных наук. Другое дело - проблема синтеза собственно алгоритма поиска A , встроенного в оптимизатор. Как представляется, к основным особенностям такого алгоритма можно отнести следующие: 1) в простейшем случае он фиксирован, т.е. имеет постоянную структуру и параметры; 2) в более сложных случаях он может изменяться в ходе поиска в зависимости от получаемых результатов и накапливаемого опыта (последнее называют адаптацией поиска); 3) он может содержать случайную компоненту, в потенции обеспечивающую возможность нахождения всех решений задачи оптимизации, т.е. реализацию глобального поиска; 4) он также может содержать дополнительную регулярную компоненту, формирующуюся на базе ранее полученного опыта поисковой оптимизации и обеспечивающую повышение эффективности локального (а затем - и глобального) поиска экстремума соответствующей целевой функции; 5) сочетания регулярной и случайной компонент в таком алгоритме могут быть самыми разнообразными. Из вышеперечисленных пунктов 2) и 4) следует, что опыт, накапливаемый в процессе поиска экстремума оптимизируемой целевой функции, является основой для введения механизма адаптации алгоритма A, обуславливающего возможность кардинального улучшения эффективности поисковых характеристик последнего. Таким образом, предположение, что важнейшим параметром алгоритма A является именно глубина его памяти т, не выглядит необоснованным. Введение параметра т позволяет получить простой и ясный показатель выявления типовых вариантов реализации поискового алгоритма A, т.е. фактически сформировать классификатор поисковых методов оптимизации: для этого достаточно выделить его типовые значения 0 и 1 (т=0, 1) , а также типовой интервал значений, больших единицы (т>1) - см. табл. 1.
3.4.1. Простейший случайный поиск (глубина памяти т=1) Действительно, структура алгоритмов простейшего случайного поиска (например, описанный выше алгоритм с линейной тактикой либо его вариант с нелинейной) зависит от знака приращения целевой функции оптимизации AQ (t, t -1) = Q (X(t))- Q(X(t -1)), т.е. от последовательных во времени двух пар значений (поисковой переменной X и целевой функции Q(X)): A(t,t-1) = A(X(t),Q(X(t)),X(t-1),Q(X(t-1))). Именно двух этих пар значений достаточно для построения алгоритмом A (t, t -1) (в соответствующем пространстве) простейших линейных прогнозов тенденции изменения целевой функции, и действий при поиске ее экстремума в соответствии с этим прогнозом. Например, в зависимости от знака AQ (t, t -1) происходит выбор нужной ветви из двух возможных в алгоритме простейшего случайного поиска с линейной тактикой: 6 a% при AQ (t, t -1)> 0; (AX (t -1) при AQ (t, t -1)< 0; единичный (k = 1) случайный вектор, равномерно распределенный по всем направлениям AX(t) где: a величина шага поиска (AX = a ), а % пространства оптимизируемых переменных X . Забегая несколько вперед, отмечу, что такая линейная тактика поведения - прямое повторение удачного шага - довольно характерна для поведения живых систем (хотя и не исчерпывает всего разнообразия используемых ими тактик). Алгоритм простейшего случайного поиска, реализующий преемственность последовательных значений поисковой переменной X , относится к классу методов локальной оптимизации. 3.4.2. Адаптивный случайный поиск (глубина памяти т>1) В свою очередь, вариант т>1, т.е. возможность запоминания сразу нескольких пар значений (поисковой переменной X и целевой функции Q), т.е. удлинение памяти о предыстории поиска - делает алгоритм более гибким и, следовательно, более эффективным. В частности, большой объем запоминаемой информации позволяет строить более сложные нелинейные прогнозы тенденции изменения целевой функции Q (X). Поскольку нет никаких логических причин для ограничения теоретически возможной глубины памяти т поиска, эта величина, по-видимому, может возрастать до весьма больших значений. Как следствие, предел совершенствования адаптивных алгоритмов поисковой оптимизации не просматривается ни в технических приложениях, ни в Природе. Алгоритм адаптивного случайного поиска, опирающийся как на преемственность последовательных значений поисковой переменной X (что обеспечивает локальность поиска), так и на возможность прогнозирования рельефа целевой функции Q (что позволяет назвать его глобальную составляющую регулярной , а реализуемое ею свойство поиска - регулярной глобальностью), следует отнести к классу методов локально-глобальной оптимизации. 3.4.3. Слепой поиск/ слепые блуждания (глубина памяти т=0) Наиболее интересным с точки зрения основной проблемы настоящей статьи является противоположный вариант алгоритма A , с нулевой глубиной памяти т=0, т.е. зависимости его только от текущего момента времени t: A (t) = A (X(t), Q (X(t))). Как можно интерпретировать реализуемый на его основе оптимизационный процесс? Зависимость алгоритма A (t) строго лишь от текущего момента времени t (а не от его предыстории, хотя бы и вчерашней , сиюминутной и т.д.) эквивалентна возможности оперирования только с одной точкой в соответствующем пространстве (т. е. только с одной парой значений - поисковой переменной X и целевой функции Q (X)). Поскольку из геометрии известно, что через одну точку можно провести любое число кривых любого вида (в том числе и их частного случая - прямых), возможность прогнозирования алгоритмом A (t) будущего поведения целевой функции Q(X) в такой ситуации отсутствует по определению. Кроме того, нулевая память поисковой переменной X однозначно определяет и характер поиска: он также по определению не может обладать преемственностью ее последовательных значений. Тем самым для данного варианта поиска сразу же отсекается использование всей группы регулярных алгоритмов, существенным образом зависящих от информации о предыдущих значениях как поисковой переменной, так и оптимизируемой функции. И как следствие - на первый план выходит дополнительная ей группа алгоритмов, активно эксплуатирующая идею случайности. В рассматриваемом варианте поиск представляет собой так называемый случайный наброс , который является неотъемлемым элементом любого алгоритма глобального поиска. Именно такой наброс поисковых точек в допустимую область значений переменной X позволяет в принципе достигнуть глобального экстремума оптимизируемой функции Q (X). Как следствие этого факта, можно утверждать, что нулевая память поискового алгоритма обеспечивает свойство вероятностной глобальности поиска, в то время как рассмотренные выше единичная его память обеспечивает свойство локальности поиска, а память, глубина которой превышает единицу, - комбинацию свойств локальности + регулярной глобальности (степень эффективности которой прямо связана с величиной глубины памяти) поиска. Таким образом, поскольку последовательные значения X не обладают преемственностью, и использование для селекции результатов поиска сравнения значений Q ( X) на смежных (хотя бы двух) шагах исключено, то и вести себя алгоритм случайного поискового наброса - как элемент контура оптимизации - теоретически может лишь одним из четырех альтернативных способов: 1) либо подчиняясь внешним влияниям на алгоритм A со стороны целевой функции Q (X), которые должны поступать на него в ходе поискового процесса; 2) либо подчиняясь каким-то иным внешним влияниям на алгоритм A, не являющимся оценками целевой функции и замыкающими контур оптимизации лишь формально, но которые могут поступать на него в ходе поискового процесса (если, конечно, в принципе существует субъект, который может их задавать); 3) либо в соответствии с некоторой комбинацией первых двух альтернатив; 4) либо реализуя чисто гипотетическую ситуацию, когда налицо только процесс каких-то изменений переменной X , а влияния на алгоритм A в ходе этого процесса вообще отсутствуют как таковые; тем самым этот алгоритм может функционировать только согласно некоторой, заранее обусловленной и отраженной в его структуре (случайной или даже регулярной) схеме, которая никак не связана с оценкой результатов его деятельности со стороны внешних по отношению к нему факторов (оценок целевой функции или иных влияний извне) - т.е. алгоритм A вырождается в способ организации программного поведения соответствующей системы. Первая альтернатива приводит к представлению о первом варианте алгоритма поисковой оптимизации с нулевой глубиной памяти (т=0). Он должен содержать две необходимые составляющие: первая - это генератор поисковой переменной X, реализующий такие ее изменения (в области Q допустимых ее значений), которые обычно называют случайным набросом поисковых точек в допустимую область; вторая - это селектор 0 получаемого результата, опирающийся на единственный доступный параметр алгоритма, который может выступать в данной роли - систему целевых требований H (X) и G (X); то есть выход поисковой переменной X за пределы допустимой для нее области Q может трактоваться как пересечение ею порога селекции, с последующим исключением (элиминированием) данного поискового действия из протокола процесса оптимизации. Таким образом, если полагать понятия случайного поискового наброса и слепого поиска в достаточной степени близкими, практически синонимами, то можно утверждать, что наименование слепого поиска наилучшим образом подходит к алгоритмам первой альтернативы (см. табл. 1). Нужно лишь отметить, что упомянутый выше протокол обычно ведут при технических приложениях подобных методов, а как это может выглядеть в Природе? Ниже этот вопрос будет кратко рассмотрен. Вторая же альтернатива базируется на понятии внешнего дополнения (введенном применительно к сложным системам Стаффордом Биром), которое по самому определению находится вне рамок рассматриваемой поисковой системы и по отношению к последней, в определенном смысле, эквивалентно сверхъестественному влиянию . Внешнему дополнению достаточно принимать лишь два значения - удача либо ошибка . Тогда необходимые составляющие поискового алгоритма, который здесь следует обозначить как A , выглядят следующим образом (второй вариант поискового алгоритма с нулевой глубиной памяти (т=0)): первая - та же, что и в варианте первой альтернативы: генератор поисковой переменной X , реализующий ее случайные изменения - случайный наброс ; вторая - это селектор в получаемого результата, реализуемый здесь внешним дополнением ; то есть любые значения поисковой переменной X , в момент генерации которых внешнее дополнение дает сигнал ошибка , будут расцениваться как неудачные и исключаться из протокола процесса полуоптимизации (название которой отражает очевидное: отсутствие в данном варианте естественного замыкания классического контура оптимизации - собственной внутрисистемной целевой функции), а при сигнале удача - расцениваться именно как удачные и включаться в такой протокол (см. рис. 2б). Таким образом, для полуоптимизационных алгоритмов второй альтернативы можно предложить наименование слепых блужданий , не смешивая их с ранее введенным (для первой альтернативы) понятием слепого поиска (см. табл. 1). Отмечу, что и здесь остается тот же вопрос: как может выглядеть подобный протокол не в технических приложениях, а в Природе? Третья альтернатива, формирующаяся как комбинация первых двух, представляет собой механизм, который при должной настройке может обладать наилучшими характеристиками его составляющих, и, тем самым, отражать более сложную моделируемую на его основе ситуацию, чем это доступно каждой из его составляющих в отдельности. Наконец, четвертая альтернатива была отвергнута ранее как предельно вырожденная, делающая рассматриваемый процесс генерации флуктуаций X вообще неоптимизационным , что полностью выводит нас за рамки проблематики настоящей работы. 3.5. Место МПиО в классификаторе поисковых методов оптимизации Приведенная выше, в подразделе 3.4, аргументация показывает, что термин МПиО может относиться только к одному типу (в худшем случае - его относят сразу к нескольким) из следующих четырех формально определенных классов методов случайной поисковой оптимизации. Это: 1) слепые блуждания (с селекцией посредством внешнего дополнения) , с нулевой глубиной памяти (т=0) алгоритма A поисковой полуоптимизации ; 2) слепой поиск (с селекцией посредством целевых ограничений) , с нулевой глубиной памяти (т=0) алгоритма A поисковой оптимизации; 3) простейший случайный поиск , с единичной глубиной памяти (т=1) алгоритма A поисковой оптимизации; 4) адаптивный случайный поиск , с глубиной памяти алгоритма A поисковой оптимизации, большей единицы (т>1). К сожалению, результаты анализа, проведенного в разделе 2, свидетельствуют о том, что на практике реализуется именно худший случай : различные (а иногда даже одни и те же) авторы применяют это понятие в самых разных смыслах, т.е. во всех четырех вышеперечисленных вариантах. Конечно, большинство (как показывает анализ) авторов все же воспринимают и используют термин МПиО как слепой поиск по варианту № 2 (см. табл. 1). И с этой позицией нельзя не согласиться. Ведь в данном варианте МПиО решает главную задачу - нахождение вероятностно-глобального экстремума оптимизируемой функции, и притом, как это интуитивно и ожидается - простейшими средствами (правда, чем проще алгоритм, тем (в среднем) больше поисковых шагов для достижения цели ему потребуется). Но большинством в науке ничего не решается. Даже единичное использование этого термина в расширительной трактовке (о чем читатель может и не знать, по умолчанию 1 2 3 4 5 |
© 2024 РубинГудс.
Копирование запрещено. |