- Популяцією, кожна з яких представляє можливе рішення даної проблеми. Кожна особина оцінюється мірою її пристосованості згідно з тим, наскільки добре відповідне їй рішення задачі. У природі це еквівалентно оцінці того, наскільки ефективний організм при конкуренції за ресурси. Найбільш пристосовані особини отримують можливість відтворювати потомство за допомогою перехресного схрещування з іншими особинами популяції. Це призводить до появи нових особин, які поєднують в собі деякі характеристики, успадковані ними від батьків. Найменш пристосовані особини з меншою ймовірністю зможуть відтворити нащадків, так що ті властивості, якими вони володіли, будуть поступово зникати з популяції в процесі еволюції.
Таким чином, з покоління в покоління хороші характеристики поширюються по всій популяції. Схрещування найбільш пристосованих особин призводить до того, що досліджуються найбільш перспективні ділянки простору пошуку. Зрештою популяція буде сходитися до оптимального рішення задачі.
Отже, потрібно проводити селекцію для відбору найбільш пристосованих особин з метою прискорити пошук оптимального рішення.
Найменш пристосовані особини з меншою ймовірністю зможуть відтворити нащадків, так що ті властивості, якими вони володіли, будуть поступово зникати з популяції в процесі еволюції. Таким чином, з покоління в покоління хороші характеристики поширюються по всій популяції. Таким чином, для вирішення завдання необхідно вибирати особини з кращим значенням цільової функції (найбільш мінімальним значенням).
Схрещування
Найбільш простим є одноточечное схрещування - кожна обрана таким чином пара рядків схрещується наступним чином: випадковим чином вибирається положення точки перетину (ціле число k в проміжку від 1 і l - 1, де l - довжина рядка). Потім, шляхом обміну усіма елементами між позиціями k + 1 і l включно, народжуються дві нові рядки. Наприклад, нехай перше особина - а друга відповідно і нехай випадково вибрана точка перетину буде після третього гена (біта). Тоді в результаті схрещування отримаємо дві особини-нащадки - і. Після цього нащадки заміщають батьківські особини в проміжній популяції. Схематично цей варіант показаний на малюнку.
одноточечную схрещування легко узагальнюється на n-точкове з n точками перетину. Граничним випадком є ??рівномірний схрещування, при якому кожен ген першого з батьків випадковим чином передається будь з нащадків, при цьому другий нащадок, відповідно, отримує ген від іншого батька.
двоточкову схрещування ілюструє наступний приклад:
Тут чорними лініями виділені точки розрізу вихідної хромосоми, а в даному випадку бітової рядка.
У двоточковому кроссинговере (і багатоточковому кроссинговере взагалі) хромосоми розцінюються як цикли, які формуються з'єднанням кінців лінійної хромосоми разом. Для заміни сегменту одного циклу сегментом іншого циклу потрібно вибір двох точок розрізу. У цьому поданні, одноточковий кроссинговер може бути розглянутий як кросинговер з двома точками, але з однією точкою розрізу, зафіксованої на початку рядка.
Розробка програми
Програма реалізована в одному модулі: genetic.pas, текст якої наведено в додатку.
Програма складається з декількох процедур.
Процедура InitPop створює початкову популяцію випадковим чином за допомогою допоміжної функції Flip, яка генерує випадкове число з варіантів 0 і 1. Процедура виконується при запуску програми і обчислює функцію придатності. Процедури Select, Mutation і Crossover реалізують 3 генетичних оператора. Процедура Select реалізує оператор турнірного відбору. Функція Select1 здійснює відбір найкращих особин для популяції.
У функції відбувається перемішування популяції і вибір особин, які перейдуть в наступне покоління (що мають найкраще значення цільової функції). Обираються дві поруч стоять особини і в наступне покоління переходить особина з найкращим значенням цільової функції. Відбір відбувається PopSize раз (кількість особин в популяції).
Функція Mutation реалізує процес двухточечной мутації. Мутація відбувається з деякою ймовірністю. Алгоритм мутації має вигляд:
У процедурі використовуються наступні змінні і константи: - хромосома для мутації; - ймовірність мутації; - лічильник мутацій; - допоміжний біт для обміну ;, jcross - номери бітів для обміну. ??
Код процедури: Mutation (var a: Chromosome; flchrom: integer; var NMutation: integer); jcross, jcross1: integer ;: Allele; Flip (PMutation) then
{Мутація з імовірністю PMutation} (NMutation); {Нарощуємо лічильник мутацій}
{Шу...
