Курсовая: Генетические алгоритмы
Министерство общего и профессионального образования
Российской Федерации
САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ИМЕНИ Н.Г.ЧЕРНЫШЕВСКОГО
Кафедра
Математической
кибернетики и компьютерных наук
Генетические алгоритмы
КУРСОВАЯ РАБОТА
студента 3 курса
факультета Компьютерных Наук и Информационных
Технологий Морозова Владимира Александровича
Научный
руководитель
заместитель заведующего кафедрой,
старший
преподаватель О.В.Емельянова
Зав. Кафедрой
член-корреспондент АТНУ,
доктор технических
наук,
профессор
Д.В.Сперанский
Содержание
Введение 3
Основная часть 4
Теоретическая часть 4
Общие сведения 4
Модели генетических алгоритмов 5
Практическая часть 10
Принцип работы программы 10
Листинг программы 11
Заключение 18
Список использованных источников 19
Введение
В настоящее время все более актуальными становятся задачи оптимизации,
поиска, реализации распределенных и (или) параллельных систем. Многие из них
легко реализуемы простыми математическими методами, но некоторые задачи
требуют к себе особого подхода. Эти задачи либо не разрешимы простыми
методами, либо их решение потребует значительного времени и объема ресурсов.
Для решения подобного рода задач существуют особые методы и алгоритмы. К их
числу относятся генетические алгоритмы.
Генетический алгоритм - это простая модель эволюции в природе, реализованная
в виде компьютерной программы. В нем используются как аналог механизма
генетического наследования, так и аналог естественного отбора.
Задача курсовой работы состоит в изучении генетических алгоритмов и
рассмотрении основных принципов решения задач с их помощью. Так же
реализовать решение задачи с использованием генетического алгоритма.
Основная часть
Теоретическая часть
Общие сведения
Эволюционная теория
утверждает, что каждый биологический вид целенаправленно развивается и
изменяется для того, чтобы наилучшим образом приспособиться к окружающей среде.
Можно сказать, что эволюция - это процесс оптимизации всех живых организмов.
Основной механизм эволюции - это естественный отбор. Его суть состоит в том,
что более приспособленные особи имеют больше возможностей для выживания и
размножения и, следовательно, приносят больше потомства, чем плохо
приспособленные особи. При этом благодаря передаче генетической информации (
генетическому наследованию) потомки наследуют от родителей основные их
качества. Таким образом, потомки сильных индивидуумов также будут относительно
хорошо приспособленными, а их доля в общей массе особей будет возрастать. После
смены нескольких десятков или сотен поколений средняя приспособленность особей
данного вида заметно возрастает. Схема генетического алгоритма приведена на
рисунке справа.
Вначале генерируется начальная популяция особей (индивидуумов), т.е.
некоторый набор решений задачи. Как правило, это делается случайным образом.
Затем необходимо смоделировать размножение внутри этой популяции. Для этого
случайно отбираются несколько пар индивидуумов, производится скрещивание
между хромосомами в каждой паре, а полученные новые хромосомы помещаются в
популяцию нового поколения. В генетическом алгоритме сохраняется основной
принцип естественного отбора Ч чем приспособленнее индивидуум (чем больше
соответствующее ему значение целевой функции), тем с большей вероятностью он
будет участвовать в скрещивании. Теперь моделируются мутации Ч в нескольких
случайно выбранных особях нового поколения изменяются некоторые гены. Затем
старая популяция частично или полностью уничтожается и мы переходим к
рассмотрению следующего поколения. Популяция следующего поколения в
большинстве реализаций генетических алгоритмов содержит столько же особей,
сколько начальная, но в силу отбора приспособленность в ней в среднем выше.
Теперь описанные процессы отбора, скрещивания и мутации повторяются уже для
этой популяции и т. д.
В каждом следующем поколении мы будем наблюдать возникновение совершенно
новых решений нашей задачи. Среди них будут как плохие, так и хорошие, но
благодаря отбору число хороших решений будет возрастать.
Мутация Ч это преобразование хромосомы, случайно изменяющее одну или
несколько ее позиций (генов). Наиболее распространенный вид мутаций Ч случайное
изменение только одного из генов хромосомы.
Кроссинговер (кроссовер или скрещивание) Ч это операция,
при которой из двух хромосом порождается одна или несколько новых хромосом.
Модели генетических алгоритмов
1. Canonical GA (J. Holland)
Данная модель алгоритма является классической. Она была предложена Джоном
Холландом в его знаменитой работе "Адаптация в природных и исусственных средах"
(1975). Часто можно встретить описание простого ГА (Simple GA, D.
Goldberg), он отличается от канонического тем, что использует либо рулеточный,
либо турнирный отбор. Модель канонического ГА имеет следующие характеристики:
з Фиксированный размер популяции.
з Фиксированная разрядность генов.
з Пропорциональный отбор.
з Особи для скрещивания выбираются случайным образом.
з Одноточечный кроссовер и одноточечная мутация.
з Следующее поколение формируется из потомков текущего поколения без
"элитизма". Потомки занимают места своих родителей.
2. Genitor (D. Whitley)
В данной модели используется специфичная стратегия отбора. Вначале, как и
полагается, популяция инициализируется, и её особи оцениваются. Затем
выбираются случайным образом две особи, скрещиваются, причем получается
только один потомок, который оценивается и занимает место наименее
приспособленной особи. После этого снова случайным образом выбираются 2
особи, и их потомок занимает место особи с самой низкой приспособленностью.
Таким образом, на каждом шаге в популяции обновляется только одна особь.
Подводя итоги можно выделить следующие характерные особенности:
з Фиксированный размер популяции.
з Фиксированная разрядность генов.
з Особи для скрещивания выбираются случайным образом.
з Ограничений на тип кроссовера и мутации нет.
з В результате скрещивания особей получается один потомок, который
занимает место наименее приспособленной особи.
3. Hybrid algorithm (L. "Dave" Davis)
Использование гибридного алгоритма позволяет объединить преимущества ГА с
преимуществами классических методов. Дело в том, что ГА являются робастными
алгоритмами, т.е. они позволяют находить хорошее решение, но нахождение
оптимального решения зачастую оказывается намного более трудной задачей в
силу стохастичности принципов работы алгоритма. Поэтому возникла идея
использовать ГА на начальном этапе для эффективного сужения пространства
поиска вокруг глобального экстремума, а затем, взяв лучшую особь, применить
один из "классических" методов оптимизации. Характеристики алгоритма:
з Фиксированный размер популяции.
з Фиксированная разрядность генов.
з Любые комбинации стратегий отбора и формирования следующего поколения
з Ограничений на тип кроссовера и мутации нет.
з ГА применяется на начальном этапе, а затем в работу включается
классический метод оптимизации.
4. Island Model GA
Представим себе следующую ситуацию. В некотором океане есть группа
близкорасположенных островов, на которых живут популяции особей одного вида.
Эти популяции развиваются независимо, и только изредка происходит обмен
представителями между популяциями. Островная модель ГА использует описанный
принцип для поиска решения. Вариант, безусловно, интересный и является одной
из разновидностей параллельных ГА. Данная модель генетического алгоритма
обладает следующими свойствами:
з Наличие нескольких популяций, как правило, одинакового
фиксированного размера.
з Фиксированная разрядность генов.
з Любые комбинации стратегий отбора и формирования следующего
поколения в каждой популяции. Можно сделать так, что в разных популяциях
будут использоваться разные комбинации стратегий, хотя даже один вариант дает
разнообразные решения на различных "островах".
з Ограничений на тип кроссовера и мутации нет.
з Случайный обмен особями между "островами". Если миграция будет
слишком активной, то особенности островной модели будут сглажены, и она будет
не очень сильно отличаться от моделей ГА без параллелизма.
5. CHC (Eshelman)
CHC расшифровывается как Cross-population selection, Heterogenous
recombination and Cataclysmic mutation. Данный алгоритм довольно быстро
сходится из-за того, что в нем нет мутаций, используются популяции небольшого
размера, и отбор особей в следующее поколение ведется и между родительскими
особями, и между их потомками. В силу этого после нахождения некоторого
решения алгоритм перезапускается, причем лучшая особь копируется в новую
популяцию, а оставшиеся особи подвергаются сильной мутации (мутирует примерно
треть битов в хромосоме) существующих и поиск повторяется. Еще одной
специфичной чертой является стратегия скрещивания: все особи разбиваются на
пары, причем скрещиваются только те пары, в которых хромосомы особей
существенно различны (хэммингово расстояние больше некоторого порогового плюс
возможны ограничения на минимальное расстояние между крайними различающимися
битами). При скрещивании используется так называемый HUX-оператор (Half
Uniform Crossover) - это разновидность однородного кроссовера, но в нем к
каждому потомку попадает ровно половина битов хромосомы от каждого родителя.
Таким образом, модель обладает следующими свойствами:
з Фиксированный размер популяции.
з Фиксированная разрядность генов.
з Перезапуск алгоритма после нахождения решения.
з Небольшая популяция.
з Особи для скрещивания разбиваются на пары и скрещиваются при условии
существенных отличий.
з Отбор в следующее поколение проводится между родительскими особями и
потомками.
з Используется половинный однородный кроссовер (HUX).
з Макромутация при перезапуске.
Практическая часть
В данной курсовой работе приведен пример программы использующей генетический
алгоритм. Программа создана посредством среды программирования Delphi 7 с
использованием библиотеки компонентов GeneBase 2.0. Алгоритм компонента
представляет собой применение методов, известных в теории эволюции, для
эвристического поиска решений переборных задач.
Принцип работы программы
Сразу при запуске программы еще перед прорисовкой окна выполняется процедура
FormCreate в которой производится инициализация внутренних переменных,
инициализация интерфейса и прорисовка изображения. Прорисовка изображения
проходит в процедуре CreateImage в два этапа: сначала необходимо рассчитать
образ на экране при помощи одной из трёх целевых функций; и только после
этого производится прорисовка посредством пикселей канвы объекта.
После этого программа переходит в режим ожидания во время которого вы можете
изменить такие параметры алгоритма как: количество особей, вероятности
кроссовера мутации и инверсии, разрядность генов, установить использование
стратегии элитизма, выбрать принцип поиска решений (по максимуму или по
минимуму значения целевой функции), выбрать саму целевую функцию и количество
эпох, на протяжении которых значение целевой функции не меняется, для
останова процесса обучения.
После выбора параметров нажатие на кнопку лПуск алгоритма приведет к
запуску основной процедуры программы btnStartClick. В первые моменты
выполнения программы происходит считывание установленных параметров в
переменные и поля объекта GA1, который является прототипом класса
TgeneticAlgorithm, тем самым этому объекту задаются основные параметры для
дальнейшей работы методов объекта. Затем вызывается метод Init объекта GA1 в
который производит начальную инициализацию особей, используемых в
генетическом алгоритме, случайными значениями. Переменные xCnt и xMaxCnt
предназначены для отслеживания ситуации останова алгоритма. Переменная xOldS
содержит значение приспособленности предыдущей, лучшей особи популяции. Затем
запускается основной цикл программы и в нем, после проверок возможных
ситуаций останова алгоритма, вызывается процедура OneEpoch объекта frmMain, в
которой вызывается метод OneEpoch объекта GA1. Вызов данного метода приводит
к выполнению одного шага генетического алгоритма. При этом производится
вычисление приспособленности всех особей из популяции, а на основании этих
данных формируется новая популяция. Далее происходит сравнивание
приспособленностей: лучшего индивида текущей и предыдущей популяций и в
случае малого различия наращивается переменная xCnt, а в противном случае Ц
обнуляется. Затем обновляется переменная xOldS и выводятся основные значения
лучшей особи текущей популяции.
Листинг программы
unit fmMain;
interface
uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
ExtCtrls, StdCtrls, genetic, math;
type
TTargetFunction = function(X1,X2 : double):double;
TfrmMain = class(TForm)
Panel1: TPanel;
Panel2: TPanel;
GroupBox1: TGroupBox;
GA1: TGeneticAlgorithm;
Label1: TLabel;
edtChromosomeCount: TEdit;
Label2: TLabel;
cbxGeneDegree: TComboBox;
Label3: TLabel;
edtCrossoverP: TEdit;
Label4: TLabel;
edtMutationP: TEdit;
Label5: TLabel;
edtInversionP: TEdit;
Label6: TLabel;
Label7: TLabel;
cbxOptimizeMethod: TComboBox;
Label8: TLabel;
cbxFunction: TComboBox;
imgFunction: TImage;
btnStart: TButton;
chbUseElitism: TCheckBox;
GroupBox2: TGroupBox;
Label9: TLabel;
Label10: TLabel;
stxTarget: TStaticText;
stxX: TStaticText;
stxY: TStaticText;
Label11: TLabel;
Label12: TLabel;
edtMaxCount: TEdit;
Label13: TLabel;
btnStop: TButton;
procedure FormCreate(Sender: TObject);
function GA1GetSutability(
Chromosome: TChromosome): Double;
procedure btnStartClick(Sender: TObject);
procedure cbxFunctionChange(Sender: TObject);
procedure btnStopClick(Sender: TObject);
private
{ Private declarations }
fTarget : TTargetFunction;
fImage : TBitmap;
public
{ Public declarations }
StopFlag : boolean;
procedure CreateImage;
property Target : TTargetFunction read fTarget write fTarget;
procedure OneEpoch;
end;
var
frmMain: TfrmMain;
xBmp : array [0..99,0..99] of double;
implementation
var
fMinX,fMaxX,fMinY,fMaxY : double;
{$R *.DFM}
function De_Jong_5(X1,X2:double):double;
var
J : integer;
xS1,xS2 : double;
begin
fMinX := -65.536;
fMinY := -65.536;
fMaxX := 65.536;
fMaxY := 65.536;
X1 := (X1*65.536*2)-65.536;
X2 := (X2*65.536*2)-65.536;
xS1 := 0;
for J := 1 to 25 do
begin
xS2 := power(X1 - 16*((J mod 5)-2),6)+
power(X2 - 16*((J div 5)-2),6);
xS1 := xS1 + 1/(J+xS2);
end;
Result := xS1 + 0.002;
end;
function Rasstrigin(X1,X2:double):double;
begin
fMinX := -5.12;
fMinY := -5.12;
fMaxX := 5.12;
fMaxY := 5.12;
X1 := (X1*5.12*2)-5.12;
X2 := (X2*5.12*2)-5.12;
Result := 20 + sqr(X1) + sqr(X2) - 10*cos(2*Pi*X1)-10*cos(2*Pi*X2);
end;
function Griewank(X1,X2:double):double;
begin
fMinX := -20;
fMinY := -20;
fMaxX := 20;
fMaxY := 20;
X1 := (X1*20*2)-20;
X2 := (X2*20*2)-20;
Result := 1/((sqr(X1)+sqr(X2))/200 - cos(X1)*cos(X2/sqrt(2))+2);
end;
procedure TfrmMain.CreateImage;
var
I,J : integer;
xMax,xMin : double;
xR,xG,xB : integer;
xVal : double;
begin
// рассчитываем образ на экране
for I:=0 to 99 do
for J:=0 to 99 do
begin
xBmp[I,J] := Target(I/100,J/100);
if (I=0) and (J=0) then
begin
xMax := xBmp[I,J];
xMin := xBmp[I,J];
end;
if xBmp[I,J] < xMin then
xMin := xBmp[I,J];
if xBmp[I,J] > xMax then
xMax := xBmp[I,J];
if xMax>1000 then
begin
xMax := xMax+1;
end;
end;
stxTarget.Caption := FloatToStr(xMax);
// а теперь рисуем картинку
for I := 0 to 99 do
for J := 0 to 99 do
begin
xB := 255-Round(255*(xBmp[I,J]-xMin)/(xMax-xMin));
xR := Round(255*(xBmp[I,J]-xMin)/(xMax-xMin));
if xB<128 then
xG := xB
else
xG := xB-128;
fImage.Canvas.Pixels[I,J] := RGB(xR,xG,xB);
end;
imgFunction.Picture.Assign(fImage);
end;
procedure TfrmMain.FormCreate(Sender: TObject);
begin
DecimalSeparator := '.';
// инициализируем интерфейс
cbxGeneDegree.ItemIndex := 1;
cbxOptimizeMethod.ItemIndex := 1;
cbxFunction.ItemIndex := 0;
// инициализируем внутренние переменные
fImage := TBitmap.Create;
fImage.Width := 100;
fImage.Height := 100;
frmMain.Target := De_Jong_5;
// рисуем первую картинку
CreateImage;
end;
function TfrmMain.GA1GetSutability(
Chromosome: TChromosome): Double;
var
X1,X2 : double;
begin
// рассчитываем приспособленность
X2 := Chromosome.GeneAsFloat[0];
X1 := Chromosome.GeneAsFloat[1];
Result := Target(X1,X2);
// рисуем хромосому
imgFunction.Canvas.Pixels[round(X1*100),round(X2*100)]:=RGB(255,255,255);
end;
procedure TfrmMain.btnStartClick(Sender: TObject);
var
I : integer;
xCnt : integer;
xOldS : double;
xMaxCnt : integer;
begin
// инициализируем все переменные
xMaxCnt := StrToInt(edtMaxCount.Text);
GA1.OptimizeMethod := TOptimizeMethod(cbxOptimizeMethod.ItemIndex);
GA1.UseElita := chbUseElitism.Checked;
GA1.Inversion_P := StrToFloat(edtInversionP.Text);
GA1.Mutation_P := StrToFloat(edtMutationP.Text);
GA1.Crossover_P := StrToFloat(edtCrossoverP.Text);
GA1.GeneDegree := TGeneDegree(cbxGeneDegree.ItemIndex);
GA1.ChromosomeCount := StrToInt(edtChromosomeCount.Text);
GA1.Init;
xOldS := 0;
xCnt := 0;
btnStart.Enabled := False;
btnStop.Enabled := True;
StopFlag := False;
for I := 0 to 1000000 do
begin
if xCnt >= xMaxCnt then
begin
Application.MessageBox(PChar(Format('Обучение остановлено'#10#13+
'Приспособленность не менялась в течении %d эпох',[xMaxCnt])),
'Завершение обучения',0);
break;
end;
if StopFlag then break;
OneEpoch;
if (abs(xOldS - GA1.BestChromosome.Suitability) < 1.0E-8) then
inc(xCnt)
else
xCnt := 0;
xOldS := GA1.BestChromosome.Suitability;
stxTarget.Caption := FloatToStr(GA1.BestChromosome.Suitability);
stxX.Caption := FloatToStr(GA1.BestChromosome.GeneAsFloat[0]*(fMaxX-
fMinX)+fMinX);
stxY.Caption := FloatToStr(GA1.BestChromosome.GeneAsFloat[1]*(fMaxY-
fMinY)+fMinY);
Application.ProcessMessages;
end;
btnStart.Enabled := True;
btnStop.Enabled := False;
end;
procedure TfrmMain.OneEpoch;
begin
imgFunction.Picture.Assign(fImage);
GA1.OneEpoch;
end;
procedure TfrmMain.cbxFunctionChange(Sender: TObject);
begin
case cbxFunction.ItemIndex of
0: Target := De_Jong_5;
1: Target := Rasstrigin;
2: Target := Griewank;
end;
CreateImage;
end;
procedure TfrmMain.btnStopClick(Sender: TObject);
begin
StopFlag := True;
end;
end.
Заключение
В данной курсовой работе была рассмотрена задача обучения нейронных сетей Ц
одна из классических задач генетических алгоритмов. Была использована
библиотека компонентов GeneBase 2.0 которая показала себя пригодной для
решения задач средней сложности с помощью генетических алгоритмов.
Список использованных источников
1)
4)
6)
7)
9) http://trubchaninoff.narod.ru/ssilki.htm
10)http://glossary.basegroup.ru/g/genetic-algorithm.htm
