3.3. Функціонування генетичного алгоритму

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

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

У документі «Пояснювальна записка» описано критерії вибору генетичних операторів та принципи їх дії.

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

• одноточковий кросинговер із точкою схрещування;

• двоточковий кросинговер із точками схрещування;

• схрещування навпіл.

Відповідно до вибраного способу буде відбуватися схрещування.

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

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

Початковою умовою мутації особини є отримання випадковим чином числа 5 з множини від 0 до 10. При тестуванні програми встановлено, що при згаданих умовах мутація відбувається в 5-10-ти випадках з 64-ох особин популяції.

Наступним етапом виконання алгоритму – оцінка та відбір особин для наступного покоління.

Відбір популяції може відбуватися трьома способами:

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

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

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

Більш детально методи відбору описані в документі «Пояснювальна записка».

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

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

3.4. Опис роботи з програмою

Програма умовно поділена на три складові, тобто три етапи виконання, доступ до яких можна отримати через головне меню програми (рис. 3.4).

Рис. 3.4. Головне меню програми

Пункт меню «Формування комбінаційних схем» дозволяє завантажити форму для побудови структурної схеми комбінаційної схеми, її програмну модель справного і несправного станів. Для побудови комбінаційних схем в програмі передбачено використання наступних типів логічних елементів: NOT, 2OR, 2OR_NOT, 2AND, 2AND_NOT, 3OR, 3OR_NOT, 3AND, 3AND_NOT. Загальний вигляд форми для побудови комбінаційних схем наведено на рис. 3.5.

Рис. 3.5. Побудова комбінаційних схем

Основні частини форми містять:

– меню користувача;

– панель інструментів;

– поля для задання та відображення вхідних сигналів;

– таблиця істинності;

– об’єкт відображення комбінаційних схем.

Меню користувача дозволяє виконувати наступні дії:

– вибрати схему, тобто завантажити або зберегти схему у вигляді графічного файлу;

– видаляти елементи, від останнього побудованого до першого;

– видаляти лінію, від останньої побудованої до першої;

– перевіряти правильність зв’язків у схемі;

– формувати таблицю істинності;

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

Панель інструментів. В даній панелі знаходяться кнопки для створення логічних елементів, відповідно під кожною кнопкою знаходиться відповідний їй тип елементу І, АБО, І-НІ, АБО-НІ, двох типів (дво- та тривходові) та елемент інвертор НІ. Для вибору логічного елемента достатньо натиснути на його вигляді на панелі елементів. Щоб відобразити один тип елемента кілька раз, то його достатньо вибрати на панелі один раз, а далі натискання кнопкою миші на робочій формі він буде дублюватися кожний раз. При зміні типу логічного елемента, так само будуть відбуватися події й для іншого типу.

Для з’єднання елементів між собою вибираємо елемент лінія зв’язку, натиснувши на відповідну кнопку меню «Намалювати лінію». Для встановлення лінії зв’язку необхідно натиснути лівою клавішею мишки на виході одного елемента та, утримуючи клавішу мишки, потягнути лінію на вхід іншого логічного елемента.

Поля для задання вхідних значень. Ця панель складається з:

– вхідних даних для елемента який створюється;

– кнопки Add – додає до створеної схеми введену вхідну комбінацію;

– таблиці для вхідної комбінації схеми.

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

Робоча область. На даній панелі реалізовано робочу зону для побудови комбінаційних схем. Дана панель керується процедурами опрацювання подій мишки користувача.

Загальний вигляд форми зі створеною схемою та її таблицею істинності наведено на рис. 3.6. Далі на основі цієї схеми буде пояснено роботу програми.

Рис. 3.6. Екранний вигляд форми

Наступним етапом роботи – вибір несправного логічного елемента схеми. Для цього натискаємо на відповідну кнопку на панелі елементів «Задати константну несправність», а потім на конкретний елемент на схемі.

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

Після того, як задані несправності можна приступати до відшукання генетичним алгоритмом тестової послідовності. Для цього необхідно у головному меню вибрати пункт «Налагодження параметрів генетичного алгоритму» (рис. 3.4) і завантажити відповідну форму (рис. 3.7).

Рис. 3.7. Форма для налаштування роботи генетичного алгоритму

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

На заключному етапі, коли сформована програмна модель комбінаційної схеми та налаштовані параметри генетичного алгоритму, в головному меню слід вибрати пункт меню «Виконання тесту». Після вибору даного пункту меню завантажиться форма для демонстрації роботи генетичного алгоритму (рис. 3.8). Початкова популяція формується за подією FormShow у відповідності до обраної стратегії.

Рис. 3.8. Екранна форма роботи генетичного алгоритму

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

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

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

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

Відбір здійснюється відповідно обраного методу відбору, за результатами оцінки фітнес – функції (рис. 3.9), яка описана в документі «Пояснювальна записка».

В третьому стовпчику елемента StringGrid відображається значення фітнес-функції, що отримується в результаті опрацювання програмної моделі комбінаційної схеми. Значення «1» означає, що дана особина (тестова послідовність) відшукує 1 несправність. Відповідно «0» – жодної несправності.

Рис. 3.9. Оцінка здоров’я популяції й відбір методом рулетки хромосом для наступної епохи генетичного алгоритму

У випадку турнірного методу відбору, відбираємо ті особини для схрещування, які відшуковують ту кількість несправностей, що є насправді. У нашому випадку – 1 несправність, що відображено у четвертому стовпчику.

На рис. 3.9 наведено приклад відбору методом рулетки. Словом «обрано» зроблені помітки, які батьки відібрані для схрещування в наступну епоху функціонування генетичного алгоритму. Причому процент скорочення популяції ми встановлюємо довільно на головній формі програми.

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

Рис. 3.10. Повідомлення користувача про відшукання тестової послідовності

Після відшукання, користувач повідомляється про результат діалоговим повідомленням (рис. 3.11).

Рис. 3.11. Повідомлення користувача про відшукання тестової послідовності