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

<< HOME
CONTACTS

Pages:     | 1 |   ...   | 2 | 3 || 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 4 ] --

The Node Swap neighbourhood of a feasible solution T is deﬁned as follows: Neighbours are all feasible solutions T where a node v and one of its immediate successors u ∈ succ(v) have changed their position within the tree. In other words, node v that was predecessor of node u before the move is now an immediate successor of node u. Furthermore, node u inherits all successors of node v and the successor list of node v, succ(v), is cleared.

Reconnecting all immediate successors of v to u ensures that the diameter bound is not violated. Figure 4.2 illustrates this issue.

–  –  –

For this neighbourhood it is possible to implement an incremental exploration after having

identiﬁed the most proﬁtable move. Therefore we introduce additional data structures:

–  –  –

and ﬁnally a list l of all nodes that have to be checked once again when the move is performed, since only their situation alters if node u and v change their position.

Members of this list l are pred(v), u, and all nodes n ∈ succ(v)\{u}.

• A priority queue Q containing all proﬁtable moves, including the information saved for each move. The priority queue Q has always the most lucrative move on top.

After having explored the whole neighbourhood and identiﬁed the most proﬁtable move, this priority queue plays the key role for computing the successive best move within the neighbourhood.

Using again a best improvement strategy the full exploration of the Node Swap neighbourhood of a solution T can be described as in Algorithm 5. Already the ﬁrst line points out a major diﬀerence to the Edge Exchange neighbourhood. The Node Swap neighbourhood does not exclude the centre nodes, enabling neighbouring solutions T having a diﬀerent centre. After having selected a node v the algorithm computes in lines 3 to 8 the current costs cv of the connections from v to its immediate successors, succ(v), and, if v ∈ V0, / also the current costs from v to its predecessor. Then each node u ∈ succ(v) is tried to be swapped with node u. Lines 10 to 15 calculate the costs cu of this potential new arrangement. This time the connections from u to each node in succ(v) \ u are essential plus the connection from u to v. And again, if v ∈ V0, also the costs from u to v’s current / predecessor. In case the diameter is odd the costs from u to the second centre node have to be taken into account. In line 16 the costs saved by a node swap of v and u are computed.

If this leads to an improvement greater than the best found so far then node u is marked as best node for a swap with node v. After having tested every node u ∈ succ(v) line 20 checks if a proﬁtable move has been identiﬁed. If so the move and the corresponding data is put into the priority queue Q.

The total size of the Node Swap neighbourhood is O(n). The evaluation of a single neighbouring solution depends on the degree of the node under consideration. Therefore the time required to completely enumerate the whole neighbourhood is O(n · dmax ), where dmax denotes the maximum degree of any node in the current solution.

For reaching a local optimal solution with respect to the Node Swap neighbourhood an incremental enumeration can be applied after having explored the whole neighbourhood once. Since the worst case scenario has to be taken into account the incremental enumeration still requires time in O(n · dmax ), nevertheless, it speeds up computation in practice signiﬁcantly.

4. Neighbourhood Structures 26

–  –  –

After executing the most lucrative move, only certain nodes have to be checked in order to have once again all possible improvement moves stored in the priority queue Q. The nodes aﬀected when executing an improvement move are part of the data stored for it in Q, they can be found in list l. So for an incremental enumeration of the Node Swap neighbourhood only a slight modiﬁcation of Algorithm 5 is required: Instead of executing it for all nodes, as stated in the ﬁrst line, it is only executed for those aﬀected when performing the best move received from Q.

The complete algorithm to reach a local optimal solution is now as follows: First the whole neighbourhood is explored as described in Algorithm 5 to identify the ﬁrst best move.

Afterwards, the priority queue Q contains all proﬁtable moves, having the best one on top.

Then, as long as the priority queue Q is not empty, the ﬁrst element, containing the best improvement move, is received from Q. In the following it has to be checked if this move is still valid. Therefore the current local situation is compared to the situation when the

4. Neighbourhood Structures 27 move was evaluated. This means that it is veriﬁed, if node v, that will be replaced by one of its successors u, still has the same predecessor and the same successors. Only in this case the move is considered to be still valid and will be executed. Otherwise it is ignored and the next move is fetched from the priority queue Q. Therefore the set of immediate successors of node v, succ(v), and its predecessor, pred(v), are saved along with the move.

