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

Аннотация

В.В. Бегляров, А.Н. Берёза

Дата поступления статьи: 12.02.2013

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

Ключевые слова: Генетические операторы; эволюционный алгоритм; система линейных алгебраических уравнений; системы автоматизированного проектирования.

05.13.18 - Математическое моделирование, численные методы и комплексы программ

Введение
В развитии современной экономики немаловажную роль играетсоздание конкурентоспособной высокотехнологичной радиоэлектронной аппаратуры. В этой ситуации первостепенное значение приобретают современные системы автоматизации проектирования (САПР), которые являются быстроразвивающимся наукоемким направлением прикладных исследований.
В связи с переходом на нанометровый уровень проектирования возросла актуальность точного схемотехнического (SPICE-подобного) моделирования для электронных схем больших размерностей [1,2]. Также возникла необходимость разработки нового поколения САПР СБИС, поддерживающегоновые методологии, новые библиотеки, включающего новые методы и алгоритмы моделирования.
Одной из острейших проблем остается проблема решения плохо обусловленныхсистем линейных алгебраических уравнений (СЛАУ) большой размерности, возникающих в процессе схемотехнического моделирования. Данная проблема особенно обострилась в связи с увеличением степени интеграции схем и, как следствие, необходимостью учитывать в процессе моделирования влияниепаразитных компонентов на работу схемы [1-3].
Данной проблемепосвящено множество как зарубежных, так и отечественных публикаций. Среди них можно выделить труды Русакова, С.Г., Норенкова, И.П., Анисимова, В.И., Дмитриевича, Г.Д., Петренко, А.И., Сигорского, В.П., Перминова, В.Н., Денисенко, В.В., Kuh, E.S., Sangiovanni-Vincentelli, A.L., Kuehlmann, A., Nelson, V.P., Kundert, K.S. и т.д. Несмотря на множество работ, связанных с данной тематикой, в настоящее время практически не существует эффективных методов решения плохо обусловленных СЛАУ большой размерности[4-6].

Гибридный эволюционный алгоритм решения СЛАУ (PEA)
  Увеличение предельного размера проектируемых СБИС привело к резкому увеличению времени работы и/или снижению точности подсистем схемотехнического моделирования.
Резервы повышения точности связаны, в основном, с точностью компонентных моделей элементов СБИС, а также с разработкой более совершенного математического аппарата.
На этапе схемотехнического проектирования СБИС проверяется работоспособность будущей СБИС с добавленной паразитной нагрузкой на межсоединениях. Для определения паразитных параметров схемы используются процедуры экстракции.Полученная после этапа экстракции схема является схемой второго порядка и в общем виде описывается системой дифференциальных уравнений:

,   (1)
где х - вектор переменных состояния (в качестве которых могут быть выбраны напряжения и/или токи ветвей,напряжения и/или токи реактивных элементов, контурные токи или узловые потенциалы) размерности N;
F–вектор правых частей системы дифференциальных уравнений по времени;
t –время;
x₀–вектор начальных значений переменных состояния.
Так как в общем виде систему дифференциальных уравнений математической модели можно решать неявными методами, которые требуют решения систем нелинейных и линейных уравнений, то для повышения эффективности схемотехнического проектирования достаточно увеличить эффективность решения СЛАУ и систем нелинейных уравнений большой размерности [7,8].
На рис. 1 представлена классификация основных методов решения СЛАУ, используемых в САПР ЭВТ [1,2].Традиционные методы решения СЛАУ не всегда способны эффективно решать плохо обусловленные системы большой размерности, а также не способны преодолевать овражные участки ландшафтов уравнений системы. Следовательно, необходима разработка новых более эффективных методов решения уравнений математических моделей схемотехнических решений, для которых увеличение размерности системы не будет приводить к резкому росту погрешности вычислений.  Предлагается использовать модифицированный метод решения СЛАУ, сочетающий в себе проекционные методы (метод бисопряженных градиентов и обобщенных минимальных невязок) и  эволюционные методы и оптимизационные метод на основе принципа Парето.

Рис.1.–Классификация основных методов решения СЛАУ, используемых в САПР ЭВТ

Гибридизация проекционных методов решения СЛАУ и эволюционных методов[9-11]и оптимизационных методов на основе принципа Парето [12,13] позволяет увеличить скорость сходимости и преодолеть овражные участки ландшафтов уравнений системы.
Полученные на схемотехническом этапе СЛАУ, имеют следующий вид:
Ax = b.   (2)

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

• ––евклидова норма невязки,

• –евклидова норма вектора x,

•  -  значение эффективности, полученное по принципу Парето.

