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

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

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

Хромосома () в случае многопараметрической функции будет представлять координату точки на многопараметрической функции, а ген () координату точки на одном параметре функции (₁ это ген, представляющий координату точки на параметре x₁, ₂ на x₂ и т.д.). Соответственно число генов (n) равно числу параметров функции.

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

Разобьём каждую координату на 2 точек. Соответственно максимальное значение гена будет = 2. Это означает, что ген будет представлен битами (-двоичная длина гена). Двоичная длина хромосомы будет = *n. Все комбинации этого числа будут представлять допустимое решение задачи.

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

Приведём основные параметры генетического алгоритма:

- размер популяции особей.

- размер элиты (количество элитных хромосом).

- двоичный размер гена.

n - количество генов.

P_m - вероятность мутации в гене.

P - поколение (P⁰ - нулевое поколение, P¹ - первое и т.д.).

А так же условия для выхода:

Max_хром - число хромосом с максимальной фитнесс-функцией.

Max_покол - число поколений с одинаковым значением максимальной фитнесс-функции (приспособленности особи).

Структура "Генетического алгоритма”:

1. Формирование начальной популяции P⁰ из особей :

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

Особи образуют начальную популяцию P^t для поколения t=0.

2. Выбор элиты поколения (применение элитарного подхода).

Для каждой особи поколения происходит вычисление её фитнесс-функции (приспособленности).

Выбор определённого процента набора особей с максимальной приспособленностью, которые копируются и дополняют собой популяцию. Они не будут подвергаться скрещиванию.

3. Воспроизводство "потомков” с наследственными признаками "родителей”:

Выбор конкретной "родительской” пары для участия в процессе размножения. (Сначала берётся 1-я и (/2+1) - я особь, затем 2-я и (/2+2) - я особь и т.д., пока не скрестятся все особи.).

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

Обмен частями хромосом (части образовались после разрыва хромосом) и построение их "потомков”, сохраняющих наследственные признаки "родителей”.

Вычисления повторяются с шага 3.1 до тех пор, пока не будут скрещены все особи, т.е. произойдёт /2 скрещиваний (т.к. элита не подвергается скрещиванию).

4. Мутагенез, приводящий к генетическим изменениям "родительских” признаков:

Мутации подвергается всё поколение, включая элиту. В каждой особи каждый ген с заданной вероятностью P_m подвергается мутации. (Обычно эта вероятность берётся маленькой - P_m=0,010,001)

Если ген должен подвергнутся мутации, то происходит следующее: Генерируется случайное число в пределах от 0 до 2, и это число, заменяет собой мутируемый ген.

Вычисления повторяются с шага 4.1 до тех пор, пока не будет подвержено мутации всё поколение.

5. Естественный отбор:

Всё поколение подвергается естественному отбору. Для каждой особи поколения происходит вычисление её фитнесс-функции (приспособленности).

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

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

Запуск рулетки производится раз. Из выбранных особей формируется новое поколение Рⁱ⁺¹

6. Проверка условий окончания процесса эволюции популяции P.

Условия:

Если число поколений t не превысило заданноё число T_min, то вычисления будут продолжаться в любом случае.

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

Если число поколений, в которых вычисляется одна и та же максимальная фитнесс-функция также превысит определённый заданный порог Max_покол.

Если количество поколений t превысит заданное число T_max (t>T_max).

Выводы