ЕФЕКТИВНІСТЬ СИНТЕЗУ ЗВОРОТНИХ МЕРЕЖ З ДОПОМОГОЮ МУРАШИНОГО АЛГОРИТМУ - Наукові конференції
Головна
UA RU EN

Вас вітає Інтернет конференція!

Вітаємо на нашому сайті

Рік заснування видання - 2011

ЕФЕКТИВНІСТЬ СИНТЕЗУ ЗВОРОТНИХ МЕРЕЖ З ДОПОМОГОЮ МУРАШИНОГО АЛГОРИТМУ

02.05.2023 14:17

[1. Інформаційні системи і технології]

Автор: Палагута Михайло Ілліч, студент, Чернівецький національний університет імені Юрія Федьковича, м. Чернівці


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

Мурашиний алгоритм – це евристичний метод пошуку оптимального шляху, який був запропонований на основі спостережень за соціальними взаємодіями мурах при пошуку їжі [1]. В даному підході створюється група віртуальних мурах, які на основі видимості намагаються знайти шлях від мурашника до джерела їжі. Пройшовши шлях до їжі, мурахи повертаються тією ж дорогою, залишаючи по собі феромони, кількість яких залежить від загальної довжини пройденого ними шляху. Таким чином, на наступних ітераціях пошуку мурахи надають перевагу шляхам, які містять більше феромону, а отже, з більшою ймовірністю приведуть до їжі.

Базисним елементом для побудови зворотних мереж було обрано вентиль Тоффолі, який часто використовують при синтезі схем [2,3]. Вентиль Тоффолі – це універсальний зворотний гейт, що виконує перетворення CCNOT (двічі контрольоване НЕ), тобто перетворює значення цільового біта на протилежне, якщо всі біти контролю позитивні. Приклад синтезованої схеми наведено на рис 1.

Задля зручності комп’ютерного моделювання, таблиця істинності синтезованого пристрою представляється як вектор перестановок, що є можливим через бієктивність зворотних функцій. У такому векторі, індекс позиції числа відповідає десятковому представленню бітів вхідного рядка, а число на цій позиції – десятковому представленню бітів вихідного рядка. Вентилі, у свою чергу, представляються як g(t, [c0, c1, …, cn]), де t - номер лінії цільового біта, а [c0, c1, …, cn] – вектор, який містить число-індикатор ролі для кожної лінії схеми відповідно до індексу позиції у векторі. Число-індикатор може набувати одного із трьох значень: 0 – позитивний контроль, 1 – негативний контроль, 2 – лінія не є контрольним бітом даного вентиля. Наприклад, третій вентиль на рис 1 можна описати як g(1, [2, 0, 0]).

Аби застосувати мурашиний алгоритм до проблеми синтезу зворотних логічних пристроїв, зручно представити синтез як зважений напрямлений граф. Вузлами графу вважаємо таблиці істинності схем. Ребрами є вентилі, що призводять до зміни від однієї таблиці істинності до іншої. Початковим вузлом пошуку обирається таблиця істинності синтезованої схеми, а кінцевим вузлом – так звана нульова таблиця істинності, яка відповідає схемі без жодного вентиля, тобто, здійснюється зворотний пошук [4]. Приклад такого графу показано на рис 2.

Через свою евристичну природу, мурашиний алгоритм керується певною кількістю параметрів, які потрібно ретельно підібрати відповідно до розмірності та складності синтезованої схеми, щоб досягнути задовільних результатів. Узагальнений алгоритм містить такі параметри, як:

-кількість ітерацій;

-кількість мурах;

-коефіцієнт важливості значення видимості;

-коефіцієнт важливості кількості феромонів;

-швидкість випаровування феромонів.

Також алгоритми спеціалізовані на синтезі передбачають ще такі додаткові параметри, як:

-глибина пошуку;

-кількість циклів локального пошуку.

