الگوریتم شاهین هریس — آموزش رایگان ۰ تا ۱۰۰ الگوریتم HHO

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

آشنایی با شاهین هریس

در سال ۱۹۹۷، لوئیس لوفور رویکردی را برای اندازه گیری “ضریب هوشی” پرندگان پیشنهاد کرد. بر اساس مطالعات او، شاهین‌ها را می‌توان در زمره باهوش‌ترین پرندگان طبیعت قرار داد. شاهین هریس پرنده‌ای شکاری است که در گروه‌های نسبتاً ثابتی در نیمه جنوبی آریزونا، ایالات متحده یافت می‌شوند، زندگی می‌کنند.

در طبیعت جستجوی هماهنگ شده برای شکار و سپس اشتراک گذاری حیوان کشته شده تنها برای پستانداران خاصی مشاهده شده است. پرندگان شکاری دیگر معمولاً به تنهایی برای کشف و گرفتن یک طعمه حمله می‌کنند اما شاهین هریس به دلیل فعالیت‌های منحصر به فردش به همراه سایر اعضای خانواده که در یک گروه ثابت زندگی می‌کنند متمایز از سایر پرندگان شکاری است.

این شکارچی، توانایی‌های مبتکرانه‌ای را در تعقیب در ردیابی، محاصره کردن، بیرون ریختن و در نهایت حمله به طعمه احتمالی را از خود نشان می‌دهد. این پرندگان هوشمند می‌توانند مهمانی‌های چند نفره را در فصل غیر تولید مثل ترتیب دهند. آن‌ها به عنوان شکارچیان هماهنگ و زبردست شناخته می‌شوند. آن‌ها مأموریت تیمی خود را در گرگ و میش صبح آغاز می‌کنند، این کار با ترک محل‌های زندگی آن‌ها که اغلب بر روی درختان غول پیکر است، آغاز می‌شود. آن‌ها اعضای خانواده خود را می‌شناسند و سعی می‌کنند از حرکات آن‌ها در هنگام حمله آگاه باشند.

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

تاکتیک اصلی شاهین‌های هریس برای گرفتن طعمه، «پرش غافلگیرانه» (surprise pounce) است که به عنوان استراتژی «هفت کشته» (seven kills) نیز شناخته می‌شود. در این استراتژی هوشمند، چندین شاهین سعی می‌کنند به طور مشترک از جهات مختلف به طعمه حمله کنند و به طور همزمان روی یک خرگوش در حال فرار شناسایی شده در خارج از پوشش همگرا شوند.

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

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

الگوریتم شاهین هریس

در این بخش، مراحل اکتشاف (exploration) و بهره‌برداری (exploitation) الگوریتم HHO با الهام از جستجوی طعمه، حملات غافلگیرکننده و استراتژی‌های مختلف حمله مدل‌سازی می‎‌شود. الگوریتم شاهین هریس یک روش بهینه سازی مبتنی بر جمعیت و بدون گرادیان است. از این رو، می‌توان آن را برای هر مسئله بهینه سازی با یک فرمول مناسب اعمال کرد. شکل زیر تمام مراحل الگوریتم را نشان می‌دهد که در بخش‌های بعدی به طور کامل تشریح خواهند شد.

مرحله اکتشاف در الگوریتم شاهین هریس

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

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

1. شاهین‌ها بر اساس موقعیت سایر شاهین‎ها و خرگوش نشسته و منتظر هستند ( q < 0.5 ).
2. یا بر روی درختان بلند بصورت تصادفی (مکان تصادفی در محدوده خانه گروه)، نشسته و منتظر هستند (q >= 0.5 )

که در آن X(t+1) بردار موقعیت شاهین‌ها در تکرار t است، X_rabbit(t) موقعیت خرگوش، X(t) بردار موقعیت فعلی شاهین‌ها، r_۱، r_۲، r_۳، r_۴ و q اعداد تصادفی در داخل (۰،۱) هستند که در هر تکرار به روز می‌شوند، LB و UB کران‌های بالایی و پایینی متغیرها را نشان می‌دهند، X_rand(t) موقعیت یک شاهین تصادفی از جمعیت فعلی و X_m میانگین موقعیت از جمعیت فعلی شاهین‌ها است.

