Курсовая работа по дисциплине «Разработка систем автоматизированного проектирования»


Скачать 367.39 Kb.
НазваниеКурсовая работа по дисциплине «Разработка систем автоматизированного проектирования»
страница2/3
Дата публикации16.03.2013
Размер367.39 Kb.
ТипКурсовая
userdocs.ru > Математика > Курсовая
1   2   3
Глава 4. РАЗРАБОТКА АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ ТРАССИРОВКИ
^ 4.1. Обоснование выбора алгоритмов решения задачи

В главе 3 мы рассмотрели 2 группы алгоритмов для следующих задач:

  1. Определение порядка соединения выводов внутри цепи

  2. Нахождение последовательности проведения соединений в каждом слое


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

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

Лучевой алгоритм позволяет существенно уменьшить затраты машинного времени на задачу. [2] Но при распространении луча может возникнуть ситуация, когда все соседние ячейки будут заняты. В этом случае луч считается заблокированным и его распространение прекращается. Обычно с помощью лучевого алгоритма удается построить до 70-80% трасс, остальные проводят, используя волновой алгоритм или вручную. Его применение особенно выгодно при проектировании плат с невысокой плотностью монтажа.

В нашей работе для проведения трасс будет использован волновой алгоритм Ли, как дающий 100% результат, не требующий проверок и применения дополнительных методов.
^ 4.2 Бионические предпосылки алгоритма пчелиных колоний

Для описания поведения пчёл в природе используются три следующих основных понятия [10].

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

Занятые фуражиры – пчелы, которые «связаны» с одним из источников нектара, т.е. добывают на нем нектар. Занятые фуражиры владеют следующей информацией о «своем» источнике нектара: направление от улья на источник; полезность источника.

Незанятые фуражиры – пчелы-разведчики, которые осуществляют поиск источников нектара для их использования, а также пчелы-наблюдтели, которые в данное время выполняют некоторые работы в улье.

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

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

Одновременно в пределах области танцев разные пчелы могут "рекламировать" различные источники нектара. Механизмы принятия решений, в соответствии с которыми пчела решает следовать за той или иной пчелой-вербовщиком, исследованы недостаточно хорошо. Логично предположить, что вероятность вербовки тем или иным образом определяется полезностью соответствующего источника нектара [10].

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

1)Положительная обратная связь – на основе информации, полученной от других пчел, пчела летит к одному из источников нектара.

2)Отрицательная обратная связь – основываясь на информации, полученной от других пчёл, данная пчела может решить, что «ее» источник нектара значительно хуже других найденных источников, и оставить этот источник.

3) Случайность – вероятностный поиск пчёлами-разведчиками новых источников нектара.

4) Множественность взаимодействия – информация об источнике нектара, найденном одной пчелой, передается многим другим пчелам улья.
^ 4.3 Трассировка как задача глобальной условной оптимизации

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

Рассмотрим задачу глобальной условной оптимизации:

где  - вектор варьируемых параметров,   - множество допустимых значений этого вектора.

Обозначим пчелиный рой  , где - пчела (агент),  - число агентов в рое.

Положение пчелы  в момент времени  определяется вектором ее координат . Пусть   - пчела-разведчик; S < Z.

