36247

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

Доклад

Информатика, кибернетика и программирование

Некоторым обычно случайным образом создаётся множество генотипов начальной популяции. Таким образом можно выделить следующие этапы генетического алгоритма: Задать целевую функцию приспособленности для особей популяции Создать начальную популяцию Начало цикла Размножение скрещивание Мутирование Вычислить значение целевой функции для всех особей Формирование нового поколения селекция Если выполняются условия останова то конец цикла иначе начало цикла. Создание начальной популяции Перед первым шагом нужно...

Русский

2013-09-21

57.5 KB

1 чел.

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

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

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

При выборе «функции приспособленности» важно следить, чтобы её «рельеф» был «гладким».

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

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

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

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

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

  1.  Задать целевую функцию (приспособленности) для особей популяции
  2.  Создать начальную популяцию
  •  (Начало цикла)
  1.  Размножение (скрещивание)
  2.  Мутирование
  3.  Вычислить значение целевой функции для всех особей
  4.  Формирование нового поколения (селекция)
  5.  Если выполняются условия останова, то (конец цикла), иначе (начало цикла).

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

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

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

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

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

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

Мутации

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

Отбор

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

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

  1.  Оптимизация функций
  2.  Оптимизация запросов в базах данных
  3.  Разнообразные задачи на графах (задача коммивояжера, раскраска, нахождение паросочетаний)
  4.  Настройка и обучение искусственной нейронной сети
  5.  Задачи компоновки
  6.  Составление расписаний
  7.  Игровые стратегии
  8.  Теория приближений
  9.  Искусственная жизнь
  10.  Биоинформатика (фолдинг белков)
  11.  

Пример тривиальной реализации на C++

Поиск в одномерном пространстве, без скрещивания.

#include <algorithm>

#include <iostream>

#include <numeric>

#include <cstdlib>

#include <ctime>

 

 

int main()

