Page 34 - 4521
P. 34
1.7.4 Гібридний алгоритм
Ідея гібридних алгоритмів (Hybrid algorithms) полягає
в поєднанні генетичного алгоритму з деяким іншим класичним
методом пошуку, відповідним в даному завданні. У кожному
поколінні всі нащадки, що згенерували, оптимізуються вибра-
ним методом і потім заносяться у нову популяцію. Тим самим
виходить, що кожна особина в популяції досягає локального
оптимуму, поблизу якого вона знаходиться. Далі проводяться
звичайні для ГА дії: відбір батьківських пар, кросинговер і
мутації. На практиці гібридні алгоритми виявляються дуже
вдалими. Це пов'язано з тим, що вірогідність попадання однієї
з особин в область глобального максимуму зазвичай велика.
Після оптимізації така особина буде рішенням задачі. Відомо,
що генетичний алгоритм здатний швидко знайти у всій області
пошуку хороші рішення, але він може зазнавати труднощі в
отриманні з них якнайкращих. Звичайний оптимізаційний ме-
тод може швидко досягти локального максимуму, але не може
знайти глобальний. Поєднання двох алгоритмів дозволяє вико-
ристовувати переваги обидвох.
1.7.5 CHC
CHC (Eshelman, 1991) розшифровується як Cross-
population selection, Heterogeneous recombination and Cataclys-
mic mutation. Даний алгоритм досить швидко сходиться через
те, що в ньому немає мутацій, наступних за оператором кро-
синговера, використовуються популяції невеликого розміру, і
відбір особин в наступне покоління ведеться і між батьківсь-
кими особинами, і між їх нащадками. У даному методі для
кросинговера вибирається випадкова пара, але не допускаєть-
ся, щоб між батьками була маленька хеммінгова відстань або
мала відстань між крайніми бітами, що розрізняються. Для
схрещування використовується різновид однорідного кросове-
ра HUX (Half Uniform Crossover), при якому нащадкові пере-
ходить рівно половина бітів кожного батька. Для нового поко-
ління вибираються N кращих різних особин серед батьків і
33
