Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Реферат: Разработка методов исследования характеристик генетического алгоритма распределе-ния цепей по слоям в МСМ

Название: Разработка методов исследования характеристик генетического алгоритма распределе-ния цепей по слоям в МСМ
Раздел: Рефераты по информатике, программированию
Тип: реферат Добавлен 21:55:36 29 марта 2005 Похожие работы
Просмотров: 86 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

Разработка методов исследования характеристик генетического алгоритма распределения цепей по слоям в МСМ

С.Н. Щеглов, А.В. Мухлаев, В.А. Кулинский

Одной из задач проектирования топологии матричных БИС и СБИС является задача оптимального распределения по слоям трассируемых соединений в базовом матричном кристалле. Известно, что базовый матричный кристалл (БМК) – это компактный модуль с высшей степенью интеграции, служащий для расположения нескольких сотен кристаллов и их соединения несколькими тысячами цепями. Самой общей целью при решении этой проблемы является наиболее эффективное использование площади коммутационного пространства при одновременной оптимизации таких конструктивных параметров схемы, как число слоев количество межслойных переходов, процент реализованных соединений.

Традиционные методы решения этой задачи имеют существенный недостаток – “ловушки” локальных оптимумов. Рассматриваемый генетический метод является методом направленного случайного поиска. Основной характеристикой таких методов является то, что они допускают временное ухудшение целевой функции. Это позволяет избежать “ловушек”, а при достаточном числе итераций найти приемлемое решение. Генетические алгоритмы являются адаптивными поисковыми алгоритмами, которые осуществляют процесс накопления и использования информации в проектируемой области, направленной на достижение оптимального решения при первоначальной неопределенности и изменяющихся внешних условиях. В отличие от стандартных поисковых алгоритмов, генетические алгоритмы базируются на улучшении некоторой популяции, состоящей из ограниченного множества решений. Данная методика мотивируется тем, что поиск в области многих решений уменьшает риск попадания в локальные оптимумы, что дает более лучшие результаты, чем использование одного решения.

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

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

Рис 1.

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

Если условие рассматриваемой задачи заданно на рис. 1, то хромосома примет вид

1 2 3 4 5 6 7

Пусть после применения некоторых генетических операторов новая хромосома имеет вид:

3 4 6 5 2 7 1

тогда решение, закодированное в новой хромосоме, изображено на рис. 2

Рис 2

где разными типами линий показаны разные слои распределяемых цепей.

Раскодирование хромосомы происходит по следующим правилам:

Берется первый ген хромосомы и по значению его аллели определяется исходная цепь. Полученная цепь кладется в первый слой, затем аналогичным образом получаем новую цепь из аллели второго гена хромосомы (цепь 4 в данном примере); сведения о том могут ли эти ребра находится в одном слое получаем из массива ограничений, который мы определили выше. Если могут, то определяем их в один слой, если нет, то слой объявляем заполненным цепь определяем в следующем слое, а к заполненным слоям не возвращаемся с попытками дополнить их новыми цепями.

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

Оператор селекции выбирает представителей настоящего поколения для участия в последующих генетических операциях. Для каждой хромосомы вычисляется целевая функция. В данной задаче основным критерием оценки является минимум числа слоев, необходимых для распределения трассируемых соединений:

Где f(i,t) – значение целевой функции для i-й хромосомы;

N – число слоев.

Целевая функция определяет ценность каждой хромосомы. Хромосомы с лучшими характеристиками затем подвергаются действиям генетических операторов. В программе реализованы три оператора селекции: стандартные операторы “Колесо рулетки» и “Турнирный”, а также модификация “Колеса рулетки” в котором выбор хромосомы происходит как в “Колесе” но второй раз хромосома уже не может выбираться.

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

Например: оператор кроссинговера получил двух родителей

Р1: 1 8 11 12 15 0 3 5 6 9 2 7 4 10 13 14

P2: 1 2 7 8 11 0 6 9 4 10 12 13 14 15 3 5

При раскодировке алгоритм распределил их по слоям

P 1

Слой 0: 1 8 11

Слой 1: 12 15

Слой 2: 0 3 5 6 9

Слой 3: 2 7

Слой 4: 4 10 13 14

P 2

Слой 0: 1 2 7 8 11

Слой 1: 0 6 9

Слой 2: 4 10

Слой 3: 12 13 14 15

Слой 4: 3 5

Слой 0: 1 8 11:

Слой 1: 12 15

Слой 2: 0 3 5 6 9

Слой 3: 2 7

Слой 4: 4 10 13 14

Слой 2,0: 1 2 7 8 11

Слой 0: 1 2 7 8 11

Слой 1: 0 6 9

Слой 2: 4 10

Слой 3: 12 13 14 15

Слой 4: 3 5

Слой 1,2: 0 3 5 6 9

П1:

Слой 0: 12 15

Слой 1: 0 3 5 6 9

Слой 2: 4 10 13 14

Слой 3: 1 2 7 8 11

П2:

Слой 0: 1 2 7 8 11

Слой 1: 4 10

Слой 2: 12 13 14 15

Слой 3: 1 5 6 14 15

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

Операция мутации применяется к одной хромосоме и незначительно преобразует ее путем локальных случайных перемещений. Однако применение различных операторов мутации убыстряет или замедляет нахождение приемлемого решения задачи. Неплохие результаты дает применение оператора мутации известного в литературе как “Золотое сечение”.

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

Но, как выяснилось в ходе исследования, ощутимого вклада в решение задачи они не внесли. Цель их, как и операторов мутации, – предотвращение единообразия во множестве решений. Сознательное ухудшение некоторых решений привносит новую информацию и является механизмом выхода из “локальных” ям.

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

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

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

По выше описанному алгоритму была сделана программа на языке BorlandC++ под Windows 95, которая позволяет эффективно использовать все богатство генетического инструментария.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений21:38:08 18 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
14:46:18 24 ноября 2015

Работы, похожие на Реферат: Разработка методов исследования характеристик генетического алгоритма распределе-ния цепей по слоям в МСМ

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(150348)
Комментарии (1830)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru