2.2.7. Порядок контролю і приймання

Контроль за виконанням дипломного проекту здійснює керівник роботи, а перевірку правильності оформлення дипломного проекту – нормоконтролер.

2.3. Опис генетичного алгоритму для формування тестових послідовностей комбінаційних схем

Для розроблення генетичного алгоритму, який буде формувати тести комбінаційних схем, спочатку визначимо особини, популяцію та цільову функцію. За основу, при побудові генетичного алгоритму взято простий генетичний алгоритм (рис. 1.2).

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

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

2.3.1. Створення вихідної популяції

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

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

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

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

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

2.3.2. Відбір батьків - селекція

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

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

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

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

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

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

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

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

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