19. Генетичний алгоритм. Загальна схема генетичного алгоритма.

Генети́чний алгори́тм (англ. genetic algorithm) — це еволюційний алгоритм пошуку, що використовується для вирішення задач оптимізації і моделювання шляхом послідовного підбору, комбінування і варіації шуканих параметрів з використанням механізмів, що нагадують біологічну еволюцію. Задача кодується таким чином, щоб її вирішення могло бути представлено в вигляді масиву подібного до інформації складу хромосоми. Цей масив часто називають саме так «хромосома». Випадковим чином в масиві створюється деяка кількість початкових елементів «осіб», або початкова популяція. Особи оцінюються з використанням функції пристосування, в результаті якої кожній особі присвоюється певне значення пристосованості, яке визначає можливість виживання особи. Після цього з використанням отриманих значень пристосованості вибираються особи допущені до схрещення (селекція). До осіб застосовується "генетичні оператори" (в більшості випадків це оператор схрещення (crossover) і оператор мутації (mutation), створюючи таким чином наступне покоління осіб. Особи наступного покоління також оцінюються застосуванням генетичних операторів і виконується селекція і мутація. Так моделюється еволюційний процес, що продовжується декілька життєвих циклів (поколінь), поки не буде виконано критерій зупинки алгоритму. Таким критерієм може бути:

• знаходження глобального, або надоптимального вирішення;

• вичерпання числа поколінь, що відпущені на еволюцію;

• вичерпання часу, відпущеного на еволюцію.

Генетичні алгоритми можуть використатися для пошуку рішень в дуже великих і тяжких просторах пошуку.

Можна виділити такі етапи генетичного алгоритму:

1. Створення початкової популяції:

2. Обчислення функції пристосованості для осіб популяції (оцінювання)

3. Повторювання до виконання критерію зупинки алгоритму:

1. Вибір індивідів із поточної популяції (селекція)

2. Схрещення або/та мутація

3. Обчислення функції пристосовуваності для всіх осіб

4. Формування нового покоління

20. Генетична операція «кроссовер».

Предположим, что все особи зашифрованы в виде битовых строк. Если в размножении участвуют два предка, то такая операция называется кроссовером и состоит в формировании новой строки из частей строк родителей. Для двух строк одинаковой длины и результатом кроссовера с маской является строка , которая определяется как:

В зависимости от маски:

- одноточечный кроссовер[1111.0000]

- двухточечный кроссовер[000.111.0]

- однородный кроссовер

В маске нули и единицы распределяются случайным образом.X=[011011] Y=[001101] M=[001110] Z=[001011]

Допустим требуется закодировать несколько правил. Требуется скрестить две строки длиной l1n и l2n, n-длина правила, l1, l2-количество правил. В результате новое правило с длиной l3n. Если использовать двухточечный кроссовер и выбираем случайно 2 точки первой гипотезы, то во второй гипотезе нужно выбирать такие точки, чтобы расстояние от левой точки до левого края правила, а также расстояние от правой точки до правого края правила было таким же. Кроссовер осуществляется путем перестановки.

[01.1001 0011.01] l1n

[001101 11.10.10 010011] l2n

[011001]

[001101 111001 001110 010011]