الگوریتم جستجوی هارمونی — Harmony Search

4.39k بازدید
آخرین بروزرسانی: 20 دی 1403
الگوریتم های فرا ابتکاری
زمان مطالعه: 13 دقیقه

در این پست، به تشریح الگوریتم جستجوی هارمونی که اصطلاحاً Harmony Search نیز نامیده می‌شود؛ خواهیم پرداخت. الگوریتم جستجوی هارمونی با نام اختصاری HS، از سری الگوریتم های فرا ابتکاری (Meta Heuristic algorithms) مبتنی بر طبیعت (الگوریتم های NI) بوده و با استفاده از فرآیند موسیقایی جستجو، برای حالت کامل هماهنگی، مفهوم‌سازی شده است. الگوریتم HS، از روش جستجوی تصادفی (Random search) به جای جستجوی گرادیان (Gradient search) استفاده می‌کند تا راه حل‌های بهتری برای مسائل مهندسی ارائه دهد. در ادامه به تشریح کامل این الگوریتم خواهیم پرداخت.

مقدمه

این آموزش، برگرفته از مقاله A new meta-heuristic algorithm for continuous engineering optimization: harmony search theory and practice نوشته آقایان Kang Seok Lee a و Zong Woo Geem بوده؛ برای اولین بار، در ۳۰ سپتامبر ۲۰۰۴ در دانشگاه مریلند (Maryland) آمریکا، ارائه شده و اکنون هم در سایت‌های علمی قابل دانلود و مطالعه است.

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

اشکالات محاسباتی روش‌های عددی موجود، محققان را وادار کرده است که برای حل مسائل بهینه‌سازی مهندسی، بر الگوریتم‌های فراابتکاری مبتنی بر شبیه سازی، تکیه کنند. جالب است بدانید؛ عامل رایج در الگوریتم‌های فراابتکاری این است که قوانین و تصادفی بودن را برای تقلید از پدیده‌های طبیعی، ترکیب می‌کنند. این پدیده‌ها شامل فرآیند تکاملی بیولوژیکی مثل الگوریتم ژنتیک (GA)، الگوریتم بازپخت شبیه سازی شده (Simulated annealing) و الگوریتم جستجوی تابو (Tabu Search) ارائه شده توسط محققان حوزه علوم کامپیوتر، می‌باشند.

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

مروری کوتاه، بر الگوریتم های فرا ابتکاری موجود

از ابتدای دهه ۱۹۷۰ میلادی، بسیاری از الگوریتم‌های فرا ابتکاری که قواعد ریاضی و علوم کامپیوتر را با الگوریتم‌های جستجوی تصادفی و در تقلید از پدیده‌های طبیعی ترکیب می‌کنند؛ برای غلبه بر اشکالات محاسباتی الگوریتم‌های عددی موجود، مثل مشتقات پیچیده (Complex derivatives)، حساسیت به مقادیر اولیه (Sensitivity to initial values) و حافظه شمارش انبوه (The large amount of enumeration memory) و غیره ابداع شده‌اند.

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

با ادامه فرآیند خنک سازی، سیستم منظم‌تر شده و به حالت پایه «یخ زده» در T = 0 نزدیک می‌شود. بنابراین، می‌توان این فرآیند را به عنوان یک رویکرد آدیاباتیک، به پایین ترین حالت انرژی در نظر گرفت.

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

جستجوی تابو (A tabu search) که در ابتدا توسط گلاور (Glover) پیشنهاد شد؛ یک جستجوی گرادیان نزولی با حافظه بوده و به این ترتیب عمل می‌کند که حافظه تعدادی از حالت‌های بازدید شده قبلی را همراه با تعدادی از حالت‌هایی که ممکن است؛ نامطلوب در نظر گرفته شوند؛ را حفظ کرده و این اطلاعات را در طی فهرست تابو ذخیره می‌نماید.

