Разработка программных средств трассировки печатных соединений

Графическая решеткаРисунок 11. Графическая решетка.Разработка алгоритмов трассировки печатных соединенийНиже приводится базовый муравьиный алгоритм оптимизации, в котором воплощены основные идеи предыдущего раздела.Инициализация параметров алгоритма α, β, е, Ϙ, τ0.m=n (количество муравьев равно количеству городов)For i=1 to n For i=1 to n (для каждого ребра)If i<>jղ(i,j)=1/D(i,j)(видимость)τ(i,j)=τ_0(феромон)Else t(i,j)=0EndEndEndFor k=1 to mРазместить муравья k в случайно избранный город.EndИзбрать условно самый короткий маршрут + и измерить его длину L+(Главная программа)For t=1 〖to〗_max(количество итераций алгоритма)For k=1 to m(для каждого муравья)Построить маршрут Tk (t) по правилу (1) и вычислить его длину Lk(t).EndIf «Лучшее решение найдено» Обновить T+ и L+EndFor i=1 to nFor j=1 to m (для каждого ребра)Обновить следы феромона по правилу (3).EndEndEndВывести самый короткий маршрут T+и его длину L+.Глава 33.1. Разработка программного обеспечения для трассировки печатных соединений электронных средств.Разработка программного продукта/* Муравьиный алгоритм для решения задачи */#include #include #include #include using namespace std;#define N_MIN3// минимальное количество вершин#define N_MAX30// максимальное количество вершин#define ALPHA1// вес фермента#define BETTA3// коэффициент эвристики#define T_MAX100// время жизни колонии#define M20// количество муравьев в колонии#define Q100// количество#define RHO0.5// коэффициент испарения феромона// структура ПУТЬ (длинна, массив вершин, количество вершин)struct WAY_TYPE {int itabu;int length;int *tabu;};// вероятность перехода муравья ant в вершину todouble probability (int to, WAY_TYPE ant, double **pheromone, double **distance, int vertex) {// если вершина уже посещена, возвращаем 0for (int i=0; i= p_max) {p_max = p;j_max = j;}}}ants[k].length += distance0[ants[k].tabu[ants[k].itabu-1]][j_max];ants[k].tabu[ants[k].itabu++] = j_max;} while (ants[k].tabu[ants[k].itabu-1] != finish);// оставляем феромон на пути муравьяfor (int i=0; i N_MAX) {cout << "Введите количество вершин [" << N_MIN << ", " << N_MAX << "]: "; cin >> N;}cout << "Введите матрицу расстояний" << endl;D = (double **) malloc (sizeof (double *) * N);for (int i=0; i> D[i][j];}// инициализация начальной и конечной точекwhile (A < 1 || A > N) {cout << "Введите начальную вершину от 1 до " << N << ": "; cin >> A;}while (B < 1 || B > N || B == A) {cout << "Введите конечную вершину от 1 до " << N << " исключая " << A << ": "; cin >> B;}// запускаем алгоритмWAY_TYPE way = AntColonyOptimization (D, N, --A, --B);// выводим результатcout << "Длинна пути: " << way.length << endl;cout << "Путь: " << ++way.tabu[0];for (int i=1; i " << ++way.tabu[i];return 0;}Анализ полученных алгоритмов трассировки и их сложностиАнализ полученных алгоритмов трассировки представлен на рисунке 12.Рисунок 12. Анализ алгоритмов трассировки.Для сравнения, автоматическая трассировка этой же платы была выполнена впрограммеP-CAD.Сравнительныерезультатыработыприведенывтаблице1.Таблица1–результатыавтоматическойтрассировкиНаименованиеДлинатрасс,ммВремяработы,сP-CAD165423МА154272По результатам работы программ видно, что, хотя реализованный алгоритмсильно проигрывает во времени работы, он имеет незначительное преимущество вдлинетрасс.Тестирование разработанных программных средств и анализ полученных результатов На рисунке 13 представлен скриншот запуска программы.Рисунок 13. Запуск программы на выполнение.На рисунке 14 представлен результат исследований по полученным данным .Рисунок 14. Зависимость качества решения от количества итераций.ЗаключениеРезультаты показывают, что муравьиный алгоритм является одним из наиболее перспективных способов поиска решений, когда пространство поиска превышает определенные пределы. А в некоторых случаях он является единственным вариантом. Хотя результаты реализованного алгоритма не очень впечатляют, он все же пригоден для использования в отслеживании печатных плат. Из проведенных экспериментов можно сделать следующие выводы1. Увеличение числа итераций и агентов приводит к повышению эффективности бионического алгоритма, но результаты не достигают оптимального решения.2. Муравьиный алгоритм редко показывает результат оптимального решения, поскольку он основан на вероятностной теории. Классический муравьиный алгоритм в задаче трассировки печатных ссылок требует введения эвристики, которая модифицирует алгоритм.Список литературы1. Курейчик, В.М. Искусственный интеллект в САПР: Текст лекций / В.М. Курейчик, Б.К. Лебедев. – Таганрог: Изд-во ТРТИ, 1989. – 48 с.2. Курейчик, В.М. Проблемы эволюционной адаптации в САПР / В.М. Курейчик, Б.К. Лебедев, А.В. Лях. – Новинтех, №3, 1991.3. Лебедев, Б.К. Методы поисковой адаптации на основе механизмов генетики, самообучения и самоорганизации / Б.К, Лебедев. – Программные продукты и системы, №1, 2002 г. – С. 16-20.4. Средства и технологии проектирования и производства электронных устройств // EDA Express. - 2000.- № 1. - С. 16-23. 5. Хигстон Д., Логхид Ф., Ирвин Р. Новый топологический автотрассировщик // Chip News. - 2002. - № 2. - C. 60-64. 6. Сухарев А.В., Золотов А.И. Модели и процедуры оптимизации в автоматизации проектирования. Программный комплекс FreeStyle Router: Учеб. пособие. - СПб.: СЗТУ, 2001. - 165 с.