سلام به همه بچههای علاقمند به کامپیوتر و برنامهنویسی و هوش مصنوعی. همانطور که میدونین روز به روز دنیای هوش مصنوعی داره وسیعتر میشه و به حوزه مختلف از علوم راه یافته است. ما تصمیم داریم هر هفته با یک مقاله در این حوزه، شمارو با رویداد های دنیای هوش مصنوعی آشنا کنیم و مهمتر اینکه ریاضیات این حوزه رو با ساده سازی به شما دانش آموزان عزیز کانونی توضیح بدیم. در نهایت بتونیم قدم به قدم به کد نویسی در محیط پایتون برای مسئله های جذاب هوش مصنوعی برسیم. پیشنهاد میکنم هر هفته مارو با یک مقاله در این حوزه دنبال کنید.
الگوریتم ژنتیک – بخش دوم
سلام خدمت همه دوستان علاقمند به دنیای جذاب هوش مصنوعی یادگیری ماشین . در جلسه قبل، با الگوریتمی آشنا شدیم که اساس اون بر پایه نظریه تکاملی بوده و اسم این الگوریتم رو گذاشتیم الگوریتم ژنتیک . در این جلسه، به ادامه توضیح در مورد این الگوریتم می پردازیم .
گفتیم که در الگوریتم ژنتیک، از قوانین حاکم بر نظریه تکامل استفاده می کنیم . به این ترتیب که برای حل مسائل NP-hard ، ابتدا نسل صفر داده های موجود رو تشکیل داده و سپس با استفاده از نظریه انتخاب طبیعی و یا Natural selection ، والدین نسل بعدی رو برای تشکیل generation و یا نسل بعدی انتخاب میکنیم و به این ترتیب، به سمت انتخاب بهینه ترین جواب ممکن میریم. این توضیح شاید کمی در ابتدا گیج کننده به نظر بیاد؛ برای همین ما سعی کردیم این الگوریتم رو در قالب حل یک مسئله معروف بهتون توضیح بدیم و از این رو، مسئله کوله پشتی و یا Knapsack problem رو مطرح کردیم و قسمتی از این مسئله رو نیز در مقاله هفته قبل با الگوریتم ژنتیک حل کردیم. پس حتما ضروری هست که قبل خوندن این مقاله، مقاله هفته قبلمون رو در مورد الگوریتم ژنتیک بخونید و بعد سراغ این مقاله بیاید.
خب ، پس در مسئله کوله پشتی، به دنبال این بودیم که بهینه ترین ترکیب رو از بین اقلامی انتخاب کرده و بار کوله پشتیمون کنیم و بریم سفر! اما فهمیدیم حل این مسئله به ظاهر ساده، خیلی هم آسون نیست، مخصوصا اگه تعداد اقلامی که میتونیم بین اونها انتخاب داشته باشیم، از یه حدی بالاتر بره، چک کردن تمام حالات های ممکن و انتخاب بهینه ترین انتخاب اونم توسط زبان برنامه نویسی، چند میلیارد سال طول میکشه! پس برای حل این مسئله، از الگوریتم ژنتیک کمک خواستیم و به کمک این الگوریتم، نسل صفر کوله پشتی هامون رو انتخاب کردیم . حالا دنبال والدین نسل بعدی کوله پشتی ها (که به نوعی جواب های محتمل ما برای مسئله هستند) هستیم. برای انتخاب والدین، باید مناسب ترین گزینه ها رو انتخاب کنیم و یا به اصطلاح Fit ترین اونها به عنوان والدین نسل بعدی انتخاب میشن. انتخاب طبیعی در نظریه تکامل هم اینطوری هست. به طوری که بر طبق این نظریه، والدین نسل جدید معمولا مناسب ترین و fitness ترین موجودات در بین موجودات دیگه هستند . اینجا باید یه نکته ای رو بهتون بگم و اونم اینه که fit ترین موجود، معمولا به معنای بزرگترین و یا قوی ترین موجود نیست، بلکه موجودی هست که سازگاری اون با شرایط ممکن بالاتر باشه. برای مثال، در دوره زمانی انقراض دایناسورها، پستانداران کوچک تونستند به زندگیشون ادامه بدند و والدین نسل بعدی موجودات زمین باشند، اما بسیاری از دایناسورهای عظیم الجثه و قدرتمند منقرض شدند!
خب، پس برای انتخاب والدین نسل بعدی کوله پشتی هامون هم باید Fit ترین ها رو انتخاب کنیم. برای این منظور یک کوله پشتی با وزن بالا و یک کوله پشتی با وزن پایین انتخاب میکنیم .
این دو کوله پشتی به عنوان والدین نسل بعدی انتخاب شدند . الان وقت اینه که والدین نسل جدید، با هم تولید مثل داشته باشند . اما چطوری؟
اگه خاطرتون باشه، ما برای هر کوله پشتی بر حسب محتوایاتش، یه کد باینری اختصاص داده بودیم . این کدها، مثل DNA برای هر کوله پشتی میمونه و هنگام تولید مثل برای نسل بعدی، این کدها اثرش رو روی نسل بعدی میگذاره. دقیقا مثل روند تولید مثل در موجودات طبیعی! خب برای اینکار، چند رقم از این کدهای باینری والدین با همدیگه ترکیب میشن و کدهای جدیدی رو به وجود میارن . برای مثال، 4 رقم آخر کدهای والدین انتخاب شده برای مثالمون رو به ترتیب شکل زیر انتخاب می کنیم :
سپس این کدها رو با همدیگه سویچ میکنیم تا ترکیب جدیدی به وجود بیاد. این ترکیب های جدید، ما رو به فرزندان نسل جدید میرسونه که fit تر و مناسب تر از نسل قبلی هستند . برای مثال :
همونطور که میبیند، نسل جدید کوله پشتی ها با وزن 1050 گرم و 670 گرم، دو کوله پشتی با وزن 1075 و 645 بود . به این فرایند در اصطلاح انگلیسی Single point crossover function می گویند.
این روند برای هر دو کوله پشتی در نسل صفر اتفاق میوفته، و نسل جدیدی رو به وجود میاره که خیلی فیت تر و مناسب تر هستند . البته باید توجه داشت که از اونجایی که این روند به صورت random صورت میگیره و ماشین کوله پشتی ها رو به صورت اتفاقی انتخاب میکنه، در نتیجه احتمالش هست که در برخی از مواقع، نسل بعدی از نسل کنونی وضعیت نامناسب تری داشته باشه! از اینرو، در الگوریتم ژنتیک، در هر نسل فیت ترین داده های ممکن انتخاب میشن و به نسل بعدی بدون تغییر خاصی کپی میشن! این روند باعث میشه که پس از چندین بار تکرار و ایجاد نسل های جدید، نسلی از پاسخ ها بدست بیاد که مناسب ترین شرایط رو برای اون مسئله دارا هستند.
در مسئله کوله پشتی هم، همین اتفاق میوفته . به طوری که پس از شکل گیری نسل بعدی، پاسخ های فیت برتر به نسل بعدی منتقل شده و پاسخ های دیگه دوباره دچار Single point crossover می شن. این روند انقدر ادامه پیدا میکنه تا ماشین، کوله پشتی هایی رو به عنوان خروجی به ما بده که به راحتی بتونیم با انتخابش، هم محدودیت وزنی رو رعایت کرده باشیم و هم، مناسب ترین ترکیب رو بدست بیاریم . این روش حدود 60 برابر از روش brutal force سریع تر هست . brutal force همون روشی بود که در مقاله هفته قبل برای حل این مسئله به کار گرفتیم و تو اون ، تمام شرایط و تمام حالات مختلف رو بررسی کردیم و دیدیم که حتی در برخی موارد ممکنه عمر اجرا شدن برنامه از عمر کل کهکشان راه شیری بالاتر بره!
الگوریتم ژنتیک محدودیت هایی هم داره. یکی از این محدودیت ها، محدودیت زمانی هستش. چون با وجود اینکه این الگوریتم حدود 60 برابر از روش حل ساده مسائل سرعت داره، بازم برای حل برخی مسائل به اندازه کافی سریع نیست!! چون برخی از مسائل زمانی که نیاز دارند از چند صد سال هم بالاتره، واسه همین در این مقیاس ها 60 برابر سریع بودن هم مشکلمون رو حل نمیکنه . برای همین، الگوریتم ژنتیک در طول سالها پیشرفت کرده و روش های جدیدتری در این الگوریتم به وجود اومده. اما در همه اونها، از انتخاب طبیعی و نظریه تکامل الگوبرداری شده و به همین علت به این دسته از الگوریتم ها Genetic algorithm گفته میشه.
از کاربردهای دیگه این الگوریتم، اینه که میشه شبیه سازی های از روند تکامل موجودات زنده هم بدست آورد . برای همین، این الگوریتم به کمک علوم زیست شناسی هم اومده و به دانشمندان این حیطه این امکان رو میده که با دقت بسیاری به مطالعه روند تکامل طبیعی بپردازن .
خب، در این دو هفته ما تونستیم یه آشنایی اولیه با الگوریتم ژنتیک داشته باشیم. گفتیم که این الگوریتم، یکی از الگوریتم های تکاملی هست که برای مسائل بهینه سازی کاربرد بسیاری داره. در هفته های آینده، قصد داریم شما رو با دیگر الگوریتم های بهینه سازی و تکاملی آشنا کنیم . پس با ما همراه باشید ..
منابع
https://www.youtube.com/watch?v=uQj5UNhCPuo
https://www.javatpoint.com/genetic-algorithm-in-machine-learning
کلیدواژه ها
دوستان عزیزم؛ برای ارتباط با برترها و رزرو پشتیبان ویژه پیج کانون برترها را دنبال کنید.
همچنین میتوانید با شماره 0218451 داخلی 3123 تماس بگیرید.
