FREE ELECTRONIC LIBRARY - Thesis, documentation, books

Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |

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

-- [ Page 6 ] --

The ACO for the BDMST problem, proposed within the context of this master thesis, is based on the ant colony system (ACS), first proposed by Dorigo et al. in 1996 [12, 11]. A property taken from the ACS for the travelling salesman problem (TSP) is the pheromone initialisation process. Another adapted characteristic is that every artificial ant is only responsible for constructing a solution, since the pheromone update process is managed by a daemon. This daemon identifies, as it is representative for ACS algorithms, the best solution found by the whole colony in one iteration and updates the pheromone information proportional to the fitness of this best solution found. Pheromone trail evaporation is also performed by the daemon. A main difference between the ACS concept and the ant colony optimisation metaheuristic presented here lies in the local decision policy. In general the decision policy of ACS algorithms includes a heuristic component when computing a state transition. This heuristic component for the local decision policy is completely omitted for this ACO algorithm.

For the implementation of the ACO algorithm some data structures are required, most of

them already known from the four different neighbourhoods:

• Again the successor lists succ, storing for each node its immediate successors, the predecessor array pred, saving for each node its predecessor in the directed tree from the centre to the leaves, the level information lev, stating the level a node is assigned to and the level sets Vl with l = 0,..., D/2, containing all nodes at the level l, are used.

• In addition, a two dimensional n × ( D/2 + 1) pheromone matrix is needed to keep one pheromone entry for each combination of a node and a level. The value τi,j reflects the desirability of assigning node i to level j.

–  –  –

regarding pheromone deposition in comparison to the basic ACO concept for the TSP proposed by Dorigo [10, 13]. There they operate on a graph G = (V, E) where pheromone is deposited – either by ants themselves or by a daemon – on edges e ∈ E contained in the solution. The ACO algorithm presented here does not deposit pheromone on edges but exploits the fact that once given the level information lev(v) for all nodes v ∈ V an optimal solution for the bounded diameter spanning tree problem with respect to this level information lev can be easily derived. Therefore simply for each non centre node v the least cost predecessor p with lev(p) lev(v) has to be found. In case of several possible least cost predecessors, always one with minimum level is selected. Thus ants construct a solution not by “running” through the graph structure, but by assigning nodes to levels, building the level information lev. So the pheromone information reflects instead of the desirability of using an edge the desirability of assigning a node to a certain level. Algorithm 9 gives an overview of the ant colony optimisation algorithm developed in the context of this master thesis.

To be able to construct a solution based on the information stored in the pheromone matrix, it has to be first initialised. This initial amount of pheromone for each combination of node and level has to be in relation to those values the pheromone update process is going to write into the matrix. E.g., if the initial values are too big compared to those, the pheromone update process is going to deposit, it will last very long until the ant colony will be capable of exploiting the information stored in the pheromone matrix. To guarantee that ants are able to use the collected information very soon the pheromone initialisation process follows the scheme of ACS algorithm for the TSP [12, 11], where the initial amount of pheromone deposited is proportional to the product of an initial solution value and the total number of nodes of the instance graph. Therefore in the first line of Algorithm 9 a solution S using the randomised tree construction (RTC) heuristic [31] is computed. The solution value obtained from the RTC heuristic, together with the total number of nodes n is used to initialise the pheromone matrix with τi,j = 1/(S ∗ n), i = 0,..., n − 1 and j = 0,..., D/2.

Until no termination condition is met (line 3), which can be either a time limit, a maximum number of iterations without further improvement or both combined, in each iteration an colony of a finite number of artificial ants tries to find good solutions based on the so far collected information on the problem instance.

Each artificial ant builds a solution based on the information stored in the pheromone matrix. As already mentioned, the solution construction process exploits the fact that a given level information lev for each node is enough to construct the local optimal tree.

5. Ant Colony Optimisation for the BDMST Problem 43 Algorithm 9: ACO for the BDMST create an initial solution S using the RTC heuristic;

initialise the pheromone matrix with 1/(S ∗ n);

while termination condition not met do for each ant of the colony do create a solution T, based on the information saved in the pheromone matrix;

VND(T );

–  –  –

