Создание начальной популяции

Содержание

1. Возможности генетических алгоритмов3

2. Эффективность генетических алгоритмов14

3. Особенности генетических алгоритмов20

4. Выводы22

Возможности генетических алгоритмов

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

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

Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.

Описание алгоритма

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

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

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

Фенотип — совокупность характеристик, присущих индивиду на определённой стадии развития. Фенотип формируется на основе генотипа.

Из полученного множества решений («поколения») с учётом значения «приспособленности» выбираются решения (обычно лучшие особи имеют большую вероятность быть выбранными), к которым применяются «генетические операторы» (в большинстве случаев «скрещивание» — crossover и «мутация» — mutation), результатом чего является получение новых решений. Для них также вычисляется значение приспособленности, и затем производится отбор («селекция») лучших решений в следующее поколение.

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

• Нахождение глобального решения;
• Исчерпание числа поколений, отпущенных на эволюцию;
• Исчерпание времени, отпущенного на эволюцию.

Таким образом, можно выделить следующие этапы генетического алгоритма:

1. Задать целевую функцию (приспособленности) для особей популяции

2. Создать начальную популяцию

• (Начало цикла)

1. Размножение (скрещивание)

2. Мутирование

3. Вычислить значение целевой функции для всех особей

4. Формирование нового поколения (селекция)

5. Если выполняются условия остановки, то (конец цикла), иначе (начало цикла).

Создание начальной популяции

Перед первым шагом нужно случайным образом создать начальную популяцию; даже если она окажется совершенно неконкурентоспособной, вероятно, что генетический алгоритм всё равно достаточно быстро переведёт её в жизнеспособную популяцию. Таким образом, на первом шаге можно особенно не стараться сделать слишком уж приспособленных особей, достаточно, чтобы они соответствовали формату особей популяции, и на них можно было подсчитать функцию приспособленности (Fitness). Итогом первого шага является популяция H, состоящая из N особей.

 

Отбор (селекция)

На этапе отбора нужно из всей популяции выбрать определённую её долю, которая останется «в живых» на этом этапе эволюции. Есть разные способы проводить отбор. Вероятность выживания особи h должна зависеть от значения функции приспособленности Fitness(h). Сама доля выживших s обычно является параметром генетического алгоритма, и её просто задают заранее. По итогам отбора из N особей популяции H должны остаться sN особей, которые войдут в итоговую популяцию H'. Остальные особи погибают.

 

· Турнирная селекция - сначала случайно выбирается установленное количество особей (обычно две), а затем из них выбирается особь с лучшим значением функции приспособленности

 

·
Метод рулетки - вероятность выбора особи тем вероятнее, чем лучше её значение функции приспособленности p i = f i ∑ i = 1 N f i {\displaystyle p_{i}={\frac {f_{i}}{\sum _{i=1}^{N}{f_{i}}}}}

 

где p_i p i {\displaystyle p_{i}} - вероятность выбора i особи,

f_i f i {\displaystyle f_{i}} - значение функции приспособленности для i особи,

N N {\displaystyle N} - количество особей в популяции.

· Метод ранжирования - вероятность выбора зависит от места в списке особей отсортированном по значению функции приспособленности p i = 1 N (a − (a − b) i − 1 N − 1) {\displaystyle p_{i}={\frac {1}{N}}(a-(a-b){\frac {i-1}{N-1}})}

 

,

где , a ∈ [ 1, 2 ] {\displaystyle a\in [1,2]}

b = 2 − a {\displaystyle b=2-a} i {\displaystyle i} i - порядковый номер особи в списке особей отсортированном по значению функции приспособленности.

 

· Равномерное ранжирование - вероятность выбора особи определяется выражением:

где параметр метода.

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

где

 

f_avg - среднее значение целевой функции для всей популяции, σ - среднеквадратичное отклонение значения целевой функции.

 

Выбор родителей

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

Можно выделить несколько операторов выбора родителей:

1. Панмиксия - оба родителя выбираются случайно, каждая особь популяции имеет равные шансы быть выбранной

2. Инбридинг - первый родитель выбирается случайно, а вторым выбирается такой, который наиболее похож на первого родителя

3. Аутбридинг - первый родитель выбирается случайно, а вторым выбирается такой, который наиболее не похож на первого родителя

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

Размножение (Скрещивание)

Размножение в разных алгоритмах определяется по-разному — оно, конечно, зависит от представления данных. Главное требование к размножению — чтобы потомок или потомки имели возможность унаследовать черты обоих родителей, «смешав» их каким-либо способом.

