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

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

1. Алгоритм: понятия и свойства

Алгоритм (от латинской формы имени среднеазиатского математика аль-Хорезми) — правило действий, последовательность проведения вычислительных операций, способ нахождения искомого результата.

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

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

Понятие алгоритма — одно из основных в программировании и информатике. Это последовательность команд, предназначенная исполнителю, в результате выполнения которой он должен решить поставленную задачу. Алгоритм должен описываться на формальном языке, исключающем неоднозначность толкования. Исполнитель может быть человеком или машиной. Исполнитель должен уметь выполнять все команды, составляющие алгоритм. Множество возможных команд конечно и изначально строго задано. Действия, выполняемые по этим командам, называются элементарными.

Запись алгоритма на формальном языке называется программой. Иногда само понятие алгоритма отождествляется с его записью, так что слова «алгоритм» и «программа» — почти синонимы. Небольшое различие заключается в том, что под алгоритмом, как правило, понимают основную идею его построения. Программа же всегда связана с записью алгоритма на конкретном формальном языке.

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

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

Б. Понятность — алгоритм не должен содержать предписаний, смысл которых может восприниматься исполнителем неоднозначно, т. е. запись алгоритма должна быть настолько четкой и полной, чтобы у исполнителя не возникало потребности в принятии каких-либо самостоятельных решений. Алгоритм всегда рассчитан на выполнение «не размышляющего» исполнителя. Алгоритм составляется из команд, входящих в СКИ.

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

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

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

Д. Массовость — алгоритм пригоден для решения любой задачи из некоторого класса задач, т. е. алгоритм правильно работает на некотором множестве исходных данных, которое называется областью применимости алгоритма.

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

2. Генетические алгоритмы. Основные понятия

2.1 Понятие генетического алгоритма. Общие понятия

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

В частности, генетические алгоритмы:

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

В) Используют только целевую функцию, и не ее производные либо иную дополнительную информацию.

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

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

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

1. Популяция — это конечное множество особей.

2. Особи, входящие в популяцию, в генетических алгоритмах представляются хромосомами с закодированными в них множествами параметров задачи, то есть решений, которые иначе называются точками в пространстве поиска (search points). В некоторых работах особи называются организациями.

3. Хромосомы (цепочки или кодовые последовательности) — это упорядоченные последовательности генов.

4. Ген (свойство, знак или детектором) — это атомарный элемент генотипа, в частности, хромосомы.

5. Генотип или структура — это набор хромосом данной особи. Следовательно особями популяции могут быть генотипы либо единичные хромосомы.

6. Фенотип — это набор значений, соответствующих данному генотипу, то есть декодированная структура или множество параметров задачи (решение, точка пространства поиска).

7. Аллель — это набор значений конкретного гена, также определяемое как значение свойства или вариант свойства

8. Локус или позиция указывает место размещения данного гена в хромосоме (цепочке). Множество позиций генов — это локи.

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

Очередная популяция в генетическом алгоритме называется поколением, а к вновь создаваемой популяции особей применяется термин «новое поколение» или «поколение потомков».

2.3 Пример простейшей программы

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

Шаг 1: генерируется начальная популяция, состоящая из N особей со случайными наборами признаков.

Шаг 2 (борьба за существование): вычисляется абсолютная приспособленность каждой особи популяции к условиям среды f (i) и суммарная приспособленность особей популяции, характеризующая приспособленность всей популяции. Затем при пропорциональном отборе для каждой особи вычисляется ее относительный вклад в суммарную приспособленность популяции P_s(i), т. е. отношение ее абсолютной приспособленности f (i) к суммарной приспособленности всех особей популяции (3):

В выражении (3) сразу обращает на себя внимание возможность сравнения абсолютной приспособленности i-й особи f (i) не с суммарной приспособленностью всех особей популяции, а со средней абсолютной приспособленностью особи популяции (4):

Тогда получим (5):

Если взять логарифм по основанию 2 от выражения (5), то получим количество информации, содержащееся в признаках особи о том, что она выживет и даст потомство (6).

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

