source: liacs/ai/graaf/ga.cpp.tex@ 220

Last change on this file since 220 was 2, checked in by Rick van der Zwet, 15 years ago

Initial import of data of old repository ('data') worth keeping (e.g. tracking
means of URL access statistics)
File size: 39.0 KB
Line 
1% Generator: GNU source-highlight, by Lorenzo Bettini, http://www.gnu.org/software/src-highlite
2\noindent
3\mbox{}\texttt{001:} \textit{/*\ File\ \ \ \ \ \ \ \ :\ ga.cpp} \\
4\mbox{}\texttt{002:} \textit{\ *\ Authors\ \ \ \ \ :\ Rick\ van\ der\ Zwet\ \&\ Thomas\ Steenbergen} \\
5\mbox{}\texttt{003:} \textit{\ *\ S-number\ \ \ \ :\ 0433373\ /\ 0117544\ } \\
6\mbox{}\texttt{004:} \textit{\ *\ Version\ \ \ \ \ :\ \$Id:\ ga.cpp\ 610\ 2008-05-13\ 07:25:13Z\ rick\ \$} \\
7\mbox{}\texttt{005:} \textit{\ *\ Licence\ \ \ \ \ :\ BSD} \\
8\mbox{}\texttt{006:} \textit{\ *\ Description\ :\ 4th\ Assignment\ AI\ 2008:\ Genetic\ Algoithm} \\
9\mbox{}\texttt{007:} \textit{\ */} \\
10\mbox{}\texttt{008:} \\
11\mbox{}\texttt{009:} \textbf{\#include}\ \texttt{$<$iostream$>$} \\
12\mbox{}\texttt{010:} \textbf{\#include}\ \texttt{$<$climits$>$} \\
13\mbox{}\texttt{011:} \textbf{\#include}\ \texttt{$<$ctime$>$} \\
14\mbox{}\texttt{012:} \textbf{\#include}\ \texttt{$<$cstdlib$>$} \\
15\mbox{}\texttt{013:} \textbf{\#include}\ \texttt{$<$fstream$>$} \\
16\mbox{}\texttt{014:} \textbf{\#include}\ \texttt{$<$math.h$>$} \\
17\mbox{}\texttt{015:} \textbf{\#include}\ \texttt{$<$string$>$} \\
18\mbox{}\texttt{016:} \textbf{\#include}\ \texttt{$<$sysexits.h$>$} \\
19\mbox{}\texttt{017:} \\
20\mbox{}\texttt{018:} \textbf{using}\ \textbf{namespace}\ std; \\
21\mbox{}\texttt{019:} \\
22\mbox{}\texttt{020:} \textit{/*NOTE:\ Graph\ can\ only\ have\ this\ many\ nodes\ */} \\
23\mbox{}\texttt{021:} \textbf{\#define}\ MAX$\_$NODES\ 50 \\
24\mbox{}\texttt{022:} \textbf{\#define}\ MAX$\_$ARCHS\ 250 \\
25\mbox{}\texttt{023:} \\
26\mbox{}\texttt{024:} \textit{/*NOTE:\ Maximum\ numbers\ of\ newly\ generated\ children\ */} \\
27\mbox{}\texttt{025:} \textbf{\#define}\ MAX$\_$POP\ 20 \\
28\mbox{}\texttt{026:} \\
29\mbox{}\texttt{027:} \textit{/*NOTE:\ The\ chance\ to\ which\ we\ mutate\ a\ given\ point\ */} \\
30\mbox{}\texttt{028:} \textbf{\#define}\ MUT$\_$LEV\ 50 \\
31\mbox{}\texttt{029:} \\
32\mbox{}\texttt{030:} \textit{/*NOTE:\ The\ maximum\ number\ of\ generations\ that\ the\ algorithm\ runs\ */} \\
33\mbox{}\texttt{031:} \textbf{\#define}\ DEFAULT$\_$LOOPS\ 100000 \\
34\mbox{}\texttt{032:} \\
35\mbox{}\texttt{033:} \textbf{\#define}\ DEFAULT$\_$FILENAME\ \texttt{"{}input.txt"{}} \\
36\mbox{}\texttt{034:} \textbf{\#define}\ MAX$\_$COORDINATES\ 1000 \\
37\mbox{}\texttt{035:} \\
38\mbox{}\texttt{036:} \\
39\mbox{}\texttt{037:} \textbf{struct}\ arch\ \{ \\
40\mbox{}\texttt{038:} \ \ \ \ int\ a,\ b; \\
41\mbox{}\texttt{039:} \ \ \ \ double\ distance; \\
42\mbox{}\texttt{040:} \\
43\mbox{}\texttt{041:} \ \ \ \ \textbf{arch}()\ \{ \\
44\mbox{}\texttt{042:} \ \ \ \ a\ =\ -1; \\
45\mbox{}\texttt{043:} \ \ \ \ b\ =\ -1; \\
46\mbox{}\texttt{044:} \ \ \ \ distance\ =\ -1; \\
47\mbox{}\texttt{045:} \ \ \ \ \} \\
48\mbox{}\texttt{046:} \}; \\
49\mbox{}\texttt{047:} \\
50\mbox{}\texttt{048:} \textit{/*\ Coordinate\ of\ point\ in\ graph\ */} \\
51\mbox{}\texttt{049:} \textbf{struct}\ point\ \{ \\
52\mbox{}\texttt{050:} \ \ \ \ int\ x,\ y;\ \ \ \ \ \ \ \textit{/*\ X,Y\ coordinates\ */} \\
53\mbox{}\texttt{051:} \ \ \ \ \\
54\mbox{}\texttt{052:} \ \ \ \ \textbf{point}()\{ \\
55\mbox{}\texttt{053:} \ \ \ \ \ \ x\ =\ -1; \\
56\mbox{}\texttt{054:} \ \ \ \ \ \ y\ =\ -1; \\
57\mbox{}\texttt{055:} \ \ \ \ \} \\
58\mbox{}\texttt{056:} \}; \\
59\mbox{}\texttt{057:} \\
60\mbox{}\texttt{058:} \textit{/*\ Comparision\ between\ 2\ points\ */} \\
61\mbox{}\texttt{059:} bool\ \textbf{operator}==(point\ \&a,\ point\ \&b)\ \{ \\
62\mbox{}\texttt{060:} \ \ \ \ \textbf{if}\ (\ (a.x\ ==\ b.x)\ \&\&\ (a.y\ ==\ b.y)) \\
63\mbox{}\texttt{061:} \ \ \ \ \ \ \ \ \textbf{return}\ \textbf{true}; \\
64\mbox{}\texttt{062:} \ \ \ \ \textbf{else} \\
65\mbox{}\texttt{063:} \ \ \ \ \ \ \ \ \textbf{return}\ \textbf{false}; \\
66\mbox{}\texttt{064:} \} \\
67\mbox{}\texttt{065:} \\
68\mbox{}\texttt{066:} \textbf{struct}\ graph\ \{ \\
69\mbox{}\texttt{067:} \ \ \ \ point\ nodes[MAX$\_$NODES];\ \ \ \textit{/*\ Location\ of\ nodes\ */} \\
70\mbox{}\texttt{068:} \ \ \ \ int\ fitness;\ \ \ \ \ \ \ \ \ \ \ \ \ \ \textit{/*\ Overall\ fitness\ graph\ */} \\
71\mbox{}\texttt{069:} \ \ \ \ int\ fitnessDistance; \\
72\mbox{}\texttt{070:} \ \ \ \ int\ fitnessIntersection; \\
73\mbox{}\texttt{071:} \ \ \ \ \\
74\mbox{}\texttt{072:} \ \ \ \ \textbf{graph}()\ \{ \\
75\mbox{}\texttt{073:} \ \ \ \ \ \ fitness\ =\ -1; \\
76\mbox{}\texttt{074:} \ \ \ \ \ \ fitnessDistance\ =\ -1; \\
77\mbox{}\texttt{075:} \ \ \ \ \ \ fitnessIntersection\ =\ -1; \\
78\mbox{}\texttt{076:} \ \ \ \ \} \\
79\mbox{}\texttt{077:} \}; \\
80\mbox{}\texttt{078:} \\
81\mbox{}\texttt{079:} \textit{/*} \\
82\mbox{}\texttt{080:} \textit{\ *\ BEGIN\ Global\ variables\ } \\
83\mbox{}\texttt{081:} \textit{\ */} \\
84\mbox{}\texttt{082:} \\
85\mbox{}\texttt{083:} arch\ archs[MAX$\_$ARCHS];\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \textit{/*\ arch\ listing\ in\ graph\ */} \\
86\mbox{}\texttt{084:} int\ num$\_$archs\ =\ -1;\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \textit{/*\ Number\ of\ archs\ in\ graph\ */} \\
87\mbox{}\texttt{085:} int\ num$\_$nodes\ =\ -1;\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \textit{/*\ Number\ of\ nodes\ in\ graph\ */} \\
88\mbox{}\texttt{086:} int\ max$\_$cord\ =\ -1;\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \textit{/*\ Domain\ e.g.\ maximum\ coord\ of\ X,\ Y*/} \\
89\mbox{}\texttt{087:} int\ lon$\_$con\ =\ -1;\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \textit{/*\ Longest\ connection\ of\ two\ points\ */} \\
90\mbox{}\texttt{088:} int\ distances\ [MAX$\_$NODES][MAX$\_$NODES];\ \textit{/*\ Distances\ between\ node\ i\ and\ j\ */} \\
91\mbox{}\texttt{089:} graph\ population[MAX$\_$POP];\ \ \ \ \ \ \ \ \ \ \ \ \textit{/*\ Graph\ list\ */} \\
92\mbox{}\texttt{090:} \\
93\mbox{}\texttt{091:} \textit{/*} \\
94\mbox{}\texttt{092:} \textit{\ *\ END\ Global\ variables} \\
95\mbox{}\texttt{093:} \textit{\ */} \\
96\mbox{}\texttt{094:} \\
97\mbox{}\texttt{095:} \\
98\mbox{}\texttt{096:} \\
99\mbox{}\texttt{097:} \textit{/*\ Calculates\ the\ distance\ between\ two\ points} \\
100\mbox{}\texttt{098:} \textit{\ *\ Distance\ (A,B)\ =\ d((x1,y1),(x2,y2))=SQRT((x1-x2)\textasciicircum{}2+(y1-y2)\textasciicircum{}2)} \\
101\mbox{}\texttt{099:} \textit{\ */} \\
102\mbox{}\texttt{100:} double\ \textbf{calcDistance}(point\ A,\ point\ B)\ \{ \\
103\mbox{}\texttt{101:} \ \ double\ dist\ =\ 0; \\
104\mbox{}\texttt{102:} \ \ dist\ =\ \textbf{sqrt}(\textbf{pow}((A.x\ -\ B.x),2)\ +\ \textbf{pow}((A.y\ -\ B.y),2)); \\
105\mbox{}\texttt{103:} \ \ \textbf{return}\ dist; \\
106\mbox{}\texttt{104:} \} \\
107\mbox{}\texttt{105:} \\
108\mbox{}\texttt{106:} \textit{/*\ How\ well\ is\ the\ scaling\ of\ the\ branches\ ofthis\ graph\ weel\ } \\
109\mbox{}\texttt{107:} \textit{\ *\ versus\ the\ input\ graph.\ The\ more\ it\ deviates\ of\ the\ orginal\ the\ higher} \\
110\mbox{}\texttt{108:} \textit{\ *\ the\ fitness\ number.} \\
111\mbox{}\texttt{109:} \textit{\ */} \\
112\mbox{}\texttt{110:} int\ \textbf{fitnessDistance}(graph\&\ A)\ \{ \\
113\mbox{}\texttt{111:} \ \ int\ i,j; \\
114\mbox{}\texttt{112:} \ \ int\ org$\_$dist\ =\ 0;\ \ \textit{//\ distance\ between\ 2\ points\ in\ input\ graph} \\
115\mbox{}\texttt{113:} \ \ double\ new$\_$dist\ =\ 0;\ \ \textit{//\ distance\ between\ 2\ points\ in\ population\ graph} \\
116\mbox{}\texttt{114:} \ \ double\ diff$\_$dist\ =\ 0;\ \textit{//\ absolute\ difference} \\
117\mbox{}\texttt{115:} \ \ int\ tmp$\_$fitness\ =\ 0; \\
118\mbox{}\texttt{116:} \\
119\mbox{}\texttt{117:} \ \ \textbf{for}\ (i=0;\ i$<$\ num$\_$nodes;\ i++)\ \{ \\
120\mbox{}\texttt{118:} \ \ \ \ \textbf{for}\ (j=i+1;\ j$<$\ num$\_$nodes;\ j++)\ \{ \\
121\mbox{}\texttt{119:} \ \ \ \ \ \ org$\_$dist\ =\ distances[i][j]; \\
122\mbox{}\texttt{120:} \ \ \ \ \ \ \textbf{if}\ (org$\_$dist\ !=\ 0)\{ \\
123\mbox{}\texttt{121:} \ \ \ \ \ \ \ \ new$\_$dist\ =\ \textbf{calcDistance}(A.nodes[i],A.nodes[j]); \\
124\mbox{}\texttt{122:} \ \ \ \ \ \ \ \ diff$\_$dist\ =\ \textbf{fabs}(new$\_$dist\ -\ org$\_$dist); \\
125\mbox{}\texttt{123:} \ \ \ \ \ \ \ \ tmp$\_$fitness\ +=\ diff$\_$dist; \\
126\mbox{}\texttt{124:} \ \ \ \ \ \ \} \\
127\mbox{}\texttt{125:} \ \ \ \ \} \\
128\mbox{}\texttt{126:} \ \ \} \\
129\mbox{}\texttt{127:} \\
130\mbox{}\texttt{128:} \ \ \textbf{return}(tmp$\_$fitness); \\
131\mbox{}\texttt{129:} \} \\
132\mbox{}\texttt{130:} \\
133\mbox{}\texttt{131:} \textit{/*\ Output\ point\ itself\ */} \\
134\mbox{}\texttt{132:} void\ \textbf{printPoint}(point\ \&A)\ \{ \\
135\mbox{}\texttt{133:} \ \ \ \ cerr\ $<$$<$\ \ A.x\ $<$$<$\ \texttt{"{},"{}}\ $<$$<$\ A.y; \\
136\mbox{}\texttt{134:} \} \\
137\mbox{}\texttt{135:} \\
138\mbox{}\texttt{136:} \textit{/*\ Calculates\ whether\ the\ line\ A-B\ crosses\ with\ line\ C-D\ and\ wether\ in} \\
139\mbox{}\texttt{137:} \textit{\ *\ domain\ if\ so\ a\ it\ returns\ the\ point\ of\ intersection\ else\ return\ point} \\
140\mbox{}\texttt{138:} \textit{\ *\ [-1,-1]\ All\ explained\ in:} \\
141\mbox{}\texttt{139:} \textit{\ *\ }\underline{\texttt{http://www.topcoder.com/tc}}\textit{?module=Static\&d1=tutorials\&d2=geometry2} \\
142\mbox{}\texttt{140:} \textit{\ *\ }\underline{\texttt{http://en.wikipedia.org/wiki/Line-line$\_$intersection}} \\
143\mbox{}\texttt{141:} \textit{\ */} \\
144\mbox{}\texttt{142:} bool\ \textbf{calcIntersection}(point\ A,\ point\ B,\ point\ C,\ point\ D,\ point\&\ tmp)\ \{ \\
145\mbox{}\texttt{143:} \ \ double\ K,\ L,\ M; \\
146\mbox{}\texttt{144:} \ \ double\ S,\ T,\ R; \\
147\mbox{}\texttt{145:} \ \ double\ det; \\
148\mbox{}\texttt{146:} \ \ bool\ result; \\
149\mbox{}\texttt{147:} \ \ double\ distance$\_$a$\_$b; \\
150\mbox{}\texttt{148:} \\
151\mbox{}\texttt{149:} \ \ \textit{//\ rewrite\ line\ A-B\ into\ formula\ form:\ Kx\ +\ Ly\ =\ M} \\
152\mbox{}\texttt{150:} \ \ K\ =\ B.y\ -\ A.y; \\
153\mbox{}\texttt{151:} \ \ L\ =\ A.x\ -\ B.x; \\
154\mbox{}\texttt{152:} \ \ M\ =\ K\ *\ A.x\ +\ L\ *\ A.y; \\
155\mbox{}\texttt{153:} \ \ \\
156\mbox{}\texttt{154:} \ \ \textit{//\ rewrite\ line\ C-D\ into\ formula\ form:\ Sx\ +\ Ty\ =\ R} \\
157\mbox{}\texttt{155:} \ \ S\ =\ D.y\ -\ C.y; \\
158\mbox{}\texttt{156:} \ \ T\ =\ C.x\ -\ D.x; \\
159\mbox{}\texttt{157:} \ \ R\ =\ S\ *\ C.x\ +\ T\ *\ C.y; \\
160\mbox{}\texttt{158:} \\
161\mbox{}\texttt{159:} \ \ \textit{//\ Now\ we\ calculate\ the\ intersection\ between\ the\ lines} \\
162\mbox{}\texttt{160:} \ \ det\ =\ K*T\ -\ S*L; \\
163\mbox{}\texttt{161:} \\
164\mbox{}\texttt{162:} \ \ \textbf{if}(det\ ==\ 0)\{ \\
165\mbox{}\texttt{163:} \ \ \ \ \textit{/*\ Lines\ A-B\ \&\ C-D\ are\ parallel,\ checking\ wether\ they\ are\ on\ top\ of} \\
166\mbox{}\texttt{164:} \textit{\ \ \ \ \ *\ each\ other} \\
167\mbox{}\texttt{165:} \textit{\ \ \ \ \ */} \\
168\mbox{}\texttt{166:} \ \ \ \ tmp.x\ =\ -1; \\
169\mbox{}\texttt{167:} \ \ \ \ tmp.y\ =\ -1; \\
170\mbox{}\texttt{168:} \ \ \ \ result\ =\ \textbf{false}; \\
171\mbox{}\texttt{169:} \\
172\mbox{}\texttt{170:} \ \ \ \ distance$\_$a$\_$b\ =\ \textbf{calcDistance}(A,B); \\
173\mbox{}\texttt{171:} \ \ \ \ \textbf{if}\ ((\textbf{calcDistance}(A,C)\ +\ \textbf{calcDistance}(B,C)\ ==\ distance$\_$a$\_$b))\ \{ \\
174\mbox{}\texttt{172:} \ \ \ \ \ \ tmp.x\ =\ C.x; \\
175\mbox{}\texttt{173:} \ \ \ \ \ \ tmp.y\ =\ C.y; \\
176\mbox{}\texttt{174:} \ \ \ \ \ \ result\ =\ \textbf{false}; \\
177\mbox{}\texttt{175:} \ \ \ \ \}\ \textbf{else}\ \textbf{if}\ ((\textbf{calcDistance}(A,D)\ +\ \textbf{calcDistance}(B,D)\ ==\ distance$\_$a$\_$b))\ \{ \\
178\mbox{}\texttt{176:} \ \ \ \ \ \ tmp.x\ =\ D.x; \\
179\mbox{}\texttt{177:} \ \ \ \ \ \ tmp.y\ =\ D.y; \\
180\mbox{}\texttt{178:} \ \ \ \ \ \ result\ =\ \textbf{false}; \\
181\mbox{}\texttt{179:} \ \ \ \ \} \\
182\mbox{}\texttt{180:} \\
183\mbox{}\texttt{181:} \ \ \}\ \textbf{else}\ \{ \\
184\mbox{}\texttt{182:} \ \ \ \ tmp.x\ =\ (T*M\ -\ L*R)/det; \\
185\mbox{}\texttt{183:} \ \ \ \ tmp.y\ =\ (K*R\ -\ S*M)/det; \\
186\mbox{}\texttt{184:} \ \ \ \ result\ =\ \textbf{true}; \\
187\mbox{}\texttt{185:} \\
188\mbox{}\texttt{186:} \ \ \ \ \textit{/*\ Verify\ intersection\ in\ domain\ */} \\
189\mbox{}\texttt{187:} \ \ \ \ \textbf{if}\ (tmp.x\ $<$\ 0\ $|$$|$\ tmp.x\ $>$=\ max$\_$cord\ $|$$|$\ tmp.y\ $<$\ 0\ $|$$|$\ tmp.y\ $>$=\ max$\_$cord)\ \{ \\
190\mbox{}\texttt{188:} \ \ \ \ \ \ \ \ result\ =\ \textbf{false}; \\
191\mbox{}\texttt{189:} \ \ \ \ \} \\
192\mbox{}\texttt{190:} \\
193\mbox{}\texttt{191:} \ \ \ \ \textit{/*\ Verify\ intersection\ not\ a\ actual\ end\ point\ */} \\
194\mbox{}\texttt{192:} \ \ \ \ \textbf{if}\ ((tmp\ ==\ A\ $|$$|$\ tmp\ ==\ B)\ \&\&\ (tmp\ ==\ C\ $|$$|$\ tmp\ ==\ D))\ \{ \\
195\mbox{}\texttt{193:} \ \ \ \ \ \ \ \ result\ =\ \textbf{false}; \\
196\mbox{}\texttt{194:} \ \ \ \ \} \\
197\mbox{}\texttt{195:} \ \ \} \\
198\mbox{}\texttt{196:} \\
199\mbox{}\texttt{197:} \ \ \textbf{return}\ result; \\
200\mbox{}\texttt{198:} \} \\
201\mbox{}\texttt{199:} \\
202\mbox{}\texttt{200:} bool\ \textbf{calcIntersection}(point\ A,\ point\ B,\ point\ C,\ point\ D)\ \{ \\
203\mbox{}\texttt{201:} \ \ \ \ point\ tmp; \\
204\mbox{}\texttt{202:} \ \ \ \ \textbf{return}\ \textbf{calcIntersection}(A,\ B,\ C,\ D,\ tmp); \\
205\mbox{}\texttt{203:} \} \\
206\mbox{}\texttt{204:} \\
207\mbox{}\texttt{205:} \textit{/*} \\
208\mbox{}\texttt{206:} \textit{\ *\ The\ number\ of\ intersections\ a\ graph.\ How\ more\ intersections\ the\ higher} \\
209\mbox{}\texttt{207:} \textit{\ *\ the\ fitness\ number.} \\
210\mbox{}\texttt{208:} \textit{\ */} \\
211\mbox{}\texttt{209:} int\ \textbf{fitnessIntersection}(graph\&\ A)\ \{ \\
212\mbox{}\texttt{210:} \ \ int\ i,j; \\
213\mbox{}\texttt{211:} \ \ int\ tmp$\_$fitness\ =\ 0; \\
214\mbox{}\texttt{212:} \\
215\mbox{}\texttt{213:} \ \ \textbf{for}\ (i\ =\ 0;\ i\ $<$\ num$\_$archs;\ i++)\ \{ \\
216\mbox{}\texttt{214:} \ \ \ \ \textbf{for}\ (j\ =\ i\ +\ 1;\ j\ $<$\ num$\_$archs;\ j++)\ \{ \\
217\mbox{}\texttt{215:} \ \ \ \ \ \ \textbf{if}\ (\ \textbf{calcIntersection}(A.nodes[archs[i].a], \\
218\mbox{}\texttt{216:} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ A.nodes[archs[i].b], \\
219\mbox{}\texttt{217:} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ A.nodes[archs[j].a], \\
220\mbox{}\texttt{218:} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ A.nodes[archs[j].b]))\ \{ \\
221\mbox{}\texttt{219:} \ \ \ \ \ \ \ \ \ tmp$\_$fitness++; \\
222\mbox{}\texttt{220:} \ \ \ \ \ \ \} \\
223\mbox{}\texttt{221:} \ \ \ \ \} \\
224\mbox{}\texttt{222:} \ \ \} \\
225\mbox{}\texttt{223:} \ \ \textbf{return}(tmp$\_$fitness); \\
226\mbox{}\texttt{224:} \} \\
227\mbox{}\texttt{225:} \\
228\mbox{}\texttt{226:} \\
229\mbox{}\texttt{227:} \textit{/*\ Calculates\ the\ fitness\ of\ every\ graph\ in\ the\ population\ */} \\
230\mbox{}\texttt{228:} void\ \textbf{calcFitness}(graph\&\ A)\ \{ \\
231\mbox{}\texttt{229:} \ \ \ \ A.fitnessIntersection\ =\ \textbf{fitnessIntersection}(A); \\
232\mbox{}\texttt{230:} \ \ \ \ A.fitnessDistance\ =\ \textbf{fitnessDistance}(A); \\
233\mbox{}\texttt{231:} \ \ \ \ A.fitness\ =\ A.fitnessDistance\ +\ A.fitnessIntersection; \\
234\mbox{}\texttt{232:} \} \\
235\mbox{}\texttt{233:} \\
236\mbox{}\texttt{234:} void\ \textbf{crossover}(graph\&\ A,\ graph\&\ B)\{ \\
237\mbox{}\texttt{235:} \ \ \ \ \textit{/*\ XXX:\ Find\ clever\ way\ to\ combine\ the\ different\ graphs\ to\ be\ able} \\
238\mbox{}\texttt{236:} \textit{\ \ \ \ \ *\ to\ make\ new\ ones.\ Three\ to\ expiriment\ with:} \\
239\mbox{}\texttt{237:} \textit{\ \ \ \ \ *\ -\ uniform\ crossover} \\
240\mbox{}\texttt{238:} \textit{\ \ \ \ \ *\ -\ single-point\ crossover} \\
241\mbox{}\texttt{239:} \textit{\ \ \ \ \ *\ -\ partially\ mapped\ crossover} \\
242\mbox{}\texttt{240:} \textit{\ \ \ \ \ *\ All\ explained\ in:\ }\underline{\texttt{http://www.liacs.nl/}}\textit{\textasciitilde{}kosters/AI/genetisch.pdf} \\
243\mbox{}\texttt{241:} \textit{\ \ \ \ \ */} \\
244\mbox{}\texttt{242:} \\
245\mbox{}\texttt{243:} \} \\
246\mbox{}\texttt{244:} \\
247\mbox{}\texttt{245:} \textit{//\ Combine\ two\ graphs\ using\ single\ point\ crossover} \\
248\mbox{}\texttt{246:} \textit{//\ A\ single\ random\ point\ is\ chosen\ in\ a\ graph's\ node} \\
249\mbox{}\texttt{247:} \textit{//\ array\ dividing\ it\ into\ two\ halves\ e.g.\ the\ head\ and\ the\ tail.} \\
250\mbox{}\texttt{248:} \textit{//\ Then\ heads\ are\ swapped\ between\ parents\ A\ \&\ B} \\
251\mbox{}\texttt{249:} void\ \textbf{crossSingle}(graph\&\ A,\ graph\&\ B)\{ \\
252\mbox{}\texttt{250:} \ \ \ point\ tmp; \\
253\mbox{}\texttt{251:} \ \ \ unsigned\ int\ cut; \\
254\mbox{}\texttt{252:} \ \ \ unsigned\ int\ i; \\
255\mbox{}\texttt{253:} \\
256\mbox{}\texttt{254:} \ \ \ cut\ =\ \textbf{rand}()\ \%\ num$\_$nodes; \\
257\mbox{}\texttt{255:} \ \ \ \textbf{for}\ (i=0;\ i$<$\ cut;i++)\ \{ \\
258\mbox{}\texttt{256:} \ \ \ \ \ \ \ tmp\ =\ A.nodes[i]; \\
259\mbox{}\texttt{257:} \ \ \ \ \ \ \ A.nodes[i]\ =\ B.nodes[i]; \\
260\mbox{}\texttt{258:} \ \ \ \ \ \ \ B.nodes[i]\ =\ tmp; \\
261\mbox{}\texttt{259:} \ \ \ \} \\
262\mbox{}\texttt{260:} \} \\
263\mbox{}\texttt{261:} \\
264\mbox{}\texttt{262:} \textit{//\ Combine\ two\ graphs\ using\ uniform\ crossover} \\
265\mbox{}\texttt{263:} \textit{//\ The\ points\ are\ swapped\ with\ a\ fixed\ probability\ of\ 0.5.} \\
266\mbox{}\texttt{264:} void\ \textbf{crossUniform}(graph\&\ A,\ graph\&\ B)\{ \\
267\mbox{}\texttt{265:} \ \ \ point\ tmp; \\
268\mbox{}\texttt{266:} \ \ \ int\ i,\ rnd; \\
269\mbox{}\texttt{267:} \\
270\mbox{}\texttt{268:} \ \ \ \textbf{for}\ (i=0;\ i$<$\ num$\_$nodes;i++)\ \{ \\
271\mbox{}\texttt{269:} \ \ \ \ \ rnd\ =\ \textbf{rand}()\%\ 2; \\
272\mbox{}\texttt{270:} \ \ \ \ \ \textbf{if}\ (rnd\ ==\ 1)\{ \\
273\mbox{}\texttt{271:} \ \ \ \ \ \ \ tmp.x\ =\ A.nodes[i].x; \\
274\mbox{}\texttt{272:} \ \ \ \ \ \ \ A.nodes[i].x\ =\ B.nodes[i].x; \\
275\mbox{}\texttt{273:} \ \ \ \ \ \ \ B.nodes[i].x\ =\ tmp.x; \\
276\mbox{}\texttt{274:} \ \ \ \ \ \} \\
277\mbox{}\texttt{275:} \ \ \ \ \ rnd\ =\ \textbf{rand}()\%\ 2; \\
278\mbox{}\texttt{276:} \ \ \ \ \ \textbf{if}\ (rnd\ ==\ 1)\{ \\
279\mbox{}\texttt{277:} \ \ \ \ \ \ \ tmp.y\ =\ A.nodes[i].y; \\
280\mbox{}\texttt{278:} \ \ \ \ \ \ \ A.nodes[i].y\ =\ B.nodes[i].y; \\
281\mbox{}\texttt{279:} \ \ \ \ \ \ \ B.nodes[i].y\ =\ tmp.y; \\
282\mbox{}\texttt{280:} \ \ \ \ \ \} \\
283\mbox{}\texttt{281:} \ \ \ \} \\
284\mbox{}\texttt{282:} \} \\
285\mbox{}\texttt{283:} \\
286\mbox{}\texttt{284:} \\
287\mbox{}\texttt{285:} \textit{//\ Copies\ the\ contents\ of\ graph\ A\ to\ graph\ B} \\
288\mbox{}\texttt{286:} void\ \textbf{copyGraph}(graph\ \&\ A,\ graph\&\ B)\{ \\
289\mbox{}\texttt{287:} \ \ int\ i; \\
290\mbox{}\texttt{288:} \\
291\mbox{}\texttt{289:} \ \ \textbf{for}\ (i=0;\ i$<$\ num$\_$nodes;i++)\ \{ \\
292\mbox{}\texttt{290:} \ \ \ \ B.nodes[i]\ =\ A.nodes[i]; \\
293\mbox{}\texttt{291:} \ \ \} \\
294\mbox{}\texttt{292:} \ \ B.fitness\ =\ A.fitness; \\
295\mbox{}\texttt{293:} \ \ B.fitnessIntersection\ =\ A.fitnessIntersection; \\
296\mbox{}\texttt{294:} \ \ B.fitnessDistance\ =\ A.fitnessDistance; \\
297\mbox{}\texttt{295:} \} \\
298\mbox{}\texttt{296:} \\
299\mbox{}\texttt{297:} \textit{/*\ Mutate\ random\ point\ in\ a\ graph\ and\ change\ it\ to\ random\ value} \\
300\mbox{}\texttt{298:} \textit{\ *\ within\ the\ domain\ of\ points} \\
301\mbox{}\texttt{299:} \textit{\ */} \\
302\mbox{}\texttt{300:} void\ \textbf{mutateGraph\ }(int\ mutationLevel,\ graph\&\ A)\{ \\
303\mbox{}\texttt{301:} \ \ int\ i,x,y; \\
304\mbox{}\texttt{302:} \\
305\mbox{}\texttt{303:} \ \ \textbf{if}\ ((\textbf{rand}()\ \%\ 100)\ $>$\ mutationLevel)\ \{ \\
306\mbox{}\texttt{304:} \ \ \ \ \textbf{return}; \\
307\mbox{}\texttt{305:} \ \ \} \\
308\mbox{}\texttt{306:} \\
309\mbox{}\texttt{307:} \ \ i\ =\ \textbf{rand}()\ \%\ num$\_$nodes; \\
310\mbox{}\texttt{308:} \ \ x\ =\ (\textbf{rand}()\%\ max$\_$cord)+1; \\
311\mbox{}\texttt{309:} \ \ y\ =\ (\textbf{rand}()\%\ max$\_$cord)+1; \\
312\mbox{}\texttt{310:} \\
313\mbox{}\texttt{311:} \ \ A.nodes[i].x\ =\ x; \\
314\mbox{}\texttt{312:} \ \ A.nodes[i].y\ =\ y; \\
315\mbox{}\texttt{313:} \} \\
316\mbox{}\texttt{314:} \\
317\mbox{}\texttt{315:} \textit{/*\ To\ do\ selection\ we\ use\ roulettewheel\ selection,\ only\ we\ } \\
318\mbox{}\texttt{316:} \textit{\ *\ invert\ adjust\ the\ regular\ algorithm\ so\ it\ prefers} \\
319\mbox{}\texttt{317:} \textit{\ *\ the\ lowest\ fitness\ numbers\ e.g.\ the\ biggest\ slice\ of} \\
320\mbox{}\texttt{318:} \textit{\ *\ piece\ is\ now\ the\ least\ attractive.} \\
321\mbox{}\texttt{319:} \textit{\ */} \\
322\mbox{}\texttt{320:} int\ \textbf{selectGraph}()\ \{ \\
323\mbox{}\texttt{321:} \ \ int\ i; \\
324\mbox{}\texttt{322:} \ \ int\ choice\ =\ -1; \\
325\mbox{}\texttt{323:} \ \ int\ combined$\_$fitness; \\
326\mbox{}\texttt{324:} \ \ int\ fitness$\_$reverse[MAX$\_$POP]; \\
327\mbox{}\texttt{325:} \ \ int\ max$\_$fitness\ =\ INT$\_$MIN; \\
328\mbox{}\texttt{326:} \ \ int\ min$\_$fitness\ =\ INT$\_$MAX; \\
329\mbox{}\texttt{327:} \ \ int\ total$\_$fitness\ =\ 0; \\
330\mbox{}\texttt{328:} \ \ int\ wheelnumber; \\
331\mbox{}\texttt{329:} \\
332\mbox{}\texttt{330:} \ \ \textit{/*\ Find\ minimum/maximum\ */} \\
333\mbox{}\texttt{331:} \ \ min$\_$fitness\ =\ population[0].fitness; \\
334\mbox{}\texttt{332:} \ \ max$\_$fitness\ =\ population[MAX$\_$POP\ -\ 1].fitness; \\
335\mbox{}\texttt{333:} \\
336\mbox{}\texttt{334:} \ \ \textit{/*\ Set\ balanced\ fitness\ */} \\
337\mbox{}\texttt{335:} \ \ combined$\_$fitness\ =\ min$\_$fitness\ +\ max$\_$fitness; \\
338\mbox{}\texttt{336:} \ \ \textbf{for}(i=0;\ i$<$\ MAX$\_$POP;\ i++)\ \{ \\
339\mbox{}\texttt{337:} \ \ \ \ fitness$\_$reverse[i]\ =\ combined$\_$fitness\ -\ population[i].fitness; \\
340\mbox{}\texttt{338:} \ \ \ \ total$\_$fitness\ +=\ fitness$\_$reverse[i]; \\
341\mbox{}\texttt{339:} \ \ \} \\
342\mbox{}\texttt{340:} \\
343\mbox{}\texttt{341:} \ \textit{/*\ Get\ random\ number\ of\ wheel\ */} \\
344\mbox{}\texttt{342:} \ \ wheelnumber\ =\ \textbf{rand}()\ \%\ total$\_$fitness; \\
345\mbox{}\texttt{343:} \\
346\mbox{}\texttt{344:} \ \ \textit{/*\ Find\ matching\ graph\ */} \\
347\mbox{}\texttt{345:} \ \ total$\_$fitness\ =\ 0; \\
348\mbox{}\texttt{346:} \ \ \textbf{for}(i=0;\ i$<$\ MAX$\_$POP;\ i++)\ \{ \\
349\mbox{}\texttt{347:} \ \ \ \ total$\_$fitness\ +=\ fitness$\_$reverse[i]; \\
350\mbox{}\texttt{348:} \ \ \ \ \textbf{if}\ (total$\_$fitness\ $>$\ wheelnumber)\ \{ \\
351\mbox{}\texttt{349:} \ \ \ \ \ \ \ \ choice\ =\ i; \\
352\mbox{}\texttt{350:} \ \ \ \ \ \ \ \ \textbf{break}; \\
353\mbox{}\texttt{351:} \ \ \ \ \} \\
354\mbox{}\texttt{352:} \ \ \} \\
355\mbox{}\texttt{353:} \\
356\mbox{}\texttt{354:} \ \ \textbf{return}\ (choice); \\
357\mbox{}\texttt{355:} \} \\
358\mbox{}\texttt{356:} \\
359\mbox{}\texttt{357:} \textit{/*\ Set\ the\ values\ of\ a\ \ given\ graph\ to\ random\ numbers} \\
360\mbox{}\texttt{358:} \textit{\ *\ In\ other\ word\ those\ graphs\ who\ aint\ fit\ enough\ } \\
361\mbox{}\texttt{359:} \textit{\ *\ for\ the\ next\ round\ will\ be\ discarded.\ } \\
362\mbox{}\texttt{360:} \textit{\ */} \\
363\mbox{}\texttt{361:} void\ \textbf{setRandGraph}(graph\&\ A)\ \{ \\
364\mbox{}\texttt{362:} \ \ int\ i; \\
365\mbox{}\texttt{363:} \ \ \textbf{for}\ (i=0;\ i$<$\ num$\_$nodes;i++)\ \{ \\
366\mbox{}\texttt{364:} \ \ \ \ \ A.nodes[i].x\ =\ (\textbf{rand}()\%max$\_$cord)+1; \\
367\mbox{}\texttt{365:} \ \ \ \ \ A.nodes[i].y\ =\ (\textbf{rand}()\%max$\_$cord)+1; \\
368\mbox{}\texttt{366:} \ \ \ \} \\
369\mbox{}\texttt{367:} \ \ \\
370\mbox{}\texttt{368:} \ \ \textbf{calcFitness}(A); \\
371\mbox{}\texttt{369:} \} \\
372\mbox{}\texttt{370:} \\
373\mbox{}\texttt{371:} \textit{/*\ Create\ a\ graph\ and\ set\ nodes\ to\ certain\ location\ */} \\
374\mbox{}\texttt{372:} graph\ \textbf{initGraph}()\ \{ \\
375\mbox{}\texttt{373:} \ \ \ graph\ A; \\
376\mbox{}\texttt{374:} \ \ \ \textbf{setRandGraph}(A); \\
377\mbox{}\texttt{375:} \ \ \ \textbf{return}\ A; \\
378\mbox{}\texttt{376:} \} \\
379\mbox{}\texttt{377:} \\
380\mbox{}\texttt{378:} \textit{//\ Generates\ a\ population\ of\ MAX$\_$POP\ graphs\ with\ random\ coordinates} \\
381\mbox{}\texttt{379:} void\ \textbf{initPopulation\ }()\ \{ \\
382\mbox{}\texttt{380:} \ \ int\ i; \\
383\mbox{}\texttt{381:} \\
384\mbox{}\texttt{382:} \ \ \textbf{for}\ (i=0;\ i$<$\ MAX$\_$POP;i++)\ \{ \\
385\mbox{}\texttt{383:} \ \ \ \ population[i]\ =\ \textbf{initGraph}(); \\
386\mbox{}\texttt{384:} \ \ \} \\
387\mbox{}\texttt{385:} \} \\
388\mbox{}\texttt{386:} \textit{//\ Using\ bubblesort\ we\ sort\ the\ graphs\ in\ the\ population\ on\ fitness} \\
389\mbox{}\texttt{387:} void\ \textbf{sortPopulation\ }()\ \{ \\
390\mbox{}\texttt{388:} \ graph\ tmp; \\
391\mbox{}\texttt{389:} \ int\ i,\ j; \\
392\mbox{}\texttt{390:} \ \textbf{for}\ (j\ =\ 1;\ j\ $<$\ MAX$\_$POP;\ j++\ )\ \{ \\
393\mbox{}\texttt{391:} \ \ \textbf{for}\ (i\ =\ 0;\ i\ $<$\ MAX$\_$POP-j;\ i++\ )\ \{ \\
394\mbox{}\texttt{392:} \ \ \ \ \textbf{if}\ (population[i].fitness\ $>$\ population[i+1].fitness)\ \{ \\
395\mbox{}\texttt{393:} \ \ \ \ \ \ tmp\ =\ population[i]; \\
396\mbox{}\texttt{394:} \ \ \ \ \ \ population[i]\ =\ population[i+1]; \\
397\mbox{}\texttt{395:} \ \ \ \ \ \ population[i+1]\ =\ tmp; \\
398\mbox{}\texttt{396:} \ \ \ \ \} \\
399\mbox{}\texttt{397:} \ \ \} \\
400\mbox{}\texttt{398:} \ \} \\
401\mbox{}\texttt{399:} \} \\
402\mbox{}\texttt{400:} \\
403\mbox{}\texttt{401:} \textit{/*\ Opens\ input\ file\ with\ adjacency-matrix\ which\ contains\ data\ about\ the} \\
404\mbox{}\texttt{402:} \textit{\ *\ number\ of\ nodes\ (N)\ on\ the\ first\ line\ and\ the\ values\ of\ the} \\
405\mbox{}\texttt{403:} \textit{\ *\ connections\ between\ those\ nodes\ in\ a\ N\ x\ N\ matrix\ in\ the\ following} \\
406\mbox{}\texttt{404:} \textit{\ *\ lines} \\
407\mbox{}\texttt{405:} \textit{\ */} \\
408\mbox{}\texttt{406:} void\ \textbf{openFile}(char\ *\ inputFile)\ \{ \\
409\mbox{}\texttt{407:} \ \ ifstream\ input; \\
410\mbox{}\texttt{408:} \ \ int\ i,\ j; \\
411\mbox{}\texttt{409:} \ \ input.\textbf{open}(inputFile,\ ios::in); \\
412\mbox{}\texttt{410:} \\
413\mbox{}\texttt{411:} \ \ \textbf{if}\ (input)\ \{ \\
414\mbox{}\texttt{412:} \ \ \ \ cerr\ $<$$<$\ \texttt{"{}Opening\ "{}}$<$$<$\ inputFile\ $<$$<$\ \texttt{"{}..."{}}\ $<$$<$\ endl; \\
415\mbox{}\texttt{413:} \ \ \ \ input\ $>$$>$\ num$\_$nodes; \\
416\mbox{}\texttt{414:} \ \ \ \ \textbf{if}\ (num$\_$nodes\ $<$=\ 0)\ \{ \\
417\mbox{}\texttt{415:} \ \ \ \ \ \ \ \ input.\textbf{close}(); \\
418\mbox{}\texttt{416:} \ \ \ \ \ \ \ \ cerr\ $<$$<$\ \texttt{"{}Error:\ Invalid\ data\ format!"{}}\ $<$$<$\ endl; \\
419\mbox{}\texttt{417:} \ \ \ \ \ \ \ \ \textbf{exit}(EX$\_$DATAERR); \\
420\mbox{}\texttt{418:} \ \ \ \ \}\ \textbf{else}\ \textbf{if}\ (num$\_$nodes\ $<$\ MAX$\_$NODES)\ \{ \\
421\mbox{}\texttt{419:} \ \ \ \ \ \ \textbf{for}\ (i=0;\ i$<$\ num$\_$nodes;\ i++)\ \{ \\
422\mbox{}\texttt{420:} \ \ \ \ \ \ \ \ \textbf{for}\ (j=0;\ j$<$\ num$\_$nodes;\ j++)\ \{ \\
423\mbox{}\texttt{421:} \ \ \ \ \ \ \ \ \ \ input\ $>$$>$\ distances[i][j]; \\
424\mbox{}\texttt{422:} \ \ \ \ \ \ \ \ \ \ \textbf{if}\ (input.\textbf{eof}())\ \{ \\
425\mbox{}\texttt{423:} \ \ \ \ \ \ \ \ \ \ \ \ cerr\ $<$$<$\ \texttt{"{}Error:\ Invalid\ data\ format!"{}}\ $<$$<$endl; \\
426\mbox{}\texttt{424:} \ \ \ \ \ \ \ \ \ \ \ \ \textbf{exit}(EX$\_$DATAERR); \\
427\mbox{}\texttt{425:} \ \ \ \ \ \ \ \ \ \ \} \\
428\mbox{}\texttt{426:} \ \ \ \ \ \ \ \ \ \ \textbf{if}\ (distances[i][j]\ $>$\ lon$\_$con)\{ \\
429\mbox{}\texttt{427:} \ \ \ \ \ \ \ \ \ \ \ \ lon$\_$con\ =\ distances[i][j]; \\
430\mbox{}\texttt{428:} \ \ \ \ \ \ \ \ \ \ \} \\
431\mbox{}\texttt{429:} \ \ \ \ \ \ \ \ \} \\
432\mbox{}\texttt{430:} \ \ \ \ \ \ \} \\
433\mbox{}\texttt{431:} \ \ \ \ \}\ \textbf{else}\ \{ \\
434\mbox{}\texttt{432:} \ \ \ \ \ \ \ \ input.\textbf{close}(); \\
435\mbox{}\texttt{433:} \ \ \ \ \ \ \ \ cerr\ $<$$<$\ \texttt{"{}Error:\ Number\ of\ nodes\ in\ "{}}$<$$<$\ inputFile; \\
436\mbox{}\texttt{434:} \ \ \ \ \ \ \ \ cerr\ $<$$<$\ \texttt{"{}\ exceeds\ maximum\ number\ of\ nodes"{}}\ $<$$<$\ endl; \\
437\mbox{}\texttt{435:} \ \ \ \ \ \ \ \ \textbf{exit}(EX$\_$DATAERR); \\
438\mbox{}\texttt{436:} \ \ \ \ \} \\
439\mbox{}\texttt{437:} \ \ \}\ \textbf{else}\ \{ \\
440\mbox{}\texttt{438:} \ \ \ \ \ \ input.\textbf{close}(); \\
441\mbox{}\texttt{439:} \ \ \ \ \ \ cerr\ $<$$<$\ \texttt{"{}Error:\ Couldn't\ open\ file\ "{}}\ $<$$<$\ inputFile\ $<$$<$\ endl; \\
442\mbox{}\texttt{440:} \ \ \ \ \ \ \textbf{exit}(EX$\_$NOINPUT); \\
443\mbox{}\texttt{441:} \ \ \} \\
444\mbox{}\texttt{442:} \\
445\mbox{}\texttt{443:} \ \ \textit{/*\ Transform\ 2d\ structure\ to\ 1d\ archs\ to\ allow\ easy\ computations\ */} \\
446\mbox{}\texttt{444:} \ \ num$\_$archs\ =\ 0; \\
447\mbox{}\texttt{445:} \ \ \textbf{for}\ (i\ =\ 0;\ i\ $<$\ num$\_$nodes;\ i++)\ \{ \\
448\mbox{}\texttt{446:} \ \ \ \ \textbf{for}\ (j\ =\ i+1;\ j\ $<$\ num$\_$nodes;\ j++)\ \{ \\
449\mbox{}\texttt{447:} \ \ \ \ \ \ \textbf{if}\ (distances[i][j]\ $>$\ 0)\ \{ \\
450\mbox{}\texttt{448:} \ \ \ \ \ \ \ \ archs[num$\_$archs].a\ =\ i; \\
451\mbox{}\texttt{449:} \ \ \ \ \ \ \ \ archs[num$\_$archs].b\ =\ j; \\
452\mbox{}\texttt{450:} \ \ \ \ \ \ \ \ archs[num$\_$archs].distance\ =\ distances[i][j]; \\
453\mbox{}\texttt{451:} \ \ \ \ \ \ \ \ num$\_$archs++; \\
454\mbox{}\texttt{452:} \ \ \ \ \ \ \} \\
455\mbox{}\texttt{453:} \ \ \ \ \} \\
456\mbox{}\texttt{454:} \ \ \} \\
457\mbox{}\texttt{455:} \} \\
458\mbox{}\texttt{456:} \\
459\mbox{}\texttt{457:} \textit{//\ Prints\ the\ adjacency-matrix\ of\ openFile()\ to\ the\ screen} \\
460\mbox{}\texttt{458:} void\ \textbf{printDistances}()\ \{ \\
461\mbox{}\texttt{459:} \ \ int\ i,\ j; \\
462\mbox{}\texttt{460:} \\
463\mbox{}\texttt{461:} \ \ cout\ $<$$<$\ \texttt{"{}\ "{}}\ $<$$<$\ endl; \\
464\mbox{}\texttt{462:} \ \ \textbf{for}\ (i=0;\ i$<$\ num$\_$nodes;\ i++)\ \{ \\
465\mbox{}\texttt{463:} \ \ \ \ \textbf{for}\ (j=0;\ j$<$\ num$\_$nodes;\ j++)\ \{ \\
466\mbox{}\texttt{464:} \ \ \ \ \ \ \ \ \ \ \ \ cout\ $<$$<$\ distances[i][j]$<$$<$\ \texttt{"{}\ "{}}; \\
467\mbox{}\texttt{465:} \ \ \ \ \} \\
468\mbox{}\texttt{466:} \ \ \ \ cout\ $<$$<$\ endl;\ \ \ \ \ \\
469\mbox{}\texttt{467:} \ \ \} \\
470\mbox{}\texttt{468:} \ \ cout\ $<$$<$\ \texttt{"{}\ "{}}\ $<$$<$\ endl; \\
471\mbox{}\texttt{469:} \} \\
472\mbox{}\texttt{470:} \\
473\mbox{}\texttt{471:} \textit{/*\ Prints\ the\ coordinates\ of\ every\ point\ in\ a\ graph\ to\ the\ screen\ in} \\
474\mbox{}\texttt{472:} \textit{\ *\ graphviz\ compatible\ output} \\
475\mbox{}\texttt{473:} \textit{\ *\ cat\ $<$$<$EOF\ $|$\ neato\ \ -Tpng\ -oga.png\ \ \&\&\ open\ ga.png} \\
476\mbox{}\texttt{474:} \textit{\ */} \\
477\mbox{}\texttt{475:} void\ \textbf{printGraph}(graph\&\ A)\ \{ \\
478\mbox{}\texttt{476:} \ \ int\ i; \\
479\mbox{}\texttt{477:} \\
480\mbox{}\texttt{478:} \ \ cout\ $<$$<$\ \texttt{"{}graph\ G\ \{\ node\ [shape=circle,"{}} \\
481\mbox{}\texttt{479:} \ \ \ \ \ \ \ $<$$<$\ \texttt{"{}fontname=}\texttt{\textbackslash{}"{}}\texttt{Lucida\ Console}\texttt{\textbackslash{}"{}}\texttt{,margin=0,0];"{}}\ $<$$<$\ endl; \\
482\mbox{}\texttt{480:} \ \ \textbf{for}\ (i=0;\ i$<$\ num$\_$nodes;\ i++)\ \{ \\
483\mbox{}\texttt{481:} \ \ \ \ \ cout\ $<$$<$\ \texttt{"{}C"{}}\ $<$$<$\ i\ $<$$<$\ \texttt{"{}[pos=}\texttt{\textbackslash{}"{}}\texttt{"{}}\ $<$$<$\ A.nodes[i].x\ *\ 28\ $<$$<$\ \texttt{"{},"{}}\ $<$$<$ \\
484\mbox{}\texttt{482:} \ \ \ \ \ A.nodes[i].y\ *\ 28\ $<$$<$\ \texttt{"{}!}\texttt{\textbackslash{}"{}}\texttt{,\ label=}\texttt{\textbackslash{}"{}}\texttt{C"{}}\ $<$$<$\ i\ $<$$<$\ \texttt{"{}}\texttt{\textbackslash{}"{}}\texttt{];"{}}\ $<$$<$\ endl;\ \\
485\mbox{}\texttt{483:} \ \ \} \\
486\mbox{}\texttt{484:} \ \ \textbf{for}\ (i=0;\ i\ $<$\ num$\_$archs;\ i++)\ \{ \\
487\mbox{}\texttt{485:} \ \ \ \ cout\ $<$$<$\ \texttt{"{}C"{}}\ $<$$<$\ archs[i].a\ $<$$<$\ \texttt{"{}\ -\/-\ C"{}}\ $<$$<$\ archs[i].b\ $<$$<$\ \texttt{"{};"{}}\ $<$$<$\ endl; \\
488\mbox{}\texttt{486:} \ \ \} \\
489\mbox{}\texttt{487:} \ \ cout\ $<$$<$\ \texttt{"{}\}"{}}\ $<$$<$\ endl; \\
490\mbox{}\texttt{488:} \} \\
491\mbox{}\texttt{489:} \\
492\mbox{}\texttt{490:} \\
493\mbox{}\texttt{491:} \textit{//\ Prints\ every\ graph\ stored\ in\ array\ population} \\
494\mbox{}\texttt{492:} void\ \textbf{printPopulation\ }()\ \{ \\
495\mbox{}\texttt{493:} \ \ int\ i; \\
496\mbox{}\texttt{494:} \ \ cerr\ $<$$<$\ \texttt{"{}\ "{}}\ $<$$<$\ endl; \\
497\mbox{}\texttt{495:} \ \ \textbf{for}\ (i=0;\ i$<$\ MAX$\_$POP;\ i++)\ \{ \\
498\mbox{}\texttt{496:} \ \ \ \ cerr\ $<$$<$\ i\ $<$$<$\ \texttt{"{}\ =$>$\ "{}}; \\
499\mbox{}\texttt{497:} \ \ \ \ \textbf{printGraph}(population[i]); \\
500\mbox{}\texttt{498:} \ \ \} \\
501\mbox{}\texttt{499:} \ \ cerr\ $<$$<$\ \texttt{"{}\ "{}}\ $<$$<$\ endl; \\
502\mbox{}\texttt{500:} \} \\
503\mbox{}\texttt{501:} \\
504\mbox{}\texttt{502:} \\
505\mbox{}\texttt{503:} \textit{/*\ Implementation\ of\ Steady\ State\ Evolution\ Algorithm\ based\ on\ p.119\ AI} \\
506\mbox{}\texttt{504:} \textit{\ *\ Book\ */} \\
507\mbox{}\texttt{505:} int\ \textbf{main}(int\ argc,\ char\ *\ argv[])\ \{ \\
508\mbox{}\texttt{506:} \ \ int\ i,j; \\
509\mbox{}\texttt{507:} \ \ int\ org$\_$dist,\ new$\_$dist; \\
510\mbox{}\texttt{508:} \ \ int\ select$\_$one,\ select$\_$two; \\
511\mbox{}\texttt{509:} \ \ int\ loopCounter; \\
512\mbox{}\texttt{510:} \ \ unsigned\ int\ randomSeed; \\
513\mbox{}\texttt{511:} \\
514\mbox{}\texttt{512:} \ \ graph\ min; \\
515\mbox{}\texttt{513:} \ \ graph\ child$\_$one,\ child$\_$two; \\
516\mbox{}\texttt{514:} \\
517\mbox{}\texttt{515:} \ \ \textit{//\ use\ random\ seed\ to\ create\ x,y\ coordinates\ of\ a\ point} \\
518\mbox{}\texttt{516:} \ \ randomSeed\ =\ (unsigned)\textbf{time}(0); \\
519\mbox{}\texttt{517:} \ \ randomSeed\ =\ 0; \\
520\mbox{}\texttt{518:} \ \ \textbf{srand}(randomSeed); \\
521\mbox{}\texttt{519:} \ \ \textit{/*\ Debug\ static\ seed\ */} \\
522\mbox{}\texttt{520:} \ \ \textit{//\ srand(0);} \\
523\mbox{}\texttt{521:} \ \ \\
524\mbox{}\texttt{522:} \ \ \textit{//\ Open\ the\ file\ that\ \ contains\ data\ about} \\
525\mbox{}\texttt{523:} \ \ \textit{//\ the\ number\ odf\ branches\ and\ which\ branches\ are\ } \\
526\mbox{}\texttt{524:} \ \ \textit{//\ connected\ with\ each\ other} \\
527\mbox{}\texttt{525:} \ \ \textbf{if}\ (argc\ $>$=\ 2)\ \{ \\
528\mbox{}\texttt{526:} \ \ \ \ \textbf{openFile}(argv[1]); \\
529\mbox{}\texttt{527:} \ \ \}\ \textbf{else}\ \{ \\
530\mbox{}\texttt{528:} \ \ \ \ cerr\ $<$$<$\ \texttt{"{}Usage:\ "{}}\ $<$$<$\ argv[0]\ $<$$<$\ \texttt{"{}\ $<$filename$>$\ $<$loopCount$>$"{}}\ $<$$<$\ endl; \\
531\mbox{}\texttt{529:} \ \ \ \ \textbf{exit}(EX$\_$USAGE); \\
532\mbox{}\texttt{530:} \ \ \} \\
533\mbox{}\texttt{531:} \\
534\mbox{}\texttt{532:} \ \ \textbf{if}\ (argc\ ==\ 3)\ \{ \\
535\mbox{}\texttt{533:} \ \ \ \ loopCounter\ =\ \textbf{atoi}(argv[2]); \\
536\mbox{}\texttt{534:} \ \ \}\ \textbf{else}\ \{ \\
537\mbox{}\texttt{535:} \ \ \ \ loopCounter\ =\ DEFAULT$\_$LOOPS; \\
538\mbox{}\texttt{536:} \ \ \} \\
539\mbox{}\texttt{537:} \\
540\mbox{}\texttt{538:} \ \ \textit{/*\ To\ optimize\ the\ speed\ of\ the\ genetic\ algoritm\ we\ limit\ the\ domain} \\
541\mbox{}\texttt{539:} \textit{\ \ \ *\ of\ the\ points\ */} \\
542\mbox{}\texttt{540:} \ \ \textbf{if}\ ((lon$\_$con\ *\ num$\_$nodes)\ $<$\ MAX$\_$COORDINATES)\{ \\
543\mbox{}\texttt{541:} \ \ \ \ max$\_$cord\ =\ lon$\_$con\ *\ num$\_$nodes; \\
544\mbox{}\texttt{542:} \ \ \}\ \textbf{else}\ \{ \\
545\mbox{}\texttt{543:} \ \ \ \ max$\_$cord\ =\ MAX$\_$COORDINATES; \\
546\mbox{}\texttt{544:} \ \ \} \\
547\mbox{}\texttt{545:} \ \ cerr\ $<$$<$\ \texttt{"{}Domain\ of\ points\ is\ set\ to\ "{}} \\
548\mbox{}\texttt{546:} \ \ \ \ \ \ \ $<$$<$\ max$\_$cord\ $<$$<$\ \texttt{"{}\ x\ "{}}\ $<$$<$\ max$\_$cord\ $<$$<$\ endl; \\
549\mbox{}\texttt{547:} \ \ \\
550\mbox{}\texttt{548:} \ \ \textit{//\ Minimum\ graph\ to\ store\ best\ found\ solution} \\
551\mbox{}\texttt{549:} \ \ min.fitness\ =\ INT$\_$MAX; \\
552\mbox{}\texttt{550:} \ \ \\
553\mbox{}\texttt{551:} \ \ \textit{/*\ Populate\ population,\ with\ random\ values\ */} \\
554\mbox{}\texttt{552:} \ \ \textbf{initPopulation}(); \\
555\mbox{}\texttt{553:} \ \ \\
556\mbox{}\texttt{554:} \ \ \textbf{for}\ (i=0;\ i$<$\ loopCounter;\ i++)\ \{ \\
557\mbox{}\texttt{555:} \ \ \ \ \ \textit{//\ Sort\ the\ population\ of\ graphs\ so\ that\ graph} \\
558\mbox{}\texttt{556:} \ \ \ \ \ \textit{//\ with\ smallest\ fitness\ is\ placed\ in\ population[0]} \\
559\mbox{}\texttt{557:} \ \ \ \ \ \textbf{sortPopulation}(); \\
560\mbox{}\texttt{558:} \ \ \ \ \ \\
561\mbox{}\texttt{559:} \ \ \ \ \ \textit{//\ Store\ the\ lowest\ found\ fitness\ if\ it\ is\ better} \\
562\mbox{}\texttt{560:} \ \ \ \ \ \textit{//\ then\ the\ fitness\ we\ already\ had\ stored} \\
563\mbox{}\texttt{561:} \ \ \ \ \ \textbf{if}\ (min.fitness\ $>$\ population[0].fitness)\{ \\
564\mbox{}\texttt{562:} \ \ \ \ \ \ \ \ \textbf{copyGraph}(population[0],min); \\
565\mbox{}\texttt{563:} \ \ \ \ \ \} \\
566\mbox{}\texttt{564:} \ \ \ \ \ \ \ \ \ \ \\
567\mbox{}\texttt{565:} \ \ \ \ \ \textit{//\ Stop\ if\ optimal\ is\ found\ e.g\ fitness\ equals\ zero} \\
568\mbox{}\texttt{566:} \ \ \ \ \ \textbf{if}(population[0].fitness\ ==\ 0)\{ \\
569\mbox{}\texttt{567:} \ \ \ \ \ \ \textbf{break}; \\
570\mbox{}\texttt{568:} \ \ \ \ \ \} \\
571\mbox{}\texttt{569:} \ \ \ \ \ \ \ \ \ \ \\
572\mbox{}\texttt{570:} \ \ \ \ \ \textit{//\ Selection\ reproducing\ parents\ via\ roulette\ wheel} \\
573\mbox{}\texttt{571:} \ \ \ \ \ \textit{//\ fittest\ parents\ get\ selected\ } \\
574\mbox{}\texttt{572:} \ \ \ \ \ select$\_$one\ =\ \textbf{selectGraph}(); \\
575\mbox{}\texttt{573:} \ \ \ \ \ \textbf{do}\ \{ \\
576\mbox{}\texttt{574:} \ \ \ \ \ \ \ select$\_$two\ =\ \textbf{selectGraph}(); \\
577\mbox{}\texttt{575:} \ \ \ \ \ \}\textbf{while}\ (select$\_$one\ ==\ select$\_$two); \\
578\mbox{}\texttt{576:} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\
579\mbox{}\texttt{577:} \ \ \ \ \ \textit{//\ set\ points\ in\ children\ with\ crossover\ result\ of\ parents\ } \\
580\mbox{}\texttt{578:} \ \ \ \ \ \textbf{copyGraph}(population[select$\_$one],\ child$\_$one); \\
581\mbox{}\texttt{579:} \ \ \ \ \ \textbf{copyGraph}(population[select$\_$two],\ child$\_$two);\ \\
582\mbox{}\texttt{580:} \ \ \ \ \ \\
583\mbox{}\texttt{581:} \ \ \ \ \ \textit{//\ Crossover\ the\ selected\ parents\ \ } \\
584\mbox{}\texttt{582:} \ \ \ \ \ \textbf{crossUniform}(child$\_$one,\ child$\_$two); \\
585\mbox{}\texttt{583:} \ \ \ \ \ \\
586\mbox{}\texttt{584:} \ \ \ \ \ \textit{//\ mutate\ childs\ with\ small\ random\ probability\ usually\ 50\%} \\
587\mbox{}\texttt{585:} \ \ \ \ \ \textbf{mutateGraph}(99,\ child$\_$one); \\
588\mbox{}\texttt{586:} \ \ \ \ \ \textbf{mutateGraph}(99,\ child$\_$two); \\
589\mbox{}\texttt{587:} \ \ \ \ \ \\
590\mbox{}\texttt{588:} \ \ \ \ \ \textit{//\ Calculate\ fitness\ of\ both\ children} \\
591\mbox{}\texttt{589:} \ \ \ \ \ \textbf{calcFitness}(child$\_$one); \\
592\mbox{}\texttt{590:} \ \ \ \ \ \textbf{calcFitness}(child$\_$two); \\
593\mbox{}\texttt{591:} \ \ \ \ \ \\
594\mbox{}\texttt{592:} \ \ \ \ \ \textit{//\ Least\ fittest\ graphs\ in\ population\ get\ replaced} \\
595\mbox{}\texttt{593:} \ \ \ \ \ \textbf{copyGraph}(child$\_$one,population[MAX$\_$POP\ -2]); \\
596\mbox{}\texttt{594:} \ \ \ \ \ \textbf{copyGraph}(child$\_$two,population[MAX$\_$POP\ -1]); \\
597\mbox{}\texttt{595:} \ \ \} \\
598\mbox{}\texttt{596:} \ \ \\
599\mbox{}\texttt{597:} \ \ cerr\ $<$$<$\ \texttt{"{}Best\ found\ coordinates\ after\ "{}}$<$$<$\ i\ $<$$<$ \\
600\mbox{}\texttt{598:} \ \ \texttt{"{}\ epochs\ for\ given\ input\ graph:\ "{}}\ $<$$<$\ endl;\ \\
601\mbox{}\texttt{599:} \ \ \textbf{printGraph}(min); \\
602\mbox{}\texttt{600:} \ \ \\
603\mbox{}\texttt{601:} \ \ \textbf{if}(min.fitness\ !=\ 0)\{ \\
604\mbox{}\texttt{602:} \ \ \ \ \textbf{for}\ (i=0;\ i$<$\ num$\_$nodes;\ i++)\ \{ \\
605\mbox{}\texttt{603:} \ \ \ \ \ \ \textbf{for}\ (j=i+1;\ j$<$\ num$\_$nodes;\ j++)\ \{ \\
606\mbox{}\texttt{604:} \ \ \ \ \ \ \ \ org$\_$dist\ =\ distances[i][j]; \\
607\mbox{}\texttt{605:} \ \ \ \ \ \ \ \ \textbf{if}\ (org$\_$dist\ !=\ 0)\{ \\
608\mbox{}\texttt{606:} \ \ \ \ \ \ \ \ \ \ new$\_$dist\ =\ \textbf{calcDistance}(min.nodes[i],min.nodes[j]); \\
609\mbox{}\texttt{607:} \ \ \ \ \ \ \ \ \ \ cerr\ $<$$<$\ \texttt{"{}Distance\ between\ point\ C"{}}$<$$<$\ i\ $<$$<$\ \texttt{"{}\ -\ C"{}}\ $<$$<$\ j\ $<$$<$\ \texttt{"{}\ =\ "{}}; \\
610\mbox{}\texttt{608:} \ \ \ \ \ \ \ \ \ \ cerr\ $<$$<$\ \textbf{calcDistance}(min.nodes[i],min.nodes[j])\ $<$$<$\ \texttt{"{}\ "{}}; \\
611\mbox{}\texttt{609:} \ \ \ \ \ \ \ \ \ \ \textbf{if}\ (new$\_$dist\ !=\ org$\_$dist)\{ \\
612\mbox{}\texttt{610:} \ \ \ \ \ \ \ \ \ \ \ \ cerr\ $<$$<$\ \texttt{"{}SHOULD\ BE\ "{}}\ $<$$<$\ org$\_$dist\ $<$$<$\ endl; \\
613\mbox{}\texttt{611:} \ \ \ \ \ \ \ \ \ \ \}\ \textbf{else}\ \{ \\
614\mbox{}\texttt{612:} \ \ \ \ \ \ \ \ \ \ \ \ cerr\ $<$$<$\ \texttt{"{}CORRECT"{}}\ $<$$<$\ endl; \\
615\mbox{}\texttt{613:} \ \ \ \ \ \ \ \ \ \ \} \\
616\mbox{}\texttt{614:} \ \ \ \ \ \ \ \ \} \\
617\mbox{}\texttt{615:} \ \ \ \ \ \ \} \\
618\mbox{}\texttt{616:} \ \ \ \ \} \\
619\mbox{}\texttt{617:} \ \ \ \} \\
620\mbox{}\texttt{618:} \ \ cerr\ $<$$<$\ \texttt{"{}Fitness\ Intersection\ :\ "{}}\ $<$$<$\ min.fitnessIntersection\ $<$$<$\ endl; \\
621\mbox{}\texttt{619:} \ \ cerr\ $<$$<$\ \texttt{"{}Fitness\ Distance\ \ \ \ \ :\ "{}}\ $<$$<$\ min.fitnessDistance\ $<$$<$\ endl; \\
622\mbox{}\texttt{620:} \ \ cerr\ $<$$<$\ \texttt{"{}Fitness\ Overall\ \ \ \ \ \ :\ "{}}\ $<$$<$\ min.fitness\ $<$$<$\ endl; \\
623\mbox{}\texttt{621:} \ \ cerr\ $<$$<$\ \texttt{"{}Random\ seed\ \ \ \ \ \ \ \ \ \ :\ "{}}\ $<$$<$\ randomSeed\ $<$$<$\ endl; \\
624\mbox{}\texttt{622:} \ \ \textbf{return}(EX$\_$OK); \\
625\mbox{}\texttt{623:} \} \\
626
Note: See TracBrowser for help on using the repository browser.