Суть генетического алгоритма

Генетические алгоритмы оптимизации

ГА моделирует процессы природной эволюции и относятся к глобальным методам поиска.

ГА обладают следующими свойствами:

  1. Поиск решения с помощью ГА основан на оптимизации случайно заданного не одного, а множества решений.
  2. ГА относятся к эвристическим методам оптимизации, поскольку он гарантирует нахождение строгого решения: это решение либо близко к глобальному, либо субоптимальное.
  3. При реализации ГА материалами исследования являются закодированные структуры (символьные модели), а не совокупность параметров объекта.
  4. Для оценки пригодности решения используется специальная функция – функция полезности (фитнесса). Одновременно с её введением формируется "правило выживания решений".
  5. В процессе поиска решений используются вероятностные, а не детерминированные характер вывода условий для отбора решений на каждом шаге.
  6. ГА позволяет устранить недостатки BP.

 

 

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

Генетическим алгоритмом называется следующий объект:

ГА( Р°, r, l, sl, Fit, cr, m),

где ГА – генетический алгоритм;

Р° – исходная популяция;

r – количество элементов популяции;

l – длина битовой строки, кодирующей решение;

sl – оператор селекции;

Fit – функция фитнесса (функция полезности), определяющая «пригодность» решения;

cr - оператор кроссинговера, определяющий возможность получения нового решения;

m – оператор мутации;

ot – оператор отбора.

Будем считать, что область поиска решения D задачи однокритериального выбора является конечным множеством решений, в котором каждое допустимое решение XD является n-мерным вектором .

Наименьшей неделимой единицей биологического вида является особь (k – номер особи, t – момент времени эволюционного процесса).

Аналог особи в задаче оптимизации: произвольное допустимое решение XD ().

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

Интерпретация качественных признаков проводится в терминах хромосомной наследственности.

В качестве гена (единицы наследственного материала, ответственного за формирование альтернативных признаков особи) принимается бинарная комбинация h.

h определяет фиксированное значение параметра xi в двоичном коде.

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

Тогда структуру битовой строки можно интерпретировать хромосомой, содержащей п сцепленных между собой генов.

Локус – местоположение i-го гена в хромосоме.

Аллель h – значение i-го гена в хромосоме.

Хромосома, содержащая в своих локусах конкретные значения генов, называется генотипом (генетическим кодом). Генотип содержит всю наследственную генетическую информацию об особи. Конечное множество всех допустимых генотипов называют генофондом.

При взаимодействии особи с внешней средой ее генотип порождает фенотип.

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

Фитнесс Fit() каждой особи равен численному значению функции J(X), вычисленной для допустимого решения XD (). Чем больше значение функции финтесса при решении задачи нахождения max J(X), тем лучше особь приспособлена к внешней среде.

 

Генетический алгоритм используется в тех случаях, когда:

  1. необходимо найти один или несколько глобальных экстремумов;
  2. представление параметров описания объектов может быть как в непрерывном, так и в дискретном (или даже в словесном) виде.

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

ГА относится к эвристическим методам, так как его сходимость в математическом смысле для всех типов задач не доказана.

 

Схема генетического алгоритма