Разработка подсистемы САПР, по размещению конструктивных элементов на печатной плате на основе муравьиного алгоритма

1. Разработка подсистемы САПР по размещению конструктивных элементов на печатной плате на основе муравьиного алгоритма

Казанский национальный исследовательский технический университет
им. А.Н. Туполева
Разработка подсистемы САПР по
размещению конструктивных
элементов на печатной плате на
основе муравьиного алгоритма
Автор: Руденко Андрей
Руководитель: Богула Н.Ю.
Казань 2015

2. Цели и задачи

Целью данной работы является:
• Разработка подсистемы САПР по решению задачи размещения
конструктивных элементов на печатной плате на основе муравьиного
алгоритма.
Задачами данной работы являются:
• Анализ производственно-хозяйственной деятельности по проектированию
печатных плат;
• Постановка задачи размещения конструктивных элементов на монтажном
пространстве;
• Разработка алгоритмов для решения задачи размещения конструктивных
элементов на монтажном пространстве;
• Создание информационного обеспечения подсистемы САПР по
размещению конструктивных элементов на монтажном пространстве;
• Создание программного обеспечения подсистемы САПР по размещению
конструктивных элементов на монтажном пространстве.
• Исследование эффективности алгоритмов для решения задачи
размещения

3. Диаграмма IDEF0 A-0

4. Диаграмма IDEF0 A0

5. Диаграмма IDEF0 A1

6. Диаграмма IDEF0 A2

7. Постановка задачи

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

8. Постановка задачи

• Минимум суммарной взвешенной длины соединений
- расстояние между i-тым и j-тым элементами, с ij -количество
связей между i-тым и j-тым элементами.
Ограничения: невыход элементов за пределы монтажного
пространства и ограничение на непересекаемость размещаемых
элементов на коммутационном пространстве

9. Последовательный алгоритм решения задачи

10. Муравьиный алгоритм решения задачи

11. Приме муравьиного алгоритма

(1),
где - уровень феромона,
- вес ребра

12. Приме муравьиного алгоритма

13. Муравьиный алгоритм решения задачи

Кодированное решение
Декодированное решение
5
1
2
4
3

14. Логическая модель базы данных

15. Экранная форма программы

16. График исследования эффективности алгоритма

Зависимость качества решения от количества итераций
110
100
100.23
100.23
100.23
90.45
90
Качество решения
80.2
80
80.2
80.2
70.28
70
70.28
70.28
90
100
60
50
40
10
20
30
40
50
60
Количество итераций
70
80

17. График исследования эффективности алгоритма

Зависимость качества решения от размера популяции
110
100
100.48
100.48
100.48
Качество решения
90.2
90
80.28
80
70.48
70
80.28
70.48
70.48
70.48
90
100
60
50
10
20
30
40
50
60
Размер популяции
70
80

18. Сравнение эффективности последовательного и муравьиного алгоритмов

2000
1800
1600
1400
1200
1000
Качество решения
800
Муравьиный
Последовательный
600
400
200
0
Размерность

19. Основные выводы исследований

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

20. Основные выводы по работе

В ходе проделанной работы:
1) Была изучена производственно-хозяйственная
деятельности предприятия или организации;
2) Была поставлена математическая модель задачи;
3) Был разработан бионический алгоритма для решения
задачи размещения конструктивных элементов на печатной
плате;
4) Было создано информационное обеспечение
подсистемы САПР по размещению конструктивных
элементов на печатной плате;
5) Было создано программное обеспечение подсистемы
САПР по размещению конструктивных элементов на
печатной плате.

21. Спасибо за внимание!