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

Основная проблема, возникающая при автоматизации проектирования, заключается в росте объема вычислений, необходимых для оценки пригодности разрабатываемых проектных решений. В условиях рыночной экономики и жесткой конкуренции между фирмами-разработчиками осуществить такое проектирование в приемлемые сроки при использовании систем автоматизированного проектирования (САПР), ориентированных на использование одиночных компьютеров, не представляется возможным. Выход из сложившейся ситуации заключается в создании САПР, ориентированных на применение распределенных вычислительных структур [34]. Их отличительная особенность заключается в необходимости организации эффективной передачи данных. Если распределенная вычислительная структура состоит из небольшого числа компьютеров, территориально расположенных в непосредственной близости один от другого, то среда передачи данных образуется за счет кабельных соединений между компьютерами. При увеличении числа компьютеров, включаемых в вычислительную структуру, оказывается необходимым прокладывать дополнительные линии связи. При больших расстояниях между узлами необходимо использовать дополнительные ретрансляционные станции, расположенные друг от друга на расстояниях, составляющих 100 — 300 метров. Использование в качестве линий передачи волоконно-оптических линий связи также сталкивается с проблемами их прокладки между элементами распределенной вычислительной структуры.

Если компьютеры, объединяемые в вычислительную структуру, располагаются на существенных расстояниях один от другого, то среда передачи данных организуется за счет использования радиоканалов, использующих для передачи информации электромагнитные волны сверхвысоких частот. Подобные линии связи позволяют разворачивать распределенные вычислительные структуры вне зависимости от особенностей расположения их элементов. Основным требованием к каналам связи при проектировании подобной среды передачи данных является необходимость обеспечить широкую полосу пропускания, необходимую для передачи сигналов с избыточной информативностью для уменьшения вероятности появления ошибки в передаваемой информации [34]. Одним из перспективных подходов к построению распределенных вычислительных структур является RadioEthernet, работающий на основе стандарта IEEE 802/11. В соответствии с требованиями этого стандарта ширина спектра сигнала составляет 22 МГц при несущей частоте 2,4 ГГц. При этом обеспечивается скорость передачи информации до 6 Мбит/с. Для обеспечения подобной полосы пропускания в телекоммуникационные системы должны быть включены широкополосные антенны с большим коэффициентом усиления, позволяющие обеспечить надежную связь между абонентами на расстояниях 15−20 км. Требования к большому коэффициенту усиления антенны связаны с ростом затухания при распространении сигналов более высоких частот.

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

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

Одним из методов случайно-направленного поиска является метод генетического поиска [23]. В середине прошлого века американский исследователь Дж. Холланд [92] описал методологию изучения адаптивных систем и их применения для искусственных систем, а также разработал подходы к решению комбинаторно-оптимизационных задач. Идеи Холланда и его учеников оказались плодотворными и эффективными. В настоящее время генетические алгоритмы — это хорошо известная и эффективная технология оптимизации, применяемая для различных задач техники, моделирующая естественный процесс эволюции в качестве средства достижения оптимума. Она основана на имитации процессов натуральной селекции и генетических преобразований [23].

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

Другим методом случайно-направленного поиска является метод имитации отжига. Он был применен для решения комбинаторно-оптимизационных задач в конце прошлого века. С тех пор этот метод широко используется при решении технических задач, проводятся исследования и разработки его модификаций [64]. Алгоритм имитации отжига повышает вероятность выхода поискового процесса из локальных экстремумов. Недостатком этого метода является большая временная сложность. Алгоритм генетического поиска обладает более быстрой сходимостью по сравнению с методами динамического программирования и моделирования отжига, простотой реализации, но может сходиться к локальному экстремуму используемой функции пригодности [63].

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

Ввиду вышеизложенного, разработка алгоритмов, позволяющих найти приемлемое по качеству и по трудоёмкости решение задачи проектирования элементов телекоммуникационных систем, является АКТУАЛЬНОЙ.

ПРОБЛЕМОЙ, стоящей перед разработчиками САПР.

