1.1.1. Еволюційні методи побудови перевірочних тестів
Для підвищення рівня «інтелекту» і ефективності сучасних САПР комп’ютерних систем, розширюючи їх можливості використовуються різні методи штучного інтелекту. Одним з самих перспективних напрямів є використання еволюційних обчислень. [2]
Особливості ідей теорії еволюції і самоорганізації полягають в тому, що вони знаходять своє підтвердження не тільки для біологічних систем, що успішно розвиваються мільярди років. На сьогодні, розвивається новий напрямок в теорії та практиці штучного інтелекту – еволюційні обчислення, термін, переважно використовується для загального опису алгоритмів пошуку, оптимізації або навчання, що базуються на деяких формалізованих принципах природного еволюційного відбору. Еволюційні обчислення використовують різні моделі еволюційного процесу. Серед них можна виділити наступні основні парадигми:
генетичні алгоритми;
еволюційні стратегії;
еволюційне програмування;
генетичне програмування.
Відрізняються вони, в основному, способом представленням шуканих рішень і різним набором використовуваних в процесі моделювання еволюції операторів. Відмітимо, що в даний час, всі парадигми використовуються при генерації тестів цифрових систем.
1.1.2. Простий генетичний алгоритм для генерації тестів комбінаційних схем
Генетичні алгоритми (ГА) [3], являються однією з парадигм еволюційних обчислень, що являють собою алгоритми пошуку, побудови на принципах, похожих на природній відбір. Ці принципи побудовані на наступних механізмах еволюції.
1. Перший принцип ГА базується на концепції виживання сильніших і природного відбору по Дарвіну, яка була сформульована ним в 1859 р. в книзі «Походження видів шляхом природного відбору». Згідно Дарвіна, особини, які краще можуть вирішувати задачі у своєму середовищі, виживають і краще розмножуються (репродукують). В ГА кожна особина являє собою деяке рішення даної проблеми (наприклад, пошуку екстремуму функції). За аналогією з цим принципом нащадки з кращими значеннями цільової (фітнес) функції мають більше шансів вижити і репродукувати.
2. Другий принцип ГА зумовлений тим фактором, що хромосома нащадку складається з частин, що отримують їх з хромосом батьків. Цей важливий принцип був відкритий в 1865 р. Менделем.
3. Третій принцип, який використовується ГА, побудований на концепції мутації, відкритої в 1900 р. de Vries. Початково цей термін використовувався для опису існуючих змін властивостей нащадків та отримування ними властивостей, що відсутні у батьків. За аналогією з цим принципом ГА використовують подібний механізм для зміни властивостей нащадків і тим самим, збільшуючи різноманітність особин в популяції (множина рішень).
Ці три принципи складають основу ГА. У відповідності з цим простим ГА використовує три основні оператори: репродукція, кросинговер, мутація. При репродукції хромосоми копіюються відповідно їхнім значенням цільової функції. Копіювання кращих хромосом з більшими значеннями цільової функції визначає більшу ймовірність їх попадання в наступну генерацію. Оператор репродукції реалізує принцип «виживання сильніших» по Дарвіну.
Самий простий (популярний) метод реалізації оператора репродукції – побудова асиметричного колеса рулетки, в якому кожна хромосома має сектор, пропорціональний її значенню цільової функції. Наприклад, «колесо рулетки» має наступний вигляд, представлений на рис. 1.1.
Рис. 1.1. Оператор репродукції у вигляді рулетки
Для селекції хромосом використовується пошук на основі колеса рулетки. При цьому колесу рулетки повертається в проміжну популяцію. Очевидно, що хромосома, якій відповідає великий сектор рулетки, має велику ймовірність попасти в наступне покоління. В результаті виконання оператора репродукції з поточної популяції формується проміжна популяція, хромосоми які будуть використані для побудови покоління за допомогою операторів (кросинговеру) схрещування і мутація.
Оператор кросинговеру переважно виконується за три етапи:
1. Два рядки (хромосоми, особини): А=а1а2...аn i B=b1b2...bn вибираються випадково з проміжної популяції після репродукції;
2. Вибирається також випадково точка кросинговеру k (1≤k<n);
3. Хромосоми А і В обмінюються частинами після k-ої позиції і формують два нових рядки: А=а1а2...аkbk+1...bn i B=b1b2...bk аk+1...аn.
Оператор мутації випадковим чином (з невеликою точністю Р=0,001) змінює випадковий ген (елемент) рядка.
Використовуючи ці три основні оператори, популяція (множина потенційних рішень даної проблеми) еволюціонує від покоління до покоління. Еволюція такої штучної популяції представлена на рис. 1.2.
Таким чином, генетичні алгоритми використовуючи випадковий напрямлений пошук для побудови оптимального рішення даної проблеми. При цьому напрямлений випадковий пошук моделює процес природної еволюції. Кожне рішення задачі (особина) представляється хромосомою – рядком елементів (генів). Класичний «простий» генетичний алгоритм [2, 3] використовує двійкові рядки – рядки з елементів 0 і 1, що робить його цікавим для задач генерації перевірочних наборів або їх послідовностей, які в даному випадку розглядаються як особини популяції – множини можливих рішень. На множині рішень визначається цільова (фітнес) функція, яка дозволяє оцінювати наближеність кожної особини до оптимального рішення.
Рис. 1.2. Простий генетичний алгоритм
У випадку задачі генерації тестів цільової функції прямо або неявно повинна відображати такі властивості двійкових наборів або послідовностей як число перевірочних несправностей або змін сигналів у схемі.
Таким чином, щоб задати генетичний алгоритм, необхідно визначити поняття особини, популяції, операторів схрещування і мутації, задати оціночну функцію.