Министерство образования и науки Республики Казахстан
Карагандинский Государственный Технический Университет
Кафедра САПР
Пояснительная записка
к курсовой работе
по дисциплине: "Прикладная теория систем"
Тема: "Генетический алгоритм"
2009
Цель работы
Выработать способность системного рассмотрения проблем и задач и дать методологию и методы их решения (вне зависимости от их проблемной ориентации). Получить практические навыки разработки базовых понятий аксиоматики, методологии исследования проектирования сложных систем. Разработка концептуальных формализованных средств, представление объектов и процессов как сложную систему. Построение обобщённых моделей, объектов и процессов как систему логико-математического аппарата их анализа и синтеза. Разработка иерархического строения систем, их целенаправленного поведения, управления и оптимизации. Научиться формализовано представлять задачу в терминах характеристик её решения, формировать наиболее адекватный критерий эффективности оценки решения, применять для этого генетический алгоритм.
Задача:
Разработать программу реализации генетического алгоритма в соответствии с выданным вариантом. Для разработки использовать любую визуальную среду программирования.
В интерфейсе программы предусмотреть возможность ввода параметров:
объём популяции;
число поколений;
коэффициент скрещивания;
коэффициент мутации;
для дифференциального кроссовера коэффициенты k,c;
для задачи коммивояжёра ввод [4. .40] числа городов и их расстановку вручную и автоматически;
для биологической задачи возможность ввода названий характеристик [10.15], их значений [4. .40], значимости и веса [0.1] каждой характеристики.
Результаты работы программы должны включать:
на каждом шаге отображать номер поколения и лучшее значение фитнес-функции в этом поколении;
лучшее значение фитнес-функции за все поколения и соответствующую ей структуру особи;
для биологической задачи и задачи оптимизации функции график зависимости значения целевой функции от номера поколения;
для задачи коммивояжёра на каждом поколении графически отображать лучщий маршрут.
Интерфейс программы должен включать характеристики генетического алгоритма в соответствии с вариантом, сведения о разработчике, краткую справку (руководство пользователя).
Вариант задания:
Тип задачи - коммивояжёр
Выбор пары - панмиксия
Кроссовер - двухточечный
Мутация - перестановка
Отбор - элитный
Критерий останова - количество поколений
Выходные данные – карта.
Анализ результатов моделирования на основе разработанной программы представляется в виде таблицы:
№ эксперимента |
Кол-во маршрутов |
Число поколений |
Коэф. скрещивания |
Коэф. мутации |
Фитнес- функция (min) |
| 1 | 100 | 500 | 0,5 | 0,001 | 3110 |
| 2 | 150 | 500 | 0,5 | 0,001 | 2783 |
| 3 | 200 | 500 | 0,5 | 0,001 | 2697 |
| 4 | 200 | 1000 | 0,5 | 0,001 | 3034 |
| 5 | 200 | 1500 | 0,5 | 0,001 | 2817 |
| 6 | 200 | 2000 | 0,5 | 0,001 | 3088 |
| 7 | 200 | 500 | 1 | 0,001 | 3282 |
| 8 | 200 | 500 | 1,5 | 0,001 | 3296 |
| 9 | 100 | 500 | 1 | 0,001 | 3334 |
| 10 | 100 | 500 | 0,5 | 0,01 | 3025 |
| 11 | 200 | 500 | 0,5 | 0,01 | 2511 |
| 12 | 100 | 500 | 1 | 0,01 | 2852 |
| 13 | 200 | 500 | 1 | 0,01 | 2749 |
| 14 | 100 | 500 | 0,5 | 0,1 | 3221 |
| 15 | 200 | 500 | 1 | 0,1 | 2497 |
Вывод:
Анализируя полученные результаты моделирования приходим к выводу, что оптимальным количеством маршрутов можно считать 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. Изменяемые параметры
Листинг программы
unitUnit1;
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: TObje
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<t2 then // выбираем границы цикла
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 [0] ;
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<random (10) /100 then // проверка на мутацию
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.