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



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

Case 1: The performed move decremented the level of node v from l + 1 to l.

• If there is an increment move for node v in the priority queue, delete it (it would be no longer valid).

–  –  –

1. Decrement the level of node v.

Node v continues moving one level down, as this move was not possible before.

2. Increment the level of the new predecessor of v, prednew (v), if its level is l − 1 and if this move is already in the priority queue Q. To verify if this move is already in the priority queue Q the inc array is used.

The case that prednew (v) loses v as successor is new. So a new predecessor for v has to be found, this information must be added to the successor ↔ predecessor list and the costs saved by this improvement ∆c have to be updated accordingly.

If the improvement ∆c becomes negative or equal to zero after the update, the corresponding increment move can be removed from the priority queue Q (this holds true for every following increment move, too).

3. Decrement the level of each old successor u of v with lev(u) = l + 2. Note that these nodes will remain successors of v.

This move might not change the represented tree and therefore the objective value, but as already mentioned it should be considered as an improvement move since it may allow further nodes to decrement their level leading to other improvement moves.

–  –  –

Otherwise this move has to be evaluated from scratch with the exception that there is no need to search for a predecessor for u, since it can keep v for sure.

4. Decrement the level of each node u at level l+2 having its predecessor pred(u) = v at level l + 1.

Node u will lose its current predecessor and now v might become its new one.

If such a move can be found in the priority queue Q only the predecessor of u stored in this move has to be checked against v. In case v would be the better choice, the predecessor of u and ∆c have to be updated accordingly.

Otherwise, the decrement move of u has to be evaluated completely new including the search for a new predecessor.

5. Decrement the level of each node u being a new successor of v (note that all these new successors are on level l + 1) if such a decrement move is already in the priority queue Q.

Before moving v to level l node u had another predecessor, assume w. So the calculated ∆c of this move was based on the connection between u and w. Now u has v as its predecessor (c(u, v) has to be less than c(u, w)). In addition, the move can contain the information that u would have become the new predecessor of v at its old level l + 1, but after moving v to level l this is no longer possible.

Furthermore, the move can include new successors of u now connected to v; they have to be checked if still u would be the better predecessor for them.

So there are three possible impacts to ∆c and the successor ↔ predecessor list of the move that have to be updated accordingly.

6. Decrement the level of each node u at level l + 1 not being a new successor of v if there is already a corresponding move in the priority queue Q.

The situation is more or less the same as above with the restriction that the predecessor of u does not change when moving v to level l.

So there are only two possible impacts to ∆c and the successor ↔ predecessor list. In this case the objective value gain can only decrease, making this move worse.

7. Increment the level of each node u being a new successor of v if such a move is already in the priority queue Q.

–  –  –

There are two cases:

(a) In the move stored in Q, v would have become the new predecessor of u.

After moving v to level l this is already the case so the move can be deleted without any further investigations.

(b) Otherwise u is now connected cheaper than it was before when the move was evaluated so ∆c of the corresponding move has to be updated accordingly.

8. Decrement the level of each node u at level l, excluding v, if u would be a cheaper predecessor for v than its current predecessor, i.e. c(v, u) c(v, prednew (v)).

If a decrement move for u is already found in Q only the new connection between u and v has to be added. Furthermore, ∆c of the corresponding move has to be updated.

Otherwise, the move has to be calculated from scratch.

9. Increment the level of each node u at level l excluding v.

Now node v could be a new predecessor for u and for all old successors of u at level l + 1, as they lose their predecessor.

If there is already an increment move for u in the priority queue two things have

to be checked:

(a) The move contains another new predecessor, assume w, for u. If v would be a cheaper predecessor than w, update the corresponding information and the improvement ∆c.

(b) Old successors of u at level l + 1 will lose their predecessor. For all of these nodes there will be a new predecessor stored in the move.

– In the meantime (after the decrement move of v) it is possible that an old successor, assume w, of u is now successor of v. In this case w will not lose its predecessor, the corresponding information stored in the move record of u must be removed and ∆c has to be updated.





–  –  –

• If there is a decrement move of node v in the priority queue, delete it (it would be no longer valid).

• Reevaluate the following moves:

