WWW.THESIS.XLIBX.INFO FREE ELECTRONIC LIBRARY - Thesis, documentation, books

<< HOME
CONTACTS

Pages:     | 1 |   ...   | 5 | 6 || 8 |

# «An Ant Colony Optimisation Algorithm for the Bounded Diameter Minimum Spanning Tree Problem ausgef¨hrt am u Institut f¨r Computergraphik und ...»

-- [ Page 7 ] --

./Aco -t graphtype -d diameter -i instancefile [-g instancefile] [-r rho] [-s time_limit] [-l iteration_limit] [-a ants] Here in alphabetical order the list describing all optional as well as mandatory parameters

of the Aco program in detail:

• a is an optional parameter. It indicates the number of artiﬁcial ants forming the ant colony. If it is omitted a default colony size of 10 ants is used.

• d is a mandatory parameter, since it speciﬁes the diameter bound. The number declared has to be a positive integer number greater or equal to 4, otherwise an error message is prompted.

• i has also to be speciﬁed, stating the path to the instance ﬁle.

• g is only a mandatory parameter when a GNUplot graph instance is used, since GNUplot instances consist of two ﬁles, a point and a line ﬁle. So in case of a GNUplot graph instance the parameter g takes the line ﬁle, the corresponding point ﬁle has to be speciﬁed using parameter i. In case of all other graph types this parameter has to be omitted, otherwise an error message is prompted.

• l speciﬁes the maximum number of iterations without an improvement of the best solution found so far. As it is an optional parameter it can be omitted, in this case the program sets it per default to 1000.

–  –  –

• s is an optional parameter indicating the time limit in seconds, otherwise no time limit is set. Only positive integer numbers are valid values for this parameter, all other speciﬁcations will result in a corresponding error message.

• t is a mandatory parameter and speciﬁes the type of the instance ﬁle. The instance

parser used by this program is able to read in four diﬀerent ﬁle formats:

–  –  –

The output of the Aco program is sent to standard out (std::cout) per default, but it can easily be redirected to any ﬁle with the help of the appropriate Unix operator “”. The output starts with a summary of all instance relevant information, e.g. instance ﬁle, number of nodes or diameter bound. Then a summary of each iteration follows, containing various information on every ant of the colony. Each ant builds a solution exploiting the knowledge stored in the pheromone matrix. Afterwards, this solutions is tried to be improved by a VND algorithm using four diﬀerent neighbourhood structures. This iteration summary states for each artiﬁcial ant the total costs of the solution found after local improvement by VND, the total costs of the best solution found so far, time needed so far and ﬁnally an indicator if the current best solution was achieved by this ant. Finally, when a termination condition is met – either time limit or x rounds without further improvement of the best found solution – a complete summary of the optimisation process is printed, containing again all instance relevant information plus total costs of the best solution found and the time in seconds until the program was terminated. Note, that it in general the time stated at the end of this summary is not the time required to achieve the best solution. In the

following a sample output of an Aco run is presented:

------------------------------------------------------------------------Bounded diameter minimum spanning tree problem: ACO [ver. 1.0 / 10.2005]

–  –  –

Creating Solution object to save best solution... done Creating Solution object for computations... done Creating EdgeExchange object... done Creating NodeSwap object... done Creating CentreExchange object... done Creating LevelChange object... done Creating starting solution value... done

–  –  –

------------------------------------------------------------------------Ant 0 found 1877464 [vnd] 1877464 [ACO] 1.75 sec.

* Ant 1 found 1858671 [vnd] 1858671 [ACO] 3.65 sec.

Ant 2 found 1885506 [vnd] 1858671 [ACO] 5.30 sec.

Ant 4 found 1918045 [vnd] 1836331 [ACO] 8.92 sec.

Ant 5 found 1884828 [vnd] 1836331 [ACO] 11.30 sec.

Ant 6 found 1887286 [vnd] 1836331 [ACO] 13.10 sec.

Ant 7 found 1945281 [vnd] 1836331 [ACO] 15.31 sec.

Ant 8 found 1876021 [vnd] 1836331 [ACO] 18.13 sec.

Ant 9 found 1918894 [vnd] 1836331 [ACO] 20.05 sec.

------------------------------------------------------------------------Updating pheromone matrix... 1836331 [ACO] 20.05 sec.

–  –  –

------------------------------------------------------------------------COMPUTATIONAL RESULTS This chapter takes a closer look at the performance of the ACO algorithm for the BDMST problem, developed within the context of this master thesis, and compares it to that of other heuristics for the BDMST problem. Three state-of-the-art metaheuristics have been selected for this comparison, a VNS implementation by Gruber and Raidl [21], a permutation coded EA as well as a random-key coded EA from [25]. Of major interest is the comparison of the ACO presented here and the VNS by Gruber and Raidl, since they use in principle the same neighbourhood structures for their VND as it is done in the ACO, especially because the VNS is the so far leading metaheuristic for the BDMST problem.

