Применение общей схемы при решении задачи размещения электронных компонентов на печатной плате

Размещено на http://www.allbest.ru/

1

Министерство образования и науки Российской Федерации

Казанский государственный технический университет им. А.Н. Туполева

Факультет технической кибернетики и информатики

Кафедра информационных технологий проектирования ЭВС

Курсовая работа по дисциплине: «Эволюционное моделирование в системах автоматизированного проектирования электронных средств»

Тема: «Применение общей схемы при решении задачи размещения электронных компонентов на печатной плате»

Работу выполнил: студент группы 4414 Исламов А.А.

Научный руководитель: Доцент каф. ИТПЭВС Воронова В.В.

Казань 2014



Аннотация

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

Abstract

The current stage of scientific and technological revolution is characterized by the growing need for the development of modern electronic means (ES), which are increasingly used in all areas of the economy. The growing complexity of designing ES is caused by an increase in volume of information processed at ever-increasing demand for its quality and reliability, as well as to reduce the complexity of manufacturing, cost and design time. Solve all these issues allows automation of design work, a hook as it allows us to solve automation tasks with the least complexity, minimum cost, in the shortest possible time and receive at the same time reliable, error-free design documentation.



Введение

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

Однако изучение задач размещения началось в 17 веке, когда Ферма сформулировал задачу, известную ныне как задача Вебера: даны три точки на плоскости, требуется найти четвертую точку, такую, что сумма расстояний от нее до трех фиксированных точек минимальна. Задача была решена геометрически Торичелли в 1640 году. Затем в 1750 году Симпсон обобщил задачу в направлении учета произвольных весов связей между объектами. В 1909 году Вебер использовал подобную модель для определения оптимального размещения фабрики при известных точках расположения ресурсов и потребителей продукта.

Итак, проблема размещения каких-либо объектов на определенном пространстве была и остается актуальной и по сей день.

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



1. Теоретическая часть

1.1 Постановка задачи размещения

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

Необходимо найти такое размещение конструктивных элементов на печатной плате, при котором значение выбранного критерия качества F оптимизируется. Существует множество критериев качества F для данной задачи, среди которых необходимо выбрать наиболее подходящий: минимум суммарной взвешенной длины межсоединений, минимум максимальной длины межсоединений, минимум числа пересечений проводников и т.д.

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

Рассмотрим математическую постановку задачи размещения:

Исходные данные:

1) Множество конструктивных элементов Е=(е₁,е₂,…,е_n),

2) Множество связей между КЭ С=(с₁,с₂,…,с_m),

3) Множество установочных позиций S=(s₁,s₂,…,s_k), k і n.

Необходимо:

Найти отображение множества Е на множество S, которое обеспечит оптимальное значение критерия качества F.

1.2 Эволюционное моделирование

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

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

Разберемся в сути эволюционного подхода в общем виде.

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

-Эволюционное программирование. Ориентировано на оптимизацию непрерывных функций без использования рекомбинаций.

-Эволюционная стратегия. Ориентирована на оптимизацию непрерывных функций с использованием рекомбинаций.

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

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



2. Практическая часть

2.1 Генетический алгоритм