Поскольку количество потомства особи пропорционально ее приспособленности, то естественно считать, что если это количество информации:

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

— равно нулю, то особь доживает до половозрелого возраста, но потомства не дает (его численность равна нулю);

— меньше нуля, то особь погибает до достижения половозрелого возраста.

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

Это накопление информации происходит на различных уровнях иерархии популяции, как системы, включающей:

— элементы системы: отдельные особи;

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

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

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

Шаг 3: начало цикла смены поколений.

Шаг 4: начало цикла формирования нового поколения.

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

Шаг 6 (кроссовер): отобранные для продолжения рода на предыдущем шаге особи с заданной вероятностью P_c подвергаются скрещиванию или кроссоверу (рекомбинации).

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

Если кроссовер не происходит, то исходные особи — несостоявшиеся родители, переходят на стадию мутации.

Шаг 7 (мутация): выполняются операторы мутации. При этом признаки потомков с вероятностью P_m случайным образом изменяются на другие. Отметим, что использование механизма случайных мутаций роднит генетические алгоритмы с таким широко известным методом имитационного моделирования, как метод Монте-Карло.

Шаг 8 (борьба за существование): оценивается приспособленность потомков (по тому же алгоритму, что и на шаге 2).

Шаг 9: проверяется, все ли отобранные особи дали потомство.

Если нет, то происходит переход на шаг 5 и продолжается формирование нового поколения, иначе — переход на следующий шаг 10.

Шаг 10: происходит смена поколений:

— потомки помещаются в новое поколение;

— наиболее приспособленные особи из старого поколения переносятся в новое, причем для каждой из них это возможно не более заданного количества раз;

— полученная новая популяция замещает собой старую.

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

Если ГА сошелся, то это означает, что решение найдено, т. е. получено поколение, идеально приспособленное к условиям данной фиксированной среды обитания.

3. Практическое применение генетического алгоритма

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

Каждая переменная кодируется 20 битами. Расчеты провести для 40 и 80 поколений, сравнить полученные результаты при размерах популяции 8, 12 и 20 особей.

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

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

3.1 Запуск программы и получения результатов

Текст основной программы предоставлен в приложении, А При выполнении программы были получены следующие результаты — минимум функции за 20 прогонов (таблица 1) и среднее значение минимума за 20 циклов (таблица 2)

Таблица 1 — Минимум функции

Заключение

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

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

При выполнении данного курсового проекта учитывали, что решение задачи является подверженным влиянию случайных величин. Поэтому запуск основной программы был реализован в цикле — 20 раз. Одновременно с этим вычислили среднее значение минимума за эти 20 циклов.

Каждая переменная кодируется 20 битами. Расчеты проводились для 40 и 80 поколений. Проведем анализ полученных данных. Самый лучший результат получился при числе поколений — 40 и числе особей — 20. Минимальное значение функции min=0.320 289 227. Среднее значение функции =0.87 630 460 526.

Увеличение количества поколений, показало что при одних и тех же условиях, результат полученный при количестве поколений равный 40, лучше. Это можно объяснить тем, что алгоритм используя свои механизмы, находит лучшее решение с каждым последующим поколением, т. е. использует «накопленный опыт».

Таким образом, меняя размер популяции, тем самым увеличив количество геномов и кол-во поколений для нахождения решения, пробуем найти средний минимум функции. Увеличение геномов в работе алгоритма, дает более приближенный результат при решении задачи, полученные значения стремятся к 0, и с увеличением популяции это выглядит все нагляднее.

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

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

Список источников

1. http://www.genon.ru

2. Исаев С. «Популярно о генетических алгоритмах». http://home.od.ua/~relayer/algo/neuro/ga-pop/

3. Алексей Андреев. «Электродарвин». http://www.fuga.ru/articles/2004/03/genetic-pro.htm

4. Сотник С. Л. Конспект лекций по курсу «Основы проектирования систем искусственного интеллекта»: (1997;1998), http://neuroschool.narod.ru/books/sotnik.html.

Приложение А