So each ant simply sets each node to a certain level. The level a node is assigned to is selected randomly with a probability proportional to the pheromone information stored for this node, i.e. Pi,l is the probability that node i is assigned to level l.

–  –  –

In general – due to the stochastic level selection process – each node can be assigned to any level as long as no entry in the pheromone matrix is zero. This is a desirable behaviour except for level 0, where the number of nodes is fixed in advance based on the diameter bound. Therefore the centre node(s) is (are) selected separately based on the information stored in the first column of the pheromone matrix (the pheromone values of level 0 for each node). As said above this local decision policy has no heuristic component, every node is assigned to a certain level independently from all other nodes, only the decoding step – deriving a tree from the level information – makes use of a problem specific heuristic when using for each non centre node its cheapest available predecessor.

To improve solutions built by artificial ants the variable neighbourhood descend for the BDMST, presented in the previous section, is applied to these solutions. Thus each ant constructs a solution based on the information stored in the pheromone matrix. Afterwards the VND algorithm tries to improve this solution (lines 5 to 6).

The daemon is responsible for collecting all solutions found by the ant colony in the current iteration (line 7). From this pool of solutions it selects the best one T and determines the amount of pheromone, that is proportional to the fitness of this best solution, going to be written into the pheromone matrix for the appropriate node/level combinations.

5. Ant Colony Optimisation for the BDMST Problem 44

–  –  –

After having calculated the amount of pheromone to be deposited, the pheromone matrix is updated (line 8). This update process combines the pheromone laying and the pheromone

evaporation process and follows the scheme introduced for ACS algorithms:

–  –  –

The parameter ρ, with 0 ≤ ρ ≤ 1 has a crucial impact on the convergence of the ant colony.

The greater ρ the faster the ant colony commits itself to a certain solution, it converges faster, perhaps too fast. On the contrary, the smaller ρ the later the ant colony is able to exploit already collected knowledge of the problem instance, in terms of the pheromone matrix, to construct good solutions, but therefore the solution space is explored in more detail. So using this parameter the behaviour of this ant colony optimisation algorithm can be influenced substantially and adjusted for different applications.

In line 9 and 10 the daemon verifies if the best solution found by the ant colony in the current iteration is better than the best solution found so far. If so this solution is saved as new best solution.

6. IMPLEMENTATION The ant colony optimisation metaheuristic, introduced in this master thesis, is implemented in C++, following the C++ coding standard, e.g. representing each class through a header file, stating the attribute and method declarations, and an implementation file, stating the program code. The only non-standard class library used is LEDA (Library of Efficient Data Types and Algorithms) in terms of version 5.0.1. The aim of the LEDA project, launched in 1988, was to build a small, but extendable library of data structures and algorithms for combinatorial computing in a form making them easy to use. Since February 1st, 2001, Algorithmic Solutions Software GmbH is responsible for maintaining and developing LEDA1.

Figure 6.1 shows the UML class diagram of the major classes, their relationships as well as the most important attributes and methods of the respective classes.

The Instance class encapsulates all relevant information concerning a BDMST problem instance that does not change during computations, e.g. the underlying graph or the diameter bound. Due to this fact, each run of the ant colony optimisation algorithm has exactly one Instance object.

The InstanceParser is responsible for parsing the input file and storing the relevant information in the corresponding data structures. The InstanceParser is able to parse various file formats, e.g. GNUplot or EA graph instances. GNUplot files were created at the Institute of Computer Graphics and Algorithms for testing and visualising purposes.

EA files are instances from the Beasley’s OR-Library2 which haven been originally intended for Euclidean Steiner tree problems. As in [31, 25, 21] these instances have been used for comparing this ACO with other state-of-the-art metaheuristics.

–  –  –

are used. The predecessor attribute stores for each node its direct predecessor and centreNode keeps the centre node. In case of an odd diameter centreNode2 saves the second one. To express the correlation between a Solution object and the instance it belongs to, a pointer to the Instance object is passed to in the constructor of the Solution class. This pointer enables the Solution object to access instance specific information, like number of nodes, diameter bound or connection costs between two nodes. Important methods of the Solution class are ValidateSolution() and CalcSolValue(). The ValidateSolution() method verifies if the solution represented by this Solution object contains all nodes of the problem instance, if the diameter bound is not violated and if the solution is free of circles. If it turns out that the Solution object represents a valid BDMST true is returned, otherwise false. The CalcSolValue() method calculates the total costs of the solution represented by the object and returns this objective value.

