Рис.1.1 - Идея метода множественных стрельб

Несмотря на значительный рост числа неизвестных в ММС, данная схема обладает рядом преимуществ :

1. Упрощается учёт априорной информации о переменных состояния, определяемой по значениям замеров, при выборе начального приближения.
2. Подходящий выбор начальной точки обычно позволяет избежать выхода на локальный минимум задачи.
3. Данный метод является численно устойчивым и позволяет решать задачу оценки параметров даже для нестабильных и хоатических систем.
4. Особая структура целевой функции позволяет упростить реализацию параллельных алгоритмов её подсчёта.

2. Алгоритмы оптимизации

2.1 Классификация алгоритмов оптимизации

Существует несколько альтернативных подходов к классификации локально-детерминистических алгоритмов оптимизации (рис.2.1).

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

1. алгоритмы безусловной оптимизации;
2. алгоритмы решения задачи оптимизации с прямыми ограничениями на переменные;
3. алгоритмы условной оптимизации для задач с ограничениями-равенствами;
4. алгоритмы условной оптимизации для задач со смешанными ограничениями;
5. алгоритмы нелинейных наименьших квадратов.

Второй подход основывается на учёте различных критериев, которые определяют характерные черты реализации алгоритмов . Согласно одному из таких критериев методы оптимизации делятся на активные (последовательные ) и пассивные . В пассивных методах все точки для дальнейшего анализа выбираются одновременно до начала вычислений. В активных методах точки выбираются последовательно, выбор каждой последующей точки зависит от значений предыдущих. Другим критерием классификации является информация о функции, которую требует алгоритм. Если для успешного выполнения алгоритма достаточно лишь информации о значение функции в точке, то такой алгоритм относится к алгоритмам нулевого порядка (метод Гаусса, симплексный метод Недлера-Мида, методы поворота системи координат Хука-Дживса, классический Розенброка, метод Пауэлла и т.д.). Если дополнительно требуется знание о градиенте, то алгоритм относится к алгоритмам первого порядка . Алгоритмы второго порядка кроме знания значение функции в точке и её градиента, нуждаются также в информации о матрице Гессе (метод Ньютона, классические SQP-схемы). Среди локально-детерминистических методов оптимизации наиболее представительную группу составляют методы спуска , которые в свою очередь базируются на двух моделях. Первую модель образуют методы линейного поиска , в которых на каждой итерации направление спуска определяется однозначно, а оцениванию подлежит длина шага. Вторую модель образуют методы доверительных областей (trust-region ), в которых наоборот на каждой итерации оценивается направление спуска. Среди методов спуска первого порядка можно выделить такие группы методов :

1. градиентные алгоритмы;
2. квазиньютоновские алгоритмы (ДФП, БФГШ, SR1);
3. методы сопрпяжённых направлений (метод Флетчера-Ривза, метод Полака-Рибьера);
4. специализированные алгоритмы минимизации квадратов нелинейных функций (метод Гаусса-Ньютона, метод Левенберга-Маркарда, ряд SQP-схем).

Рис.2.1 - Классификация алгоритмов, решающих задачу математического программирования

2.2 Обзор существующего оптимизационного ПО

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

1. программные пакеты, ориентированные на решение задачи математического программирования (на рис. оттенки зелёного);
2. численные библиотеки, содержащие алгоритмы оптимизации (на рис. жёлтый цвет);
3. системы оптимизации и моделирующие среды (на рис. синий цвет).

Рис.2.2 - Классификация ПО, решающего задачу математического программирования

Часть из известных оптимизационных пакетов ориентирована на решение только одного класса оптимизационных задач, но некоторые пакеты способны эффективно решать несколько классов задач. Характерной чертой пакетов для решения задачи оптимизации с прямыми ограничениями на переменные является то, что они достаточно эффективно справляются с задачей безусловной оптимизации. Большинство оптимизационных пакетов реализованы на языке Fortran. Наиболее известными из них являются LANCELOT и MERLIN. Именно с эффективностью реализованных в них процедур обычно производится сравнение эффективности новых алгоритмов. LANCELOT является одной из наиболее мощных библиотек оптимизационных алгоритмов, ориентированных прежде всего на решение задач большой размерности. Язык реализации библиотеки - ANSI Fortran 77. Хотя недавно вышла адаптация пакета LANCELOT на Fortran 99. На данный момент LANCELOT разработкой занимается Council for the Central Laboratory of the Research Councils (CCLRC). Пакет MERLIN был разработан в университете г.Иоаннина (Греция) и первоначально предназначался для решения задачи оптимизации с прямыми ограничениями на переменные. Сейчас функциональность пакета значительно расширилась. Одним из наиболее известных пакетов для решения задач безусловной оптимизации и оптимизации с прямыми ограничениями на переменные на сегодня является пакет L-BFGS-B, разработанный в Северо-Западном университете (США). С недавнего времени начали появляться оптимизационные пакеты, реализованные на C++ (OptSolve++, OPT++, macopt). Часто такие пакеты уже содержат реализации параллельных алгоритмов оптимизации (OptSolve++, Bob++).

Численные библиотеки NAG, HSL и IMSL среди прочих неспециализированных численных библиотек выделяются наиболее развитой системой алгоритмов оптимизации. В библиотеке NAG алгоритмы оптимизации собраны в папку E04. Разработкой библиотеки занимается The Numerical Algorithms Group Ltd. На данный момент доступны реализации библиотеки на Fortran и C, в недавнем прошлом сушествовали только Fortran77 и Algol68 версии библиотеки. Библиотека является коммерческой. Библиотека HSL (Harwell Subroutine Library) разрабатывается CCLRC (в деревушке Харвел неподалёку от Оксфордшира). На данный моент библиотека HSL реализована только на ISO Fortran. Последний известный релиз библиотеки состоялся в сентябре 2004. Алгоритмы оптимизации библиотеки IMSL собраны в главу 8 её реализации на языке ANSI Fortran. Реализация библиотеки на C содержит только часть этих алгоритмов. Доступны также ограниченные реализации этой библиотеке на Java и C#.NET. Разработкой библиотеки занимается компания Visual Numerics Inc.

Системы оптимизации и моделирующие среды обычно представляют из себя развитый законченый продукт и имеют встроенный собственный (либо стандартизированный) язык моделирования, позволяющий достаточно просто формулировать оптимизационные задачи. Обычно такие системы и среды предоставляют интерфейс для подключения внешних пакетов, реализованных на Fortrn и C. Более того, моделирующая среда GAMS, разработанная GAMS Development Corporation, не имеет собственных оптимизационных кодов, а лишь предоставляет интерфейс для подключения пакета MINOS. Системы оптимизации Speakeasy также имеет интерфейс для подключения внешней библиотеки NAG, но в то же время в ней содержатся и "родные" пакеты, такие как EISPACK и FFTPACK. AMPL представляет из себя специализированный достаточно гибкий язык моделирования для постановки и решения задач математического программирования. Matlab является наиболее известной системой из вышеперечисленных. В данной системе реализованы квазиньютоновские алгоритмы, метод Недлера-Мида, метод Ньютона, метод Левенберга-Маркарда и т.д.

