Spelling suggestions: "subject:"βελτιστοποίηση""
1 |
Ένα εκπαιδευτικό πακέτο για το πρόβλημα της βελτιστοποίησης χωρίς περιορισμούςΚανατζιάς, Γαβριήλ 31 March 2010 (has links)
Το Βασικό κομμάτι της εργασίας είναι ένα πρόγραμμα με γραφικό περιβάλλον γραμμένο στο Matlab για την επίλυση προβλημάτων Βελτιστοποίησης χωρίς περιορισμούς χρησιμοποιώντας αλγορίθμους. / The main subject of this diploma is a program with graphical environment written in Matlab for solving Optimization problems without restrictions using algorithms. The first part of the diploma, has the theory that is necessary for understanding the problem of Optimization, definitions and theorems. The second part contains the description of the algorithms: Steepest Descent, Conjugate Gradient (Hestenes-Stiefel formula, Polak-Ribiere formula, Fletcher-Reeves formula, Powell formula), Newton-Raphson, Quasi-Newton (SR1, DFP, BFGS). A few information are given for the programming language of Matlab. Also there is a chapter in the paper which contains information about the functions of the program. The user can choose the function, the initial point, the precision, the algorithm and the interval for the graphics. The results of the program are the points of algorithm, the value of the function, and the graphics for one, two or more variables. Lastly there are five functions for testing the algorithms and the program.
|
2 |
Μία μέθοδος ανάλυσης της αποδοτικότητας μεγάλων οργανισμώνΚαρατζάς, Ανδρέας 18 February 2010 (has links)
Σκοπός αυτής της διπλωματικής είναι να παρουσιάσει τη μεθοδολογία της Data Envelopment Analysis, μιας τεχνικής σύγκρισης οργανισμών με απώτερο σκοπό τη βελτιστοποίηση της λειτουργίας τους και τη μέτρηση της αποδοτικότητας τους. Γενικά οι μέθοδοι της ΠΕΑ χρησιμοποιούνται ως εργαλείο ώστε να αντιληφθούμε καλυτέρα και να αναλύσουμε το πώς κατανέμονται οι πόροι μιας επιχείρησης και πως αυτοί συνεισφέρουν στην παραγωγή της. Επιπρόσθετα, έχουν ως σκοπό να μεγιστοποιήσουν την απόδοση της επιχείρησης είτε περιορίζοντας τους πόρους της διατηρώντας το παραγόμενο προϊόν σταθερό είτε ελαχιστοποιώντας το παραγόμενο προϊόν διατηρώντας τους πόρους σταθερούς.
Προκειμένου να μελετηθεί μια μονάδα απόφασης διαχωρίζεται σε «εισόδους» και «εξόδους». Όταν μιλάμε για εισόδους της υπό μελέτης μονάδας εννοούμε τους αναγκαίους πόρους που χρειάζεται για να λειτουργήσει ενώ αντίστοιχα ως εξόδους αναφέρουμε τα παραγόμενα προϊόντα ή υπηρεσίες που προσφέρει. Για παράδειγμα, ως είσοδοι σε τραπεζικά υποκαταστήματα μπορεί να θεωρηθούν τα λειτουργικά κόστη του ακινήτου και το προσωπικό ενώ ως έξοδοι το σύνολο των χρηματικών συναλλαγών που πραγματοποιούνται ή ο αριθμός των πελατών που έχουν συνάψει συνεργασία με το υποκατάστημα αυτό. Παρουσιάζεται αρχικά το μοντέλο CCR που είναι το βασικότερο ανάμεσα στις μεθόδους της DEA (παρουσιάστηκε το 1978 από τους Charnes, Cooper και
Rhodes). Παρατίθεται η υπολογιστική διαδικασία του μοντέλου ΕΟΚ καθώς και μία επέκταση του με την χρήση του δυϊκού προβλήματος το οποίο υπερτερεί έναντι του πρωτεύοντος σε ταχύτητα επίλυσης σε μεγάλο αριθμό μονάδων απόφασης καθώς επίσης και στο εύρος λύσεων του προβλήματος. Το μοντέλο CCR καθώς και οι επεκτάσεις του στηρίχτηκαν στον ορισμό των σταθερών οικονομιών κλίμακας δηλαδή θα πρέπει να ισχύει ότι εάν μια δράση (x,y) είναι εφικτή, τότε για κάθε θετικό αριθμό t, η δράση (tx,ty) είναι επίσης εφικτή. Έτσι, αν αποδώσουμε γραφικά την αποδοτικότητα όλων των μονάδων απόφασης και σχεδιάσουμε το σύνορο αποδοτικότητας, αυτό θα αποτελείται από ευθύγραμμα τμήματα με ακμές τις μονάδες απόφασης.
Το επόμενο μοντέλο που παρουσιάζεται είναι αυτό των Banker, Charnes και Cooper (BBC) όπου η κύρια διάφορα του με το προηγούμενο έγκειται στο γεγονός ότι το σύνολο παραγωγικότητας είναι το κυρτό σύνολο των σημείων που απεικονίζουν τις μονάδες απόφασης (και όχι τα ευθύγραμμα τμήματα τους).
Κοινό χαρακτηριστικό και των δύο παραπάνω μοντέλων είναι ότι κάθε φορά στην ανάλυση των δεδομένων πρέπει να εστιάσουμε είτε στην ελαχιστοποίηση των εισόδων είτε στην μεγιστοποίηση των εξόδων για να εξάγουμε συμπεράσματα. Τα προσθετικά μοντέλα που παρουσιάζονται στη συνέχεια δεν κάνουν αυτόν τον διαχωρισμό καθώς στηρίζονται στην ελαχιστοποίηση της περίσσειας πόρων εισόδου και την ταυτόχρονη μεγιστοποίηση των παραγόμενων εξόδων. Επιπρόσθετα, πλεονέκτημα των προσθετικών μοντέλων είναι η ανάλυση αρνητικών δεδομένων κάτι που δεν ήταν εφικτό από τα προηγούμενα μοντέλα. Παρουσιάζεται, επίσης, μια επέκταση του προσθετικού μοντέλου όπου η μέτρηση της αποδοτικότητας δεν επηρεάζεται από τυχόν διαφορές στις μονάδες μέτρησης ανάμεσα στις εξόδους και τις εισόδους.
Τέλος περιγράφεται η ανάλυση ευαισθησίας που είναι μία σημαντική παράμετρος των μεθόδων της DEA καθώς δίνει την δυνατότητα σε κάποιον να μελετήσει τις διαφοροποιήσεις όταν εισάγονται η διαγράφονται μονάδες λήψης αποφάσεων η όταν εισάγονται η διαγράφονται είσοδοι και έξοδοι σε ένα πρόβλημα. / The purpose of this thesis is to present the methodology of Data Envelopment Analysis, a technique to compare organizations with a view to optimizing the operation and measurement of their profitability.
Generally, methods of DEA are used as a tool to better understand and analyze how resources are distributed and how each one contributes to company’s production. Additionally, they are designed to maximize the performance of business by limiting its resources while maintaining the output constant or by minimizing the product obtained by maintaining the resources constant.
The unique characteristics of every decision making unit are "inputs" and "outputs". Inputs of a unit correspond to the resources needed for the company to operate and outputs correspond to the products or services offered. For example, inputs in bank branches can be considered all the operating costs of the property and the personnel occupied and us outputs all financial transactions carried out or the whole number of customers that have made transactions with a particular branch.
Initially the CCR model is presented as it is considered to be the very first method of DEA (firstly introduced by Charnes, Cooper and Rhodes). The whole process of the CCR model is presented and also an extension and the use of the dual problem that outweighs the computational speed of the primary model in solving a large number of decision points as well as the range of solutions to the problem. The CCR model and its extensions are based on the definition of constant economies of scale which can be expressed as if an action (x, y) is feasible, then for each positive number t, the action (tx, ty) is also feasible. Thus, if we depict the performance of every decision making unit in a single graph with their corresponding performance, then the efficient frontier consists of segments that have decision making units in each edge
The next model presented is that of Banker, Charnes and Cooper (BBC) where the main difference with the previous lies in the fact that total productivity is the convex set of points that reflects the decision making units (and not their segments). A common feature of both these models is that each time the data analysis should focus either on minimizing inputs or on maximizing outputs to come over a conclusion. The additive models presented does not make this distinction as they are based on the minimization of the excess resources of inputs and simultaneously on the maximization of produced outputs. Additionally, a competitive advantage of the additive model is the analysis of negative data which was not possible with previous models. An extension of the additive model is presented where the measurement of efficiency is not affected by any differences in units between the inputs and outputs. Finally, the sensitivity analysis is described as an important parameter of DEA’s methods as it analyses the differences in production when a decision making unit is imported or deleted or when inputs and outputs are being inserted or deleted in a problem set.
|
3 |
Σύστημα οικονομικής και περιβαλλοντικής διαχείρισης οδοστρωμάτων με χρήση γενετικών αλγορίθμωνΠαναγοπούλου, Μαίρη 31 August 2012 (has links)
Τα τελευταία χρόνια στις περισσότερες χώρες έχει ολοκληρωθεί η κατασκευή οδικών δικτύων και το ενδιαφέρον των φορέων οδοποιίας έχει στραφεί στη διαχείριση των υφιστάμενων οδικών κατασκευών. Το κυριότερο τμήμα της Διαχείρισης Οδικών Δικτύων καταλαμβάνει η Διαχείριση Οδοστρωμάτων. Τα Συστήματα Διαχείρισης Οδοστρωμάτων έχουν ως στόχο την οικονομική διαχείριση των οδοστρωμάτων και χρησιμοποιούν τεχνητή νοημοσύνη για να καταλήξουν στη βέλτιστη και οικονομικά αποδοτικότερη κατανομή των διαθέσιμων πόρων. Το ευφυές σύστημα που διαθέτουν καταφέρνει να εντοπίζει τη βέλτιστη λύση που ελαχιστοποιεί το κόστος συντήρησης αλλά δεν λαμβάνουν υπόψη τους το αντίκτυπο της επιδείνωσης της κατάστασης του οδοστρώματος στο χρήστη και στο περιβάλλον.
Στην παρούσα εργασία χρησιμοποιείται ένας γενετικός αλγόριθμος και αναζητείται η βέλτιστη λύση που ελαχιστοποιεί το γενικευμένο κόστος, το οποίο περιλαμβάνει το κόστος συντήρησης, το κόστος του χρήστη εξαιτίας της κατάστασης του οδοστρώματος και το περιβαλλοντικό κόστος. Τα δεδομένα του προβλήματος αφορούν την κατάσταση των τμημάτων που πρόκειται να συντηρηθούν, το είδος της οδού στο οποίο ανήκουν τα τμήματα οδοστρώματος, τα στοιχεία φθορών κάθε τμήματος, τα διαθέσιμα είδη συντήρησης, το ύψος της χρηματοδότησης και τα κυκλοφοριακά χαρακτηριστικά της περιοχής στην οποία βρίσκονται τα υπό συντήρηση τμήματα.
Ο αλγόριθμος κατασκευάζει γονίδια επιλέγοντας είδος συντήρησης για κάθε τμήμα και για κάθε χρόνο συμπεριλαμβανομένης και της επιλογής να μην γίνει καμία συντήρηση σε κάποιο χρόνο. Τα γονίδια ελέγχονται με βάση περιορισμούς που έχουν τεθεί από τα μοντέλα φθορών κάθε τμήματος και επιλέγονται να μεταφερθούν στην επόμενη γενιά αυτά που συνδυάζουν το ελάχιστο κόστος και το μέγιστο επίπεδο λειτουργικότητας στο οδόστρωμα. Η διαφορά του μοντέλου σε σχέση με τα κοινά συστήματα διαχείρισης οδοστρωμάτων έγκειται περισσότερο στις υπολογιστικές απαιτήσεις του συστήματος καθώς η εφαρμογή γενετικού αλγορίθμου οδηγεί γρηγορότερα σε λύση από ότι οι κλασικές μέθοδοι βελτιστοποίησης όπως π.χ. ο γραμμικός προγραμματισμός.
Η καταλληλότητα και η ευκολία προσαρμογής των γενετικών αλγορίθμων σε προβλήματα διαχείρισης οδοστρωμάτων επαληθεύεται στην παρούσα εργασία. Το σύστημα καταφέρνει να εντοπίζει το βέλτιστο χρόνο με την οικονομικότερη συντήρηση του κάθε τμήματος του οδικού δικτύου και την πιο φιλική λύση για το χρήστη της οδού και το περιβάλλον. / In recent years the focus of the transportation authorities, researchers and practitioners is being shifted from the construction of new roads to the management of existing road structures and especially to road pavements. Pavement Management Systems are widely used and are continuously being improved because they can lead to considerable fund savings and/or to higher levels of service of road pavements.
In this work, a model for pavement maintenance and rehabilitation planning and optimal resource allocation is presented. The objective function aims at minimizing a generalized cost parameter which includes a number of monetary cost components and no monetary impacts. In particular, the objective function consists of the following components: (1) agency cost (the cost of applying the selected maintenance and rehabilitation strategy), (2) user costs (they include vehicle operating cost for fuel consumption, vehicle maintenance and depreciation, traffic delay cost, accident cost, discomfort cost, and delay cost due to maintenance works and (3) environmental impact costs due to traffic pollution and noise. The above cost components are considered with regard to the existing pavement condition levels which are represented by the PSI index. Pavement condition deterioration is assessed through deterministic models that have been developed earlier by our team based on expert opinions and fuzzy systems considering pavement related and traffic parameters, i.e., pavement age, pavement strength, pavement construction quality and traffic loads. The maintenance and rehabilitation treatments are considered with regard to their cost and effectiveness characteristics. Besides the pavement condition deterioration functions, other constraints of the model include budgetary availability (total and individually for different highway groups), threshold values for the minimum accepted pavement condition levels (by highway class), desirable pavement condition levels (by highway class), maintenance and rehabilitation treatment applicability and effectiveness, etc.
Due to the size and complexity of the problem (non linear functions), a genetic algorithm has been used as an optimization tool. The algorithm forms solutions by considering applicable maintenance treatments at each pavement section and year within the analysis period. Each solution is checked against all constraints to ensure the feasibility of the solution. No feasible solutions are discarded and new solutions are generated until the required offspring solutions are obtained. The optimization runs over several road sections with different traffic and pavement condition characteristics and within a time span of 10 years. The budgetary or the minimum accepted pavement condition constraints can be altered in order to get a Pareto-front set of optimal solutions for a particular application. Preliminary evaluation indicates that the model provides reasonable results in terms of the appropriate selection of maintenance and rehabilitation treatments and the time of application.
|
4 |
Ανάπτυξη αποδοτικών παραμετρικών τεχνικών αντιστοίχισης εικόνων με εφαρμογή στην υπολογιστική όρασηΕυαγγελίδης, Γεώργιος 12 January 2009 (has links)
Μια από τις συνεχώς εξελισσόμενες περιοχές της επιστήμης των υπολογιστών είναι η Υπολογιστική Όραση, σκοπός της οποίας είναι η δημιουργία έξυπνων συστημάτων για την ανάκτηση πληροφοριών από πραγματικές εικόνες. Πολλές σύγχρονες εφαρμογές της υπολογιστικής όρασης βασίζονται στην αντιστοίχιση εικόνων. Την πλειοψηφία των αλγορίθμων αντιστοίχισης συνθέτουν παραμετρικές τεχνικές, σύμφωνα με τις οποίες υιοθετείται ένα παραμετρικό μοντέλο, το οποίο εφαρμοζόμενο στη μια εικόνα δύναται να παρέχει μια προσέγγιση της άλλης. Στο πλαίσιο της διατριβής μελετάται εκτενώς το πρόβλημα της Στερεοσκοπικής Αντιστοίχισης και το γενικό πρόβλημα της Ευθυγράμμισης Εικόνων. Για την αντιμετώπιση του πρώτου προβλήματος προτείνεται ένας τοπικός αλγόριθμος διαφορικής αντιστοίχισης που κάνει χρήση μιας νέας συνάρτησης κόστους, του Τροποποιημένου Συντελεστή Συσχέτισης (ECC), η οποία ενσωματώνει το παραμετρικό μοντέλο μετατόπισης στον κλασικό συντελεστή συσχέτισης. Η ενσωμάτωση αυτή καθιστά τη νέα συνάρτηση κατάλληλη για εκτιμήσεις ανομοιότητας με ακρίβεια μικρότερη από αυτήν του εικονοστοιχείου. Αν και η συνάρτηση αυτή είναι μη γραμμική ως προς την παράμετρο μετατόπισης, το πρόβλημα μεγιστοποίησης έχει κλειστού τύπου λύση με αποτέλεσμα τη μειωμένη πολυπλοκότητα της διαδικασίας της αντιστοίχισης με ακρίβεια υπο-εικονοστοιχείου. Ο προτεινόμενος αλγόριθμος παρέχει ακριβή αποτελέσματα ακόμα και κάτω από μη γραμμικές φωτομετρικές παραμορφώσεις, ενώ η απόδοσή του υπερτερεί έναντι γνωστών στη διεθνή βιβλιογραφία τεχνικών αντιστοίχισης ενώ φαίνεται να είναι απαλλαγμένος από το φαινόμενο pixel locking. Στην περίπτωση του προβλήματος της ευθυγράμμισης εικόνων, η προτεινόμενη συνάρτηση γενικεύεται με αποτέλεσμα τη δυνατότητα χρήσης οποιουδήποτε δισδιάστατου μετασχηματισμού. Η μεγιστοποίησή της, η οποία αποτελεί ένα μη γραμμικό πρόβλημα, επιτυγχάνεται μέσω της επίλυσης μιας ακολουθίας υπο-προβλημάτων βελτιστοποίησης. Σε κάθε επανάληψη επιβάλλεται η μεγιστοποίηση μιας μη γραμμικής συνάρτησης του διανύσματος διορθώσεων των παραμέτρων, η οποία αποδεικνύεται ότι καταλήγει στη λύση ενός γραμμικού συστήματος. Δύο εκδόσεις του σχήματος αυτού προτείνονται: ο αλγόριθμος Forwards Additive ECC (FA-ECC) και o αποδοτικός υπολογιστικά αλγόριθμος Inverse Compositional ECC (IC-ECC). Τα προτεινόμενα σχήματα συγκρίνονται με τα αντίστοιχα (FA-LK και SIC) του αλγόριθμου Lucas-Kanade, ο οποίος αποτελεί σημείο αναφοράς στη σχετική βιβλιογραφία, μέσα από μια σειρά πειραμάτων. Ο αλγόριθμος FA-ECC παρουσιάζει όμοια πολυπλοκότητα με τον ευρέως χρησιμοποιούμενο αλγόριθμο FA-LΚ και παρέχει πιο ακριβή αποτελέσματα ενώ συγκλίνει με αισθητά μεγαλύτερη πιθανότητα και ταχύτητα. Παράλληλα, παρουσιάζεται πιο εύρωστος σε περιπτώσεις παρουσίας προσθετικού θορύβου, φωτομετρικών παραμορφώσεων και υπερ-μοντελοποίησης της γεωμετρικής παραμόρφωσης των εικόνων. Ο αλγόριθμος IC-ECC κάνει χρήση της αντίστροφης λογικής, η οποία στηρίζεται στην αλλαγή των ρόλων των εικόνων αντιστοίχισης και συνδυάζει τον κανόνα ενημέρωσης των παραμέτρων μέσω της σύνθεσης των μετασχηματισμών. Τα δύο αυτά χαρακτηριστικά έχουν ως αποτέλεσμα τη δραστική μείωση του υπολογιστικού κόστους, ακόμα και σε σχέση με τον SIC αλγόριθμο, με τον οποίο βέβαια παρουσιάζει παρόμοια συμπεριφορά. Αν και ο αλγόριθμος FA-ECC γενικά υπερτερεί έναντι των τριών άλλων αλγορίθμων, η επιλογή μεταξύ των δύο προτεινόμενων σχημάτων εξαρτάται από το λόγο μεταξύ ακρίβειας αντιστοίχισης και υπολογιστικού κόστους. / Computer Vision has been recently one of the most active research areas in computer society. Many modern computer vision applications require the solution of the well known image registration problem which consist in finding correspondences between projections of the same scene. The majority of registration algorithms adopt a specific parametric transformation model, which is applied to one image, thus providing an approach of the other one. Towards the solution of the Stereo Correspondence problem, where the goal is the construction of the disparity map, a local differential algorithm is proposed which involves a new similarity criterion, the Enhanced Correlation Coefficient (ECC). This criterion is invariant to linear photometric distortions and results from the incorporation of a single parameter model into the classical correlation coefficient, defining thus a continuous objective function. Although the objective function is non-linear in translation parameter, its maximization results in a closed form solution, saving thus much computational burden. The proposed algorithm provides accurate results even under non-linear photometric distortions and its performance is superior to well known conventional stereo correspondence techniques. In addition, the proposed technique seems not to suffer from pixel locking effect and outperforms even stereo techniques, dedicated to the cancellation of this effect. For the image alignment problem, the maximization of a generalized version of ECC function that incorporates any 2D warp transformation is proposed. Although this function is a highly non-linear function of the warp parameters, an efficient iterative scheme for its maximization is developed. In each iteration of the new scheme, an efficient approximation of the nonlinear objective function is used leading to a closed form solution of low computational complexity. Two different iterative schemes are proposed; the Forwards Additive ECC (FA-ECC) and the Inverse Compositional ECC (IC-ECC) algorithm. Τhe proposed iterative schemes are compared with the corresponding schemes (FA-LK and SIC) of the leading Lucas-Kanade algorithm, through a series of experiments. FA-ECC algorithm makes use of the known additive parameter update rule and its computational cost is similar to the one required by the most widely used FA-LK algorithm. The proposed iterative scheme exhibits increased learning ability, since it converges faster with higher probability. This superiority is retained even in presence of additive noise and photometric distortion, as well as in cases of over-modelling the geometric distortion of the images. On the other hand, IC-ECC algorithm makes use of inverse logic by swapping the role of images and adopts the transformation composition update rule. As a consequence of these two options, the complexity per iteration is drastically reduced and the resulting algorithm constitutes the most computationally efficient scheme than three other above mentioned algorithms. However, empirical learning curves and probability of convergence scores indicate that the proposed algorithm has a similar performance to the one exhibited by SIC. Though FA-ECC seems to be clearly more robust in real situation conditions among all the above mentioned alignment algorithms, the choice between two proposed schemes necessitates a trade-off between accuracy and speed.
|
5 |
Μελέτη των RWA και IA-RWA μέσω γενετικών αλγορίθμωνΜονογιός, Δημήτρης 26 August 2009 (has links)
Η πρόσφατη τεχνολογική ανάπτυξη των οπτικών ενισχυτών, πολυπλεκτών/αποπλεκτών, οπτικών διακοπτών καθώς και άλλων οπτικών συσκευών μας οδηγεί στο να ελπίζουμε ότι σύντομα στο μέλλον θα υλοποιηθεί ένα πλήρες οπτικό (all optical), WDM (wavelength division multiplexing) δίκτυο που να ικανοποιεί και την ανάγκη για μεγάλα μεγέθη χωρητικότητας. Σε ένα τέτοιο δίκτυο η μετατροπή του οπτικού σήματος σε ηλεκτρονικό και εκ νέου στο οπτικό (ΟΕΟ) δεν θα χρησιμοποιείται στους ενδιάμεσους κόμβους, και αυτό συμβάλει σε οικονομικότερες υλοποιήσεις των οπτικών δικτύων. Σε ένα WDM δρομολογούμενο δίκτυο, τα δεδομένα μεταφέρονται μέσω ενός οπτικού καναλιού, lightpath, στους κόμβους του δικτύου που συνδέονται με οπτικές ίνες. Στις πλείστες των περιπτώσεων, κατά την άφιξη ενός lightpath σε κάποιο κόμβο, εφαρμόζεται σε αυτό οπτικό-ηλεκτρονική μετατροπή και αντίστροφα, ούτως ώστε το σήμα να αναδημιουργηθεί λόγω των απωλειών που υπέστη κατά την μεταφορά, ή ακόμη για να αναλυθεί από ενδιάμεσες ηλεκτρονικές συσκευές. Στα μη πλήρη οπτικά δίκτυα, η μεταφορά των δεδομένων γίνεται από κόμβο σε κόμβο κατά μήκος του δικτύου, ούτως ώστε το οπτικό σήμα να ενισχύεται και να αναγεννάτε μέσω της OEO επεξεργασίας. Παρ’ όλα αυτά, η κάθε ενδιάμεση ανάλυση του θέματος σε ένα τέτοιο δίκτυο προϋποθέτει πολύ μεγάλα κόστη λόγω των πολλών συσκευών που απαιτούνται για τη OEO επεξεργασία. Το γεγονός αυτό μας οδηγεί στα ημί-πλήρη δίκτυα όπου η ενίσχυση και αναγέννηση του θέματος δε γίνεται σε όλους τους ενδιάμεσους κόμβους αλλά σε μερικούς από αυτούς. Ο τελικός στόχος όμως είναι η απαλοιφή της ηλεκτρονικής μετατροπής και αυτό οδηγεί στην υλοποίηση των πλήρως οπτικών δικτύων. Στα πλήρη οπτικά δίκτυα, ένα σήμα που μεταδίδεται παραμένει, για όλο το lightpath, στο οπτικό επίπεδο. Έτσι, το πλήρες οπτικό δίκτυο μπορεί να απαλείψει την ασύμφορη OEO μετατροπή.
Η αναζήτηση των κατάλληλων μονοπατιών με τα κατάλληλα μήκη κύματος που θα ικανοποιούσε ένα πλήρες οπτικό δίκτυο το οποίο δρομολογείται από ligthpaths, ονομάζεται Routing and Wavelength Assignment (RWA) και αποτελεί ένα από τα σημαντικότερα ζητήματα για το σωστό σχεδιασμό των οπτικών δικτύων τέτοιου είδους. Το πρόβλημα γίνεται ιδιαίτερα πολύπλοκο όταν στην τελική απόφαση θα πρέπει να συμπεριληφθούν και τα χαρακτηριστικά του φυσικού επιπέδου του δικτύου, όπως εξασθένιση του σήματος, μη γραμμικά φαινόμενα, διασπορά κ.ά, η συμβολή των οποίων στην τελική δρομολόγηση δεν θεωρείται αμελητέα (Impairment Aware Routing and Wavelength Assignment, ΙΑ-RWA). Σε αυτή την εργασία μελετάται το RWA πρόβλημα και προτείνεται ένας μονού στόχου γενετικός αλγόριθμος (Single Objective Genetic Algorithm - SOGA), ο οποίος επιλύει ικανοποιητικά το πρόβλημα θεωρώντας στατική κίνηση. Επιπλέον τονίζεται η σημασία των φυσικών παραμέτρων του προβλήματος και πως αυτές επηρεάζουν την απόδοση του πλήρους οπτικού δικτυου. Στη συνέχεια προτείνεται ένας νέος, πολλαπλών στόχων γενετικός αλγόριθμος (multi objective genetic algorithm – MOGA) ο οποίος βελτιστοποιεί τις λύσεις του προβλήματος ικανοποιητικά λαμβάνοντας ταυτόχρονα υπόψη, με έμμεσο τρόπο, και τις φυσικές παραμέτρους. Επίσης προτείνεται και ένας μονού στόχου γενετικός αλγόριθμος οποίος χρησιμοποιεί ένα εργαλείο αποτίμηση της ποιότητας μετάδοσης (Q-TOOL) σαν μέτρο κατά τη διαδικασία εύρεσης ικανοποιητικής λύσης. Το υπόλοιπο της εργασίας οργανώνεται ως ακολούθως: Στην ενότητα 2 παρουσιάζεται μια σύντομη αναφορά στα WDM δίκτυα καθώς και η περιγραφή του RWA και IA-RWA προβλήματος, ενώ στην ενότητα 3 παρουσιάζεται η πρόταση επίλυσης του RWA προβληματος με τη χρήση γενετικών αλγορίθμων. Ακολουθεί στην ενότητα 4 η πρότασή μας για επίλυση του IA-RWA προβλήματος με τη χρήση Multi-objective διαδικασιών βελτιστοποίησης, καθώς και η βελτιστοποίηση του προβλήματος με τη χρήση του Q-TOOL. Τέλος στην ενότητα 5 συνοψίζουμε την εργασία και παρουσιάζουμε τα συμπεράσματα. / The recent development of optical amplifiers, multiplexers / de-multiplexers, optical switches and other optical devices leads us to hope that soon in future all optical, WDM (wavelength division multiplexing) networks will be implemented which that will satisfy the needs for large capacity. In such networks a viable conversion of the optical -> Electronic and back to optical (OEO) will not be used at intermediate nodes, and this will contribute to efficient and economical implementation.
The search for the appropriate paths with the appropriate wavelengths that meet the requirement in all optical networks is called Routing and Wavelength Assignment (RWA) and is one of the most important issues for proper design of such optical networks. The problem becomes particularly complex when the final decision should include the characteristics of the physical layer of the network, such as attenuation of the signal, nonlinear effects, dispersion, etc., whose contribution to the final result is not considered negligible (Impairment Aware Routing and Wavelength Assignment,IA-RWA).
This work studies the RWA problem considering static traffic, and proposes a single-objective genetic algorithm (Single Objective Genetic Algorithm - SOGA), which resolves the problem satisfactorily. Furthermore the work stresses the importance of physical parameters of the problem and how these affect the performance of the all optical networks, and proposes a new, multi-objective genetic algorithm (MOGA) which optimizes the solution of IA-RWA problem adequately taking into account indirectly, and the physical impairments that affect the quality of the signal. In addition, a single objective genetic algorithm is proposed that uses a tool to assess the quality of the transmission signal (Q-TOOL), as a benchmark, in the process of optimization of the solution to the IA-RWA problem.
|
6 |
Σύστημα υλοποίησης και γραφικής αναπαράστασης αλγορίθμων ανάθεσης υπερσυνδέσμων στον παγκόσμιο ιστόΤριανταφυλλίδης, Γρηγόριος 02 September 2008 (has links)
Ο παγκόσμιος ιστός έχει εδραιωθεί πλέον ως το δημοφιλέστερο μέσο ανάκτησης πληροφοριών. Όπως είναι λογικό, όσο παλαιώνει τόσο μεγαλύτερη πληροφορία εμπεριέχει. Πληθαίνουν έτσι εκείνοι οι ιστότοποι που γιγαντώνονται άναρχα και ενώ σαν στόχο έχουν να προσφέρουν την πληροφορία στον χρήστη που τους επισκέπτεται, λόγω του τεράστιου όγκου της, κάνουν συχνά δύσκολη την πρόσβαση σε συγκεκριμένα κομμάτια αυτής. Με στόχο την αντιμετώπιση αυτής της κατάστασης, αναπτύσσονται τα τελευταία χρόνια αλγόριθμοι ανάθεσης υπερσυνδέσμων σε ιστοτόπους. Η λογική τους είναι ο εντοπισμός της πιο δημοφιλούς ή πιθανής πληροφορίας και η εξασφάλιση καλύτερης πρόσβασης σε αυτήν, αναθέτοντας υπερσυνδέσμους (hotlinks) προς τις ιστοσελίδες που την περιέχουν. Οι αλγόριθμοι αυτοί εφαρμόζονται όχι σε πραγματικές αναπαραστάσεις ιστοτόπων, αλλά κατά κανόνα στα αντίστοιχα κατευθυνόμενα άκυκλα γραφήματα (DAG) αυτών. Όπως είναι γνωστό κανένας ιστότοπος δεν έχει μορφή DAG, με συνέπεια να υπάρχει μία απόσταση από τη θεωρητική ανεύρεση υπερσυνδέσμων και την πιθανή εφαρμογή τους στην πραγματικότητα. Σε αυτήν την εργασία ασχολούμαστε αρχικά με την μεθοδική καταγραφή της πραγματικής συνδεσμολογίας ενός ιστότοπου, που αποτελεί ένα πρώτο βήμα στην ανάθεση υπερσυνδέσμων σε πραγματικούς ιστοτόπους. Αυτό επιτυγχάνεται με την κατάλληλη προδιαγραφή και υλοποίηση μιας δικτυακής μηχανής αναζήτησης, ώστε να ανταποκρίνεται στις ανάγκες μας. Προτείνουμε στη συνέχεια το εργαλείο ‘HotLink Visualizer’, το οποίο αρχικά μετατρέπει την πληροφορία της συνδεσμολογίας ενός ιστοτόπου σε απλά δεδομένα μορφής πίνακα και στη συνέχεια οπτικοποιεί το αποτέλεσμα. Τέλος, υλοποιεί την απευθείας ανάθεση υπερσυνδέσμων προσθέτοντας αυτόματα μέσα στις σελίδες του ιστοτόπου τους υπερσυνδέσμους και οπτικοποιεί εκ νέου το αποτέλεσμα. Παρέχει έτσι τη δυνατότητα διατήρησης διαφορετικών εκδόσεων της μορφής ενός ιστοτόπου, ανάλογα με το σύνολο από υπερσυνδέσμους που έχουν ανατεθεί σε αυτό. / The World Wide Web has become established as the most popular source of information retrieval. As expected, the older it gets the more information it contains and thus the number of the web sites with gigantic growth and bad information access rates is constantly increased within it. During the last years the matter is being addressed with the development of several hotlink assignment algorithms for web sites. The main idea behind those algorithms is to spot the most popular or more likely to be accessed piece of information and provide better access to it by assigning links (hotlinks) to the web pages containing it. These algorithms are not applied to the actual representations of these web sites but usually to their corresponding direct acyclic graphs (DAGs). However, it is widely known that a web site in its true form is not a DAG, since there can be found hundreds of links pointing to just one page. Hence, there is a gap between the theoretical determination of a set of hotlinks and the possible application of this set to a real web site. In this paper we first address the issue of recording and persisting the exact map of a web site with its full connectivity, which can be considered as a first step towards the assignment of hotlinks in real web sites. We succeed in that, with the appropriate specification and implementation of a web crawler, with functionality suited to our specific needs. We then propose an administrative tool, the ‘Hotlink Visualizer’, which, after persisting in tabular data all the necessary information to capture a web site’s real map, visualizes the outcome and implements hotlink additions by adding with an automated procedure the generated hotlinks in the web pages of the site. Thus we have the ability to maintain in row data different forms and versions of the originally parsed web site, as it can be formed from the assignment of different hotlink sets to it.
|
7 |
Στοχαστικός (γραμμικός) προγραμματισμόςΜαγουλά, Ναταλία 07 April 2011 (has links)
Πολλά είναι τα προβλήματα απόφασης τα οποία μπορούν να μοντελοποιηθούν ως προβλήματα γραμμικού προγραμματισμού. Πολλές όμως είναι και οι καταστάσεις όπου δεν είναι λογικό να υποτεθεί ότι οι παράμετροι του μοντέλου καθορίζονται προσδιοριστικά. Για παράδειγμα, μελλοντικές παραγωγικότητες σε ένα πρόβλημα παραγωγής, εισροές σε μία δεξαμενή που συνδέεται με έναν υδροσταθμό παραγωγής ηλεκτρικού ρεύματος, απαιτήσεις στους διάφορους κόμβους σε ένα δίκτυο μεταφορών κλπ, είναι καταλληλότερα μοντελοποιημένες ως αβέβαιες παράμετροι, οι οποίες χαρακτηρίζονται στην καλύτερη περίπτωση από τις κατανομές πιθανότητας.
Η αβεβαιότητα γύρω από τις πραγματοποιημένες τιμές εκείνων των παραμέτρων δεν μπορεί να εξαλειφθεί πάντα εξαιτίας της εισαγωγής των μέσων τιμών τους ή μερικών άλλων (σταθερών) εκτιμήσεων κατά τη διάρκεια της διαδικασίας μοντελοποίησης. Δηλαδή ανάλογα με την υπό μελέτη κατάσταση, το γραμμικό προσδιοριστικό μοντέλο μπορεί να μην είναι το κατάλληλο μοντέλο για την περιγραφή του προβλήματος που θέλουμε να λύσουμε. Σε αυτή τη διπλωματική υπογραμμίζουμε την ανάγκη να διευρυνθεί το πεδίο της μοντελοποίησης των προβλημάτων απόφασης που παρουσιάζονται στην πραγματική ζωή με την εισαγωγή του στοχαστικού προγραμματισμού. / There are many practical decision problems than can be modeled as linear programs. However, there are also many situations that it is unreasonable to assume that the coefficients of model are deterministically fixed. For instance, future productivities in a production problem, inflows into a reservoir connected to a hydro power station, demands at various nodes in a transportation network, and so on, are often appropriately modeled as uncertain parameters, which are at best characterized by probability distributions.
The uncertainty about the realized values of those parameters cannot always be wiped out just by inserting their mean values or some other (fixed) estimates during the modelling process. That is, depending on the practical situation under consideration, the linear deterministic model may not be the appropriate model for describing the problem we want to solve. In this project we emphasize the need to broaden the scope of modelling real life decision problems by inserting stochastic programming.
|
8 |
Νέες μέθοδοι εκμάθησης για ασαφή γνωστικά δίκτυα και εφαρμογές στην ιατρική και βιομηχανία / New learning techniques to train fuzzy cognitive maps and applications in medicine and industryΠαπαγεωργίου, Ελπινίκη 25 June 2007 (has links)
Αντικείµενο της διατριβής είναι η ανάπτυξη νέων µεθοδολογιών εκµάθησης και σύγκλισης των Ασαφών Γνωστικών ∆ικτύων που προτείνονται για τη βελτίωση και προσαρµογή της συµπεριφοράς τους, καθώς και για την αύξηση της απόδοσής τους, αναδεικνύοντάς τα σε αποτελεσµατικά δυναµικά συστήµατα µοντελοποίησης. Τα νέα βελτιωµένα Ασαφή Γνωστικά ∆ίκτυα, µέσω της εκµάθησης και προσαρµογής των βαρών τους, έχουν χρησιµοποιηθεί στην ιατρική σε θέµατα διάγνωσης και υποστήριξης στη λήψη απόφασης, καθώς και σε µοντέλα βιοµηχανικών συστηµάτων που αφορούν τον έλεγχο διαδικασιών, µε πολύ ικανοποιητικά αποτελέσµατα. Στη διατριβή αυτή παρουσιάζονται, αξιολογούνται και εφαρµόζονται δύο νέοι αλγόριθµοι εκµάθησης χωρίς επίβλεψη των Ασαφών Γνωστικών ∆ικτύων, οι αλγόριθµοι Active Hebbian Learning (AHL) και Nonlinear Hebbian Learning (NHL), βασισµένοι στον κλασσικό αλγόριθµό εκµάθησης χωρίς επίβλεψη τύπου Hebb των νευρωνικών δικτύων, καθώς και µια νέα προσέγγιση εκµάθησης των Ασαφών Γνωστικών ∆ικτύων βασισµένη στους εξελικτικούς αλγορίθµους και πιο συγκεκριµένα στον αλγόριθµο Βελτιστοποίησης µε Σµήνος Σωµατιδίων και στον ∆ιαφοροεξελικτικό αλγόριθµο. Οι προτεινόµενοι αλγόριθµοι AHL και NHL στηρίζουν νέες µεθοδολογίες εκµάθησης για τα ΑΓ∆ που βελτιώνουν τη λειτουργία, και την αξιοπιστία τους, και που παρέχουν στους εµπειρογνώµονες του εκάστοτε προβλήµατος που αναπτύσσουν το ΑΓ∆, την εκµάθηση των παραµέτρων για τη ρύθµιση των αιτιατών διασυνδέσεων µεταξύ των κόµβων. Αυτοί οι τύποι εκµάθησης που συνοδεύονται από την σωστή γνώση του εκάστοτε προβλήµατος-συστήµατος, συµβάλλουν στην αύξηση της απόδοσης των ΑΓ∆ και διευρύνουν τη χρήση τους. Επιπρόσθετα µε τους αλγορίθµους εκµάθησης χωρίς επίβλεψη τύπου Hebb για τα ΑΓ∆, αναπτύσσονται και προτείνονται νέες τεχνικές εκµάθησης των ΑΓ∆ βασισµένες στους εξελικτικούς αλγορίθµους. Πιο συγκεκριµένα, προτείνεται µια νέα µεθοδολογία για την εφαρµογή του εξελικτικού αλγορίθµου Βελτιστοποίησης µε Σµήνος Σωµατιδίων στην εκµάθηση των Ασαφών Γνωστικών ∆ικτύων και πιο συγκεκριµένα στον καθορισµό των βέλτιστων περιοχών τιµών των βαρών των Ασαφών Γνωστικών ∆ικτύων. Με τη µεθοδο αυτή λαµβάνεται υπόψη η γνώση των εµπειρογνωµόνων για τον σχεδιασµό του µοντέλου µε τη µορφή περιορισµών στους κόµβους που µας ενδιαφέρουν οι τιµές των καταστάσεών τους, που έχουν οριστοί ως κόµβοι έξοδοι του συστήµατος, και για τα βάρη λαµβάνονται υπόψη οι περιοχές των ασαφών συνόλων που έχουν συµφωνήσει όλοι οι εµπειρογνώµονες. Έτσι θέτoντας περιορισµούς σε όλα τα βάρη και στους κόµβους εξόδου και καθορίζοντας µια κατάλληλη αντικειµενική συνάρτηση για το εκάστοτε πρόβληµα, προκύπτουν κατάλληλοι πίνακες βαρών (appropriate weight matrices) που µπορούν να οδηγήσουν το σύστηµα σε επιθυµητές περιοχές λειτουργίας και ταυτόχρονα να ικανοποιούν τις ειδικές συνθήκες- περιορισµούς του προβλήµατος. Οι δύο νέες µέθοδοι εκµάθησης χωρίς επίβλεψη που έχουν προταθεί για τα ΑΓ∆ χρησιµοποιούνται και εφαρµόζονται µε επιτυχία σε δυο πολύπλοκα προβλήµατα από το χώρο της ιατρικής, στο πρόβληµα λήψης απόφασης στην ακτινοθεραπεία και στο πρόβληµα κατηγοριοποίησης των καρκινικών όγκων της ουροδόχου κύστης σε πραγµατικές κλινικές περιπτώσεις. Επίσης όλοι οι προτεινόµενοι αλγόριθµοι εφαρµόζονται σε µοντέλα βιοµηχανικών συστηµάτων που αφορούν τον έλεγχο διαδικασιών µε πολύ ικανοποιητικά αποτελέσµατα. Οι αλγόριθµοι αυτοί, όπως προκύπτει από την εφαρµογή τους σε συγκεκριµένα προβλήµατα, βελτιώνουν το µοντέλο του ΑΓ∆, συµβάλλουν σε ευφυέστερα συστήµατα και διευρύνουν τη δυνατότητα εφαρµογής τους σε πραγµατικά και πολύπλοκα προβλήµατα. Η κύρια συνεισφορά αυτής της διατριβής είναι η ανάπτυξη νέων µεθοδολογιών εκµάθησης και σύγκλισης των Ασαφών Γνωστικών ∆ικτύων προτείνοντας δυο νέους αλγορίθµους µη επιβλεπόµενης µάθησης τύπου Hebb, τον αλγόριθµο Active Hebbian Learning και τον αλγόριθµο Nonlinear Hebbian Learning για την προσαρµογή των βαρών των διασυνδέσεων µεταξύ των κόµβων των Ασαφών Γνωστικών ∆ικτύων, καθώς και εξελικτικούς αλγορίθµους βελτιστοποιώντας συγκεκριµένες αντικειµενικές συναρτήσεις για κάθε εξεταζόµενο πρόβληµα. Τα νέα βελτιωµένα Ασαφή Γνωστικά ∆ίκτυα µέσω των αλγορίθµων προσαρµογής των βαρών τους έχουν χρησιµοποιηθεί για την ανάπτυξη ενός ∆ιεπίπεδου Ιεραρχικού Συστήµατος για την υποστήριξη λήψης απόφασης στην ακτινοθεραπεία, για την ανάπτυξη ενός διαγνωστικού εργαλείου για την κατηγοριοποίηση του βαθµού κακοήθειας των καρκινικών όγκων της ουροδόχου κύστης, καθώς και για την επίλυση βιοµηχανικών προβληµάτων για τον έλεγχο διαδικασιών. / The main contribution of this Dissertation is the development of new learning and convergence methodologies for Fuzzy Cognitive Maps that are proposed for the improvement and adaptation of their behaviour, as well as for the increase of their performance, electing them in effective dynamic systems of modelling. The new improved Fuzzy Cognitive Maps, via the learning and adaptation of their weights, have been used in medicine for diagnosis and decision-making, as well as to alleviate the problem of the potential uncontrollable convergence to undesired states in models of industrial process control systems, with very satisfactory results. In this Dissertation are presented, validated and implemented two new learning algorithms without supervision for Fuzzy Cognitive Maps, the algorithms Active Hebbian Learning (AHL) and Nonlinear Hebbian Learning (NHL), based on the classic unsupervised Hebb-type learning algorithm of neural networks, as well as a new approach of learning for Fuzzy Cognitive Maps based on the evolutionary algorithms and more specifically on the algorithm of Particles Swarm Optimization and on the Differential Evolution algorithm. The proposed algorithms AHL and NHL support new learning methodologies for FCMs that improve their operation, efficiency and reliability, and that provide in the experts of each problem that develop the FCM, the learning of parameters for the regulation (fine-tuning) of cause-effect relationships (weights) between the concepts. These types of learning that are accompanied with the right knowledge of each problem-system, contribute in the increase of performance of FCMs and extend their use. Additionally to the unsupervised learning algorithms of Hebb-type for the FCMs, are developed and proposed new learning techniques of FCMs based on the evolutionary algorithms. More specifically, it is proposed a new learning methodology for the application of evolutionary algorithm of Particle Swarm Optimisation in the adaptation of FCMs and more concretely in the determination of the optimal regions of weight values of FCMs. With this method it is taken into consideration the experts’ knowledge for the modelling with the form of restrictions in the concepts that interest us their values, and are defined as output concepts, and for weights are received the arithmetic values of the fuzzy regions that have agreed all the experts. Thus considering restrictions in all weights and in the output concepts and determining a suitable objective function for each problem, result appropriate weight matrices that can lead the system to desirable regions of operation and simultaneously satisfy specific conditions of problem. The first two proposed methods of unsupervised learning that have been suggested for the FCMs are used and applied with success in two complicated problems in medicine, in the problem of decision-making in the radiotherapy process and in the problem of tumor characterization for urinary bladder in real clinical cases. Also all the proposed algorithms are applied in models of industrial systems that concern the control of processes with very satisfactory results. These algorithms, as it results from their application in concrete problems, improve the model of FCMs, they contribute in more intelligent systems and they extend their possibility of application in real and complex problems. The main contribution of the present Dissertation is to develop new learning and convergence methodologies for Fuzzy Cognitive Maps proposing two new unsupervised learning algorithms, the algorithm Active Hebbian Learning and the algorithm Nonlinear Hebbian Learning for the adaptation of weights of the interconnections between the concepts of Fuzzy Cognitive Maps, as well as Evolutionary Algorithms optimizing concrete objective functions for each examined problem. New improved Fuzzy Cognitive Maps via the algorithms of weight adaptation have been used for the development of an Integrated Two-level hierarchical System for the support of decision-making in the radiotherapy, for the development of a new diagnostic tool for tumour characterization of urinary bladder, as well as for the solution of industrial process control problems.
|
Page generated in 0.0271 seconds