Содержание к диссертации
Введение
1. Обзор и анализ генетических алгоритмов для решения задач проектирования БИС 11
1.1. Генетические операторы 11
1.2. Генетические алгоритмы компоновки элементов СБИС 21
1.3. Алгориты трассировки СБИС 32
1.4. Выводы 37
2. Разработка архитектуры и стратегии генетического поиска генетических алгоритмов компоновки, группирования элементов и трассировки СБИС 39
2.1. Архитектура и стратегии 39
2.2. Генетический алгоритм компоновки 47
2.3. Генетический алгоритм группирования элементов 60
2.4. Генетический алгоритм трассировки СБИС построением дерева Штейнера 66
2.5. Выводы 77
3. Разработка модифицированных генетических операторов 78
3.1. Представление хромосом по Нейману 78
3.2. Разработка модифицированных операторов кроссинговера 83
3.3. Разработка модифицированных операторов мутации 93
3.4. Анализ разработанных генетических операторов 98
3.5. Выводы 105
4. Экспериментальные исследования разработанных генетических алгоритмов 106
4.1. Программная среда для решения задач компоновки и группирования элементов СБИС 106
4.2. Программная среда для решения задачи трассировки СБИС ПО
4.3. Результаты экспериментальных исследований 112
4.3.1. Порядок выполнения экспериментальных исследований 112
4.3.2. Результаты экспериментальных исследований генетических алгоритмов компоновки элементов СБИС 113
4.3.3. Результаты экспериментальных исследований генетических алгоритмов трассировки СБИС 119
4.4. Выводы 125
Заключение 126
Список литературы
- Генетические операторы
- Архитектура и стратегии
- Представление хромосом по Нейману
- Программная среда для решения задач компоновки и группирования элементов СБИС
Введение к работе
В настоящее время основным фактором ускорения научно-технического прогресса, повышения качества общественного производства, является полная автоматизация производственных процессов, одним из важных направлений является использование средств вычислительной техники, которая в настоящее время достигла высоких результатов в скорости и быстродействии. В то же время появление новых разработок в области вычислительной техники, создание компьютерных моделей, обладающих более высокой степенью быстродействия, являются основными предпосылками для разработки новых технологий производства основных узлов электронно-вычислительной аппаратуры (ЭВА), основными элементами которых являются БИС и СБИС[8,90,96,100-119]. Основным языком ЭВА является формальный язык математики. Способность формализовать математические структуры и оперировать с ними - краеугольный камень человеческого интеллекта. Математические структуры и алгоритмы - это те формы, в которых теория вычислительной техники и искусственного интеллекта (ИИ) образуют знания об интеллектуальных процессах. Вследствие роста интеграции элементной базы ЭВА и повышения требований к параметрам узлов ЭВА актуальной является проблема создания методов проектирования БИС, выполняемых без участия человека. СБИС составляют элементную базу ЭВА новых поколений, содержат миллион и более транзисторов на кристалле. В этом случае трудоёмкость NP- полных задач проектирования [90, 96, 100 - 119], конструирования и технологии резко возрастает и поэтому использовать алгоритмы с экспоненциальной временной сложностью становится невозможным из-за необходимости обработки огромных массивов информации. В этой связи становится необходимым модернизация структуры, как традиционных САПР, так и основных алгоритмов входящих в математическое обеспечение(МО) САПР. Одним из подходов такой модернизации является использование методов моделирования эволюции и генетических алгоритмов(ГА), а также их модифика-
ция и нахождение новых подходов к решению задач проектирования СБИС.
Впервые термин "эволюция" был использован в биологии швейцарским учёным Бонне в 1782году. Слово "эволюция" произошло от латинского слова "развёртывание" и является синонимом понятия развития. Под эволюцией понимаются медленные, постепенные, количественные и качественные изменения объекта. При этом каждое состояние объекта должно иметь по сравнению с предшествующим более высокий уровень развития и организации.
В биологии эволюция определяется наследственной изменчивостью, борьбой за существование, естественным и искусственным отбором. Эволюция приводит к формированию адаптации (приспособлений) организмов к условиям их существования, изменению генетического состава, популяции видов, а также отмиранию неприспособленных видов. Сейчас под адаптацией понимается процесс приспособления строения и функций организмов и их органов к условиям окружающей среды. О том, что явление адаптации имеется в живой природе было известно биологам прошлых веков.
Генетика - наука о законах наследственности и изменчивости организмов. Основные задачи генетики это разработка методов управления наследственностью и наследственной изменчивостью для получения "нужных" индивидууму форм организмов или в целях управления их индивидуальным развитием. В 1985 году Мендель разработал основные законы генетики. Они утвердили принцип дискретности в явлениях наследования и организации генетического материала, сосредоточив основное внимание на изучение закономерностей наследования потомками признаков и свойств их родителей. Понятие "гена" введено в 1909 году В.Иогансеном. В настоящее время ген это элементарная единица наследственности, отвечающая за появление какого- либо признака. Гены обычно собираются в пределах хромосом. Наследование признаков может изменяться и нару-
шаться в результате различных генетических операций, а также изменение порядка расположения генов в хромосоме, ведущих к перераспределению генетического материала между хромосомами. Наследственное разнообразие особей создаётся с одной стороны за счёт рекомендации генов при скрещивании, а с другой стороны в результате изменения самих генов за счёт разнообразных мутаций.
В 1975 году Холланд [5], описал методологию для изучения натуральных адаптивных систем и их применение для искусственных адаптивных систем, а также привёл подходы к решению задач ИИ. Идеи Холланда и его учеников оказались настолько плодотворными и эффективными, что в США и в других странах начали проводиться разработки и исследования в этой области. Сейчас генетические алгоритмы - хорошо известная и эффективная оптимизационная методология, которую применяют для решения различных задач техники, основанная на аналогии процессов натуральной селекции и генетических преобразований в биологии. Биологическая основа этой эффективной методологии для адаптивных процессов, есть эволюция от одной генерации к другой. Причём основой этого процесса является выживание сильнейших, что выполняется путём исключения слабых элементов и составления оптимальных или квазиоптимальных элементов.
В последнее время проведена разработка и исследование применения генетических алгоритмов эффективного решения задач в проектировании СБИС [47,52]. А именно для этапов конструкторского проектирования: компоновка элементов СБИС, компоновка блоков СБИС, трассировка, размещение элементов, группирование элементов и блоков СБИС, типизация, верификация и кланирование кристалла [14,15,34,68,81,84,101,105-119]. Разработаны эффективные ГА, позволяющие оптимизировать процесс проектирования. Разрабатываются новые модифицированные генетические операторы и генетические алгоритмы. Среди основных задач данного этапа (конструкторского проектирования) являются задачи компонов-
ки элементов и трассировки СБИС, которые являются многовариантными, экстремальными, комбинаторно-логическими задачами, требующими больших временных затрат для их решения. Поэтому разработка новых генетических алгоритмов с полиномиальной временной сложностью для решения рассматриваемых задач является актуальной проблемой.
Цель и задачи исследования. Целью диссертационной работы является разработка и исследование эффективных поисковых и генетических алгоритмов для решения задач компоновки элементов и трассировки СБИС.
Достижние указанной цели предполагает решение следующих основных задач:
построение архитектур генетического поиска, ориентирован
ных на решение задач компоновки элементов и трассировки СБИС;
разработка и исследование генетических алгоритмов компо
новки и группирования элементов СБИС;
разработка генетического алгоритма трассировки СБИС путём
построения дерева Штейнера;
разработка модифицированных генетических операторов
кроссинговера и мутации, позволяющих сокращать область поиска;
Методы исследования. В работе используются методы теории графов, множеств, алгоритмов и методология генетических алгоритмов и эволюционного моделирования. Научная новизна диссертационной работы заключается в следующем:
Разработана архитектура генетического поиска, ориентированная на решение задач компоновки элементов и трассировки СБИС;
Разработаны генетические алгоритмы компоновки и группирования элементов СБИС, позволяющие получать локальные оптиму-мы;
Разработан алгоритм генетического поиска для построения дерева Штейнера;
4. Построены генетические операторы кроссинговера и мутации; Практическая ценность результатов диссертационной работы определяется созданием комплекса алгоритмов и программ решения комбинаторных задач компоновки, группирования элементов и трассировки СБИС. Программы реализованы на языке Паскаль. Проведённые экспериментальные исследования показали преимущество предложенных поисковых и генетических алгоритмов для решения рассматриваемых задач, по сравнению с существующими численными и поисковыми алгоритмами. Временная сложность разработанных алгоритмов компоновки, группирования и трассировки соответствует полиномиальному времени, которое требуют итерационные алгоритмы. На защиту выносятся:
- архитектуры генетического поиска, ориентированные на решение за
дач компоновки элементов и трассировки СБИС;
алгоритм компоновки элементов СБИС, позволяющий находить локальные оптимумы;
алгоритм группирования элементов СБИС;
алгоритм трассировки соединений для построения дерева Штейнера;
модифицированные операторы кроссинговера и мутации, позволяющие быстрее локализовать решение.
Реализация результатов работы. Полученные результаты использованы при выполнении фундаментальных госбюджетных научно-исследовательских работ Ростовской государственной академии сельскохозяйственного машиностроения(РГАСХМ) на кафедре "Прикладная математика и вычислительная техника"(ПМ и ВТ) по заказу Минобрнауки РФ по темам: "Теория поисковой адаптации для решения комбинаторных задач оптимизации"^ 1.01.2003 - 31.12.2004г.г.) и "Теория интеллектуальных процедур поиска оптимальных решений"(01.01.2005 - 31.12.2005 г.г.), а также при проектировании и эксплуатации автоматизированных систем контроля и диагностики радиоэлектронной аппаратуры в НИИ специальных информа-
ционно-измерительных систем НИИСИИС (г. Росто-на-Дону). Кроме того, материалы диссертации используются в учебном процессе на кафедре "ПМ и ВТ" РГАСХМ при чтении лекций по дисциплинам "Дискретная математика" и "Программные средства САПР". Основные положения, выносимые на защиту:
Архитектура и стратегии генетического поиска;
Модифицированные генетические алгоритмы компоновки и группирования элементов СБИС, позволяющие получать оптимальные решения за однократное срабатывание операторов.
Генетический алгоритм трассировки СБИС, позволяющий получать оптимальные решения за полиномиальное время.
Модифицированные операторы кроссинговера и мутации, основанные на представлении хромосом по Нейману.
Апробация работы. Основные научные и практические результаты работы докладывались, обсуждались и были одобрены на Международых научно-технических конференциях "Интеллектуальные системы "(AIS-05) и "Интеллектуальные CAITP"(CAD-2005) (г. Геленджик 2005 г.), на VII Всероссийской научной конференции студентов и аспирантов "Техническая кибернетика, радиоэлектроника и системы управления" (КРЭС'04) (г.Таганрог 2004 г.), на региональных научно-технических конференциях "Проблемы современного машиностроения"^. Ростов-на-Дону, РГАСХМ, 2005, 2004 г.г.)
По материалам диссертационной работы опубликовано 6 работ, материалы вошли в два отчета по НИР.
Публикации. Основные результаты диссертационной работы отражены в 6 печатных работах.
Структура и объём диссертационной работы. Данная работа содержит четыре основных раздела. В первом разделе обзор и анализ известных генетических операторов и алгоритмов решения задач конструкторского проектирования. В частности задач компоновки элементов и трасси-
ровки СБИС. Приводится описание алгоритмов построения дерева Штей-нера и решения данных задач на графах. Показана трудоёмкость работы каждого из рассмотренных алгоритмов. Во втором разделе разработаны модифицированные архитектура и стратегии генетического поиска, ориентированные на решение задач компоновки элементов и трассировки СБИС. На основе предложенных архитектуры и стратегий генетического поиска предложены алгоритмы компоновки и группирования элементов СБИС, а также алгоритм трассировки соединений СБИС при построении дерева Штейнера. Описана работа каждого из предложенных алгоритмов, на основе модифицированных генетических операторах кроссинговера и мутации. В третьем разделе представлены предложенные модифицированные генетические операторы кроссинговера и мутации. Описана работа каждого из предложенных операторов. Дана сравнительная характеристика предложенных операторов кроссинговера и мутации с известными двухточечными операторами кроссинговера и мутации. В четвёром разделе приведены результаты экспериментального исследования разработанных алгоритмов с существующими и программное обеспечение для решения рассматриваемых задач проектирования СБИС.
Генетические операторы
Решение задач оптимизации на основе механизмов генетики являются эффективным средством решения оптимизационных задач [4,5, 42, 48,90,100-120], преимущество которых в параллельной обработке множества альтернативных решений, что является мощным средством выхода из локальных оптимумов. Генетические алгоритмы (ГА) - алгоритмы случайного поиска, однако заложенная в них стратегия эволюционного развития на основе естественного отбора приводит к синтезу решений, близких к оптимальным [16].
Объяснение принципа работы генетических алгоритмов представлено Д. Гольдбергом [3] как гипотеза о строительных блоках, в которой предполагается, что генетические алгоритмы выполняют одновременно две задачи. Первая заключается в выращивании строительных блоков, а вторая состоит в смешивании этих блоков с целью получения оптимального решения. Чтобы получить достаточно уверенную сходимость к глобальному оптимуму, необходимо, чтобы оба этих процесса были сбалансированы. Математические оценки эффективности генетических алгоритмов сформулированы в виде фундаментальной теоремы генетических алгоритмов [5].
Генетический алгоритм включает основные понятия и операции [ 2-7, 42, 86,87]: хромосома - закодированный вариант решения; ген - элемент решения; популяция - исходное множество вариантов решений; функция соответствия - критерий отбора вариантов; скрещивание -операция получения вариантов-отпрысков из вариантов-родителей; мутация -случайное изменение элементов хромосом.
Генетические алгоритмы предполагают выполнение следующих этапов [29, 30]: кодирование генотипа и фенотипа; создание начальной по пуляции; определение целевой функции; селекция и репродукция (крос-синговер, мутация и т.д.); репродукция. Под фенотипом понимается решение ГА, а генотипом является закодированная последовательность решений в виде определённого набора символов.
Рассмотрим существующие генетические операторы и их модификации. 1. Оператор кроссинговера (репродукция) заключается в разрыве гомологичных хроматид с последующим соединением их в новом сочетании. Схема простого оператора кроссинговера: X А
Двухточечный ОК(ДОК). Определяются две точки ОК, и гены обмениваются между двумя точками ОК. Точки ОК и ДОК определяются случайно. Развитием двухточечного ОК является многоточечный опера тор кроссинговера, выполняется аналогично ДОК, однако большое число "разрезающих" точек может привести к потере "хороших" родительских свойств.
Операторы кроссинговера делятся на несколько типов, которые являются частными случаями универсального кроссинговера. При действии универсального кроссинговера используется маска выбора родительских генов для потомка. Если в маске в текущей позиции значение 1, то ген данной позиции наследуется от первого родителя, если О, то от второго.
Упорядоченный кроссинговер Выбирается точка деления хромосом, перед которой группы родительских генов переходят потомкам. Группы генов потомков после деления заполняются родительскими генами, недостающими и неповторяющимися в передней части потомков.
Частично соответствующий OK, здесь также случайно выбирается "разрезающая" точка или точка ОК. Далее анализируются сегменты в обоих родителях и устанавливается частичное соответствие между элементами первого и второго родителей с формированием потомков. Циклический ОК, выполняет рекомбинации согласно циклам, которые существуют при установлении соответствия между генами первого и второго родителей. Циклический ОК и его модификации эффективно применяются для решения задач о коммивояжере и некоторых задачах размещения элементов на плоскости.
Существует ещё несколько модификаций оператора кроссинговера (ОК): порядковый, частично соответствующий, циклический, универ-сальный(рассмотренный выше), "жадный", на основе множества Кантора, на основе дихотомии, на основе метода "золотого сечения", на основе чисел Фибоначчи (2,3,5, 8, 13,21,...).
2. Оператор мутации (ОМ), существует несколько видов оператора мутации: одноточечная, двухточечная, многоточечная, порядковая, универсальная, "жадная", на основе множества Кантора, на основе дихотомии, на основе метода "золотого сечения", на основе чисел Фибоначчи, аргументированный знаниями, дупликация, делеция, внутри-хромосомная, межхромосомная. Мутация - генетическое изменение, приводящее к качественному поколению на основе основных свойств генетического материала: дискретности, непрерывности или линейно сти. Мутация представляет собой изменение генов, хромосом, геномов. Простая мутация представляет собой изменение хромосомы, т.е. изменение расположения гена.
Архитектура и стратегии
При проектировании СБИС одним из основных этапов является конструкторское проектирование. Среди основных задач которого являются задачи компоновки элементов и трассировки СБИС. Т.к. в настоящее время существует большое количество алгоритмов и архитектур генетического поиска, то возникает необходимость в их модернизации для уменьшения времени и улучшения качества поиска решения. В архитектурах генетического поиска для улучшения качества решения оптимизационной задачи используется понятие адаптации. Адаптация - это процесс, а также и результат приспособления строения и функций организмов к условиям внешней среды [96], в данном случае способность технической системы изменять свое состояние и поведение (параметры, структуру, алгоритм и функционирование) в зависимости от изменения условий внешней среды путем накопления и использования информации о ней. В процессе изменения внешних условий, полученную информацию в процессе работы об этих условиях используют для повышения эффективности работы системы.
Предложенный в [96] групповой генетический алгоритм с направленной мутацией. Алгоритм состоит из двух уровней. Верхний уровень алгоритма выполняет групповой, а нижний - индивидуальный поиск. На первом этапе берется популяция размером в несколько раз больше чем в простом ГА с целью большего охвата пространства поиска. Элементы в популяции оцениваются, затем хромосомы со значением ЦФ меньше средней отбрасываются, а из оставшихся составляются подпопуляции. Далее поиск ведется внутри отдельных групп.
На основе рассмотренных архитектур генетического поиска предлагается упрощенная модифицированная схема последовательного эволюционного поиска, показанная на рис. 2.1.
Опишем работу упрощенной схемы эволюционного поиска: Конструируется начальная популяция Р = Np, Pj є Р, і = \,Np. 1. Определяется значение ЦФ для всех хромосом популяции, которое также зависит от конкретной задачи. 2. Производится применение генетических операторов к хромосомам в популяции (кроссинговера и мутации). 3. Производится вычисление ЦФ популяции хромосом после применения операторов кроссинговера и мутации, а также среднее значение ЦФ. 4. К потомкам, на основе взаимодействия с внешней средой, блоками адаптации и ЭС применяется модель эволюции Дарвина. При этом, если получено заданное решение или значение критерия останова алгоритма, то п. 6, иначе п.5. 5. Производится селекция, оставляя количество потомков равное размеру начальной популяции. 6. Конец работы алгоритма.
В схеме эволюционного поиска после селекции популяции будут применяться операторы кроссинговера и мутации до тех пор, пока не будет найдено заданное решение.
Преимущество рассмотренной схемы эволюционного поиска является использование меньшего числа генетических операторов, в отличие от всех известных архитектур поиска.
При решении задач компоновки элементов и трассировки СБИС, по мнению автора, будут иметь преимущества, разработанные генетические алгоритмы основанные на применении модифицированных генетических операторов кроссинговера и мутации (описанные ниже). Другое преимущество предлогаемого ГА является возможность увеличения популяции для нахождения заданного решения за счет применения модифицированного оператора кроссинговера (работа которого описана ниже), который работает с некоторым множеством решений, что позволит быстрее получить необходимый результат.
Автором предлагается модифицированный ГА, состоящий из четырех основных блоков. Первый блок называется блоком моделей, в котором осуществляется построение графовый и гиперграфовых моделей коммутационных (а также электрических и функциональных) схем для дальнейшей компоновки элементов. Для задачи трассировки СБИС этот блок задает количество узлов и их размещение на коммутационном поле. Второй блок называется генератором, в котором производится создание одной начальной популяции решения компоновки элементов либо трассировки СБИС.
Третий блок - блок генетического поиска: выбор представления решения; разработка модифицированных генетических операторов случайных, направленных и комбинированных изменений входной информации; определение закона выживания; рекомбинация.
Четвертый блок называется блоком анализа полученного решения. Здесь реализуются принципы адаптации полученных решений к внешней среде. Это обобщенная горизонтально организованная архитектура генетического поиска при компоновке элементов и трассировки СБИС, показанная на рис.2.2. Ее преимуществом является то, что в ней все уровни связаны с уровнем внешней среды и могут общаться между собой.
Представление хромосом по Нейману
Современная теория явлений наследственности, называемая генетикой, развилась из простых законов, открытых Георгом Менделем сто лет назад. Эти законы по существу являются вероятностными, т.е. они формулируются в терминах относительных частот и открывают очень интересную и важную область приложений теории вероятностей[42]. Как и всякое явление природы, процесс формирования наследственности сложен, и проявляющиеся закономерности подвержены многим исключениям[9,62]. Так как организм не наследует непосредственно свои признаки, он наследует скорее способность реагировать некоторым образом на окружающие условия. Носителями способностей к отдельным реакциям являются гены. Гены объединяются в хромосомы, которые можно видеть в клетках организма. Число хромосом в каждой клетке зависит от вида организма. Например, у человека 48 хромосом. За некоторыми исключениями, хромосомы существуют парами, так что мы будем говорить о хромосомной паре как о простейшей единице. На рис. 3.1 иллюстрируется процесс формирования и оплодотворения половых клеток - гамет. Для простоты предполагается, что в каждой клетке имеется только одна хромосомная пара. В мужском организме обозначим эти хромосомы через А и В, а в женской через а и Ъ. Для каждого признака (или для каждого отдельного вида реакций) существует ровно два гена, носителем каждого из которых является та или иная хромосома. На рис.3.1 первый показана ситуация, предшествующая началу образования гамет Первый шаг этого процесса показан на рис. 3.2; каждая из двух хромосомных пар может разделиться на две части в некоторой точке, которая меняется от одной хромосомной пары к другой и от одной клетке к другой. Обе нити одной хромосомной пары разбиваются в одной и той же точке. Полученные части нитей хромосомной пары А обо значим через Ап, Aj2, A2j и А22; аналогично поступим с частями хромосомной пары В. В некоторых случаях хромосомы могут делиться на число частей, большее двух. Рис. 3.1 и рис. 3.2 иллюстрируют, однако, только простейший случай деления. На рис. 3.3 показан следующий шаг. Он состоит в продольном расщеплении получившихся после деления частей, которые начинают двигаться самостоятельно.
Затем части нитей объединяются в пары, которые располагаются в противоположных концах клетки. На этом шаге, называемом рекомбинацией хромосомных пар, с одинаковой частотой происходит одно из двух событий: либо, как показано на хромосоме А, обе части соединяются в том же порядке, какой они занимали, до деления, или, как показано на хромосомной паре В, первая часть одной нити комбинируется со второй частью другой нити. Последний шаг состоит в разделении первоначальной клетки на две половые клетки - гаметы, как показано на рис. 3.4.
Каждая гамета несёт лишь одну нить от каждой хромосомной пары. Оплодотворение состоит в соединении двух гамет- одной из отцовского организма и одной из материнского организма. На рис. 3.5 показана такая материнская клетка, в которой имеется по одной нити из двух хромосомных пар, полученных рекомбинацией частей яц и я22 и Ь\\ и соответственно.
Хромосомы в отцовской и материнской клетках, конечно, не обязательно делятся в одной и той же точке.
На рис. 3.6 показана та же материнская клетка, что и на рис. 3.5, оплодотворённая первой из двух отцовских гамет, показанных на рис. 3.4. Соответствующие нити отдельных хромосомных пар соединились, образовав обычную хромосомную пару, состоящую из двух хромосомных нитей. Жизнь живого организма — потомка - начинается с образования оплодотворённой клетки - зиготы. Эта клетка растёт и делится, производя две тождественные клетки, которые делятся снова и снова и т.д.
На рисунках в каждой из обеих хромосомных пар обозначено по 10 символов (gn и т.д.). Эти символы обозначают гены или положения, которые они могут занимать, называемые локусами. Хотя действительное число генов в какой-либо данной хромосомной паре неизвестно, можно с уверенностью сказать, что оно превосходит десять, так что наши рисунки сильно упрощают ситуацию. Кроме того, схемы клеток и хромосомных пар, показанные на рис.3.2- 3.6, имеют мало общего с тем, что мы видим под микроскопом в действительной клетке.
Рассмотрим отдельный локус в хромосомной паре, например, в хромосоме А, отмеченные буквами а.\ и аг. Этот локус связан с некоторой способностью или свойством организма. Мы можем считать, например, что это — окраска цветов гороха. В обычных условиях горох может цвести либо красными, либо белыми цветами. Таким образом, существует два различных гена, скажем G и g, которые могут занимать локус ( хь а ). Один из этих генов (g) обуславливает белую окраску цветов гороха, другой (G) красную. Если данное растение имеет два гена вида g ( т.е. имеет " генетический тип gg"), то его цветы имеют белую окраску и все потомки наследуют лишь ген g. Если растение имеет два гена G ( т.е. имеет " генетический тип GG"), то его цветы красные и все его гаметы несут ген G. Перекрёстное опыление растений с генотипами gg и GG даёт потомков с генотипом gG. Организмы, которые являются носителями одинаковых генов в некотором локусе, т.е. либо gg, либо GG, называются гомозиготными. Организмы с двумя различными генами gG называются гетерозиготными или гибридами. Цветы гибридного гороха всегда красные, т.е. имеют ту же окраску, что и гомозиготные растения GG. Это обстоятельство находит своё выражение в том, что G называется доминантным геном, а g - рецессивным геном. Аналогично растения с генотипом gg называются чисто рецессивными, а с генотипом GG - чисто доминантными.
Явление полной подавляемости одного гена другим, так что гибриды внешне ничем не отличаются от чистых доминантов, встречается очень
часто. Для некоторых признаков, однако, доминируемость бывает или неполной или вообще отсутствует, так что гибрид можно всегда отличить от гомозиготного индивидуума. В некоторых случаях гибридный тип занимает промежуточное положение между чисто рецессивным и чисто доминантным. Доминантные гены обычно обозначаются большими латинскими буквами, а рецессивные гены - малыми латинскими буквами. В случае с цветами гороха существует только два гена g и G, относительно которых известно, что они могут занимать определённый локус, обуславливающий ту или иную окраску цветов. Другими словами, какое бы растение гороха мы ни рассмотрели, этот частный локус будет содержать одну из трёх комбинаций gg, gG или GG и больше ничего. Это таков простейший случай. В других случаях существует п 2 генов, скажем gb g2, ..., gn, которые могут у различных организмов одного вида комбинироваться парами и располагаться в одном и том же локусе. Например, группа крови человека зависит, по-видимому, от трёх различных генов.
Программная среда для решения задач компоновки и группирования элементов СБИС
Структурная схема программной среды реализации алгоритма трассировки для построения дерева Штейнера показана на рис.4.3. Программа состоит также из двух основных блоков: блока входных данных и блока построения новой популяции. Отличие заключается в блоке оценки трассировки соединений, в котором осуществляется оценка и расчет длины построенного дерева Штейнера.
Входными данными для алгоритма трассировки является количество точек на коммутационном поле(КП), входные данные могут быть оригинальными - задаются соответственно схеме на которой необходимо произвести трассировку соединений и тестовыми - количество точек(узлов) тестируемой схемы.
После задания входных данных задаются параметры ГА, какие операторы будут использоваться, для данной задачи используется модифицированный ОК описанный в пункте (3.2). Здесь также задаются количество хромосом и вероятность кроссинговера.
Далее генерируется начальная популяция, в данном случае четыре хро-мосомы(по две от каждого родителя). После того, как начальная популяция сгенерирована переход на второй блок, генерируется новая популяция -применение модифицированного ОК, и далее производится отбор родительской пары хромосом для построения на КП. После отбора осуществляется построение хромосом на КП и производиться оценка и расчет длины построенного дерева Штейнера. Алгоритм заканчивает свою работу, если найдено оптимальное значение построенного дерева. Если оптимального решения не найдено, то переход на ОК и процесс продолжается.
Целью экспериментальных исследований разработанных алгоритмов является опредление оптимальных параметров, при которых алгоритмы находят лучшие решения за минимальное время работы по сравнению с существующими.
Эффективность алгоритмов может быть доказана в результате: 1. Теоретических исследований, т.е. сравнением временной и пространственной сложности алгоритмов. 2. Экспериментальных исследований путём сранения полученных данных. Объектами исследования являются: 1. Генетические алгоритмы компоновки и группирования элементов СБИС, основанные на модифицированных операторах кроссинговера и му тации. 2. Генетический алгоритм трассировки СБИС построением дерева Штей нера, основанный на применении предложенных операторах.
Для обеспечения объективности проводилась серия экспериментов с использованием различных тестовых функций.
Экспериментальные исследования проводились в следующей последовательности: 1. Проведение экспериментов для фиксированных значений общих и изменяемых дополнительных параметров алгоритма. 2. Снятие экспериментальных данных и получение значений ЦФ, являющихся результатами решений при использовании конкретного алгоритма. 3. Определение параметров при которых решение задачи наиболее оптимально. Для подтверждения теоретической оценки временной алгоритма исследовалась: 1. Зависимость быстродействия алгоритма от исходного множества точек(вершин) при решении задач компоновки элементов и трассировки СБИС. 2. Значение критерия остановки при вычислении оптимального решения.
Объектом экспериментальных исследования на данном этапе является сравнение оптимизационных задач на графах для решения задач компоновки элементов СБИС. Показателем качества(целевой функцией) будет являться количество внешних связей (рёбер), при разбиения графа на час-ти(блоки).
Входными параметрами программы компоновки элементов являются: 1. Количество вершин графа от 50 до 1000. 2. Количество рёбер графа от 150 до 3000. 3. Размер начальной популяции п=2.
Так как в последнее время автором не обнаружено алгоритмов компоновки элементов СБИС, то сравним предложенный алгоритм с алгоритмом компоновки блоков СБИС [8 8], потому, что эти задачи сводятся к решению оптимизационных задач на графах.
В таблицах 4.1. и 4.2. приведены данные экспериментальных исследований и на рисунках 4.4 и 4.5 показаны графики зависимостей, в которых Ряд 1 - известный алгоритм, Ряд 2 — предложенный алгоритм. При этом для предложенного алгоритма количество итераций не учитывается, так как оно лежит в пределах от 1 до 4-х.
