سلام به همه بچههای علاقمند به کامپیوتر و برنامهنویسی و هوش مصنوعی. همانطور که میدونین روز به روز دنیای هوش مصنوعی داره وسیعتر میشه و به حوزه مختلف از علوم راه یافته است. ما تصمیم داریم هر هفته با یک مقاله در این حوزه، شمارو با رویداد های دنیای هوش مصنوعی آشنا کنیم و مهمتر اینکه ریاضیات این حوزه رو با ساده سازی به شما دانش آموزان عزیز کانونی توضیح بدیم. در نهایت بتونیم قدم به قدم به کد نویسی در محیط پایتون برای مسئله های جذاب هوش مصنوعی برسیم. پیشنهاد میکنم هر هفته مارو با یک مقاله در این حوزه دنبال کنید.
الگورتیم ژنتیک
آیا میدونستید که از طریق نظریه تکامل میتونید شبیه سازیهای بسیاری رو در کامپیوترتون انجام بدید؟ و از این طریق، به حل مسائلی بپردازید که از طریق روش های معمول نمیشه اونا رو حل کرد؟ جواب این سوال، موضوعی هست که امروز میخواهیم در موردش صحبت کنیم.
خب، بزارید با یک طرح مسئله، سوالمون رو شروع کنیم. فرض کنید که شما می خواید سفر چند روزهای به خارج به یه شهر دیگه داشته باشید؛ اما تمام چیزی که می تونید با خودتون به همراه داشته باشید، یک کیف دستی هست که بیشتر از 4 کیلوگرم وسیله نمی تونه حمل کنه. فرض کنید انتخابتون باید محدود به لپ تاب، فنجان قهوه، دفترچه، هدفون و بطری آّبتون باشه و ترکیبی از این وسیله ها انتخاب کنید طوری که وزن اونها از سه کیلوگرم بالاتر نره. وزن اقلامی که میخوایم با هم داشته باشیم رو میتونید در تصویر زیر ببینید:
خب شما چیکار میکنید؟ هر کسی میتونه بر حسب ضرورتی و اهدافی که از این سفر داره، انتخاب هایی داشته باشه. برای مثال اگه شما یک سفر کاری در پیش دارید، لپ تاب دفترچه حتما باید همراهتون باشه، یا اگه میخواید یک سفر تفریحی داشته باشید تو دل طبیعت و به دور از شلوغی ها، ممکنه فنجان قهوه، بطری آب و هدفون رو انتخاب کنید! در کل میشه گفت حل این مسئله چندان هم دشوار نیست و نیازی هم به روش های حل مسئله پیشرفته نداریم . اما حالا فرض کنید که ما برای حل این مسئله، از کامپیوترمون کمک بخوایم . چیزی که برای کامپیوتر قابل فهم هست، اینه که ما پنج آیتم داریم. خب اگه گفتید چند ترکیب مختلف برای این 5 آیتم میشه به وجود آورد؟؟ آفرین! 2 به توان پنچ ترکیب مختلف! که میشه 32 ترکیب مختلف از اقلام.. همچین کاری برای کامپیوتر با سرعت بالا 0.000003 ثانیه طول میکشه! حالا فرض کنید تعداد اقلامی که میتونیم انتخاب کنیم رو زیادتر باشه و بتونیم علاوه بر آقلام مثال قبلی، چیزهایی مثل دستمال کاغذی، جوراب، گوشی همراه و کلاه هم به لیستمون اضافه کنیم:
خب اینجاست که ما 10 ایتم داریم و اگه دوباره به درس آمار و احتمال رجوع کنیم، متوجه میشیم که دو به توان ده و یا 1024 ترکیب مختلف میشه از این آیتم ها بدست آورد. این کاری هم برای خود ما کمی سخت تر از مثال قبلی هست، و هم خود کامپیوتر هم حدود 0.000807 ثانیه طول میکشه تا این ترکیب ها رو به ما بده. یعنی حدود 269 برابر مدت زمانی که برای اقلام قبلی لازم بود! خب نظرتون چیه کمی تعداد اقلام رو بالا ببریم و ببینیم چه مدت برای کامپیوتر لازم هست تا ترکیب های مختلفی از اقلام رو برای ما به عنوان خروجی بده؟ نتایجی که بدست میاد خیلی جالب هست! فرض کنید تعداد اقلام 20 تا بشه! در این صورت تعداد ترکیب ها 1048576 عدد میشه و برای کامپیوتر 1 ثانیه زمان میبره تا این کار رو انجام بده. زمانی که تعداد اقلام رو 21 عددد کنیم، ترکیب و زمان مورد نیاز حدود دو برابر میشن! به جدول زیر دقت کنید :
پس مدت زمان اجرا شدن و پیدا کردن این ترکیب ها به صورت نمایی و به سرعت رشد میکنه. به طوری که اگه تعداد اقلامتون از یه تعداد خاصی بیشتر بشه، مدت زمان اجرای این برنامه انقدر طول میکشه که نه تنها سفرتون رو از دست میدید، بلکه حتی امکان داره کل منظومه شمسی عمرش به پایان برسه! برای مثال اگه فقط تعداد اقلاممون به 77 عدد برسه، باید کامیپوترمون حدود 5 میلیارد سال کار کنه تا در نهایت جواب مسئله رو به ما بده! خب پس راه حل چیه؟ قبل اینکه به سراغ راه حل های سریع وتر و بهتر بریم، شاید براتون جالب باشه که مسئله ای که بررسی کردیم، یکی از مسائل معروف و مهم در زمینه الگوریتم ها هست که به مسئله کوله پشتی و یا knapsack problem معروفه . این مسئله در حیطه های بسیاری مانند مدیریت مالی، ریاضیات کابردی و غیره وجود داره و از مسائلی نیست که با روش های مرسوم حل بشه و همونطور که قبلا بهتون گفتیم، به مسائل NP-hard معروف هست. این مسئله سالهاست که مورد بررسی قرار گرفته و تلاش های بسیاری صورت گرفته تا حل این مسئله با زمان کمتری صورت بگیره . این مسئله، یکی از مسائلی بوده که در به وجود اومدن علوم کامپیوتر و هوش مصنوعی نقش داشته!
خب پس در اینجا با یک مسئله ای مواجه هستیم که باید از طریق الگوریتم های بهینه سازی براش جواب پیدا کنیم. یکی از الگوریتم های مهم در این زمینه، الگوریتم ژنتیک نام داره. الگوریتم ژنتیک، در دسته الگوریتم های بهینه سازی تکاملی قرار داشته و از ((انتخاب طبیعی)) که در نظریه تکامل وجود داره، الگوبرداری میکنه تا ما رو به راه حل بهینه ای برای مشکلات NP hard برسونه. این الگوریتم نه تنها در پاسخ مثالی که گفتیم، بلکه در بسیاری از حیطه های تکنولوژی هم تاثیر مهمی داره و برای مثال در آنتنی که ناسا در سال 2006 برای پیدا کردن بهینه ترین تابش و تشعششی به وجود اومده بود، از این الگوریتم استفاده شده.
خب ببینیم این الگوریتم چطور عمل میکنه؟ اگه بخوایم مثال کوله پشتی رو با الگوریتم ژنتیک عمل کنیم، باید ابتدا مسئلمون رو تبدیل به کد های باینتری کنیم. پس اول میایم و به محتویات هر کیف احتمالی که یکی از جواب هامون میتونه باشه، عدد صفر و یک اختصاص میدیم. برای مثال در شکل زیر، به جای هر آیتمی که در کوله پشتی موجود هست عدد 1 و به جای هر آیتمی که در کوله پشتی انتخابی فرضی موجود نیست، عدد صفر رو اختصاص میدیم . خواهیم داشت:
پس برای هر کوله پشتی میشه گفت یک کد باینری به دست میاد . اما کد باینری چیه؟ کد باینری مفهومی هست که در علوم کامپیوتر و برنامه نویسی کاربرد حیاتی داره. به این صورت که این کدها فقط از دو عدد صفر و یک تشکیل شده و کامپیوتر فقط این کدها رو تشخیص میده. برای مثال برای کامپیوتر اعداد دیگه معنی نداره، حتی حروف و کلمات هم معنی نداره و تنها این کدها هستند که معنی و تعابیری رو به کامپیوتر ارائه میدن.
خب در ابتدا برای هر ترکیب ممکن یک کد در نظر گرفته میشه. به این روند generation ویا تولید مثل گفته میشه! در حالت ابتدایی ما با بی نهایت کد طرف هستیم و عملا هنوز گامی برای حل مسئله برنداشتیم. سپس به سراغ انتخاب طبیعی یا natural selection میریم. در این انتخاب، وزن اقلام موجود در هر کیف حساب میشه و اگه از حد ممکن بالاتر باشه، مقدار باینری صفر برای اون کوله پشتی در نظر گرفته میشه. چرا به این روند میگیم انتخاب طبیعی؟ چون در طبیعت هم طبق نظریه تکاملی داروین، موجوداتی که به اصطلاح سازگاری بیشتری با محیط داشته باشند، در طبیعت به حیات خود ادامه میدن اما موجوداتی که این سازگاری رو نداشته باشن، از چرخه تولید مثل خارج میشن! اینجا هم کیف کوله پشتی که وزنش از حد تعیین شده بیشتر باشه، از چرخه خارج میشه! خب در تصویر زیر، تعدادی از کوله پشتی هایی که میتونه جواب محتمل ما باشند، به عنوان نسل اول کوله پشتی ها نشون داده شدن . در این تصویری میبینیم که کوله پشتی هایی که مقدارشون از حد مجاز بیشتر بوده، کنار گذاشته شدن و بهشون عدد صفر اختصاص داده شده.
اما هنوز پاسخ های زیادی برای مسئله ما وجود داره و هنوز به اون جواب بهینه نرسیدیم . برای رسیدن به پاسخ بهینه، باید نسل بعدی پاسخ های ممکن رو به وجود بیاریم! برای این کار باید والدین نسل بعدی مشخص بشه! برای دیدن فرایند انجام این کار و ادامه فرایند الگوریتم ژنتیک، حتما به مقاله هفته آیندمون سر بزنید تا در اون مقاله به ادامه این موضوع بپردازیم!
منابع
https://www.youtube.com/watch?v=uQj5UNhCPuo
https://en.wikipedia.org/wiki/Evolved_antenna
https://en.wikipedia.org/wiki/Knapsack_problem
کلیدواژهها
دوستان عزیزم؛ برای ارتباط با برترها و رزرو پشتیبان ویژه پیج کانون برترها را دنبال کنید.
همچنین میتوانید با شماره 0218451 داخلی 3123 تماس بگیرید.