Фитнесс-функция Генетические алгоритмы стали особенно популярны благодаря работе Джона Холланда в начале 70-х годов и его книге «Адаптация в естественных и искусственных системах» (1975). Его исследование основывалось на экспериментах с клеточными автоматами, проводившимися Холландом и на его трудах написанных в университете Мичигана. Холланд ввел формализованный подход для предсказывания качества следующего поколения, известный как Теорема схем. Исследования в области генетических алгоритмов оставались в основном теоретическими до середины 80-х годов, когда была, наконец, проведена Первая международная конференция по генетическим алгоритмам в Питтсбурге, Пенсильвания (США). Генетический алгоритм относится к эвристическим алгоритм поиска, используемым для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, аналогичных естественному отбору в природе. Является разновидностью эволюционных вычислений, с помощью которых решаются оптимизационные задачи с использованием методов естественной эволюции, таких как наследование, мутации, отбор и скрещивание. Задача, решаемая с помощью генетического алгоритма, формализуется таким образом, чтобы её решение могло быть закодировано в виде вектора («генотипа») генов, где каждый ген может быть битом, числом или неким другим объектом. В классических реализациях генетического алгоритма предполагается, что генотип имеет фиксированную длину. Однако существуют вариации генетического алгоритма, свободные от этого ограничения. Некоторым, обычно случайным, образом создаётся множество генотипов начальной популяции. Они оцениваются с использованием «функции приспособленности», называемой также «фитнесс - функцией», в результате чего с каждым генотипом ассоциируется определённое значение 9(«приспособленность»), которое определяет насколько хорошо фенотип, им описываемый, решает поставленную задачу. Отбирается множество решений. Из полученного множества решений («поколения») с учётом значения «приспособленности» выбираются решения (обычно лучшие особи имеют большую вероятность быть выбранными), к которым применяются «генетические операторы» (в большинстве случаев «скрещивание» и «мутация»), результатом чего является получение новых решений. Для них также вычисляется значение приспособленности, и затем производится отбор («селекция») лучших решений в следующее поколение. Этот набор действий повторяется итерационно, так моделируется «эволюционный процесс», продолжающийся несколько жизненных циклов («поколений»), пока не будет выполнен критерий остановки алгоритма. Таким критерием может быть: - нахождение глобального, либо субоптимального решения; - исчерпание числа поколений, отпущенных на эволюцию; - исчерпание времени, отпущенного на эволюцию. Отличительной особенностью генетического алгоритма является акцент на использование оператора скрещивания, который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе. Нередко акцентируется и использование в генетическом алгоритме оператора мутаций. Одним из главных понятий в ГА является понятие «функции приспособленности» или «фитнесс-функции». Она показывает насколько хорошо решение, представленное данной особью, удовлетворяет условиям поставленной задачи. В контексте задачи компоновки блоков электронных схем в качестве основного критерия оценки «приспособленности» особи можно использовать критерий минимума количества соединений между узлами, т.е. сумма весов рёбер, соединяющих эти подмножества - стоимость разбиения, была минимальна. 10Фитнесс функция вычисляется по формуле f = 1 F, где F=? i=1 n ? j=1 n U i , j ,i? j Также генетический алгоритм невозможно себе представить без формирования популяций следующего поколения. Оператора, который на основе фитнесс функции отбирает особи в новую популяцию.

Репродукция - процесс, в котором хромосомы копируются согласно их целевой функции. Биологи называют эту функцию fitness. Оператор репродукции, конечно, является искусственной версией натуральной селекции «выживания сильнейших» по Дарвину. Оператор репродукции представляется в алгоритмической форме разлиными способами. Самый простой - создать колесо рулетки, в котором каждая хромосома имеет поле, пропорциональное его целевой функции. В одной генерации колесо рулетки вращается и после останова ее указатель определяет хромосому, выбранную для следующей популяции. Очевидно, но не всегда выполнимо, что хромосома с большой целевой функцией в результате применения оператора репродукции будет выбрана для следующей популяции. Оператор репродукции выбирает хромосомы для оператора кроссинговера. В популяцию P t+1 должны входить более приспособленные к требованиям решаемой задачи особи из популяции P t . Особи, включаемые в популяцию P t+1 , являются непосредственными потомками особей предыдущего поколения P t . Будем считать, что численность популяции n сохраняется от поколения к поколению. Это означает, что ровно n--выживших особей из поколения P t становятся родителями в следующем поколении P t+1 . Одними из возможных схем формирования являются: Общая схема, где в R(t) включаются все особи t-го поколения: родители, потомки, мутанты.

Общая схема. моделирование программа оптимизация

В R(t) включаются все особи t-го поколения: «родители», «потомки», «мутанты», тогда численность репродукционной группы определяется как

N(t)= +N_n(t)+N_м(t)=N_э(t), где

N_э(t) - эффективная численность популяции;

- численность популяции P^t;

N_n(t) - численность потомков;

N_м(t) - численность мутантов, воспроизведенных в новом поколении.

На рис.1 показана модель формирования общей схемы репродукционной группы Родители

Рис.1

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

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

2.2 Генные мутации

В процессе генной мутации в i-ом гене «родительской» хромосомы аллель, находящаяся в j-ом локусе, полностью заменяется на новую и в результате образуется хромосома «мутант». Новая аллель должна принадлежать генофонду того гена, который подвергается мутации, а также должна отличаться от аллельных форм уже имеющихся в хромосомном наборе популяции.

Приведем схему реализации генной мутации:

1. В «родительской» хромосоме случайным образом с вероятностью p =1/n, определяется j-ый ген (), в котором аллель «родительского» гена будет подвержена мутации.

2. Из генофонда Г(j) j-ого гена исключаются все аллели хромосомного набора популяции , находящиеся в j-ом локусе: Г(j) := Г(j)\{,…, }