–  –  –

If this move is not in the priority queue Q it still has not to be considered, as nothing changed to make this move profitable. Nevertheless, if the move is already in Q the costs saved by this move ∆c include the benefit of connecting v to u instead of connecting it to predold (v). Therefore, ∆c and the fact that v is already connected to u have to be updated.

4. Increment the level of each node u at level l − 1 if such a move is already in the priority queue Q.

The move of v to level l has a lot of side effects on already existing increment moves of other nodes from level l − 1 to l. For example v is no longer available as predecessor for u and all old successors of u at level l. In addition, v and some old successors of v at level l could now have u as their new predecessor and so would require to find a new node they can connect to. Due to these various special cases an increment move of u already found in Q is evaluated from scratch.

5. Decrement the level of each node u at level l excluding v.

In case such a move is found in the priority queue Q two things have to be checked.

(a) Node v could become a new successor of u if u is a cheaper predecessor for v than its new one, i.e. c(u, v) c(prednew (v), v).

(b) Old successors of v at level l have lost their predecessor. Node u could now be attractive as new predecessor, if this connection is not already saved in the decrement move of u.

In both cases the objective value gain ∆c and the successor ↔ predecessor list of the move object have to be updated accordingly.

If such a move is not found in the priority queue Q it has to be evaluated from scratch. For efficiency the computation can be split into two steps. The only things changed are the two points described above, u is a possible new predecessor for v and for old successors of v. If the evaluation of these changes does not lead to a positive ∆c the move cannot be valuable. Therefore, the computation can already be aborted at this point.

6. Increment the level of each old successor u of v at level l.

–  –  –

can get back its old and cheaper predecessor v.

If such a move is already in the priority queue Q then only ∆c has to be updated accordingly, since before v’s increment move u was successor of v and u has now a different predecessor. The increment move of u stored in the priority queue Q means that there is another, cheaper predecessor for u at level l so it is not necessary to check the new predecessor of u stored in the move record against v.

If no such move can be found in the priority queue Q the increment move of u has to be evaluated completely new.

7. Decrement the level of each successor u of v at level l + 1 if such a move is already in the priority queue.

If no such move is found in Q it can be ignored since nothing happened that would now make a decrement of node u profitable.

In case there is such a move, u will lose v as predecessor so a new predecessor has to be found leading to a different objective value gain ∆c. The rest of the move can be taken without any change.

8. Decrement the level of each node u at level l + 1 with predecessors at level l, excluding successors of v, if such a move is already stored in the priority queue Q and u would have become successor of v.

Node u will lose its best predecessor v after performing its decrement move.

Again, the move itself can keep unchanged, only a new predecessor has to be found and the improvement ∆c must be updated accordingly.

5. ANT COLONY OPTIMISATION FOR THE BDMST PROBLEM

In this chapter the concrete design of the ant colony optimisation algorithm for the bounded diameter minimum spanning tree problem, developed within the context of this master thesis, is presented. As already mentioned, ACO algorithms can be extended with extra capabilities to improve overall system efficiency, e.g. lookahead, local optimisation or backtracking strategies, to name just a few. The ACO algorithm introduced here is equipped with a local optimisation heuristic, namely a variable neighbourhood descent. So before going into the details of the ACO algorithm for the BDMST problem itself, first a VND for the BDMST is introduced, as this VND plays an important role within the ant colony optimisation algorithm.

5.1 Variable Neighbourhood Descent

In Chapter 3.1 various strategies to guide a search within a certain neighbourhood have been described. For the ACO the deterministic variable neighbourhood descent (VND) framework is used. The different neighbourhood structures for this VND are those four presented in the preceding chapter, namely Edge Exchange, Node Swap, Centre Exchange and Level Change.

The VND algorithm introduced here varies a little from the general VND framework as proposed by Hansen and Mladenovi´ [23]. When following this general VND framework, c the algorithm stops exploring a certain neighbourhood of a solution T, Ni (T ) with i 1, after identifying the best neighbouring solution of T with respect to this neighbourhood structure, T ∈ Ni (T ). It sets T to T and switches back immediately to the first neighbourhood structure N1. However, as a best improvement strategy is used to identify an improvement move, the whole neighbourhood has to be enumerated. Depending on the denition of the neighbourhood structure it is sometimes possible to store information while exploring the whole neighbourhood (as shown in the previous chapter). This information allows a faster computation of the successive best move when a move has only local impact on it. Such an incremental enumeration has been introduced for the Node Swap and Level

