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

Пономарев  Иван  Сергеевич

без  уч.  степени,  ассистент  на  кафедре  автоматизации  предприятий  связи  Санкт-Петербургского  государственного  университета  телекоммуникаций  им.  проф.  М.А.  Бонч-Бруевича,  РФ,  г.  Санкт-Петербург

E-mail: 

SOFTWARE  MODULE  OF  GENETIC  ALGORITHMS  FOR  CAD  MULTISIM

Ivan  Ponomarev

without  scientific  degree,  Assistant  at  the  Department  of  Automation  Communications  Enterprises  of  the  Bonch-Bruevich  Saint-Petersburg  State  University  of  Telecommunications,  Russia  Saint-Petersburg

АННОТАЦИЯ

В  данной  работе  рассматривается  разработка  программного  модуля  генетических  алгоритмов  для  структурно-параметрической  оптимизации. 

ABSTRACT

This  paper  describes  the  development  of  a  software  module  of  genetic  algorithms  for  structural  and  parametric  optimization.

Ключевые  слова:  генетические  алгоритмы;  структурно-параметрическая  оптимизация;  лестничные  цепи;  Multisim;  SPICE;  программный  модуль.

Keywords:  genetic  algorithms;  structural  and  parametric  optimization;  ladder  circuit;  Multisim;  SPICE;  a  software  module.

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

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

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

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

Рисунок  1.  Представление  схемы  и  принципа  работы  алгоритма

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

Рисунок  2.  АЧХ  лучшего  решения  начальной  популяции

Рисунок  3.  АЧХ  лучшего  решения  всей  эволюции

Для  вычислительного  эксперимента  была  поставлена  задача  найти  оптимальное  решение  фильтра  нижних  частот  с  частотой  среза  200  кГц.  Количество  популяций  и  хромосом  в  каждой  популяции  равны  100.  В  ходе  эксперимента  лучшим  решением  в  начальной  популяции  была  хромосома  №  53  (рис.  2).  Лучшим  решением  во  всей  эволюции  после  окончания  работы  генетического  алгоритма  была  9-я  регенерация  хромосомы  №  61  в  47-й  популяции  (рис.  3).

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

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

1.Акимов  С.В.  Четырехуровневая  интегративная  модель  для  автоматизации  структурно-параметрического  синтеза  //  Труды  учебных  заведений  связи.  —  2004.  —  №  171.  —  С.  165.

2.Курейчик  В.В.,  Гладков  Л.А.  Генетические  алгоритмы.  2.  М.:  ФИЗМАТЛИТ,  2006.  —  стр.  320.