دوستان عزیز، همان طور که در مقالات قبلی نیز گفته شد؛ روش‌های محاسباتی تکاملی، از جمله الگوریتم GA، الگوریتم استراتژی‌های تکامل یا برنامه‌ریزی تکاملی، الگوریتم برنامه‌ریزی ژنتیکی، ازدحام ذرات و الگوریتم ژنتیک ساخت مدل احتمالی (PMBGA) یا تخمین الگوریتم توزیع (EDA) بر اساس اصل تکامل یا بقای ژن‌های با برازندگی (Survival-of-the-fittest) بهتر است. فراموش نشود که هر کدام از الگوریتم‌های گفته شده نیز، از برخی پدیده‌های طبیعی مثل وارث ژنتیکی، تقلید خواهند کرد.

الگوریتم فرا ابتکاری جستجوی هارمونی (Harmony search meta-heuristic algorithm)

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

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

در بداهه نوازی موسیقی، هر نوازنده، نوایی را در محدوده ممکن به صدا در آورده و یک بردار هارمونی، ایجاد می‌نماید. اگر همه نوازنده‌ها، هارمونی خوبی ایجاد کنند؛ آن تجربه در حافظه هر نوازنده ذخیره شده و در تکرارهای بعدی، امکان ایجاد هارمونی بهتر، افزایش خواهد یافت. در بهینه‌سازی مهندسی نیز، هر متغیر تصمیم، در ابتدا مقداری را در محدوده ممکن انتخاب کرده و اشتراکاً بردار راه حل را تولید می‌کند. اگر همه مقادیر متغیرهای تصمیم، یک راه حل (جواب) خوب ایجاد کنند؛ آن تجربه در حافظه هر متغیر، ذخیره شده و امکان ایجاد یک راه حل خوب در تکرارهای بعدی، افزایش خواهد یافت.

همراهان گرامی، جالب است بدانید که آقای فیثاغورس، برای یک موسیقی، نسبت‌های فرکانس یا نسبت‌های طول رشته با کشش مساوی را بررسی کرد و پس از تحقیق در مورد این که چه نُت‌هایی با هم جذاب تر به نظر می‌رسند؛ به این نتیجه رسید که نت‌ها، با یکدیگر رابطه ریاضی خاصی دارند. آهنگساز فرانسوی ژان فیلیپ رامو (Jean-Philippe Rameau) نظریه‌های هارمونی کلاسیک را در کتابی به نام (Treatise on Harmony) به معنای رساله هارمونی ارائه داد که تا حال حاضر نیز، منبع مهمی برای مطالعه مدرن هارمونی آهنگ، محسوب می‌شود.

شکل زیر، از کتاب رساله هارمونی بوده و ساختار حافظه هارمونی (HM) را نشان می‌دهد و در واقع، بخش اصلی الگوریتم جستجوی هارمونی یا HS می‌باشد. اگر یک تریو جاز (Jazz trio) متشکل از ساکسیفون (Saxophone)، کنترباس (Double bass) و گیتار (Guitar) را در نظر بگیرید؛ متوجه خواهید شد که در حافظه هر نوازنده، مقدار مشخصی از آهنگ‌های ارجح وجود دارد. به عنوان مثال، در حافظه یک فرد ساکسیفونیست، آهنگ {Do, Mi, Sol} یا در حافظه یک شخص کنترباسیست، ملودی {Si، Sol، Re} و یا حتی در ذهن یک گیتاریست هم، آهنگ {La, Fa, Do} هک شده است.

فرض کنید؛ ساکسیفونیست به صورت تصادفی Sol را در حالت بدون حافظه از {Do, Mi, Sol} بخواند و از طرف دیگر، کنترباسیست Si را از {Si, Sol, Re} و گیتاریست Do را از {La, Fa, Do} اجرا کند؛ در این صورت، از نظر موسیقی آکورد C-7، هارمونی (Sol, Si, Do) یک هارمونی دیگر و خارج از برنامه گروه، ایجاد خواهد کرد. اگر از دید مهندسی به این هارمونی بنگریم؛ در صورتی که هارمونی جدید، بهتر از بدترین هارمونی موجود در HM باشد؛ هارمونی جدید در HM لحاظ شده؛ بدترین هارمونی از HM حذف گردیده و این فرآیند، تا زمانی که یک هارمونی ایده آل، یافت شود؛ ادامه خواهد یافت.

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