–  –  –

LocalSearch class a reference to a Solution object is passed to. This enables different LocalSearch objects, in case they are referencing the same object, to operate on the same Solution object in a sequential order. Additional instance specific information can be accessed via this reference to the Solution object and its pointer to the Instance object.

The Execute() method, each subclass of LocalSearch has to implement, starts the improvement process, stopping in a local optimal solution with respect to the neighbourhood structure implemented by this subclass. In case the objective value of the solution passed to the constructor of the LocalSearch class has been improved, Execute() returns true, otherwise false.

EdgeExchange is a subclass of the


LocalSearch class and implements the Edge Exchange neighbourhood. All improvement moves found by the Execute() method are executed directly on the Solution object passed to it in the constructor. This holds true for all other subclasses of the abstract LocalSearch class, too.

Node Swap, another subclass of LocalSearch, implements the second neighbourhood structure based on the successor and predecessor relationships of the nodes, beside Edge Exchange, namely – as the name already presumes – Node Swap.

The LevelBased class is abstract and summarises attributes and methods used by its two subclasses, CentreExchange and LevelChange, implementing neighbourhoods based on the level representation of a solution. An example for such an additional attribute is nodesAtLevel which stores for each level all nodes assigned to it.

As already mentioned CentreExchange and LevelChange are subclasses of LevelBased.

The Execute() method of CentreExchange computes a local optimal solution with respect to the Centre Exchange neighbourhood, whereas LevelChange implements the Level Change neighbourhood.

The Aco class is the core of this ant colony optimisation program. It is responsible for creating all the required objects, as there are for example the sole object of the Instance class, objects of Solution and subclasses of the abstract LocalSearch class. Furthermore, it administrates – strictly speaking initialises and updates – the pheromone matrix. Based on the information stored in this pheromone matrix each artificial ant builds a solution by calling the CreateSolution() method. These solutions are then tried to be locally improved by a variable neighbourhood descent algorithm using the four different neighbourhood structures implemented as subclasses of LocalSearch.

6. Implementation 48

6.1 User Manual

The proposed ant colony optimisation metaheuristic, implemented in C++, is a simple command line program, named Aco. The program was developed under Linux 2.4.21.

The program was compiled using gcc in version 3.3.1 under glibc in version 2.3.2. To start the program some mandatory parameters have to be specified. If they are missing the program will prompt an error message followed by a usage instruction. Furthermore, Aco has some optional parameters, that can be omitted when starting the ant colony optimisation program. In the following a synopsis of the program parameters is shown.

Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |

Similar works:

«For more information, please visit the Privacy Technical Assistance Center: http://ptac.ed.gov Best Practices for Data Destruction About PTAC The U.S. Department of Education established the Privacy Technical Assistance Center (PTAC) as a “one-stop” resource for education stakeholders to learn about data privacy, confidentiality, and security practices related to student-level longitudinal data systems and other uses of student data. PTAC provides timely information and updated guidance on...»

«Forestry Commission (Scotland) External Use Guidance Note 19 April 2001 Derelict and Reclaimed Land 1. Introduction Derelict and reclaimed land can be particularly hostile for tree growth and often present important challenges to successful woodland establishment. However there is now considerable information and experience as to the practical techniques necessary to establish successful woodland on such sites. The purpose of this instruction is to highlight the main factors that Conservancies...»

«Landing Techniques Flight Operations Briefing Notes Preventing Tailstrikes at Landing Flight Operations Briefing Notes Landing Techniques Preventing Tailstrike at Landing I Introduction A tailstrike occurs when the tail of an aircraft touches the runway during takeoff or landing. It can occur with any type of aircraft, although tailstrikes occur more often with long aircraft, because tailstrike occurrence is directly related to pitch attitude versus aircraft geometry, and the status of main...»

