بررسی برخی از تكنيك های حل مسئله كوله پشتی

نوع فایل: word
قابل ویرایش 89 صفحه

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

مقدمه:
هميشه در برخورد با مسائل مختلف براي حل آنها شروع به طرح روشهاي مختلف كرده ايم . از ميان راه حلهاي طرح شده اكثرا بهترين و قابل اطمينان ترين پاسخها را الگوريتم هايي توليد مي كردند كه براساس قوانين رياضي پي ريزي شده بودند . امروزه با توجه به پيشرفتهاي حاصله محدوده ي مطالعات بزرگتر و جزئيات پيچيده تر شده اند يا به عبارتي خواستار سرعت و دقت زياد و در عين حال محدوده ي بزرگتر هستيم . طبيعي است كه استفاده از قوانين محض رياضي در حل چنين مسائل نياز به محاسبات پيچيده اي دارد كه شايد در بعضي موارد مقرون به صرفه نباشد . از اين رو بدنبال روشهاي ديگري هستيم كه بتوانيم اين نياز را مرتفع سازيم با نگاهي به اطرافمان متوجه مي شويم كه در فرايندهاي طبيعي مسايل قابل توجهي وجود دارد كه شايد شبيه سازي فرايندها بتوانند تاثير شايان ذكري را به همراه داشته باشد .
فهرست مطالب:
چكيده مطالب
فصل اول : مقدمه
مقدمه
-1بهينه سازي
1-2پيدا كردن بهترين راه حل
1-3تعريف مسئله كوله پشتي
1-3-1 مسئله كوله پشتي كسري
1-3-2 مسئله كوله پشتي صفر و يك
1-3-3 مسئله كوله پشتي چند بعدي
فصل دوم : حل مسئله كوله پشتي با استفاده از برنامه نويسي پويا ، روش حريصانه ، عقبگرد و شاخه و حد
2-1روش حريصانه در مقابل برنامه نويسي پويا : مسئله كوله پشتي
2-1-1روش حريصانه در حل مسئله كوله پشتي صفرويك
2-1-2يك روش حريصانه براي مسئله كوله پشتي كسري
2-1-3روش برنامه نويسي پويا براي مسئله كوله پشتي صفرويك
2-1-4شكل بهتر الگوريتم برنامه نويسي پويا براي مسئله كوله پشتي صفرويك
2-2حل مسئله كوله پشتي با استفاده از روش عقبگرد
2-2-1يك الگوريتم عقبگرد براي مسئله كوله پشتي صفرويك
2-2-2مقايسه الگوريتم برنامه نويسي پويا و الگوريتم عقبگرد براي مسئله كوله پشتي صفرويك
2-3راهبرد شاخه و حد
2-3-1تشريح روش شاخه و حد با مسئله كوله پشتي صفرويك.
2-3-1-1جست وجوي عرضي با هرس كردن شاخه و حد
2-3-1-2 بهترين جست وجو با هرس كردن شاخه و حد
فصل سوم : تكنيك حل مسئله كوله پشتي با استفاده از الگوريتم ژنتيك
3-1 الگوريتم ژنتيك
3-1-1 مفاهيم اوليه ژنتيك
3-1-2 ايده ي اصلي
3-1-3 الگوريتم ژنتيك (Genetic Algorithm_ GA) چيست؟
3-1-4 ويژگي هاي الگوريتم ژنتيك
3-1-5 اصول اساسي الگوريتم ژنتيك
3-1-5-1 تعيين عدد برازندگي براي هر كروموزوم (دنباله ها)
3-1-5-2 مكانيزم انتخاب كروموزوم ها
3-1-5-3 عملگرهاي ژنتيكي كه بر روي هر كروموزوم اعمال مي شود
3-1-6 روند كلي اجراي الگوريتم ژنتيك
3-1-7 روشهاي نمايش يا كد كردن مقادير
3-1-7-1 روش كدگذاري مبناي دو
3-1-7-2 روش كدگذاري جايگشتي
3-1-7-3 روش كدگذاري مقدار
3-1-7-4 روش كدگذاري درختي
3-1-8 شبه كد
3-1-9 روشهاي انتخاب در الگوريتم ژنتيك
3-1-9-1 انتخاب Elitist
3-1-9-2 انتخاب Roulette
3-1-9-3 انتخاب Scaling
3-1-9-4 انتخاب Tournament
3-2 حل مسئله كوله پشتي با استفاده از الگوريتم ژنتيك
3-2-1 رويكرد نمايش دودويي
3-2-1-1 متد جريمه
3-2-1-2 متد رمز گشايي
3-2-2 رويكرد نمايش ترتيبي
3-2-3 رويكرد نمايش با طول متغيير
فصل چهارم : تكنيك حل مسئله كوله پشتي با استفاده از آتوماتاي يادگيرنده
4-1 آتوماتاي يادگيرنده
4-1-1 آتوماتاي يادگير با ساختار ثابت (FSLA
4-1-1-1 آتوماتا با دو حالت (L2,2
4-1-1-2 آتوماتاي Tsetline (L2N,2)
4-1-1-3 آتوماتاي G2N
4-1-1-4 آتوماتاي Krinsky
4-1-1-5 آتوماتاي Krylov
4-1-2 آتوماتاي يادگير با ساختار متغيير
4-1-3 آتوماتاي يادگير توزيع شده (DLA)
4-2 حل مسئله كوله پشتي با استفاده از آتوماتاي يادگيرنده.
4-2-1 نتايج شبيه سازي هاي انجام شده
ديكشنري
مراجع و منابع

منابع و مأخذ:
[1] Fraser, Alex S. (1957). "Simulation of Genetic Systems by Automatic Digital Computers. I. Introduction". Australian Journal of Biological Sciences 10: 484–491.
[2] Goldberg, David E (1989), Genetic Algorithms in Search, Optimization and Machine Learning, Kluwer Academic Publishers, Boston, MA.
[3] Goldberg, David E (2002), The Design of Innovation: Lessons from and for Competent Genetic Algorithms, Addison-Wesley, Reading, MA.
[4] Fogel, David B (2006), Evolutionary Computation: Toward a New Philosophy of Machine Intelligence, IEEE Press, Piscataway, NJ. Third Edition
[5] Schmitt, Lothar M (2004), Theory of Genetic Algorithms II: models for genetic operators over the string-tensor representation of populations and convergence to global optima for arbitrary fitness function under scaling, Theoretical Computer Science (310), pp. 181-231
[6] Sutton, R. S., and Barto, A. G., Reinforcement learning: An introduction. MA: MIT Press, Cambridge, 1998.
[7] Thathachar, M. A. L., Sastry, P. S., Varieties of learning automata: An overview. IEEE Transactions on Systems, Man and Cybernetics – Part B: Cybernetics, 32, 6, 2002.
[8] Alaya, I., Solnon, Ch., and Ghedira, K., Ant algorithm for the multidimensional knapsack problem. Dans Proceedings of Iinternational Conference on Bioinspired Methods and their Applications, Slovenia, 2004.
[8] Beigy, H., Meybodi, M. R., "Utilizing Distributed Learning Automata to Solve Stochastic Shortest Path Problem" International Journal of Uncertainty, Fuzziness and Knowledge-based Systems, vol. 14, pp. 591-615, 2006.
[9] Beigy, H.,Meybodi, M. R., "A New Distributed Learning Automata for Solving Stochastic Shortest Path Problem," in International Joint Conference on Information Science, Durham, USA, 2002, pp. 339-343.
[10] H. Beigy, “Intelligent Channel Assignment in Cellular Networks: A Learning Automata Approach”, PhD Thesis, Computer Engineering Department, Amir Kabir University of Technology, Tehran, Iran, 2006.
[11] M. A. L. Thathachar and B. R. Harita, "Learning Automata with Changing Number of Actions", IEEE Transactions on Systems, Man, and Cybernetics, vol. SMG17, pp. 1095-1100, Nov. 1987.

---