Генетический алгоритм-ргр2-ver3 (Расчётно-графическая работа №2 (полностью сделанная))
Описание файла
Файл "Генетический алгоритм-ргр2-ver3" внутри архива находится в папке "rgr2". Документ из архива "Расчётно-графическая работа №2 (полностью сделанная)", который расположен в категории "". Всё это находится в предмете "автоматизированные информационно-управляющие системы (аиус)" из 6 семестр, которые можно найти в файловом архиве МПУ. Не смотря на прямую связь этого архива с МПУ, его также можно найти и в других разделах. Архив можно найти в разделе "остальное", в предмете "автоматизированные информационно-управляющие системы (аиус)" в общих файлах.
Онлайн просмотр документа "Генетический алгоритм-ргр2-ver3"
Текст из документа "Генетический алгоритм-ргр2-ver3"
Генетический алгоритм
Генетический алгоритм— это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путем последовательного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию.
Случайным образом создаётся некоторое количество начальных векторов («начальная популяция»). Они оцениваются с использованием «функции приспособленности», в результате чего каждому вектору присваивается определённое значение («приспособленность»), которое определяет вероятность выживания организма, представленного данным вектором. После этого с использованием полученных значений приспособленности выбираются вектора (селекция), допущенные к «скрещиванию».
Особи следующего поколения также оцениваются, затем производится селекция, применяются генетические операторы и т. д. Так моделируется «эволюционный процесс», продолжающийся несколько жизненных циклов (поколений), пока не будет выполнен критерий остановки алгоритма. Таким критерием может быть:
-
нахождение глобального, либо субоптимального решения;
-
исчерпание числа поколений, отпущенных на эволюцию;
-
исчерпание времени, отпущенного на эволюцию.
Генетические алгоритмы применяются для решения следующих задач:
-
Оптимизация функций
-
Оптимизация запросов в базах данных
-
Разнообразные задачи на графах (задача коммивояжера, раскраска, нахождение паросочетаний)
-
Настройка и обучение искусственной нейронной сети
-
Задачи компоновки
-
Составление расписаний
-
Игровые стратегии
-
Теория приближений
-
Искусственная жизнь
-
Биоинформатика (свёртывание белков)
Пример реализации генетического алгоритма
Найти значения параметров 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 |
Анализируя показатели «здоровья» популяций приходим к заключению, что генетический алгоритм приводит к увеличению среднего значения показателя «здоровья» популяций.
Таким образом, показан пример реализации генетического алгоритма