3. Если окажется, что Г(j):= , то Г(j) := {,…, }\{}, .

4. Случайным образом с вероятностью P=1/ |Г(j)| из множества аллелей генофонда Г(j) выбирается альтернативная аллель .

5. В j-ом локусе «родительской» хромосомы аллель заменяется на альтернативную аллель .

6. Генотип мутанта сформирован.

2.3 Проблема получения недопустимого и незаконного решений. Способы ее устранения

а) В случае появления недопустимых решений в ходе работы оператора генной мутации, когда аллели генов в хромосоме повторяются, выбираем аллель случайным образом с вероятностью p = 1/ из множества аллелей генофонда Г(j), еще не задействованных в данной хромосоме.

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

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

1) Пусть хромосома имеет длину, равную 9 генам, а аллели генов могут принимать значения из генофонда Г(j) = {0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001}:

2) Пусть случайным образом, с помощью генератора случайных чисел для генной мутации был выбран 1-ый ген хромосомы:

3) Заметим, что в результате генной мутации в хромосоме появились 2 гена (ген1 и ген5) с одинаковыми аллелями, равными 1000:

4) Присвоим гену5 еще не использованное в данной хромосоме значение 0111 из генофонда Г(j) и получим окончательное решение:

б) В случае появления незаконных решений в ходе работы оператора генной мутации, когда в результате мутации образуются аллели, не принадлежащие генофонду Г(j), можно случайным образом, с вероятностью p = 1/ из множества аллелей генофонда Г(j) выбирать аллель из оставшихся еще не использованных в данной хромосоме.

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

1) Пусть хромосома имеет длину, равную 9 генам, а аллели генов могут принимать значения из генофонда Г(j) = {0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001}:

2) Пусть случайным образом, с помощью генератора случайных чисел для генной мутации был выбран 3-ий ген хромосомы с аллелью 0011:

3) Заметим, что в результате генной мутации в хромосоме появляется ген, не принадлежащий генофонду Г(j), с аллелью, равной 1100.

4) Отнимем от полученной аллели в ходе генной мутации 1000 и получим аллель 0100, которая входит в генофонд Г(j):

5) Теперь в хромосоме появились недопустимые решения: аллели гена3 и гена 4 совпадают. Необходимо для гена 4 из генофонда Г(j) такую аллель, которая еще не использовалась в нашей хромосоме, т. е. аллель 0011. Запишем результат:

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

Для начала закодируем решение:

пусть G = {g_1, g_2, … , g_n} - множество установочных позиций на печатной плате (печатная плата размером 3х3) и E = {e_1, e_2, … , e_n } - множество конструктивных элементов, которые необходимо разместить на данной печатной плате. Причем, |G| = |E| = n = 9. Используем двоичное кодирование хромосомы, тогда наш ген будет иметь длину в 4 бита, а хромосома - 36 бит. Порядковый номер гена будет соответствовать номеру установочной позиции печатной платы, а аллель будет соответствовать номеру устанавливаемого элемента. Тогда наше закодированная хромосома будет выглядеть так:

Приведем общий алгоритм решения задачи размещения с использованием оператора мутации:

1. Определим генофонд Г(j), включим в него все возможные аллели хромосомного набора нашей популяции: Г(j) = {0001; 0010; 0011; 0100; 0101; 0110; 0111; 1000; 1001}

2. Сформируем начальную популяцию из N = 5 особей случайным образом, где длина каждой хромосомы равна 9 генам, т.е. 36 битам:



3. Осуществим генные мутации, выбрав случайным образом хромосомы нашей популяции и ген в каждой такой хромосоме. Пусть было случайно выбрано четыре хромосомы (1, 2, 4, 5) из нашей популяции, в которых будет происходить генная мутация, и в каждой этой хромосоме случайным образом был выбран ген (1 - ген 9, 2 - ген 4, 4 - ген 1, 5 - ген 7):

4. В случае появления незаконных решений, когда какой-либо ген хромосомы не принадлежит генофонду Г(j), либо в случае появления недопустимых решений, когда в результате мутации образуются одинаковые аллели в одной хромосоме, случайным образом с вероятностью p = 1/| Г(j) | из множества аллелей генофонда Г(j) выбираем аллель, еще не использованную в данной хромосоме.

5. Поскольку в качестве критерия оптимизации поставленной задачи размещения мы выбрали минимизацию суммарной длины связей конструктивных элементов F, обозначим фитнесс-функцию: f = 1/F.