Текст программы

program sga;

uses crt;

const

maxpop = 20;

maxstring = 20;

dim = 2; {размерность пространства поиска}

type

allele = boolean;

{Алель — позиция в битовой строке}

chromosome = array [1.maxstring*dim] of allele;

{битовая строка}

fenotype = array [1.dim] of real;

individual = record

chrom:chromosome;

{генотип = битовая строка}

x:fenotype; {фенотип = массив вещественных координат точки в пространстве поиска}

fitness:real; {значение целевой функции}

end;

population = array [1.maxpop] of individual;

const

xmax:fenotype=(2. 048,2.048);

{массив максимальных значений для координат точки в пространстве поиска}

xmin:fenotype=(-2.048, — 2.048);

{массив минимальных значений для координат точки в пространстве поиска}

var

minBest, minSum, minAverage: real;

count3, nProgon: byte; {счетчики}

oldpop, newpop, intpop: population;

{Три непересекающихся популяции — старая, новая и промежуточная}

popsize, lchrom, flchrom, gen, maxgen: integer;

{Глобальные целые переменные}

pcross, pmutation: real;

{глобальные вещественные переменные}

min:real; {Статистические вещественные}

{Вероятностные процедуры}

function random_:real;

begin

random_:= random (65 535)/(65 535−1);

end;

function flip (probability:real):boolean;

{подбрасывание монетки — true если орел}

begin

if probability = 1.0 then

flip:= true

else

flip:= (random_ <= probability);

end;

function rnd (low, high: integer):integer;

{Случайный выбор между low и high}

var

i:integer;

begin

if low >= high then

i:= low

else begin

i:= trunc (random_ * (high-low+1) + low);

if i > high then i:= high;

end;

rnd:= i;

end;

{интерфейсные процедуры: decode and objfunc}

function objfunc (x:fenotype):real;

var me: real;

begin

me:= x[1]*x[1] - x[2];

me:= me*me*100;

objfunc:= me+(1-x[1])*(1-x[1]);

end;

procedure decode (chrom:chromosome; lbits: integer; var x: fenotype);

{Декодирование строки в массив вещественных координат точки в пространстве поиска — true=1, false=0}

var

i, j: integer;

f, accum, powerof2: real;

begin

for i:=1 to dim do begin

accum:= 0.0;

powerof2:= 1;

f:=1;

for j:= 1+lbits*(i-1) to lbits+lbits*(i-1) do begin

if chrom[j] then accum:= accum + powerof2;

powerof2:= powerof2 * 2;

f:=f*2;

end;

x[i]: = xmin[i]+(xmax[i] - xmin[i])*accum/(f-1)

end

end;

{Расчет статистических величин: statistics}

procedure statistics (popsize:integer; var min: real;

var pop: population);

{Расчет статистик популяции}

var

j:integer;

begin

{Инициализация}

min:= pop[1]. fitness;

{Цикл для min}

for j:= 2 to popsize do with pop[j] do begin

if fitness

min:= fitness;

end;

{Новое значение min}

end;

end;

{Процедура инициализации initpop}

procedure initpop;

{Инициализация начальной популяции случайным образом}

var

j, j1: integer;

begin

for j:= 1 to popsize do with oldpop[j] do begin

for j1:= 1 to lchrom*dim do chrom[j1]: = flip (0.5);

{Бросок монетки}

decode (chrom, lchrom, x);

{Декодирование строки}

fitness:= objfunc (x);

{Вычисление начальных значений функции пригодности}

end;

end;

{3 генетических оператора: отбора (select), скрещивания (crossover) и мутации (mutation)}

procedure select;

{процедура выбора}

var

ipick:integer;

procedure shuffle (var pop: population);

{процедура перемешивания популяции в процессе отбора}

var

i, j: integer;

ind0:individual;

begin

for i:= popsize downto 2 do begin

j:= random (i-1)+1;

ind0:=pop[i];

pop[i]:=pop[j];

pop[j]:=ind0;

end;

end;

function select₁:integer;

var

j1, j2, m: integer;

