نوع فایل: word
قابل ویرایش 91 صفحه
چکیده:
در حل مسائل همیشه دنبال راه حل هایی بوده ایم که بتوانند کارایی بهتری داشته باشد . یعنی راه حل بتواند در زمان کمتر پاسخ مناسب تری ارائه دهد . علت بیان کلمه ی مناسب تر اینست که در حل بعضی مسائل نیاز به پاسخ دقیق داریم که تعداد این مسائل نسبت به مسائلی که در آنها نیاز به مجموعه ی جوابها که می توان گفت پاسخ بهینه است ، کمتر است .
وقتی می خواهیم روی مجموعه ای بررسی انجام دهیم یا در سطوح بالای الگوریتم با مسائلی کار می کنیم که یک پاسخ قطعی ندارند ، برای همین همانند مسائل ریاضی نمی توان یک راه حل مطلق ارائه کرد . در اینگونه مسائل روبه مسائل بهینه سازی می آوریم ، تا بتوانیم راه حل مناسب و بهینه ارائه کنیم .
با نگاهی به طبیعت اطرافمان متوجه می شویم که روشهای استفاده شده در طبیعت بهینه ترین نوع راه حل هاست . بنابراین اگر از سیستم طبیعت بتوانیم در حل مسائل مشابه استفاده کنیم ، بهینه ترین راه حل را ارائه داده ایم .
الگوریتم ژنتیک با یک پشتوانه ی قوی که از ژنتیک طبیعی بدن تقلید شده اند می توانند در حل مسائلی که مجموعه هدف ما ، بسیار بزرگ است و همچنین حالت پراکندگی دارد ، بسیار مفید باشد . فرض کنید که در یک مجموعه هدف که اعضای آن را پستی و بلندی های یک رشته کوه تشکیل داده است می خواهیم نقطه مینیمم را بیابیم . در اینحالت به علت بزرگی مجموعه هدف و همچنین کم بودن سطح اختلاف بین مجموعه های متناظر و زیاد بودن تعداد این مجموعه ها ، اگر بخواهیم این عملیات را با روشهای رایج انجام دهیم ، مثلا بخواهیم بصورت ترتیبی آنها را مورد بررسی قرار دهیم ، ممکن است هزینه این کار آنقدر زیاد شود که از انجام آن منصرف شویم .
طبق نظریه ی تکاملی داروین و یا همان اصل بقا ء اصلح در بین ژنهای یک کروموزوم ، ژنی که برتری بیشتری نسبت به بقیه داشته باشد ، در چرخه تولید مثل حفظ شده و ژنی که ضعیف باشد از بین می رود . در اینحالت نسلهای جدید رفته رفته بهبود یافته و ایرادهای نسل های قبلی ، در نسل جدید دیده نمی شود .
در حل مسئله فوق بوسیله الگوریتم ژنتیک ، برتری ژن ، مینیمم بودن ارتفاع است و به علت اینکه در این مسئله ، مجموعه هدف بسیار بزرگ است و مطمئنا ، مقادیر نزدیک بهم است ، مطمئن هستیم که فرزند تولید شده در این مجموعه قرار دارد و همچنین طبق نظریه تکاملی داروین ، این مقدار جدید حتما به جواب نزدیکتر است و به احتمال زیاد مقادیر تولید شده در چرخه های تولید مثل در مجموعه جواب نخواهد بود و بین کل مجموعه پراکنده خواهد شد پس عملا داریم نقاطی از قسمتهای مختلف را انتخاب و با هم مقایسه می کنیم .
این الگوریتم ها در حل مسئله با در نظر داشتن اصل بقا اصلح و انتخاب تصادفی جهت دار به این صورت عمل می کنند که بجای خود پارامترها از شکل کد بندی شده مناسبی استفاده می کنند و همچنین همیشه برای یافتن پاسخ بهینه عملیات خود را روی مجموعه ای از فضای جستجو اعمال می کنند . یک عامل دیگر که به الگوریتم ژنتیک برتری می دهد و ناشی از سیستم ژنتیک است ، استفاده از قوانین احتمال بجای قوانین ریاضی است .
در بخش بعدی نیز یک الگوریتم تکرارشونده مبتنی بر اتوماتاهای یادگیر برای حل مساله کوله پشتی مطرح می شود. که در این الگوریتم، مساله کوله پشتی با یک گراف کامل مدل می شود که هر گره از گراف متناظر با یکی از کالاهاست. هر گره از گراف به یک اتوماتای یادگیر مجهز است که انتخاب یا عدم انتخاب کالای متناظر با گره برای قرار گرفتن در کوله پشتی را مشخص می کند. نتایج شبیه سازی ها نشان داده است که این الگوریتم در مقایسه با الگوریتم های موجود از کارایی بالاتری برخوردار است. نتایج شبیه سازی ها همچنین نشان داده است که این الگوریتم برای مسائل با اندازهای بزرگ دارای سرعت همگرایی بالایی می باشد.
مقدمه:
همیشه در برخورد با مسائل مختلف برای حل آنها شروع به طرح روشهای مختلف کرده ایم . از میان راه حلهای طرح شده اکثرا بهترین و قابل اطمینان ترین پاسخها را الگوریتم هایی تولید می کردند که براساس قوانین ریاضی پی ریزی شده بودند . امروزه با توجه به پیشرفتهای حاصله محدوده ی مطالعات بزرگتر و جزئیات پیچیده تر شده اند یا به عبارتی خواستار سرعت و دقت زیاد و در عین حال محدوده ی بزرگتر هستیم . طبیعی است که استفاده از قوانین محض ریاضی در حل چنین مسائل نیاز به محاسبات پیچیده ای دارد که شاید در بعضی موارد مقرون به صرفه نباشد . از این رو بدنبال روشهای دیگری هستیم که بتوانیم این نیاز را مرتفع سازیم با نگاهی به اطرافمان متوجه می شویم که در فرایندهای طبیعی مسایل قابل توجهی وجود دارد که شاید شبیه سازی فرایندها بتوانند تاثیر شایان ذکری را به همراه داشته باشد .
فهرست مطالب:
چکیده مطالب
فصل اول : مقدمه
مقدمه
1-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 روش کدگذاری مبنای دو (Binary Encoding)
3-1-7-2 روش کدگذاری جایگشتی (Permutation Encoding)
3-1-7-3 روش کدگذاری مقدار (Value Encoding)
3-1-7-4 روش کدگذاری درختی (Tree Encoding)
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,2
4-1-1-4 آتوماتای Krinsky
4-1-1-5 آتوماتای Krylov
4-1-2 آتوماتای یادگیر با ساختار متغییر (VSLA)
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.
پروژه بررسی برخی از تکنیک های حل مسئله کوله پشتی. doc