Почему особи для размножения обычно выбираются из всей популяции H, а не из выживших на первом шаге элементов H' (хотя последний вариант тоже имеет право на существование)? Дело в том, что главный бич многих генетических алгоритмов — недостаток разнообразия (diversity) в особях. Достаточно быстро выделяется один-единственный генотип, который представляет собой локальный максимум, а затем все элементы популяции проигрывают ему отбор, и вся популяция «забивается» копиями этой особи. Есть разные способы борьбы с таким нежелательным эффектом; один из них — выбор для размножения не самых приспособленных, но вообще всех особей. Однако такой подход вынуждает хранить всех существовавших ранее особей, что увеличивает вычислительную сложность задачи. Поэтому часто применяют методы отбора особей для скрещивания таким образом, чтобы «размножались» не только самые приспособленные, но и другие особи, обладающие плохой приспособленностью. При таком подходе для разнообразия генотипа возрастает роль мутаций.

Мутации

К мутациям относится все то же самое, что и к размножению: есть некоторая доля мутантов m, являющаяся параметром генетического алгоритма, и на шаге мутаций нужно выбрать mN особей, а затем изменить их в соответствии с заранее определёнными операциями мутации.

Недостатки

Существует несколько поводов для критики насчёт использования генетического алгоритма по сравнению с другими методами оптимизации:

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

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

 

 

Пример 1

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

1. Сначала пропорциональный отбор назначает каждой особи вероятность, которая равна отношению её приспосабливаемости к суммарной приспосабливаемости популяции:

Потом происходит отбор (с замещением) всех n особей для дальнейшей генетической обработки, согласно величины P_i.

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

После отбора, n отобранных особей случайным способом разбиваются на n/2 пари. Для каждой пары с вероятностью P_c может выполнятся кросинговер. С вероятностью 1-P_c кросинговер может не произойти и неизмененные особи переходят в стадию мутации. Если кросинговер происходит, полученные потомки заменяют собой родителей и переходят к мутации.

2. Кросинговер это операция, при которой с двух хромосом порождается одна или несколько новых хромосом. Одноточечный кросинговер работает так: сначала, случайным образом выбирается одна с I-1 точек разрыва (участок между соседними битами в рядку).

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

Например, допустим, один родитель состоит с 10 нулей, а другой с 10 единиц. Пусть с 9 возможных точек разрыва выбрана точка 3. Родители и их потомки показаны ниже.

Родитель1 0000000000 000~0000000 --> 111~0000000 1110000000 Потомок1

Родитель2 1111111111 111~1111111 --> 000~1111111 0001111111 Потомок2

После того как заканчивается стадия кросинговера, выполняются операции мутации.

3. Мутация – это преобразование хромосомы, которое случайно изменяет одну или несколько её позиций (генов). Распространенный вид мутаций - это случайная замена только одного гена с хромосомы.

В каждом рядке, который подвергается мутации, случайный бит с вероятностью P_m изменяется на противоположный.

4. Популяция, полученная после мутации заменяет старую и цикл одного поколения оканчивается. Следующие поколения обрабатываются подобным образом: отбор, кросинговер и мутация.

 

 

 

Пример 2

Рассмотрим функцию f(х) = 2х² +1 (1.1) и предположим что х принимает целое значение с интервала от 0 до 15. Задача оптимизации этой функции состоит в перемещении в пространстве с 16 точками со значениями 0,…,15 для определения точки, в которой функция принимает максимальное (или минимальное) значение.

В таком случае в роли параметра задачи выступает переменная х. Множество {0,1,…,15} составляет пространство поиска и одновременно – множество потенциальных решений задачи. Каждое из 16 чисел, которые принадлежат этому множеству, называется точкой пространства поиска, решением, значение параметра, фенотипом. Решение, которое оптимизирует функцию, называется наилучшим или оптимальным решением. Значение параметра х можно закодировать следующим способом:

0000 0001 0010 0011 0100 0101 0110 0111

1000 1001 1010 1011 1100 1101 1110 1111

Это широко известный способ двоичного кодирования, связанный с записью десятичных чисел в двоичной системе. Представленные кодовые комбинации также называются цепочками или хромосомами. В рассматриваемом пример они выступают и в качестве генотипов. Каждая из хромосом состоит из 4х генов. Значение гена в конкретной позиции называется алелью, которая принимает в данном случае значение 0 или 1.

Популяция состоит из особей, которые выбираются из этих 16 хромосом. Примером популяции с численностью 6 может быть, например, множество хромосом {0010, 0101, 0111, 1001, 1100, 1110}, которые представляют собой закодированную форму таких фенотипов: {2, 5, 7, 9, 12, 14}. Функция приспосабливаемости задается таким выражением:

f(х) = 2х² +1.

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