تحصيلات تکميلي

نام و نام خانوادگي : رضا وثوقي

دانشکده : فني و مهندسي

استاد راهنما : دکتر کامران زماني فر

تاريخ دفاع : 13/11/83

رشته و گرايش : کامپيوتر-معماري کامپيوتر

استاد مشاور : -

ارائه روشي براي پيدا کردن کوتاهترين مسير با استفاده از عملگرهاي ژنتيک

چکيده

در تحليل شبکه ها، مسيريابي1 يکي از مهمترين مواردي است که روي کارايي شبکه تاثير بسزايي دارد. مسيريابي مناسب مي بايست در زمان معين انجام گيرد. پروسة مسيريابي مناسب مي بايست در زمان ذکر شده، کوتاهترين مسير را پيدا کند و کوتاهترين مسير يعني مسيري بين دو گره مفروض از شبکه بطوري که حداقل هزينه2 را در بر داشته باشد.

براي مسئلة کوتاهترين مسير، الگوريتمهاي زيادي تاکنون ارائه شده است. اين الگوريتمها به دو گروه تقسيم ميشوند: الگوريتمهاي کلاسيک و الگوريتمهاي ژنتيک. از آنجائيکه امروزه از الگوريتمهاي ژنتيک به عنوان روشهاي بهينه سازي با کاربرد وسيع، استفاده مي گردد، در اين تحقيق سعي بر آن است که گامي در جهت بهبود الگوريتمهاي ژنتيک کوتاهترين مسير برداشته شود. با توجه به اهميت روزافزون اين الگوريتمها در بهبود روشهاي موجود، اهميت اين کار مشخص مي گردد.

الگوريتمهاي ژنتيک داراي اجزاء مختلفي ميباشند که عملگرهاي جهشي و ترکيب مجدد از آن جمله اند. از آنجائيکه انتخاب عملگرها و ترکيب آنها در هنگام اجراي الگوريتم، از اهميت بسزايي برخوردار است و عملکرد الگوريتم را تحت الشعاع قرار مي دهد، در اين تحقيق روشي جهت پيدا نمودن عملگرهاي مناسب براي الگوريتمهاي ژنتيک کوتاهترين مسير ارائه ميشود. نتايج حاصل از روش بهبود يافته با نتايج حاصل از الگوريتمي که انتخاب عملگرها را بطور تجربي انجام داده است، مقايسه ميگردد.

1- routing

2- cost