Существуют также пакеты, ориентированные на решение задачи оценки параметров. К ним следует отнести пакеты EASY-FIT, разработанный в университете г.Бейрут под руководством проф. К.Шитковского, и пакет PAREST, разработанный в Мюнхенском техническом университете. Причём в пакете PAREST реализован метод множественных стрельб.

К оптимизационному ПО стоит также отнести библиотеку тестовых оптимизационных задач CUTEr, разработанную Н.Гоулдом, Д.Орбаном и Ф.Тоинтом. Данная библиотека, по сути, является стандартом для тестирования алгоритмов оптимизации.

3. Обзор публиуаций по теме

Ежегодно появляются десяки публикаций, посвящённых оптимизационным задачам, возникающих при моделировании СДС, и в частности вопросам оценки параметров моделеи. Не смотря на то, что сушествует множество основательных трудов в области оценки параметров , метод множественных стрельб достаточно слабо освещён в литературе. Классические книги проф. Х.Бока, в которых проведено обоснование и доказательство практической ценности ММС, из-за малого тиража практически недоступны. Статей посвящённых ММС также относительно не много. В большинстве из них производится только обзор метода, а также способов его реализации. Анализ сходимости и другие важные вещи там отсутствуют.

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

Поскольку в данной работе в первую очередь планируется реализовать модификацию БФГШ-метода для решения задачи оптимизации с прямыми ограничениями на переменные, то в дальнейшем здесь будут рассматриваться только публикации, в которых описывается БФГШ-метод. Метод Бройдена-Флетчера-Голдфарба-Шэнно (БФГШ) был предложен в 1970 году как развитие общей идеи квазиньютоновских методов, предложенной Давидоном. На сегодняшний день этот метод является наиболее эффективным квазиньютоновским методом. В 1980 Дж.Ноцедалем была предложена модификация БФГШ-алгоритма, требующая небольших затрат оперативной памяти и известная под названием LBFGS-метода , а в 1991 году им же в соавторстве с Р.Бёрдом был предложен L-BFGS-B-метод, позволяющий решать не только задачи безусловной оптимизации, но и задачи оптимизации с прямыми ограничениями на переменные . В 1994 году появился пакет, реализующий LBFGS-B-алгоритм на языке Fortran. В 1994 году вышел последний релиз этого пакета. В дальнейшем публикации, касающиеся LBFGS появлялись ежегодно, но принципиально новых идей по модификацие LBFGS-алгоритма в них не было.

4. Краткое описание используемых алгоритмов

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

В качестве основного алгоритма оптимизации на данном этапе используется LBFGS-B-метод . Направление в данном методе ищется согласно формуле (4.1):

Для учёта ограничений в LBFGS-B-алгоритме используется схема, идентичная той, которая применяется в методе проекции градиента. Классический LBFGS-B-алгоритм использует при выборе длины шага процедуру "бэктрэкинга" ("backtracking"). В данной работе планируется несколько улучшить классическую схему LBFGS-B-метода путём использования в нём при выборе длины шага интерполяционной процедуры.

Рис.4.1 - Схема работы методов спуска

Выводы

В данной работе были кратко рассмотрены основные классы оптимизационных задач, выделены их особенности и рассмотрены подходы, позволяющие находить их решения. Также здесь приведен краткий обзор алгоритмов оптимизации, существующего оптимизационного ПО и литературы по данной тематике. На текущий момент в рамках работы разработаны и внедрены в моделирующую среду Diana интерфейсы основных оптимизационных задач и решателей данных задач. Был дополнительно реализован простой градиентный алгоритм алгоритм с модификацией Армихо , но в связи с тем, что данный алгоритм не справлялся с решением плохо масштабированных задач, от дальнейших исследований в данном направление пришлось отказаться. Вместо этого в моделирующую среду Diana мной был имплементирован код LBFGS-B-алгоритма, разработанный П.Лу .

В дальнейшем планируется на языке C++ реализовать модифицированный LBFGS-B-алгоритм и исследовать эффективность предложенной модификации на реальных моделях с использованием как подхода с оценкой начальной точки, так и ММС, а также исследовать один из алгоритмов минимизации квадратов нелинейных функций.

Список использованной литературы

1. Nocedal, Jorge; Wright, Stephen J. Numerical optimization. - New York, NY : Springer, Springer series in operations research, 1999. - 623 с.
2. Измаилов, А.Ф.; Солодов, М.В. Численные методы оптимизации. - М.: «ФИЗМАТЛИТ», 2003. - 304 с.
3. Бертсекас, Д. Условная оптимизация и методы множителей Лагранжа. - М.:Радио и связь, 1987. - 400 с.
4. Сухарев, А.Г.; Тимохов, А.В.; Фёдоров, В.В. Курс методов оптимизации. - М.: Наука, 1986. - 328 с.
5. More, Jorge J.; Wright, Stephen J. Optimization software guide. - Philadelphia, Pa.: SIAM Soc. for Industrial and Applied Mathematics, 1994. - 154 с.
6. Peifer, M.; Timmer, J. Parameter estimation in ordinary differential equations using the method of multiple shooting - a review. - Freiburg: Freiburg Centre for Data Analysis and Modelling, 2005
7. Byrd, Richard H.; Lu,P.; Nocedal, Jorge; Zhu, C. A Limited Memory Algorithm for Bound Constrained Optimization. - Northwest university, 1994
8. Horbelt, Werner Maximum likelihood estimation in dynamical systems. - Freiburg: Albert-Ludwigs-Universitaet Freiburg Fakultaet fuer Physik, 2001.
9. Polak, Elijah Optimization: algorithms and consistent approximations (Applied mathematical sciences; v.124). - New York, NY : Springer, 1997. - 779 с.
10. Censor, Yair; Zenios, Stavros Andrea Parallel optimization: theory, algorithms, and applications - New York, NY : Oxford Univ. Press, 1997. - 539 с.
11. Сеа, Ж. Оптимизация. Теория и алгоритмы. - М.: «Мир», 1973. - 244 с.
12. Retout, Sylvie; Mentre, France; Bruno, Rene Fisher information matrix for non-linear mixed-e ects models: evaluation and application for optimal design of enoxaparin population pharmacokinetics. - Sylvie Retout, INSERM U436, CHU Pitie Salpetriere, 91 bd de l Hopital, 75013 Paris, France, May 2001. - 15 с.
13. Bock, Hans Georg; Koerkel, Stefan; Kostina, Ekaterina; Schloeder, Johannes P. Methods of Design of Optimal Experiments with Application to Parameter Estimation in Enzyme Catalytic Processes. - Interdisciplinary Center for Scientific Computing (IWR), University of Heidelberg, Im Neuenheimer Feld 368, 69120 Heidelberg, Germany, October 2004. - 25 с.
14. Kutalik, Zoltan; Cho, Kwang-Hyun; Gordon, Steve V.; Wolkenhauer, Olaf Optimal Sampling Time Selection for Parameter Estimation in Dynamic Pathway Modelling. - Control Systems Centre, Department of Electrical Engineering and Electronics, UMIST, Manchester, UK, - 2003. - 22 с.
15. Broyden, C. G. Journal of the Institute of Mathematics and Its Applications.#6. - 1970. - 76-90 с.
16. Fletcher, R. Computer Journal.#13. - 1970. - 317 с.
17. Goldfarb, D. - 1970. - 23 с.
18. Shanno, D. F. Mathematics of Computation.#24. - 1970. - 647 с.
19. Walter, Eric ; Pronzato, Luc Identification of parametric models from experimental data. - London: Springer, 1997. - 403 с.
20. Schittkowski, Klaus Numerical data fitting in dynamical systems: a practical introduction with applications and software . - Dordrecht : Kluwer, 2002. - 392 с.
21. Nocedal, Jorge Mathematics of Computation.(Updating quesi-Newton matrices with limited storage.)#35 - 1980, - 773-782 с.

