Study project - Evolutionary and metaheuristic algorithms. PUT Poznań 2019 - ITI
First part of exercise, prepare implementations:
- Read instance from file
- Calculate Euclidean distance as matrix
- Prim's algorithm
- Naive clustering algorithm
- Regret clustering algorithm
Mean of penalties for naive = 39.900595119245025
Mean of penalties for random init = 135.75271621549777
Mean of penalties for naive = 35.49503486771387
Mean of penalties for random init = 135.08643123338223
Mean of penalties for naive = 39.011295834053264
Mean of penalties for random init = 135.53711196324468
Mean of penalties for naive = 35.14187076629383
Mean of penalties for random init = 135.9655738700544
Mean of penalties for naive = 36.27305307962702
Mean of penalties for random init = 135.03082032364546
Mean of penalties for naive = 37.80474634484859
Mean of penalties for random init = 135.53917109012156
Mean of penalties for naive = 37.9211106317265
Mean of penalties for random init = 134.49742108496406
Mean of penalties for naive = 37.62284207220346
Mean of penalties for random init = 134.78697916669196
Mean of penalties for naive = 33.26663091241597
Mean of penalties for random init = 135.49551031675114
Mean of penalties for naive = 35.33140109218009
Mean of penalties for random init = 134.50362845023557
Mean of penalties for naive = 39.900886226803806
Mean of penalties for random init = 135.51275900494971
Mean of penalties for naive = 35.36383510202018
Mean of penalties for random init = 134.95367055220137
Mean of penalties for naive = 34.70790041365516
Mean of penalties for random init = 134.96684454529964
Mean of penalties for naive = 34.04393846527409
Mean of penalties for random init = 135.52493772198423
Mean of penalties for naive = 41.02995309804462
Mean of penalties for random init = 134.36928114239032
Mean of penalties for naive = 34.985965060647764
Mean of penalties for random init = 135.1189289535232
Mean of penalties for naive = 42.39500221114502
Mean of penalties for random init = 135.29563652286814
Mean of penalties for naive = 38.34308783835723
Mean of penalties for random init = 134.8486535837417
Mean of penalties for naive = 36.05088510007149
Mean of penalties for random init = 136.15561382296505
Mean of penalties for naive = 30.901651837390773
Mean of penalties for random init = 136.4969211462216
Mean of penalties for naive = 35.31648523268266
Mean of penalties for random init = 133.55303122335476
Mean of penalties for naive = 39.17170751502611
Mean of penalties for random init = 135.58531921030928
Mean of penalties for naive = 39.248722757967435
Mean of penalties for random init = 135.64266394275188
Mean of penalties for naive = 38.755640503341766
Mean of penalties for random init = 135.33948196214578
Mean of penalties for naive = 43.023145145956676
Mean of penalties for random init = 135.39298776559903
Mean of penalties for naive = 35.616507352551466
Mean of penalties for random init = 135.56147591388546
Mean of penalties for naive = 33.223328187807425
Mean of penalties for random init = 136.35983373563704
Mean of penalties for naive = 41.856836668782094
Mean of penalties for random init = 135.99281238506796
Mean of penalties for naive = 35.340426480663574
Mean of penalties for random init = 136.14263965007012
Mean of penalties for naive = 37.18430781062369
Mean of penalties for random init = 134.44625996996774
Mean of penalties for naive = 32.94985820584259
Mean of penalties for random init = 135.12071133428014
Mean of penalties for naive = 34.089230873014614
Mean of penalties for random init = 134.45565990274355
Mean of penalties for naive = 37.638773422732456
Mean of penalties for random init = 133.9779997622594
Mean of penalties for naive = 40.76166841400741
Mean of penalties for random init = 134.53324000148496
Mean of penalties for naive = 31.948124215708138
Mean of penalties for random init = 134.745224499092
Mean of penalties for naive = 37.669385364548596
Mean of penalties for random init = 136.52273177585784
Mean of penalties for naive = 39.63455570840816
Mean of penalties for random init = 135.57804143585523
Mean of penalties for naive = 36.38740322874589
Mean of penalties for random init = 135.6815333885813
Mean of penalties for naive = 40.17723028332459
Mean of penalties for random init = 134.32593953358054
Mean of penalties for naive = 36.18627893264114
Mean of penalties for random init = 134.69792358368616
Mean of penalties for naive = 44.09158556951911
Mean of penalties for random init = 136.21501314258904
Mean of penalties for naive = 40.26804701293543
Mean of penalties for random init = 136.09174588002173
Mean of penalties for naive = 43.04029475251489
Mean of penalties for random init = 134.9388518813835
Mean of penalties for naive = 34.23298538964543
Mean of penalties for random init = 135.90324351042983
Mean of penalties for naive = 33.41696608229438
Mean of penalties for random init = 133.14792747432602
Mean of penalties for naive = 34.15615702211205
Mean of penalties for random init = 135.15719493540536
Mean of penalties for naive = 59.57623240857713
Mean of penalties for random init = 136.37206913065458
Mean of penalties for naive = 32.41340062534244
Mean of penalties for random init = 135.73954877131666
Mean of penalties for naive = 37.10353341063197
Mean of penalties for random init = 136.07124569107285
Mean of penalties for naive = 36.819609307448296
Mean of penalties for random init = 135.71112417280727
Mean of penalties for naive = 33.541319896861104
Mean of penalties for random init = 134.5019092118047
Mean of penalties for naive = 35.290931642972566
Mean of penalties for random init = 134.77896622712015
Mean of penalties for naive = 36.12220491903022
Mean of penalties for random init = 135.17407420148783
Mean of penalties for naive = 35.190899463341275
Mean of penalties for random init = 134.45964324443088
Mean of penalties for naive = 37.47742096690287
Mean of penalties for random init = 135.2097598399406
Mean of penalties for naive = 35.04175841301276
Mean of penalties for random init = 136.11674861218074
Mean of penalties for naive = 37.648039928314134
Mean of penalties for random init = 136.352030064664
Mean of penalties for naive = 38.41427878228459
Mean of penalties for random init = 136.1770739996943
Mean of penalties for naive = 33.04501746484601
Mean of penalties for random init = 134.42339339009163
Mean of penalties for naive = 38.95095018790154
Mean of penalties for random init = 135.62854975085187
Mean of penalties for naive = 57.17727882979429
Mean of penalties for random init = 134.2982170651456
Mean of penalties for naive = 43.61069090412381
Mean of penalties for random init = 135.60148705728474
Mean of penalties for naive = 39.59771970158356
Mean of penalties for random init = 137.19366845224803
Mean of penalties for naive = 42.03007536926168
Mean of penalties for random init = 136.05409852675302
Mean of penalties for naive = 41.06538340102205
Mean of penalties for random init = 134.2493604824708
Mean of penalties for naive = 34.77622997294535
Mean of penalties for random init = 135.97352453124665
Mean of penalties for naive = 37.61345565856387
Mean of penalties for random init = 135.37147273693063
Mean of penalties for naive = 40.33303213629305
Mean of penalties for random init = 135.04235860439806
Mean of penalties for naive = 35.82111604865718
Mean of penalties for random init = 134.36896234854146
Mean of penalties for naive = 36.96120614963395
Mean of penalties for random init = 134.91637318449258
Mean of penalties for naive = 36.72026152956373
Mean of penalties for random init = 133.88045651862953
Mean of penalties for naive = 36.51349633538395
Mean of penalties for random init = 135.74963361000374
Mean of penalties for naive = 31.86104202076033
Mean of penalties for random init = 134.79940173846632
Mean of penalties for naive = 44.435084276361586
Mean of penalties for random init = 133.87028754826454
Mean of penalties for naive = 34.765975485191824
Mean of penalties for random init = 135.13789701518925
Mean of penalties for naive = 39.231442811472306
Mean of penalties for random init = 135.81567073251057
Mean of penalties for naive = 35.94437885572257
Mean of penalties for random init = 135.33757366359518
Mean of penalties for naive = 36.435787099436396
Mean of penalties for random init = 135.5189748853278
Mean of penalties for naive = 37.33800723430211
Mean of penalties for random init = 135.91761983042926
Mean of penalties for naive = 37.80715779600092
Mean of penalties for random init = 135.8078863308988
Mean of penalties for naive = 36.63910150494236
Mean of penalties for random init = 136.63873709629928
Mean of penalties for naive = 39.62964558465717
Mean of penalties for random init = 137.44013135455674
Mean of penalties for naive = 36.366441608892025
Mean of penalties for random init = 136.10280151021067
Mean of penalties for naive = 35.87703008749238
Mean of penalties for random init = 135.7685853629156
Mean of penalties for naive = 36.63517916884184
Mean of penalties for random init = 134.6290496123004
Mean of penalties for naive = 44.46132801699366
Mean of penalties for random init = 134.91027790344413
Mean of penalties for naive = 36.658739805168025
Mean of penalties for random init = 135.89384555604593
Mean of penalties for naive = 38.899077937227084
Mean of penalties for random init = 134.57157399556735
Mean of penalties for naive = 40.83573911077482
Mean of penalties for random init = 135.56664963555835
Mean of penalties for naive = 35.16424479591292
Mean of penalties for random init = 134.9415856334793
Mean of penalties for naive = 36.93533045016222
Mean of penalties for random init = 134.51314609851977
Mean of penalties for naive = 36.67794375676952
Mean of penalties for random init = 134.86314103731397
Mean of penalties for naive = 43.45155489143641
Mean of penalties for random init = 135.89650554796387
Mean of penalties for naive = 43.129314190067916
Mean of penalties for random init = 135.21915060201465
Mean of penalties for naive = 36.53388938510102
Mean of penalties for random init = 135.5257946436275
Mean of penalties for naive = 42.16305366081355
Mean of penalties for random init = 136.5845994280568
Mean of penalties for naive = 40.20175222653635
Mean of penalties for random init = 135.1213851330335
Mean of penalties for naive = 37.5437131357445
Mean of penalties for random init = 135.32729969524763
Mean of penalties for naive = 35.615837596261095
Mean of penalties for random init = 135.3291241756271
Mean of penalties for naive = 37.12052881010973
Mean of penalties for random init = 136.35753243566407
=====
Min result for naive greedy = 26.390124159687748
Min result for random greedy = 26.37331079380186
Min result for naive steepest = 26.390124159687915
Min result for random steepest = 26.395535870862762
Mean result for naive greedy = 27.003651057926387
Mean result for random greedy = 26.955423093553318
Mean result for naive steepest = 27.271734484801595
Mean result for random steepest = 27.12499900178513
Max result for naive greedy = 29.077647974429212
Max result for random greedy = 27.995741849103318
Max result for naive steepest = 28.82608459848714
Max result for random steepest = 28.866394996897064
TIMING:
Min time for naive greedy = 1.10630231E8
Min time for random greedy = 3.42253459E8
Min time for naive steepest = 8.35229369E8
Min time for random steepest = 4.505142579E9
Mean time for naive greedy = 1.9065575608E8
Mean time for random greedy = 4.1408087362E8
Mean time for naive steepest = 1.48732848527E9
Mean time for random steepest = 5.52419767697E9
Max time for naive greedy = 6.07953681E8
Max time for random greedy = 7.12567084E8
Max time for naive steepest = 3.289188956E9
Max time for random steepest = 7.511130793E9
Min result for naive steepest = 26.395535870863323
Min result for naive steepest candidate = 26.652335284818715
Min result for naive steepest cache = 26.69310154235926
Min result for naive steepest candidate + cache = 27.157902517321197
Mean result for naive steepest = 27.270848152743273
Mean result for naive steepest candidate = 27.82201849737944
Mean result for naive steepest cache = 28.689225709127886
Mean result for naive steepest candidate + cache = 29.56522990870902
Max result for naive steepest = 28.672883938984224
Max result for naive steepest candidate = 31.253620683755926
Max result for naive steepest cache = 32.775639549293956
Max result for naive steepest candidate + cache = 34.09466226249165
TIMING:
Min time for naive steepest = 8.16427113E8
Min time for naive steepest candidate = 5.50219609E8
Min time for naive steepest cache = 6.570077491E9
Min time for naive steepest candidate + cache = 1.35000992E8
Mean time for naive steepest = 1.40433823153E9
Mean time for naive steepest candidate = 9.6736037531E8
Mean time for naive steepest cache = 2.349565652522E10
Mean time for naive steepest candidate + cache = 6.8870383674E8
Max time for naive steepest = 2.328463603E9
Max time for naive steepest candidate = 2.050889699E9
Max time for naive steepest cache = 4.0168981048E10
Max time for naive steepest candidate + cache = 2.520349143E9
Min result for MSLS = 26.373310793801114
Min result for ILS small perturbation = 26.741260751749792
Min result for ILS big random perturbation = 26.373310793801835
Min result for ILS big heuristic perturbation = 26.37331079380183
Mean result for MSLS = 26.379266000591805
Mean result for ILS small perturbation = 27.18527906869686
Mean result for ILS big random perturbation = 26.414335063148304
Mean result for ILS big heuristic perturbation = 26.876501906065585
Max result for MSLS = 26.395535870863107
Max result for ILS small perturbation = 27.820126930722033
Max result for ILS big random perturbation = 26.490608638583936
Max result for ILS big heuristic perturbation = 27.335237007683777
TIMING:
Min time for MSLS = 38.59564335
Min time for ILS small perturbation = 392.697860707
Min time for ILS big random perturbation = 392.700572927
Min time for ILS big heuristic perturbation = 392.743207554
Mean time for MSLS = 39.97228733398
Mean time for ILS small perturbation = 399.760888031
Mean time for ILS big random perturbation = 399.7769527616
Mean time for ILS big heuristic perturbation = 399.7722327566
Max time for MSLS = 52.18850176
Max time for ILS small perturbation = 446.754591477
Max time for ILS big random perturbation = 446.817009173
Max time for ILS big heuristic perturbation = 446.821177664