جستجوی هارمونی (Harmony Seach) چیست؟

 

جستجوی هارمونی یا  harmony search یکی از بهترین روش‌های بهینه سازی مسائل یک هدفه است. علت نامگذاری این نوع جستجو، مربوط به این است که در این الگوریتم، هر متغیر تصمیم مانند یک موسیقیدان و هر مقدار مانند یک نوت عمل می‌کند. این الگوریتم در سال 2001 توسعه یافت. هدف اصلی این الگوریتم، مسیریابی در شبکه‌ها حسگر بی سیم، به منظور افزایش عمر این شبکه‌ها است.

harmony search چیست؟

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

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

مراحل الگوریتم جستجوی هارمونی، به ترتیب زیر است :

1. رائه پاسخ‌های اولیه به همراه ارزیابی آنها و پر کردن حافظه HM
2. تولید یک هارمونی جدید به همراه احتمال استفاده از HM برابر با HMCR
3. تغییر دادن فرکانس با احتمال PAR یا pitch adjustment rate و همچنین ارزیابی پاسخ‌های جدید
4. مقایسه کردن هارمونی جدید با قبلی و افزودن آن به HM در صورت بهینه بودن آن
5. برگشتن به مرحله 2، در صورتی که شرط توقف وجود نداشته باشد.

با احتمال PAR، در مولفه مورد نظرمان، تغییرات کوچکی را اعمال می‌کنیم.

طرز کار الگوریتم harmony search بر اساس توضیحات مربوط به قسمت 4 :

پارامترهای الگوریتم harmony search

الگوریتم harmony search از تعدادی پارامتر تشکیل شده است که در مورد هر یک، به تفکیک توضیح خواهیم داد.

• Maxlt : این پارامتر بیانگر مقادیر مربوط به تکرار الگوریتم است.
• HMS : HMS یا harmony Memory Size پارامتری است که بیانگر مقدار هارمونی‌هایی است که در حافظه نگهداری می‌شوند.
• nNew : این پارامتر بیانگر مقدار هارمونی‌های جدیدی است که در هر بار تکرار، ساخته میشود.
• HMCR : HMCR یا harmony Memory Consideration Rate ، پارامتری است که میزان احتمال استفاده از هارمونی مموری را نشان می‌دهد. به طور مثال، اگر میزان آن را برابر با 0.5 قرار دهیم، به این معنی است که در هنگام ایجاد یک هارمونی جدید، % 50 احتمال این موضوع وجود دارد که از هارمونی مموری استفاده شود. این ویژگی تقریبا مشابه با ویژگی انتخاب، در الگوریتم ژنتیک می‌باشد.
• PAR : PAR یا Pitch Adjustment Rate، پارامتری است که میزان احتمال ایجاد تغییرات جزیی در یک مولفه را نشان می‌دهد. این ویژگی تقریبا مشابه با ویژگی جهش ، در الگوریتم ژنتیک می‌باشد.
• FW : FW یا Fret Width پارامتری است که برای مسائل پیوسته به کار می‌رود. نام این پارامتر، برگرفته از fret یا باره ی گیتار یا ویالون است. مقدار این پارامتر باید متناسب با فاصله بین  VarMax و VarMin باشد، بنابراین می‌توانیم اینطور بگوییم که مقدار 0.05* (VarMax-VarMin)، تقریبا قابل توجه میباشد. سازهایی مانند پیانو، برخلاف سازهایی مانند گیتار از فِرِت برخوردار نیستند.

شرح کلی مراحل الگوریتم جستجوی هارمونی به ترتیب زیر است :

شرح جزئی تر الگوریتم harmony search

در عکس‌های بالا قسمت هایی با رنگ قرمز شماره گذاری شده‌اند که در این بخش در مورد هر یک توضیح خواهیم داد.

