покоління завершується. Наступні покоління обробляються таким же чином: відбір, кросовер і мутація. p> В даний час дослідники генетичних алгоритмів пропонують багато інших операторів відбору, кросовера і мутації. Ось лише найбільш поширені з них. Перш за все, турнірний. Турнірний відбір реалізує n турнірів, щоб вибрати n особин. Кожен турнір побудований на вибірці k елементів з популяції, і вибору кращої особини серед них. Найбільш поширений турнірний відбір з k = 2. p> Елітні методи відбору гарантують, що при відборі обов'язково будуть виживати кращий або кращі члени популяції сукупності. Найбільш поширена процедура обов'язкового збереження тільки однієї кращої особини, якщо вона не пройшла як інші через процес відбору, кросовера і мутації. Елітизм може бути впроваджений практично в будь стандартний метод відбору. p> Двоточковий кросовер і рівномірний кросовер - Цілком гідні альтернативи одноточечную оператору. У двоточковому кросовері обираються дві точки розриву, і батьківські хромосоми обмінюються сегментом, який знаходиться між двома цими точками. У рівномірному кросовері, кожен біт першого батька успадковується першим нащадком із заданою ймовірністю; в іншому випадку цей біт передається другому нащадку. І навпаки.
Шима (schema)
Хоча зовні здається, що генетичний алгоритм обробляє рядки, насправді при цьому неявно відбувається обробка шим, які представляють шаблони подібності між рядками. Генетичний алгоритм практично не може займатися повним перебором всіх точок у просторі пошуку. Однак він може робити вибірку значного числа гіперплоскостей в областях пошуку з високою пристосованістю. Кожна така гіперплощина відповідає безлічі схожих рядків з високою пристосованістю. p> Шима - це рядок довжини l (що й довжина будь рядка популяції), що складається із знаків алфавіту {0, 1, *}, де {*} - невизначений символ. Кожна Шім'а визначає безліч всіх бінарних рядків довжини l, що мають у відповідних позиціях або 0, або 1, залежно від того, який біт знаходиться у відповідній позиції самої Шім'ї .. Наприклад, Шім'а, 10 ** 1, визначає собою безліч з чотирьох пятібітових рядків {10001; 10011; 10101; 10111}. У шим виділяють дві властивості - порядок і певна довжина. Порядок Шім'ї - це число певних бітів ("0" або "1") в Шім'у. Певна довжина - відстань між крайніми певними бітами в Шім'у. Наприклад, вищезгадана Шім'а має порядок o (10 ** 1) = 3, а певна довжина d (10 ** 1) = 4. Кожен рядок у популяції є прикладом шим. br/>
Будуючі блоки
Будуючі блоки - це Шім'ї володіють: p> - високою пристосованістю,
- низьким порядком,
- короткою певною довжиною. br/>
Пристосованість Шім'ї визначається як середнє пристосованість прикладів, які її містять. p> Після процедури відбору залишаються лише рядки з більш високою пристосованістю. Отже рядки, які є прикладами шим з високою пристосованістю, вибираються частіше. Кросовер рідше руйнує Шім'ї з коротшою певною довжиною, а мутація рідше руйнує Шім'ї з низьким порядком. Тому, такі Шім'ї мають більше шансів переходити з покоління в покоління. Голланд показав, що, в той час як генетичний алгоритм явним чином обробляє n рядків на кожному поколінні, у теж час неявно обробляються порядку таких коротких шим низького порядку і з високою пристосованістю (корисних шим, "useful schemata"). Він називав це явище неявним паралелізмом. Для вирішення реальних завдань, присутність неявного паралелізму означає, що велика популяція має більше можливостей локалізувати рішення експоненціально швидше популяції з меншим числом особин. h3> Теорема шим
Простий експоненціально збільшує число прикладів корисних шим або будують блоків. Доказом цього служить наступна теорема, відома як "теорема шим". p> Нехай m (H, t) - число прикладів Шім'ї H в t-му поколінні. Обчислимо очікуване число прикладів H в наступному поколінні або m (H, t +1) у термінах m (H, t). Простий генетичний алгоритм кожному рядку ставить у відповідність імовірність її "виживання" при відборі пропорційно її пристосованості. Очікується, що Шім'а H може бути обрана m (H, t) Ч (F (H)/fср.) Раз, де fср. - Середня пристосованість популяції, а f (H) - середня пристосованість тих рядків у популяції, які є прикладами H. p> Ймовірність того, що одноточковий кросовер зруйнує шіму дорівнює ймовірності того, що точка розриву потрапить між певними бітами. Імовірність же того, що H "переживає" кросовер не менш 1-Pc_ (d (H)/l-1). Ця ймовірність - нерівність, оскільки Шім'а зможе вижити якщо в кросовері брав участь також приклад схожою Шім'ї. Ймовірність того, що H переживе мутацію - (1-Pm) o (H), цей вираз можна апроксимувати як (1-o (H)) для малого Pm і o (H). Твір очікуваного число відборів і ймовірностей виживання відомо як теорема шим (3):
m (H, t +1) (3)
Теорема шим показує, що будують блоки ростуть по експоненті, в той час Шім'ї з п...
