مقایسه الگوریتم‌های هیوریستیک، متاهیوریستیک و احتمالاتی

در این مقاله از سری آموزش‌های مجله پی استور به بررسی الگوریتم‌های هیوریستیک «Heuristics»، متاهیوریستیک یا فراابتکاری «Meta-Heuristics» و احتمالاتی «Probabilistic» خواهیم پرداخت. هدف ما بررسی تعریف، شباهت‌ها، تفاوت‌ها و ارائه مثال‌هایی از هر یک از این الگوریتم‌ها است.

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

حل مسئله در علوم کامپیوتر

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

دو مثال فوق، مسئله فروشنده دوره‌گرد «Traveling Salesman Problem» و مسئله کوله‌پشتی «Knapsak Problem» هستند که به عنوان مسائل بهینه‌سازی کلاسیک در علوم کامپیوتر شناخته می‌شوند.

برای حل این مسائل، می‌توان از چندین راهکار مختلف استفاده کرد. برخی از این راهکارها فقط یک مسئله را حل می‌کنند، در حالی که برخی دیگر قابل تنظیم برای حل مسائل دیگر نیز هستند. برخی از راه‌کارها می‌توانند به نتایج بهینه سراسری دست یابند، در حالی که دیگر روش‌ها ممکن است نتایج بهینه محلی و به اندازه کافی خوب ارائه دهند.

پاورپوینت های آماده در مورد الگوریتم های بهینه سازی هوشمند

کلیک کنید

در این بخش، ما استراتژی‌های حل مسئله را به دو دسته دقیق «Exact» و غیردقیق «Non-exact» تقسیم می‌کنیم.

استراتژی‌های دقیق و غیردقیق

همانطور که اشاره شد، دسته‌بندی دقیق و غیردقیق به احتمال دستیابی به نتیجه بهینه بستگی دارد. به طور خلاصه، الگوریتم‌های دقیق با احتمال ۱۰۰ درصد تضمین می‌کنند که بهترین راه‌حل را برای یک مسئله پیدا می‌کنند. به‌عنوان مثال، الگوریتم‌های جستجوی کامل «Brute-force» همیشه دقیق هستند. برای نمونه می توانید سورس کد حل مسئله ۸ وزیر با روش Brute Force مشاهده نمایید.

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

الگوریتم‌های هیوریستیک، فراابتکاری و احتمالاتی در دسته غیردقیق قرار می‌گیرند. مثال‌هایی از این الگوریتم‌ها شامل جستجوی حریصانه «Greedy Search»، جستجوی تابو و الگوریتم‌های تکاملی هستند.

هیوریستیک‌ها

الگوریتم‌های هیوریستیک از اطلاعات مسئله برای یافتن راه‌حل‌های امیدوارکننده استفاده می‌کنند. هدف این الگوریتم‌ها لزوماً یافتن راه‌حل بهینه نیست، بلکه ارائه یک راه‌حل خوب و قابل قبول است. الگوریتم‌های مبتنی بر جستجوی حریصانه شامل ویژگی‌های مشترک زیر هستند:

• طراحی مبتنی بر مسئله: هیوریستیک‌ها برای یک مسئله خاص طراحی می‌شوند و معمولاً فقط یک مسئله را حل می‌کنند.
• موفقیت غیرقابل اندازه‌گیری: هیوریستیک‌ها نشان نمی‌دهند که چقدر نتیجه به‌دست‌آمده نزدیک یا دور از راه‌حل بهینه است.
• اجرای معقول: زمان یا منابع محاسباتی مورد نیاز برای اجرای یک هیوریستیک نباید از روش‌های دقیق تجاوز کند.

به عنوان نمونه در تصویر زیر نشان داده شده است که چگونه یک الگوریتم دقیق، یک هیوریستیک پشتیبانی‌کننده، و یک هیوریستیک مبتنی بر جستجوی حریصانه، یک مسئله ساده فروشنده دوره‌گرد را حل می‌کنند:

در تصویر بالا نتایج نهایی با رنگ قرمز مشخص شده است. بنابراین، الگوریتم دقیق همیشه نتایج بهینه سراسری را ارائه می دهد. الگوریتم دقیق با اکتشافی پشتیبان نیز نتایج بهینه سراسری را پیدا کرد. در نهایت، روش هیوریستیک ممکن است نتیجه بهینه سراسری را برگرداند، اما به پارامترهای ارائه شده برای اجرا به شدت وابستگی دارد.

متاهیوریستیک‌ها

الگوریتم‌های متاهیوریستیک یا فراابتکاری نیز مانند هیوریستیک‌ها به دنبال نتایج امیدوارکننده برای مسائل هستند، اما برخلاف هیوریستیک‌ها، این الگوریتم‌ها عمومی هستند و می‌توانند مسائل مختلفی را حل کنند. ویژگی‌های مشترک فراابتکاری‌ها شامل طراحی مستقل از مسئله است یک الگوریتم فراابتکاری قابلیت حل طیف وسیعی از مسائل را دارد. مثال‌های مشهور فراابتکاری‌ها عبارتند از الگوریتم ژنتیک، بهینه‌سازی ازدحام ذرات (PSO)، تبرید شبیه‌سازی شده گرگ خاکستری و غیره می‌باشد.