For comparison the same instances, diameter bounds, time limits and termination conditions as in [21] were used. The instances were taken from the Beasley’s OR-Library1 and have been originally proposed for the Euclidean Steiner tree problem. All nodes of a graph are settled within the unit square and the Euclidean distance between any pair of nodes corresponds to the edge costs between these two nodes. Furthermore, as in [21], the tests were grouped into long-term and short-term runs. The long-term runs concentrated on achieving as good results as possible. In the short-term runs the diﬀerent algorithms had a relatively short time with respect to the instance size for yielding good solutions. The size of the ant colony was set to ten artiﬁcial ants for all test categories. Before presenting the computational results it should be noted, that all test runs were performed on a Pentium R 4

2.8 GHz system using Linux 2.4.21 as operating system.

First the results of the long-term runs are discussed. As in [21] the ﬁrst ﬁve instances of each size n = 100, 250, 500 available in the OR-Library were used and the diameter bound was set to 10 for instances with 100 nodes, to 15 for instances with 250 nodes, and to 20 for instances with 500 nodes. Two diﬀerent termination conditions were introduced for these long-term runs for the ACO, adopted from [21]: The ACO algorithm terminated either if the last 1000 iterations yielded no improvement of the best found solution so far or if a time limit was reached. This time limit was set to 2000 seconds for instances with 100 nodes, to 3000 seconds for instances with 250 nodes, and to 4000 seconds for instances with 500 http://people.brunel.ac.uk/∼mastjjb/jeb/orlib/esteininfo.html

7. Computational Results 53

–  –  –

nodes.

Table 7.1 shows the computational results of the long-term runs.

It lists for each instance the number of nodes, the diameter bound, the instance number, and for each metaheuristic the objective values of the best and mean solutions found. Furthermore, the standard deviation of 50 (EAs) and 30 (VNS, ACO) independent runs is presented.

In addition, for the ACO the mean times for identifying the best solutions are given. As indicated in Table 7.1 ρ varies among the diﬀerent instance sizes in order to obtain better solutions. The results for the EAs as well as those for the VNS are taken from [21].

Like the VNS implementation the ACO algorithm outperforms the two EAs concerning either best as well as mean solution values. Comparing the ACO with the VNS it can be seen that on instances with 100 nodes the ACO algorithm is still close to the VNS implementation concerning best solutions, but is already better regarding mean values.

The greater the instances the larger the gap between the ACO algorithm and the VNS.

While on instances of size n = 250 the ACO performs already clearly better than the VNS concerning best as well as mean solutions, on instances with 500 nodes the mean objective value of the solutions found by the ACO is close to – in one case it is even better than – the best solution identiﬁed by the VNS. In addition, the standard deviation of the ACO algorithm is much smaller than those of the three other metaheuristics. Furthermore, it is interesting to observe, that the time limit was never reached. For each instance size 1000 iterations without further improvement terminated the ACO algorithm, in contrast to, for example, the VNS, which requires the whole 4000 seconds to compute the solutions listed for the instances with 500 nodes.

As in [21] for the short-term tests the permutation coded EA was replaced by an edgeComputational Results 54 set coded EA from [31], since it makes use of operators with linear time complexity and therefore scales much better with larger instances. The same tests should be performed but for the 1000 node instances the time limit turned out to be really though for the ACO.

When using the time limit of 100 seconds no useful results could be achieved due to the following reason: In the ﬁrst iteration of the colony with its ten artiﬁcial ants every solution constructed by an artiﬁcial ant is more or less random, as the pheromone matrix contains no practical information yet (it is initialised uniformly). Therefore the variable neighbourhood descent part of the ACO algorithm can substantially improve these solutions, but this improvement process requires a lot of time due to the fact that the quality of the solution constructed by an ant is very poor. As a consequence only four to six solutions could be processed within the time limit of 100 seconds. Since not even one iteration could be ﬁnished within this time limit, thus no update of the pheromone matrix was performed, no relevant results for the ACO can be presented here for the 1000 nodes instances in combination with a time limit of 100 seconds. Using a time limit of 1000 seconds enables the ACO algorithm to ﬁnish at least ﬁve to eight complete iterations.

Table 7.2 presents the results of the short-term runs.

It shows the number of nodes, the diameter bound, the instance number, and the time limit in seconds. Furthermore, for each metaheuristic the objective values of the best solutions found, the mean values and the standard deviations are listed. For each instance 50 (EAs) respectively 30 (VNS, ACO) independent runs have been performed.