У даному дослідженні проведено аналіз впливу кожного з вище перелічених параметрів на якість синтезованих зворотних схем із трьома входами на базі вентиля Тоффолі. Обчислення було виконано програмою написаною мовою програмування Go [5]. Результати містять узагальнені показники 3 спроб синтезу 3 різних схем за набором значень кожного з параметрів.

У ході дослідження чіткої закономірності щодо вибору коефіцієнтів важливості значень видимості та кількості феромонів не було виявлено. Вплив помилок у виборі цих коефіцієнтів не виявився вагомим. Схожі висновки можна зробити й про кількість циклів локального пошуку. При збільшенні значень цього параметру, зростає час синтезу та не спостерігається вплив на якість синтезованої схеми. Проте, варто зазначити, що якщо кількість циклів буде надто малою, бажана таблиця істинності може не бути реалізованою.

Параметр швидкості випаровування феромонів виявив тенденцію позитивного впливу на баланс кількості помилок та вартості синтезованої схеми (рис 3) у проміжку значень 0.2-0.4. З цих даних, можна зробити припущення, що варто намагатися мінімізувати значення цього параметру, задля досягнення максимально якісних результатів синтезу.

Надважливим параметром при використанні мурашиного алгоритму є кількість мурах. Як показало дослідження, збільшення кількості мурах гарантовано зменшує кількість помилок у синтезованій схемі (рис 4) та забезпечує стабільну якість вартості схеми (рис 5). Проте, варто бути обережним, адже збільшення даного параметру раптово збільшує час синтезу (рис 6), який може дійти до меж неприйнятності. Тому варто шукати збалансоване значення цього параметру, яке забезпечить якість результатів при допустимому часі роботи програми.

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

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




Рисунок 1. Приклад синтезованої схеми з базисом Тоффолі




Рисунок 2. Граф переходу станів у мурашиному алгоритмі




Рисунок 3. Графік зміни вартості схеми відносно швидкості випаровування




Рисунок 4. Зміна кількості помилок схеми відносно кількості мурах




Рисунок 5. Зміна вартості схеми відносно кількості мурах




Рисунок 6. Зміна часу синтезу відносно кількості мурах


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

1.Awan-Ur-Rahman. Introduction to Ant colony optimization(ACO) / Towards Data Science  [сайт]. – Режим доступу: https://towardsdatascience.com/the-inspiration-of-an-ant-colony-optimization-f377568ea03f,. 

2.Abdessaied N. and Drechsler R. Reversible and Quantum Circuits. Optimization and Complexity Analysis. Springer Cham, 2016.

3.Fredkin E. and Toffoli T. Conservative logic / Int. Journal of Theoretical Physics, 1982, 21(3-4): 219-253.

4.Min Li, Yexin Zheng, Michael S. Hsiao, Chao Huang. Reversible logic synthesis through ant colony optimization / 2010 Design, Automation & Test in Europe Conference & Exhibition (DATE 2010), Dresden, Germany, 2010, pp. 307-310.

5.Podlaski K. Ant colony optimization implementation for reversible synthesis in Walsh-Hadamard domain. Lect Notes Comput Sci 2020, v.2141, pp. 230-43. 

6.M. Tim Jones.  AI Application Programming.  Charles River Media, 2011.


________________________________________________________________________

Науковий керівник: Дейбук Віталій Григорович, доктор фізико-математичних наук, професор, Чернівецький національний університет імені Юрія Федьковича, м. Чернівці

Creative Commons Attribution Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License
допомога Знайшли помилку? Виділіть помилковий текст мишкою і натисніть Ctrl + Enter

Інші наукові праці даної секції

Конференції

Конференції 2024

Конференції 2023

Конференції 2022

Конференції 2021



Міжнародна інтернет-конференція з економіки, інформаційних систем і технологій, психології та педагогіки

Наукова спільнота - інтернет конференції

:: LEX-LINE :: Юридична лінія

Інформаційне суспільство: технологічні, економічні та технічні аспекти становлення