480 руб. | 150 грн. | 7,5 долл. ", MOUSEOFF, FGCOLOR, "#FFFFCC",BGCOLOR, "#393939");" onMouseOut="return nd();"> Диссертация - 480 руб., доставка 10 минут , круглосуточно, без выходных и праздников

Салеев Дмитрий Владимирович. Алгоритмическое обеспечение подсистемы оптимизации технологического процесса производства интегральных схем типа ТТЛ: диссертация... кандидата Технических наук: 05.13.06 / Салеев Дмитрий Владимирович;[Место защиты: Тамбовский государственный технический университет], 2016

Введение

1 Анализ исследований в области управления качеством при производстве интегральных схем 13

1.1 Исследование существующих теорий контроля качества продукции 13

1.2 Анализ технологического процесса производства интегральных схем 16

1.3 Анализ технологического процесса производства интегральных схем как объекта управления 20

1.4 Целевая функция технологического процесса производства интегральных схем 23

1.5 Анализ современных методов оптимизации технологических процессов и контроля качества производства интегральных схем и постановка задачи

исследования 27

Выводы к главе 1 37

2 Разработка подсистемы оптимизации технологического процесса производства интегральных схем 38

2.1 Сравнение статистических и адаптивных методов оптимизации технологических процессов 38

2.2 Анализ современных САПР для проектирования интегральных схем 39

2.3 Разработка подсистемы адаптивного управления как части автоматизированной системы управления технологического процесса производства интегральных схем 42

2.4Задача оптимизации и анализ методов многокритериальной оптимизации технологических процессов 46

2.5 Алгоритм выделения главного критерия качества технологического процесса производства интегральных схем 50

2.6 Модификация метода анализа иерархий Т. Саати для выбора лучшего технического решения при производстве интегральных схем 54

2.7 Алгоритм выбора технологического оборудования при производстве новой серии интегральных схем 58

2.8 Алгоритм управления технологическим процессом производства интегральных схем 64

2.9Алгоритм выбора режима построения модели технологического процесса 76

Выводы к главе 2 83

3 Моделирование управления технологическим процесом производства интегральных схем с использованием алгоритма управления технологическим процессом производства интегральных схем (с подстройкой модели) 84

3.1 Моделирование управления технологическим процессом производства интегральных схем с подстройкой модели 84

3.2 Реализация алгоритма управления технологическим процессом производства для интегральных серий 130 и 533 91

Выводы к главе 3 105

4 Формирование математических моделей технологических операций при производстве интегральных схем 106

4.1 Классификация и анализ методов аппроксимации нелинейных характеристик 106

4.2 Построение модели операции ионной имплантации 116

4.3 Алгоритм построения модели технологических операций производства интегральных схем 120

Выводы к главе 4 124

Заключение 125

Список литературы

Введение к работе

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

В научно-технической литературе большое внимание уделяется проблемам регулирования и управления ТП: известны работы авторов по данной тематике Я. Е. Львовича, В. В. Токарева, А. Е. Егорова и других Алгоритмы оптимизации и регулирования ТП производства ИС строятся в работах российских ученых В. К. Дорошевича, Ю. А. Долгова, в США исследования в данной области проводятся Д. А. Ходжсом, Д. Хурингом, Г. Смитом, в Белоруссии вопросы надежности ИС изучает группа ученых под руководством Д. Л. Ануфриева.

В сложившихся экономических условиях – с учетом роста курса доллара и евро, действующих в отношении России санкциях западных стран по запрету на продажу высокотехнологичного оборудования, в том числе для производства изделий микроэлектроники, а также реализующимися программами по созданию «Отечественной электронной компонентной базы, используемой при производстве вооружений, военной и специальной техники» и «Импортозамещению технологического оборудования и комплектующих изделий для производства вооружений, военной и специальной техники», необходимо проведение мероприятий, позволяющих производить на отечественном оборудовании ИС для различных отраслей промышленности.

Эффективное управление производством ИС может быть достигнуто при использовании современных подсистем оптимизации ТП с учетом его особенностей: влияния качества и неоднородности исходных материалов на качество ИС, групповой характер производства, многокритериальность, возможностью изготовления новой серии и (или) нового типа ИС с уровнем качества, отличным от ранее требующегося.

Таким образом, актуальность темы определяется необходимостью алгоритмизации подсистемы оптимизации конкретного класса ИС с целью повышения выхода годных.

Цель диссертационной работы – обеспечение заданного уровня качества производимых ИС типа ТТЛ и алгоритмизация соответствующей подсистемы оптимизации ТП производства ИС с целью повышения процента выхода годных ИС.

Для достижения поставленной цели ставятся следующие задачи :

провести исследование ТП производства ИС как объекта управления и современных САПР, выявить существующие недостатки и поставить задачу оптимизации;

разработать на основе проведенного анализа функциональную схему подсистемы оптимизации ТП процесса ИС;

проанализировать существующие подходы к многокритериальной оптимизации для применения в подсистеме оптимизации ТП производства ИС;

построить алгоритмы поиска оптимальных вариантов производства ИС – алгоритм построения математических моделей в условиях недостатка практиче-

ских данных, алгоритм выбора оборудования, алгоритм управления ТП с подстройкой модели;

провести имитационное моделирование работы ТП производства ИС с подстройкой модели, а также выдать рекомендации по корректировке настройки оборудования для важнейших процессов (операций) ТП производства ИС;

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

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

В диссертации получены следующие основные положения, выносимые на защиту и характеризующиеся научной новизной :