Assuming a move turns out to be valid it is executed immediately: The successor list of pred(v) has to be updated, by deleting node v and adding node u. Furthermore, each node that was a direct successor of node v before performing the move has to be deleted from the successor list of node v and added, excluding node u, to the successor list of node u. In addition the predecessors of all rearranged nodes have to be set accordingly: Node v gets node u as its new predecessor, u gets the old predecessor of node v, pred(v), and all old successors of node v, succ(v), get node u as their new predecessor. The last step before fetching the next move from the priority queue Q is the update of all aﬀected nodes as described above. A local optimal solution is reached when the priority queue Q is empty.

At this place it has to be mentioned that Gruber and Raidl demonstrated in [21] that the exploration of this Node Swap neighbourhood can be implemented more eﬃciently by directly manipulating the moves stored in the priority queue when updates are required.

As a consequence Q always contains only valid moves and so there is no need for the corresponding validity test and list l.

4.2 Level Based Neighbourhoods

The Centre Exchange and Level Change neighbourhood structures are not based on the predecessor and successor relationships of the nodes but on the levels (0 ≤ lev(v) ≤ D/2, v ∈

V ) the nodes are assigned to. There are always exactly 1 + D mod 2 nodes with a level of 0,

building the centre. From the level information a local optimal tree can easily be derived:

Each node v ∈ V \ V0 is connected to the least cost predecessor p with lev(p) lev(v). If there are multiple potential predecessors for a node v with the same minimum edge costs, v always connects to one with minimum level.

–  –  –

Again, for a full and especially eﬃcient exploration of the whole neighbourhood some

• For each move the old and the new centre nodes are stored. Furthermore, a list l of new successor ↔ predecessor relations ((u, v): node u will get node v as new predecessor).

Algorithm 6 describes the complete enumeration of the Centre Exchange neighbourhood.

As the name suggests this neighbourhood focuses on ﬁnding a new centre. This is quite an important fact, since beside Centre Exchange there is only the Node Swap neighbourhood that is able to change the centre, but not on this scale. In line 3 the centre node c is assigned to level D/2. Afterwards, a new predecessor has to be found for c. Candidates are all nodes v with 0 ≤ lev(v) D/2. Note that a potential predecessor for the moved centre node c at level 0 exists only in case of an odd diameter. In addition, for all successors u ∈ succ(c) with lev(u) 1 new predecessors have to be found (lines 5, 6). Everything happened so far is only computed once. In lines 8 to 19 each node, excluding those forming the (old) centre, is tried as new centre node. For each node u ∈ V1 it has to be checked in case of an odd diameter if it is cheaper to connect u to the new centre node v or the remaining second centre node. The even diameter case is much simpler since all nodes u ∈ V1 have to be appended to v, because v is their only available predecessor. This happens in lines 11 to 14. For all nodes at the levels 2 to the old level of v it has to be checked if now v is a cheaper predecessor than their current one. In line 16 the attempt installing node v as new centre node is evaluated. If it turns out that moving node v to the centre is the most proﬁtable move found so far it is saved as new best move (lines 17-19).

–  –  –

a complete exploration of the neighbourhood of a given solution T, including identifying the most lucrative move, can only be done in O(n2 ).

An incremental enumeration of the neighbourhood is not presented here, since an implementation is not straightforward and we assume that the solution this neighbourhood structure is applied to is already of some good quality. Therefore it is unlikely to have a longer chain of consecutive improvement moves. A local optimal solution can be reached by calling Algorithm 6 as long as it yields an improvement move. After having identiﬁed the most proﬁtable move of the whole neighbourhood it is executed by deleting the old centre node c from the set V0 and the new centre node v from the set Vlev(v). Then they are appended to their new level sets, c to V and v to V0. Furthermore, the level array lev is D/2

–  –  –

The Level Change neighbourhood is the second one for which an incremental enumeration, after having explored the whole neighbourhood once, is presented. As for the incremental enumeration of the Node Swap neighbourhood again additional data structures are required.

• For every proﬁtable move the following information has to be stored: First the direction of the move, indicating if it is an increment or decrement one. Furthermore, the costs ∆c saved by it, and ﬁnally a list l representing new successor ↔ predecessor relations.

• A priority queue Q always having the most proﬁtable move on top.

• An array dec, saving for each node a pointer to its decrement move within Q, and one array inc, storing a pointer to its increment move. These two arrays are necessary to have immediate access to all moves saved in the priority queue Q.

