دسته: ویژه کاربران آزاد

اگر درس‌های دوره‌ی جاری (الگوریتم‌های فراابتکاری) را خوانده باشید، متوجه شده‌اید که این الگوریتم‌ها به دنبال پیدا کردن راه حل در یک زمان معقول هستند. یعنی به جای اینکه تمامی مسئله را جستجو کنند، به دنبال جستجو در قسمت‌هایی از مسئله می‌گردند تا بتوانند به یک بهینه‌ی سراسری یا یک بهینه‌ی محلیِ خوب دست پیدا کنند. در درسِ بهینه‌ی سراسری و بهینه‌ی محلی، گفتیم که هدفِ الگوریتم فرار کردن از بهینه‌ی محلی و رسیدن به بهینه‌ی سراسری یا چیزی نزدیک به آن است. در همین راستا در این درس می‌خواهیم یکی دیگر از الگوریتم‌های فراابتکاری به نام جستجوی ممنوعه یا همان Tabu Search را با یکدیگر مرور کنیم.

ادامه خواندن “الگوریتم جستجوی ممنوعه (Tabu Search)”

یک بچه بیشتر به دنبال کنجکاوی و جستجو است و یک آدمِ مسن و پیر، بیشتر به دنبالِ استفاده از تجربیات گذشته‌ی خود هست. الگوریتمِ شبیه‌سازی تبرید نیز دقیقاً از همین روند استفاده می‌کند و با این کار به دنبالِ یافتن حالت بهینه در مسئله می‌گردد. الگوریتم وقتی شروع می‌کند بچه است و بیشتر جستجو می‌کند، سپس آرام آرام مسن‌تر می‌شود و کم‌تر تجربه‌ی جدید کرده و بیشتر به تجربه‌های قبلیِ خود پابند است.

ادامه خواندن “شبیه سازی تبرید (Simulated Annealing) و الگوریتم متروپولیس”

طبق نظریه‌ی داروین، نسل موجوداتِ کره‌ی خاکی، روز به روز بهتر می‌شود. به این صورت که موجودِ بهتر، با تکثیر و فرآیند‌های مختلف روز به روز بهتر می‌شود و موجوداتِ ضعیف‌تر از بین می‌روند. در واقع قانونِ بقای اصلح موجب بهینه‌سازیِ نسلِ موجودات بر روی کره‌ی خاکی می‌شود. این کار به وسیله‌ی ژن‌های موجود در موجودات انجام شده و دانشمندانِ علوم‌کامپیوتر و هوش‌مصنوعی با الهام از این نظریه، به الگوریتمی به نام الگوریتمِ ژنتیک یا همان Genetic Algorithm رسیده‌اند.

ادامه خواندن “الگوریتم ژنتیک (Genetic)”

دانشمندان و مهندسانِ تحقیقاتی، معمولاً سعی دارند تا با زبانی مشترک با یکدیگر صحبت کنند. آن‌ها در تلاشند تا با توافق بر سر یک سری کلیدواژه‌های واحد، بتوانند معنای نوشته‌ها و تحقیقات خود را به دیگران بفهمانند. هوش‌مصنوعی و زیرشاخه‌ی آن یعنی بهینه‌سازیِ هوشمند نیز از این قاعده مستثنی نیست. یکی از واژه‌ها و تعاریف اولیه و پایه‌ای که دانشمندان علوم کامپیوتر در حوزه‌ی هوش مصنوعی بر سر آن به توافق رسیده‌اند، واژه‌ی ابعاد (Dimensions) مسئله است. در واقع این واژه را می‌توان پایه‌ی اصلی برای بسیاری از مقالات و الگوریتم‌های بهینه‌سازی دانست. در این درس می‌خواهیم به بررسیِ این واژه و نحوه‌ی مقابله‌ی الگوریتم‌های بهینه‌سازی با این رویکرد را بررسی کنیم.

ادامه خواندن “ابعاد (Dimension) مسئله و فضای حالت در الگوریتم‌های بهینه‌سازی”

برای شروع بحث در مورد الگوریتم‌ها و روش‌های متداولِ فراابتکاری، ابتدا بهتر است به چند مثالِ کاربردی در این حوزه بپردازیم تا ببینیم یک الگوریتمِ فراابتکاری چگونه می‌تواند به حل مسائل کمک کند.

ادامه خواندن “الگوریتم‌های فراابتکاری (Meta Heuristic)، تابع برازش (Fitness Function) و چند مثال”

فرض کنید در یک پاساژ مشغولِ خریدِ یک نوعِ خاص کفش هستید و در فروشگاه‌های مختلف، به دنبال فروشگاهی می‌گردید که ارزان‌ترین قیمت را برای آن کفش داشته بدهد. یکی یکی فروشگاه‌ها را سرکشی می‌کنید تا متوجه می‌شوید، مغازه‌های طبقه‌ی ۴ معمولاً اجناس را ارزان‌تر می‌فروشند. پس فروشگاه‌های طبقه‌ی ۴ را با دقتِ بیشتری می‌گردید تا بالاخره به فروشگاهی می‌رسید که ارزان‌ترین قیمت را در طبقه‌ی ۴ در آن پاساژ می‌دهد. در واقع شما به یک حالتِ بهینه دست پیدا کردید ولی این بهینگی مخصوصِ آن پاساژ بوده است. شاید اگر پاساژهای دیگر را می‌گشتید، قیمتی پایین‌تر و بهینه‌تر نیز پیدا می‌کردید. می‌توان گفت شما در یک بهینه‌ی محلی افتاده‌اید و ممکن است در پاساژهای دیگر، قیمت‌های بهینه‌تری نیز موجود باشد.

ادامه خواندن “منظور از بهینه محلی (Local Optimum) و بهینه سراسری (Global Optimum) چیست؟”

فرض کنید در یک شهر دنبال خریدِ یک خانه با قیمت مناسب می‌گردید. احتمالاً به دنبال این هستید که بهترین خانه را با توجه به بودجه‌ی خود انتخاب کنید. پس یک راه حل ساده و الگوریتمی این است که از جنوبِ شرقی در شهر شروع کرده و یکی یکی تمامِ خانه‌های شهر را خیابان به خیابان تا شمالِ غربی بررسی کنید. به این ترتیب شما بعد از بررسیِ تمامیِ خانه‌های شهر، می‌توانید بهترین خانه را پیدا کنید. اما نکته‌ی مهم اینجاست که این کار، احتمالاً چندسالی طول بکشد! پس احتمالاً به سراغ روشِ دیگری خواهید رفت.

ادامه خواندن “الگوریتم فراابتکاری (Meta Heuristic) و تفاوت آن با الگوریتم‌های عادی”