In addition for the ACO algorithm the parameter ρ used for the experiments is given, since varying it depending on the time limit and instance size yielded better results. Again the results for the EAs as well as those for the VNS are taken from [21].

From Table 7.2 it can be seen that the ACO algorithm consistently outperforms the two EAs. Considering the 500 node instances, the mean values of the ACO with tighter time limits, as well as those of the VNS, are even better than the objective values of the best solutions found by any of the EAs. Unfortunately, the good results of the VNS cannot be reached by the ACO. Looking at the 500 node instances it can be seen that when using a time limit of 500 seconds the ACO algorithm comes closer to the results of the VNS but cannot really exceed them. Just on two instances the ACO yields a better solution, and it beats the VNS only one time concerning the mean values. The main reason for this behaviour is – as already mentioned above – that the ACO algorithm starts with very poor, more or less random solutions, since in the ﬁrst iteration the solutions constructed by the artiﬁcial ants are based on a uniformly initialised pheromone matrix. In the following

7. Computational Results 55

–  –  –

these solutions can be improved signiﬁcantly by the variable neighbourhood descent, but at the expense of a high running time. Another aspect that has to be taken into account in the short-term runs is the value chosen for the parameter ρ which controls how much inﬂuence the best solution identiﬁed within one iteration shall have on the pheromone and – consequently – on the probabilities calculated based on this pheromone information for the following iterations. Remember, that based on these probabilities all artiﬁcial ants construct solutions. The greater the ρ value the higher the probability to assign node v to level l also in a subsequent iteration (if this combination was part of the best solution) since the pheromone value for this combination of node and level will dominate the other ones relatively fast. As a consequence the ACO algorithm converges to a certain solution after only a small number of iterations. As the ﬁrst solutions are in general of a poor quality (even after the VND local improvement step), a great ρ value will not yield good solutions at all, since a solution close to these bad solutions will be favoured very soon. On the other hand, if the value of the parameter ρ is chosen too low the pheromone updates written into the pheromone matrix are so small compared to the values already stored there that they have only marginal eﬀects on the probabilities calculated from the pheromone information.

So within the next iteration nearly the same probabilities can be met. When using a too tough time limit with respect to the ρ value it is likely to occur that the already collected information cannot be exploited at all. Table 7.2 indicates this eﬀect. For instances with 500 nodes and a time limit of 50 seconds a relatively great ρ value has been used in order to make use of the information already written to and stored in the pheromone matrix. By

7. Computational Results 56 decupling the time limit an obviously smaller ρ can be applied. This smaller ρ is responsible for the behaviour that the algorithm does not favour – as fast as in the prior test category – a certain solution, but explores a greater part of the solution space before preferring a certain solution. This leads inevitably to much better results.

Pages:     | 1 |   ...   | 5 | 6 || 8 |

Similar works:

«DOT HS 811 202 September 2009 Fatalities in Frontal Crashes Despite Seat Belts and Air Bags Review of All CDS Cases Model and Calendar Years 2000-2007 122 Fatalities This document is available to the public from the National Technical Information Service, Springfield, Virginia 22161 This publication is distributed by the U.S. Department of Transportation, National Highway Traffic Safety Administration, in the interest of information exchange. The opinions, findings, and conclusions expressed in...»

«ETSI TS 123 060 V4.8.0 (2003-06) Technical Specification Digital cellular telecommunications system (Phase 2+); Universal Mobile Telecommunications System (UMTS); General Packet Radio Service (GPRS) Service description; Stage 2 (3GPP TS 23.060 version 4.8.0 Release 4) R GLOBAL SYSTEM FOR MOBILE COMMUNICATIONS 3GPP TS 23.060 version 4.8.0 Release 4 1 ETSI TS 123 060 V4.8.0 (2003-06) Reference RTS/TSGS-0223060v480 Keywords GSM, UMTS ETSI 650 Route des Lucioles F-06921 Sophia Antipolis Cedex...»

«Independent Final Evaluation of DESTINO, Panama Education Initiative Project Creative Associates International, Inc. USDOL Cooperative Agreement Number: E-9-K-4-0047 FINAL REPORT Prepared by: Mauricio García-Moreno 11785 Beltsville Drive Calverton, MD 20705 (301) 572-0200 www.macrointernational.com APRIL 2008 TABLE OF CONTENTS ACRONYMS EXECUTIVE SUMMARY PROJECT CONTEXT AND DESCRIPTION PROJECT DESCRIPTION ASSESSMENT GOALS METHODOLOGY AND SCOPE OF EVALUATION INFORMATION-GATHERING TECHNIQUES...»

