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

2. Апресян, Ю. Д. Идеи и методы современной структурной лингвистики / Ю. Д. Апресян. М. : Наука, 1966.

3. Вердиева, З. Н. Семантические поля в современном английском языке / З. Н. Вердиева. М. : Высш. шк., 1986.

4. Никитин, М. В. Лексическое значение слова / М. В. Никитин. М. : Высш. шк., 1983.

5. Личаргин, Д. В. Операции над семами слов естественного языка в машинном переводе / Д. В. Личаргин // Тр. конф. молодых ученых / Ин-т вычисл. моделирования Сиб. отд-ния Рос. акад. наук. Красноярск, 2003. С. 23-31.

6. Личаргин, Д. В. Устранение семантического шума как средство адекватного перевода / Д. В. Личаргин // Вопросы теории и практики перевода : тр. Всерос. конф. Пенза : Приволж. дом знаний, 2003. С. 90-92.

7. Личаргин, Д. В. Порождение фраз естественного языка в рамках задачи построения естественно-языкового интерфейса с программным обеспечением / Д. В. Личаргин // Проблемы информации региона (ПИР-2003) : материалы Восьмой Всерос. конф. / Краснояр. гос. техн. ун-т. Красноярск, 2003. Т. 2. С. 152-156.

K. V Safonov, D. V. Lichargin

ELABORATION OF A VECTOR BASED SEMANTIC CLASSIFICATION OVER THE WORDS AND NOTIONS OF THE NATURAL LANGUAGE

The problem of vector-based semantic classification over the words and notions of the natural language is discussed. A set of generative grammar rules for the generation of the semantic classification vector is offered. The examples of the classification application are given. A theorem ofoptionalformal classification incompleteness is presented. The principles of assigning of the meaning-bearing functions over the classification word groups are analyzed.

Keywords: natural language generation, natural language semantics.

© Сафонов К. В., Личаргин Д. В., 2009

УДК 519.688

П. В. Галушин, Е. С. Семенкин АСИМПТОТИЧЕСКИЙ ВЕРОЯТНОСТНЫЙ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ*

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

Ключевые слова: вероятностный генетический алгоритм, мутация, селекция.

Вероятностный генетический алгоритм (ВГА) является попыткой создания алгоритма, имеющего схему, похожую на схему традиционного генетического алгоритма (ГА), и сохраняющего основные свойства генетических операторов, но сформулированного в терминах теории псевдобулевой оптимизации [1]. В вероятностном генетическом алгоритме, в отличие от традиционного ГА, явным образом вычисляются компоненты вектора вероятностей и отсутствует оператор скрещивания (вместо него используется оператор случайного выбора решения в соответствии с построенным распределением), однако сохранены генетические операторы мутации и селекции.

Целью проведенного авторами исследования была разработка модификации вероятностного генетического

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

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

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

* Работа выполнена при финансовой поддержке АВЦП «Развитие научного потенциала высшей школы» (НИР 2.1.1/2710) и Федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» (НИР НК-136П/3).

на вероятность того, что этот ген будет равен единице после мутации. Обозначим искомую вероятность как р', а вероятность мутации - как р .

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

Р {у = 1} = Р {х= 1} (1 - рт ) + Р {х = 0} рт =

= р(1 - рт ) + (1 - р)рт= рт + р(1 - ^т )-

Используя введенные выше обозначения для вероятностей значений генов и вероятности мутации, получим

р' = рт + р

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

Можно сказать, что традиционная реализация мутации в ВГА есть вычисление распределения генов после мутации с помощью метода Монте-Карло, которое сводится к стохастической аппроксимации результатов вычисления по формуле (1). Название асимптотическая мутация обусловлено тем, что данная процедура является предельным случаем традиционного оператора мутации при размере популяции, стремящемся к бесконечности.

Рассмотрим некоторые свойства предложенной процедуры мутации. Преобразование, которое она задает, является линейным, сжимающим отрезок [0; 1] до отрезка [рт, 1 - рт]. Действительно, линейность следует непосредственно из формулы (1), а границы интервала можно получить, подставив вместо р значения 0 и 1 соответственно. Так как линейная функция является монотонной, то значения из интервала [0; 1] будут отображаться в интервал [р ; 1 - р ]. Таким образом, мутация не позволяет вероятности р приближаться к 0 или 1 более чем на величину рт. Это исключает вырождение распределения, а значит и преждевременную сходимость по отдельным компонентам бинарного представления решения.

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

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

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

