Анотація: В лекції наведені теоретичні оцінки ефективності генетичних алгоритмів пошуку масок і експериментальні дані їх застосування до різних схем з каталогів ISCAS85 і ISCAS89.
У попередній лекції були описані прості генетичні алгоритми для пошуку масок. Інтерес представляють питання, що стосуються оцінки часу пошуку масок з використанням цих алгорітмов.Кроме того, якщо мова йде про наближеному вирішенні, то цікава також оцінка віддаленості такого рішення від оптимального і швидкості збіжності процесу пошуку оптимального рішенню.
Спочатку наведемо твердження про оцінку обчислювальної складності описаних в попередній лекції ПГА.
Введемо наступні позначення. нехай 
- число етапів еволюції, що реалізуються ГА, 
- число особин в популяції, 
- обсяг пам'яті (в бітах) для зберігання однієї особини.
Теорема. Нехай для ЦУ з безліччю несправностей 
отримано СПР. Тоді оцінка алгоритмічної складності одного запуску генетичного алгоритму зі структурою хромосоми (29.1) або (29.6) і з використанням будь-якої з фітнес-функцій (29.3) - (29.5), (29.7) - (29.10) дорівнює 
, А обсяг пам'яті, необхідної для роботи генетичного алгоритму, дорівнює 
.
Доведення . На кожному етапі еволюції має бути обчислено значення фітнес-функції кожної особини в популяції, після чого особини повинні бути впорядковані за значеннями їх пристосованості.
Виходячи з виду формул (29.3) - (29.5), (29.7) - (29.10), оцінка обчислювальної складності для функцій пристосованості зводиться до оцінки обчислювальної складності величин 
і 
. згідно [ 1 ] Обчислювальна складність величини оцінюється величиною
Для обчислення значення необхідно також провести
порівнянь. Сортування елементів популяції виробляється за час
Беручи до уваги той факт, що в процесі еволюції має бути знайдено поколінь, а також з урахуванням (30.1) - (30.3), отримаємо оцінку обчислювальної складності, наведену в формулюванні теореми.
На кожному етапі еволюції потрібно зберігання двох поколінь: батьківської популяції і популяції дочірніх особин. Звідси місткість складність генетичного алгоритму для задач мінімізації та оптимізації діагностичної інформації оцінюється величиною .
Зауважимо, що один з можливих способів прискорення часу роботи ПГА складається в їх розпаралелювання.
Генетичні алгоритми надають безліч можливостей для реалізації на архітектурі, що допускає паралельні процеси.
Найпростіший спосіб распараллелить ГА - распараллелить процес виконання його операторів і обчислення значення фітнес-функції. У разі паралельних операторів алгоритм буде працювати наступним чином. Базовий потік породжує робочі потоки, які можуть обмінюватися повідомленнями з базовим за допомогою деякого інтерфейсу. Коли обчислення в базовому потоці доходять до паралельного оператора, формуються завдання робочим потокам. Популяція ділиться на рівні частини (за кількістю робочих потоків) і кожна частина надсилається відповідному робочому потоку. Базовий потік продовжує свою роботу після отримання результатів від усіх робочих потоків. Якщо в процесі очікування результатів робиться висновок про аварійне завершення будь-якого робочого потоку, завдання надсилається повторно іншому робочому потоку, вільному в даний момент.
Важливо зауважити, що при такій організації ГА йому байдуже, як і в якому середовищі передаються повідомлення, тому цей спосіб підходить для обчислювальних систем будь-якої організації: однопроцесорних ЕОМ, багатопроцесорних ЕОМ або кластерів будь-якої структури. Ефективність такого розпаралелювання залежить перш за все від швидкості передачі повідомлень між потоками. Якщо розглядати многопроцессорную ЕОМ із загальною пам'яттю, де скороcть передачі даних між потоками максимальна, то розпаралелювання будь-яких операторів ефективно в переважній більшості випадків, т. К. Генотипи, що зберігаються в загальній пам'яті, чи не копіюються для кожного робочого потоку, а використовуються спільно.
Якщо ж розглядати кластер, де оперативна пам'ять у потоків розділена, а передача повідомлень виробляється через локальну мережу, то необхідно провести детальний аналіз наслідків розпаралелювання того чи іншого оператора з точки зору втрат продуктивності алгоритму при передачі повідомлень між потоками. В цілому, оператор доцільно распараллеливать, якщо обчислення результату для кожного генотипу займає набагато більше часу, ніж передача генотипу в повідомленні потоку і прийом відповіді.
Якісні оцінки обчислювальної складності ПГА, отримані в сформульованої вище теоремі, безсумнівно представляють інтерес, але значно більший інтерес представляють експериментальні дані, отримані для різних реальних ЦУ. Нижче буде представлена статистика, отримана в результаті проведення численних експериментів як на вихідних даних, що генеруються випадковим чином, так і на реальній ДІ для деяких реальних ДУ.
Результати експериментів, які демонструються нижче в табл. 30.1 -30.7, отримані на PC Pentium III, 1024 MHz, 256 MB RAM і частково відображені в [ 5 ].
Дані про ефективність застосування представленого вище простого ГА для мінімізації інформації (1-я із завдань, сформульованих в лекції 4) при пошуку маски наведені в табл. 30.1 (Ці результати отримані на випадкових вихідних даних).
Ці дані були отримані з використанням оператора відбору лінійним ранжированием і оператора булева схрещування. Застосування інших типів операторів, перерахованих нами раніше, як показали чисельні експерименти, вимагають в середньому великих тимчасових витрат на пошук оптимальної маски і при цьому дають менші розміри скорочення інформації.
В процесі проведення розрахунків було емпірично встановлено, що чисельність популяції досить обмежити 50 особинами, а довжину життєвого циклу - 50 поколіннями.
В табл. 30.2 для порівняння наведені результати вирішення тієї ж завдання пошуку оптимальної маски методом повного перебору.
Як видно з цієї таблиці, навіть для досить скромних розмірів вихідної інформації (загальний обсяг не перевищував 3810 біт) пошук рішення вимагає дуже великих часових затрат. Звідси можна зробити висновок, що для реальних завдань класифікації об'єктів з великим числом ознак (більше 100) застосування перебору неприйнятно.
Перейдемо тепер до оцінки ефективності застосування розробленого простого ГА для оптимізації інформації при пошуку маски на випадкових даних. Відповідні результати наведені в табл. 30.3 .
Нагадаємо, що дані, наведені в табл. 30.3 , Були отримані із застосуванням спеціальних операторів булева кросовера і мутації. При такій організації виконання схрещування і мутації в кожному новому поколінні присутні особини з одним і тим же числом одиниць в відповідних їм хромосомах, т. Е. Особи-маски одного і того ж обсягу. У зв'язку з цим для вирішення задачі оптимізації інформації замість фітнес-функції (29.4) вигідно використовувати фітнес-функцію (29.5), для якої ПГА повинен знайти мінімум. Таке спрощення призводить до скорочення часу роботи алгоритму.
Спроби знаходити рішення 2-ий завдання методом повного перебору показали, що тут ситуація повністю аналогічна тій, що мала місце для 1-ої задачі. Для реальних завдань пошуку маски при довжині повної реакції ДУ понад 100 біт метод простого перебору практично не застосуємо.
Наведемо дані для скорочення ДІ конкретних реальних пристроїв. У наступній серії експериментів була використана ДІ, отримана для ЦУ з каталогу ISCAS'89 [ 2 ] При моделюванні одиночних несправностей за допомогою імовірнісних послідовностей як діагностичний тест. Кожен імовірнісний тест був складений з 100 вхідних наборів. У безліч технічних станів для ДУ було включено справний стан, а також по одному представнику від кожного безлічі не відрізняються один від одного за допомогою цього тесту несправностей.
Табл. 30.4 представляє динаміку знаходження рішення задачі мінімізації ДІ для ЦУ з набору схем каталогу ISCAS'89.
Дані, наведені в цій таблиці, так само як і в табл. 30.1 , Отримані із застосуванням вибору лінійним ранжированием, оператора однорідного кросовера і фітнес-функції (4.1).
Табл. 30.5 показує динаміку знаходження рішення задачі 2 для деяких схем з набору ISCAS'89.
Так само як і в табл. 30.3 ці дані отримані із застосуванням спеціальних операторів кросовера і мутації і фітнес-функції (29.4).
Варто відзначити, що, як показує досвід, значне збільшення довжини імовірнісного діагностичного тесту призводить до досить малому росту числа виявлених з його допомогою несправностей. З цієї причини збільшення довжини тесту, наслідком якого є зростання обсягу ДІ, по -видимому, може тільки поліпшити показники в останньому стовпці таблиць 30.4 і 30.5, але не погіршити їх.
Експерименти по знаходженню індивідуальних масок проводилися для ДІ отриманої для ДУ з каталогу ISCAS'89 при моделюванні одиночних несправностей за допомогою тестових послідовностей HITEC [ 3 ]. Так само як і в попередньому випадку в безліч технічних станів було включено по одному представнику від кожного класу еквівалентності на безлічі різноманітних технічних станів.
<