разработан алгоритм управления ТП производства ИС, компенсирующий влияние возникающих в ходе ТП неконтролируемых параметров (случайной и постоянной составляющих, в том числе устаревание оборудования) на итоговое качество производимых ИС;

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

предложена математической модель температуры кремниевой пластины в ходе операции некогерентного отжига, позволяющая с высокой точностью реали-зовывать температурно-временные режимы отжига пластин по заданной программе;

сформирован алгоритм построения модели технологических операций, отличающийся тем, что он позволяет с большей точностью в сравнении с используемыми в настоящее время в ТП моделями аппроксимировать функциональные зависимости технологических операций ТП производства ИС;

разработана функциональная схема подсистемы оптимизации ТП производства ИС, отличающаяся наличием модулей оптимизации и управления, определяющая механизм взаимодействия разработанных алгоритмов.

Практическая значимость результатов работы:

применение разработанного алгоритма управления ТП производства ИС с подстройкой модели в подсистеме оптимизации процесса производства позволяет добиться улучшения выходных параметров ИС;

функциональная схема подсистемы оптимизации ТП производства ИС определяет основные требования к алгоритмам управления и составу технологического оборудования;

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

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

Тематика работы соответствует следующему пункту паспорта специальности 05.13.06 – Автоматизация и управление технологическими процессами и производствами (по отраслям):

4. Теоретические основы и методы математического моделирования организационно-технологических систем и комплексов, функциональных задач и объектов управления и их алгоритмизация.

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

Основные положения, выносимые на защиту:

алгоритм управления ТП производства ИС с подстройкой модели с использованием обобщенного критерия качества;

алгоритм выбора режима построения модели ТП производства ИС;

алгоритм построения аппроксимационной модели технологических операций производства ИС;

функциональная схема подсистемы адаптивного управления ТП производства ИС.

Полученные теоретические и практические результаты были использованы при выполнении работ ФКА «Роскосмос» ОАО «Турбонасос» (с привлечением соисполнителей). Разработанные алгоритмы внедрены в учебный процесс «Воронежского института высоких технологий» – АНОО ВО.

Апробация работы. Основные положения диссертационной работы докла
дывались и обсуждались на следующих научно-технических конференциях: Меж
дународной молодежной конференции «Математические проблемы современной
теории управления системами и процессами», г. Воронеж, 2012 г.; Международ
ной молодежной конференции «Микроэлектронные информационно-
управляющие системы и комплексы», г. Воронеж, 2012 г.; IX Международной
научно-практической конференции «Техника и технология: новые перспективы
развития», г. Москва, 2013 г.; XII Всероссийской научно-технической конферен
ции «Новые технологии в научных исследованиях, проектировании, управлении,
производстве (НТ ВГТУ – 2013)», г. Воронеж, 2013 г.; XV Международной науч
но-практической конференции «Современное состояние естественных и техниче
ских наук», г. Москва, 2014 г.; XVI Международной научной конференции «Ак
туальные вопросы современной техники и технологии», г. Липецк, 2014 г.; VII
Международной научно-практической конференции «Фундаментальные и при
кладные исследования в современном мире», г. Санкт-Петербург, 2014 г.; конфе
ренции и семинары направления САПРИС Воронежского института высоких тех
нологий (2011-2015 гг.).

Публикация результатов работы. По теме диссертации опубликовано 14 научных работ, в том числе 5 в изданиях, рекомендованных ВАК РФ,

1 работа – в иноязычном издании, включенном в международную систему цитирования Web of Science, 2 работы написаны с другими авторами.

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка используемой литературы и приложений. Общий объем работы составляет 144 страницы машинописного текста, включая 41 рисунок, 11 таблиц, список литературы состоит из 127 наименований.

Анализ технологического процесса производства интегральных схем как объекта управления

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

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

Схема ТП производства ИС В общем случае схема ТП производства ИС представлена на рисунке 1.5. ТП изготовления ИС относится к классу дискретных : операции разделены во времени: только по окончании одной операции, начинается следующая: то есть операция (n+1, n=0,1,2 …m) начинается по окончании операции n, затем начинается n+2) . Таким образом, при разработке подсистемы оптимизации необходимо учитывать, что значения выходных параметров на большинстве технологических операции при производстве ИС могут быть измерены только по ее окончании и до начала следующей и фактически измерения (операции контроля) также проходят дискретно.

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

В настоящее время технологии позволяют изготавливать ИС, состоящих до одного миллиона элементов и более – БИС и СБИС.

ТП производства таких ИС состоит из сотен последовательных операций по формированию структурных слоев . Главной технологической задачей является формирование этих структурных слоев с наиболее высокой точностью.

Этого можно достичь с использованием различных методов оптимизации, адаптивного управления, корреляционным анализом и прочим в алгоритмах управления ТП: проводится учет неконтролируемых параметров на ТП и на каждую операцию .

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

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

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

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

Необходимость управления ТП определяется тремя основными факторами: 1. технические характеристики входных и выходных компонентов должны поддерживаться на требуемом уровне от партии к партии; 2. остановка каждой технологической операции должна выполняться в соответствии и имеющимися алгоритмами, синхронизирующими включение или отключение или изменение воздействия на процесс со стороны различного оборудования; 3. постоянный технологический износ оборудования требует регулярной коррекции параметров процесса. Запишем полную модель ТП как последовательность отдельных технологических операций. Рассмотрим (7-1)-ю операцию ТП. ut=F(ut_1,vt), где щ это параметры качества ИС на текущей операции (конструктивные), v,- -вариант производства, то есть некоторая совокупность воздействующих на процесс изготовления параметров, задаваемых системой управления. Однако необходимо учитывать, что фактически требуются не параметры качества ИС (глубина р-п перехода, доза внедренных ионов и прочие), а конструктивные параметры, зависящие от них (быстродействие, стойкость к радиационным воздействиям и прочие), то есть: gt=F\ut_1,kt), где gt - это контролируемые параметры текущей операции, kt - это конструктивные параметры.

Процесс изготовления ИС является по существу последовательным переходом из одного состояния в другое по некоторой траектории.

Так как целью проведения ТП является получение заданных характеристик производимых ИС, то для использования в управлении режимами производства и в ТП, необходимо получить несколько (множество) функций (траекторий), позволяющих управлять ТП: происходит коррекция (подстройка) по конечному состоянию. Фактически, необходимо решить задачу траекторного управления, то есть найти оптимальное решение из множества с учетом заданных характеристик изготавливаемой ИС - то есть подобрать такие значения управляющих воздействий, чтобы выходные характеристики изготавливаемой ИC ,"(где п -общее число операций в ТП) были максимально совпадающими с требуемыми .

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

Анализ современных САПР для проектирования интегральных схем