Схема используемого варианта метода роя пчел имеет следующий вид. На первом шаге метода в точки со случайными координатами , отправляются пчелы-разведчики. В зависимости от значений целевой функции F(Xв этих точках, в области D выделяются два вида участков (подобластей) :

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

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

Подобласть   называется подобластью локального поиска и представляет собой гиперкуб в пространстве  с центром  в точке  и длинами сторон, равными . Здесь  - параметр, называемый размером области локального поиска.

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

  • поставить в соответствие этим агентам два различных пересекающихся участка  (лучших и/или перспективных);

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

В каждый из лучших и перспективных участков посылается по N и по M агентов, соответственно. Координаты этих агентов в указанных участках определяются случайным образом.

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

На основе анализа значений целевой функции, соответствующих всем агентам роя, после некоторого числа итераций находятся новых лучших и m новых перспективных участков. В качестве критерия окончания итераций можно использовать достижение заданного количества итераций T. Можно также заканчивать итерации, если в течение  итераций не удалось увеличить максимальное достигнутое значение целевой функции. Здесь  - параметр останова.

Более сложный вариант метода пчелиного роя рассмотрен, например, в работе [13].

Глава 5. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ РАЗРАБОТАННОГО АЛГОРИТМА ТРАССИРОВКИ.
^ 5.1 Выбор среды разработки и реализации программы

Программная реализация метода пчелиного роя выполнена на языке программирования PHP 5.3, который представляет собой высокоуровневый интерпретируемый язык программирования общего назначения, применяемый для проектирования веб-приложений.

Приложение выполнено в виде подключаемой веб-страницы, способной выполняться на высокопроизводительных серверах, облачных хранилищах, либо на локальном сервере, что позволит в дальнейшем избежать проблем с незаконным использованием, копированием программы целиком, либо отдельных её модулей, путем предоставления программы конечному пользователю по схеме SaaS (Software As A Service).
^ 5.2 Создание улья пчел и описание его характеристик

С помощью функции __construct выполняется первый шаг, т.е. создается основной улей пчел, который является отправным пунктом для пчел-разведчиков и пчел-комивояжеров.































Поля данных totalNumberBees, numberInactive, numberActive, numberScout являются переменными, в которых хранятся общее количество пчел, а также количества неактивных пчел, активных и разведчиков. Поскольку каждая пчела представляет потенциальное решение, то чем больше пчел в улье, тем лучше. Однако с ростом популяции пчел производительность программы уменьшается.

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

Поле данных, maxNumberVisits, хранит пороговое значение, не дающее пчеле слишком долго задерживаться на одном решении. На каждой итерации основного цикла обработки в методе Solve, если пчела не находит соседний источник нектара с более высоким качеством, счетчик numberOfVisits этой пчелы увеличивается на 1. Как только счетчик numberOfVisits в объекте Bee превысит пороговое значение maxNumberVisits, пчела переходит в неактивное состояние.

Далее созданный улей сохраняется в массив bees для последующего использования и обработки.
^ 5.3 Моделирования поведения улья

Основную управляющую функцию, то есть функцию улья несет метод solve, он обрабатывает циклы алгоритма, в нем выбираются и отправляются активные пчелы на перспективные участки с нектаром.




































^ 5.4 Описание логики поведения активных пчел

Поведение активных пчел запрограммировано в методе ProcessActiveBee. Этот метод является сердцевиной алгоритма пчелиных коллоний и самым сложным и разветвленным по своей логике.












































































































Метод ProcessActiveBee принимает единственный параметр, i, который является индексом пчелы в массиве bees. Активная пчела сначала получает смежное решение, относительное ее текущему решению, которое хранится в memoryMatrix, а затем определяет добротность этого смежного решения.

Так же алгоритм инициализирует три локальные переменные, prob, memoryWasUpdated, numberOfVisitsOverLimit.

Переменная prob имеет значение между 0.0 и 1.0 и будет сравниваться со значением поля probMistake, чтобы определить, совершила ли ошибку пчела при оценке смежного решения, т. е. отклонила более эффективное смежное решение или приняла менее эффективное.
Булево значение memoryWasUpdated будет использоваться, чтобы определить, должна активная пчела исполнить виляющий танец для неактивных пчел (если true) или нет (если false). Булево значение numberOfVisitsOverLimit будет сравниваться с полем maxNumberVisits, чтобы выяснить, исчерпала ли пчела конкретный источник нектара, не найдя более эффективного смежного решения. Если да, то ее состояние должно быть переведено из активного в неактивное.

Если текущая пчела находит более эффективное смежное решение, алгоритм определяет, приняла ли она более эффективное решение или совершила ошибку, отклонив более эффективное смежное решение. Аналогично, если текущая пчела не нашла более эффективное смежное решение, алгоритм определяет, совершила ли пчела ошибку, приняв менее эффективное смежное решение, или не ошиблась, отклонив такое решение.
^ 5.5 Имитация танца пчелы в улье

После того как текущая активная пчела принимает или отвергает смежное решение, алгоритм проверяет, не превысил ли счетчик числа визитов пороговое значение maxNumberVisits. Если да, текущая пчела переводится в неактивное состояние, а наугад выбранная неактивная пчела становится активной и обновляется массив indexesOfInactiveBees. Далее алгоритм проверяет, была ли обновлена память этой пчелы. Если да, новое решение проверяется на пригодность в качестве нового глобального лучшего решения, а затем вызывается закрытый вспомогательный метод DoWaggleDance, чтобы имитировать возврат пчелы в улей и передачу информации о новом источнике нектара неактивным пчелам.
^ 5.6 Описание логики поведения пчел – скаутов

Вспомогательный метод ProcessScoutBee, используемый методом Solve, моделирует действие пчелы-разведчика, осуществляющей случайный поиск привлекательных источников нектара.




























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

1   2   3

Похожие:

Курсовая работа по дисциплине «Разработка систем автоматизированного проектирования» iconМетодическое пособие по выполнению лабораторных работ 
Методическое пособие соответствует гос впо направления подготовки дипломированных специалистов 230100 «Информатика и вычислительная...
Курсовая работа по дисциплине «Разработка систем автоматизированного проектирования» iconКурсовая работа тема: «Разработка стратегии предприятия» по дисциплине: «Экономика отрасли»

Курсовая работа по дисциплине «Разработка систем автоматизированного проектирования» iconКурсовая работа по дисциплине «Агрохимия»
Курсовая работа по дисциплине «Агрохимия»: / И. И. Серегина, В. Ф. Волобуева, В. М. Лапушкин, Т. В. Украинская. М.: Изд-во ргау –...
Курсовая работа по дисциплине «Разработка систем автоматизированного проектирования» iconКурсовая работа по дисциплине «Основы технологического проектирования...
Расчет производственной программы, трудоемкости технического воздействия и количества ремонтных рабочих
Курсовая работа по дисциплине «Разработка систем автоматизированного проектирования» iconКурсовая работа по дисциплине: «Администрирование сетей» тема: «Разработка...

Курсовая работа по дисциплине «Разработка систем автоматизированного проектирования» iconАльтернативная энергетика – новое направление развития промышленности, экономики
На данном форуме обсуждаются текущие вопросы по конструированию, технологии изготовления, оборудованию и автоматизации машиностроения...
Курсовая работа по дисциплине «Разработка систем автоматизированного проектирования» iconКурсовая работа по дисциплине «Основы технологического проектирования...
Указанные расчеты выполняются с использованием следующих исходных данных (задание из разделов коммерческой эксплуатации)
Курсовая работа по дисциплине «Разработка систем автоматизированного проектирования» iconКурсовая работа по дисциплине «Основы технологического проектирования...
Указанные расчеты выполняются с использованием следующих исходных данных (задание из разделов коммерческой эксплуатации)
Курсовая работа по дисциплине «Разработка систем автоматизированного проектирования» iconКурсовая работа по дисциплине на тему: «Технологии социальной работы...
Фгбоу впо Пензенский государственный университет Факультет   Кафедра социологии и социальной теории и практики работы социальной...
Курсовая работа по дисциплине «Разработка систем автоматизированного проектирования» iconСистема автоматизированного проектирования
Сапр решает задачи автоматизации работ на стадиях проектирования и подготовки производства. Основная цель создания сапр - повышение...
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2020
контакты
userdocs.ru
Главная страница