тервале [0; 1], и если оно попадает в интервал [0; рт], где рт - вероятность мутации, то ген необходимо инвертировать. Таким образом, при использовании стандартной реализации оператора мутации на каждой итерации необходимо выполнить 0(Ы ; М) действий, где N - размер популяции; М - число генов. При этом большая часть генов не будет инвертирована, так как вероятность мутации обычно выбирается очень малой.

Но какова вероятность того, что решение вообще не изменится в ходе мутации? Решение не изменится, если ни один из его генов не будет изменен. Вероятность того, что данный ген не будет изменен, не зависит от того, были ли изменены другие гены, и равна 1 - р = q . По правилу вычисления вероятности одновременного наступления независимых событий получаем, что искомая вероятность Q = (1 - р )М. Для выбора вероятности мутации часто используется следующее правило: рт = 1/М, тогда Q » ег\ Данное соотношение выполняется довольно точно уже при М, равном 10. Это значит, что более трети решений в ходе мутации вообще не изменятся, т. е. все вычисления, связанные с реализацией оператора мутации, действующего на решения, более чем в трети случаев проводятся только для того, чтобы установить, что никаких действий выполнять не нужно.

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

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

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

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

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

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

пр+С

рв _-------,

в п+2С

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

Проведя элементарные преобразования, получим, что байесовская оценка вероятности эквивалентна мутировавшей классической оценке вероятности мутации, если выбрать вероятность мутации равной С/(п + 2 С).

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

Пусть популяция состоит из особей х1, ..., хп, каждой из которых назначена вероятность быть отобранной в одном испытании 81, ..., g Подсчитаем математическое ожидание вероятности того, что /-й ген окажется равным единице в одном испытании:

.(/) =

= X х*) 8к.

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

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

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

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

Пусть размер турнирной группы равен & Предположим сначала для простоты, что все решения имеют различную пригодность. Подсчитаем вероятность того, что особь с к-м значением пригодности пройдет отбор. В турнирную группу каждое решение может попасть с равной вероятностью, т. е. распределение равномерное. Победителем турнира будет особь с наибольшим рангом, т. е. ранг победителя турнира распределен как максимум & равномерно распределенных случайных величин [3]:

_ к& - (к -1)&

8к .

Рассмотрим теперь случай повторяющихся значений пригодности. Пусть в популяции встречается К различных значений пригодности и к-е значение встречается пк раз. Тогда имеет место равенство

К

X пк_п

к_1

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

_ 81, Ск_Ск-1+8к, к_ 2,..., К.

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

X'

V1=1

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

Используя описанные выше методы реализации асимптотической мутации и селекции, получим модификацию ВГА со следующей схемой:

к_1

1. Создать и оценить начальную популяцию с равномерным распределением генов.

2. Если выполнен критерий останова, то прекратить работу.

3. Построить распределение с помощью асимптотического метода селекции.

4. Скорректировать распределение с помощью асимптотического оператора мутации.

5. Создать новую популяцию с полученным распределением вероятностей генов. Оценить новую популяцию.

6. Перейти к п. 2.

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

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

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

При сравнении алгоритмов использовались следующие настройки: размер популяции - 100, максимальное число итераций - 50, число запусков для определения характеристик качества - 1 000, мутация - слабая, метод кодирования - код Грея. Сравнение производилось отдельно для каждого метода селекции и тестовой функции, причем оценка характеристик выполнялась пять раз. Для тестирования были использованы те же стандартные тестовые функции, что и в работе [1].

Для проверки гипотез о значимости различий использовался непараметрический критерий согласия Уилкок-сона-Манна-Уитни [4] с объемом выборок 5. Результаты тестирования алгоритмов приведены в табл. 1, в которой указаны медианы усредненных по всем тестовым

функциям значений. В столбце «Результат» приводится количество тестовых функций, на которых качество одного алгоритма статистически значимо отличается от другого (общее число тестовых функций - 16); значения для базового алгоритма и модификации приведены через косую черту.

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

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

