جستجوی محلی یا همان Local Search یکی از سادهترین الگوریتمهای هوشمصنوعی در حوزهی بهینهسازی است. در درس فعلی میخواهیم یک بهینهسازیِ ارائه شده برای این الگوریتم به اسم جستجوی محلیِ تکراری را مورد بررسی قرار دهیم تا بتوانیم یکی از نقاط ضعف الگوریتم جستجوی محلی را حذف کنیم.
ادامه خواندن “جستجوی محلی تکراری (Iterated Local Search) در بهینهسازی”بهینهسازی سراسری (Global Optimization) و تفاوت آن با کاهش گرادیان (Gradient Descent)
از آنجایی که امکان دارد برخی از دانشجویان کمی در درک مفاهیمِ بهینهسازی و کارایی آنها دچار سردرگمی شده باشند، در این درس میخواهیم کمی به این مباحث بپردازیم تا مدل ذهنی دانشجویان عزیز کمی بهتر با مفاهیم اصلی و بنیادین این حوزه آشنا شود.
ادامه خواندن “بهینهسازی سراسری (Global Optimization) و تفاوت آن با کاهش گرادیان (Gradient Descent)”الگوریتمهای چند شروعی (Multi Start) در مسائل بهینهسازی
با مطالعهی دورس گذشته از دورهی جاری، مشاهده کردیم که الگوریتمهای فراابتکاری برای این ساخته شدهاند که بدون جستجوی همهی حالات، بتوانند به یک حالت بهینه دست پیدا کنند.
ادامه خواندن “الگوریتمهای چند شروعی (Multi Start) در مسائل بهینهسازی”الگوریتم ممتیک (Memetic) بر اساس الگوهای رفتاری
الگوریتم ممتیک یا همان Memetic Algorithm را نمیتوان یک الگوریتم ثابث فرض کنید. در واقع الگوریتمهای ممتیک را میتوان از دستهی الگوریتمها داسنت که به نوعی بهبود یافتهی الگوریتم ژنتیک (Genetic Algorithm) هستند. در این درس ما به یکی از معروفترین این الگوریتمها اشاره میکنیم. این الگوریتم در واقع ترکیبی از الگوریتم ژنتیک و الگوریتم جستجوی تپهنوردی است که در دروس گذشتهی دورهی جاری به این دو الگوریتم پرداختیم.
ادامه خواندن “الگوریتم ممتیک (Memetic) بر اساس الگوهای رفتاری”جستجوی محلی (Local Search) و الگوریتم تپهنوردی (Hill Climbing)
این درس به نوعی تکرار درس بهینه محلی و بهینه سراسری است و برای تاکید و درک بهتر با عنوانی دیگر و توضیحاتی دیگر در اینجا تکرار شده است. شاید نتوان این دسته از الگوریتمها را به صورت جداگانه، یک الگوریتم فراابتکاری (Meta heuristic) قوی دانست. اما شناخت این الگوریتمها میتواند به وسعت دید در درکِ بحثِ بهینهسازی کمک کرده و پایهی الگوریتمهای بعدی و پیشرفتهتر باشد.
ادامه خواندن “جستجوی محلی (Local Search) و الگوریتم تپهنوردی (Hill Climbing)”الگوریتم بهینهسازی کلونی مورچگان (Ant Colony Optimization)
مورچهها در یک حرکتِ جمعی قادر هستند مسیرِ بهینه از کلونیِ خود به سمت غذا را به دست آورند. آنها بدون داشتن بینایی میتوانند با استفاده از قدرتِ اجتماعِ خود این مسیر را پیدا کنند. دانشمندان با تحقیق و بررسیِ نحوهی کار مورچهها، توانستند الگوریتمی را شناسایی کنند که میتواند با تقریب بسیاری خوبی، چیزی نزدیک به بهینهی سراسری را در یک مسئلهی بهینهسازی بیابد.
ادامه خواندن “الگوریتم بهینهسازی کلونی مورچگان (Ant Colony Optimization)”الگوریتم جستجوی ممنوعه (Tabu Search)
اگر درسهای دورهی جاری (الگوریتمهای فراابتکاری) را خوانده باشید، متوجه شدهاید که این الگوریتمها به دنبال پیدا کردن راه حل در یک زمان معقول هستند. یعنی به جای اینکه تمامی مسئله را جستجو کنند، به دنبال جستجو در قسمتهایی از مسئله میگردند تا بتوانند به یک بهینهی سراسری یا یک بهینهی محلیِ خوب دست پیدا کنند. در درسِ بهینهی سراسری و بهینهی محلی، گفتیم که هدفِ الگوریتم فرار کردن از بهینهی محلی و رسیدن به بهینهی سراسری یا چیزی نزدیک به آن است. در همین راستا در این درس میخواهیم یکی دیگر از الگوریتمهای فراابتکاری به نام جستجوی ممنوعه یا همان Tabu Search را با یکدیگر مرور کنیم.
ادامه خواندن “الگوریتم جستجوی ممنوعه (Tabu Search)”شبیه سازی تبرید (Simulated Annealing) و الگوریتم متروپولیس
یک بچه بیشتر به دنبال کنجکاوی و جستجو است و یک آدمِ مسن و پیر، بیشتر به دنبالِ استفاده از تجربیات گذشتهی خود هست. الگوریتمِ شبیهسازی تبرید نیز دقیقاً از همین روند استفاده میکند و با این کار به دنبالِ یافتن حالت بهینه در مسئله میگردد. الگوریتم وقتی شروع میکند بچه است و بیشتر جستجو میکند، سپس آرام آرام مسنتر میشود و کمتر تجربهی جدید کرده و بیشتر به تجربههای قبلیِ خود پابند است.
ادامه خواندن “شبیه سازی تبرید (Simulated Annealing) و الگوریتم متروپولیس”الگوریتم ژنتیک (Genetic)
طبق نظریهی داروین، نسل موجوداتِ کرهی خاکی، روز به روز بهتر میشود. به این صورت که موجودِ بهتر، با تکثیر و فرآیندهای مختلف روز به روز بهتر میشود و موجوداتِ ضعیفتر از بین میروند. در واقع قانونِ بقای اصلح موجب بهینهسازیِ نسلِ موجودات بر روی کرهی خاکی میشود. این کار به وسیلهی ژنهای موجود در موجودات انجام شده و دانشمندانِ علومکامپیوتر و هوشمصنوعی با الهام از این نظریه، به الگوریتمی به نام الگوریتمِ ژنتیک یا همان Genetic Algorithm رسیدهاند.
ادامه خواندن “الگوریتم ژنتیک (Genetic)”ابعاد (Dimension) مسئله و فضای حالت در الگوریتمهای بهینهسازی
دانشمندان و مهندسانِ تحقیقاتی، معمولاً سعی دارند تا با زبانی مشترک با یکدیگر صحبت کنند. آنها در تلاشند تا با توافق بر سر یک سری کلیدواژههای واحد، بتوانند معنای نوشتهها و تحقیقات خود را به دیگران بفهمانند. هوشمصنوعی و زیرشاخهی آن یعنی بهینهسازیِ هوشمند نیز از این قاعده مستثنی نیست. یکی از واژهها و تعاریف اولیه و پایهای که دانشمندان علوم کامپیوتر در حوزهی هوش مصنوعی بر سر آن به توافق رسیدهاند، واژهی ابعاد (Dimensions) مسئله است. در واقع این واژه را میتوان پایهی اصلی برای بسیاری از مقالات و الگوریتمهای بهینهسازی دانست. در این درس میخواهیم به بررسیِ این واژه و نحوهی مقابلهی الگوریتمهای بهینهسازی با این رویکرد را بررسی کنیم.
ادامه خواندن “ابعاد (Dimension) مسئله و فضای حالت در الگوریتمهای بهینهسازی”