{

   ::std::srand((unsigned int)::std::time(NULL));

   const size_t N = 1000;

   int a[N] = { 0 };

   for ( ; ; )

   {

       //мутация в случайную сторону каждого элемента:

       for ( size_t i = 0 ; i < N ; ++i )

           if ( ::std::rand() % 2 == 1 )

               a[i] += 1;

           else

               a[i] -= 1;

       //теперь выбираем лучших, отсортировав по возрастанию...

       ::std::sort(a, a+N);

       //... и тогда лучшие окажутся во второй половине массива.

       //скопируем лучших в первую половину, куда они оставили потомство, а первые умерли:

       ::std::copy(a+N/2, a+N,    a);

       //теперь посмотрим на среднее состояние популяции. Как видим, оно всё лучше и лучше.

       ::std::cout << ::std::accumulate(a, a+N, 0) / N << ::std::endl;


 

А также другие работы, которые могут Вас заинтересовать

81666. Философская критика (Д.В.Веневитинов, И.В.Киреевский и др.). Литературно-критическая и журналистская деятельность Надеждина 37.23 KB
  Манна философская предоснова восприятия искусства строго говоря присущая любой художественной теории в том числе классицизму романтизму и т. здесь уже ощущается недостаточной и уступает место целенаправленному включению искусства в философское наукоучение. Высокую оценку Галича получали идеи натурфилософии Шеллинга понимание природы как целесообразного целого где происходит взаимодействие противоположно направленных сил и основные положения шеллинговой философии искусства: представление о самоценности искусства об идеале как...
81667. А.С. Пушкин как литературный критик. Проблематика его литературно-критических статей и заметок; жанровое, стилевое своеобразие. Типологический анализ одной из работ 35.6 KB
  Его статьи и художественные произведения становились итогом долгих и основательных раздумий о самых разнообразных теоретических проблемах художественного творчества о предмете и назначении искусства о взаимосвязи писателя и общества об историзме и народности литературы роли критики в развитии эстетического вкуса читателей путях становления русского литературного языка и т. В многообразном по своему составу литературнокритическом наследии Пушкина есть и опыты больших историколитературных обобщений незавершенная статья О ничтожестве...
81668. Творчество А. С. Пушкина в критике разных эпох. Сравнительный типологический анализ статей В. Г. Белинского (8-я, 9-я, из цикла «Сочинения Александра Пушкина»), Д. И. Писарева («Пушкин и Белинский»), Д. С. Мережковского («Пушкин») 39.06 KB
  Пушкина в критике разных эпох. Белинского 8я 9я из цикла Сочинения Александра Пушкина Д. Вообще творчеству Пушкина Белинский посвящает огромное количество критических статей и сочинений. Обратимся к 89 статьям сочинения Александра Пушкина.
81669. Литературно-критическое тв-во Н.В.Гоголя. Типологический анализ одной из статей 40.33 KB
  Статья Плетнева Чичиков или Мертвые души Гоголя опубликованная в июльском номере Современника за 1842 г. Плетнев как и Белинский ставил Гоголя в первый ряд среди современных писателей отмечая удивительную верность автора действительности. В произведениях Гоголя П. Вяземский решительно противился тому что именем Гоголя теоретики натуральной школы пытались придать ей идейную и эстетическую целостность.
81670. Особенности развития литературной критики в 1840-е гг. Литер.критика «Отечественных записок». Славянофильская критика. Литературно-критическая позиция журнала «Современник» 34.72 KB
  Анненков определялись противостоянием двух сформировавшихся на рубеже 1830 1840х годов течений русской общественной мысли западничества и славянофильства. отстаивали необходимость исторического движения России по европейскому пути выдвигали на первый план идею свободы и самоценности человеческой личности подчеркивали исчерпанность тех начал которые составляли основу древнерусской жизни. – публиковали свои статьи на страницах Москвитянина Московских литературных и ученых сборниковРусской беседы выступили против перенесения...
81671. Понятие о литературной критике, ее происхождение. Значение термина «критика» 28.26 KB
  Значение термина критика. В широком общекультурном смысле литературная критика обозначение восходящей к глубокой древности филологической рефлексии по поводу любого словесно-организованного текста. В современной западной культуре понятия литературная наука и литературная критика часто совпадают и употребляются на правах синонимов. В специальном литературоведческом смысле закрепленном отечественной гуманитарной традицией литературная критика род литературно-творческой и литературно-коммуникативной деятельности направленной на...
81672. Природа и предмет литературной критики. Взаимодействие критики с различными отраслями искусства и науки. Соотношение критики и литературоведения. Основные функции критики 31.97 KB
  Литературная критика двойственна по своей природе. Литературная критика естественно соотносится со многими областями науки и культуры: с филологией философией историей эстетикой герменевтикой культурологией психологией социологией книговедением с публицистикой и журналистикой с критикой художественное музыкальной театральной с кинокритикой телевизионной критикой и др. Испытывая непосредственное влияние близких или смежных гуманитарных сфер литературная критика в слою очередь способствует их развитию. Литературная критика одна...
81673. Типология литературной критики с точки зрения субъекта критической деятельности 38.99 KB
  Для критики словесного искусства нужны люди которые бы показывали бессмыслицу отыскивания мыслей в художественном произволении м постоянно руководили бы читателем в том бесконечном лабиринте сцеплений в котором и состоит сущность искусства и к тем законам которые служат основанием этих сцеплений. Сопряжение собственного эстетического опыта и литературной неизведанности явленной в оцениваемых словеснохудожественных произведениях одна из постоянно одолеваемых сложностей профессиональной литературной критики. Лидеров профессиональной...
81674. Типология литературной критики с точки зрения ее соотношения с определенными литературными направлениями 33.54 KB
  эстетические взгляды критика; Его соц. Классицистическая критика. Ломоносов Тредиаковский Сумароков Державин Херасков Лукин Плавильщиков Сентименталистская критика.Реакционная критика лагеря официальной народности.