Приминение муравьиных алгоритмов для задачи коммивояжера

Содержание
Введение 2
1. Задача коммивояжера 4
1.1. Содержательное описание 4
1.2. Математическая модель 4
1.3. Постановка оптимизационной задачи 6
1.4. Методы решения задачи коммивояжера 7
1.4.1. Метод ветвей и границ 7
1.4.2. Алгоритм Дейкстры 10
1.4.3. Генетические алгоритмы 12
2. Муравьинные алгоритмы 13
2.1. История создания муравьиных алгоритмов 13
2.2. Концепция муравьиных алгоритмов 14
2.3. Обобщённый алгоритм 15
2.4. Этапы решения задачи при помощи муравьиных алгоритмов 17
3. Применение муравьиных алгоритмов для задачи коммивояжёра 19
4. Реализация муравьинного алгоритма 27
4.1. Выбор средства разработки 27
4.2. Разработка экранной формы приложения 28
4.3. Тестирование 34
5. Сравнение методов решения задачи коммивояжера 38
Заключение 41
Литература 43
Приложение 45
...

Содержание
Введение 2
1. Задача коммивояжера 4
1.1. Содержательное описание 4
1.2. Математическая модель 4
1.3. Постановка оптимизационной задачи 6
1.4. Методы решения задачи коммивояжера 7
1.4.1. Метод ветвей и границ 7
1.4.2. Алгоритм Дейкстры 10
1.4.3. Генетические алгоритмы 12
2. Муравьинные алгоритмы 13
2.1. История создания муравьиных алгоритмов 13
2.2. Концепция муравьиных алгоритмов 14
2.3. Обобщённый алгоритм 15
2.4. Этапы решения задачи при помощи муравьиных алгоритмов 17
3. Применение муравьиных алгоритмов для задачи коммивояжёра 19
4. Реализация муравьинного алгоритма 27
4.1. Выбор средства разработки 27
4.2. Разработка экранной формы приложения 28
4.3. Тестирование 34
5. Сравнение методов решения задачи коммивояжера 38
Заключение 41
Литература 43
Приложение 45

-

