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

, где

- рассчитываемый световой поток, лм;

- нормированная минимальная освещенность, лк. В соответствии с пунктом 1.1.2, ;

- площадь освещаемого помещения (в нашем случае S =42 м²);

-коэффициент минимальной освещенности, характеризует неравномерность освещения и составляет 1.1 для люминесцентных ламп.

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

- установленное число светильников, ;

- число ламп в светильнике, ;

- коэффициент использования светового потока, выражается отношением светового потока, падающего на расчетную поверхность, к суммарному потоку всех ламп и исчисляется в долях единицы; зависит от характеристик светильника, размеров помещения, окраски стен и потолка, характеризуемых коэффициентами отражения от стен , потолка и расчетной поверхности ; значение коэффициентов:=0.5, (в помещениях, где находится компьютер, необходимо обеспечить следующие величины коэффициента отражения: для потолка: 80... 90%, для стен: 50... 60%, для пола: около 30%. Для других поверхностей и рабочей мебели: 30... 40%).

Индекс помещения:

, где

- площадь помещения, ;

- расчетная высота подвеса,

- ширина помещения, ;

- длина помещения,

Подставив значения, получим: .

Зная индекс помещения , по таблице 2 приложения 3 Методических указаний «Производственное освещение авиастроительных предприятий», находим .

Подставим все значения в формулу для определения светового потока и получим следующее значение: .

В помещении используются люминесцентные лампы типа ЛБ-40, световой поток которых .

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

Выводы

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

Фактор освещенности признан основным. Произведен анализ условий труда и расчет освещенности вычислительного центра (лаборатории). Оптимальными для освещения помещения являются лампы ЛБ-40 (лампы люминесцентные белого света, мощность - 40 Вт, световой поток - 3000 лм). Показатель освещенности в данном помещении не отклоняется от нормы. Шум и вибрация в помещении соответствуют нормам.

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

Заключение

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

Для каждого варианта задачи был успешно найден кратчайший маршрут. Было оценено время выполнения программы. При дробных значениях параметров и время выполнения программы увеличивается на 30-50%, в зависимости от количества городов.

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

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

В экономической части дипломной работы был проведен расчет затрат на разработку алгоритма муравья для решения задачи коммивояжера. На основании величины уровня экономической эффективности (Е_ПП=1.02), а также срока окупаемости затрат на создание алгоритма и ПП (около 11 месяцев) можно сделать вывод о том, что разработка и внедрение данного ПП являются экономически целесообразными и эффективными.

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

Фактор освещенности признан основным. Произведен анализ условий труда и расчет освещенности вычислительного центра (лаборатории). Оптимальными для освещения помещения являются лампы ЛБ-40 (лампы люминесцентные белого света, мощность - 40 Вт, световой поток - 3000 лм). Показатель освещенности в данном помещении не отклоняется от нормы. Шум и вибрация в помещении соответствуют нормам.

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

передвижение муравей задача коммивояжер

Список использованной литературы

1. Рассел С. Дж., Норвиг, П. Искусственный интеллект: современный подход -- М.: Вильямс, 2006. 2006.

2. А.Левитин. Алгоритмы. Введение в разработку и анализ, 2006.

3. Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы. Построение и анализ -- М. «Вильямс», 2005.

4. Павленко А.И., Титов Ю.П. Метод муравьиной оптимизации в задачах распределения ресурсов -- МАИ, 2008.

5. Субботин С.А., Олейник Ан.А., Олейник Ал.А. Интеллектуальные мультиагентные методы (swarm intelligence) -- http://csit.narod.ru/subject/MA/MA_lect.pdf

6. Ермолаев С.Ю. Муравьиные алгоритмы оптимизации -- УДК 621.395.8

7. С.Д. Штовба. Муравьиные алгоритмы. http://www.serhiy-shtovba.narod.ru/doc/Shtovba_Ant_Algorithms_ExponentaPro_2003_3.pdf

8. М. Тим Джонс. Программирование искусственного интеллекта в приложениях -- ДМК Пресс, 2004.

9. Т.В. Маланова, Н.С. Серебрянска. Сравнительный анализ алгоритмов муравья. -- УДК 004.032.026:004.3

10. Чжо Мьо Хан, Диссертационная работа на тему «Планирование движения маршрута городского транспорта» -- МАИ 2010.

11. Панагушин В.П., Ковалева Т.С., Малютина О.А.Экономическое обоснование дипломных проектов (работа) по приборо- и радиоприборостроению. М.: МАИ, 2008.

12. ГОСТ 12.1.005-88 «Воздух рабочей зоны».

13. СНиП 23.05-95 «Естественное и искусственное освещение».

14. ГОСТ 12.1.038 - 82 «Допустимые значения напряжения и токов».

15. ГОСТ 12.1.003-83«Шум Общие требования безопасности».

16. ГОСТ 12.1.012-90 «Вибрационная безопасность. Общие требования».

17. СанПиН 2.2.2/2.4.1340-03 «Гигиенические требования к персональным электронно-вычислительным машинам и организации работы» с дополнением СанПиН 2.2.2/2.4.2620-10

18. ГОСТ Р52324-2005 «Эргономические требования к работе с визуальными дисплеями, основанными на плоских панелях».

19. Березкин В.М. Дайнов М.И. Методические указания к дипломному проектированию «Защита от вредных производственных факторов при работе на ПЭВМ», М.:МАИ, 2001.

20. Березин В.М., Дайнов М.И. "Защита от вредных производственных факторов при работе на ПЭВМ". М.: МАИ, 2002

21. Беков Б.Е., Н.И. Бобков, А.В. Копылов, Н.С. Чудакова "Производственное освещение авиастроительных предприятий", методические указания к разделу "Охрана труда" М.: МАИ, 1987.

22. Marco Dorigo, Thomas Stutze, Ant colony optimization -- Massachusetts Institute of Technology, 2004.

23. Dorigo M. Optimization, Learning and Natural Algorithms. -- Milano: Politecnico di Milano, 1992.

24. Dorigo M., Maniezzo V., Colorni A. Positive feedback as a search strategy. -- Milano: Politecnico di Milano, 1991.

25. Bullnheimer B., Hartl R.F., Strauss C. A new rank-based version of the Ant System: A computational study, central European Journal for Operations Research and Economics. -- 1999. - №7 (1).

26. Maniezzo V., Colorni A., Dorigo M. The ant system applied to the quadratic assignment problem. -- Bruxelle: Universite Libre de Bruxelles, 1994.

27. Ghosh S.K. Visibility Algorithms in the Plane -- Cambridge University Press, 2007.

28. Alberto Colorni, Marco Dorigo, Vittorio Maniezzo. An investigation of some properties of an “Ant algorithm” -- Elsevier Publishing, 1992.



Приложение 1

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

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

unit Ant_algorythm;

interface

uses

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

Dialogs, ExtCtrls, StdCtrls, Math, DateUtils;

const

MAX_OBSTACLE_NODES=15;

MAX_CITIES=10;

MAX_NODES=MAX_OBSTACLE_NODES+MAX_CITIES;

MAX_DISTANCE=100;

MAX_ANTS=10;

ALPHA=2.0;

BETA=1.0;

RHO=0.7;

QVAL=20;

MAX_TOURS=MAX_CITIES * MAX_DISTANCE * 10;

MAX_TIME=MAX_TOURS * MAX_CITIES; //MAX_TOURS * MAX_CITIES;

INIT_PHEROMONE=1.0 / MAX_CITIES;

NK=4; //number of obstacles+1

type

sol = record

X:integer;

Y:integer;

end;

cityType = record

X: integer;

Y: integer;

end;

antType = record

curCity : integer;

nextCity : integer;

pathIndex : integer;

pathIndex_city: integer;

tabu : array [1..MAX_NODES] of integer;

