Участник:Kilkavteste 607: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
(Новая страница: «== Свойства и структура алгоритма == === Общее описание алгоритма ===»)
 
Строка 2: Строка 2:
  
 
=== Общее описание алгоритма ===
 
=== Общее описание алгоритма ===
 +
'''Генетический алгоритм''' - широко применяемый метод исследования в самых разных сферах науки: математике, биологии, компьютерном обучении и во многих других. Существует бесконечное множество реализаций данного алгоритма, в зависимости от поставленной задачи. Алгоритм основан на таких природных явлениях, как скрещивание, селекция, мутация и кроссинговер.
 +
Задача формализуется таким образом, чтобы её решение могло быть закодировано в виде вектора («генотипа») генов, где каждый ген может быть битом, числом или неким другим объектом. В классических реализациях генетического алгоритма (ГА) предполагается, что генотип имеет фиксированную длину. Однако существуют вариации ГА, свободные от этого ограничения.
 +
Некоторым, обычно случайным, образом создаётся множество генотипов начальной популяции. Они оцениваются с использованием «функции приспособленности», в результате чего с каждым генотипом ассоциируется определённое значение («приспособленность»), которое определяет насколько хорошо фенотип, им описываемый, решает поставленную задачу.
 +
При выборе «функции приспособленности» (или fitness function в англоязычной литературе) важно следить, чтобы её «рельеф» был «гладким».
 +
Из полученного множества решений («поколения») с учётом значения «приспособленности» выбираются решения (обычно лучшие особи имеют большую вероятность быть выбранными), к которым применяются «генетические операторы» (в большинстве случаев «скрещивание» — crossover и «мутация» — mutation), результатом чего является получение новых решений. Для них также вычисляется значение приспособленности, и затем производится отбор («селекция») лучших решений в следующее поколение.
 +
 +
Этот набор действий повторяется итеративно, так моделируется «эволюционный процесс», продолжающийся несколько жизненных циклов (поколений), пока не будет выполнен критерий остановки алгоритма. Таким критерием может быть:
 +
*нахождение глобального, либо субоптимального решения;
 +
*исчерпание числа поколений, отпущенных на эволюцию;
 +
*исчерпание времени, отпущенного на эволюцию.
 +
 +
Генетические алгоритмы служат, главным образом, для поиска решений в многомерных пространствах поиска.
 +
 +
Таким образом, можно выделить следующие этапы генетического алгоритма:
 +
 +
*Задать целевую функцию (приспособленности) для особей популяции
 +
*Создать начальную популяцию
 +
 +
*(Начало цикла)
 +
 +
**Размножение (скрещивание)
 +
**Мутирование
 +
**Вычислить значение целевой функции для всех особей
 +
**Формирование нового поколения (селекция)
 +
**Если выполняются условия остановки, то (конец цикла), иначе (начало цикла).

Версия 22:19, 10 октября 2017

1 Свойства и структура алгоритма

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

Генетический алгоритм - широко применяемый метод исследования в самых разных сферах науки: математике, биологии, компьютерном обучении и во многих других. Существует бесконечное множество реализаций данного алгоритма, в зависимости от поставленной задачи. Алгоритм основан на таких природных явлениях, как скрещивание, селекция, мутация и кроссинговер. Задача формализуется таким образом, чтобы её решение могло быть закодировано в виде вектора («генотипа») генов, где каждый ген может быть битом, числом или неким другим объектом. В классических реализациях генетического алгоритма (ГА) предполагается, что генотип имеет фиксированную длину. Однако существуют вариации ГА, свободные от этого ограничения. Некоторым, обычно случайным, образом создаётся множество генотипов начальной популяции. Они оцениваются с использованием «функции приспособленности», в результате чего с каждым генотипом ассоциируется определённое значение («приспособленность»), которое определяет насколько хорошо фенотип, им описываемый, решает поставленную задачу. При выборе «функции приспособленности» (или fitness function в англоязычной литературе) важно следить, чтобы её «рельеф» был «гладким». Из полученного множества решений («поколения») с учётом значения «приспособленности» выбираются решения (обычно лучшие особи имеют большую вероятность быть выбранными), к которым применяются «генетические операторы» (в большинстве случаев «скрещивание» — crossover и «мутация» — mutation), результатом чего является получение новых решений. Для них также вычисляется значение приспособленности, и затем производится отбор («селекция») лучших решений в следующее поколение.

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

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

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

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

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