Algorithm 7 describes the exploration of the whole Level Change neighbourhood. As stated in line one this algorithm is executed for all nodes, excluding those forming the centre. The algorithm is split into two parts. In the ﬁrst one (lines 2 to 11) the algorithm decrements the level of node v and saves this move if proﬁtable. A decrement move is only possible if lev(v) 1, since this neighbourhood does not eﬀect the centre, but decrementing a node u with l(u) = 1 would put this node u into the centre. After decrementing the level of v for each node u at the old level of v it has to be checked if it is now cheaper to reconnect u to become successor of v (lines 4 to 6). If the level of v’s predecessor is less than the new level

4. Neighbourhood Structures 31

–  –  –

of v, v’s predecessor is kept. Otherwise, a new predecessor has to be found (lines 7, 8) in the appropriate levels. In line 9 the costs of this move are evaluated. If it turns out that decrementing v will improve the solution this move is put into the priority queue Q. Even if the move does not change the objective value instantly (∆c = 0) it is put into the priority queue since a node at a lower level can act as potential predecessor for a larger number of other nodes, this could be valuable for subsequent iterations. Such a move, where the level of a node is decremented but the tree derived from the level information does not change, is called a null move in the following.

–  –  –

v can be connected as successor in a cheaper way (lines 15, 16). If no such predecessor can be found an improvement is impossible. Assuming a cheaper predecessor was found, in lines 18 to 20 the algorithm assigns to all old successors u of v (u ∈ succ(v), with lev(u) = levnew (v)) a new predecessor with an appropriate level, since u and v are now on the same level and so cannot be connected any longer. In line 21 the increment move of v is evaluated and if it gains an improvement it is put into the priority queue Q.

As the Level Change neighbourhood is of size O(n) and in the worst-case scenario for each decrement or increment move a node has to be compared with nearly every other node, a complete enumeration of it requires time in O(n2 ).

A local optimal solution has been reached when the priority queue Q is empty. In the following section an incremental enumeration of the Level Change neighbourhood is presented that can be applied after having explored a whole neighbourhood once. In this section it will also be described how to eﬃciently update information stored in Q when executing a move which has local impact on other nodes and their ability to improve the solution with a level increment or decrement. The incremental enumeration cannot reduce the worst-time complexity of O(n2 ), but still speeds up the computation time essential in practice.

Incremental enumeration of the neighbourhood of solution T

Assuming the whole neighbourhood has been explored applying Algorithm 7 and all improvement moves are saved in the priority queue Q, now the best move is fetched and performed. Therefore the node to be moved is deleted from its old and added to its new level: According to the direction of the move it is assigned either to the higher level, in case of an increment move, or to the lower level in case of a decrement move. Furthermore, the predecessor array and successor lists are updated based on the list l included in the data stored for a move in Q.

In order to have again all possible improvement moves in a valid state in the priority queue Q, the following rechecks and updates have to be done after executing a move. We have to distinguish between a decrement and increment move.

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

Similar works:

«VISUAL DIGITAL CULTURE Surface play and spectacle in new media genres Andrew Darley London and New York CONTENTS List of illustrations ix Acknowledgements x Introduction 1 PART I History 9 1 A back story: realism, simulation, interaction 11 Beginnings 11 Digital cinema 16 Computer games 23 Special venue attractions 31 2 Genealogy and tradition: mechanised spectacle as popular entertainment 37 Popular entertainments and the cinema 37 Spectacle displaced 48 Extending a tradition: fin-de-siècle...»

«PRINCIPLES FOR THE SUPERVISION OF OPERATORS OF COLLECTIVE INVESTMENT SCHEMES Technical Committee of the International Organization of Securities Commissions September 1997 I. INTRODUCTION The collective investment scheme is well established in many jurisdictions and now serves as an investment vehicle for a wide range of investment opportunities around the world. Many millions of people world-wide have invested in collective investment schemes (CIS)1 and rely upon operators of the schemes to...»

«TECHNISCHE UNIVERSITÄT MÜNCHEN Lehrstuhl für Zoologie Molekulare Genetik im Artenschutz von Großraubtieren – Eine Fallstudie am Wolf Roland M. Hausknecht 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: Univ.-Prof. Dr. H. Luksch Prüfer der Dissertation: 1. Priv.-Doz....»