6. Отбираем хромосому-мутанта с наилучшим значением фитнесс-функции. Это и будет являться решением задачи размещения конструктивных модулей на печатной плате.

7. Конец алгоритма.

2.4 Формирование популяций следующего поколения

Репродукция - процесс, в котором хромосомы копируются согласно их целевой функции. Биологи называют эту функцию fitness. Оператор репродукции, конечно, является искусственной версией натуральной селекции «выживания сильнейших» по Дарвину. Оператор репродукции представляется в алгоритмической форме разлиными способами. Самый простой - создать колесо рулетки, в котором каждая хромосома имеет поле, пропорциональное его целевой функции. В одной генерации колесо рулетки вращается и после останова ее указатель определяет хромосому, выбранную для следующей популяции. Очевидно, но не всегда выполнимо, что хромосома с большой целевой функцией в результате применения оператора репродукции будет выбрана для следующей популяции. Оператор репродукции выбирает хромосомы для оператора кроссинговера. В популяцию P t+1 должны входить более приспособленные к требованиям решаемой задачи особи из популяции P t . Особи, включаемые в популяцию P t+1 , являются непосредственными потомками особей предыдущего поколения P t . Будем считать, что численность популяции ? сохраняется от поколения к поколению. Это означает, что ровно ? «выживших» особей из поколения P t становятся «родителями» в следующем поколении P t+1 . Одними из возможных схем формирования являются: Общая схема, где в R(t) включаются все особи t-го поколения: «родители», «потомки», «мутанты»

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

2.5 Блок схема программы

Структурная схема работы общей схемы представлена на рисунке 2.

Рис.2. «Структурная схема работы общей схемы»

2.6 Описание Массивов

Опишем основные массивы, использованные в создании нашей программы:

int[,] Pop - двумерный массив, содержащий в себе сгенерированную популяцию хромосом;

int[,] Mrow - двумерный массив, содержащий в себе матрицу расстояний.

Int[,] Msm - двумерный массив, содержащий в себе матрицу смежностей.

Int[,] Par - двумерный массив, содержащий в себе родительские хромосомы для следующей популяции

int[,] Rep - двумерный массив, содержащий в себе репродукционную группу, из которой будут выбраны N особей, для скрещивания и мутации в следующей популяции.

2.7 Инструкция пользователя

Данное приложение написано на языке высокого уровня С# и реализовано в среде разработки Visual Studio 2010 Ultimate. Необходимая минимальная конфигурация компьютера для нормального функционирования программы: ОС Microsoft Windows XP/Vista/7/8, процессор Pentium III 336 МГц, 512 МБ оперативной памяти, видеокарта 64 МБ.

Открываем приложение «Размещение генетическим алгоритмом» и видим перед собой следующее окно.

Рис.3

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

Рис.4

После этого мы можем нажать кнопку «Обозначить диагональ», и значениям по главной диагонали матрицы присвоится 0.

Рис.5

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

Рис.6

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

Рис.7

Следующим шагом, в выделенном окошке, следует указать, сколько родительских хромосом нам нужно в первом поколении и нажать кнопку «Ввод».

Рис.8

После нажатия кнопки «Генерировать популяции» программа выведет случайно сгенерированные родительские хромосомы.

Рис.9

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

Рис.10

Далее, нажав кнопку «Ответ», мы можем увидеть полученную схему размещения элементов в монтажной зоне.

Рис.11



Заключение

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

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

Решение мы получили посредством разработки и работы в программе, написанной на языке C#. Листинг программы приведен в Приложении.



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

1. В.В. Воронова, «Методические указания для курсового проектирования по дисциплине «Автоматизация конструкторско-технологического проектирования электронно-вычислительных средств»» Казань, 2001 г. - 96 c.

2. Курейчик В.М., Курейчик В.В. Модифицированные генетические операторы: Известия ЮФУ. Технические науки. - 2009. - № 12 (101). - 7-15 с.

3. Портал искусственного интеллекта http://neuronus.com/em.html.

4. Visual Studio Magazine: http://visualstudiomagazine.com/articles/2014/02/01/evolutionary-optimization-using-c.aspx.

5. A block-based evolutionary algorithm for flow-shop scheduling problem: http://www.sciencedirect.com/science/article/pii/S1568494613002640.

6. MSDN Magazine: Evolutionary Optimization Algorithms http://msdn.microsoft.com/en-us/magazine/jj133825.aspx.



Приложение