در قانون اول راه حل‌هایی، بر اساس یک مکان تصادفی متاثر از موقعیت قبلی و سایر شاهین‌ها (به تصادف) ایجاد می‌شود. اما در قانون دوم معادله ۱ ما یک مدل برای ایجاد مکان‌های تصادفی در محدوده LB و UB ارائه شده است. تفاوت مکان بهترین موقعیت کنونی و میانگین موقعیت گروه را به اضافه یک مؤلفه با مقیاس تصادفی بر اساس دامنه متغیرها داریم.

متغیرهای r_۳ و r_۴ ضریب مقیاس برای افزایش ماهیت تصادفی بودن کران بالا و پایین است. در این قانون، یک طول حرکت با مقیاس تصادفی به LB اضافه شده است سپس، یک ضریب مقیاس‌پذیری تصادفی را برای مؤلفه در نظر گرفته شده تا روند متنوع‌سازی جمعیت در مناطق مختلف فضای ویژگی کشف شود. میانگین موقعیت شاهین‌ها با استفاده از معادله ۲ به دست می‌آید.

که در آن X_i(t) مکان هر شاهین را در تکرار t و N نشان دهنده تعداد کل شاهین‌ها است.

انتقال از مرحله اکتشاف به بهره برداری در الگوریتم شاهین هریس

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

که در آن E انرژی فرار طعمه را نشان می‌دهد، T حداکثر تعداد تکرارها و E0 انرژی اولیه طعمه است. E0 می‌تواند به طور تصادفی در بازه (۱+ ، ۱-) در هر تکرار تغییر کند. هنگامی که مقدار E0 از ۰ به ۱- کاهش می‌یابد، خرگوش از نظر فیزیکی ضعف می‌کند، در حالی که زمانی که مقدار E0 از ۰ به ۱ افزایش می‌یابد، به این معنی است که خرگوش در حال تقویت خود است. انرژی فرار دینامیکی E در طول تکرارها روند کاهشی دارد.

وقتی انرژی در حال فرار ۱=<|E| می‌شود، شاهین‌ها مناطق مختلف را برای یافتن مکان خرگوش جستجو می‌کنند، از این رو، در الگوریتم شاهین هریس مرحله اکتشاف انجام می‌شود و زمانی که ۱>|E| می‌شود، الگوریتم سعی می‌کند از همسایگی راه حل‌ها در طول مرحله بهره برداری، استفاده کند. به طور خلاصه، اکتشاف زمانی اتفاق می‌افتد که ۱=<|E| باشد و بهره برداری در مراحل بعدی با۱>|E| اتفاق می‌افتد. رفتار وابسته به زمان E نیز در شکل زیر نشان داده شده است.

مرحله بهره برداری در الگوریتم شاهین هریس

در این مرحله، شاهین‌های هریس با حمله به طعمه شناسایی شده در مرحله قبل، پرش غافلگیرکننده (surprise pounce) را انجام می‌دهند (همان حمله معروف seven kills). طعمه‌ها اغلب سعی می‌کنند از موقعیت‌های خطرناک فرار کنند. از این رو، سبک‌های مختلف تعقیب در موقعیت‌های واقعی رخ می‌دهد. با توجه به رفتارهای فرار طعمه و استراتژی‌های تعقیب و گریز شاهین‌های هریس، چهار استراتژی در الگوریتم HHO برای مدل سازی مرحله حمله وجود خواهد داشت.

طعمه‌ها همیشه سعی می‌کنند از موقعیت‌های تهدیدآمیز فرار کنند. فرض می‌کنیم r شانس فرار موفقیت آمیز یک طعمه با مقدار (r<0.5) است و عدم فرار موفقیت آمیز (r>=0.5) قبل از حمله غافلگیرانه باشد. هر کاری که طعمه انجام دهد، شاهین‌ها برای گرفتن طعمه محاصره سخت hard besiege یا نرم soft besiege انجام می‌دهند. این بدان معنی است که شاهین‌ها طعمه را از جهات مختلف به آرامی یا بصورت سخت بسته به انرژی حفظ شده طعمه محاصره می‌کنند. در موقعیت‌های واقعی، شاهین‌ها به طعمه مورد نظر نزدیک‌تر و نزدیک‌تر می‌شوند تا شانس خود را برای کشتن مشترک خرگوش با انجام فرودهای غافلگیرکننده افزایش دهند.

