دانلود ترجمه مقاله کاربرد الگوریتم ژنتیکی و جستجوی ممنوعه در بهینه سازی مسیریابی چندگانه کیفیت خدمات

• فهرست مطالب:

چکیده
۱ مقدمه
۲ فرمول نویسی مسئله
۳ روشی برای مسیریابی چندبخشی QoS بر مبنای الگوریتم ژنتیکی جستجوی ممنوعه (GTS)
۱ ۳ نمایش و جمعیت اولیه
۲ ۳ تابع برازش
۳ ۳ انتخاب
۴ ۳ طرح کراس اور
۵ ۳ عملیات جهش جستجوی ممنوعه
۱ ۵ ۳ مجموعه مسیرهای پشتیبانی
۲ ۵ ۳ ایجاد راه حل همسایگی
۳ ۵ ۳ لیست ممنوعه و طول ممنوعه
۴ ۵ ۳ معیار انتظار
۶ ۳ تابع ترمیم
۴ نتایج آزمایش
۵ نتایج

• بخشی از ترجمه:

مقاله حاضر یک الگوریتم کارآمد به نام GTS بر مبنای الگوریتم ژنتیکی و جستجوی ممنوعه برای حل مسئله مسیریابی چند بخشی هزینه حداقل با محدودیت های تاخیر انتها به انتها و پهنای باند مطرح کرد. الگوریتم مذکور برای حل این مسئله، GA و TS را به اندازه کافی باهم ترکیب می کند. کروموزوم های درخت چند بخشی با طرح کدگذاری ساختار درختی نمایش داده می شوند. این طرح کدگذاری عملیات کدگذاری را ساده کرده و فرایند کدگذاری و کدگشایی را حذف می کند. روش مقدار دهی اولیه جمعیت جدیدی براساس الگوریتم Prim پیشنهاد شده است. این روش اطمینان حاصل می کند که هر کروموزوم درخت چند بخشی مطلوبی بدون حلقه بوده و هر یک از محدودیت های تاخیر انتها به انتها و پهنای باند را تامین می کند.
در الگوریتم GTS پیشنهادی، از کاراکتر TS برای اجتناب از همگرایی نابهنگام GA و از کاراکتر GA برای اجتناب از کمبود TS استفاده شده است. در اینجا از نتایج شبیه سازی برای مقایسه عملکرد دو الگوریتم پیشنهادی با سایر الگوریتم های مبتنی بر GA موجود استفاده کرده ایم. نتایج شبیه سازی نشان داد که الگوریتم GTS پیشنهادی بهتر است، زیرا عملیات جهش جدید در الگوریتم پیشنهادی قدرت اکتشافی بالاتر و معیار تنوع ژنتیکی نسبتاً خوبی دارد.

• بخشی از مقاله انگلیسی:

Introduction With the advances in networking, switching technology and rapid growth of the Internet, many new communication services, high-bandwidth real time and multimedia applications have been become reality. Some of these applications require the transformation of multiple copies from a source node to a set of destination nodes in a network with various quality of service (QoS) performance [1],[2]. This kind of communication is called multicasting and it must be supported by a network. Multicasting is defined as the ability of a communication network to accept a single message from an application and deliver copies of the message to many recipients at different locations. To carry large number of multicast sessions, a network must minimizes the session‟s resource consumption, while meeting their QoS requirements [3],[4],[5]. QoS requirements are often versatile. For example, in video conference applications each link on the routing tree should guarantees a minimum available bandwidth (i.e., bandwidth constraint). In real-time applications, such as game applications and messages must be transmitted from the source node to their destinations within a certain amount of time. So, end-to-end delay can be considered as another important QoS parameter. The algorithms that construct multicast trees in the network are called multicast routing algorithms. An efficient QoS multicast algorithm should construct a multicast tree, by which the data can be transmitted from the source to a subset of destination nodes with guaranteed QoS [6],[7],[8],[9]. Several algorithms are proposed for solving the QoS multicast routing problem, these algorithms are based on separated metaheuristic methods such as genetic algorithm (GA), tabu search (TS) and simulated annealing (SA) [10],[11],[12]. But, few algorithms are proposed by combining two of these algorithms for solving this problem. A method based on genetic simulated annealing algorithm is proposed to solve this problem [5], in this method genetic algorithm or simulated annealing algorithm works respectively when the other algorithm can not be effective, which leads to a lower evolution speed. Each of genetic algorithm, tabu search and simulated annealing have their characteristics and some shortages. For example the shortage of TS and SA is depending on initial value and lower convergence speed and the shortage of GA is the premature convergence. ACSIJ Advances in Computer Science: an International Journal, Vol. 4, Issue 3, No.15 , May 2015 ISSN : 2322-5157 www.ACSIJ.org 118 Copyright (c) 2015 Advances in Computer Science: an International Journal. All Rights Aiming to that shortage, the Genetic Tabu search algorithm (GTS) is proposed for QoS multicast routing. Our proposed algorithm combines GA and TS adequately to solve this problem. The character of TS is used to avoid the premature convergence of GA. And the character of GA is used to avoid the shortage of TS such as depending on initial value and the lower convergence speed. GA has the character of parallel processing and high convergence speed. TS has the capability of escaping from local optimum. The objective of the new hybrid algorithm (GTS) is keeping the advantages and avoiding the disadvantages of both search algorithms. In the proposed algorithm GTS, the chromosomes of the multicast tree are represented by tree structure of Genetic Programming, to save the time of conversion between encoding space and solution space. A population initialization method is used to make sure that every chromosome in initial population is reasonable multicast tree without loops that satisfies the (link) bandwidth and (path) delay constraints. The crossover generates new chromosomes by exchanging partial chromosomes (i.e., sub-trees) without positional consistency of potential crossing site (crossover point) between two chromosomes. A new tabu search mutation operator is presented. Finally, a repair function treats infeasible chromosomes possibly generated after crossover. The rest of the paper is organized as follows. Section 2 describes a mathematical model for the representing multicast routing problem. The proposed GA is presented in Section 3. Section 4 shows experimental results. The paper is concluded in Section 5.