Розробка методів дослідження характеристик генетичного алгоритму розподілу ланцюгів на шари, в МСМ

С.Н. Щеглов, А.В. Мухлаев, В.А. Кулінський

Одним із завдань проектування топології матричних ВІС і НВІС є задача оптимального розподілу на шари трасуванню сполук у базовому матричному кристалі. Відомо, що базовий матричний кристал (БМК) - це компактний модуль з вищої ступенем інтеграції, що служить для розташування кількох сотень кристалів і їх з'єднання кількома тисячами ланцюгами. Самою загальною метою при вирішенні цієї проблеми є найбільш ефективне використання площі комутаційного простору при одночасній оптимізації таких конструктивних параметрів схеми, як число шарів кількість міжшарових переходів, відсоток реалізованих з'єднань.

Традиційні методи вирішення цього завдання мають істотний недолік - "пастки" локальних оптимумів. Розглянутий генетичний метод є методом спрямованого випадкового пошуку. Основний характеристикою таких методів є те, що вони допускають тимчасове погіршення цільової функції. Це дозволяє уникнути "пасток", а при достатньому числі ітерацій знайти прийнятне рішення. Генетичні алгоритми є адаптивними пошуковими алгоритмами, які здійснюють процес накопичення і використання інформації в проектованої області, спрямованої на досягнення оптимального рішення при первісної невизначеності та змінних зовнішніх умовах. На відміну від стандартних пошукових алгоритмів, генетичні алгоритми базуються на поліпшенні деякої популяції, що складається з обмеженого безлічі рішень. Ця методика мотивується тим, що пошук в області багатьох рішень зменшує ризик потрапляння в локальні оптимуму, що дає більш кращі результати, ніж використання одного рішення.

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

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

Рис 1.

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

Якщо умова розглянутої задачі задано на рис. 1, то хромосома набуде вигляду

1 2 3 4 5 6 7

Нехай після застосування деяких генетичних операторів нова хромосома має вигляд:

3 4 6 5 2 7 1

тоді рішення, закодоване в новій хромосомі, зображено на рис. 2

Рис 2

де різними типами ліній показані різні верстви розподіляються ланцюгів.

розкодування хромосоми відбувається за такими правилами:

Береться перший ген хромосоми і за значенням його аллели визначається вихідна ланцюг. Отримана ланцюг кладеться в перший шар, потім аналогічним чином отримуємо нову ланцюг з аллели другого гена хромосоми (ланцюг 4 в даному прикладі); відомості про те чи можуть ці ребра знаходиться в одному шарі отримуємо з масиву обмежень, який ми визначили вище. Якщо можуть, то визначаємо їх в один шар, якщо ні, то шар оголошуємо заповненим ланцюг визначаємо в наступному шарі, а до заповнених верствам не повертаємося зі спробами доповнити їх новими ланцюгами.

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

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

Де f (i, t) - значення цільової функції для i-ї хромосоми;

N - число шарів.

Цільова функція визначає цінність кожної хромосоми. Хромосоми з кращими характеристиками потім піддаються діям генетичних операторів. У програмі реалізовані три оператори селекції: стандартні оператори "Колесо рулетки" і "Турнірний", а також модифікація "Колеса рулетки" в якому вибір хромосоми відбувається як у "Колесі" але другий раз хромосома вже не може вибиратися.

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

Наприклад: оператор Кросинговер отримав двох батьків

Р1: 1 8 11 12 15 0 3 5 6 9 2 7 4 10 13 14

P2: 1 2 7 8 11 0 6 9 4 10 12 13 14 15 3 5

При розкодування алгоритм поділили їх на шари        

P 1   

Шар 0: 1 8 11   

Шар 1: 12 15   

Шар 2: 0 3 5 6 9   

Шар 3: 2 7   

Шар 4: 4 10 13 14            

P 2   

Шар 0: 1 2 7 8 11   

Шар 1: 0 6 9   

Шар 2: 4 10   

Шар 3: 12 13 14 15   

Шар 4: 3 5             

Шар 0: 1 8 11: