مجموعه آموزشی پی استور - https://programstore.ir

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

در این مقاله آموزشی، الگوریتم شاهین هریس یا Harris Hawks Optimizer که به اختصار HHO نامیده می شود بصورت رایگان از 0 تا 100 تشریح می شود. این الگوریتم در سال 2019 توسط علی اصغر حیدری در ژورنال Future Generation Computer Systems [1] از الزویر [2] ابداع و چاپ شده است. الگوریتم HHO یک الگوریتم بهینه‌سازی [3] مبتنی بر جمعیت و الهام‌گرفته از طبیعت است که از رفتار مشارکتی و سبک تعقیب و گریز شاهین‌های هریس در غافلگیری طعمه نشأت می گیرد.

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

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

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

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

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

شاهین هریس

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

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

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

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

رفتار های شاهین هریس

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

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

مراحل مختلف الگوریتم HHO

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

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

پاورپوینت آماده الگوریتم شاهین هریس HHO در 23 اسلاید در قالب ppt. یا pptx. با قابلیت ویرایش برای ارائه درسی آماده دانلود می‌باشد. برای تهیه و دانلود این پاورپوینت از طریق لینک زیر اقدام کنید.

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

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

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

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

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

که در آن X(t+1) بردار موقعیت شاهین ها در تکرار t است، Xrabbit(t) موقعیت خرگوش، X(t) بردار موقعیت فعلی شاهین ها، r1، r2، r3، r4 و q اعداد تصادفی در داخل (0،1) هستند که در هر تکرار به روز می شوند، LB و UB کران های بالایی و پایینی متغیرها را نشان می‌دهند، Xrand(t) موقعیت یک شاهین تصادفی از جمعیت فعلی و Xm میانگین موقعیت از جمعیت فعلی شاهین ها است.

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

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

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

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

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

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

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

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

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

رفتار E در طول دو اجرا و 500 تکرار HHO

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

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

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

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

محاصره نرم soft besiege

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

معادله محاصره نرم soft besiege در الگوریتم شاهین هریس

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

محاصره سخت Hard besiege

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

معادله محاصره سخت Hard besiege در الگوریتم شاهین هریس

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

مثالی از محاصره سخت در الگوریتم HHO

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

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

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

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

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

فرمول شماره 7 در الگوریتم HHO

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

فرمول شماره 8 در الگوریتم HHO

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

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

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

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

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

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

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

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

فرمول شماره 11 در الگوریتم HHO

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

فرمول شماره 12 و 13 در الگوریتم HHO

که در آن Xm(t) با استفاده از معادله (2) به دست می آید. یک مثال ساده از این مرحله در شکل های زیر نشان داده شده است. توجه داشته باشید که نقاط رنگی ردپای مکان الگوهای مبتنی بر 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–872. https://doi.org/10.1016/j.future.2019.02.028 [8]