شماره ركورد
10107
شماره راهنما(اين فيلد مربوط به كارشناس ميباشد لطفا آن را خالي بگذاريد)
10107
پديد آورنده
امين نيكانجام
عنوان
بهبود كارايي مدلسازي در الگوريتمهاي تخمين توزيع
مقطع تحصيلي
دكتري
رشته تحصيلي
كامپيوتر - هوشمصنوعي
سال تحصيل
تيرماه 1391
تاريخ دفاع
تيرماه 1391
استاد راهنما
دكتر عادل رحماني
چكيده
چكيده
الگوريتمهاي تخمين توزيع نوعي از الگوريتمهاي تكاملي هستند كه در دهه گذشته به طور گسترده براي حل مجموعه متنوعي از مسائل بهينهسازي به كار رفتهاند. در اين الگوريتمها به جاي استفاده از عملگرهاي ژنتيكي سنتي، در هر نسل يك مدل احتمالي از راهحلهاي برگزيده جمعيت ساخته ميشود. اين مدل نشاندهندهي وابستگيها و ارتباط اجزاي مسأله است و براي يادگيري آن از جمعيت معمولاً از روشهاي يادگيري ماشين استفاده ميشود. اين الگوريتمها دو گلوگاه كارايي دارند: ساخت مدل و ارزيابي راهحلها، كه دومي در بين همه الگوريتمهاي تكاملي مشترك است. از سوي ديگر براي حل مسائل پيچيده نميتوان از مدلهاي ساده بهره گرفت اما هر چه مدل و به تبع آن روش يادگيري پيچيدهتر باشد، كارايي الگوريتم كاهش مييابد. بنابراين روشهاي متعددي براي بهبود كارايي الگوريتمهاي تخمين توزيع ارائه شده است.
هدف اين رساله بهبود كارايي ساخت مدل در الگوريتمهاي تخمين توزيع گسسته است به ترتيبي كه هزينه محاسباتي ساخت مدل كاهش يابد. رويكرد پيشنهادشده براي بهبود كارايي مبتني بر تعاملهاي زوجمتغيرها (وابستگيهاي دومتغيره) است. در ابتدا و پيش از شروع الگوريتم تكاملي ماتريس تعامل كه دربردارنده وابستگيهاي دومتغيره است، با روش كارآمدي محاسبه ميشود. از اطلاعات ماتريس به دو شيوه ميتوان استفاده كرد: 1- استخراج مستقيم گروههاي پيوندي و حل مسأله بهينهسازي به كمك اين گروهها، 2- ايجاد مدل مناسب بر مبناي اين اطلاعات. در اين رساله هر دو شيوه مدنظر قرار گرفتهاند. ابتدا الگوريتم جديدي براي خوشهبندي ماتريس تعامل ارائه شده است كه گروههاي پيوندي را با كارايي و دقت بالايي بدست ميآورد. سپس الگوريتم تكاملي بر مبناي اين گروهها، مسأله بهينهسازي را به سادگي حل ميكند. همچنين روشي براي يادگيري شبكه بيزي، به عنوان يك مدل پركاربرد در الگوريتمهاي تخمين توزيع، بر اساس ماتريس تعامل ارائه شده است. نتايج به دست آمده نشان ميدهد به كمك روش پيشنهادي، سرعت يادگيري شبكه بيزي در مسائل آزمايشي افزايش مييابد. با بهبود كارايي يادگيري شبكه بيزي، كارايي الگوريتم تخمين توزيع مبتني بر شبكه بيزي نيز بهتر ميشود.
واژههاي كليدي: الگوريتمهاي تخمين توزيع، ساخت مدل، بهبود كارايي، تعاملهاي دوتايي.