اگر اولین متغیر 100mm را از بازه {100mm, 300mm, 500mm}، دومین مقدار 500mm را از بین اعداد {700mm, 500mm, 200mm} و سومین مقدار 400mm را از بین مقادیر {600mm, 400mm, 100mm} انتخاب کند؛ یک بردار جدید با مقادیر (100mm، 500mm، 400mm) تولید خواهد شد که اگر این بردار جدید، بهتر از بدترین بردار موجود در HM باشد؛ بردار جدید در HM لحاظ شده؛ بدترین بردار از HM حذف می‌گردد و این روش، تا زمانی که مطلوب‌ترین حالت ممکن، حاصل شود؛ تکرار خواهد شد.

هنگامی که یک نوازنده، آهنگی را به صورت بداهه می‌نوازد؛ معمولاً سه قانون پیش رو دارد:

نواختن یک آهنگ از حافظه خود.
نواختن یک آهنگ از طراحی دیگران یا نواختن آهنگ تکراری.
پخش آهنگ کاملاً تصادفی از محدوده صدای ممکن.

به طور مشابه، در بهینه سازی مهندسی نیز، وقتی هر متغیر تصمیم گیری، یک مقدار را در الگوریتم HS انتخاب می کند؛ سه قانون پیش رو خواهد داشت:

انتخاب یک مقدار از حافظه HS (تعریف شده به عنوان حافظه).
انتخاب یک مقدار مجاور از یک فضای انتخاب در حافظه HS (تعریف شده به عنوان تنظیمات الگوریتم).
انتخاب مقدار کاملاً تصادفی از محدوده مقدار ممکن (تعریف شده به عنوان مقادیر تصادفی).

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

همانند سایر الگوریتم های متاهیوریستیک، الگوریتم HS نیز شامل مراحلی از مقداردهی پارامترها تا بدست آوردن جواب بهینه می‌باشد. به طور کلی الگوریتم جستجوی هارمونی دارای ۵ مرحله مهم است که در ادامه به توضیح و تشریح هر یک از این مراحل خواهیم پرداخت.

۱- مقداردهی اولیه مسئله بهینه سازی و پارامترهای الگوریتم

برای این منظور، از فرمول زیر استفاده می‌گردد:

در رابطه بالا، f(x) تابع هدف، x مجموعه هر متغیر مدل سازی (xi) و N تعداد متغیرهای طراحی می‌باشند. از طرف دیگر، Xi مجموعه‌ای از محدوده مقادیر ممکن برای هر متغیر طراحی پیوسته بوده و در بازه زیر، تعریف می‌گردد:

با استفاده از مقداردهی مسئله، ۴ فاکتور مهم که عبارتند از: اندازه حافظه هارمونی، تعداد بردارهای حل در حافظه هارمونی یا HMS، میزان تخصیص حافظه هارمونی که اصطلاحاً HMCR نامیده می‌شود؛ نرخ تنظیم گام یا PAR و معیار خاتمه یا حداکثر تعداد جستجو تعیین می‌گردند. دوستان عزیز، به یاد داشته باشید که HMCR و PAR از جمله پارامترهایی هستند که برای بهبود بردار اصلی، استفاده می‌شوند و در گام سوم به توضیح هر کدام، خواهیم پرداخت.

۲- راه اندازی حافظه هارمونی (HM)

ماتریس حافظه هارمونی (HM) که در معادله زیر، نشان داده شده است؛ با استفاده از بردارهای حل تصادفی تولیدی، پر شده و بر اساس مقادیر تابع هدف f(x)، مرتب سازی خواهند گردید.

۳- ایجاد کردن یک هارمونی جدید از HM

یک بردار هماهنگی جدید از HM بر پایه شرایط حافظه، تنظیمات زیر و بم و تصادفی سازی ایجاد می‌‎گردد که در فرمول زیر، نشان داده شده است.

