Расчётно-графическая работа №2 (полностью сделанная) (Генетический алгоритм-ргр2-ver3)

Посмотреть архив целиком

Генетический алгоритм

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


Случайным образом создаётся некоторое количество начальных векторов («начальная популяция»). Они оцениваются с использованием «функции приспособленности», в результате чего каждому вектору присваивается определённое значение («приспособленность»), которое определяет вероятность выживания организма, представленного данным вектором. После этого с использованием полученных значений приспособленности выбираются вектора (селекция), допущенные к «скрещиванию».

Особи следующего поколения также оцениваются, затем производится селекция, применяются генетические операторы и т. д. Так моделируется «эволюционный процесс», продолжающийся несколько жизненных циклов (поколений), пока не будет выполнен критерий остановки алгоритма. Таким критерием может быть:

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

  • исчерпание числа поколений, отпущенных на эволюцию;

  • исчерпание времени, отпущенного на эволюцию.


Генетические алгоритмы применяются для решения следующих задач:

  1. Оптимизация функций

  2. Оптимизация запросов в базах данных

  3. Разнообразные задачи на графах (задача коммивояжера, раскраска, нахождение паросочетаний)

  4. Настройка и обучение искусственной нейронной сети

  5. Задачи компоновки

  6. Составление расписаний

  7. Игровые стратегии

  8. Теория приближений

  9. Искусственная жизнь

  10. Биоинформатика (свёртывание белков)

















Пример реализации генетического алгоритма


Дана функция 2

Найти значения параметров x,y,z,которые являются максимируемыми


В данном случае хромосомы построены из трех генов. Создадим фонд хромосом, в котором будет использоваться генетический алгоритм.


ХРОМОСОМА

ГЕНЫ

ЗДОРОВЬЕ’’


X

Y

Z


Cо

2

1

-1

4

С1

0

-1

4

6

С2

1

0

-4

6

С3

-1

2

0

1



Проанализировав текущие значения функции f(x,y,z) можно сделать вывод, что наиболее слабой популяцией является популяция с набором хромосом С3.

На основании показателей «здоровья» алгоритм выбирает хромосомы С1 и С2,

а в качестве второй пары родителей алгоритмом выбирается С1, и Cо





















Составим таблицу для новых популяций



ХРОМОСОМА

ГЕНЫ

ЗДОРОВЬЕ’’


X

Y

Z


Cо(Xc0,Yc1,Zc2)

2

-1

-4

6

С1(Xc0,Yc2,Zc1)

2

0

4

36

С2(Xc1,Yc0,Zc2)

0

1

-4

6

С3(Xc1,Yc2,Zc0)

0

0

-1

1

С4(Xc2,Yc0,Zc1)

1

1

4

36

С5(Xc2,Yc1,Zc0)

1

-1

-1

1



Анализируя показатели «здоровья» популяций приходим к заключению, что генетический алгоритм приводит к увеличению среднего значения показателя «здоровья» популяций.

Таким образом, показан пример реализации генетического алгоритма


Случайные файлы

Файл
23710-1.rtf
10940-1.rtf
Bilety.doc
83947.rtf
168817.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.