1.  این قسمت شامل ساخت یک هارمونی خام و اعمال تکثیر و …. بر روی آن است. این هارمونی، قادر است که اطلاعات مربوط به هر پاسخ را ذخیره کند. بنابراین لازم است که در ادامه، اطلاعات را در آن بریزیم. این یک هارمونی خام خصوصیت‌های اصلی   positon و cost را دارا است که در آن، cost متناظر با position است.
2. این قسمت مربوط به تکثیر هارمونی خام به میزان 20 مرتبه است. علت تکرار به این میزان، این است که میزان HMS را برابر با 20 قرار دادیم.
3. با توجه به مقدار nVar، هر پاسخ شامل 5 المان متفاوت است. این 5 المان به شکل ماتریس 1 در 5 هستند. اعضای این ماتریس بین 10- و 10 می‌باشند. ( بین مقادیر VarMax و VarMin ). در این مرحله، باید ظرفیت هارمونی خام، توسط اطلاعات تصادفی پر شود. در نتیجه، با تکرار تشکیل می‌شود. میزان این تکرار، توسط مقادیر HMS تعیین می‌شود. اگر به شکل تصادفی، یک ماتریس 1 در 5 را تشکیل دهیم و اعضای این ماتریس به شکل تصادفی، شامل مقادیر VarMax و VarMin باشد، پاسخ‌های ایجاد شده نیز، تصادفی خواهد بود. در این صورت با استفاده از unifrnd ( تابعی از ابزارهای آماری )، می‌توانیم جواب‌های تصادفی را ایجاد کنیم. پس از تولید این جواب‌های تصادفی، ارزشیابی آنها را به ازای position ای که دارند، انجام می‌دهیم.
4. این مرحله مربوط به مرتب سازی هارمونی مموری است. این مرتب سازی باید بر اساس   costانجام شود. پس از این مرحله، فاز اول الگوریتم harmony search تمام می‌شود.
5. در این مرحله، بهترین راه حل را در BestSol ذخیره می‌کنیم. همچنین، بهترین میزان cost ها را نیز، تا پایان یافتن تمامی تکرارها نگه میداریم. به عبارت دیگر، تا پایان تعداد تکرارها (MaxIt)، در هر مرتبه، بهترین جواب را در BestSol ذخیره می‌کنیم.
6. این مرحله شامل حلقه‌ای است که در واقع حلقه اصلی برنامه است و به اندازه‌ای که در پارامتر MaxIt ذکر شده، تکرار می‌شود. در این حالت باید آرایه‌ای را برای هارمونی‌های جدید بسازیم. آرایه فوق به میزان nNew ، ظرفیت نگهداری هارمونی‌های جدید را دارد.
7. در هر بار تکرار حلقه مرحله قبل، موقعیت یک هارمونی را به شکل تصادفی پر می‌کنیم.
8. حلقه موجود در این قسمت، به اندازه nVar تکرار می‌شود. در هر کدام از این تکرارها، اگر مقدار تصادفی، برابر HCMR و یا از آن کوچکتر باشد، عضوی از HM و به شکل تصادفی انتخاب می‌شود و موقعیت j ام عضو i ام HM در موقعیت j ام از عضو k ام آرایه جدید قرار می‌گیرد. اگر مقدار تصادفی، از HCMR بزرگتر باشد، جواب به شکل تصادفی ساخته می‌شود. در شرط دیگری، اگر مقدار تصادفی، برابر PAR و یا از آن کوچکتر باشد، جواب به شکل تصادفی و با استفاده از مقادیر FW ساخته شده و بر موقعیت j ام از عضو k ام آرایه جدید، اعمال می شود.
9. این قسمت مربوط به اعمال محدودیت است. اگر موقعیتی از VarMin و یا VarMax خارج شود، آن را به VarMin و یا VarMax باز خواهیم گرداند.
10. این مرحله شامل ارزیابی جواب‌ها از ابتدا تا انتها و مرتب سازی آنها و تشکیل BestCost وBestSol است.

تست بر روی تابع Sphere

کمترین مقدار این تابع در بازه [-10,10 ] و برای تابع  Sphere،  برابر با 0 است که الگوریتم harmony search، به طور قابل قبولی به آن نزدیک می‌شود، به شکلی که:

همانطور که مشاهده میکنید، بعد از 17 تکرار، مقدار best cost به زیر 1 رسیده است. در آخر و پس در تکرار 1000ام، این مقدار به 06e-3.8352 رسیده که بسیار نزدیک به 0 است.

تست بر روی تابع  DeJongs

از نمودار تابع مشاهده می‌کنید که این تابع، جواب‌های بهینه محلی فراوانی را دارد. در نتیجه الگوریتم harmony search باید دارای قابلیت پویش مناسبی باشد تا جواب‌های بهینه محلی برای آن تولید نشود. به این منظور از پارامتر PAR , HMCR استفاده می‌کنیم.

همانطور که در نمودار تابع مشاهده می‌کنید، در بازه ی 10 – تا 10 ، کمترین میزان این تابع 0 است. در تکرار اول، مقدار این تابع، 694.0663 بوده و در تکرار 18 مقدار آن به عدد 0.23157 رسیده و در تکرار 1000 ام این عدد به 12 e- 4.1108 رسیده است که به صفر بسیار نزدیک است.

تست بر روی تابع  Griewank

جواب‌های بهینه‌ی محلی در تابع Griewank بسیار زیاد است. در نتیجه باید الگوریتم harmony search دارای قابلیت پویش مناسبی باشد تا جواب‌های بهینه سراسری قابل قبولی برای آن تولید شود.

همانطور که در نمودار تابع مشاهده می‌کنید، در بازه ی 10 – تا 10 ، کمترین میزان این تابع 0 است. در تکرار 1000 ام این تابع، مقدار bestcost به 06 e- 9.2247 رسیده است که به صفر بسیار نزدیک است.

تست بر روی تابع  Rosenbrock

همانطور که در این نمودار مشاهده می‌کنید، کمترین مقدار این تابع، در بازه 10- و 10، تقریبا برابر صفر است.

همانطور که در نمودار تابع مشاهده می‌کنید، در بازه ی 10 – تا 10 ، کمترین میزان این تابع 0 است. در تکرار اول، مقدار این تابع، 2263.9681 بوده و در تکرار 432 مقدار آن به زیر 1 رسیده است. همچنین در تکرار 1000 ام این عدد به  0.002871 رسیده است که به صفر بسیار نزدیک است و با تکرار بیشتر، مقدار bestcost به مقدار بیشتری به صفر نزدیک خواهد شد.

تابع Rastrigin بر روی الگوریتم harmony search جواب نمی‌دهد. همچنین این تابع بر روی الگوریتم PSO نیز فاقد جواب مناسب است. (جواب مناسب و مد نظر ما، صفر بود که در هر دو الگوریتم، این تابع از این جواب فاصله زیادی داشت.)