Суммарная погрешность i-ого блока  определяется по формуле:
,,  (4)
где P_i– это матрица, являющаяся частью матрицы А, состоящая из правых частей образующих блок уравнений;
v_i– это вектор, являющийся частью вектораb, состоящий из левых частей образующих блок уравнений;
m – число блоков, на которые была разбита исходная система.
Для  увеличения скорости расчета эффективности по принципу Парето (F) исходная система разбивается на блоки. Значения невязок полученных блоков используется для вычисления значения F. Увеличение скорости расчета достигается за счетуменьшения числа сравнений.
Оптимальное количество блоков было получено экспериментальным путем в процессе исследования гибридного эволюционного алгоритма и равно 40. Данное количество блоков обеспечивает незначительное увеличение погрешности при существенном снижении времени расчета значения целевой функции за счет сокращения количества сравнений для определения фронта Парето.
Разработанный алгоритм работает с набором решений, полученных на этапе инициализации популяции.
Для пояснения определения эффективности возможного решения по принципу Парето рассмотрим следующее неравенство, связывающее два вектора x¹ и x²:

.,

где f_i– значение погрешности i-ого блока уравнений.
Если, по крайней мере, одно из неравенств выполняется строго, тогда вектор x² является более эффективным, чем x¹. С другой стороны, если ни одно неравенство не выполняется строго, то в таких случаях оба вектора x¹ и x² представляют интерес.  Если для некоторого вектора не существует более предпочтительных решений, то такое решение называют Парето-оптимальным или эффективным. Этот набор решений представляет фронтПарето(границу Парето) в пространстве решений [9].
Для определения значения эффективности Fдля текущего вектора хвоспользуемся следующей формулой:

,

где G–множество более эффективных векторов x; g – вектор, являющийсячленом множества G; S–количество менее эффективных векторов g.
Разработанный алгоритм решения СЛАУ описывается следующей последовательностью действий:
Шаг1. Ввод параметров работы алгоритма, определение счетчика поколений k=0, используемого для определения момента применения редукции популяции и критерия выбора генетических операторов.
Шаг 2. Инициализация начальной популяции. Определение начальной приспособленности популяции и упорядочение.
Шаг 4. Определение общего счетчика поколений i=0.
Шаг 5. Если k меньше параметра случайной вероятности определения генетических операторов, то переходим к шагу 6, иначе к шагу 8.
Шаг6. Определение кандидатов для применениягенетических операторов с помощью турнирной селекции.
Шаг 7. Случайный выбор генетических операторов и их применение. Переход к шагу 10.
Шаг 8. Определение кандидатов для применения генетических операторов с помощью турнирной селекции.
Шаг 9. Выбор генетических операторов на основе анализа эффективности и их выполнение.
Шаг 10.Добавляем потомков в популяцию потомков, приспособленность которых лучше средней приспособленности по популяции.
Шаг 11. Если потомки были добавлены в популяцию, то переходим к шагу 12, иначе к шагу 13.
Шаг 12.Определение приспособленности популяции, расстояний между хромосомами и упорядочение.
Шаг 13. Если k равно параметру редукции, то переходим к шагу 14, иначе к шагу 17.
Шаг 14. Уменьшение скученности популяции, т.е. концентрации большого количества особей вокруг одной хромосомы.
Шаг 15. k=0.
Шаг 16.Определение приспособленности популяции, расстояний между хромосомами и упорядочение.
Шаг 17. Формирование новой популяции с помощью элитной селекции. Определение лучшей, средней и худшей хромосомы.
Шаг 18. Если улучшение лучшей хромосомы произошло, то переходим к шагу19, иначе к шагу 21.
Шаг 19. Если значения параметров мутации обобщенных минимальных невязок и бисопряженных градиентов равны установленным перед началом работы алгоритма, то переходим к шагу 23, иначе к шагу 20.
Шаг 20. Уменьшение на 1 значений параметров мутации обобщенных минимальных невязок и бисопряженных градиентов (данные параметры отражают количество итераций и размер внешнего цикла для метода бисопряженных градиентов и метода обобщенных минимальных невязок соответственно). Переходим к шагу 23.
Шаг 21. Если предел застоя достигнут, т.е. в течение определенного количества поколений не происходило улучшение лучшей хромосомы, то переходим к шагу 22, иначе к шагу 23.
Шаг 22.Увеличение значений параметров для мутации обобщенных минимальных невязок и бисопряженных градиентов на 1.
Шаг 23. Если размерность популяции меньше 1/3 от исходной, то приводим популяцию к исходному размеру.
Шаг 24. Если приспособленность лучшей хромосомы меньше установленной, т.е. найдено решение с заданной погрешностью, то переходим к шагу 26, иначе к шагу 25.
Шаг 25. Если i меньше количества поколений, то i=i+1и k=k+1переходим к шагу 5, иначе к шагу 2.
Шаг 26. Вывод результата.
Экспериментальные исследования
Программная реализация разработанного алгоритма была выполнена в виде универсального подключаемого модуля на языке C#.
Экспериментальные исследования проводились для алгоритма PEA, алгоритмов на основе метода Гаусса-Зейделя, методов крыловского типа GMRES(метод обобщенных минимальных невязок) и BCG (метод бисопряженных градиентов), метода Нелдера-Мида и Хука-Дживса.Экспериментальное исследование подтвердило неэффективность использования итерационного алгоритма Гаусса-Зейделя и алгоритмов Нелдера-Мида и Хука-Дживса для решения плохо обусловленных СЛАУ большой размерности с сильно разреженной матрицей.Данные алгоритмы оказались не способны преодолеть овражные участкиландшафта поверхности, образованной в области определения искомых неизвестных в СЛАУ, средняя погрешность на наборе тестовых схем составила 0.01. Эффективность проекционных методов на основе подпространств Крылова сильно падает при увеличении размерности СЛАУ. В результате примененияразработанного алгоритмадля решения СЛАУ не происходит сильного увеличения погрешностивычисленияпри увеличении размера системы уравнений, так эволюционный подход позволяет вывести итерационный процесс из локальных оптимумов. Низкая погрешность решения в разработанном гибридном алгоритме обеспечивается использованием методов крыловского типа GMRES и BCG, а также механизма корректировки параметров работы алгоритмов на основе данных методов в зависимости от скорости сходимости процесса решения.
На рисунках 2 и 3 представлены сводные диаграммы времени выполнения и точности решения соответственно.