5. Ant Colony Optimisation for the BDMST Problem 40

–  –  –

Change neighbourhood structures. To benefit from this incremental exploration the VND algorithm presented here does not switch back to the first neighbourhood after having identified the best improvement move. Instead it computes a local optimal solution with respect to the current neighbourhood structure under consideration and only jumps back to the first neighbourhood N1, in case the solution could be improved.

After defining the different neighbourhood structures the VND is based on, the order these neighbourhoods should by applied to a solution has to be determined. This decision has crucial impact either on the computation time as well as on the quality of solutions obtained.

The neighbourhood order for this VND algorithm has been taken from the VNS for the BDMST proposed by Gruber and Raidl [21], as the neighbourhood structures used in their VNS algorithm are basically the same as those utilised within this VND framework.

Algorithm 8 gives an overview of the VND framework used within the context of this master thesis. Starting from a solution T, first the Edge Exchange neighbourhood tries to improve T by moving around whole subtrees. When a local minimum with respect to the Edge Exchange neighbourhood is reached, T is tried to be further improved by optimising the arrangement of every node and its immediate successors (Node Swap). This is again done – as already mentioned and in contrast to the general VND – until a local optimal solution T is found. Afterwards, in case T is better than T, T is saved as new so far best solution T within this VND and the algorithm jumps back to the first neighbourhood structure.

If T was already a local minimum due to these two neighbourhoods the Centre Exchange neighbourhood tempts to further improve it by changing the centre node(s). Again, if the Centre Exchange neighbourhood yields an improvement move, the algorithm does not switch back immediately to the Edge Exchange neighbourhood. Instead, it computes a local minimum T due to the Centre Exchange neighbourhood structure and jumps back

5. Ant Colony Optimisation for the BDMST Problem 41 afterwards. And finally, if T is a local minimum with respect to the Edge Exchange, Node Swap and Centre Exchange neighbourhood, Level Change tries to optimally arrange all non-centre nodes within the level structure. When this VND algorithm terminates it reached a local optimal solution with respect to all four different neighbourhood structures.

5.2 Ant Colony Optimisation

As already presented in Chapter 3.2, several different ant algorithms have been developed.



Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |   ...   | 8 |


Similar works:

«Visual scale factor for speed perception Florent Colombet, Damien Paillot, Fr´d´ric Merienne, Andras Kemeny ee To cite this version: Florent Colombet, Damien Paillot, Fr´d´ric Merienne, Andras Kemeny. Visual scale factor for ee speed perception. Journal of Computing and Information Science in Engineering, American Society of Mechanical Engineers, 2011, 11 (4), pp.041010-1 to 041010-6. hal-00669934 HAL Id: hal-00669934 https://hal.archives-ouvertes.fr/hal-00669934 Submitted on 14 Feb 2012...»

«Industrial Crisis Quarterly 5 (1991) 293-322 Elsevier Muddling through a nuclear-political emergency: multilevel crisis management in West Germany after radioactive fallout from Chernobyl Roland M. Czada Faculty ofPolitical and Administrative Sciences. University ofConstance. PO Box 5560, 7750 Constance. Germany Abstract Czada, R.M., 1991. Muddling through a nuclear-political emergency: multilevel crisis management in West Germany after radioactive fallout from Chernobyl. Industrial Crisis...»

«Ohio’s State Tests Fall 2015 DIRECTIONS FOR ADMINISTRATION MANUAL Testing Support For assistance with Contact Portal for Ohio’s State Tests Testing resources, manuals, user guides, guidance documents, technical specifications and practice www.ohiostatetests.org materials Portal for Ohio’s State Tests Online Testing Checklist and oral script www.ohiostatetests.org American Institutes for Research (AIR) Error messages received during the online test 1-877-231-7809 administrations...»

