Генетичний алгоритм генерації тестів для комбінаційних схем

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

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

2. Другий принцип ГА зумовлений тим фактором, що хромосома нащадка складається з частин, які отримують із хромосом батьків.

3. Третій принцип побудований на концепції мутації. У відповідності до цього принципу ГА використовують механізм для зміни властивостей нащадків і тим самим збільшують різноманітність особин у популяції (множина рішень).

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

Рис. 6.2. Програмна модель комбінаційної схеми

Використовуючи ці три основні оператори, популяція (множина потенційних розв’язків даної проблеми) еволюціонує від покоління до покоління. Еволюція такої штучної популяції зображена на рис. 6.3.

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

Рис. 6.3. Алгоритм функціонування простого генетичного алгоритму

Відповідно до рис. 6.3, на кроці 1 алгоритму у простішому випадку випадковим чином генерується множина двійкових наборів – вихідна популяція. Далі, на кроці 2, вибираються в деякому випадку кращі особини-батьки в проміжну популяцію. На кроці 3 з імовірністю Р_с шляхом використання класичного оператора кросинговеру генеруються особини-нащадки (двійкові набори), які і на кроці 4 змінюються з імовірністю Р_m за допомогою класичного оператора мутації. Знову отримані двійкові набори поповнюють проміжну популяцію, що відображено кроком 5 алгоритму. Таким чином, після кроку 5 проміжна популяція містить як батьківські особини, так і їх нащадків. Оскільки потужність популяції переважно підтримують постійною (вона є одним із важливіших параметрів алгоритмів), на кроці 5 в популяції залишаються в деякій мірі кращі особини. Як критерій зупинки на кроці 6 в простішому випадку використовується кількість виконаних ітерацій – поколінь алгоритму. Результатом роботи генетичного алгоритму на кроці 7 є поточна популяція – множина двійкових наборів, які складають перевірковий тест.

Створення вихідної популяції. На сьогодні найбільш відомі й поширені на практиці три способи створення вихідної популяції (початкової множини рішень).

Стратегія «покривала» – формування повної популяції, яка містить всі можливі рішення.

Стратегія «дробовика» – генерація достатньо великої випадкової множини рішень (псевдовипадкова генерація тестів).

Стратегія «фокусування» – генерація множини рішень, які включають різновиди одного рішення.

Всі три стратегії можуть бути використані при генерації тестів.

Відбір батьків – селекція. Метод вибору батьків для наступного формування нащадків за допомогою генетичних операторів кросинговеру і мутації робить вагомий вплив на ефективність функціонування генетичного алгоритму.

Серед найпоширеніших операторів відбору розрізняють:

– пропорційний відбір (метод рулетки);

– лінійне ранжування;

– рівномірне ранжування;

– локальний відбір;

– відбір на основі відсічення;

– турнірний відбір.

Передумовою для вибору методу відбору служить кількість тестових комбінацій та їх можливості виявлення несправностей, що може забезпечуватися порогом відсічення. Цей метод використовується для великих популяцій (N>100). Відповідно до вибору методу створення вихідної популяції – стратегії «покривала» обрано метод відбору на основі відсічення. При цьому особини впорядковуються згідно зі значеннями цільової функції і як батьки вибираються тільки кращі особини. Далі, з однаковою ймовірністю, серед них випадково вибираємо пари-батьки. Порогом відсічки Т вибираємо значення 25 %.

Вибір оператора рекомбінації (кросинговеру). Оператор кросинговеру переважно виконується за три етапи:

1. Два рядки (хромосоми, особини): А=а₁а₂...а_n i B=b₁b₂...b_n вибираються випадково з проміжної популяції після репродукції.

2. Вибирається також випадково точка кросинговеру k (1≤k<n).

3. Хромосоми А і В обмінюються частинами після k-ї позиції і формують два нових рядки: А=а₁а₂...а_kb_k+1...b_n i B=b₁b₂...b_k а_k+1...а_n.

При однокрапковому кросинговері випадково вибирається точка схрещування з деякою ймовірністю (наприклад, Р_с=0,5) та проводиться обмін фрагментами хромосом після точки схрещування, як показано на рис. 6.4.

Рис. 6.4. Однокрапковий двійковий кросинговер

Вибір оператора мутації. Мутація з ймовірністю застосування операції Р_мут проводить вибір одної з можливих операцій:

– вилучення одного вхідного вектора з випадково вибраної позиції. Застосування даної операції дозволяє зменшувати довжину тестової послідовності в тому випадку, коли вилучений вектор не погіршує тестові властивості послідовності;

– додавання одного вхідного вектора у випадкову позицію, що дозволяє розширити пошук можливих рішень;

– випадкова заміна бітів у тестовій послідовності.

Далі вибір між трьома операторами мутації здійснюється з ймовірностями Р_мут1, Р_мут2 і Р_мут3.

Оскільки ми формуємо тестові послідовності для виявлення константних несправностей, то нас цікавить випадкова заміна бітів у тестовій послідовності, тобто «0» замінюємо на «1» й навпаки із заданою випадковим чином Р_мут.

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

Таблиця 6.1

Проблемно-зорієнтовані фітнес-функції для генерації тестів

№ п/п	Позначення	Значення фітнес-функції
	N	Кількість вузлів у схемі
	Nd	Кількість вузлів, що мають різні значення сигналів у справній і несправній схемах
	T	Кількість тригерів у схемі
	Td	Кількість тригерів, які змінили стан
	E	Кількість кодів у справній і несправній схемах
	L	Довжина тестової послідовності
	F	Кількість несправностей у схемі
	Fd	Кількість перевірених несправностей
	Fdt	Кількість несправностей, що активовані до тригерів
	D	Прозорість несправності
	W	Потужність послідовності

Продовження табл. 6.1