Основная задача для повышения эффективности ТП состоит в создании и настройке (подстройке под конкретные параметры выходных характеристик ИС в зависимости от типа изделия, производимого в данный момент): в АСУ ТП помимо функции управления текущим ТП, должна быть реализована возможность хранения данных (система баз данных), являющихся характеристиками ТП и (или) влияющими на конечные характеристики изготавливаемых ИС – настроек оборудования в зависимости от типа производимой ИС, показания КИП (датчиков) в момент производства ИС, записи сообщений о сбоях и ошибках в ТП, которые впоследствии можно будет использовать для прогнозирования выхода годных изделий при производстве новой серии аналогичных ИС, для анализа параметров ТП – настроенности, эффективности с целью их улучшения, поиска ошибок в ТП, оценки экономической эффективности производства ИС данной серии .

АСУ ТП должна состоять из нескольких модулей (подсистем) – подсистемы управления технологическими операциями (каждой технологической операции), управления режимами ТП, модуля управления транспортными операциями, подсистемы межоперационного контроля и работать в режиме реального времени.

Таким образом, АСУ ТП производства ИС должна обеспечивать трансляцию информации от конструктора до производства, имея при этом обратные связи, которые позволяют вести разработку новых модификаций, устранять ошибки, выявленные в ходе производства, производить текущий контроль производства.

Для оптимизации производства в составе АСУ ТП применяются различные системы управления качеством производимых изделий, в состав которых входят подсистемы оптимизации производства .

Под предлагаемой автором данной работы подсистемой оптимизации понимается автоматизированная система, обеспечивающая различные виды воздействий на ТП производства ИС на любом этапе производства с целью улучшить качество выпускаемой продукции: уменьшить количество бракованных (или не соответствующих техническим требованиям, предъявляемым к изделиям согласно техническому заданию (негодных)), улучшить качество производимой в данной момент серии ИС, используя ранее полученные данные .

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

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

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

Основой модуля автоматизированного задания является головная программа, осуществляющая передачу настроек и параметров ТП производства ИС с целью корректировки настроек оборудования и поддержания заданного уровня качества производимых изделий. Для возможности корректировки ТП в ручном режиме предназначены программы обработки сообщений и программы диалогового взаимодействия. Программы ИС С помощью модуля ввода и вывода оператор может выгрузить из базы данных текущие настройки, либо задать их в ручном режиме (посредством ручного ввода или загрузки из файла историй настроек, использовавшихся при производстве микросхем ранее), а также указать характеристики используемых материалов (сырья).

В модуле оптимизации составляется список операций, получаемого из системы управления верхнего уровня для данного конкретного ТП и проводится его анализ: задается точность оптимизации и параметры производства (настройки оборудования).

Полученная информация передается в модуль прикладных моделей, который характеризуется наличием аналитических, статистических моделей (теоретических, а также практических, составленных с использованием метода регрессионного анализа ) основных операций ТП производства ИС: отжига, окисления, имплантации и прочих для определения «точек контроля». Здесь происходит определение входных и выходных параметров для каждой последовательной операции ТП и формирование целевой функции оптимизации.

Ключевой особенностью предлагаемой нами подсистемы оптимизации производства ИС является модуль управления. В нем используется алгоритмы управления (с подстройкой модели) . Данный модуль в процессе производства формирует и уточняет математическую модель, полученную из модуля прикладных моделей, а также передает ее в модуль автоматизированного задания: проводятся процедуры максимизации целевой функции ряда дискретных аргументов при наложении функциональных, топологических ограничений . Полученные настройки оборудования, параметры процесса и выражения для управления заносятся в базу данных для возможности анализа процесса и загрузки при производстве следующих партий ИС.

Реализация алгоритма управления технологическим процессом производства для интегральных серий 130 и 533

Фактическое значение рассчитывается путем подстановки в целевую функцию вместо текущих значений Yтек, величин, измеряемых на выходе ТП.

Расчетное значение нами предлагается найти подстановкой значений выходных переменных Y1i и Y2i, рассчитанных по математической модели.

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

Значения управляющих и выходных переменных для i-гo момента обозначим через U1i, U2i, U1i, U2i. Взаимодействие с системой управления предлагается организовать следующим образом: Передача данных в систему управления начинается в момент времени t=t0=0. С момента начала ТП требуется некоторый промежуток времени (с момента t=t0 до t=ti, i=1,2…n) для сбора сведений о текущем состояний системы: настройках оборудования, заданных алгоритмах производства ИС и прочего. В момент времени t=ti начинается реализация алгоритма управления. Включение системы управления (то есть управление ТП) начинается с момента времени ti ,то есть с момента включения технологического оборудования. В процессе управления передаваемые данные заносятся в систему управления и записываются в файлы истории ТП через определенный промежуток времени.

При оптимизации ТП следует ограничить данные передаваемые в систему управления, используемые в настоящий момент: нужно применять данные за последний промежуток времени – t, так как ранее записанные данные являются устаревшими. Начало Измерение выходных переменных текущей операции Вычисление расчетного и фактического значений целевой функций Fфактич_i , Fрасч_i Уточнение параметров модели и параметров уравнений адаптивных уравнений I Расчет Xопт Передача сигнала в АСУ на корректировку режима работы Нет Рисунок 2.11 – Алгоритм управления ТП производства ИС Момент времени t=0 – момент первого измерения параметров ТП. Величина t подбирается с учетом времени проведения каждой технологической операции.

Таким образом, АСУ ТП получает и передает данные, необходимые для адаптации под фактическое состояние ТП. Для определения влияния степени воздействия с помощью системы управления под фактическое состояние процесса для производства последующих серий изделий используется регрессионный анализ и данные, переданные в АСУ ТП.

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

Полученная таким образом модель используется в алгоритме управления ТП по любому из параметров качества .

Для практической реализации, необходимо информационно-вычислительное устройство, канал передачи данных с технологической системой с обратной связью (двунаправленный), использование данных контрольно-измерительных приборов (датчики) системы управления ТП производства ИС для контроля входных, выходных параметров процесса, а также воздействий на процесс . Рисунок 2.12 – Структурная схема модуля управления

Предлагаемая структурная схема блока подстройки математических моделей технологической системы представлена на рисунке 2.12. Систему автором предлагается разрабатывать на базе существующей системы управления ТП производства ИС (блок АСУ на рисунке 2.1), в составе: системы технологического оборудования (ТО); системы датчиков (КИП), снимающих информацию о текущем значении параметров качества; ПЛК.

Контроллер предназначен для организации обмена информацией датчиков с ЭВМ и технологической системой. Связь ЭВМ с контроллером осуществляется через стандартный интерфейс RS-485 / RS-232 .

Функциональная схема блока подстройки математических моделей технологической системы представлена на рисунке 2.13.

Программное и алгоритмическое обеспечение блока подстройки математических моделей можно разделить на две части.

