15. Типи кодування інформації в генетичному алгоритмі

Типи кодування:

- бінарне - В классическом генетическом алгоритме применяется двоичное кодирование хромосом. Оно основано на известном способе записи десятичных чисел в двоичной системе, где каждый бит двоичного кода соответствует очередной степени цифры 2. Например, двоичная последовательность   представляет собой код числа  :

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

- арифметичне

- Шима (Shema) – шаблон, частина розрядів яких однакова, а інша може бути закодована

- код Грея - который характеризуется тем, что двоичные последовательности, соответствующие двум последовательным целым числам, отличаются только одним битом. Такой способ кодирования хромосом может оказаться оправданным при использовании операции мутации.

0 0000 1 0001

2 0011 3 0010

4 0110 5 0111 6 0101 7 0100

8 1100 9 1101

16. Типи вибору генетичного алгоритма

Батьківські пари можна вибирати такими способами:

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

Селективний - батьками можуть стати лише ті особи, значення пристосованості яких не менше порогової величини, наприклад середнього значення пристосованості по популяції. Порогова величина в селекції може бути обчислена різними способами. Тому в літературі для генетичного алгоритму виділяють різні варіації селекції:

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

• На базі колеса рулеки – чим вища оціночна функція тим більший сектор рулетки займає ті хромосоми.

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

• Ранжування –ділимо на декілька груп (не обов’язково) та ранжуємо по фітнес функції. За допомогою рангів обираємо кращіх представників.

У методі рулетки (roulette-wheel selection) особини відбираються за допомогою   «запусків» рулетки, де   — розмір популяції. Колесо рулетки містить по одному сектору для кожного члена популяції. Розмір   -го сектору пропорційний ймовірності попадання в нову популяцію  . При такому відборі члени популяції з більш високою пристосованістю з більшою ймовірністю будуть частіше вибиратись, ніж особини з низькою пристосованістю.

Популяція із 5 особин	Придатність	Ймовірність вибору
	52
	85
	37
	3
	23

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

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

Рошарняють фенотипний і генотипний інбрідінг та аутбрідінг. Генотипним (коли в якості відстані береться різниця значень цільової функції для відповідних особин) і фенотипним (в якості відстані береться відстань Хемінга).

 Відстань Геммінга дорівнює числу різних локусів (позицій генів в хромосомі) у бінарному рядку. Приклад визначення спорідненості бінарних хромосом при виборі батьківської пари для хромосоми 1010001 показаний в таблиці.

Хромосоми популяції	Кількість різних локусів
1000000	2
1010101	1
1111111	4
1100001	2