пливаютьна поведінку генетичного алгоритму. Так інбридинг можна охарактеризувати властивістюконцентрації пошуку в локальних вузлах, що фактично призводить до розбиття популяціїна окремі локальні групи навколо підозрілих на екстремум ділянок ландшафту,навпроти аутбридинг якраз спрямований на попередження збіжності алгоритму до вжезнайденим рішенням, змушуючи алгоритм переглядати нові, недосліджені області.
3.3 Механізм відбору
Обговорення питання про вплив методу створеннябатьківських пар на поведінку генетичного алгоритму неможливо вести у відривівід реалізованого механізму відбору при формуванні нового покоління. Найбільш ефективнідва механізми відбору елітний і відбір з витісненням.
Ідея елітного відбору, загалом, не нова,цей метод заснований на побудові нової популяції тільки з кращих особин репродукційноїгрупи, що об'єднує в собі батьків, їхніх нащадків і мутантів. В основному це пояснюютьпотенційною небезпекою передчасної збіжності, віддаючи перевагу пропорційномувідбору. Швидка збіжність, що забезпечується елітним відбором, може бути, коли ценеобхідно, з успіхом компенсовано відповідним методом вибору батьківських пар,наприклад аутбридинг. Саме така комбінація "аутбридинг - елітний відбір"є однією з найбільш ефективних.
Другий метод, на якому хотілосяб зупинитися, це відбір витісненням. Чи буде особина з репродукційної групизаноситися в популяцію нового покоління, визначається не тільки величиною її пристосованості,але і тим, чи є вже в формованої популяції наступного покоління особина з аналогічнимхромосомним набором. З усіх особин з однаковими генотипами перевагу спочатку,звичайно ж, віддається тим, чия пристосованість вище. Таким чином, досягаютьсядві мети: по-перше, не губляться кращі знайдені рішення, що володіють різнимихромосомними наборами, а по-друге, в популяції постійно підтримується достатнягенетичну різноманітність. Витіснення в даному випадку формує нову популяціюскоріше з далеко розташованих особин, замість особин, що групуються близько поточногознайденого рішення. Цей метод особливо добре себе показав при вирі
шенні багатоекстремальногозавдань, при цьому крім визначення глобальних екстремумів з'являється можливістьвиділити і ті локальні максимуми, значення яких близькі до глобальних.
4. Найбільш актуальні проблеми ГА і цікаві модифікаціїГА
Невдалий вибір упорядкування та кодування бітів в хромосоміможе спричинити передчасне сходження до локального оптимуму, ведучи алгоритм похибному шляху. Для подолання цього недоліку можна вибирати спосіб кодуваннягрунтуючись на додатковій інформації про завдання. Існують так само мобільні ГА,із змінною довжиною хромосом. Для деяких завдань таке подання природно,для інших треба вводити спеціальні правила читання хромосом. Замість оператора кросинговерувикористовуються оператори розрізання рядків (CUT), ймовірністьякого підвищується із збільшенням довжини рядка, і оператор зчеплення рядків (SPLICE),який вибирає з популяції два шматки і зчіплює їх в один шматок. Популяція представляєсобою сукупність пере-і недовизначених рядків. Правила читання таких рядків можутьбути, наприклад такими: в перевизначення рядку при читанні зліва направо не враховуютьсявже використані гени, а в недовизначених рядках відсутні місця запозичуютьсяу кращого елемента.
Проблема балансу дослідження нових областей і пристосуваннядо знайдених. Це необхідно для запобігання передчасної збіжності до локальногооптимуму. Використовуються модифіковані способи відбору хромосом в проміжнупопуляцію (відмова від імовірнісних принципів на користь елітного та відбору з витісненням)і вибору батьківської пари (випадковий, селективний, на основі близького чи далекогоспорідненості).
Цікаві результати може дати поєднання ГА з іншимиметодами. І на закінчення зупинимося на те, коли ж слід використовувати генетичніалгоритми. В одних обставин вони гарні, в інших - не дуже. У загальному випадкугенетичні алгоритми не знаходять оптимального рішення дуже важких завдань. Якщооптимальне рішення задачі (наприклад, ЗКВ з дуже великим числом міст) не можебути знайдено традиційними способами - наприклад, методом зчеплення гілок (branchand bound method), - то і генетичний алгоритм навряд чи знайде оптимум. З іншогобоку, цілком можливо, що генетичний алгоритм знайде достатньо хороше рішення.Зрештою, комівояжеру в будь-якому випадку треба їхати продавати свої товари, навітьякщо ми не впевнені в абсолютній оптимальності маршруту! Але є приклади, коли вдуже важких завданнях, в тому числі і в ЗКВ, за допомогою генетичних алгоритмів булиотримані дуже гарні рішення.
У двох випадках генетичні алгоритми дуже хороші. Першийвипадок: коли не відомий спосіб точного рішення задачі. Якщо ми знаємо, як оцінитипристосованість хромосом, то завжди можемо змусити генетичний алгоритм вирішуватицю задачу. Другий випадок: коли спосіб для точного рішення існує, але він дужескладний в реалізації, вимагає великих витрат часу і грошей, тобто, просто кажучи,справа того не варто. Приклад - створення програми для складання персонального розкладуна основі техніки покриття множин з використанням лінійного програмування.
Незважаючи на те, що конструювання хромосом і фітнес-функційможе вимагати значних зусиль, генетичні алгоритми легко реалізуютьсянавіть з нуля і здатні вирішувати широке коло завдань. Використовуючи аналогію з розвиткомживих організмів від простих форм до більш складних, генетичні алгоритми наблизилисядо того, щоб стати загальним методом вирішення завдань. Інші "пріродоподобние"парадигми, такі як моделювання відпалу (simulated annealing) і табу-пошук (taboosearch), теж дозволяють вирішувати аналогічні завдання.
5. Приклад ГА: Рішення діофантових рівнянь
Розглянемо диофантово (тільки цілі рішення)рівняння: a +2 b +3 c +4 d = 30, де a, b, c і d - деякі позитивні цілі. ЗастосуванняГА за дуже короткий час знаходить шукане рішення (a, b, c, d). Звичайно, Ви можетезапитати: чому б не використати метод грубої сили: просто не підставити всіможливі значення a, b, c, d (очевидно, 1 <= a, b, c, d <= 30)? АрхітектураГА-систем дозволяє знайти рішення швидше за рахунок більш 'осмисленого' перебору.Ми не перебираємо всі підряд, але наближаємося від випадково вибраних рішень до кращих.Для початку виберемо 5 випадкових рішень: 1 =
Таблиця 2: 1-е покоління хромосомі їх вміст
Хромосома
(a, b, c, d)
1
(1,28,15,3)
2
(14,9,2,4)
3
(13,5,7,3)
4
(23,8,16,19)
5
(9,13,5,2)
Щоб обчислити коефіцієнтивиживаності (fitness), підставимо кожне рішення у вираз a +2 b +3 c +4 d. Відстаньвід отриманого значення до 30 і буде потрібним значенням.
Таблиця 3: Коефіцієнти виживаностіпершого покоління хромосом (набору рішень)
Хромосома
Коефіцієнт виживаності
1
| 114-30 | = 84
2
| 54-30 | = 24
3
| 56-30 | = 26
4
| 163-30 | = 133
5
| 58-30 | = 28
Так як менші значення ближчедо 30, то вони більш бажані. У нашому випадку великі чисельні значення коефіцієнтіввиживаності підходять, на жаль, менше. Щоб створити систему, де хромосоми з більшпідходящими значе...
