Диссертация (1137121), страница 14
Текст из файла (страница 14)
В этом методе осуществляется поворот системыкоординат в исходном пространстве признаков таким образом, чтобы проекции нановые оси – главные компоненты – дисперсия всего множества быламаксимальна. При этом дисперсия сосредоточена большей частью в первыхкомпонентах, что позволяет рассматривать только их, отбрасывая остальные.Метод PCA был использован при создании относительно небольшого числасистем [33,34].93К нелинейным методам снижения размерности относят методы, с помощьюкоторыхпроизводитсяпространстваотображениемножествавекторовмногомерногов пространство малой размерности (как правило, двух- илитрёхмерное) с сохранением, по возможности, расстояний между ними.
Всеподобные методы пытаются минимизировать некоторую функцию потерь,характерную величину рассогласования расстояний между первоначальными иполученными векторами в пространстве малой размерности. В случае если влитографической технологии функцию потерь задают в виде∗=∑(здесь∗и∙ ∑(2.5.1)- расстояние между объектами i и j, соответственно, вмногомерном и двумерном пространстве, N – количество объектов), её называютошибкой Сэммона, а соответствующий метод снижения размерности называютметодом двумерного отображения Сэммона [35].Нелинейные методы отображения применяются во многих системах,описанных в литературе.
Среди нелинейных методов, применяемых для сниженияразмерности, можно выделить отдельный класс алгоритмов, использующихсиловые методы укладки графов. Работа этих алгоритмов основана наматематическихмоделяхмеханическихпроцессов.Наиболееизвестнымиявляются модели Фрухтермана - Рейнгольда и Камада – Кавайни [35].Также выделяется отдельный класс алгоритмов, работающих на дискретнойсетке. Очевидным способом получения отображения на дискретную сеткуявляется привязка к ней результата работы, полученного в непрерывномпространстве.Однимизраспространённыхспособовснижениявычислительнойсложности базового метода Сэммона является использование триангуляции.
Вданном методе сначала с использованием базового алгоритма ищется решение длянекоторого количества объектов M < N. Затем производится последовательное94добавление (M - N) объектов с использованием триангуляции. При этом длякаждого объекта oi, i = (M+1)…N выбирается два объекта oj, ok, j k = 1…M изчисла уже спроецированных с использованием базового алгоритма, а положение(yi1; yi2) объекта oi на плоскости определяется, исходя из соотношений,обеспечивающих точное сохранение расстояний межу рассматриваемымиобъектами:=∗,∗=.Если выполнение соотношений невозможно, то за искомое положениеобъекта oi берётся точка (yi1; yi2) на отрезке (yj1; yi2) (yk1; yk2), для которой∗=выполняется:∗.Если выполнение приведённых соотношений возможно и существует дварешения ()и;;, то из числа уже спроецированных объектов берётсяещё один объект os, s = 1…M и искомое решение выбирается исходя изсоотношения:(где∗;)=и∗;, если∗−≤∗−,;, если∗−>∗−,- расстояния от точек (противном случае решение (;;) и;(2.5.2)до точки (;).
В) единственно.Решением проблемы высокой вычислительной сложности может бытьалгоритм, использующий аппроксимации приращений координат точек на каждойитерации.Приэтом,есливычислительнаясложностьдляпостроенияаппроксимационной оценки приращений координат объектов на каждой итерациисоставляет O[k], где k << N, то вычислительная сложность всего алгоритма можетбыть снижена до O[N 2].95Среди существующих решений в качестве такой аппроксимации можетбыть рассмотрен подход, предложенный Чалмерсом в работе [35]. В этом подходена каждой итерации для каждого корректируемого элемента формируется 2множества.
В первом из множеств содержатся элементы, наиболее близкиерассматриваемомувмногомерномпространстве.Вовтороммножествесодержатся элементы отбираемые на каждой итерации случайным образом. Такойподход был использован для минимизации ошибки выражаемой в виде=−∗,(2.5.3)Однако он может быть применен при минимизации ошибки Сэммона (1).Ещё одним методом, рассматриваемым в данной работе, являетсямодифицированныйкомбинированныйметодсниженияразмерности,предложенный в работах [34,35].Подход, положенный в основу метода состоит в использовании приснижении размерности результатов иерархической кластеризации в рамкахдвухэтапной процедуры следующего вида.На первом этапе для всех k кластеров самого первого уровня строитсядвумерное отображение центров этих кластеров.
На втором этапе строится kотображений для подклатеров и объектов второго уровня. При этом дляпостроения отображения каждого подкластера расположение координат центровкластеров самого верхнего уровня фиксируется и производится оптимизацияположения на плоскости только объектов, находящихся в рассматриваемомподкластере.
Процесс повторяется для третьего уровня иерархии и так далее, покане будет построено отображения всех объектов.Было показано [34], что в случае сбалансированного дерева кластероввысотой=, когда в каждом кластере оказывается k элементов,выражение сложности принимает вид.96Задача снижения размерности в литографической технологии на практикереализуетсякоррекциейоптическогоэффектаблизостивпроцессепроектирования промежуточных шаблонов с размерами элементов меньше длиныволны экспонирующего излучения проекционной установки [36].При экспонировании микроизображения с размерами, равными и меньшимипредельного размера по Рэлею – Аббе, изображение претерпевает различногорода искажения.
Это сужение или недоэкспонирование узкой длинной линии,сокращение и округление её концов, заплывание узких зазоров и острых углов. Сэтими искажениями можно бороться, создавая упреждающие компенсирующие ихэлементы на фотошаблоне. Один из типичных случаев на примере Т-образного иГ-образного элементов топологии [37] (рис. 2.5.1).Рис. 2.5.1 Коррекция оптической близости на примере Т – образного иГ –образного элементов интегральной схемы.Здесь используются угловые засечки для уменьшения скруглений ипредотвращения укорачивания элементов рисунка, а также локальные измененияширины линии для предотвращения её сужения.Этиэлементыпозволяютвоспроизвестинеобходимуюструктурумикрорисунка интегральной схемы при размерах существенно меньших, чем97«релеевский», вычисленный для заданной длины волны и числовой апертуры поформуле Рэлея (рис. 2.5.2).Рис.2.5.2 Изображение светящихся точек разрешимых по Рэлею – Аббе.Иначе говоря, коррекция оптического эффекта близости заключается впроектировании топологии СБИС, которое позволит учесть деструктивноевоздействиеэффектовдифракциииинтерференции,возникающихвпроекционных системах, когда размеры элементов меньше «λ» [38] (рис.
3).98Рис. 2.5.3. Фрагмент исходной топологии и фрагмент после травленияПриэтомисходнаятопологиямоделируется,проводитсяанализполученного контура, и в местах несоответствий вводится обратная коррекция,процесс проводится итеративно до достижения заданных параметров [38] (рис.2.5.4).Рис. 2.5.4. Фрагмент исходной топологии и фрагмент после травленияВведение коррекции оптического эффекта близости невозможно без точныхи стабильных методов отображения коллекции изображений в двухмерноепространство.2.6 Применение методов многомерной оптимизации при разработкетехнологического процесса ультрафиолетовой литографииРассмотрим методы оптимизации функции одной переменной вкачестве реализации алгоритмов поиска наилучших решений при разработке99технологического процесса ультрафиолетовой литографии.
Данные методыможно сгруппировать следующим образом: Методы исключения интервалов:o метод половинного деления,o метод «золотого» сечения,o метод Фибоначчи; Методы полиномиальной аппроксимации; Методы с использованием производных.Методы безусловной оптимизации делятся на методы одномерной имногомерной оптимизации.К методам многомерной оптимизации относятся.1. Методы нулевого порядка:o покоординатного спуска,o Хука-Дживса,o симплексный метод Нелдера-Мида;2. Методы первого порядка:o градиентный,o наискорейшего спуска,o сопряженных градиентов: метод Дэвидона-Флетчера-Пауэла, метод Флетчера-Ривса.Рассмотрим функцию n действительных переменныхf ( x1 , x2 , ..., xn ) f ( x) .Точка в n-мерном евклидовом пространстве с координатами x1 , x2 , x3 ..., xnобозначаетсявектором-столбцомx.Градиентфункции,т.е.векторскомпонентами f / x1 , f / x2 ,..., f / xn , обозначается f (x) или, иногда, g(x).100Матрица Гессе (гессиан) функции f(x) обозначается какG(x) и являетсясимметричной матрицей n×n элементов видаGij 2 f / x i x j .Функция f(x) имеет локальный минимум в точке x0, если существуетокрестность точки x0, такая, что f ( x) f ( x0 ) во всех точках этой окрестности, т.е.существует положительная величина δ, такая, что для x x0 справедливонеравенство f ( x) f ( x0 ) .В случае глобального минимума в точке x* для всех x справедливо*неравенство f ( x) f ( x ) .