پس از چند دقیقه فرار، طعمه انرژی بیشتر و بیشتری را از دست می‌دهد. سپس، شاهین‌ها فرآیند محاصره را تشدید می‌کنند تا طعمه‌ خسته را بدون دردسر بگیرند. برای مدل‌سازی این استراتژی و فعال کردن الگوریتم برای تغییر بین فرآیندهای محاصره نرم و سخت، از پارامتر E استفاده می‌شود. در این رابطه وقتی ۰.۵=<|E|، محاصره نرم اتفاق می‌افتد و زمانی که ۰.۵>|E|، محاصره سخت رخ می‌دهد.

پاورپوینت الگوریتم شاهین هریس HHO

کلیک کنید

محاصره نرم soft besiege

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

که در آن ΔX(t) تفاوت بین بردار موقعیت خرگوش و مکان فعلی در تکرار t است، r_۵ یک عدد تصادفی در محدوده (۰,۱) است و J=2(1-r_۵) نشان دهنده قدرت پرش تصادفی خرگوش در تمام مراحل فرار است. مقدار J را به طور تصادفی در هر تکرار تغییر می‌کند تا ماهیت حرکات خرگوش را شبیه سازی کند.

محاصره سخت Hard besiege

وقتی r>=0.5 و E|<0.5| باشد طعمه بسیار خسته است و انرژی فرار کمی دارد. در این حالت شاهین‌های هریس طعمه مورد نظر را  به صورت سخت محاصره می‌کنند تا در نهایت حمله غافلگیرکننده را انجام دهند. در این وضعیت، موقعیت‌های فعلی با استفاده از معادله (۶) به روز می‌شوند:

یک مثال ساده از این مرحله با یک شاهین در شکل زیر نشان داده شده است.

محاصره نرم با شیرجه های سریع پیشرونده

هنگامی که E|>=0.5| اما r<0.5 است، خرگوش انرژی کافی برای فرار موفقیت آمیز را دارد و همچنان یک محاصره نرم قبل از حمله غافلگیرکننده ایجاد می‌شود. این روش هوشمندتر از مورد قبلی است. برای مدل‌سازی ریاضی الگوهای فرار حرکات طعمه و جهش، مفهوم پرواز یا Levy Flight (LF) در الگوریتم HHO استفاده می‌شود.

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

تأیید شده است که فعالیت‌های مبتنی بر LF تاکتیک‌های جستجوی بهینه برای جستجوگران/شکارچیان در شرایط جستجوی غیر مخرب هستند. علاوه بر این، تشخیص داده شده است که الگوهای مبتنی بر LF را می توان در فعالیت‌های تعقیب و گریز حیواناتی مانند میمون‌ها و کوسه‌ها تشخیص داد. از این رو، حرکات مبتنی بر LF در این مرحله از الگوریتم HHO مورد استفاده قرار گرفت.

با الهام از رفتارهای واقعی شاهین‌ها، فرض شده که آن‌ها می‌توانند به تدریج بهترین شیرجه ممکن را به سمت طعمه انتخاب کنند، بنابراین، برای انجام یک محاصره نرم، فرض شده که شاهین‌ها بتوانند حرکت بعدی خود را بر اساس قانون زیر در معادله (۷) ارزیابی کرده تصمیم بگیرند:

سپس نتیجه احتمالی چنین حرکتی را با شیرجه قبلی مقایسه می‌کنند تا تشخیص دهند که آیا شیرجه خوبی خواهد بود یا خیر. اگر معقول نبود (وقتی می‌بینند که طعمه حرکات فریبنده بیشتری انجام می‌دهد)، هنگام نزدیک شدن به خرگوش نیز شروع به شیرجه‌های نامنظم، ناگهانی و سریع می‌کنند. فرض شده شاهین‌ها بر اساس الگوهای مبتنی بر LF با استفاده از قانون زیر شیرجه خواهند زد:

که در آن D بعد مسئله است و S یک بردار تصادفی با اندازه ۱×D و LF تابع پروازی است که با استفاده از معادله ۹ محاسبه می‌شود.