Первая часть относится к алгоритмическому обеспечению аппаратной части системы управления ТП производства ИС и выполнение заданного режима работы и запись информации в базу данных для возможности в дальнейшем оценки качества производимой в данной партии ИС.

Алгоритм можно разделить на несколько блоков: блок «Анализ исходных данных» предназначен анализа исходных данных перед началом текущей операции.

К исходным данным относятся: исходное сырье (материалы), режимы работы, перечень параметров качества которые необходимо обеспечить в ходе производства, и их требуемые значения. По введенным данным модуль управления устанавливает, существует ли ранее использовавшаяся математическая модель, полученная при производстве предыдущих партий ИС .

Построение модели операции ионной имплантации

Рассмотрим в качестве примера график зависимости толщины окисла от времени при постоянных температуре и давлении газообразного окислителя.

На рисунке 4.2 представлена теоретическая зависимость толщины окисла от времени окисления при постоянных температуре и давлении газообразного окислителя, на рисунке 4.3 – экспоненциальная аппроксимация вышеуказанной характеристики.

Существенным недостатком экспоненциальной аппроксимации является ограниченность его применения .

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

К преимуществам использования данной аппроксимации стоит отнести достаточно простые расчеты коэффициентов аппроксимации. Кусочно-линейная аппроксимация.

Основной принцип кусочно-линейной аппроксимации состоит в том, чтобы исходная зависимость разбивается на несколько отрезков небольшой длины, на которых она имеет вид близкий к линейному. Таким образом, на каждом участке зависимость аппроксимируется функцией вида: F(x) = Kx + b где К и Ъ это некоторые коэффициенты. Результатом аппроксимации будет некоторая функция: (К0х + Ь0,х = 0...х0 K1x + b1,x = x0...x1 F(x)=.... Кхп + bn,x = xn_1...xn Недостатком аппроксимации такого вида является возможность разрыва аппроксимирующей функции в местах х0, xh…, xn. Однако, исходя из принципов формирования полупроводниковых подложек и ИС, разрывы в аппроксимационной функции физически не могут быть обоснованы.

Исходя из этого, при применении данного вида аппроксимации, требуется выполнение условия согласованности (сходимости) соседних отрезков: F(xt) = Ktxt + bt = Ki+1xt + bi+1 i = 0...n что может привести в конечном итоге к увеличению числа отрезков, либо к существенному возрастанию погрешности аппроксимации.

Для недопущения разрыва функции в точках перехода, для каждой линии из двух отрезков (ломаная линия из двух прямолинейных отрезков) используются выражение вида: F(x) = -(\x\ + x) Достоинством кусочно-линейной аппроксимации является простая форма аппроксимирующей функции (выражения для расчета коэффициентов) и малые вычислительные затраты. Аппроксимация зависимости представлена на рисунке 4.4.

Результаты кусочно-линейной аппроксимации (сплошная линия) зависимости толщины окисла от времени окисления при постоянных температуре и давлении газообразного окислителя (число разбитий = 16). Существенным недостатком кусочно-линейной интерполяции – в точках стыка двух отрезков имеется излом. При аппроксимации нелинейных характеристик с высокой степенью точности, необходимо увеличение количества отрезков, на которых данная функция рассматривается, что в конечном итоге потребует значительных вычислительных затрат. При этом увеличение числа отрезков требует увеличения числа практических (экспериментальных) данных, что возможно далеко не всегда.

Полиномиальная аппроксимация. Для полиномиальной аппроксимации используется следующее выражение: т=Ъу (4.2) г=0 где п (п=0,1,2…т - степень полинома, Kt - коэффициенты аппроксимации, т -порядок полинома. При порядке полинома равном единице, выражение (4.2) представляет собой по сути выражение для линейной аппроксимации. С увеличением порядка полинома (степени полинома), ошибка аппроксимации уменьшается .

Для нахождения коэффициентов аппроксимации наиболее часто для широкого круга задач используется метод наименьших квадратов , который состоит в следующем: проводится поиск таких значений коэффициентов регрессии, при которых сумма квадратов отклонений теоретического распределения от фактического (экспериментального) была бы наименьшей: m .-F(jc,.))2- min V 2=1 где (хь F(x{)), (х2, F(x2))… (xN, F(xN)) - заданный набор точек (экспериментальные данные). Аппроксимационная функция ищется в виде многочлена т-ой степени: F(xt) = К0 + K1xt + K2x2 +... + Ктх = J К$ 7=0 Требуется найти набор коэффициентов аппроксимации Ц}, для которых значения функции/ будет максимально приближена к практическим данным. Для этого (4.1) дифференцируется по каждому из параметров я,- и приравнивается к нулю.

В общем случае получается система уравнений, которая решается в матричном виде. Результаты аппроксимации экспериментальных данных зависимости глубины залегания бора в кремнии. Вид аппроксимации Вид функции аппроксимации Погрешность аппроксимации Числоопераций(асимптотическаяоценка) Экспоненциальная F(x) = F0-exp(Kx-b) 2,510-2 O(log n) Кусочно-линейная F{x) = Kx + b 1,14 Ю-2 Зависит отчисла разбиений0(п2) Полиномиальная(метод наименьшихквадратов) г=0 2,16 КГ4 (п=4) О(п) Сравнение результатов аппроксимации зависимости толщины окисла от времени окисления при постоянных температуре и давлении газообразного окислителя представлены в таблице 4.2.

Таким образом, наибольшую точность показал метод наименьших квадратов, предлагается использовать его для аппроксимации функциональных зависимостей в алгоритме построения моделей технологической операции подсистемы оптимизации ТП производства ИС.

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

Из теоретических данных известно, что профиль внедренных ионов представляется в виде гауссовой кривой с максимумом концентрации примеси на глубине Rp: где Щх) - концентрация внедренной примеси, L доза ионов, Rp - средний пробег ионов, ARP - дисперсия среднего проективного пробега. Однако на практике при имплантации, форма профиля внедренных ионов может существенно отличаться от гауссовой. Причины данного несоответствия теоретических и практических данных связаны, в частности, с тем, что происходит диффузионное перераспределение примеси, а также наблюдается эффект каналирования, а также влияют другие факторы .

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

Эта последовательность графиков иллюстрирует применение метода исследователей к реальной проблеме компьютерного зрения. Решение каждой задачи (красные шарики) используется для инициализации (зеленые стрелки) поиска решения в последующей.

В январе на Международной конференции по методам геометрической оптимизации в компьютерном зрении и распознавании образов, Хоссейн Мобэхи (Hossein Mobahi), учёный, проводящий докторские исследования в Массачусетском технологическом институте информатики и лаборатории искусственного интеллекта (Computer Science and Artificial Intelligence Laboratory - CSAIL), и Джон Фишер (John Fisher), старший научный сотрудник в CSAIL, описали способ генерации последовательности упрощенных функций, что гарантирует наилучшее приближение у применяемого в настоящее время метода.