«FAQs Dental Plan Am I eligible to enroll in the Delta Dental of New Jersey Yale Graduate & Professional Student dental plan? A: You must be a Yale University Graduate or Professional student enrolled at least half-time in a Yale degree program. What is the enrollment deadline? A: September 15, 2015 How do I enroll? A: Enrollment can be completed online at www.yale.edu/gradprofdenteye/ Important note: Before you begin the enrollment process, be sure that you have all the information necessary to...»

«International Journal of Enhanced Research in Science Technology & Engineering, Vol. 2 Issue 10, October-2013, pp: (54-59), Available online at: www.erpublications.com Low power high speed bypassing based multipliers with modified adders for dsp applications Teffi Francis1, Jobin K. Antony2 Dept of Electronics and Communication Rajagiri School of Engineering And Technology Kochi, India Abstract: Braun multiplier is one of the parallel array multipliers, which is used for unsigned numbers...»

«23 January 2014 Multi-factor Productivity, Indicative Estimates to 2012 Author Name(s): Simon Field and Mark Franklin, ONS Abstract This article presents indicative estimates of multi–factor productivity (MFP) to 2012 using estimates of quality adjusted labour inputs and capital services. Using a growth accounting framework, output growth can be decomposed into contributions due to changes in labour and capital inputs, and a residual component variously described in the literature as...»

«Technische Universität München Lehrstuhl für Entwicklungsgenetik Functional role of Bcl10 and Malt1 in signal transduction from the FcεRI in mast cells and the LPA receptor in murine embryonic fibroblasts Stefanie Klemm 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 Naturwissenschaften genehmigten Dissertation. Vorsitzender:...»

«Institute for Software Research University of California, Irvine A Rationalization of Confusion, Challenges, and Techniques in Model-Based Software Development Yongjie Zheng University of California, Irvine zhengy@ics.uci.edu Richard N. Taylor University of California, Irvine taylor@ics.uci.edu August 2011 ISR Technical Report # UCI-ISR-11-5 Institute for Software Research ICS2 221 University of California, Irvine Irvine, CA 92697-3455 www.isr.uci.edu www.isr.uci.edu/tech-reports.html A...»

«Math Geosci (2012) 44:449–468 DOI 10.1007/s11004-012-9402-9 SPECIAL ISSUE Multivariate Block-Support Simulation of the Yandi Iron Ore Deposit, Western Australia Alexandre Boucher · Roussos Dimitrakopoulos Received: 13 April 2012 / Accepted: 17 April 2012 / Published online: 5 May 2012 © International Association for Mathematical Geosciences 2012 Abstract Mineral deposits frequently contain several elements of interest that are spatially correlated and require the use of joint geostatistical...»

«Master thesis Final draft Quantifying vegetation cover changes from NDVI time series and determination of main causes for the Nile Basin Suzan van der Kruijs Graduation committee: Water Resource Management Prof. dr. W.G.M. Bastiaanssen Faculty of Civil Engineering Prof. dr. S.B. Kroonenberg Delft University of Technology Ir. M.M. Rutten January 2009 Preface This study was done in the scope of the Master study of Water Resource Management at the Faculty of Civil Engineering at the University of...»

«Clemens Felsmann, Juliane Schmidt, Tomasz Mróz Effects of Consumption-Based Billing Depending on the Energy Qualities of Buildings in the EU Potential assessment for member states Dresden, Poznan, 18 December 2015 Technische Universität Dresden Faculty of Mechanical Science and Engineering Institute of Power Engineering Chair of Building Energy Systems and Heat Supply Prof. C. Felsmann Juliane Schmidt Tel.: +49 (0) 351 463 32145 Tel.: +49 (0) 351 463 34557 Fax.: +49 (0) 351 463 37076 Fax: +49...»

«THE MORPHOLOGICAL ANALYSIS AS A SUPPORT FOR URBAN PLANNING. THE CASE STUDY OF THE GATE OF CASCAIS EXTENDED ABSTRACT André Filipe Pereira Saraiva1 KEYWORDS: Urban morphology; Urban fabric; Plan units; Cascais; Kropf;ABSTRACT The morphological analysis of the city has as its main objective the understanding of urban reality through the study of the relationships shown between the all urban elements. This analysis also sees the city as a product of an evolutionary and dynamic process, which...»

<<  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.