که در آن u ،v مقادیر تصادفی در محدوده (۰،۱) هستند، بتا  B یک ثابت پیش فرض بر روی ۱.۵ است. از این رو، استراتژی نهایی برای به روز رسانی موقعیت شاهین‌ها در مرحله محاصره نرم می‌تواند توسط معادله ۱۰ انجام شود:

یک تصویر ساده از این مرحله برای یک شاهین در شکل زیر نشان داده شده است. تاریخچه موقعیت الگوهای حرکت جهشی مبتنی بر LF در طول برخی از تکرارها نیز در این تصویر ثبت و نشان داده شده است. نقاط رنگی ردپای موقعیت الگوهای مبتنی بر LF در یک آزمایش هستند و سپس، HHO به مکان Z می‌رسد. در هر مرحله، تنها موقعیت بهتر Y یا Z به عنوان مکان بعدی انتخاب می‌شود. این استراتژی برای همه عوامل جستجو اعمال می‌شود.

محاصره سخت با شیرجه‌های سریع پیشرونده

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

که در آن Y و Z با استفاده از قوانین جدید در معادلات (۱۲) و (۱۳) به دست می‌آیند.

که در آن X_m(t) با استفاده از معادله (۲) به دست می‌آید. یک مثال ساده از این مرحله در شکل‌های زیر نشان داده شده است. توجه داشته باشید که نقاط رنگی ردپای مکان الگوهای مبتنی بر LF در یک آزمایش هستند و تنها Y یا Z مکان بعدی برای تکرار جدید خواهند بود.

شبه کد الگوریتم شاهین هریس HHO

در ادامه مراحل الگوریتم شاهین هریس HHO به بخش شبه کد این الگوریتم می‌رسیم که بصورت زیر است:

Inputs: The population size N and maximum number of iterations T
Outputs: The location of rabbit and its fitness value
Initialize the random population Xi(i = 1, 2, . . . ,N)
while (stopping condition is not met) do
     Calculate the fitness values of hawks
     Set Xrabbit as the location of rabbit (best location)
     for (each hawk (Xi)) do
         Update the initial energy E0 and jump strength J ▷ E0=2rand()-1, J=2(1-rand())
         Update the E using Eq. (3)
         if (|E| >= 1) then  ▷  Exploration phase
            Update the location vector using Eq. (1)
         if (|E| < 1) then   ▷  Exploitation phase
             if (r >= 0.5 and |E| >= 0.5 ) then ▷ Soft besiege
                Update the location vector using Eq. (4)
             else if (r >= 0.5 and |E| < 0.5 ) then ▷ Hard besiege
                Update the location vector using Eq. (6)
             else if (r <0.5 and |E| >= 0.5 ) then ▷ Soft besiege with progressive rapid dives
                Update the location vector using Eq. (10)
             else if (r <0.5 and |E| < 0.5 ) then ▷ Hard besiege with progressive rapid dives
                Update the location vector using Eq. (11)
Return Xrabbit

پیچیدگی محاسباتی الگوریتم HHO

پیچیدگی محاسباتی الگوریتم HHO عمدتاً به سه فرآیند مقداردهی اولیه، ارزیابی تابع تناسب و به روز رسانی شاهین‌ها بستگی دارد. توجه داشته باشید که با N شاهین، پیچیدگی محاسباتی فرآیند مقداردهی اولیه O(N) است. پیچیدگی محاسباتی مکانیزم به روز رسانی O(T×N)+O(T×N×D) است که از جستجوی بهترین مکان و به روز رسانی بردار مکان همه شاهین‌ها تشکیل شده است، جایی که T حداکثر تعداد تکرار است و D بعد مسئله است. بنابراین، پیچیدگی محاسباتی الگوریتم شاهین هریس O(N×(T + TD + 1)) است.

نتیجه گیری مقاله الگوریتم شاهین هریس

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

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

منابع مقاله الگوریتم شاهین هریس

Heidari, A. A., Mirjalili, S., Faris, H., Aljarah, I., Mafarja, M., & Chen, H. (2019). Harris hawks optimization: Algorithm and applications. Future Generation Computer Systems, 97, 849–۸۷۲. https://doi.org/10.1016/j.future.2019.02.028