Задание на лабораторную работу

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное автономное образовательное учреждение
высшего образования

«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ»

ИНСТИТУТ НЕПРЕРЫВНОГО И ДИСТАНЦИОННОГО ОБРАЗОВАНИЯ

КАФЕДРА 43

ОЦЕНКА

ПРЕПОДАВАТЕЛЬ


должность, уч. степень, звание		подпись, дата		инициалы, фамилия

ОТЧЕТ О ЛАБОРАТОРНОЙ РАБОТЕ №1

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

по дисциплине: ЭВОЛЮЦИОННАЯ МЕТОДОЛОГИЯ В ПРОГРАММНОЙ ИНЖЕНЕРИИ

РАБОТУ ВЫПОЛНИЛ(А)

СТУДЕНТ(КА) ГР.	Z7430m		А.С. Хромцова
	номер группы	подпись, дата	инициалы, фамилия
Студенческий билет №	2017/2649

Санкт-Петербург 2019

Общие сведения

ГА используют принципы и терминологию, заимствованные у биологической науки – генетики. В ГА каждая особь представляет потенциальное решение некоторой проблемы. В классическом ГА особь кодируется строкой двоичных символов – хромосомой, каждый бит которой называется геном. Множество особей – потенциальных решений составляет популяцию. Поиск (суб)оптимального решения проблемы выполняется в процессе эволюции популяции - последовательного преобразования одного конечного множества решений в другое с помощью генетических операторов репродукции, кроссинговера и мутации.

ЭВ используют следующие механизмы естественной эволюции:

1) Первый принцип основан на концепции выживания сильней-

ших и естественного отбора по Дарвину, который был сформулирован им в

1859 году в книге «Происхождение видов путем естественного отбора».

Согласно Дарвину особи, которые лучше способны решать задачи в своей

среде, выживают и больше размножаются (репродуцируют). В генетиче-

ских алгоритмах каждая особь представляет собой решение некоторой

проблемы. По аналогии с этим принципом особи с лучшими значениями

целевой (фитнесс) функции имеют большие шансы выжить и репродуци-

ровать. Формализация этого принципа, как мы увидим далее, дает опера-

тор репродукции.

2) Второй принцип обусловлен тем фактом, что хромосома по-

томка состоит из частей полученных из хромосом родителей. Этот прин-

цип был открыт в 1865 году Менделем. Его формализация дает основу для

оператора скрещивания (кроссинговера).

3) Третий принцип основан на концепции мутации, открытой в

1900 году де Вре. Первоначально этот термин использовался для описания

существенных (резких) изменений свойств потомков и приобретение ими

свойств, отсутствующих у родителей. По аналогии с этим принципом гене-

тические алгоритмы используют подобный механизм для резкого измене-

ния свойств потомков и тем самым, повышают разнообразие (изменчи-

вость) особей в популяции (множестве решений).

Эти три принципа составляют ядро ЭВ. Используя их, популяция

(множество решений данной проблемы) эволюционирует от поколения к

поколению.

Эволюцию искусственной популяции – поиска множества решений некоторой проблемы формально можно описать алгоритмом, который представлен на рис.1.1. ГА берет множество параметров оптимизационной проблемы и кодирует их последовательностями конечной длины в некотором конечном алфавите (в простейшем случае двоичный алфавит «0» и «1») .

Предварительно простой ГА случайным образом генерирует начальную популяцию стрингов (хромосом). Затем алгоритм генерирует следующее поколение (популяцию), с помощью трех основных генетических операторов:

1) Оператор репродукции (ОР);

2) Оператор скрещивания ( кроссинговера, ОК);

3) Оператор мутации (ОМ).

Генетические операторы являются математической формализацией приведенных выше трех основополагающих принципов Дарвина, Менделя и де Вре естественной эволюции. ГА работает до тех пор, пока не будет выполнено заданное количество поколений (итераций) процесса эволюции или на некоторой генерации будет получено заданное качество или вследствие преждевременной сходимости при попадании в некоторый локальный оптимум.

В каждом поколении множество искусственных особей создается с использованием старых и добавлением новых с хорошими свойствами. Генетические алгоритмы - не просто случайный поиск, они эффективно используют информацию накопленную в процессе эволюции. В отличие от других методов оптимизации ГА оптимизируют различные области пространства решений одновременно и более приспособлены к нахождению новых областей с лучшими значениями целевой функции за счет объединения квазиоптимальных решений из разных популяций.

Цель работы

Изучение простого генетического алгоритма.

Задание на лабораторную работу

1. Разработать простой генетический алгоритм для нахождения оптимума

заданной по варианту функции одной переменной (максимум).

cos(x-0.5)/abs(x) x [-10,0),(0,10] , min

2. Исследовать зависимость времени поиска, числа поколений (генераций),