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

Министерство образования и науки Республики Казахстан Карагандинский Государственный Технический Университет Кафедра САПР Пояснительная записка к курсовой работе по дисциплине: «Прикладная теория систем»

Тема: «Генетический алгоритм»

Цель работы

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

Задача:

Разработать программу реализации генетического алгоритма в соответствии с выданным вариантом. Для разработки использовать любую визуальную среду программирования.

В интерфейсе программы предусмотреть возможность ввода параметров:

объём популяции;

число поколений;

коэффициент скрещивания;

коэффициент мутации;

для дифференциального кроссовера коэффициенты k, c;

для задачи коммивояжёра ввод [4. .40] числа городов и их расстановку вручную и автоматически;

для биологической задачи возможность ввода названий характеристик [10.15], их значений [4. .40], значимости и веса [0.1] каждой характеристики.

Результаты работы программы должны включать:

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

лучшее значение фитнес-функции за все поколения и соответствующую ей структуру особи;

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

для задачи коммивояжёра на каждом поколении графически отображать лучщий маршрут.

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

Вариант задания:

Тип задачи — коммивояжёр

Выбор пары — панмиксия

Кроссовер — двухточечный

Мутация — перестановка

Отбор — элитный

Критерий останова — количество поколений

Выходные данные — карта.

Анализ результатов моделирования на основе разработанной программы представляется в виде таблицы:

Вывод:

Анализируя полученные результаты моделирования приходим к выводу, что оптимальным количеством маршрутов можно считать 200, число поколений, нет необходимости повторять алгоритм больше 500 раз (поколений), чтобы получить хороший результат. Также на значение фитнес-функции влияет коэффициент скрещивания: оптимальный коэффициент скрещивания — 1, коэффициент мутации также играет большую роль в моделировании генетического алгоритма, оптимальный коэффициент мутации — 0,1. Как видно из таблицы самое лучшее значение фитнес-функции, а значит самое минимальное расстояние за которое можно объехать 20 городов, получают за счет параметров, которые указаны в таблице в строке под номером 15.

Руководство пользователя.

Для того, чтобы открыть программу необходимо мышью дважды кликнуть по файлу «Коммивояжёр. exe». Также необходимо проверить наличие графического документа под названием «map. bmp» в исходной папке (месте).

На экране монитора появится главное окно программы, как показано на Рис. 1

Рис. № 1 Главное окно программы В данной программе города можно задавать как вручную, для этого необходимо на карте кликнуть мышью в нужном месте, так и автоматически. Чтобы задать города автоматически необходимо в правом верхнем углу окна программы выбрать «Задать города автоматически» как показано на рис. № 2.

Рис. № 2

Затем ниже необходимо ввести количество городов и нажать на кнопку «Сгенерировать города». При необходимости можно очистить поле ввода городов, т. е. удалить имеющиеся города на карте нажав кнопку «Удалить города» .

После того, как на карте будут отмечены необходимое количество городов (4−40), для того, чтобы застить алгоритм поиска минимального пути необходимо нажать кнопку «Поиск». Процент выполнения моделирования представлен ProgressBar-ом, который находится под картой рис. № 3.

Рис № 3. ProgressBar

По окончанию моделирования, а это произойдет тогда, когда ProgressBar полностью заполнится синим цветом, результат отобразится под ProgressBar-ом рис. № 4.

Рис. № 4 Результат моделирования Также на карте будет прорисован самый оптимальный маршрут рис. № 5.

Рис. № 5 Оптимальный маршрут

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

Рис. № 6. Изменяемые параметры

Листинг программы

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, ExtCtrls;

type

TForm1 = class (TForm)

Image1: TImage;

Button1: TButton;

Edit1: TEdit;

Label1: TLabel;

Edit2: TEdit;

Label2: TLabel;

Edit3: TEdit;

Label3: TLabel;

Edit4: TEdit;

Label4: TLabel;

Edit5: TEdit;

Label5: TLabel;