GraphGrid: TStringGrid;
NumberEdit: TSpinEdit;
Label1: TLabel;
Button1: TButton;
Button2: TButton;
GroupBox3: TGroupBox;
Image1: TImage;
GroupBox4: TGroupBox;
Label4: TLabel;
Label3: TLabel;
Label6: TLabel;
GroupBox5: TGroupBox;
Label2: TLabel;
Label5: TLabel;
Label7: TLabel;
GroupBox6: TGroupBox;
Label8: TLabel;
Edit_ro: TEdit;
Label9: TLabel;
Edit_alph: TEdit;
Label10: TLabel;
Edit_beta: TEdit;
EditLT: TEdit;
Label11: TLabel;
procedure GraphGridDrawCell(Sender: TObject; ACol, ARow: Integer;
Rect: TRect; State: TGridDrawState);
procedure NumberEditChange(Sender: TObject);
procedure FormCreate(Sender: TObject);
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
private
{ Private declarations }
procedure InputMatrix;
procedure Etap(var GInd:integer);
procedure Konkurir(var r,m:byte);
procedure OpredilPuti;
procedure Sbros;
procedure DelStrStolb(Stroka,Stolb:byte);
procedure Tree(K,XPos,YPos,Index,RG,MG,Blok,GIn:byte);
public
{ Public declarations }
procedure ResetGraphGrid(const n: Integer);
end;
var
MainForm: TMainForm;
ParKonkur,GorodaIJ:Gorod;
Feromon,h:MatrG;
Ant:Ants;
Ci,Cj:Dopolnit;
GIndexKon:ConPrived;
IsklStrok:Iskluch;
IsklStolb:Iskluch;
Tabu:Iskluch;
TreeList:TEdit;
ListName:TLabel;
Puti,NewPut:ItogPuti;
N:byte;
K:integer;
alph,beta,ro:Real;
implementation
{$R *.dfm}
procedure TMainForm.GraphGridDrawCell(Sender: TObject; ACol, ARow: Integer;
Rect: TRect; State: TGridDrawState);
begin
if (ACol = ARow) and (ACol > 0) then
begin
GraphGrid.Canvas.Brush.Color:= clBtnFace;
GraphGrid.Canvas.FillRect(Rect);
end;
end;
procedure TMainForm.NumberEditChange(Sender: TObject);
begin
ResetGraphGrid(NumberEdit.Value);
end;
procedure TMainForm.ResetGraphGrid(const n: Integer);
var
i: Integer;
begin
GraphGrid.ColCount:= n + 1;
GraphGrid.RowCount:= GraphGrid.ColCount;
for i:= 1 to GraphGrid.RowCount-1 do
begin
GraphGrid.Rows[i].Text:= 'a' + IntToStr(i);
GraphGrid.Cols[i].Text:= GraphGrid.Rows[i].Text;
end;
end;
procedure TMainForm.FormCreate(Sender: TObject);
begin
ResetGraphGrid(NumberEdit.Value);
Image1.Picture.Bitmap:=nil;
Image1.Picture.Bitmap := TBitmap.Create;
Image1.Picture.Bitmap.Width := Image1.Width;
Image1.Picture.Bitmap.Height := Image1.Height;
end;
procedure TMainForm.Button1Click(Sender: TObject);
Var
i,j:Integer;
Value: Integer;
begin
n:=StrToInt(NumberEdit.Text);
Randomize;
for i:= 0 to n - 1 do
for j:= 0 to n - 1 do
begin
if (j > i) then
begin
repeat
Value:= Random(5000);
until (Value <> 0);
GraphGrid.Cells[i+1,j+1]:=IntToStr(Value);
GraphGrid.Cells[j+1,i+1]:=IntToStr(Value);
end;
end;
end;
{****************************************************}
{Процедура чтения матрицы}
procedure TMainForm.InputMatrix;
var
i,j:integer;
begin
for i:=1 to N do
begin
GorodaIJ[i,i]:=-1;
for j:=1 to N do
begin
if i<>j then
begin
GorodaIJ[i,j]:=StrToInt(GraphGrid.Cells[i,j]);
end;
end;
end;
end;
{****************************************************}
{Процедура нахождения перспективной пары из множества конкурирующих пар}
procedure TMainForm.Konkurir(var r,m:byte);
var
i,j,l:byte;
xmin,ymin,max:integer;
begin
for i:=1 to N do
for j:=1 to N do
ParKonkur[i,j]:=-1;
{Определяем множество конкурирующих пар городов и определяем для них оценку}
for i:=1 to N do
for j:=1 to N do
if GorodaIJ[i,j]=0 then
begin
xmin:=9999; ymin:=9999;
for l:=1 to N do
begin
if (GorodaIJ[i,l]<=xmin) and (GorodaIJ[i,l]<>-1) and (l<>j) then
xmin:=GorodaIJ[i,l];
if (GorodaIJ[l,j]<=ymin) and (GorodaIJ[l,j]<>-1) and (l<>i) then
ymin:=GorodaIJ[l,j];
end;
if xmin=9999 then xmin:=0;
if ymin=9999 then ymin:=0;
ParKonkur[i,j]:=xmin+ymin;
end;
{Находим перспективную пару (r,m)}
max:=-1;
for i:=1 to N do
for j:=1 to N do
if ParKonkur[i,j]>max then
begin
max:=ParKonkur[i,j];
r:=i; m:=j;
end;
end;
{***************************************************}
{Процедуры ПРИВЕДЕНИЯ матрицы.
А также для нахождения нижней оценки G}
procedure TMainForm.Etap(var GInd:integer);
var
i,j,min:integer;
begin
GInd:=0;
{Находим минимальный элемент матрицы по строкам}
for i:=1 to N do
begin
min:=-1;
for j:=1 to N do
begin
if GorodaIJ[i,j]<>-1 then
begin
if min=-1 then min:=GorodaIJ[i,j];
if GorodaIJ[i,j]<=min then
begin
min:=GorodaIJ[i,j];
end;
end;
end;
if min=-1 then min:=0;
Cj[i]:=min;
end;
{отнимаем минимальные элементы из элементов соответствующих строк}
for i:=1 to N do
begin
for j:=1 to N do
begin
if GorodaIJ[i,j]<>-1 then
GorodaIJ[i,j]:=GorodaIJ[i,j]-Cj[i];
end;
end;
{Находим минимальный элемент полученной матрицы по столбцам}
for j:=1 to N do
begin
min:=-1;
for i:=1 to N do
begin
if GorodaIJ[i,j]<>-1 then
begin
if min=-1 then min:=GorodaIJ[i,j];
if GorodaIJ[i,j]<=min then
begin
min:=GorodaIJ[i,j];
end;
end;
end;
if min=-1 then min:=0;
Ci[j]:=min;
end;
{отнимаем минимальные элементы из элементов соответствующих столбцов
и находим оптимальное множество с оценкой}
for i:=1 to N do
begin
GInd:=GInd+Cj[i]+Ci[i];
for j:=1 to N do
begin
if GorodaIJ[i,j]<>-1 then
GorodaIJ[i,j]:=GorodaIJ[i,j]-Ci[j];
end;
end;
end;
{****************************************************}
{Процедура вычеркивания из матрицы Stroka строки и Stolb столбца}
procedure TMainForm.DelStrStolb(Stroka,Stolb:byte);
var
i:byte;
begin
if (Stroka<>0) and (Stolb<>0) then
for i:=1 to N do
begin
GorodaIJ[Stroka,i]:=-1;
GorodaIJ[i,Stolb]:=-1;
end;
end;
{****************************************************}
{Процедура нахождения оптимального пути}
procedure TMainForm.OpredilPuti;
var
i,j,k,l:integer;
Fl:boolean;
begin
{Поиск начального элемента}
for i:=1 to n do
begin
Fl:=False;
for j:=1 to N do
if Puti[i*2-1]=Puti[j*2] then Fl:=true;
if not Fl then
begin
NewPut[1]:=Puti[i*2-1];
NewPut[2]:=Puti[i*2];
end;
end;
{Составления оптимального маршрута}
for k:=1 to N+1 do
begin
for l:=1 to N+1 do
if Puti[l*2-1]=Newput[k] then
begin
NewPut[k]:=Puti[l*2-1];
NewPut[k+1]:=Puti[l*2];
end;
NewPut[N+1]:=newput[1];
end;
{Вывод последовательности городов на экран}
for i:=1 to N do
Label3.Caption:=Label3.Caption+'a'+inttostr(newPut[i])+'->';
Label3.Caption:=Label3.Caption+'a'+inttostr(newPut[N+1]);
end;
{****************************************************}
{Процедура проверки на замкнутость пути}
procedure ProverkaIskl;
var
i,j,Stroka,Stolbec,x,y:byte;
begin
x:=0;
y:=0;
for i:=1 to N do
begin
Stroka:=0;
Stolbec:=0;
for j:=1 to N do
begin
if (GorodaIJ[i,j]=-1) and (IsklStrok[i]<>1) then
if (IsklStolb[j]<>1) then Stroka:=1;
if (GorodaIJ[j,i]=-1) and (IsklStolb[i]<>1) then
if (IsklStrok[j]<>1) then Stolbec:=1;
end;
if (Stroka=0) and (IsklStrok[i]<>1) then
begin
x:=i;
Stroka:=1;
end;
if (Stolbec=0) and (IsklStolb[i]<>1) then y:=i;
end;
if x<>0 then
if y<>0 then GorodaIJ[x,y]:=-1;
end;
{****************************************************}
{Процедура вывода дерева ветления на экран}
procedure TMainForm.Tree(K,XPos,YPos,Index,RG,MG,Blok,GIn:byte);
begin
with Image1.Picture.Bitmap.Canvas do
begin
Font.Name:='Arial';
Font.Style:=[fsBold];
Pen.Width:=2;
Pen.Color:=clMaroon;
if (XPos=0) and (YPos=0) then
begin
Font.Size:=7;
Font.Color:=clBlue;
Brush.Color:=clYellow;
Ellipse(N*30-15,10,15+N*30,40);
TextOut(N*30-10,18,'G[0]');
Brush.Color:=clWhite;
Font.Color := clBlue;
TextOut(N*30-27,18,IntToStr(GIn));
end
else begin
Font.Size:=7;
Font.Color:=clBlue;
Brush.Color:=clYellow;
Ellipse(XPos*50+N*30-30-YPos*30+K*60,10+YPos*50,XPos*50+N*30-60-YPos*30+K*60,40+YPos*50);
TextOut(XPos*50+N*30-58-YPos*30+K*60,18+YPos*50,('G['+IntToStr(Index+1)+','+IntToStr(XPos)+']'));
Brush.Color:=clWhite;
Font.Color := clGreen;
if Blok=1 then
Font.Style:=[fsStrikeOut,fsBold]
else Font.Style:=[fsBold];
TextOut(XPos*55+N*30-60-YPos*30+K*60,YPos*50-8,'('+IntToStr(RG)+','+IntToStr(MG)+')');
Font.Color := clBlue;
Font.Style:=[fsBold];
TextOut(XPos*94+N*30-115-YPos*30+K*60,YPos*50+18,IntToStr(GIn));
Pen.Color:=clRed;
MoveTo(XPos*50+N*30-45-YPos*30+K*60,10+YPos*50);
LineTo(Index+N*30-(YPos-1)*30+K*60,38+(Index)*50);
end;
end;
end;
{****************************************************}
{Процедура сброса всех значений}
procedure TMainForm.Sbros;
var
i,j:integer;
begin
K:=-1;
for i:=1 to NN do
begin
Ci[i]:=0;
Cj[i]:=0;
IsklStrok[i]:=0;
IsklStolb[i]:=0;
for j:=1 to NN do
GorodaIJ[i,j]:=0;
end;
for i:=0 to NN do
for j:=0 to 2 do
GIndexKon[i,j]:=0;
for i:= 1 to NN*2 do
begin
Puti[i]:=0;
NewPut[i]:=0;
end;