path : array [1..MAX_NODES] of integer;

tourLength : double;

k1,k2:integer;

end;

TMainForm = class(TForm)

MainMemo: TMemo;

obst_coord: TButton;

topology: TButton;

shortest_path: TButton;

Panel1: TPanel;

MainMap: TPaintBox;

exit: TButton;

procedure obst_coordClick(Sender: TObject);

procedure topologyClick(Sender: TObject);

procedure shortest_pathClick(Sender: TObject);

procedure exitClick(Sender: TObject);

procedure FormCreate(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

MainForm: TMainForm;

list,list1: Tstrings;

distance: array [1..MAX_NODES, 1..MAX_NODES] of double;

cities: array [1..MAX_NODES] of cityType;

ants: array [1..MAX_ANTS+1] of antType; //ants[MAX_ANTS+1] содержит мин путь

pheromone: array [1..MAX_NODES, 1..MAX_NODES] of double;

best: double;

bestIndex: integer;

obstacles: array [1..MAX_NODES, 1..MAX_NODES] of integer;

curTime:integer;

denom:double;

GL:integer;

Inf:array[1..NK] of integer;

today,today1: TDateTime;

ha,z,z0,z1,ant,from,x1,y1,x2,y2,g:integer;

t:TextFile;

implementation

{$R *.dfm}

function getcoord(var str:string):string;

var r:integer;

begin

result:=str;

r:=pos(' ',str);

if r=0 then exit;

result:=copy(str,1,r-1);

delete(str,1,r);

end;

procedure ReadNodes();

var

list: Tstrings;

i,from:integer;

str:string;

begin

list:= TStringlist.Create;

list.LoadFromFile('c:\nodes.dat');

str:= List.Strings[0];

for i:=0 to NK-1 do

begin

inf[i+1]:=Strtoint(getcoord(str));

end;

for i := 1 to List.Count - 1 do

begin

if i>9 then

begin

str:= List.Strings[i];

from:= Strtoint(getcoord(str));

cities[from].x:=Strtoint(getcoord(str));

cities[from].y:=Strtoint(getcoord(str));

end

else

begin

str:= List.Strings[i];

from:= Strtoint(getcoord(str));

cities[from].x:=Strtoint(getcoord(str));

cities[from].y:=Strtoint(getcoord(str));

end;

end;

end;

procedure InitialFullFill();

var

ant, from:integer;

begin

for ant:=1 to MAX_NODES do

begin

for from:=1 to MAX_NODES do

begin

if ant=from then

obstacles[ant][from]:=1

else

obstacles[ant][from]:=2;

end;

end;

end;

procedure FullFillNeighbour(n,from:integer);

var

ant:integer;

// n - номер первого узла i препятствия

// from - номер последнего узла i препятствия

begin

for ant:=n to from do //for i:=n to m do

begin

if ant=n then //if i=n then

begin

obstacles[ant][ant+1]:=0;

obstacles[ant][from]:=0;

end;

if ant=from then

begin

obstacles[ant][ant-1]:=0;

obstacles[ant][n]:=0;

end;

if ant<>n then

begin

if ant<>from then

begin

obstacles[ant][ant+1]:=0;

obstacles[ant][ant-1]:=0;

end;

end;

end;

end;

procedure NotTemporary(n,m:integer);

var

ant, from:integer;

begin

for ant:=n to m do

begin

for from:=n to m do

begin

if obstacles[ant][from]=2 then

begin

obstacles[ant][from]:=1;

obstacles[from][ant]:=1;

end;

end;

end;

end;

function Intersect(ax1,ay1,ax2,ay2,bx1,by1,bx2,by2:integer):boolean;

var v1,v2,v3,v4:real;

begin

v1:=(bx2-bx1)*(ay1-by1)-(by2-by1)*(ax1-bx1);

v2:=(bx2-bx1)*(ay2-by1)-(by2-by1)*(ax2-bx1);

v3:=(ax2-ax1)*(by1-ay1)-(ay2-ay1)*(bx1-ax1);

v4:=(ax2-ax1)*(by2-ay1)-(ay2-ay1)*(bx2-ax1);

Intersect:=(v1*v2<0) and (v3*v4<0);

end;

procedure PreIntersect(); // определяет координаты 1 отрезка

var

ha,p,p2,ant,from,z,z0,z1,g:integer;

xkn,ykn,xkk,ykk:integer;

x1,y1,x2,y2:integer;

M:boolean;

begin

for ant:=1 to MAX_NODES do

begin

for from:=1 to MAX_NODES do

begin

if obstacles[ant][from]=2 then

begin

x1:=Cities[ant].X;

y1:=Cities[ant].Y;

x2:=Cities[from].X;

y2:=Cities[from].Y;

for ha:=1 to NK-1 do

begin

if ha=1 then

begin

z:=inf[ha]+1;

z0:=z;

z1:=z+inf[ha+1];

end

else

begin

z:=z1+1;

z1:=Inf[ha+1]+z;

z0:=z;

end;

for g:=z to z1-1 do

begin

xkn:=Cities[g].X;

ykn:=Cities[g].Y;

xkk:=Cities[g+1].X;

ykk:=Cities[g+1].Y;

M:=Intersect(x1,y1,x2,y2,xkn,ykn,xkk,ykk);

if M then

begin

obstacles[ant][from]:=1;

obstacles[from][ant]:=1;

end;

end;

g:=z1;

xkn:=Cities[g].X;

ykn:=Cities[g].Y;

xkk:=Cities[z0].X;

ykk:=Cities[z0].Y;

M:=Intersect(x1,y1,x2,y2,xkn,ykn,xkk,ykk);

if M then

begin

obstacles[ant][from]:=1;

obstacles[from][ant]:=1;

end;

//

if M=false then

for p2:=1 to 2 do

begin

begin

for p:=2 to z1-z0 do

begin

xkn:=Cities[z0].X;

ykn:=Cities[z0].Y;

xkk:=Cities[z0+p].X;

ykk:=Cities[z0+p].Y;

M:=Intersect(x1,y1,x2,y2,xkn,ykn,xkk,ykk);

if M then

begin

obstacles[ant][from]:=1;

obstacles[from][ant]:=1;

end;

end;

end;

z0:=z0+1;

end;

//

end;

end;

end;

end;

end;

procedure FinalTrans();

var

ant:integer;

from:integer;

begin

for ant:=1 to MAX_NODES do

begin

for from:=1 to MAX_NODES do

begin

if obstacles[ant][from]=2 then

obstacles[ant][from]:=0;

end;

end;

end;

//Функция инициализации

procedure init();

var

from, ant,to1: integer;

xd,yd:integer;

begin

for from:=1 to MAX_NODES do

begin

for to1:=1 to MAX_NODES do

begin

distance[from][to1]:=0.0;

if obstacles[from][to1]<>1 then //если два узла видимы

//то наносим начальный феромон

pheromone[from][to1]:= INIT_PHEROMONE;

end;

end;

//Вычисляем расстояние между городами

for from:=1 to MAX_NODES do

begin

for to1:=1 to MAX_NODES do

begin

if ((to1 <> from) and (distance[from][to1] = 0.0)) then

begin

xd:= abs(cities[from].x - cities[to1].x);

yd:= abs(cities[from].y - cities[to1].y);

distance[from][to1]:= sqrt( (xd * xd) + (yd * yd) );

distance[to1][from]:= distance[from][to1];

end;

end;

end;

//Инициализация муравьев

to1:=1;

for ant:=1 to MAX_ANTS do

begin

//Равномерное распределение муравьев по городам

if to1>MAX_CITIES then

to1:=1;

ants[ant].curCity:=to1;

to1:=to1+1;

for from:=1 to MAX_NODES do

begin

ants[ant].tabu[from]:=0;

ants[ant].path[from]:= -1;

end;

if ants[ant].curCity<=MAX_CITIES then

ants[ant].PathIndex_City:=1;

ants[ant].pathIndex:=1;

ants[ant].path[1]:= ants[ant].curCity;

ants[ant].nextCity:=-1;

ants[ant].tourLength:=0.0;

ants[ant].tabu[ants[ant].curCity]:= 1;

end;

end;

//Функция restartAnts предназначена для повторной инициализации всех муравьев

procedure restartAnts();

var

flag2:boolean;

FD,i,ant:integer;

to1:integer;

begin

flag2:=false;

to1:=0;

if GL=0 then

begin

FD:=1;

while flag2=false do

begin

if ants[FD].pathIndex_city=MAX_CITIES then

begin

best:=ants[FD].tourLength;

bestIndex:=1;

flag2:=true;

end

else

FD:=FD+1;

end;

for i:=1 to MAX_NODES do

begin

ants[MAX_ANTS+1].path[i]:=ants[FD].path[i];

end;

end;

GL:=GL+1;

for ant:=1 to MAX_ANTS do

begin

if (ants[ant].tourLength < best) then

begin

if ants[ant].pathIndex_city=MAX_CITIES then

begin

best:=ants[ant].tourLength;

bestIndex:=1;

bestIndex:= ant;

for i:=1 to MAX_NODES do

begin

ants[MAX_ANTS+1].path[i]:=ants[ant].path[i];

end;

end;

end;

ants[ant].nextCity:= -1;

ants[ant].tourLength:= 0.0;

for i:=1 to MAX_NODES do

begin

ants[ant].tabu[i]:= 0;

ants[ant].path[i]:=-1

end;

to1:=to1+1;

if to1>=MAX_CITIES then

to1:=1;

ants[ant].curCity:=to1;

if ants[ant].curCity<=MAX_CITIES then

ants[ant].PathIndex_City:=1

else

ants[ant].PathIndex_City:=0;

ants[ant].pathIndex:=1;

ants[ant].path[1]:= ants[ant].curCity;

ants[ant].tabu[ants[ant].curCity]:= 1;

end;

end;

//Функция antProduct используется для расчета движения муравья

//Проверить правильность работы

function antProduct(from,to1:integer):double;

begin

Result:=(( Power( pheromone[from][to1], ALPHA )*

Power( (1.0 / distance[from][to1]), BETA ) ));

end;

//Функция selectNextCity позволяет выбрать следующий город

//для составления пути

function selectNextCity(ant:integer):integer;

var

from,to1:integer;

denom:double;

float : single;

p:double;

flag:boolean;

begin

denom:=0.0;

//Выбрать следующий город

from:= ants[ant].curCity;

//Расчет знаменателя

for to1:=1 to MAX_NODES do

begin

if from<>to1 then

begin

if (ants[ant].tabu[to1] = 0) then

begin

denom:=denom+antProduct( from, to1 );

end;

end;

end;

if denom=0.0 then

denom:=1;

flag:=false;

repeat

to1:=to1+1;

if to1 >= MAX_NODES+1 then

to1:=1;

if from<>to1 then

begin

if ants[ant].tabu[to1] = 0 then

begin

if ants[ant].tabu[to1]<>1 then

begin

p:= antProduct(from, to1)/denom;

float:=Random;

if float < p then

begin

break;

flag:=true;

end;

end;

end;

end;

until flag;

Result:=to1;

end;

//Функция simulateAnts рассчитывает движения муравьев по графу

function simulateAnts ():integer;

var

k:integer;

moving:integer;

flag1:boolean;

from:integer;

begin

moving:=0;

for k:=1 to MAX_ANTS do

begin

flag1:=false;

for from:=1 to MAX_NODES do

begin

ants[k].tabu[from]:=obstacles[ants[k].curCity][from];

end;

for from:=1 to MAX_NODES do

begin

if ants[k].path[from]<>-1 then

ants[k].tabu[ants[k].path[from]]:=1;

end;

for from:=1 to MAX_NODES do

begin

if ants[k].tabu[from]=0 then

begin

flag1:=true;

break;

end;

end;

//Убедиться, что муравью есть куда идти

if (flag1=true) AND (ants[k].pathIndex_city < MAX_CITIES) then

begin

ants[k].nextCity:= selectNextCity( k ); //выбираем следующий город

if ants[k].nextCity <= MAX_CITIES then

begin

ants[k].tabu[ants[k].nextCity]:= ants[k].tabu[ants[k].nextCity]+1;

ants[k].pathIndex_city:=ants[k].pathIndex_city+1;

end;

ants[k].tabu[ants[k].nextCity]:= 1;

ants[k].pathIndex:=ants[k].pathIndex+1;

ants[k].path[ants[k].pathIndex]:=ants[k].nextCity;

ants[k].tourLength:=ants[k].tourLength+distance[ants[k].curCity][ants[k].nextCity];

ants[k].curCity:= ants[k].nextCity;

moving:=moving+1;

end;

if ants[k].pathIndex_city = MAX_CITIES then

begin

moving:=0;

end;

//end;

end;

Result:=moving;

end;

//Функция updateTrails - испарение и размещение нового фермента

procedure updateTrails();

var

from,to1,i,ant:integer;

begin

//Испарение фермента

for from:=1 to MAX_NODES do

begin

for to1:=1 to MAX_NODES do

begin

if (from <> to1) then

begin

if obstacles[from][to1]<>1 then

begin

pheromone[from][to1]:= pheromone[from][to1]*(1.0 - RHO);

if pheromone[from][to1] < 0.1 then

pheromone[from][to1]:= INIT_PHEROMONE;

end;

end;

end;

end;

//Нанесение нового фермента

//Для пути каждого муравья

for ant:=1 to MAX_ANTS do

begin

//Обновляем каждый шаг пути

for i:=1 to MAX_NODES do

begin

if i < MAX_NODES-1 then

begin

if (ants[ant].path[i]<>-1) and (ants[ant].path[i+1]<>-1) then

begin

if ants[ant].pathIndex_city=MAX_CITIES then

begin

from:= ants[ant].path[i];

to1:= ants[ant].path[i+1];

end;

end;

end

else

begin

if (ants[ant].path[i]<>-1) and (ants[ant].path[i+1]<>-1) then

begin

if ants[ant].pathIndex_city=MAX_CITIES then

begin

from:= ants[ant].path[i];

to1:= ants[ant].path[1];

end;

end;

end;

if ants[ant].tourLength<>0 then

begin

pheromone[from][to1]:=(pheromone[from][to1]+ QVAL / ants[ant].tourLength);

pheromone[to1][from]:= pheromone[from][to1];

end;

end;

end;

for from:=1 to MAX_NODES do

begin

for to1:=1 to MAX_NODES do

begin

pheromone[from][to1]:=pheromone[from][to1]*RHO;

end;

end;

end;

procedure TMainForm.topologyClick(Sender: TObject);

var

i,x,y,j,j1,i1,g,g1:integer;

flag:boolean;

begin

flag:=true;

MainMap.Canvas.Brush.Color:=clWhite;

MainMap.Canvas.FillRect(MainMap.Canvas.ClipRect);

for i:=1 to inf[1] do

begin

x:= Cities[i].x;

y:= Cities[i].y;

MainMap.Canvas.Textout(x*5+2,y*5+2,inttostr(i));

MainMap.Canvas.Ellipse(x*5,y*5,x*5+5,y*5+5);

MainMap.canvas.FloodFill(x*5+5,y*5+5, cLRed, fssurface);

end;

for i := inf[1]+1 to MAX_NODES do

begin

x:= Cities[i].x;

y:= Cities[i].y;

MainMap.Canvas.Ellipse(x*5,y*5,x*5+5,y*5+5);

end;

MainMap.Canvas.Pen.Color:=clBlack;

i:=0;

for g:=1 to NK do

begin

if g=1 then

begin

j:=inf[g+1];

i:=inf[g]+1;

i1:=inf[g]+1;

for g1:=1 to j do

begin

MainMap.Canvas.MoveTo(Cities[i].x*5,Cities[i].y*5);

i:=i+1;

MainMap.Canvas.LineTo(Cities[i].x*5,Cities[i].y*5);

end;

MainMap.Canvas.MoveTo(Cities[i1].x*5,Cities[i1].y*5);

MainMap.Canvas.LineTo(Cities[i].x*5,Cities[i].y*5);

end

else

begin

j1:=inf[g+1];

i:=i+1;

i1:=i;

For g1:=1 to j1 do

begin

MainMap.Canvas.MoveTo(Cities[i].x*5,Cities[i].y*5);

i:=i+1;

if i>MAX_NODES then

begin

flag:=false;

break;

end;

MainMap.Canvas.LineTo(Cities[i].x*5,Cities[i].y*5);

end;

if flag=true then

begin

MainMap.Canvas.MoveTo(Cities[i1].x*5,Cities[i1].y*5);

MainMap.Canvas.LineTo(Cities[i].x*5,Cities[i].y*5);

end;

end;

end;

end;

procedure TMainForm.obst_coordClick(Sender: TObject);

var

i,x,y:integer;

begin

for i:=1 to inf[1] do

begin

x:= Cities[i].x;

y:= Cities[i].y;

MainMap.Canvas.Textout(x*5+2,y*5+2,inttostr(i));

end;

for i := inf[1]+1 to MAX_NODES do

begin

x:= Cities[i].x;

y:= Cities[i].y;

MainMap.Canvas.Textout(x*5+2,y*5+2,inttostr(x)+';'+inttostr(y));

end;

end;

procedure TMainForm.shortest_pathClick(Sender: TObject);

var

city,x,y,x1,y1:integer;

begin

city:=1;

MainMap.Canvas.Pen.Color:=clBlue;

MainMemo.Lines[1]:=(FloatToStr(best));

MainMemo.Lines.add(inttostr(MilliSecondsBetween(today1, today)));

while city < MAX_NODES do

begin

x:=(cities[ants[MAX_ANTS+1].path[city]].x);

y:=(cities[ants[MAX_ANTS+1].path[city]].y);

if ants[MAX_ANTS+1].path[city]<=MAX_CITIES then

begin

MainMap.Canvas.Textout(x*5+2,y*5+2,inttostr(ants[MAX_ANTS+1].path[city]));

MainMap.Canvas.Ellipse(x*5,y*5,x*5+5,y*5+5);

end

else

begin

MainMap.Canvas.Pen.Color:=clRed;

MainMap.Canvas.Textout(x*5+2,y*5+2,inttostr(city));

MainMap.Canvas.Ellipse(x*5,y*5,x*5+5,y*5+5);

MainMap.canvas.FloodFill(x*5+3,y*5+3, cLRed, fsSurface);

end;

city:=city+1;

if ants[MAX_ANTS+1].path[city]=-1 then

break;

x1:=(cities[ants[MAX_ANTS+1].path[city]].x);

y1:=(cities[ants[MAX_ANTS+1].path[city]].y);

MainMap.Canvas.Pen.Color:=clBlue;

MainMap.Canvas.MoveTo(x*5,y*5);

MainMap.Canvas.LineTo(x1*5,y1*5);

end;

MainMap.Canvas.Pen.Color:=clBlack;

MainMap.Canvas.MoveTo(0,0);

MainMap.Canvas.LineTo(0,MAX_DISTANCE*5);

MainMap.Canvas.MoveTo(0,0);

MainMap.Canvas.LineTo(MAX_DISTANCE*5,0);

MainMap.Canvas.Textout(0+10,0+8,inttostr(0));

//ось Y

for i:=1 to 10 do

begin

MainMap.Canvas.MoveTo(-5,50*i);

MainMap.Canvas.LineTo(5,50*i);

MainMap.Canvas.Textout(6,50*i+2,inttostr(i*10));

end;

//ось X

for i:=1 to 10 do

begin

MainMap.Canvas.MoveTo(50*i,-5);

MainMap.Canvas.LineTo(50*i,5);

MainMap.Canvas.Textout(50*i+2,6,inttostr(i*10));

end;

end;

procedure TMainForm.exitClick(Sender: TObject);

begin

Close;

end;

procedure TMainForm.FormCreate(Sender: TObject);

begin

Today := now;

InitialFullFill();

ReadNodes();

for ha:=1 to NK-1 do

begin

if ha=1 then

begin

z:=inf[ha]+1;

z0:=z;

z1:=z+inf[ha+1];

FullFillNeighbour(z,z1);

NotTemporary(z,z1);

end

else

begin

z:=z1+1;

z1:=Inf[ha+1]+z;

z0:=z;

FullFillNeighbour(z,z1);

NotTemporary(z,z1);

end;

end;

PreIntersect();

FinalTrans();

for ha:=1 to NK-1 do

begin

if ha=1 then

begin

z:=inf[ha]+1;

z0:=z;

z1:=z+inf[ha+1];

FullFillNeighbour(z,z1);

NotTemporary(z,z1);

end

else

begin

z:=z1+1;

z1:=Inf[ha+1]+z;

z0:=z;

FullFillNeighbour(z,z1);

NotTemporary(z,z1);

end;

for g:=z to z1-1 do

begin

x1:=Cities[g].X;

y1:=Cities[g].Y;

x2:=Cities[g+1].X;

y2:=Cities[g+1].Y;

end;

g:=z1;

x1:=Cities[g].X;

y1:=Cities[g].Y;

x2:=Cities[z0].X;

y2:=Cities[z0].Y;

end;

AssignFile(t,'C:\visivility_graph.txt');

Rewrite(t);

for ant := 1 to MAX_NODES do

begin

for from:=1 to MAX_NODES do

begin

Write(t,obstacles[ant][from]);

end;

Writeln(t);

end;

CloseFile(t);

GL:=0;

Randomize();

init();

curTime:=1;

while curTime < MAX_TIME do

begin

curTime:=curTime+1;

if simulateAnts()=0 then

begin

updateTrails();

if curTime <> MAX_TIME then

restartAnts();

end;

Today1 :=now;

end;

end;

end.



Приложение 2

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

Изучение влияния сходимости	Сравнение с алгоритмом Дейкстры
5 городов	10 городов	15 городов	20 городов	25 городов	2
5 2 3 7 1 20 70 2 90 80 3 65 45 4 15 20 5 70 10 6 15 45 7 35 45 8 25 25 9 50 40 10 80 40 11 80 20 12 50 20 13 55 85 14 65 80 15 67 72 16 65 65 17 55 60 18 46 65 19 43 72 20 47 82	10 2 3 7 1 20 70 2 90 80 3 65 45 4 15 20 5 70 10 6 25 50 7 85 25 8 40 30 9 95 40 10 35 95 11 15 45 12 35 45 13 25 25 14 50 40 15 80 40 16 80 20 17 50 20 18 55 85 19 65 80 20 67 72 21 65 65 22 55 60 23 46 65 24 43 72 25 47 82	15 2 3 7 1 20 70 2 90 80 3 65 45 4 20 25 5 70 10 6 25 50 7 85 25 8 40 30 9 95 40 10 35 95 11 70 90 12 35 60 13 65 15 14 80 60 15 10 65 16 15 45 17 35 45 18 25 25 19 50 40 20 80 40 21 80 20 22 50 20 23 55 85 24 65 80 25 67 72 26 65 65 27 55 60 28 46 65 29 43 72 30 47 82	20 2 3 7 1 20 70 2 90 80 3 65 45 4 20 25 5 70 10 6 25 50 7 85 25 8 40 30 9 95 40 10 35 95 11 70 90 12 35 60 13 65 15 14 80 60 15 10 65 16 45 50 17 15 85 18 75 75 19 35 15 20 55 95 21 15 45 22 35 45 23 25 25 24 50 40 25 80 40 26 80 20 27 50 20 28 55 85 29 65 80 30 67 72 31 65 65 32 55 60 33 46 65 34 43 72 35 47 82	25 2 3 7 1 20 70 2 90 80 3 65 45 4 20 25 5 70 10 6 25 50 7 85 25 8 40 30 9 95 40 10 35 95 11 70 90 12 35 60 13 65 15 14 80 60 15 10 65 16 45 50 17 15 85 18 75 75 19 35 15 20 55 95 21 30 80 22 10 15 23 85 15 24 80 85 25 70 55 26 15 45 27 35 45 28 25 25 29 50 40 30 80 40 31 80 20 32 50 20 33 55 85 34 65 80 35 67 72 36 65 65 37 55 60 38 46 65 39 43 72 40 47 82	2 5 3 3 3 3 7 3 1 10 100 2 120 10 3 10 28 4 10 33 5 28 33 6 28 15 7 20 15 8 20 28 9 10 53 10 10 72 11 29 72 12 29 53 13 42 75 14 31 90 15 42 106 16 53 90 17 48 48 18 48 58 19 65 58 20 65 48 21 70 78 22 70 90 23 105 90 24 105 78 25 90 42 26 82 45 27 80 52 28 82 59 29 90 61 30 98 59 31 101 52 32 98 45 33 52 24 34 52 33 35 110 33 36 110 24

Таблица 16. Координаты городов и препятствий для тестируемых задач



Приложение 3

Результаты моделирования.

В таблицах 17-19 представлены результаты моделирования для задачи коммивояжера с 5 городами.

б	в		Минимальная длина пути	Время, с	Средняя длина пути	Среднее время, с
0	1	0.7	203,599 200,820 199,361 199,361 207,902 202,074 200,820 199,361 199,361 203,599	188 156 186 186 156 171 186 171 171 188	201,709	176
0.5	1	0.7	200,886 199,361 202,074 200,820 199,361 202,074 200,886 199,361 199,361 200,820	281 281 281 296 279 281 295 281 279 281	200,5	283
1	1	0.7	202,074 199,361 199,361 199,361 200,886 199,361 199,361 199,361 199,361 199,361	203 201 203 202 201 203 203 201 201 203	199,785	202
2	1	0.7	199,361 199,361 199,361 199,361 199,361 199,361 199,361 199,361 199,361 199,361	203 203 203 201 201 203 203 203 203 203	199,361	203

Таблица 17. Моделирование алгоритма муравья для задачи коммивояжера с 5 городами с варьированием параметра б

б	в		Минимальная длина пути	Время, с	Средняя длина пути	Среднее время, с
1	0.5	0.7	200,886 199,361 199,361 199,361 199,361 209,506 200,886 200,886 199,361 199,361	296 281 296 296 296 296 296 279 281 296	200,833	291
1	1	0.7	199,361 199,361 199,361 200,886 199,361 199,361 199,361 199,361 199,361 199,361	203 203 203 201 203 203 203 203 203 203	199,513	203
1	2	0.7	202,074 202,074 202,074 199,361 199,361 202,074 199,361 199,361 202,074 199,361	188 187 201 187 203 186 203 203 188 187	200,718	193
1	5	0.7	209,361 202,496 202,496 209,361 202,496 202,496 202,496 207,902 209,361 202,496	171 188 171 172 171 170 172 171 187 172	205,242	174
1	10	0.7	245,681 278,425 270,599 269,917 271,668 230,835 274,446 271,668 234,216 283,341	156 156 156 171 156 156 171 156 155 156	263,08	158

Таблица 18. Моделирование алгоритма муравья для задачи коммивояжера с 5 городами с варьированием параметра в

б	в		Минимальная длина пути	Время, с	Средняя длина пути	Среднее время, с
1	1	0.3	199,361 199,361 199,361 200,886 199,361 200,886 199,361 199,361 199,361 199,361	218 203 218 203 203 201 218 203 201 203	199,666	207
1	1	0.5	199,361 199,361 199,361 199,361 199,361 199,361 199,361 199,361 199,361 199,361	218 218 203 218 203 233 201 218 203 218	199,361	213
1	1	0.7	199,361 199,361 199,361 199,361 200,820 200,886 199,361 199,361 199,361 199,361	203 218 218 203 218 203 218 233 234 203	199,660	215
1	1	0.9	199,361 199,361 200,820 199,361 199,361 199,361 199,361 202,074 199,361 199,361	203 219 203 203 233 201 218 203 219 202	199,779	210

Таблица 19. Моделирование алгоритма муравья для задачи коммивояжера с 5 городами с варьированием параметра

В таблицах 20-22 представлены результаты моделирования для задачи коммивояжера с 10 городами.

б	в		Минимальная длина пути	Время, с	Средняя длина пути	Среднее время, с
0	1	0.7	321,870 308,068 327,015 312,675 328,514 311,903 319,955 300,741 309,831 329,653	1559 1467 1527 1465 1513 1528 1482 1482 1498 1512	317,022	1503
0.5	1	0.7	284,406 287,922 283,283 282,414 282,153 309,718 290,238 270,586 298,913 283,216	2604 2635 2604 2652 2621 2621 2636 2604 2621 2621	287,284	2622
1	1	0.7	294,993 289,701 289,210 284,039 298,934 262,045 262,045 291,317 276,750 273,7605	1856 1825 1841 1825 1855 1825 1840 1825 1825 1839	282,279	1835
2	1	0.7	262,045 262,111 269,493 262,111 262,443 262,443 269,559 269,493 262,111 269,956	1778 1825 1763 1793 1778 1793 1778 1809 1793 1763	265,176	1787

Таблица 20. Моделирование алгоритма муравья для задачи коммивояжера с 10 городами с варьированием параметра б

б	в		Минимальная длина пути	Время, с	Средняя длина пути	Среднее время, с
1	0.5	0.7	301,973 314,680 287,527 289,109 297,898 294,584 286,253 291,363 319,092 284,295	2621 2604 2637 2589 2635 2589 2636 2621 2588 2589	296,677	2611
1	1	0.7	294,993 289,701 289,210 284,039 298,934 262,045 262,045 291,317 276,750 273,7605	1856 1825 1831 1825 1855 1821 1865 1825 1898 1832	281,279	1843
1	2	0.7	273,006 262,111 262,509 273,006 262,111 269,891 269,956 262,509 265,459 262,509	1732 1715 1732 1715 1732 1732 1716 1716 1748 1715	266,306	1725
1	5	0.7	262,509 269,956 262,509 269,956 262,509 262,509 269,956 269,956 275,364 276,506	1560 1545 1575 1543 1575 1574 1543 1560 1545 1575	268,173	1556
1	10	0.7	282,962 321,249 307,475 311,575 324,241 324,241 315,346 324,241 324,241 282,962	1482 1512 1482 1512 1482 1513 1498 1497 1513 1481	311,853	1497

Таблица 21. Моделирование алгоритма муравья для задачи коммивояжера с 10 городами с варьированием параметра в

б	в		Минимальная длина пути	Время, с	Средняя длина пути	Среднее время, с
1	1	0.3	277,575 291,751 308,649 284,866 269,891 282,169 269,559 299,115 275,185 278,432	1840 1825 1840 1825 1855 1825 1825 1856 1810 1825	283,719	1832
1	1	0.5	289,641 269,956 276,108 275,292 282,874 275,366 296,734 271,943 288,706 272,255	1872 1856 1825 1840 1826 1856 1855 1825 1841 1855	279,887	1845
1	1	0.7	287,978 288,639 282,219 281,251 280,876 269,956 274,079 276,108 269,956 284,039	1865 1872 1825 1872 1853 1812 1825 1825 1856 1872	277,510	1847
1	1	0.9	283,337 296,342 273,826 276,815 287,075 284,707 272,940 282,551 292,145 280,637	1810 1808 1840 1809 1856 1810 1808 1841 1810 1808	283,037	1820

Таблица 22. Моделирование алгоритма муравья для задачи коммивояжера с 10 городами с варьированием параметра

В таблицах 23-25 представлены результаты моделирования для задачи коммивояжера с 5 городами.

б	в		Минимальная длина пути	Время, с	Средняя длина пути	Среднее время, с
0	1	0.7	381,689 365,390 366,435 401,345 410,885 399,004 379,142 402,691 385,457 403,215	5008 5054 5211 5195 5211 5211 5148 5023 5022 5257	389,525	5134
0.5	1	0.7	366,429 377,882 373,726 375,055 376,235 372,726 349,039 380,588 345,543 344,261	9640 9626 9671 9656 9640 9703 9688 9624 9686 9734	366,148	9666
1	1	0.7	341,031 352,595 340,877 328,224 340,450 349,184 345,377 347,027 339,949 337,622	6224 6224 6240 6240 6208 6240 6285 6287 6240 6333	342,233	6252
2	1	0.7	304,471 304,471 303,926 303,926 304,471 304,471 303,926 303,926 303,926 303,926	5397 5819 5335 5771 5599 5585 5663 5506 5553 5429	304,14	5565

Таблица 23. Моделирование алгоритма муравья для задачи коммивояжера с 15 городами с варьированием параметра б

б	в		Минимальная длина пути	Время, с	Средняя длина пути	Среднее время, с
1	0.5	0.7	402,111 392,230 395,262 412,370 388,0031 380,193 383,730 367,022 394,486 398,120	9671 9952 9764 9734 9781 9750 9780 9719 9781 9703	391,352	9763
1	1	0.7	328,224 352,595 340,877 328,224 340,450 349,184 345,377 347,027 352,595 337,622	6224 6323 6240 6240 6238 6424 6285 6284 6240 6333	342,217	6283
1	2	0.7	311,791 311,395 312,564 313,759 318,585 312,264 309,150 314,608 318,085 305,591	5912 5959 5928 5959 5959 5880 5928 5880 5990 5990	312,779	5938
1	5	0.7	320,058 311,395 316,238 320,058 311,040 305,591 315,128 317,629 320,058 305,591	5600 5677 5647 5616 5600 5646 5677 5647 5710 5817	314,278	5663
1	10	0.7	359,717 359,717 367,599 375,769 357,571 368,638 358,555 373,190 337,072 375,7693	5523 5491 5552 5522 5616 5584 5569 5584 5537 5600	363,359	5557

Таблица 24. Моделирование алгоритма муравья для задачи коммивояжера с 15 городами с варьированием параметра в

б	в		Минимальная длина пути	Время, с	Средняя длина пути	Среднее время, с
1	1	0.3	362,189 326,495 332,287 355,794 355,174 348,673 362,679 352,648 349,888 363,414	6162 6145 6225 6318 6192 6224 6239 6178 6145 6255	350,924	6208
1	1	0.5	347,340 344,958 333,566 325,062 356,268 341,849 327,046 352,326 337,591 345,583	6535 6068 6145 6162 6162 6145 6130 6208 6068 6208	341,158	6183
1	1	0.7	337,622 352,595 340,877 328,224 340,450 349,184 345,377 347,027 339,949 340,450	6224 6224 6230 6240 6208 6210 6255 6297 6220 6333	342,175	6244
1	1	0.9	357,629 344,132 342,803 356,439 348,374 348,120 323,829 343,084 356,795 336,178	6099 6193 6192 6162 6224 6177 6317 6131 6162 6208	345,738	6186

Таблица 24. Моделирование алгоритма муравья для задачи коммивояжера с 15 городами с варьированием параметра

В таблицах 25-27 представлены результаты моделирования для задачи коммивояжера с 20 городами.

б	в		Минимальная длина пути	Время, с	Средняя длина пути	Среднее время, с
0	1	0.7	499,394 486,626 486,626 505,397 516,337 461,955 519,651 489,683 470,891 495,061	15927 16129 16068 16178 16130 16145 16426 15943 16068 16160	493,162	16117
0.5	1	0.7	446,739 470,199 490,320 446,486 452,234 476,644 466,741 441,192 436,684 442,349	29187 29281 29344 29204 29234 29234 29484 29484 29375 29296	456,958	29312
1	1	0.7	429,654 425,935 423,685 428,559 408,697 435,610 441,373 430,971 410,478 432,241	19796 19842 19857 19922 19890 19874 19873 19967 19889 20015	426,720	19892
2	1	0.7	349,831 345,244 341,038 349,411 341,038 361,389 344,364 357,777 347,195 341,038	17051 17237 17439 17284 17394 17096 17861 17424 18110 17253	347,832	17414

Таблица 25. Моделирование алгоритма муравья для задачи коммивояжера с 20 городами с варьированием параметра б

б	в		Минимальная длина пути	Время, с	Средняя длина пути	Среднее время, с
1	0.5	0.7	487,488 501,848 493,917 526,844 507,671 507,671 502,857 491,566 499,218 486,229	28406 28501 28736 28656 28688 28688 28907 28642 28502 28454	500,530	28618
1	1	0.7	429,654 432,241 423,685 428,559 408,697 435,610 441,373 423,685 408,697 432,241	19796 19832 19857 19952 19890 19434 19873 19967 19219 20015	426,444	19783
1	2	0.7	372,438 369,060 346,436 367,952 370,689 354,513 367,341 368,199 367,341 378,024	19016 18984 19156 18953 18890 18906 18923 18891 19000 18860	366,199	18957
1	5	0.7	374,991 377,238 368,249 364,750 381,300 374,053 374,971 364,216 374,798 372,290	17580 17674 17488 17409 17690 17549 17487 17425 17456 17612	372,685	17537
1	10	0.7	400,703 405,334 395,637 412,306 414,298 414,298 407,675 399,084 399,084 390,833	17004 49233 250520 16941 17222 36862 17301 17191 17097 167216	403,925	60658

Таблица 26. Моделирование алгоритма муравья для задачи коммивояжера с 20 городами с варьированием параметра в

б	в		Минимальная длина пути	Время, с	Средняя длина пути	Среднее время, с
1	1	0.3	372,899 409,014 387,071 414,344 411,111 438,301 418,373 432,340 431,232 436,710	19671 19672 19765 19748 19749 19687 19656 19687 19687 19827	415,139	19714
1	1	0.5	441,271 443,077 428,994 413,778 422,292 396,416 448,667 443,501 427,269 439,990	19842 19671 19625 19671 19624 19609 19624 19609 19873 19701	430,525	19684
1	1	0.7	429,654 425,935 410,478 428,559 428,559 435,610 425,935 430,971 410,478 432,241	19796 19832 19817 19922 19890 19874 19863 19967 19339 20045	426,842	19834
1	1	0.9	452,622 438,295 436,301 388,593 430,213 417,868 426,566 437,035 429,3842 446,605	19702 19749 19734 19765 19781 19719 19717 19781 19717 19905	430,348	19757

Таблица 27. Моделирование алгоритма муравья для задачи коммивояжера с 20 городами с варьированием параметра



В таблицах 28-30 представлены результаты моделирования для задачи коммивояжера с 25 городами.

б	в		Минимальная длина пути	Время, с	Средняя длина пути	Среднее время, с
0	1	0.7	606,182 570,806 580,729 595,103 623,546 608,281 553,164 501,322 603,956 613,422	35957 35941 36004 36862 36082 35896 35974 36224 36191 35910	585,651	36104
0.5	1	0.7	570,731 566,232 535,265 547,427 527,484 502,115 543,282 544,595 555,640 566,888	65628 66907 65941 65691 65598 65675 65785 65644 65723 65551	545,965	65814
1	1	0.7	525,001 508,422 527,881 512,607 516,170 501,925 500,261 512,514 506,092 534,947	44445 45037 44585 45256 44585 44522 44570 43992 44632 44585	514,582	44620
2	1	0.7	408,374 396,215 391,746 392,329 412,053 375,068 417,862 389,223 406,984 375,068	37798 38096 38376 38422 38595 38033 38579 38875 38594 38016	396,492	38338

Таблица 28. Моделирование алгоритма муравья для задачи коммивояжера с 25 городами с варьированием параметра б

б	в		Минимальная длина пути	Время, с	Средняя длина пути	Среднее время, с
1	0.5	0.7	619,137 632,135 598,434 628,177 597,788 634,564 637,260 611,795 627,146 616,642	63383 63508 63383 63321 63600 63491 63413 63227 63944 63460	620,30	63473
1	1	0.7	525,001 501,925 506,092 512,607 516,170 501,925 527,881 512,514 506,092 534,947	44445 45123 44585 45256 45585 44534 44570 42923 44632 44585	514,515	44623
1	2	0.7	413,457 417,487 418,535 418,635 414,218 417,561 409,579 407,456 423,981 425,543	42042 42010 42120 42306 41980 42026 42011 41980 42119 42042	416,645	42063
1	5	0.7	411,128 407,367 410,372 406,943 413,612 407,218 413,779 414,828 401,566 404,230	39092 39140 39094 39109 39765 78717 39529 39077 39468 39265	409,104	43225
1	10	0.7	437,036 449,886 436,766 423,885 425,185 431,411 439,998 446,258 437,036 434,819	38016 38016 38001 38203 38048 38064 38033 37985 37986 38406	436,228	38075

Таблица 29. Моделирование алгоритма муравья для задачи коммивояжера с 25 городами с варьированием параметра в

б	в		Минимальная длина пути	Время, с	Средняя длина пути	Среднее время, с
1	1	0.3	535,693 520,596 483,727 514,275 509,050 514,302 531,892 490,102 506,197 498,491	44117 44257 44508 44117 44115 44382 44100 44382 44132 44397	510,432	44250
1	1	0.5	521,860 518,299 525,348 477,727 507,674 471,031 520,677 508,273 470,320 508,193	43992 44428 44069 44194 44240 44227 44320 44366 44273 44320	502,940	44242
1	1	0.7	525,001 534,947 527,881 512,607 512,607 501,925 500,261 508,422 506,092 534,947	44445 45033 44585 45256 44585 44522 44554 43923 44632 46585	516,469	44812
1	1	0.9	506,665 500,077 492,521 494,121 510,830 515,789 525,415 523,760 517,404 515,264	44756 44413 44428 44724 44709 44601 44443 44679 44490 44617	510,184	4458

Таблица 30. Моделирование алгоритма муравья для задачи коммивояжера с 5 городами с варьированием параметра

В таблице 31 представлена информация обо всех найденных средних путях для пяти задач при всех наборах параметров , , .

Номер графика				Количество городов Средняя длина пути
				5	10	15	20	25
1	0	1	1	201,709	317,022	389,525	493,162	585,651
2	0,5	1	1	200,5	287,284	366,148	456,958	545,965
3	1	1	1	199,785	282,279	342,233	426,72	514,582
4	2	1	1	199,361	265,176	304,14	347,832	396,492
5	1	0,5	1	200,833	296,677	391,352	500,53	620,3
6	1	1	1	199,513	281,279	342,217	426,444	514,515
7	1	2	1	200,718	266,306	312,779	366,199	416,645
8	1	5	1	205,242	268,173	314,278	372,685	409,104
9	1	10	1	263,08	311,853	363,359	403,925	436,228
10	1	1	0,3	199,666	283,719	350,924	415,139	510,432
11	1	1	0,5	199,361	279,887	341,158	430,525	502,94
12	1	1	0,7	199,66	277,51	342,175	426,842	516,469
13	1	1	0,9	199,779	283,037	345,738	430,348	510,184

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

На рисунке 22 в графическом виде представлена зависимость среднего найденного пути от всех протестированных наборов параметров. Номер графика соответствует номеру набора параметров, представленном в таблице 31.

Рисунок 22. Зависимость среднего найденного пути от всех протестированных наборов параметров

Приложение 4

Исходный код программы на Matlab, решающий задачу коммивояжера алгоритмом Дейкстры

алгоритм Дейкстры

function [r_path, r_cost] = dijkstra(pathS, pathE, transmat)

% This version support detecting _cyclic-paths_

%

% USAGE:

% [path, cost]= dijkstra(pathStart, pathEnd, transMatrix)

%

% PARAMETERS:

% pathS : the index of start node, indexing from 1

% pathE : the index of end node, indexing from 1

% transmat: the transition matrix, or adjacent matrix

%

% Ensure the transition matrix is square

%

if ( size(transmat,1) ~= size(transmat,2) )

error( 'detect_cycles:Dijkstra_SC', ...

'transmat has different width and heights' );

end

% Initialization:

% noOfNode : nodes in the graph

% parent(i) : record the parent of node i

% distance(i) : the shortest distance from i to pathS

% queue : for width-first traveling of the graph

noOfNode = size(transmat, 1);

for i = 1:noOfNode

parent(i) = 0;

distance(i) = Inf;

end

queue = [];

% Start from pathS

for i=1:noOfNode

if transmat(pathS, i)~=Inf

distance(i) = transmat(pathS, i);

parent(i) = pathS;

queue = [queue i];

end

end

% Width-first exploring the whole graph

%

while length(queue) ~= 0

hopS = queue(1);

queue = queue(2:end);

for hopE = 1:noOfNode

if distance(hopE) > distance(hopS) + transmat(hopS,hopE)

distance(hopE) = distance(hopS) + transmat(hopS,hopE);

parent(hopE) = hopS;

queue = [queue hopE];

end

end

end

% Back-trace the shortest-path

%

r_path = [pathE];

i = parent(pathE);

while i~=pathS && i~=0

r_path = [i r_path];

i = parent(i);

end

if i==pathS

r_path = [i r_path];

else

r_path = []

end

% Return cost

%

r_cost = distance(pathE);

программа в Matlab для модификация диаграммы Вороного

clear all

clf

xu=50:10:70;

yu=ones(1,length(xu)).*75;

xl=xu;

yl=ones(1,length(xu)).*60;

yyu=60:5:75;

xxu=ones(1,length(yyu)).*50;

xxl=ones(1,length(yyu)).*70;

bxu=60:30:120;

byu=ones(1,length(bxu)).*40;

bxl=bxu;

byl=ones(1,length(bxl)).*20;

byyu=20:10:40;

bxxu=ones(1,length(byyu)).*60;

bxxl=ones(1,length(byyu)).*120;

dxu=80:20:120;

dyu=ones(1,length(dxu)).*110;

dxl=dxu;

dyl=ones(1,length(dxl)).*90;

dyyu=90:10:110;

dxxu=ones(1,length(dyyu)).*80;

dxxl=ones(1,length(dyyu)).*120;

dd=0:60:360;

d=deg2rad(dd);

cx=cos(d).*10+100;

cy=sin(d).*10+70;

g=deg2rad(0:30:360);

cxx=cos(g).*10+100;

cyy=sin(g).*10+70;

exu=15:10:35;

eyu=ones(1,length(exu)).*100;

exl=exu;

eyl=ones(1,length(exl)).*70;

eyyu=70:10:100;

exxu=ones(1,length(eyyu)).*15;

exxl=ones(1,length(eyyu)).*35;

wallu=0:10:150;

wall1=ones(1,length(wallu))*5;

wall2=ones(1,length(wallu))*125;

cwall=0:10:150;

cwall1=ones(1,length(cwall))*10;

cwall2=ones(1,length(cwall))*135;

hold on

plot(xu,yu,'-r','LineWidth',3)

plot(xl,yl,'-r','LineWidth',3)

plot(xxu,yyu,'r','LineWidth',3)

plot(xxl,yyu,'r','LineWidth',3)

plot(bxu,byu,'r','LineWidth',3)

plot(bxl,byl,'r','LineWidth',3)

plot(bxxu,byyu,'r','LineWidth',3)

plot(bxxl,byyu,'r','LineWidth',3)

plot(dxu,dyu,'r','LineWidth',3)

plot(dxl,dyl,'r','LineWidth',3)

plot(dxxu,dyyu,'r','LineWidth',3)

plot(dxxl,dyyu,'r','LineWidth',3)

plot(cxx,cyy,'r','LineWidth',3)

plot(exu,eyu,'r','LineWidth',3)

plot(exl,eyl,'r','LineWidth',3)

plot(exxu,eyyu,'r','LineWidth',3)

plot(exxl,eyyu,'r','LineWidth',3)

xcor=[65 8 90 45 90 130 20 125]

ycor=[10 65 10 25 115 100 110 105]

xa=[xu xl xxu xxl bxu bxl bxxu bxxl cx dxu dxl dxxu dxxl exu exl exxu exxl wallu wallu cwall1 cwall2 ];

ya=[yu yl yyu yyu byu byl byyu byyu cy dyu dyl dyyu dyyu eyu eyl eyyu eyyu wall1 wall2 cwall cwall ];

[a,b]=voronoi(xa,ya);

for pppp=1:4

clear X Y newxx newyy newx newy lengthofsize xx yy distancess dist xhh r TOTALDIS path Paths matrix totaldis R netXloc netYloc

clear totalCost

X=[a(1,:) a(2,:)];

Y=[b(1,:) b(2,:)];

mm=1;

for i=1:length(X);

if X(1,i)>140 || Y(1,i)>140 || X(1,i)<0 || Y(1,i)<0

nbnbn=0;

else

nX(1,mm)=X(1,i);

nY(1,mm)=Y(1,i);

mm=mm+1;

end

end

clear X Y

X=nX;

Y=nY;

j=1;

for i=1:length(X)

p=X(1,i);

q=Y(1,i);

if p>=60 && p<=120 && q>=20 && q<=40

z=1;

elseif p>=50 && p<=70 && q>=60 && q<=75

z=1;

elseif p>=80 && p<=120 && q>=90 && q<=110

z=1;

elseif p>=15 && p<=35 && q>=70 && q<=100

z=1;

elseif p>=95 && p<=105 && q>=65 && q<=75

z=1;

else

z=0;

end

if z==0

newxx(1,j)=p;

newyy(1,j)=q;

j=j+1;

else

aaa=1;

end

end

plot(newxx,newyy,'*g')

axis([0 150 0 150])

lengthofsize=length(newyy);

for i=1:lengthofsize

[yyyyyy,ind]=min(newyy);

newx(1,i)=newxx(1,ind);

newy(1,i)=newyy(1,ind);

newxx(1,ind)=inf;

newyy(1,ind)=inf;

end

xx=[xcor(1,pppp) newx xcor(1,pppp+4)];yy=[ycor(1,pppp) newy ycor(1,pppp+4)];

n=length(xx);

for u=1:n

for v=1:n

bbb=1;

distancess=sqrt((xx(1,v)-xx(1,u))^2+(yy(1,v)-yy(1,u))^2);

dist=distancess;

slobe=(yy(1,v)-yy(1,u))/(xx(1,v)-xx(1,u));

if abs(slobe)<0.01

if yy(1,v)>19.5 && yy(1,v)<40.5

tyty=1;

elseif yy(1,v)>59.5 && yy(1,v)<75.5

tyty=1;

elseif yy(1,v)>69.5 && yy(1,v)<100.5

tyty=1;

elseif yy(1,v)>89.5 && yy(1,v)<110.5

tyty=1;

else

tyty=0;

end

elseif abs(slobe)>100

if xx(1,v)>59.5 && xx(1,v)<120.5

tyty=1;

elseif xx(1,v)>49.5 && xx(1,v)<70.5

tyty=1;

elseif xx(1,v)>14.5 && xx(1,v)<35.5

tyty=1;

elseif xx(1,v)>79.5 && xx(1,v)<120.5

tyty=1;

else

tyty=0;

end

else

tyty=0;

end

if dist==0

bbb=2;

elseif tyty==1

bbb=2;

else

c=yy(1,u)-slobe*xx(1,u);

xhh=xx(1,u);

bbb=2;

nn=(abs(xx(1,u)-xx(1,v)))/0.05;

nn=round(nn);

k=1;

if slobe>0

coe=1;

else

coe=-1;

end

for i=1:nn

chy=slobe*(xhh+0.05*k*coe)+c;

xh=xhh+0.05*k*coe;

bbb=1;

if slobe==0

bbb=2;

elseif xh>=59 && xh<=121 && chy>=19 && chy<=41

bbb=2;

break

elseif xh>=49 && xh<=71 && chy>=59 && chy<=76

bbb=2;

break

elseif xh>=79 && xh<=121 && chy>=89 && chy<=111

bbb=2;

break

elseif xh>=14 && xh<=36 && chy>=69 && chy<=101

bbb=2;

break

elseif xh>=92 && xh<=108 && chy>=62 && chy<=79

bbb=2;

break

end

k=k+1;

end

end

if bbb==2;

r(u,v)=inf;

else

r(u,v)=distancess;

end

end

end

clear path;

[path, totalCost]=dijkstra1(1,n,r);

path

totalCost

totalcosts(1,pppp)=totalCost;

for yyyy=1:length(path)

pathss(pppp,yyyy)=path(1,yyyy);

end;

if pppp==1

for i = 1:(length(path)-1)

if path(length(path)-1)==0

break;

else

line([xx(path(i)) xx(path(i+1))], [yy(path(i)) yy(path(i+1))], 'Color','b','LineWidth', 0.75, 'LineStyle', '-');

end

end;

elseif pppp==2

for i = 1:(length(path)-1)

if path(length(path)-1)==0

break;

else

line([xx(path(i)) xx(path(i+1))], [yy(path(i)) yy(path(i+1))], 'Color','r','LineWidth', 0.75, 'LineStyle', '--');

end;

end;

elseif pppp==3

for i = 1:(length(path)-1)

if path(length(path)-1)==0

break;

else

line([xx(path(i)) xx(path(i+1))], [yy(path(i)) yy(path(i+1))], 'Color','c','LineWidth', 0.75, 'LineStyle', '-');

end;

end;

else

for i = 1:(length(path)-1)

if path(length(path)-1)==0

break;

else

line([xx(path(i)) xx(path(i+1))], [yy(path(i)) yy(path(i+1))], 'Color','k','LineWidth', 0.75, 'LineStyle', '-.');

end;

end;

end;

hold on

if pppp==1

plot([xcor(1,pppp) xcor(1,pppp+4)],[ycor(1,pppp) ycor(1,pppp+4)],'bd')

elseif pppp==2

plot([xcor(1,pppp) xcor(1,pppp+4)],[ycor(1,pppp) ycor(1,pppp+4)],'rs')

elseif pppp==3

plot([xcor(1,pppp) xcor(1,pppp+4)],[ycor(1,pppp) ycor(1,pppp+4)],'co')

else

plot([xcor(1,pppp) xcor(1,pppp+4)],[ycor(1,pppp) ycor(1,pppp+4)],'kd')

end;

hold on

end;

Размещено на Allbest.ru