begin

if (ipick>popsize) then

begin

shuffle (oldpop);

ipick:=1

end;

j1:=ipick;

j2:=ipick+1;

if (oldpop[j2]. fitness

m:=j2

else

m:=j1;

ipick:=ipick+2;

select₁:=m;

end;

var

j:integer;

begin

ipick:=1;

for j:=1 to popsize do begin

intpop[j]: =oldpop [select₁];

end;

oldpop:=intpop;

end;

procedure mutation (var chrom: chromosome);

{двухточечная мутация с вероятностью pmutation}

var

mutate:boolean;

point1, point2: integer;

temp:boolean;

begin

mutate:= flip (pmutation);

{Flip the biased coin}

if mutate then begin

repeat

point1:= rnd (1, flchrom);

point2:= rnd (1, flchrom);

until point1 <> point2;

temp:=chrom[point1];

chrom[point1]:=chrom[point2];

chrom[point2]:=temp;

{обмен двух элементов}

end;

end;

procedure crossover (var parent1, parent2, child1, child2: chromosome);

{равномерное скрещивание 2 родительских строк, результат помещается в 2 строках-потомках}

var

j:integer;

begin

if flip (pcross) then begin

for j:= 1 to flchrom do begin

if flip (0.5) then begin

child1 [j]: = parent1 [j];

child2 [j]: = parent2 [j];

end else begin

child1 [j]: = parent2 [j];

child2 [j]: = parent1 [j];

end;

end;

mutation (child1);

mutation (child2);

end;

end;

{Процедура создания нового поколения: generation}

procedure generation;

{Генерирование нового поколения при помощи отбора, скрещивания и мутации}

{Прим: предполагается, что популяция имеет четный размер}

var

j, mate1, mate2: integer;

begin

select;

j:= 1;

repeat

{выполняются отбор, скрещивание и мутация, пока полностью не сформируется новая популяция — newpop}

mate1:= j;

{выбор родительской пары}

mate2:= j+1;

{скрещивание и мутация — мутация вставлена в процедуру скрещивания}

crossover (oldpop[mate1]. chrom, oldpop[mate2]. chrom,

newpop[j].chrom, newpop [j + 1]. chrom);

{Декодирование строки и вычисление пригодности}

with newpop[j] do begin

decode (chrom, lchrom, x);

fitness:= objfunc (x);

end;

with newpop [j+1] do begin

decode (chrom, lchrom, x);

fitness:= objfunc (x);

end;

j:= j + 2;

until j>popsize

end;

procedure output;

begin

writeln ('Размер популяции-', popsize, ' число поколений-', maxgen);

writeln ('Лучшее значение минимума-', minBest:14:14);

writeln ('Среднее значение минимума-', minAverage:14:14);

writeln;

end;

begin {Главная программа}

clrscr;

{Инициализация генератора случайных чисел}

randomize;

lchrom:=20; {число битов на один кодируемый параметр}

flchrom:=lchrom*dim;

pmutation:=0.01; {вероятность мутации}

pcross:=0.9; {вероятность скрещивания}

for count3:=1 to 3 do begin

case count3 of

1:popsize:=8;

2:popsize:=12;

3:popsize:=20; {размер популяции 8,12,20 особей}

end;

maxgen:=40; {число поколений}

while maxgen<=80 do begin

minSum:=0;

for nProgon:=1 to 30 do begin {30 прогонов}

initpop;

statistics (popsize, min, oldpop);

if nProgon=1 then minBest:=min;

gen:= 0; {Установка счетчика поколений в 0}

repeat {Главный итерационный цикл}

gen:= gen + 1;

generation;

statistics (popsize, min, newpop);

oldpop:= newpop; {переход на новое поколение}

until (gen >= maxgen);

if min

minSum:=minSum+min;

end; {next progon}

minAverage:=minSum/nProgon; {среднее значение min}

output;

maxgen:=maxgen+40;

end;

end; {next popsize (count3)}

writeln ('PRESS ANY KEY');

repeat until keypressed;

end. {End главной программы}