Сравнение алгоритмов при решении задачи формирования кредитного портфеля банка. Проведем сравнение стандартного ВГА и его модификаций при решении задачи формирования кредитного портфеля банка (условия взяты из работы [5]). Данная задача относится к классу задач условной псевдобулевой оптимизации, т. е. оптимизации функций, отображающий булев гиперкуб на множество вещественных чисел. Размерность пространства поиска равна 50. Для учета ограничений использовался метод динамических штрафов [6]. Размер популяции был выбран равным 1 000, число итераций - 100, число запусков для усреднения - 100. Для каждого метода селекции производилась проверка равенства математических ожиданий доходности лучшего портфеля, найденного базовым алгоритмом и его модификациями. Для проверки значимости различия использовался критерий Стьюдента [4]. Размер выборок достаточно велик (100), поэтому можно использовать асимптотическое критическое значение статистики Стьюдента. Для уровня значимости 0,95 оно составляет примерно 1,97.

Таблица 1

Результаты тестирования

Вид селекции Базовый алгоритм Модификация Результат

Надежность Затраты Надежность Затраты

Пропорциональная 0,44 2 100 0,52 2 100 0/7

Ранговая 0,46 2 200 0,62 2 300 0/7

Турнирная 0,48 2 100 0,65 2 300 0/8

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

Проверка гипотезы о равенстве математических ожиданий по критерию Стьюдента показывает, что эффективность алгоритмов с асимптотической мутацией или асимптотической селекцией (ВГА -М или ВГА - С) отличается от базового алгоритма статистически незначимо (на уровне значимости 0,95). Кроме того, эффективность этих двух алгоритмов также различается статистически незначимо. Различие же между алгоритмом, использующим и асимптотическую мутацию, и асимптотическое скрещивание (ВГА-МС), и остальными зависит от типа селекции: при использовании пропорциональной и ранговой селекции эффективность ВГА-МС статистически значимо превосходит эффективность трех остальных алгоритмов, а в случае использования турнирной селекции статистически значимых различий нет.

В заключение проанализируем время выполнения различных вариантов ВГА. Данные табл. 2 показывают, что во всех случаях базовый ВГА уступает его асимптотическим модификациям. Более того, алгоритм, использующий и асимптотическую мутацию, и асимптотическую селекцию, при использовании пропорциональной и ранговой селекции превосходит алгоритмы, у которых только один из этих этапов является асимптотическим. При использовании турнирной селекции самым быстрым является ВГА с асимптотической мутацией и обычной селекцией. Этот факт может быть объяснен следую-

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

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

Библиографический список

1. Семенкин, Е. С. Вероятностные эволюционные алгоритмы оптимизации сложных систем / Е. С. Семенкин, Е. А. Сопов // Тр. Междунар. науч.-техн. конф. «Интеллектуальные системы» (AIS’05) и «Интеллектуальные САПР» (CAD-2005). В 3 т. Т. 1. М. : Физматлит, 2005.

2. Компиляторы: принципы, технологии и инструментарий : пер. с англ. / А. В. Ахо, М. С. Лам, Р. Сети, Д. Д. Ульман. 2-е изд. М. : Вильямс, 2008.

3. Кнут, Д. Э. Искусство программирования. В 2 т. Т. 2. Получисленные методы : пер. с англ. / Д. Э. Кнут. 3-е изд. М. : Вильямс, 2007.

4. Айвазян, С. А. Прикладная статистика: Основы моделирования и первичная обработка данных : справ. изд. / С. А. Айвазян, И. С. Енюков, Л. Д. Мешалкин. М. : Финансы и статистика, 1983.

5. Пуртиков, В. А. Оптимизация управления формированием кредитного портфеля банка : дис. ... канд. техн. наук / В. А. Пуртиков. Красноярск, 2001.

6. Michalewicz, Z. Evolutionary Algorithms for Constrained Parameter Optimization Problems / Z. Michalewicz, M. Schoenauer. Evolutionary Computation. 1996. №> 4 (1). Р 1-32.

Таблица 2

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

Метод селекции Алгоритм Среднее Среднеквадратичное отклонение Время, с

Пропорциональная ВГА 199 581 б2,74 1,32