«На некоторые фундаментальные вопросы об этом методе мы отвечаем впервые», - говорит Мобэхи. - «Например, я сказал вам, что надо начинать с простой задачи, но не сказал, как выбрать эту простую задачу. Существует бесконечно много функций, с которых вы можете начать. Какая из них лучше? Даже если я скажу вам с какой функции стоит начать, есть бесконечно много способов её преобразования для определенной задачи. И это преобразование влияет на то, что вы получите в конце».

Достижение минимума

Чтобы понять, как работает оптимизация, предположим, что вы ритейлер консервированных продуктов. Вы пытаетесь сэкономить деньги на стали и хотите, чтобы соотношение площади поверхности банки к её объёму сводилось к минимуму. Это соотношение является функцией от высоты и радиуса, так что если вы сможете найти минимальное значение функции, то будете знать оптимальные размеры банки. Если вы дизайнер автомобилей, который старается сбалансировать затраты на компоненты, изготовленные из различных материалов, с весом и аэродинамическим сопротивлением автомобиля, ваша функция - известная в оптимизации как «функция затрат» - будет намного сложнее, но принцип останется все тем же.

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

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

Однако локальный минимум гарантированно будет глобальным, если функция - выпуклая вниз. Функция f(x) = x 2 выпуклая, так как описывает параболу с центром в начале координат. Функция f(x) = sin х - нет, так как описывает синусоиду, которая колеблется вверх и вниз.

Сглаживание

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

Веса, присвоенные близлежащим значениям, определяются функцией Гаусса или нормальным распределением - колоколообразной кривой, знакомой из статистики. Близлежащие значения рассчитываются преимущественно по средним, а не отдаленным значениям.

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

«Метод продолжения оптимизации на самом деле широко используется в практике, в компьютерном зрении, для решения проблемы выравнивания, отслеживания и во многих других задачах, но сам он не очень понятный», - говорит Джон Райт (John Wright), доцент кафедры электротехники в Колумбийском университете. - «Самое интересное в работе Хоссейна в целом, и этой статье, в частности, в том, что он действительно копается в этом методе и пытается узнать, что можно сказать о нем с точки зрения аналитики».

«Практическая польза состоит в том, что может быть любое число различных способов, которыми вы могли бы пойти при выполнении сглаживания или попытке осуществить «грубо-точную» оптимизацию», - добавляет Райт. - «Но если вы заранее знаете о правильном пути, то вам не нужно тратить много времени на неверные методы. У вас уже есть рецепт, так зачем искать что-то иное?»

В зависимости от природы процесса, от характера ма­тематической модели, от наличия информации о процес­се, от постановки задачи применяются различные ме­тоды оптимизации процессов (табл. 22.1).

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

Таблица 22.1

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

Эти методы применяются для решения задач с из­вестным аналитическим выражением критерия оптималь­ности, Приравнивая нулю производные и решая конеч­ную систему уравнений, определяют экстремальные значения параметра оптимизации.

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

Методы вариационного исчисления обычно применяют для решения задач с критерием оптимальности в виде функционалов. Вариационными методами решение зада­чи сводится к интегрированию системы дифферен­циальных уравнений Эйлера второго порядка с гра­ничными условиями. Число уравнений системы равно числу неизвестных функций.

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

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

Линейное программирование используется для реше­ния задач оптимизации с линейным выражением для кри­терия оптимальности и линейными ограничениями на область изменения переменных факторов. Это задача оп­тимального планирования производства с ограниченным количеством ресурсов, транспортные задачи и др. Уни­версальный алгоритм решения задач линейного програм­мирования содержится в симплексном методе, позволяю­щем за конечное число операций найти оптимальное решение большинства задач.

Методы нелинейного (динамического) программирова­ния применяют для решения задач оптимизации с нели­нейными функциями параметра оптимизации с огра­ничениями и без ограничений на независимые пере­менные.

Для оптимизации стохастических процес­сов используются экспериментально-статистические ме­тоды. Различают пассивный и активный эксперимент. Пассивный эксперимент, или, как его часто назьюают, пас­сивное наблюдение, использует методы математической статистики для обработки информации с целью изучения закономерностей технологического процесса. При этом сбор исходных данных проводится на действующем объекте без введения в процесс искусственных изменений. Обработка данных с целью получения математической модели процесса проводится в основном методами классического регрессионного и корреляционного методов ана­лиза.

Активный эксперимент основан на применении плани­рования эксперимента. Планирование эксперимента - это проведение эксперимента по заранее составленному пла­ну (матрице), обладающему оптимальными свойствами. При планировании учитываются одновременно все фак­торы, влияющие на процесс, что позволяет выявить сразу и силу взаимодействия факторов, и резко сократить об­щее число опытов для определения оптимальных параме­тров. Как в пассивном, так и в активном эксперименте математической моделью является функция отклика, связывающая параметр оптимизации с факторами, влияющими на процесс.

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

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

Управлением в динамическом программировании называется совокупность решений, принимаемых на каждом этапе с целью влияния на ход всего процесса. В прикладном плане задачи динамического программирования - это на 90 % задачи планирования: объемов производства, поставок сырья, величины финансирования и т. д. Например, совокупность решений, принимаемых в начале календарного года по обеспечению сырьем, замене оборудования, размерам инвестиций - это все этапное планирование, которое должно обеспечить генеральную задачу - максимальный выпуск продукции в конце года. И простыми мерами: использование оборудования на полную мощность, максимально возможные инвестиции - генеральную задачу не решить, т. к. начинают влиять другие факторы, например износ оборудования. В таком случае необходимо поэтапное планирование, т. е. замена оборудования при его износе на определенных этапах. Таким образом, выпуск продукции - многоэтапная задача, каждый из этапов которой осуществляет влияние на конкретную цель.

На рис. 4.5, а приведена область возможных состояний системы для одномерного случая, на рис. 4.5, б, в - для двумерного и трехмерного случая соответственно.

Область возможных состояний системы - это совокупность состояний, в которые может переходить система. Например, в случае а - это ось ОЛ" или ее участок, а управление - это закон движения точки из состояния х° -» х к.

Рис. 4.5.

Постановка задачи

Пусть состояние некоторого объекта описывается вектором фазового пространства х - (х, х 2 ,..., х я) е R„. Будем считать, что процесс является /V-шаговым, т. е. его эволюция происходит за N шагов по схеме

Переход между состояниями на к -м шаге осуществляется в соответствии с уравнением состояния

где й к е R"" - ш-мерный вектор управления на к -м шаге; J" k (x,Ti) - «-мерная векторная функция аргументов х , й.

Распишем компоненты вектора х к - /Дх*~", х*“",х к ~", и к, и к, н*). Таким образом, предполагается, что в результате к-vo шага система переходит в состояние х к, которое определяется только начальным состоянием этого шага х к ~" и выбранным на нем вектором управления й к и не зависит от предыстории процесса х°, х 1П, х (*~ 2) , н"’,..., н (*~ |) .