«USER MANUAL for all 4-line bridled foil kites Introduction Congratulations! Thank you for purchasing a Peter Lynn product. This Peter Lynn product has been designed by one of the world’s foremost designers of power-kites and buggy equipment and is constructed to give you many years of fun and joy. You are now the proud owner of a power kite, which has been designed for use on land. Please read this manual carefully before using the kite for the first time in order to get the best result and...»

«Rodovi Slanskog Primorja Most from a professionals which do regulatory free are only. There need a temperatures you can give to negotiate a bills of Rodovi Slanskog Primorja an %. You can hit and do her situation success for largest in each lender to keep the Rodovi Slanskog Primorja sector of their resources and develop going up about past lot. Defending to way products, East Estates Act leads one at a own hands-on pdf income processes in an letter that looked the eagerness with interest that...»

«Garment 1 \tech\book\garment.doc Rev. 1996 10 22 THE GARMENT INDUSTRY1 The partial automation of the garment industry provides important insights into both North-South trading relations and gender relations in the work place2. The garment industry is of major importance to Third World trade, especially to the NICs (Newly Industrialized Countries). Exports of clothing from these countries increased exponentially in the post-war period. The comparative cost argument for a global market, with each...»

«CSIR Post-graduate Programme Brochure (2014-2015) Two year PG Research Programme in Engineering entitled Advanced Automotive Technology CSIR Indian Institute of Petroleum, Dehradun Index Aims and Scope 3 Number of Seats 3 Admission Procedure and Eligibility for Admissions 3 Fellowship 4 Programme Fee Structure 4 Semester-wise Programme Outline 4 Course Description 5 Aims and Scope This PG research programme aims to provide in-depth exposure to the Engineering concepts, Scientific principles,...»

«White Paper 01-06: Expanded Beam versus Butt-Coupled Connectors Abstract: When it comes to the design of fiber optic connectors for harsh environments, two schools of thought dominate the market: Butt-Coupled or Expanded Beam Designs. Each approach has its own advantages and disadvantages and the choice of the ‘best’ connector can be blurred by the specifics of the application environment and unique requirements of the systems design. In this white paper, we explain the difference between...»

«Scientific Data Management: Challenges and Approaches in the Extreme Scale Era Arie Shoshani (LBNL), Scott Klasky (ORNL), Rob Ross (ANL) Abstract. Exascale computing will prove to be challenging for scientific data management, given the expected increased volume of data from simulations, and the current expectation of the extreme scale computer architecture and storage systems. Scientific data management includes all of the associated problems of managing the data from its inception, to how it...»

«SLAC-PUB-14789 Collective deceleration: toward a compact beam dump H.-C. Wu1, T. Tajima1,2, D. Habs1,2, A.W. Chao3, J. Meyer-ter-Vehn1 Max-Planck-Institut für Quantenoptik, D-85748 Garching, Germany Fakultät für Physik, Ludwig-Maximilians-Universität München, D-85748 Garching, Germany SLAC National Accelerator Center, Stanford University, Stanford, California 94309, USA With the increasing development of laser accelerators, the electron energy is already beyond GeV and even higher in near...»

«Speech and Debate I COURSE DESCRIPTION Discipline Specific This course offers a wide variety and range of public speaking and argumentative tasks. Students Vocabulary analyze text, create and deliver orations, create and deliver arguments, analyze literature, make verbal Ethos presentations to an audience, and evaluate and critique performances. Skills focus includes the Pathos development of techniques in diction, articulation, vocal variety, enunciation, editing and projection. Logos...»

«60 GHz Transceiver Circuits in SiGe-HBT and CMOS Technologies vorgelegt von Master of Science Amin Hamidian Von der Fakultät IV – Elektrotechnik und Informatik der Technischen Universität Berlin zur Erlangung des akademischen Grades Doktor der Ingenieurwissenschaften Dr.-Ing. genehmigte Dissertation Promotionsausschuss: Vorsitzender: Prof. Dr.-Ing. Clemens Gühmann Gutachter: Prof. Dr.-Ing. Georg Böck Gutachter: Prof. Dr.-Ing. Arne Jacob Tag der wissenschaftlichen Aussprache: 10. Dezember...»





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