Эффективное увеличение области притяжения глобального минимума квадратичного бинарного функционала при нейросетевом поиске

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2009
Hauptverfasser:	Карандашев, Я.М., Крыжановский, Б.В.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут проблем штучного інтелекту МОН України та НАН України 2009
Schlagworte:	Интеллектуальный анализ данных
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/8145
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Эффективное увеличение области притяжения глобального минимума квадратичного бинарного функционала при нейросетевом поиске / Я.М. Карандашев, Б.В. Крыжановский // Штучний інтелект. — 2009. — № 4. — С. 37-44. — Бібліогр.: 3 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-8145
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-81452025-02-23T19:44:45Z Эффективное увеличение области притяжения глобального минимума квадратичного бинарного функционала при нейросетевом поиске Ефективне збільшення області притягнення глобального мінімуму квадратичного бінарного функціонала при нейромережному пошуку A Drastic Increase in the Basin of Attraction of the Global Minimum of Quadratic Binary Functional on Application of the Neural Network Search Карандашев, Я.М. Крыжановский, Б.В. Интеллектуальный анализ данных Решается задача минимизации квадратичного функционала в конфигурационном пространстве. Для эффективного увеличения области притяжения глубоких минимумов предлагается матрицу, на которой построен функционал, возводить в степень, и на полученном новом функционале решать задачу минимизации. В работе показано на примере матриц двумерной спинстекольной модели Изинга, что такая техника приводит к сдвигу спектра минимумов в более глубокую область, резко сокращает число находимых мелких минимумов и позволяет с большей, на 3 – 4 порядка, вероятностью находить глобальный минимум. Розв’язується задача мінімізації квадратичного функціонала у конфігураційному просторі. Для ефективного збільшення області притягнення глибоких мінімумів пропонується матрицю, на якій побудований функціонал, підносити до степеня, а на отриманому новому функціоналі розв’язувати задачу мінімізації. У роботі показано на прикладі матриць двомірної спінстекольної моделі Ізінга, що така техніка приводить до зрушення спектра мінімумів у більш глибоку область, різко зменшує число знайдених мілких мінімумів і дозволяє з більшою, на 3 – 4 порядки, вірогідністю знаходити глобальний мінімум. A quadratic binary functional minimization problem is considered. To effectively increase the deep minima domains of attraction it is suggested to raise a matrix which constructed the functional on to some power, and to solve the minimization problem on the new obtained functional. By the example of matrixes of the twodimensional Ising’s model it is shown in the paper that suggested technique leads to a shift of local minima spectrum towards the region of deeper minima, reduces sharply the number of minima found, and gives an opportunity to find the global minimum with a probability on 3 – 4 orders greater. Выполнена в рамках Гранта Президента Российской Федерации по государственной поддержке ведущих научных школ, номер гранта НШ – 365.2008.9 2009 Article Эффективное увеличение области притяжения глобального минимума квадратичного бинарного функционала при нейросетевом поиске / Я.М. Карандашев, Б.В. Крыжановский // Штучний інтелект. — 2009. — № 4. — С. 37-44. — Бібліогр.: 3 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/8145 004.8:004.9 ru application/pdf Інститут проблем штучного інтелекту МОН України та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Интеллектуальный анализ данных Интеллектуальный анализ данных
spellingShingle	Интеллектуальный анализ данных Интеллектуальный анализ данных Карандашев, Я.М. Крыжановский, Б.В. Эффективное увеличение области притяжения глобального минимума квадратичного бинарного функционала при нейросетевом поиске
description	Решается задача минимизации квадратичного функционала в конфигурационном пространстве. Для эффективного увеличения области притяжения глубоких минимумов предлагается матрицу, на которой построен функционал, возводить в степень, и на полученном новом функционале решать задачу минимизации. В работе показано на примере матриц двумерной спинстекольной модели Изинга, что такая техника приводит к сдвигу спектра минимумов в более глубокую область, резко сокращает число находимых мелких минимумов и позволяет с большей, на 3 – 4 порядка, вероятностью находить глобальный минимум.
format	Article
author	Карандашев, Я.М. Крыжановский, Б.В.
author_facet	Карандашев, Я.М. Крыжановский, Б.В.
author_sort	Карандашев, Я.М.
title	Эффективное увеличение области притяжения глобального минимума квадратичного бинарного функционала при нейросетевом поиске
title_short	Эффективное увеличение области притяжения глобального минимума квадратичного бинарного функционала при нейросетевом поиске
title_full	Эффективное увеличение области притяжения глобального минимума квадратичного бинарного функционала при нейросетевом поиске
title_fullStr	Эффективное увеличение области притяжения глобального минимума квадратичного бинарного функционала при нейросетевом поиске
title_full_unstemmed	Эффективное увеличение области притяжения глобального минимума квадратичного бинарного функционала при нейросетевом поиске
title_sort	эффективное увеличение области притяжения глобального минимума квадратичного бинарного функционала при нейросетевом поиске
publisher	Інститут проблем штучного інтелекту МОН України та НАН України
publishDate	2009
topic_facet	Интеллектуальный анализ данных
url	https://nasplib.isofts.kiev.ua/handle/123456789/8145
citation_txt	Эффективное увеличение области притяжения глобального минимума квадратичного бинарного функционала при нейросетевом поиске / Я.М. Карандашев, Б.В. Крыжановский // Штучний інтелект. — 2009. — № 4. — С. 37-44. — Бібліогр.: 3 назв. — рос.
work_keys_str_mv	AT karandaševâm éffektivnoeuveličenieoblastipritâženiâglobalʹnogominimumakvadratičnogobinarnogofunkcionalaprinejrosetevompoiske AT kryžanovskijbv éffektivnoeuveličenieoblastipritâženiâglobalʹnogominimumakvadratičnogobinarnogofunkcionalaprinejrosetevompoiske AT karandaševâm efektivnezbílʹšennâoblastípritâgnennâglobalʹnogomínímumukvadratičnogobínarnogofunkcíonalaprinejromerežnomupošuku AT kryžanovskijbv efektivnezbílʹšennâoblastípritâgnennâglobalʹnogomínímumukvadratičnogobínarnogofunkcíonalaprinejromerežnomupošuku AT karandaševâm adrasticincreaseinthebasinofattractionoftheglobalminimumofquadraticbinaryfunctionalonapplicationoftheneuralnetworksearch AT kryžanovskijbv adrasticincreaseinthebasinofattractionoftheglobalminimumofquadraticbinaryfunctionalonapplicationoftheneuralnetworksearch
first_indexed	2025-11-24T18:04:58Z
last_indexed	2025-11-24T18:04:58Z
_version_	1849695926798516224
fulltext	«Штучний інтелект» 4’2009 37 2К УДК 004.8:004.9 Я.М. Карандашев, Б.В. Крыжановский Центр оптико-нейронных технологий НИИСИ РАН, г. Москва, Россия iont.niisi@gmail.com Эффективное увеличение области притяжения глобального минимума квадратичного бинарного функционала при нейросетевом поиске* Решается задача минимизации квадратичного функционала в конфигурационном пространстве. Для эффективного увеличения области притяжения глубоких минимумов предлагается матрицу, на которой построен функционал, возводить в степень, и на полученном новом функционале решать задачу минимизации. В работе показано на примере матриц двумерной спинстекольной модели Изинга, что такая техника приводит к сдвигу спектра минимумов в более глубокую область, резко сокращает число находимых мелких минимумов и позволяет с большей, на 3 – 4 порядка, вероятностью находить глобальный минимум. Введение В данной работе мы рассматриваем задачу нахождения глобального минимума квадратичного функционала в конфигурационном пространстве. Пусть T – вещественная матрица размера NN  , симметричная и с нулевой диа- гональю. Квадратичный функционал, построенный на этой матрице, имеет вид: , 2 1 1 1    N i N j jiij ssTE 1, jis . (1) Задача состоит в том, чтобы найти такой конфигурационный вектор ,( 0 10 sS  ),...,, 00 2 Nss , который даёт глобальный минимум функционала. Данная задача является NP-полной. Её можно решить, воспользовавшись ней- росетевым спуском со случайных стартов. Пусть у нас есть некоторая начальная (во- обще говоря, случайная) конфигурация спинов )....,,,( 21 NsssS  Найдём локальное поле, действующее на каждый её спин: /1    ij jijii sTsEh . (2) Последовательно разворачивая спины так, чтобы они совпадали по знаку с дейст- вующим на них локальным полем, энергия конфигурации будет понижаться до тех пор, пока мы не застрянем в одном из локальных минимумов, где все спины будут направлены вдоль действующего на них локального поля. Чтобы найти глобальный минимум, данный спуск придётся провести многократно с различных стартовых кон- фигураций. На самом деле нейросетевой спуск является аналогом покоординатного спуска в вещественном пространстве. * Выполнена в рамках Гранта Президента Российской Федерации по государственной поддержке ведущих научных школ, номер гранта НШ – 365.2008.9 Карандашев Я.М., Крыжановский Б.В. «Искусственный интеллект» 4’2009 38 2К Исходные данные В нашей работе мы будем иметь дело лишь с функционалами, построенными на матрицах спинового стекла двумерной модели Изинга. Модель Изинга – это мо- дель взаимодействия спинов, находящихся в узлах решётки и взаимодействующих только с ближайшими соседями. Рассматриваемая размерность задачи N = 100. Данный тип матриц выбран по нескольким причинам: Во-первых, для них описанный выше обычный случайный нейросетевой поиск находит глобальный минимум менее чем один раз за миллион стартов. При этом на- ходится порядка 990 тысяч других (более мелких) минимумов. Хотелось бы найти лучший способ поиска. Во-вторых, для рассматриваемых матриц Изинга каждой конфигурации S соответствует ортогональная ей конфигурация S  ( 0SS ) с противоположной по знаку энергией )()( 11 SESE  . Этот факт окажется полезным в дальнейшем. И, наконец, в-третьих, в работе [1] показано, как с помощью branch and cut ме- тода можно найти глобальный минимум функционала на рассматриваемых матрицах небольших размерностей, используя их сильную разреженность. Значит, в руках у нас уже есть конфигурации глобальных минимумов, что помогает нам при оценке резуль- тативности наших методов. Предлагаемый алгоритм Как показано в работе [2], в обобщённой модели Хопфилда при нейросетевом поиске вероятность попадания в минимум тем больше, чем больше глубина минимума. В связи с этим наша базовая идея состоит в том, чтобы видоизменить энергетическую поверхность функционала (1) таким образом, чтобы его глубокие минимумы (которые мы ищем) стали ещё глубже, а значит, находились бы с большей вероятностью, при этом мелкие минимумы (которые для нас не представляют интереса) стали мельче или совсем исчезли из виду. Покажем, как возведение исходной матрицы в квадрат реализует эту идею. Для этого представим нашу симметричную матрицу в виде взвешенного квазихеббовского разложения по внешним произведениям конфигурационных векторов: , 1    M m mmm SSrT (3) где mS – некоторые конфигурации, mr – веса этих конфигураций, а M – число, достаточ- ное для разложения. В работе [3] показано, что в качестве конфигураций в разложении (3) можно взять конфигурации экстремумов (в том числе глобальных максимумов и минимумов). В этом случае соответствующие им веса с точностью до некоторых флук- туаций будут пропорциональны энергиям этих экстремумов. С учётом выражения (3) квадрат матрицы T примет вид: ,2 RAT  (4) где   M m mmm SSrNA 2 ,     M m N n nmnmnmmn SSSSrrR 1 1 ),()1(  . (5) Эффективное увеличение области притяжения глобального минимума... «Штучний інтелект» 4’2009 39 2К Первое из слагаемых (матрица A ) с точностью до множителя N (который уйдёт при соответствующей нормировке) совпадает с исходным разложением матрицы (3), при этом веса соответствующих конфигураций оказались возведёнными в квадрат. Именно матрица A даёт нам функционал с нужным образом видоизменённой энер- гетической поверхностью. Действительно, большие веса при возведении в квадрат станут ещё больше и, следовательно, увеличится глубина соответствующих мини- мумов и вероятность их нахождения. Малые веса при возведении в квадрат станут еще меньше, и мелкие минимумы уйдут из рассмотрения. Нельзя забывать и о втором (перекрёстном) члене .R Если бы конфигурации в разложении (3) были ортогональными, то мы бы имели ,0R и новый функционал, построенный на квадрате матрицы: ,)( 2 1 1 1 2 2      N i N ij j jiij ssTE (6) имел бы конфигурации локальных минимумов, совпадающие с конфигурациями ис- ходного функционала. Однако в общем случае это неверно. Среднее значение элемен- тов матрицы R равно нулю, а их стандарт порядка N/1 . Это означает, что вклад матрицы R в 2E относительно невелик. Однако его наличие приводит к тому, что кон- фигурации локальных минимумов функционала 2E слегка сдвигаются относительно конфигураций mS исходного функционала 1E . Полученные результаты На рис. 1 приведены усреднённые по 50 матрицам графики спектральной плот- ности минимумов функционалов 1E и 2E . Во всех экспериментах мы нормировали каждую матрицу (как исходную T , так и матрицу-квадрат TTT 2 ) на дисперсию её элементов. Как видно из рис. 1, спектр функционала 2E сдвинут влево по сравне- нию со спектром исходного функционала 1E . Также на рис. 1 показано, куда сдви- нулся глобальный минимум исходного функционала. Он стал заметно глубже. Число обнаруженных за миллион стартов минимумов функционала 2E порядка 600 тысяч, что существенно меньше, чем для исходного (около 990 тысяч). Это показывает, что мы добились желаемого: глубокие минимумы стали глубже, а многие мелкие исчезли. Рисунок 1 – График спектральной плотности минимумов функционала для матрицы Изинга (Т) и квадрата этой матрицы (Т*Т). Квадратами показано изменение энергии конфигурации глобального минимума матрицы Т ( )P E E T T T Карандашев Я.М., Крыжановский Б.В. «Искусственный интеллект» 4’2009 40 2К E ( )W E 1E 2E В случаях, если конфигурация глобального минимума исходного функционала не являлась локальным минимумом функционала 2E , мы брали энергию минимума, бли- жайшего к глобальному по расстоянию (число несовпадающих спинов). Число отли- чающихся спинов расположилось в диапазоне от 0 до 6, и в среднем по 50 матрицам оказалось равным 3,4, что подтверждает малость члена R в разложении (4). Другим интересным подтверждением того, что при возведении матрицы в квад- рат веса конфигураций тоже возводятся в квадрат, является следующее. Как упоминалось выше, спектр матрицы Изинга обладает тем свойством, что произвольному локально- му минимуму функционала, построенного на этой матрице, соответствует некоторый локальный максимум этого функционала с противоположной по знаку энергией и с ортогональной конфигурацией. Заметим, что если в разложении (3) исходной матри- цы минимумам соответствовали положительные веса, а максимумам – отрицательные, то возведённые в квадрат эти веса все окажутся положительными, и значит, все они будут соответствовать минимумам нового функционала, или, в силу искажающего чле- на R , будут иметь отрицательную энергию. Эксперимент показал, что, действительно, конфигурации как максимумов, так и минимумов исходного функционала дают на 2E отрицательную энергию. Более того, большинство обнаруженных глубоких мини- мумов функционала 2E дважды вырождены! Поскольку наша задача состоит в том, чтобы найти глубокие минимумы исход- ного функционала 1E , а минимумы функционала 2E нас, вообще говоря, не интере- суют, то мы прибегли к двойному спуску. На первом этапе двойного спуска, стартуя с некоторой случайной начальной конфигурации, мы спускаемся по поверхности функ- ционала .2E Дойдя до минимума, мы продолжаем спуск уже по поверхности 1E , получая в итоге минимум нашего исходного функционала. Как показывает рис. 2, двойной спуск даёт большую плотность вероятности по- падания в области глубоких минимумов. Как следствие этого, среднее значение энер- гии, получаемое при двойном спуске, равно – 0,894, что заметно ниже, чем среднее значение энергии при обычном спуске: – 0,841. Нормировка энергий такова, что гло- бальному минимуму соответствует значение энергии – 1,000. Рисунок 2 – Плотность вероятности отыскания минимума: E1 – при простом, E2 – двойном спусках. Энергия нормирована на глубину глобального минимума Также двойной спуск резко уменьшил число обнаруживаемых минимумов (на мил- лион стартов их порядка 150 тысяч). Эффективное увеличение области притяжения глобального минимума... «Штучний інтелект» 4’2009 41 2К ( )W D D 1E 2E ( )W E E 1E 2E ' 1E ' 2E График распределения вероятности по расстояниям от глобального минимума представлен на рис. 3. Двойной спуск по сравнению с обычным дал увеличение ве- роятности попадания в глобальный минимум примерно в 160 раз. Рисунок 3 – Распределение вероятности W(D) попадания на расстояние D от глоб. минимума при: E1 – простом спуске, E2 – двойном. Представлены лишь расстояния от 0 до 10 Часто поиск останавливался в локальных минимумах, конфигурации которых расположены на расстоянии 2 – 3 спинов от глобального. В связи с этим мы слегка изменили нейросетевой спуск. А именно, как только нейросетевая динамика останавли- валась на некотором минимуме, мы случайным образом выбирали 3 спина, перевора- чивали их и продолжали спуск. Для каждой стартовой конфигурации мы делали по 100 таких «отскоков», фиксируя при этом конфигурацию самого глубокого из достиг- нутых минимумов. На рис. 4, 5 приведены результаты для динамики с «отскоками» (для обычного и двойного спусков). Рисунок 4 – Распределение плотности вероятности W(E) по энергии: E1 – для простого, E2 – двойного спусков, E’1 – для простого спуска с отскоками, E’2 – для двойного спуска с отскоками При этом среднее значение энергии при простом спуске с отскоками равно – 0,932, а при двойном с отскоками – 0,948. Карандашев Я.М., Крыжановский Б.В. «Искусственный интеллект» 4’2009 42 2К ( )W D D 2E 1E ' 1E ' 2E ' 2 1 ( )W D W D 0 500 1000 1500 2000 -1.1 -1 -0.9 -0.8 -0.7 -0.6 ' 2 1 ( )W E W E Рисунок 5 – Распределение вероятности W(D) попадания по расстояниям D от глобального минимума: E1 – для простого, E2 – двойного спусков, E’1 – для простого спуска с отскоками, E’2 – для двойного спуска с отскоками Как оказалось, метод двойного спуска с отскоками оказался самым эффективным. На рис. 6 и 7 приведены сравнительные характеристики этого метода с простым спус- ком на исходном функционале. Рисунок 6 – Отношение плотностей вероятности попадания в заданный интервал энергий при двойном спуске с отскоками (W’2(E)) и при простом спуске (W1(E)) Отношение вероятности попадания в глобальный минимум при двойном спуске с отскоками к вероятности попадания в него при простом спуске без отскоков ~ 2400 (рис. 7), т.е. нам удалось увеличить данный показатель на три порядка! Рисунок 7 – Отношение вероятностей попадания на расстояние D от глобального минимума при двойном спуске с отскоками (W’2(D)) и при простом спуске (W1(D)) Эффективное увеличение области притяжения глобального минимума... «Штучний інтелект» 4’2009 43 2К Разумеется, можно было бы возводить матрицу не в квадрат, а в большую сте- пень. При этом возведение матрицы в нечётную степень приводит к тому, что веса в 1-м члене разложения (4) тоже оказываются возведёнными в нечётную степень, а зна- чит, сохраняют знак. Поэтому минимумы полученной матрицы будут минимумами исходной матрицы, и мы не будем тратить время на спуск с максимумов. То есть воз- ведение матрицы в нечётную степень более эффективно, чем в чётную. Представлен- ные в табл. 1 полученные результаты это хорошо подтверждают. Таблица 1 – Усреднённые по 50 матрицам результаты для двойных спусков с различных степеней матриц Обсуждение результатов Не имеет смысла возводить матрицу в степень до бесконечности, ожидая роста вероятности попадания в глубокие минимумы. Как видно из рис. 1, несмотря на то, что конфигурация глобального минимума функционала 1E имеет меньшую энергию на функционале 2E , функционал 2E имеет какие-то новые, ещё более глубокие, мини- мумы. При дальнейшем увеличении степени матрицы эти минимумы-химеры станут ещё глубже, а значит, и шире, пока полностью не затмят наш глобальный минимум. Видимо, это связано с перекрёстным членом R в разложении (4), который растёт с увеличением степени. Из табл. 1 видно, что результаты для пятой степени матрицы мало отличаются от результатов для 3-й степени. Следует также отметить, что при возведении матрицы в степень возникают си- туации, когда глобальный минимум вообще не находится. А именно, при обычном (без отскоков) двойном спуске с куба матрицы из 50 рассматриваемых матриц для 15 мы вообще не находили глобальный минимум. Для пятой степени число матриц с ненай- денным глобальным минимумом равно 34 из 50! Ситуация для двойных спусков с отскоками несколько лучше. Однако даже в этой ситуации вероятность попадания в Обычные спуски Двойной спуск с матрицей kT Вероятность попадания: Простой спуск (Т) Т2 Т3 Т4 Т5 в глоб. минимум 0,00024% 0,038% 0,2% 0,12% 0,4% в интервал [– 0.99, – 1.00] 0,0022% 0,23% 1,1% 0,56% 2,5% Среднее значение энергии – 0,841 – 0,894 – 0,936 – 0,899 – 0,951 Спуски с «отскоками» Двойной спуск с матрицей kT Вероятность попадания: Простой спуск (Т) Т2 Т3 Т4 Т5 в глоб. минимум 0,04% 0,67% 3,7% 1,44% 3,2% в интервал [– 0.99, –1.00] 0,3% 3,7% 14% 5,8% 14,1% Среднее значение энергии – 0,932 – 0,948 – 0,975 – 0,950 – 0,974 Карандашев Я.М., Крыжановский Б.В. «Искусственный интеллект» 4’2009 44 2К узкий интервал энергий, очень близких к глобальному минимуму (от – 0,99 до – 1,00), в результате замены алгоритма случайного поиска возрастала с 0,0028% до 14,1%, т.е. более чем в 5000 раз (табл. 1). Одновременно среднее значение энергии случайно найденного минимума понизилось с величины – 0,841 до – 0,974, т.е. среднее расстоя- ние до глобального минимума сократилось в 6 раз. Более того, следует отметить, что даже в тех случаях, когда глобальный минимум не достигался, двойной спуск с большой вероятностью приводил систему в конфигу- рацию, очень близкую к глобальному минимуму: на расстоянии 2 – 5 бит от глобаль- ного минимума. Поэтому «отрицательный» результат является следствием того, что мы использовали «отскок» на три бита – наиболее простой приём выхода из мелких локальных минимумов. Однако мы не ставили перед собой цели оптимизировать вы- ход из локального минимума – это будет сделано в дальнейшем. Нашей целью было продемонстрировать только возможность деформации потенциальной поверхности, которая приводит к существенному увеличению вероятности глобального минимума. Эта цель нами достигнута. Литература 1. Hartmann A.K. New Optimization Algorithms in Physics / A.K. Hartmann, H. Rieger // WILEY-WCH Verlag GmbH & Co. KGaA. – Weinheim, 2004. – Р. 47-71. 2. Крыжановский Б.В. Взаимосвязь глубины локального минимума и вероятности его обнаружения в обобщённой модели Хопфилда / Б.В. Крыжановский, Б.М. Магомедов, А.Л. Микаэлян // ДАН. – 2005. – Т. 405, № 3. – С. 1-5. 3. Kryzhanovsky B.V. Expansion of a matrix in terms of external products of configuration vectors / B.V. Kry- zhanovsky // Optical Memory & Neural Networks (Information Optics). – 2007. – V. 16(4). – Р. 187-199. Я.М. Карандашев, Б.В. Крижановський Ефективне збільшення області притягнення глобального мінімуму квадратичного бінарного функціонала при нейромережному пошуку Розв’язується задача мінімізації квадратичного функціонала у конфігураційному просторі. Для ефективного збільшення області притягнення глибоких мінімумів пропонується матрицю, на якій побудований функціонал, підносити до степеня, а на отриманому новому функціоналі розв’язувати задачу мінімізації. У роботі показано на прикладі матриць двомірної спінстекольної моделі Ізінга, що така техніка приводить до зрушення спектра мінімумів у більш глибоку область, різко зменшує число знайдених мілких мінімумів і дозволяє з більшою, на 3 – 4 порядки, вірогідністю знаходити глобальний мінімум. J.M. Karandashev, B.V. Kryzhanovsky A Drastic Increase in the Basin of Attraction of the Global Minimum of Quadratic Binary Functional on Application of the Neural Network Search A quadratic binary functional minimization problem is considered. To effectively increase the deep minima domains of attraction it is suggested to raise a matrix which constructed the functional on to some power, and to solve the minimization problem on the new obtained functional. By the example of matrixes of the two- dimensional Ising’s model it is shown in the paper that suggested technique leads to a shift of local minima spectrum towards the region of deeper minima, reduces sharply the number of minima found, and gives an opportunity to find the global minimum with a probability on 3 – 4 orders greater. Статья поступила в редакцию 09.06.2009.

Эффективное увеличение области притяжения глобального минимума квадратичного бинарного функционала при нейросетевом поиске

Institution

Ähnliche Einträge