Листинг программы

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

using System.Windows.Forms;

namespace GenAlg

{

public partial class Form1 : Form

{

double Max;

int X, N, i, j=0,k=0, s;

int[,] Mrow = new int[9, 9] { { 0, 1, 2, 1, 2, 3, 2, 3, 4 }, { 1, 0, 1, 2, 1, 2, 3, 2, 3 }, { 2, 1, 0, 3, 2, 1, 4, 3, 2 }, { 1, 2, 3, 0, 1, 2, 1, 2, 3 }, { 2, 1, 2, 1, 0, 1, 2, 1, 2 }, { 3, 2, 1, 2, 1, 0, 3, 2, 1 }, { 2, 3, 4, 1, 2, 3, 0, 1, 2 }, { 3, 2, 3, 2, 1, 2, 1, 0, 1 }, { 4, 3, 2, 3, 2, 1, 2, 1, 0 } };

int[,] Msm = new int[9, 9];

int[] Par1=new int[9];

int[] Par2 = new int[9];

int[] Par3 = new int[9];

int[] Par4 = new int[9];

string A;

public Form1()

{

InitializeComponent();

}

private void textBox2_TextChanged(object sender, EventArgs e)

{

N = Convert.ToInt32(textBox2.Text);

}

private void textBox1_TextChanged(object sender, EventArgs e)

{

}

private void label1_Click(object sender, EventArgs e)

{

}

private void label2_Click(object sender, EventArgs e)

{

}

private void button1_Click(object sender, EventArgs e)

{

for (i = 0; i < N; i++)

for (j = i + 2; j <= N; j++)

{

if (dataGridView1.Rows[i].Cells[j].Value == null)

dataGridView1.Rows[i + (j - i - 1)].Cells[j - (j - i - 1)].Value = dataGridView1.Rows[i].Cells[j].Value = 0;

else

dataGridView1.Rows[i + (j - i - 1)].Cells[j - (j - i - 1)].Value = dataGridView1.Rows[i].Cells[j].Value;

}

for (i = 0; i < N; i++)

for (j = 0; j < N; j++)

{

k = j + 1;

Msm[i, j] = Convert.ToInt32(dataGridView1.Rows[i].Cells[k].Value);

}

}

private void dataGridView1_CellContentClick(object sender, DataGridViewCellEventArgs e)

{

}

private void button2_Click(object sender, EventArgs e)

{

try

{

if (N <= 2)

throw new Exception("Число вершин должно быть строго больше 2");

if (N > 9)

throw new Exception("Число вершин должно быть строго меньше 1001");

for (int i = 0; i < N; i++)

{

if(i==0)

dataGridView1.Columns.Add((i + 1).ToString(), "№");

dataGridView1.Columns.Add((i + 1).ToString(), "e" + (i + 1).ToString());

dataGridView1.Rows.Add(new DataGridViewRow().HeaderCell.Value = "e" + (i + 1).ToString());

}

}

catch (Exception ex)

{

MessageBox.Show(ex.Message);

}

}

private void button3_Click(object sender, EventArgs e)

{

for (i = 0; i < N; i++)

{

j++;

dataGridView1.Rows[i].Cells[j].Value = 0;

}

}

private void textBox1_TextChanged_1(object sender, EventArgs e)

{

}

private void button4_Click(object sender, EventArgs e)

{

textBox1.Text = " | 1 2 3 4 5 6 7 8 9 ";

textBox1.Text = textBox1.Text + Environment.NewLine + "--------------------------------------------";

textBox1.Text = textBox1.Text + Environment.NewLine + "1| 0 1 2 1 2 3 2 3 4 ";

textBox1.Text = textBox1.Text + Environment.NewLine + "2| 1 0 1 2 1 2 3 2 3 ";

textBox1.Text = textBox1.Text + Environment.NewLine + "3| 2 1 0 3 2 1 4 3 2 ";

textBox1.Text = textBox1.Text + Environment.NewLine + "4| 1 2 3 0 1 2 1 2 3 ";

textBox1.Text = textBox1.Text + Environment.NewLine + "5| 2 1 2 1 0 1 2 1 2 ";

textBox1.Text = textBox1.Text + Environment.NewLine + "6| 3 2 1 2 1 0 3 2 1 ";

textBox1.Text = textBox1.Text + Environment.NewLine + "7| 2 3 4 1 2 3 0 1 2 ";

textBox1.Text = textBox1.Text + Environment.NewLine + "8| 3 2 3 2 1 2 1 0 1 ";

textBox1.Text = textBox1.Text + Environment.NewLine + "9| 4 3 2 3 2 1 2 1 0 ";

}

private void textBox3_TextChanged(object sender, EventArgs e)

{

}

private void textBox4_TextChanged(object sender, EventArgs e)

{

}

private void button5_Click(object sender, EventArgs e)

{

X = Convert.ToInt32(textBox4.Text);

}

private void label3_Click(object sender, EventArgs e)

{

}

private void button6_Click(object sender, EventArgs e)

{

int q, w=0;

int g;

int[,] Pop = new int[9, X];

Random realRnd = new Random();

for (g = 0; g < X; g++)

{

textBox5.Text = textBox5.Text + Environment.NewLine + "Родитель № " + Convert.ToString(g + 1) + " ";

for (i = 0; i < N; i++)

{

w = 0;

q = realRnd.Next(1, N);

for (j = 0; j < N; j++)

{

if (q == Par1[j])

w++;

}

if (w == 0)

{

Par1[i] = q;

}

else

i--;

}

textBox5.Text = textBox5.Text + Environment.NewLine;

j++;

for (i = 0; i < N; i++)

{

textBox5.Text = textBox5.Text + Convert.ToString(Par1[i]);

Pop[i, g] = Par1[i];

}

}

for (i = 0; i < 4; i++)

{

public static void One_way_genetic_evolution (ref ПП FPGA, ref Soed link)

{

if (link.Length != 0)

{

link.output_with_bs();

Genotype routing = new Genotype(FPGA);

Pop check = new Po(FPGA.cb, routing, link.Bs_start, link.Bs_end);

check.ConsolePopOutput();

}

}

public static void RandomicGeneticEvolution(ref ПП FPGA, ref Soed link)

{

Genotype first = new Genotype(3, FPGA.cb);

Pop monsters = new Pop(FPGA.cb, first);

for (int i = 0; i <(FPGA.cb*2); i++)

{

monsters.Add_chromosome(Evolution(ref first,FPGA.cb));

}

Evolution(ref monsters, ref first);

Console.WriteLine("\n Конечный вид популяции \n");

monsters.ConsolePopOutput();

}

static Chromosome Evolution(ref Genotype code, int size_of_Pops)

{

Pop pop = new Pop(size_of_Pops, code);

for (int i = 0; i < 100; i++)

{

pop.Assortative_mating_positive(code);

pop.Selection();

}

return pop.The_Max;

}

static Chromosome Evolution(ref Pop best_of_best,ref Genotype code)

{

for (int i = 0; i < 100; i++)

{

best_of_best.Assortative_mating_positive(code);

best_of_best.Selection();

}

return best_of_best.The_best;

}

class Genotype

{

int length_of_gen;

int length_of_chromosome;

static ПП fpga;

public Genotype(int gen, int chromosoma)

{

length_of_chromosome = chromosoma;

length_of_gen = gen;

}

public Genotype(ПП fpg)

{

fpga = fpg;

length_of_chromosome = fpg.cb;

length_of_gen = 3;

}

public static int Fitness_routing(int start_rout, bool[,] cromos)

{

int length = 0;

bool finished = false;

int[] way = new int[0];

int i = start_rout;

int next=0;

while ((finished == false)&&(way.Length<fpga.cb))

{

int[] nw = way;

way = new int[nw.Length + 1];

nw.CopyTo(way, 0);

if ((cromos[i, 0] == false) && (cromos[i, 1] == false) && (cromos[i, 2] == false))

{

way[nw.Length] = i;

next = fpga.GetIndexOfVertical(i, true);

if (way.Contains(next)==true)

{

finished=true;

nw = way;

way = new int[nw.Length + 1];

nw.CopyTo(way, 0);

way[nw.Length]=next;

length = 0;

}

}

if ((cromos[i, 0] == false) && (cromos[i, 1] == false) && (cromos[i, 2] == true))

{

way[nw.Length] = i;

next = i + 1;

if (way.Contains(next)==true)

{

finished=true;

nw = way;

way = new int[nw.Length + 1];

nw.CopyTo(way, 0);

way[nw.Length]=next;

length = 0;

}

}

if ((cromos[i, 0] == false) && (cromos[i, 1] == true) && (cromos[i, 2] == false))

{

way[nw.Length] = i;

next = fpga.GetIndexOfVertical(i, false);

if (way.Contains(next)==true)

{

finished=true;

nw = way;

way = new int[nw.Length + 1];

nw.CopyTo(way, 0);

way[nw.Length]=next;

length = 0;

}

}

if ((cromos[i, 0] == false) && (cromos[i, 1] == true) && (cromos[i, 2] == true))

{

way[nw.Length] = i;

next = i - 1;

if (way.Contains(next)==true)

{

finished=true;

nw = way;

way = new int[nw.Length + 1];

nw.CopyTo(way, 0);

way[nw.Length]=next;

length = 0;

}

}

if ((cromos[i, 0] == true) && (cromos[i, 1] == false) && (cromos[i, 2] == false))

{

way[nw.Length] = i;

length = 0;

finished = true;

}

if ((cromos[i, 0] == true) && (cromos[i, 1] == true) && (cromos[i, 2] == true))

{

way[nw.Length] = i;

length = way.Length;

finished = true;

}

i = next;

}

return length;

}

public static int Fitness_simple(bool [,] cromos)

{

int f = 0;

for (int i = 0; i < cromos.GetLength(0); i++)

{

if (cromos[ i, 0] == false) f++;

}

return f;

}

public static bool[] GetGene(int number_of_gen)

{

bool[] gene={false,false,false};

int a=Pop.GetRandInt(0,5);

int[] str = new int[fpga.cb];

for (int i = 0; i < str.Length; i++)

{

str[i] = fpga.Текущая_матрица_смежности[number_of_gen, i];

}

if (a == 0)

{

if (cb.north == true)

{

if (str[fpga.GetIndexOfVertical(number_of_gen, true)] != 0)

{

bool[] ne = { false, false, false };

return ne;

}

}

a++;

}

if (a == 1)

{

if (cb.east == true)

{

if (str[number_of_gen + 1] != 0)

{

bool[] ne = { false, false, true };

return ne;

}

}

a++;

}

if (a == 2)

{

if (cb.south == true)

{

if (str[fpga.GetIndexOfVertical(number_of_gen, false)] != 0)

{

bool[] ne = { false, true, false };

return ne;

}

}

a++;

}

if (a == 3)

{

if (cb.west == true)

{

if (str[number_of_gen - 1] != 0)

{

bool[] ne = { false,true,true };

return ne;

}

}

a++;

}

if (a == 4)

{

gene[0] = true;

}

return gene;

}

}

}

}

private void textBox5_TextChanged(object sender, EventArgs e)

{

}

}

}