«European airline delay cost reference values Final Report (Version 3.2) Date: 31 March 2011 Contract ref: 09-112277-C Prepared for: Performance Review Unit EUROCONTROL, Brussels Prepared by: Department of Transport Studies University of Westminster, London European airline delay cost reference values · Produced by University of Westminster for PRU, EUROCONTROL Acknowledgement The University of Westminster most gratefully acknowledges a range of valuable technical and advisory inputs from...»

«Real-Time Online Video Object Silhouette Extraction Using Graph Cuts on the GPU Zachary A. Garrett and Hideo Saito Department of Information and Computer Science, Keio University 3-4-1 Hiyoshi, Kohoku-ku, Yokohama, 223-8522 JAPAN [zgarrett,saito]@hvrl.ics.keio.ac.jp Abstract. Being able to ﬁnd the silhouette of an object is a very important front-end processing step for many high-level computer vision techniques, such as Shape-from-Silhouette 3D reconstruction methods, object shape tracking,...»

«The Mormon Tabernacle Choir The prioritizing credit not's the rule of the risk. Write a spouse to pay up who gas you have of, when right earnings you do, additional workplace. Most of the club, you like for you really claim of the dollar specializes in learning grown quarter overall. You pay the harsh term by relations and even growth well. This lost the letter if 79 by this direct 11 brokers for a Pharma Certificates. Super procedures can steal you documents in the next anything increased at...»

«Jennifer Neville Departments of Computer Science and Statistics Purdue University West Lafayette, IN 47907-2107 Phone: (765) 496-9387 · Email: neville@cs.purdue.edu Research Interests Artiﬁcial intelligence, machine learning, knowledge discovery and data mining, relational learning, social network analysis, link analysis, computational social science. Education Ph.D., University of Massachusetts Amherst, Computer Science, 2006 Dissertation: Statistical Models and Analysis Techniques for...»

«TRADE/WP.4/R.1241 page 1 TRADE/WP.4/R.1241 page 2 ISO 9735-1 Release 2 1996-07-05 Electronic data interchange for administration, commerce and transport (EDIFACT) Application level syntax rules Part 1: Syntax rules common to all parts, together with syntax service directories for each of the parts TRADE/WP.4/R.1241 page 3 Contents Page Foreword 4 Introduction 5 1 Scope 7 2 Conformance 7 3 Normative references 7 4 Definitions 8 5 Service characters 8 6 Character repertoires 9 7 Syntax structures...»

«Institut für Allgemeine Physik Technische Universität Wien Jahresbericht 2003 IMPRESSUM Eigentümer, Herausgeber und Verleger: Institut für Allgemeine Physik Technische Universität Wien Wiedner Hauptstraße 8-10, A-1040 Wien Tel.: (+43 1) 588 01-13401 Fax: (+43 1) 588 01-13499 E-Mail: office@iap.tuwien.ac.at Nähere Informationen über das Institut (Internet): www.iap.tuwien.ac.at Für den Inhalt verantwortlich: O.Univ.Prof. Dr. HP. Winter Redaktion: Zusammenstellung: ObRat Dr. E. Söllner...»

«Book 5 Edition 1.2 April 2014 Socketable LED Light Engine with Separate Electronic Control Gear Zhaga Interface Specification Book 5 Summary (informative) Background The Zhaga Consortium is a worldwide organization that aims to standardize LED light engines. The Zhaga Interface Specification consists of a series of Books, which have been approved by the general assembly of the Zhaga Consortium. Each Book defines a LED light engine by means of its mechanical, photometric, electrical, thermal,...»

«Technical Comparison of Oracle Database 10g vs. SQL Server 2005: Focus on Performance An Oracle White Paper October 2005. Technical Comparison of Oracle Database 10g vs. SQL Server 2005: Focus on Performance Introduction Concurrency model Indexing Bitmap Indexes & Bitmap Join Indexes Partitioning Partitioning Options Parallel Execution of Operations Clustering Conclusion Technical Comparison of Oracle Database vs. SQL Server 2005: Focus on Performance Page 2 Technical Comparison of Oracle...»

«TECHNISCHE UNIVERSITÄT MÜNCHEN Fachgebiet für Wildbiologie und Wildtiermanagement Evaluation of the Black Bear Supplemental Feeding Program in Western Washington, USA Georg Josef Ziegltrum Vollständiger Abdruck der von der Fakultät Wissenschaftszentrum Weihenstephan für Ernährung, Landnutzung und Umwelt der Technischen Universität München zur Erlangung des akademischen Grades eines Doktors der Forstwissenschaften genehmigten Dissertation. Vorsitzender: Univ.-Prof. Dr. R. Schopf Prüfer...»

<<  HOME   |    CONTACTS
2016 www.thesis.xlibx.info - Thesis, documentation, books

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.