Показателем эффективности к -го шага является заданная числовая характеристика (целевая функция) этого шага:

А эффективность всего процесса складывается из этапных целевых функций

На фазовые траектории х и управления й наложены ограничения:

Множества Х к а U к заданы в пространствах R", R"".

Кроме того, заданы начальные и конечные условия:

Часто множества Х 0 и X N содержат по одной точке, определяющей начало и конец фазовой траектории.

Общую задачу многошаговой оптимизации можно записать следующим образом:

Требуется среди всех управлений ueU выбрать такое й" =(«*", м’ Л), для которого целевая функция (4.18) принимает экстремальное значение (минимальное или максимальное).

Пример 1. Сформулировать следующую оптимизационную задачу в виде многошаговой задачи оптимизации.

С помощью iV-ступенчатой ракеты с заданной стартовой массой М в космос выводится межпланетная станция массой т. За время работы каждая ступень ракеты получает добавочную скорость

A V = F(y,z),

где у - масса, разгоняемая этой ступенью; z - масса самой ступени.

Найти такое распределение массы ракеты (М) между ее ступенями, при котором конечная скорость ракеты максимальна.

Пусть й к (k = ,N ) - масса к -й ступени, начиная от межпланетной станции, т. е. на старте работает ступень массой г/ Л, в конце - и".

Обозначим х к (к = О...Л0 сумму масс межпланетной станции и к ступеней, примыкающих к ней.

Теория многошаговых оптимизационных задач разработана в 50-х годах американским математиком Р. Веллманом. Метод решения такой задачи носит название метода динамического протраммирования и основан он на принципе оптимальности Веллмана.

Оптимальная траектория обладает тем свойством, что каждая се завершающая часть, начинающаяся с к -го шага (& = 1, N - 1), является оптимальной для остающихся шагов процесса. Другими словами, на каждом этапе решения, учитывая развитие всего процесса, оптимизируют только один шаг. И таким образом, при принятии решения учитывают будущее. Однако в каждом процессе есть последний к -й шаг, который нс зависит от будущего. Поэтому на этом шаге управление позволяет получить максимальный эффект. Спланировав к -й шаг, к нему присоединяют (к - 1), затем (к - 2) и т. д. Процесс динамического программирования как бы разворачивается от конца к началу.

Чтобы спланировать к -й шаг, надо знать состояние системы на (/: - 1) шаге. Если состояние на (к - 1) шаге неизвестно, то делают различные предположения о возможных состояниях системы на этом шаге. Для каждого предположения выбирают оптимальное управление на последнем к -м шаге. Такое оптимальное управление называют условно оптимальным.

Рассмотрим ^-шаговый процесс (рис. 4.6). Сделаем ряд предположений о возможных состояниях процесса на (к - 1) шаге. Обозначим эти состояния S k _i , S k _ ] 2 ,..., S k ^ r . На последнем найдем для каждого из этих состояний условно оптимальное управление и к, (x t _,), и к 2 (х А._,),..., и к г (х 4 _, г).

Таким образом, к -й шаг спланирован. Действительно, какое бы состояние система ни принимала на (к - 1) шаге, уже известно как следует поступить на &-м.

Аналогично поступаем на (к - 1) шаге, только условно оптимальные управления необходимо выбирать, учитывая уже выбранные условно-оптимальные на к -м шаге. В итоге, выполнив все переходы, получим координату х°.

Для первого шага предположений не делаем, т. к. значение х° задано, далее находим оптимальные управления, учитывая все уже найденные. Проходя от х°к х*, получаем искомое оптимальное управление для всего процесса. Используя принцип оптимальности, найдем необходимые условия, которым должна удовлетворять оптимально управляемая последовательность и,..., м v _,.

Рис. 4.6.

Рассмотрим конечный участок траектории - интервал . И допустим, что для интервалов найдены оптимальные управления и оптимальная траектория, включая х к. Остается найти управление н А,...,м у на конечном участке. Из принципа оптимальности следует, что {w A ,...,w v } определяется только состоянием х к _ { и целью поиска экстремума, которая для [ к , N] имеет вид

при х-х ч, й = и ч целевая функция Z k имеет оптимальное значение (максимум или минимум). Обозначим его

Аналогично

Из принципа оптимальности можно записать следующие рекуррентные выражения:

Соотношения (4.19)-(4.20) позволяют последовательно найти функции Веллмана.

В„ (х Л -|), B N _ { {x N - 2),..., 5, (х°) - уравнения Веллмана.

Находя В к (х к ~"), к = N, N -мы одновременно находим управления ы,*(дг*’ 1), которые называются условно-оптимальными управлениями, а процесс их нахождения - условной оптимизацией.

Управление м.*(х*~"), найденное из уравнения (4.20), удовлетворяет принципу оптимальности: т. е. в зависимости от начального состояния х к ~" управления и к учитывает оптимизацию не только к-го шага, но и следующих за ним (N - к) шагов.

Итак, в результате условной оптимизации находят В к (х к ~") и и к (х к ~"), к = N, N- 1,..., 1. Теперь можно осуществить безусловную оптимизацию задачи (4.18), т. е. найти искомые оптимальные управления и = (ии ?) и оптимальную фазовую траекторию х = (х,°,..., х? ).

Т. к. значение B t (x°) равно оптимальному значению целевой функции всех N шагов, то

если х 0 - первая точка траектории, то х,° = х°.

Алгоритм метода динамического программирования

Этан I. Условная оптимизация.

Шаг 1. Находим условно-оптимальные управления г/*(х ЛЧ) и функцию Веллмана B N (x N ~") в соответствии с соотношением (4.19).

Шаг 2. Находим ^"""(х* -2) и /? v _,(x v ~ 2).

Шаг N. Находим м"(х°)и 5,(х°).

Этап II. Безусловная оптимизация.

Шаг 0. Находим х.° в соответствии с (4.21).

Шаг 1. Находим и 1 . и х по формулам (4.22).

Шаг N. Находим w. v и x. v .

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

И хотя метод динамического программирования существенно упрощает исходные задачи, однако непосредственное его применение, как правило, сопряжено с громоздкими вычислениями. Для преодоления этих трудностей существуют приближённые методы динамического программирования.

Этап I. Условная оптимизация.

Найдем уравнения Веллмана по формуле (4.19).

Шаг 1. Я,(х 2) = шах

Диапазон и 3 найден из следующих соображений: так как

Учитывая, что х г е, получаем диапазон изменения м 3:

Функция - при всех значениях х является возрастающей аргу-

мента и поэтому ее максимум

Шаг 2. С учетом формулы (4.20)

Находим стационарную точку из условия -^-:

ШагЗ. B,(x°)= max (2 , -1 + -).