public bool ReadFromFileGreed(string way)

{

try

{

StreamReader stream = new StreamReader(way);

matrixDimension = Convert.ToInt32(stream.ReadLine());

int[] myArray = new int[matrixDimension];

string[] tempStringArray;

string separate = " ";

string s;

for (int i = 0; i < this.matrixDimension; i++)

{

matrixGridView.Columns.Add((i + 1).ToString(), "e" + i.ToString());

matrixGridView.Rows.Add(new DataGridViewRow().HeaderCell.Value = "e" + i.ToString());

}

for (int j = 0; j < matrixDimension; j++)

{

s = stream.ReadLine();

tempStringArray = s.Split(separate.ToCharArray());

for (int i = 0; i < matrixDimension; i++)

matrixGridView.Rows[j].Cells[i + 1].Value = Int32.Parse(tempStringArray[i]);

}

numberOfVertexTextBox.Enabled = false;

numberOfVertexTextBox.Text = matrixDimension.ToString();

BlockLowerDiagonal();

stream.Close();

return true;

}

catch (Exception exp)

{

return false;

}

}

LayoutGeneticSolution solution;

int matrixDimension;

private void enterNumberOfVertexButton_Click(object sender, EventArgs e)

{

try

{

matrixDimension = Convert.ToInt32(numberOfVertexTextBox.Text);

if (matrixDimension <= 2)

throw new Exception("Число вершин должно быть строго больше 2");

31 if (matrixDimension > 1000)

throw new Exception("Число вершин должно быть строго меньше 1001");

CreateMatrixGreed();

openButton.Enabled = false;

mirrorButton.Enabled = true;

solveButton.Enabled = true;

numberOfVertexTextBox.Enabled = false;

matrixGridView.AutoResizeColumns();

}

catch (Exception ex)

{

MessageBox.Show(ex.Message);

}

}

