Изучение и анализ генетического алгоритма

Министерство образования и науки Республики Казахстан Карагандинский Государственный Технический Университет Кафедра: ВТ и ПО Лабораторная работа № 3

по дисциплине: «Проектирование интеллектуальных систем»

на тему: «Изучение и анализ генетического алгоритма»

Выполнил: ст. гр. ВТ — 10−2

Тулебаев А.

Приняла: Наумова А.В.

Караганда 2013

Изучение и анализ генетического алгоритма

Цель работы: изучить принцип работы генетического алгоритма, проверить его работу на функции согласно варианту на основе готовой программы.

Описание индивидуального задания. Для своего варианта необходимо:

найти экстремум заданной функции в определённой области поиска;

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

На примере выборочных поколений продемонстрировать графически нахождение экстремума функции [фитнес-функция=f (x₁)]:

на каждом выборочном поколении эволюции необходимо вычислить координату x1 всех хромосом данного поколения;

вывести на экран все точки одним цветом, а x_оптим другим;

вывести значения фитнес-функции и всех координат точки x_оптим;

на следующем выборочном поколении необходимо удалить с экрана все точки, кроме x_оптим, и вывести на экран все точки нового поколения;

соединить линией x_оптим предыдущего поколения с x_оптим текущего;

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

Рассмотрим исследуемую функцию F=5-x1*x2-x2-x3*x4*x5. Согласно диапазону поиска каждая координата (х₁, х₂, х₃, х₄, х₅) изменяется в пределах от — 12 до 12.

Функция F является суммой 4 слагаемых: 5, — x1*x2, — x2, — x3*x4*x5. Для получения максимума функции каждое слагаемое (в идеале) должно быть положительным и максимальным по модулю.

Исходя из этого получаем:

х₂=-12; х₁=12; х₃=-12; х₄=х₅=12.

Откуда F_max=5−12* (-12) — (-12) — (-12) *12*12=5+144+12+1728=1889.

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

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

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

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

Хромосома () в случае многопараметрической функции будет представлять координату точки на многопараметрической функции, а ген () координату точки на одном параметре функции (₁ это ген, представляющий координату точки на параметре 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).

Выводы

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

при увеличении требуемого % индивидуумов с максимальной фитнес-функцией в поколении (Max_хром, %) увеличивается требуемое число поколений эволюции. При слишком большом % возможно зацикливание — из-за мутаций и скрещивания такого количества особей никогда не наберется;

чем больше вероятность мутаций (P_m), тем больше вероятность зацикливания, однако при маленькой P_m эволюция замедляется и число поколений растет;

при увеличении объема элиты (, %) уменьшается разница между поколениями — эволюция замедляется и число поколений растет.