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

در اين مقاله ابتدا نوعي از بهينه‌سازي جايگشت معرفي شده است. در اين نوع بهينه‌سازي فرض گرديده كه تابع هزينه، داراي يك تابع توزيع احتمال ناشناخته است. اين فرض باعث مي‌شود كه پيچيدگي حل مسئله يافتن جايگشت بهينه كه به دليل بزرگي ذاتي فضاي جواب‌ها پيچيده است، تشديد شود. يك الگوريتم مبتني بر آتاماتاي يادگير توزيع‌شده براي حل مسئله از طريق انجام توأمان جستجو در فضاي جواب‌هاي جايگشت و نمونه‌گيري از مقادير تصادفي ارائه مي‌دهيم. ضمن بررسي رياضي رفتار الگوريتم جديد پيشنهادي، نشان مي‌دهيم كه با انتخاب مقادير مناسب پارامترهاي الگوريتم يادگير، اين روش جديد مي‌تواند جواب بهينه را با احتمالي به اندازه دلخواه نزديك به ۱۰۰% و از طريق هدفمندكردن جستجو به كمك آتاماتاي يادگير توزيع‌شده پيدا كند. نتيجه اتخاذ اين سياست، كاهش تعداد نمونه‌گيري‌ها در روش جديد در مقايسه با روش‌هاي مبتني بر نمونه‌گيري استاندارد است. در ادامه، مسئله يافتن درخت پوشاي كمينه در گراف تصادفي به عنوان يك مسئله بهينه‌سازي جايگشت تصادفي بررسي گرديده و راه حل ارائه‌شده مبتني بر آتاماتاي يادگير براي حل آن به كار گرفته شده است.