Контрольная работа по "Программированию"

Решение

Порядок действий:

Для использования генетического алгоритма необходимо:

1. Определить набор ПРИЗНАКОВ, характеризующих РЕШЕНИЕ ЗАДАЧИ оптимизации или моделирования.
2. Определить ФЕНОТИП, закодировать ПРИЗНАКИ (можно использовать код Грея).

2)  Использовать последовательность шагов генетического алгоритма с соответствующими операторами.

1. ФЕНОТИП (задаем для 5 ПРИЗНАКОВ десятичные значения случайным образом)

2. Формируем начальную ПОПУЛЯЦИЮ

Предположим, что ОСОБЬ содержит любые 2 ПРИЗНАКА из заданных 5:    

• два первых ПРИЗНАКА - значения первого критерия,

три последних ПРИЗНАКА – значения второго критерия

Особь 1: 00111110 Особь 6: 00111110

Особь 2: 11001110 Особь 7: 11000111

Особь 3: 00111001 Особь 8: 00110111

Особь 4: 11001001 Особь 9: 10101010

Особь 5: 00110111 Особь 10: 01010101

→ Получили: каждая ОСОБЬ длиной по 8 БИТ

3. Оценка ОСОБЕЙ

 Оценка особей популяции (используется фитнесс-функция равная сумме бит в особи).

Среднее значение суммы бит в популяции = 3,6.

4. Отбор – «РУЛЕТКА» с принципом «элитизма»

4.1 Строим «рулетку» - сектора должны быть пропорциональны значениям приспособленности:

[pic 1]

4.2 Запускаем «рулетку» 8 раз и выбираем 4 пары

[pic 2]

Получили:

следующие 4 пары:

1 и 5,

7 и 5,

10 и 2,

8 и 6

5. Скрещивание – оператор «одноточечный кроссовер»

Выбираем две точки разрыва (случайным образом, но числа должны различаться хотя бы на 2 и не быть равными 1 или длине особи): 2 и 5 и применяем оператор к выбранным парам особей:

Особь 1: 0011|1110 Особь 2.1: 0011|0111