private void mirrorButton_Click(object sender, EventArgs e)

{

Mirror();

}

private void InitMatrixGreed()

{

matrixGridView.Columns.Add("0", "№");

matrixGridView.Columns[0].ReadOnly = true;

DataGridViewCellStyle style = new DataGridViewCellStyle();

style.BackColor = Color.FromArgb(((int)(((byte)(236)))), ((int)(((byte)(233)))), ((int)(((byte)(216)))));

matrixGridView.Columns[0].DefaultCellStyle = style;

}

private void CreateMatrixGreed()

{

for (int i = 0; i < matrixDimension; i++)

{

matrixGridView.Columns.Add((i + 1).ToString(), "e" + i.ToString());

matrixGridView.Rows.Add(new DataGridViewRow().HeaderCell.Value = "e" + i.ToString());

}

BlockLowerDiagonal();

}

private void ResetMatrixGreed()

{

}

private void InitPopulationGreed()

{

populationGridView.Columns.Add("0", "№\\Аллель№");

//populationGridView.Columns[0].ReadOnly = true;

DataGridViewCellStyle style = new DataGridViewCellStyle();

style.BackColor = Color.FromArgb(((int)(((byte)(236)))), ((int)(((byte)(233)))), ((int)(((byte)(216)))));

populationGridView.Columns[0].DefaultCellStyle = style;

}

