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

نام و نام خانوادگي : شهريار لطفي

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

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

تاريخ دفاع : 29/11/80

رشته و گرايش : کامپيوتر-نرم افزار

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

ارائه روشي براي طراحي درخت جستجوي دودويي با استفاده ازالگوريتمهاي ژنتيكي موازي

چکيده

در محيط اطراف مي‏توان مسائلي چون پيش بيني وضعيت آب و هوا، تصميم گيري در بورس، كنترل خطوط هوايي، كنترل ربات و غيره پيدا كرد. در اين مسايل بايد پاسخ مناسبي در كمترين زمان به وضعيت موجود در اين سيستمها داد. اين امر نياز به قدرت محاسباتي بالا در زمان محدود دارد. براي رفع اين مشكل بايد مدارهاي كامپيوتري را سريعتر كرد و يا الگوريتمهاي محاسباتي را بهينه كرد.

ظهور و توسعه الگوريتمهاي ژنتيكي به عنوان يك روش جستجوي تصادفي كه حساسيت زيادي روي اطلاعات اوليه از مسايل ندارد، مي‏تواند در تخمين پارامترهاي يك سيستم جهت كسب بهترين نتيجه مورد استفاده قرار گيرد. اين امر بوسيله بهينه سازي يك تابع هدف صورت مي‏گيرد. از طرفي تغييرات سريع وضعيت بعضي سيستمها مثل سيستمهاي ديناميكي ايجاب مي‏كند از روشي استفاده شود كه بهينه سازي تابع هدف را سرعت بخشد. براي اين منظور از الگوريتم ژنتيكي موازي استفاده مي‏شود. همچنين استفاده از اين نوع الگوريتمها در بهينه سازي سيستمهايي كه داراي چند تابع هدف هستند، مناسب خواهد بود.

در اين تحقيق الگوريتمهاي ژنتيكي و ژنتيكي موازي به عنوان يكي از بهترين راه حلهاي ممكن براي انجام بهينه سازي سيستمها مورد بحث قرار گرفته است. همچنين سعي شده است كه يكي از تكنيكهاي بهينه سازي سيستمها؛ يعني برنامه نويسي پويا، با استفاده از الگوريتمهاي ژنتيكي موازي سريعتر شود. براي اين منظور الگوريتمهاي ژنتيكي و ژنتيكي موازي در يك محيط برنامه نويسي موازي موسوم به مالتي پاسكال بررسي شده است. سپس درخت جستجوي دودويي بهينه به عنوان مسئله مورد مطالعه جهت كاهش زمان جستجو، انتخاب شده است و با استفاده از الگوريتم ژنتيكي موازي، روش برنامه نويسي پوياي اين مسئله سريعتر گرديده است. همچنين نشان داده شده است درموارديكه داده ها زياد باشند شاخص تسريع، هنگام استفاده از نوع موازي اين الگوريتمها افزايش مي يابد.