الگوریتم جستجوی هارمونی (HS) و کد متلب (MATLAB)
هارمونی چیست؟
هارمونی به معنای هماهنگی، هم صدایی و ترکیب خوش آهنگ صداهایی که به صورت همزمان و در یک لحظه شنیده می شوند، می باشد. به عبارتی دقیق تر هارمونی دانشی است برای چند بخشی (چند صدایی) کردن موسیقی بر پایه خصوصیتها و آکوردها و شایستگی وصلشان به یکدیگر.
الگوریتم جستجوی هارمونی
الگوریتم جست وجوی هارمونی، یک الگوریتم بهینه سازی است که در سال ۲۰۰۱ توسعه یافت. الگوریتم جست وجوی هارمونی به عنوان یک الگوریتم فر ااکتشافی موفق جهت مسیریابی در شبکه های حسگر بی سیم و در راستای افزایش طول عمر در این نوع شبکه ها است. یکی از سادهترین و جدیدترین روشهای فراابتکاری است که در فرایند جستجوی جواب شدنی بهینه در مسائل بهینه سازی، از فرایند نواختن همزمان گروه ارکستر موزیک الهام گرفته شده است. به عبارت دیگر، میان پیدا کردن یک حل بهینه در مسأله پیچیده و فرایند اجرای موزیک تشابه وجود دارد.این روش حل را ابتدا گیم در سال ۲۰۰۱ میلادی ارائه کرد. الگوریتم HS به دلیل کاربردی بودن برای مسائل بهینه سازی گسسته و پیوسته، محاسبات ریاضیاتی کم، مفهوم ساده، پارامترهای کم و اجرای آسان به یکی از پرکاربردترین الگوریتمهای بهینهسازی در سالهای اخیر در مسائل مختلف تبدیل شده است. این الگوریتم در مقایسه با سایر روشهای فراابتکاری الزامات ریاضیاتی کمتری دارد و میتوان آن را در مسائل مختلف مهندسی با تغییر در پارامترها و عملگرها تطبیق نمود. از مزیتهای دیگر این روش نسبت به روش ژنتیک این است که برای ایجاد حل جدید برخلاف روش ژنتیک که از دو بردار حل در نسل استفاده میکند، این الگوریتم از همه حلهای موجود در حافظهاش استفاده میکند. این ویژگی انعطاف الگوریتم را در جستجوی فضاهای بهتر حل افزایش میدهد. ز ویژگیهای دیگر الگوریتم جستجوی هماهنگی این است که در مدت زمان مناسبی فضاهای حل با محدوده عملکرد بهتری را شناسایی میکند. این ویژگی در صورتی که مسأله مورد مطالعه از بهینگی محلی (Optimum Local)برخوردار باشددچار مشکل میشود و در بهینگی محلی متوقف شده و نمیتواند به بهینگی سراسری (Optimum Global)برسد. دلیل این مشکل عدم کارایی مناسب الگوریتم در اجرای جستجوی محلی در مسائل بهینه سازی گسسته است.
این الگوریتم از پنج گام تشکیل شده است:
-۱ مقداردهی اولیه مسئله بهینه سازی و پارامترهای اولیه
-۲ مقداردهی حافظه هارمونی
-۳ ایجاد یک هارمونی جدید بهبودیافته
-۴ به روز کردن حافظه هارمونی
-۵ تکرار گام های ۳و ۴ تا زمانی که شرط پایانی ارضا شود یا تکرارها پایان پذیرد.
الگوریتم جستجوی هارمونی با هدف هماهنگی و هارمونی، برای رسیدن به بهترین جواب، از موسیقی الهام گرفته شده است. تلاش برای یافتن این هارمونی و هماهنگی در موسیقی، مثل پیدا کردن شرایط بهینه در فرآیند بهینه-سازی میباشد. در واقع الگوریتم جستجوی هارمونی بهترین راهبرد برای تبدیل روندهای مورد بررسی کیفی به فرآیندهای کمی و قابل لمس بهینه سازی است. روندی به همراه بعضی از قوانین ایدهآل که نتیجه آن تبدیل قطعهای زیبا از موسیقی به یک راهحل مناسب برای حل مسائل مختلف بهینهسازی خواهد بود.
شکل زیر جزئیات فرآیند بداهه نوازی موسیقی و فرآیند بهینهسازی مهندسی را نشان میدهد. در بداهه نوازی موسیقی هر نوازنده هر گام موسیقی را در یک بازه ممکن می نوازد که با همدیگر یک بردار هارمونی را تشکیل میدهند. اگر همه گامها یک هارمونی خوب و قابل قبول را بر اساس علم زیبا شناختی تولید کنند این تجربه در حافظه نوازنده ذخیره میشود و امکان ساخت یک هارمونی بهتر در زمانهای بعدی افزایش مییابد. به همین ترتیب در مسائل بهینهسازی مهندسی، هر متغیر تصمیمگیری در ابتدا یک مقدار را داخل یک دامنه مجاز به خود اختصاص میدهد که همگی با هم یک بردار پاسخ را میسازند. اگر همه متغیرهای تصمیمگیری پاسخ خوب و قابل قبول را بر اساس تابع هدف مسئله تولید کنند این تجربه در حافظه متغیر ذخیره میشود و احتمال پاسخهای بهتر افزایش پیدا میکند.
مبانی الگوریتم جستجوی هارمونی
به منظور توضیح الگوریتم جستجوی هارمونی لازم است تا روند ایجاد یک قطعه موسقی ایدهآل را توسط یک موسیقیدان حرفهای بررسی کنیم. وقتی که یک موسیقی دان در حال آفرینش یک قطعه موسیقی است سه گزینه را در پیش روی خود دارد:
- نواختن یک نغمه و موسیقی معروف دقیقا به همان ترتیبی که در ذهن موسیقی دان است.
- نواختن آهنگی شبیه موسیقی معروف، با تغییر دادن جزئی آن چیزی که وجود دارد.
- ایجاد یک قطعه موسیقی کاملا جدید با نتهای جدید.
شباهت بین کار نوازندگان در موسیقی و عملکرد روشهای بهینه یابی را می توان به صورت شکل زیر نشان داد.
استفاده و کاربرد حافظه هارمونی بسیار مهم است، زیرا مشخص میکند که آیا جوابها و هارمونیهای جدید میتوانند قابل قبول باشند یا خیر. به این منظور استفاده مؤثر و کارا از HMCR این حافظه، پارامتری برای نشان دادن احتمال انتخاب از حافظه هارمونی با عنوان (احتمال پذیرش از حافظه هارمونی) ارائه می شود که با توجه به نرخ و میزان آن، مورد بررسی قرار می گیرد.
دومین عملگر، تنظیم گام صدا است که دارای پارامترهای پهنای باند bw (ماکزیمم مقدار تغییر ایجاد شده در متغیر انتخاب شده) و میزان احتمال تنظیم و تغییر گام PAR میباشد. این دو پارامتر در ایجاد یک هارمونی (بردار جواب) جدید مورد استفاده قرارا می گیرند.
مراحل الگوریتم جستجوی هارمونی
تعریف تابع هدف و پارامترهای الگوریتم (HMCR,PAR, bw)
در ابتدا برای شروع حل با این الگوریتم، تابع و پارامترهای الگوریتم مشخص میشوند. سپس به تعریف پارامترهای HMCR و PAR که دو پارامتر بین صفر و یک هستند و به ترتیب احتمال در نظرگیری متغیر از حافظه و احتمال تغییر در متغیر انتخاب شده از حافظه ماتریس به اندازهی تصادفی میباشد،می پردازیم.
ایجاد ماتریس حافظه
در مرحله دوم یک ماتریس حافظه هارمونی از چندین راه حل یا هارمونی تشکیل میگردد.شکل کلی این ماتریس حافظه به صورت رابطه زیر است:
تولید یک راه حل یا هارمونی جدید
برای ایجاد یک هارمونی یا راه حل جدید به چند عملگر احتیاج داریم و تک تک به ایجاد متغیرها می پردازیم.برای ایجاد مقدار برای متغیر i ام ،ابتدا یک عدد تصادفی بین صفر و یک تولید میکنیم،این عدد تصادفی با HMCR مقایسه میگردد و اگر کوچکتر از آن باشد ،یک مقدار برای متغیر i ام از ماتریس حافظه و از ستون i ام انتخاب میگردد و در غیر این صورت یک مقدار تصادفی از فضای جستجو برای متغیر i ام انتخاب میگردد . در صورتی که از ماتریس حافظه یک مقدار انتخاب شد،سپس عدد تصادفی دیگری تولید می گردد و با PAR مقایسه میشود، در صورتی که عدد تصادفی کوچکتر از PAR باشد این متغیر انتخاب شده از ماتریس حافظه به مقدار کوچکی با توجه به رابطه زیر تغییر پیدا می کند. برای تعیین مقدار تغییر بر روی متغیر انتخاب شده از حافظه ماتریس، پارامتر دیگری به نام bw تعریف می گردد که با توجه به رابطه زیرمقدار متغیر جدید بدست می آید:
به روز کردن ماتریس حافظه
به همین صورت تمام متغیرهای یک جواب یا هارمونی ایجاد میشود و سپس ارزش آن هارمونی با توجه به تابع برازش محاسبه شده، و با بدترین هارمونی موجود در حافظه ماتریس مقایسه میگردد. در صورت بهتر بودن از بدترین هارمونی موجود در حافظه ماتریس، هارمونی جدید جایگزین هارمونی قبلی میشود.
شرط توقف
شرط توقف الگوریتم به چند صورت میتواند تعیین گردد. معمولا شرط توقف، زسیدن به مقدار بهینه مورد نظر میباشد. از دیگر شروط میتوان به تغییر نکردن بهترین هارمونی موجود در ماتریس حافظه یا رسیدن به تعداد تکزازهای مشخص اشاره کرد.
با تکرار این پنج مرحله، الگوریتم به مرور به مقادیر بهینه نزدیکتر شده و جوابهای مسئله بهبود می یابد.
شبه کد این الگوریتم در شکل زیر آورده شده است
انتخاب تصادفی
انتخاب تصادفی در الگوریتم جستجوی هارمونی به افزایش تنوع راه حلها کمک میکند. گام صدا هم نقشی مشابه را ایفا میکند,ئلی تغییرات را در ناحیه خاصی محدود میکند و با جستجوی محلی تطبیق میدهد.استفاده از روش انتخاب تصادفی میتواند ,الگوریتم را به سوی کشف راه حلهای متنوع و گوناگونتر هدایت کند و این روند میتواند ادامه یابد تا بهترین و جامع ترین بهینگی به دست آید. مباحث گفته شده را میتوان به صورت مفاهیم احتمالی نیز بیان نمود.
به طورکلی احتمال اینکه مقدار برای متغیر i ام فقط به صورت تصادفی از فضای جواب انتخاب شود برابر است با:
احتمال اینکه مقدار برای متغیر i ام حاصل تغییری در متغیر انتخاب شده از حافظه ماتریس باشد برابر است با:
احتمال اینکه مقدار برای متغیر i ام فقط برابر متغیر انتخاب شده از حافظه ماتریس باشد برابر است با:
به این ترتیب با تکرار زیاد این الگوریتم ,به مرور به مقدار بهینه نزدیک خواهیم شد.