private void CreatePopulationGreed()

{

}

private void ResetPopulationGreed()

{

}

private void InitSelectionGreed()

32 {

selectionGridView.Columns.Add("0", "№\\Аллель№");

//selectionGridView.Columns[0].ReadOnly = true;

DataGridViewCellStyle style = new DataGridViewCellStyle();

style.BackColor = Color.FromArgb(((int)(((byte)(236)))), ((int)(((byte)(233)))), ((int)(((byte)(216)))));

selectionGridView.Columns[0].DefaultCellStyle = style;

}

private void CreateSelectionGreed()

{

}

private void ResetSelectionGreed()

{

}

private void BlockLowerDiagonal()

{

DataGridViewCellStyle style = new DataGridViewCellStyle();

for (int j = 0; j < matrixDimension; j++)

for (int i = 0; i < matrixDimension; i++)

{

if (i == j)

{

matrixGridView.Rows[j].Cells[i + 1].ReadOnly = true;

matrixGridView.Rows[j].Cells[i + 1].Value = 0;

style.BackColor = Color.FromArgb(((int)(((byte)(236)))), ((int)(((byte)(233)))), ((int)(((byte)(216)))));

matrixGridView.Rows[j].Cells[i + 1].Style = style;

}

if (i < j)

{

matrixGridView.Rows[j].Cells[i + 1].ReadOnly = true;

style.BackColor = Color.GhostWhite;

matrixGridView.Rows[j].Cells[i + 1].Style = style;

}

}

}

private void Mirror()

{

for (int j = 0; j < matrixDimension; j++)

for (int i = 0; i < matrixDimension; i++)

matrixGridView.Rows[i].Cells[j + 1].Value = matrixGridView.Rows[j].Cells[i + 1].Value;

}

private void EmptyCellsToZero()

{

for (int j = 0; j < matrixDimension; j++)

for (int i = 0; i < matrixDimension; i++)

if (matrixGridView.Rows[j].Cells[i + 1].Value == null)

matrixGridView.Rows[j].Cells[i + 1].Value = 0;

}

private void CheckGreed()

{

for (int j = 0; j < matrixDimension; j++)

for (int i = 0; i < matrixDimension; i++)

if (Convert.ToInt32(matrixGridView.Rows[j].Cells[i + 1].Value) < 0 &&

Convert.ToInt32(matrixGridView.Rows[j].Cells[i + 1].Value) > 1000)

throw new Exception("Значения ячеек должны быть от 0 до 1000");

}

33 private void PSBButton_Click(object sender, EventArgs e)

{

}

private void ProgramInfoButton_Click(object sender, EventArgs e)

{

MessageBox.Show("Мубаракзянов Нияз. 4314. 2013-2014.");

}

private void generateButton_Click(object sender, EventArgs e)

{

solution.ReadFromGreed(matrixGridView);

solution.InitAndCreatePopulation(4, 25, 5);

solution.FillPopulationToGreed(populationGridView);

populationGridView.AutoResizeColumns(DataGridViewAutoSizeColumnsMode.AllCells);

}

private void selectionButton_Click(object sender, EventArgs e)

{

solution.FillSelectedPopulationToGreed(selectionGridView);

selectionGridView.AutoResizeColumns(DataGridViewAutoSizeColumnsMode.AllCells);

}

}

}

Размещено на Allbest.ru

...