چكيده
مسئله پوشش مجموعه يکي از مسائل NP-Hard است که در کاربردهاي مختلفي مانند شبکه¬هاي ارتباطي مورد استفاده قرار مي¬گيرد. هدف از پوشش مجموعه، يافتن يک زيرمجموعه¬ به گونه ايست که اجتماع اعضاي اين زير مجموعه، کل مجموعه را پوشش دهد. با توجه به آنکه براي مسئله پوشش مجموعه نمي¬توان جواب دقيقي در زمان چندجمله¬اي پيدا کرد، بنابراين روش¬هاي هيوريستيکي مختلفي نيز براي حل آن ارائه شده است. در اين مقاله يک الگوريتم مبتني بر اتوماتاهاي يادگير براي حل مسئله پوشش مجموعه پيشنهاد شده است. در الگوريتم پيشنهادي، هر يک از رئوس گراف به يک اتوماتاي يادگير مجهز مي¬شوند که داراي دو عمل حضور يا عدم حضور راس متناظر در مجموعه پوشش است. با توجه به همکاري ميان اتوماتاهاي يادگير، در هر مرحله بردار احتمال اعمال اتوماتاهاي يادگير به¬روز مي¬شود و اين روند به طور تکراري ادامه مي-يابد تا آنکه در خاتمه¬ي الگوريتم، مجموعه پوشش نزديک به بهينه بدست ¬آيد. جهت ارزيابي الگوريتم پيشنهادي مبتني بر اتوماتاهاي يادگير، از دادگان آزمايشي معروف DIMACS استفاده شده است. نتايج شبيه¬سازي در مقايسه با ساير روش¬هاي متداول براي آزمايشات مختلف حاکي از موفقیت الگوريتم پیشنهادی با بیش از 40 درصد بهبود می باشد.
كلمات كليدي: اتوماتاي يادگير، اتوماتاي يادگير توزيع شده، مسائل سخت، مجموعه پوشش، مجموعه پوشش راسي.

اضافه کردن نظر