ВГА - М 199 579 57,41 1,28

ВГА - С 199 585 75,34 1,09

ВГА - МС 199 б05 59,98 0,94

Ранговая ВГА 199 б31 38,35 1,71

ВГА - М 199 б31 37,84 1,59

ВГА - С 199 б33 40,45 1,48

ВГА - МС 199 б4б 38,39 1,27

Турнирная ВГА 199 б34 48,91 1,37

ВГА - М 199 б34 48,79 1,11

ВГА - С 199 б35 38,43 1,34

ВГА - МС 199 б39 4б,09 1,24

P. V Galushin, E. S. Semenkin ASYMPTOTIC PROBABILISTIC GENETIC ALGORITHM

This paper proposes the modification of probabilistic genetic algorithm, which uses genetic operators, influencing not particular solutions, but the probabilities distribution of solution vector components. This paper also compares reliability and efficiency of the basic algorithm and proposed modification using the set of test functions and the bank credit portfolio formation problem.

Keywords: probabilistic genetic algorithm, mutation, selection.

© ranywuH n. B., CeMeHKUH E. C., 2009

УДК621.317.799

В. М. Владимиров, Э. Ф. Гринин, М. Е. Сергий, В. Н. Шепов

АВТОМАТИЗИРОВАННЫЙ ИЗМЕРИТЕЛЬ УДЕЛЬНОГО ЭЛЕКТРОСОПРОТИВЛЕНИЯ МОНОКРИСТАЛЛИЧЕСКОГО КРЕМНИЯ ЧЕТЫРЕХЗОНДОВЫМ МЕТОДОМ*

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

Ключевые слова: автоматизированный измеритель, монокристаллический кремний, удельное электросопротивление, четырехзондовый метод.

Современный уровень производства и анализа качества монокристаллического кремния требует разработки измерителей удельного электросопротивления (УЭС) нового поколения, позволяющих проводить измерения УЭС в автоматическом режиме, с высокой скоростью и точностью. Из всех методов измерения УЭС монокрис-таллического кремния только четырехзондовый метод признан Международной организацией по полупроводниковому оборудованию и материалам (Semiconductor Equipment & Materials International, SEMI) в качестве арбитражного. Данный метод рекомендован и российским ГОСТ 19658-81 [1].

На основе требований к оборудованию и методикам измерения и расчета УЭС системы международных стандартов SEMI** авторами разработан прибор «Рометр», предназначенный для автоматизированного измерения УЭС пластин и слитков монокристаллического кремния четырехзондовым методом.

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

тырехзондовой головки; двух микроконтроллеров (один

- для управления работой измерительной схемы, второй

- для управления перемещением четырехзондовой головки и столика с образцом); аналого-цифрового преобразователя (АЦП); аналоговых эквивалентов; измерительного усилителя; датчика температуры; схемы управления двигателями (СУД); датчика углового перемещения столика; датчика рабочего положения четырехзондовой головки.

В приборе применена четырехзондовая головка фирмы Jandel Engineering Ltd с межзондовым расстоянием 1,59 мм, которая обеспечивает подачу на измеряемый образец постоянного тока заданной величины по внешним зондам и измерение возникающей разности потенциалов на внутренних зондах, к которым подключен измерительный усилитель. С выхода усилителя аналоговый сигнал подается на вход 18 -разрядного АЦП MAX 132 и преобразуется в цифровой код, далее он поступает на вход первого микроконтроллера ATMEGA8, управляющего работой измерительной схемы, и затем на персональный компьютер. Источник стабилизированного питания измерительной схемы обеспечивает стабильные постоянные напряжения+15 и -15 В для работы измерительного усилителя, источника тока, АЦП и +5 В для пер-

* Работа выполнена при финансовой поддержке программы Сибирского отделения Российской академии наук «Импортозаме-щение».

** SEMI MF84. Standard Test Methods for Measuring Resistivity of Silicon Wafers With an In-Line Four-Point Probe; SEMI MF81. Standard Test Methods for Measuring Radial Resistivity Variation on Silicon Slices; SEMI MF1527. Standard Guide for Application of Silicon Standard Reference Materials and Reference Wafers for Calibration and Control of Instruments for Measuring Resistivity of Silicon.