«Technical Report Documentation Page 1. Report No. 2. Government 3. Recipient’s Catalog No. Accession No. FHWA/TX-05/5-4035-01-1 4. Title and Subtitle 5. Report Date Design Standards, Special Specifications, and Monitoring Plan September 2005 for PCP in Texas 6. Performing Organization Code 7. Author(s) 8. Performing Organization Report No. Cesar Ivan Medina-Chavez, Moon Won 5-4035-01-1 9. Performing Organization Name and Address 10. Work Unit No. (TRAIS) 11. Contract or Grant No. Center for...»

«This file was created by scanning the printed publication. Text errors identified by the software have been corrected; however, some errors may remain. SIMYAR: A United States Department of Agriculture Cable-Yarding Forest Service Pacific Northwest Research Station Simulation Model General Technical Report PNW-GTR-205 Robert J. McGaughey and Roger H. Twito ROBERT J. McGAUGHEY and ROGER H. TWITO are research forester and Authors research civil engineer, Forestry Sciences Laboratory, 4043...»

«Information Paper 7 August 2015 Issued: July 2011 Amended and reissued: March 2013, August 2015 Non-destructive Testing methods Technical Issues © Copyright National Association of Testing Authorities, Australia 2013 This publication is protected by copyright under the Commonwealth of Australia Copyright Act 1968. NATA’s accredited facilities or facilities seeking accreditation may use or copy this publication or print or email this publication internally for accreditation purposes....»

«Fakultät Umweltwissenschaften Faculty of Environmental Sciences Investigation of selected wood properties and the suitability for industrial utilization of Acacia seyal var. seyal Del and Balanites aegyptiaca (L.) Delile grown in different climatic zones of Sudan Dissertation to achieve the academic title Doctor rerum silvaticarum (Dr. rer. silv.) Submitted by MSc. Hanadi Mohamed Shawgi Gamal born 23.09.1979 in Khartoum/Sudan Referees: Prof. Dr. Dr. habil. Claus-Thomas Bues, Dresden University...»

«The ILO: An Agency for Globalization? Guy Standing ABSTRACT The International Labour Organization, set up in 1919 to develop and promote labour standards, is at a crucial point. It has preached that labour is not a commodity and in 1969 received the Nobel Peace Prize. Since then it has run into trouble. This article considers how the ILO has failed to come to terms with the Global Transformation, seeing it as trying to play three roles — a standard-setter, a technical assistance agency and a...»

«Dave Wolstencroft Technical Manager 4B Components HOW STEEL WEB ELEVATOR BELT & SJ BUCKETS ENHANCE THE PERFORMANCE OF BUCKET ELEVATORS Introduction With the demand for larger capacities, for more efficient and cost effective elevators to carry industrial products such as cement, 4B Components has researched, tested and supplied the industry for over the last nine years with an integrated system of steel web belting, SJ buckets and elevator designs for compact industrial elevators. 4B Components...»

«Evaluating a Quality Model for Software Product Assessments – A Case Study Michael Kläs1, Klaus Lochmann2, Lars Heinemann2 Fraunhofer IESE Technische Universität München, 67663 Kaiserslautern 85748 Garching, Germany michael.klaes@iese.fraunhofer.de {lochmann, heineman}@in.tum.de Abstract. Background: Software quality models have been proposed as a means for describing the concept of quality. Most quality models take an Abstract view on quality characteristics. Therefore, they are not able...»

«Comparing Mathematics Content in the National U.S. Department of Education Assessment of Institute of Education Sciences NCES 2006–029 Educational Progress (NAEP), Trends in International Mathematics and Science Study (TIMSS), and Program for International Student Assessment (PISA) 2003 Assessments Technical Report May 2006 Teresa Smith Neidorf NAEP Education Statistics Services Institute American Institutes for Research Marilyn Binkley National Center for Education Statistics Kim Gattis NAEP...»

«Brains, Bones & Hotsprings: Native American Deerskin Dressing at the Time of Contact What can we learn? What myths can we let go of? by Matt Richards photos and illus. Adapted and updated for the web from an article printed in The Bulletin of Primitive Technology, Fall 1996 Inuit tanner takes a break INTRO My original purpose with researching 100 first hand accounts of Native American tanning was to find easier, more direct techniques to accomplish that goal: velvet soft buckskin. I knew (or at...»

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