بررسي روند اجرايي الگوريتم ژنتيك در مساله كوله پشتي صفر و يك

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