ЦЕЛЬЮ диссертационной работы является разработка генетических алгоритмов для решения задачи автоматизации проектирования элементов телекоммуникационных систем.

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

1. предложен алгоритм эволюционного проектирования элементов телекоммуникационных систем;

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

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

4. реализован генетический алгоритм получения решения на основе последовательного и смешанного представления информации;

МЕТОДЫ ИССЛЕДОВАНИЯ в диссертации основаны на использовании элементов теории множеств, теории алгоритмов, теории комбинаторной оптимизации, интегральных уравнений.

НАУЧНАЯ НОВИЗНА диссертационной работы заключается в следующем: а) разработан механизм эволюционного проектирования элементов телекоммуникационных систем при последовательной и смешанной системах кодированияб) определена процедура формирования начальной популяции с учетом эвристических ограниченийв) предложены схемы двухуровневой селекцииг) определена процедура формирования текущей популяции альтернативных решений с учетом эвристических ограниченийд) получены вероятностные оценки поведения функции пригодности в зависимости от параметров генетического алгоритма.

ПРАКТИЧЕСКУЮ ЦЕННОСТЬ работы представляют:

— алгоритмы и программы эволюционного проектирования элементов телекоммуникационных систем на основе последовательного и смешанного представления информации;

— схемы двухуровневой селекции и двухуровневой параллельной селекции;

— функции пригодности для эволюционного проектирования узкополосных и широкополосных антенн.

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетной работе, проведенной в Таганрогском Государственном Радиотехническом Университете г/б НИР № 14 890 в 2001 г. При выполнении гранта РФФИ № 01−01−44 применены схемы двухуровневой селекции. Материалы диссертации также использованы в учебном процессе на кафедре ТОЭ ТРТУ в цикле практических занятий.

АПРОБАЦИЯ основных теоретических и практических результатов работы. Результаты работы докладывались и обсуждались на научно-технических семинарах в Таганрогском Государственном радиотехническом университете (2001 -2003г.г.), на Всероссийских конференциях «Информационные системы и технологии» (Нижний Новгород, 2001 г., 2002 г.), на научной сессии МИФИ (Москва, Россия, 2002 г.), на международной конференции SIMS 2002 (Оулу, Финляндия, 2002 г.), на международной конференции IEEE AIS'02 «Прикладные интеллектуальные системы» (Дивноморск, Россия, 2002), на международных конференциях «Интеллектуальные САПР» (Дивноморск, Россия, 2001 г., 2002 г.), на международной конференции ММЕТ'2002 (Киев, Украина, 2002 г.), На международной конференции IEEE AIS'03 «Интеллектуальные системы 2003» (Дивноморск, Россия, 2003 г.).

ПУБЛИКАЦИИ. Результаты диссертации отражены в 12-ти печатных работах. Получено авторское свидетельство на программу эволюционного проектирования вибраторных антенн.

СТРУКТУРА И ОБЪЁМ ДИССЕРТАЦИОННОЙ РАБОТЫ. Диссертационная работа состоит из введения, четырёх глав, заключения, списка литературы и приложения. Работа содержит 129 стр., а также 20 рис., список литературы из 121 наименования, 3 стр. приложений и актов об использовании.

4.5. Выводы.

Полученные в этой главе результаты позволяют сделать следующие выводы:

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

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

3. Существует эффективная вероятность мутации, позволяющая улучшить качество найденных решений. Её величина находится в интервале от 1% до 5%. При вероятности мутации, меньшей 1%, мутация практически не оказывает влияния на эволюционный процесс, а при вероятности мутации, превышающей 5%, эволюционный поиск сводится к простому случайному перебору решений.

4. Эффективность применения алгоритмов эволюционного проектирования с операторами одноточечного и двухточечного кроссинговера определяется используемыми функциями пригодности. Проведенные исследования позволяют сделать вывод о перспективности использования функции пригодности (4.2) для проектирования широкополосных антенн.

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

ЗАКЛЮЧЕНИЕ

.

1. На основе проведённого анализа литературы выделены достоинства и недостатки существующих методов решения задачи эволюционного проектирования элементов телекоммуникационных систем.

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

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

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

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

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

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