با توجه به اینکه چگونه یک الگوریتم متاهیوریستیک برای یافتن نتایج یک مسئله کار می‌کند، می توانیم آن‌ها را به سه دسته تقسیم کنیم:

• فراابتکاری جستجوی محلی «Local search metaheuristics»: به عنوان بهبود تکرار شونده شناخته می شود، فراابتکاری در این دسته با بهبود مکرر یک نتیجه میانی منفرد، نتیجه نهایی خوبی پیدا می کند.
• فراابتکاری سازنده «Constructive metaheuristics»: به جای حل کل مسائل در یک زمان، فراابتکاری سازنده یک مسئله را به چندین زیرمسئله تقسیم می کند، هر یک از آنها را حل می کند و نتایج جزئی را ادغام می کند تا یک نتیجه کامل ارائه کند.
• فراابتکاری مبتنی بر جمعیت «Population-based metaheuristics»: این دسته از فراابتکاری، جمعیتی از نتایج بالقوه را برای یک مسئله معین در نظر می گیرد، بنابراین این نتایج بالقوه را با ترکیب و اصلاح آن‌ها بهبود می‌بخشد.

تصویر زیر یک مثال ساده از حل مسئله فروشنده دوره گرد با الگوریتم ژنتیک را نشان می دهد که یک فراابتکاری مبتنی بر جمعیت است:

سورس کدهای آماده الگوریتم متاهیوریستیک برای حل مسئله

کلیک کنید

الگوریتم‌های احتمالاتی

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

• مونت کارلو Monte Carlo: به سرعت به نتیجه می‌رسد، اما ممکن است نتیجه صحیح یا بهینه نباشد.
• لاس وگاس Las Vegas: نتیجه بهینه را پیدا می‌کند، اما سرعت یافتن آن تضمین نمی‌شود.
• شرود Sherwood: همیشه نتیجه بهینه را پیدا می‌کند و از بدترین حالت زمان اجرا جلوگیری می‌کند.

یک مثال ساده از روش مونت کارلو

لیستی از اعداد و الگوریتم مونت کارلو را در نظر می‌گیریم تا بررسی کنیم که آیا عنصر اکثریت (حداقل ۵۰٪ + ۱ وقوع) در آن لیست وجود دارد یا خیر. الگوریتم یک عدد تصادفی را از لیست انتخاب می‌کند و وقوع آن را بررسی می‌کند، اگر عدد اکثریت باشد درست است یا اگر نباشد نادرست است. شبه کد الگوریتم توصیف شده به شرح زیر است:

algorithm MonteCarloMajority(numberList, lengthList):
    // INPUT
    //    numberList = a list of numbers
    //    lengthList = the length of numberList
    // OUTPUT
    //    Returns true if a randomly selected number appears more than lengthList / 2 times,
    //    and false otherwise

    i <- RANDOM() mod lengthList
    // RANDOM() returns a random number
    j <- 0
    c <- 0

    while j < lengthList:
        if numberList[i] = numberList[j]:
            c <- c + 1
        j <- j + 1 return c > lengthList / 2

بنابراین، اگر عنصر اکثریت وجود داشته باشد، احتمال بازگشت یک نتیجه اشتباه کمتر از ۱/۲ است. به این ترتیب، اگر این الگوریتم را N بار اجرا کنیم و در نتیجه همیشه false دریافت کنیم، اطمینان آن را افزایش می‌دهیم و احتمال اشتباه بودن آن به \({(۱/۲)^N}\) کاهش می‌یابد. البته همیشه این احتمال وجود دارد که تعداد اکثریت وجود داشته باشد. اما با افزایش تعداد اعدام‌ها و یافتن این تعداد اکثریت، احتمال وجود آن ناچیز می‌شود.

پاورپوینت الگوریتم مونت کارلو — حل مسائل ریاضی

کلیک کنید

خلاصه سیستماتیک

امروزه ما از سیستم های کامپیوتری برای حل مسائل مختلفی استفاده می‌کنیم. برخی از مسائل از نظر قابلیت‌های محاسباتی موجود، ساده هستند. در این صورت می‌توانیم از الگوریتم‌های دقیق برای حل این مسائل استفاده کنیم و نتایج بهینه را بگیریم.

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

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

نتیجه‌گیری

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

می توان نتیجه گرفت که استراتژی های غیر دقیق برای حل مسائل محاسباتی بسیار مهم هستند. با این حال، مسائل پیچیده ای وجود دارد و استفاده از الگوریتم های دقیق برای حل آنها غیرممکن است. بنابراین، الگوریتم‌های اکتشافی، فراابتکاری و احتمالاتی به گزینه‌های مناسبی برای حل این مسائل پیچیده محاسباتی تبدیل می‌شوند.

دوره‌های تخصصی آموزش الگوریتم متاهیوریستیک

دوره‌های تخصصی آموزش الگوریتم متاهیوریستیک

کلیک کنید