Диссертация (Разработка и исследование алгоритмов совмещения изображений от бортовых видеодатчиков с виртуальной моделью местности), страница 5

Онииспользуют прием, который можно назвать «снижение требований». Он27заключается в отказе от поиска оптимального решения, а в нахождении«хорошего» решения за приемлемое время [21].Алгоритмы,основанныенаэтомприеме,обычноназываютсяэвристическими, поскольку они используют разумные соображения без строгихобоснований. При их разработке используются интуитивные соображения, неподкрепленные соответствующим математическим обоснованием.Методы, применяемые для построения алгоритмов такого типа, сильнозависят от специфики задачи.

Итеративные процедуры, применяемые для этойцели, напоминают итеративные процедуры поиска экстремума при использованииалгоритмов градиентного типа и алгоритмов метода возможных направлений.При использовании алгоритмов данного класса возникает вопрос овозможности отыскания с их помощью глобального оптимума или приближения кнему с точностью до некоторой задаваемой ошибки ε. На практике оказывается,что в большинстве случаев гарантированно можно достичь только некотороголокальногоэкстремумаприближенными,ноцелевойонифункции.принципиальноДанныеалгоритмыотличаютсяотявляютсяприближенныхалгоритмов ε - оптимизации, строящихся на основе методов последовательногосужения множества решений и гарантирующих приближение к экстремуму сточностью до ε.Длякорреляционногосовмещенияизображенийможноопределитьследующие классификационные признаки методов оптимизации:–характер оптимизации: в зависимости от применяемого алгоритмавозможно отыскание локального или глобального экстремума, соответственнометоды оптимизации подразделяются на локальные и глобальные.–вид оптимизации: условная или безусловная.

Для задачи совмещенияизображений не требуется предусматривать в методе оптимизации каких-либодополнительных ограничений. Поиск наилучшего совмещения с изображениемВММ осуществляется в шестимерном пространстве, возможный выход запределы которого можно исключить программными ограничениями;28–размерностьрешаемойзадачи.Вцеломрешаетсязадачавшестимерном пространстве поиска (высота, широта, долгота, курс, тангаж икрен). Увеличив размер изображения ВММ можно исключить из рассмотрениятангаж и крен, но появляются два параметра – координаты по X и Y приперемещении РИ по ВИ.

Также можно исключить курс, который соответствуетповороту ВММ, который в рассматриваемой задаче незначительный. Такимобразом, получаем задачу в пятимерном пространстве поиска (высота, широта,долгота и координаты по X и Y).Исходяизприведенныхпризнаковдляклассификацииметодовоптимизации, в общем случае методы поиска глобального экстремума прирешении задачи совмещения изображений можно разделить на следующиеклассы:1.Методы сканирования области поиска;2.Методы редукции размерности;3.Методы локального поиска из случайных начальных точек;4.Методы искусственного отбора.В случае решения задачи корреляционного совмещения изображенийцелевая функция является многоэкстремальной, причем число экстремумов можетбытьвесьмаизображений.существеннымПоэтомуитребуетсяопределяетсявыбратьхарактеромметодысовмещаемыхглобальногопоиска,обеспечивающие поиск глобального экстремума с большой точностью, но приминимальных временных затратах.1.4.1 Метод мультистартМетод мультистарт состоит в многократном (последовательном илипараллельном) отыскании локальных экстремумов из начальных точек.

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

Чтобыизбежать данных сложностей, мультистарт обычно модифицируют одним изследующих образов [22]:точки локальных минимумов, найденные на целевой функции,окружаются окрестностями заданного размера и попадание других точек в этиокрестности считается равносильным попаданию в точки локальных минимумов;метод «конкурирующих точек» - поиск локальных минимумовосуществляется параллельно, причем точки, расстояние между которыми мало (непревышает некоторого фиксированного маленького числа) заменяются одной изних – той, значение функции в которой меньше.1.4.2 Туннельный алгоритмСуть данного алгоритма состоит в том, что после нахождения очереднойточки локального минимума x* функции f отыскивается точка x0 из множества Х,удовлетворяющая неравенству f(x0) ≤ f(x*), отличная от x*, и из нее как изначальной точки производится локальный спуск.Туннельный алгоритм состоит из двух фаз – фазы минимизации итуннельной фазы.

На фазе минимизации применяется произвольный алгоритмлокальной оптимизации для поиска локального минимума функции f. Натуннельной фазе по функции f и точке рекорда x* (то есть точки, в которойцелевая функция имеет наименьшее из вычисленных ранее значений) строитсявспомогательная функция T(x), называемая функцией штрафа. После этого натуннельной фазе отыскивается точка x* из множества A={x ∈ Х | f(x) ≤ f(x*)}\{x*}.И из нее на фазе локальной минимизации вновь осуществляется локальныйспуск. Полученная точка локального минимума функции f является точкой новогорекорда, и процедуру поиска можно повторить вновь.

Поиск прекращается, когдаалгоритму не удается найти новую точку рекорда x*.301.4.3 Сетки и методы покрытийСеткой во множестве Х называется набор точек En={x1, …, xn} из X.Методом сеток и покрытий называется метод поиска глобальногоэкстремума, состоящий в построении сетки En, вычислении значений целевойфункции f в узлах сетки и выборе точки xn*  arg min f ( xi ) (точки сетки, в которойxiEnдостигается наилучшее значение целевой функции) в качестве приближения кточке x *  arg min f ( x) глобального минимума функции f, а также выбореxXзначения f n*  f ( xn* ) в качестве приближения к величине глобального минимумацелевой функции f *  min f ( xn* ) .Методы сеток широко используются для решения различных численныхзадач, в том числе глобальной оптимизации.

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