Рис.2. - Сводная диаграмма времени выполнения по всем экспериментальным исследованиям

Рис.3. - Сводная диаграмма по точности вычислений по всем экспериментальным исследованиям

Заключение
Эффективность разработанного алгоритма решения систем линейных алгебраических уравнений обеспечивается гибридизацией эволюционных методов и традиционных методов решения систем уравнений. Преимущества эволюционных методов позволяют повысить эффективность решения уравнений математических моделей СБИС, снижая вероятность попадания итерационного процесса в локальные оптимумы. Данный алгоритм является самоадаптирующимся, что также повышает его эффективность. В результате экспериментальных исследований была подтверждена теоретическая оценка сложности, равная O(N2), что является хорошим показателем. Анализ экспериментальных исследований показал эффективность гибридного эволюционного алгоритма решения СЛАУ. По сравнению с другими представленными алгоритмами, разработанный алгоритм не испытывает проблем с потерей точности при увеличении размерности, при этом обладает квадратичной временной сложностью, что также является достоинством данного алгоритма. Предложенный алгоритм увеличивает эффективность решения СЛАУ, полученных на этапе схемотехнического проектирования, за счет увеличения точности более чем в 10000 раз при незначительном увеличении времени выполнения (менее 1.5 раз для СЛАУ размером 900х900). Следовательно, использование предлагаемого алгоритма способно повысить точность схемотехнических САПР и эффективность их применения.

Работа выполнена при поддержке РФФИ (проект № 13-07-00951).

Литература

• 1. Казеннов Г.Г. Основы проектирования интегральных схем и систем [Текст] / Г.Г.Казеннов. – М.: БИНОМ. Лаборатория знаний. 2005 -295с.
  2. Гридин В.Н. Численно –аналитическое моделирование радиоэлектронных схем. [Текст] / В.Н. Гридин. – М.: Наука, 2008 – 339с.
  3. Актуальные проблемы моделирования в системах автоматизации схемотехнического проектирования. [Текст] / А.Л. Глебов и др. – М.: Наука, 2003 -430с.
  4. Y. Saad. Iterative Methods for Sparse Linear Systems, 2nd Edition. SIAM,Philadelphia, 2003, 567.
  5. J. Lampe, L. Reichel, and H. Voss Large-scale Tikhonov regularization via reduction by orthogonal projection Linear Algebra Appl., 436 (2012), pp. 2845-2865. 
  6. C. Jagels and L. Reichel Recursion relations for the extended Krylov subspace method Linear Algebra Appl., 434 (2011), pp. 1716-1732
  7. Бахвалов, Н.С., Жидков, Н.П., Кобельков, Г.М. Численные методы [Текст]/ Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков. – М: Бином, 2008. – 636с.
  8. Баландин М.Ю., Шурина Э.П. Методы решения СЛАУ большой размерности. [Текст] / М.Ю. Баландин, Э.П. Шурина. – Новосибирск: Изд-во НГТУ. 2000 – 70с.
  9. Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы. [Текст] / Л. А. Гладков, В. В.Курейчик, В. М. Курейчик. - Физико-математическая литература. 2006 – 339с.
  10. Панченко Т.В. Генетические алгоритмы. [Текст] / Т.В. Панченко. – Астрахань: Издательский дом «Астраханский университет», 2007 -88с.
  11. Свечкарев В.П., Интеграция имитационных моделей при проведении исследований в гуманитарной сфере. // Электронный научный журнал «Инженерный вестник Дона» - 2010 - № 3.
  12. Аттеков А.В. Методы оптимизации /А.В. Аттеков, С.В. Галкин, В.С. Зарубин – М.:изд-во МГТУ им. Н.Э. Баумана,2003-440ст.
  13. Антонова А.С., Аксенов К.А. Многокритериальное принятие решений в условиях риска на основе интеграции мультиагентного, имитационного, эволюционного моделирования и численных методов. // Электронный научный журнал «Инженерный вестник Дона» - 2012 - № 4 (часть 2).