در فرمول بالا، HMCR احتمال انتخاب یک مقدار از مقادیر ذخیره شده در HM بوده و ۱ منهای HMCR احتمال انتخاب تصادفی یک مقدار امکان پذیر می‌باشد که محدود به مقادیر ذخیره شده در HM نیست. در ادامه، یک فلوچارت جدید هارمونی برای متغیرهای پیوسته، ارائه شده است.

در شکل زیر، تابع عملکرد Six-Hump Camelback را برای فلوچارت بالا، مشاهده خواهید کرد که یکی از توابع تست استاندارد در مسائل بهینه سازی می‌باشد.

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

در این حالت، برای (x)f خواهیم داشت:

۴- بروزرسانی HM

در بروزرسانی HM، اطلاعاتی در راستای بهبود شرایط کلی مسئله، به دست خواهد آمد. برای مثال، HMCR 0.95 نشان می‌دهد که الگوریتم HS مقدار متغیر طراحی را از مقادیر ذخیره شده در HM با احتمال ۹۵٪ و به دنبال آن، از کل محدوده امکان پذیر با احتمال ۵٪ انتخاب می‌نماید. البته همراهان گرامی، این نکته را هم به خاطر بسپارید که این فرآیند، کاملاً مشابه مرحله بررسی نرخ جهش در فرآیند انتخاب الگوریتم ژنتیک می‌باشد.

در بروزرسانی HM، هر جزء بردار هارمونی جدید، مورد بررسی قرار می‌گیرد تا مشخص شود که آیا باید آن را تنظیم کرد یا خیر. در فرآیند بروزرسانی HM، از پارامتر PAR استفاده می‌شود که بر اساس نرخ تنظیم برای گام انتخاب شده، عمل کرده و به وسیله آن، HM به صورت زیر، تنظیم می‌گردد.

فرآیند تنظیم Pitch تنها پس از انتخاب یک مقدار از HM انجام می‌گیرد. جالب است بدانید؛ مقدار ۱-PAR وظیفه تعیین میزان انجام هیچ کاری را بر عهده دارند. برای مثال، PAR 0.3 نشان می‌دهد که الگوریتم یک مقدار همسایه با احتمال HMCR 30% را انتخاب می‌نماید. محاسبه Pitch، از طریق فرمول زیر، انجام می‌گیرد.

۵- تکرار برای محقق شدن شرط الگوریتم جستجوی هارمونی

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

فلوچارت الگوریتم جستجوی هارمونی

با توجه به توضیحات فوق، فلوچارت بهینه سازی الگوریتم جستجوی هارمونی یا HS به صورت زیر خواهد بود.

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

جمع بندی نهایی در رابطه با الگوریتم جستجوی هارمونی

در جمع بندی آنچه گفته شد؛ می‌توان این گونه بیان کرد که در الگوریتم فراابتکاری جستجوی هارمونی، ابتدا پارامترهای الگوریتم مانند HMS ،HMCR و PAR، حداکثر تعداد جستجوها، تعداد متغیرهای طراحی و کران های متغیر طراحی، مقداردهی اولیه می‌شوند.

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

پس از اتمام مرحله اولیه الگوریتم، نوبت به مرحله جستجو خواهد رسید. به این ترتیب که هارمونی جدیدی از HM تولید شده اولیه، یا مقادیر متغیر، ممکن است با استفاده از پارامترهای HMCR و PAR ایجاد شود. این پارامترها برای اجازه دادن به راه حل، برای فرار از بهینه محلی و بهبود پیش بینی بهینه سراسری الگوریتم HS، معرفی شده‌اند. تابع هدف f(x) با استفاده از هارمونی جدید محاسبه شده و مناسب بودن آن، با استفاده از توابع استاندارد، مورد ارزیابی قرار می‌گیرد.

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

پاورپوینت الگوریتم جستجوی هارمونی Harmony Search Algorithm

زهرا یاوری

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

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