Это, в свою очередь способно значительно ускорить решение задачипоиска глобального экстремума.Метод поиска глобального экстремума, заключающийся в переборе снекоторым шагом по каждой из координат, является частным случаем методапокрытий. Сетка в названном методе имеет некоторую постоянную, регулярнуюструктуру.Благодаряеёиспользованиюможносущественносократитьвычислительные затраты, при этом практически не потеряв в точностинахождения глобального экстремума.31В качестве положительной стороны данного подхода следует отметить то,что методы покрытий дают гарантированную оценку погрешности нахожденияглобального экстремума исследуемой функции, методы покрытий хорошоисследованы теоретически.1.4.4 Поиск с запретамиСогласно [24]: «основоположником алгоритма поиска с запретами (Tabusearch) является Ф. Гловер [23], который предложил принципиально новую схемулокального поиска, позволяющую алгоритму не останавливаться в точкелокального оптимума, как это предписано в стандартном алгоритме локальногоспуска, а переходить от одного локального оптимума к другому в попыткахнайти среди них глобальный».«Основным механизмом, позволяющим алгоритму выбираться из локальногооптимума, является список запретов Tabu(ik).

Он строится с помощьюпредыстории поиска, то есть по нескольким предшествующим решениямik, ik–1,…,ik–l+1, и запрещает часть окрестности текущего решения N(ik). Точнее накаждом шаге алгоритма очередная точка ik+1 является оптимальным решениемподзадачи f(ik+1) = min {f(j) | jN(ik)\Tabul(ik)}».«Список запретов Tabul(ik)N(ik) учитывает специфику задачи и, какправило, запрещает использование тех фрагментов решения (в качестве такогорода фрагментов могут выступать ребра графа, координаты векторов, цветавершин), которые менялись на последних l шагах алгоритма. Константа l0задает длину списка запретов.

При нулевом значении l получаем стандартныйлокальный спуск».Существует много вариантов реализации основной идеи поиска с запретами.Приведем один из них, изложенный в [24], для которого удается установитьасимптотические свойства.Для рандомизированной окрестности Np(i)N(i), где каждый элементокрестности j N(i) включается в множество Np(i) с вероятностью p независимо отдругих элементов. С ненулевой вероятностью множество Np(i) может совпадать с32N(i), может оказаться пустым или содержать ровно один элемент. Общая схемаалгоритма поиска с запретами может быть представлена следующим образом [24]:Алгоритм поиска с запретами1.

Выбрать начальное решение i0 I и положить f*:= f(i0),Tabul(i0):= ,k:=0.2. Пока не выполнен критерий останова делать следующее.2.1. Сформировать окрестность Np(ik).2.2. Если Np(ik) =  , то ik+1:=ik, иначе найти ik+1 такой, чтоf(ik+1) = min {f(j) | j Np(ik)\Tabul(ik)}.2.3. Если f *> f(ik+1), то f *:= f(ik+1).2.4. Положить k= k+1и обновить список запретов Tabul(ik).Параметры p и l являются управляющими для данного алгоритма и выбор ихзначений зависит от размерности задачи и мощности окрестности [24].1.4.5 Генетические алгоритмыИдея генетических алгоритмов взята у живой природы и состоит ворганизации эволюционного процесса, целью которого является получениеоптимального решения сложной комбинаторной задачи.

Идея генетическихалгоритмов предложена Джоном Холландом в 60-х годах, а результаты первыхисследований обобщены в его монографии [25].ГА – адаптивные методы поиска, которые используются для решения задачфункциональной оптимизации. Они основаны на генетических процессахбиологических организмов: биологические популяции развиваются в течениенескольких поколений, подчиняясь законам естественного отбора и по принципу«выживает сильнейший», то есть наиболее присписобленный. Подражая этомупроцессу ГА способны «порождать» решения реальных задач, если тезакодированы требуемым образом.

Функция, определяющая приспособленность,должна удовлетворять следующему условию: чем «лучше» особь, тем вышеприспособленность [26].В отличие от эволюции, происходящей в природе, ГА только моделируют тепроцессы в популяциях, которые являются существенными для развития. Таким33образом,ГАиспользуютнаследственности,дляизменчивостисвоейиработыэволюционныеестественногоотбора.принципыОбщаясхемаорганизации ГА в приложении к рассматриваемой задаче представлена нарисунке 1.2.ЭволюционныепринципыИнициализацияпопуляции решений– кандидатов(особей)Генерация случайногонабора закодированныхточек пространствапоискаЕстественный отборОдно поколениеОценивание особейВычисление ЦФ длякаждой координатыНаследственностьОтбор координат случшими значениемЦФИзменчивостьВнесение измененийв решения дляполучения новыхкоординатСелекцияСкрещивание(кроссовер)ГА для задачи совмещенияизображенийСлучайныеизмененияпопуляции (мутация)Решение1 цикл оптимизацииОбщая схема ГАРешениеРисунок 1.2 – Схема ГАГенетический алгоритм работает со случайно генерируемым множествомисходных решений, представляющий собой некоторую популяцию особей, вхромосомах которых закодировано возможное решение задачи.