procedure Image1MouseDown (Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

procedure Image1Click (Sender: TObject);

procedure FirstGeneration (Sender: TObject);

procedure CreaChildren (Sender: TObject);

procedure Mutation (Sender: TObject);

procedure TrackRead (Sender: TObject);

procedure DrawMarsh (Sender: TObject);

function CrossOver (p, m: integer): string;

procedure Mixer (Sender: TObject);

procedure Button1Click (Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

pX, pY, elite: array of integer; // координаты городов, элитные

road: array of integer;

parents: array of string; // поколений родителей, детей; результат

child: array of string;

result: array of string;

gl: integer; // количество элитных

nCity, nMarsh: integer; // количество городов, маршрутов

kMut, kCross: real; // коэффициент мутации, скрещивания

implementation

{$R *. dfm}

procedure TForm1. Mixer (Sender: TObject);

var

i, j, n, k: integer;

s: string;

label lbl4;

BEGIN

n: =round ((nMarsh) *kCross) — 1;

for i: =0 to nMarsh-1 do

begin

setLength (child, n+i+2);

child [n+i+1]: =parents [i] ;

end;

TrackRead (sender);

setlength (elite, 1);

s: ='_';

{1}for i: =0 to nMarsh-1 do

begin

lbl4:

elite [0]: =random (n+nMarsh);

if pos ('_'+inttostr (elite [0]) +'_', s) <>0 then goto lbl4;

for j: =0 to n+nMarsh-1 do

begin

if pos ('_'+inttostr (j) +'_', s) =0 then

begin

if road [elite [0]] >road [j] then

begin

elite [0]: =j;

end;

end;

end;

s: =s+inttostr (elite [0]) +'_';

parents [i]: =child [elite [0]] ;

{1}end;

END;

function TForm1. CrossOver (p, m: integer): string;

var

gen: char;

i, j: integer; // счетчика

t1,t2: integer; // точки кроссовера

nC, kC: integer; // границы цикла

papa, mama: string;

label lbl3;

BEGIN

papa: =parents [p] ;

mama: =parents [m] ;

randomize;

t1: =random (nCity-1) +1; // выбираем 1 точку

lbl3:

t2: =random (nCity-1) +1; // выбираем 2 точку

if t2=t1 then goto lbl3; // 1 точка не 2 точка

if t1

begin

nC: =t1;

kC: =t2;

end

else

begin

nC: =t2;

kC: =t1;

end;

for i: =nC to kC do // цикл скрещивания

begin

if pos (mama [i], papa) =0 then // проверка на совпадение генов

begin

delete (papa, i, 1);

insert (mama [i], papa, i); // добавляем материнские гены

end

else

begin // изменяем повторившийся ген

gen: =papa [i] ;

papa [i]: =papa [i+1] ;

papa [i+1]: =gen;

end;

end;

crossover: =papa; // возварщаем значение функции потомка

END;

procedure TForm1. TrackRead (Sender: TObject);

var

i, j: integer;

p1,p2: integer;

p: string;

BEGIN

{1}for i: =0 to length (child) — 1 do // большой цикл по маршрутам

begin

setlength (road, i+1);

p: ='';

p: =child [i] ;

{2}for j: =1 to nCity-1 do // внутренний цикл по городам маршрутов

begin

if j<>nCity-1 then // проверка на последний город

begin

p1: =StrToInt (p [j]); //

p2: =StrToInt (p [j+1]); // соседний

end

else

begin

p1: =StrToInt (p [j+1]); // последний

p2: =StrToInt (p [1]); // первый

end; // расчет расстояния

road [i]: =road [i] +round (sqrt (sqr (pX [p1] -pX [p2]) +sqr (pY [p1] -pY [p2])));

{2}end;

{1}end;

END;

procedure TForm1. DrawMarsh (Sender: TObject);

var

i, j: integer;

p1,p2: integer;

p: string;

BEGIN

p: =parents ;

Image1. CleanupInstance;

with Image1. Canvas do

begin

for j: =1 to nCity do // внутренний цикл городам маршрута

begin

if j=nCity then

begin

p1: =StrToInt (p [j]);

p2: =StrToInt (p [1]);

end

else

begin

p1: =StrToInt (p [j]);

p2: =StrToInt (p [j+1]);

end;

MoveTo (pX [p1], pY [p1]);

LineTo (pX [p2], pY [p2]);

end;

end;

END;

procedure TForm1. Mutation (Sender: TObject);

var

i, ran: integer; // счетчик, случайное число

gen: char; // мутирующий ген

mutant: string;

BEGIN

mutant: ='';

for i: =0 to round ((nMarsh) *kCross) — 1 do // цикл мутации

begin

randomize;

if kMut

begin

mutant: =child [i]; // мутирующая особь

ran: =random (nCity-1);

gen: =mutant [ran]; //

mutant [ran]: =mutant [ran+1]; // мутируем

mutant [ran+1]: =gen; //

child [i]: =mutant;

end;

end;

END;

procedure TForm1. FirstGeneration (Sender: TObject);

var

i, j, ram: integer; // счетчики, рандомное значение

s: string; // строка маршрута

label lbl1; // метка

BEGIN

randomize;

for i: =0 to nMarsh-1 do // цикл формирования первого поколения

{1}begin

s: ='';

setlength (parents, i+1); // устанавливаем длину массива родителей

for j: =0 to nCity-1 do // цикл формирования строки маршрута

{2}begin

setlength (s, j+1); // устанавливаем длину строки маршрута

lbl1:

ram: =random (nCity); // случайный выбор номера города

if pos (IntToStr (ram), s) =0 then // проверка на повтор номера города

begin

insert (IntToStr (ram), s,1); // добавление номера города в строку маршрута

end

else goto lbl1; // переход на метку

{2}end;

parents [i]: =s; // заполняем массив родителей (первое поколение)

{1}end;

END;

procedure TForm1. CreaChildren (Sender: TObject);

var

i: integer; // счетчики

p, m: integer; // номера родителей

label lbl2;

BEGIN

randomize;

for i: =0 to round ((nMarsh) *kCross) — 1 do // цикл создания пар

begin

setlength (child, i+1);

p: = random (nMarsh); // выбираем номер папы

lbl2:

m: = random (nMarsh); // выбираем номер мамы

if m=p then goto lbl2; // папа не мама

child [i]: =crossover (p, m); // создаем потомков

end;

END;

procedure TForm1. Image1Click (Sender: TObject);

begin

inc (nCity); // считаем города

end;

procedure TForm1. Image1MouseDown (Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

begin

// // /

with Image1. Canvas do

begin

Brush. Color: =clRed;

Brush. Style: =bsSolid;

Rectangle (x-5,y-5,x+5,y+5);

Brush. Color: =clWhite;

TextOut (x, y, inttostr (nCity));

end;

// // /

SetLength (pX, nCity+1);

pX [nCity]: =x;

SetLength (py, nCity+1);

pY [nCity]: =y;

// // /

end;

procedure TForm1. Button1Click (Sender: TObject);

var

i, nPokol: integer;

begin

nMarsh: =StrToInt (Edit3. Text);

kMut: =StrToFloat (Edit2. Text);

kCross: =StrToFloat (Edit4. Text);

nPokol: =StrToInt (Edit5. Text);

FirstGeneration (sender);

for i: =1 to nPokol do

begin

CreaChildren (sender);

Mutation (sender);

Mixer (sender);

DrawMarsh (sender);

end;

end;

end.