Hough Transform
ژوئن 14, 2019
نصب جاوا بر روی انواع سیستم عامل
ژوئن 14, 2019
Show all

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

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

چکیده:

بسیاری از مسائل بهینه سازی در زمینه های مختلف با استفاده از الگوریتم های بهینه سازی متنوع حل شده است. تکنیک های بهینه سازی سنتی مانند برنامه ریزی خطی (LP)، غیر خطی برنامه نویسی (NLP)، و برنامه نویسی پویا (DP) نقش عمده ای در حل این مشکلات داشته اند. با این حال،  (drawbacks) نقص آنها آنها تقاضا را برای انواع دیگر الگوریتم ها، مانند روش بهینه سازی اکتشافی (شبیه سازی شده بازپخت، جستجوی ممنوع و الگوریتم های تکاملی) ایجاد می کند. با این حال، هنوز هم امکان ابداع الگوریتم های جدید اکتشافی بر اساس بر اساس مقایسه با پدیده های طبیعی یا مصنوعی وجود دارد. الگوریتم ابتکاری جدید، به تقلید از بداهه از پخش موسیقی، توسعه داده شده است و به نام جستجوی هارمونی (HS) نامگذاری شد. عملکرد الگوریتم با یک مسئله فروشنده دوره گرد (TSP)، مشکل خاص بهینه سازی دانشگاهی، و طراحی شبکه pipe با حداقل هزینه را توضیح میدهد.

کلمات کلیدی

جستجوی هارمونی، بهينه سازي، الگوریتم ابتکاری، بهینه سازی ترکیبی، موسیقی

مقدمه

امروزه اکثر جوامع سرمایه داری نیاز به حداکثر حداکثر سود و حداقل هزینه دارند. برای دستیابی به این هدف، ما معمولا در تکنیک های بهینه سازی بستگی دارد. بسیاری از مشکلات در زمینه های مختلف به عنوان فرموله مسائل بهینه سازی و حل استفاده از بهینه سازی های مختلف الگوریتم باشد. برای دستیابی به این هدف، ما معمولا وابسته به تکنیک های بهینه سازی هستیم. بسیاری از مسائل در زمینه های مختلف به عنوان مسائل بهینه سازی فرموله  با استفاده از الگوریتمهای بهینه سازی های مختلف حل شدند. در طول یک دهه، توسعه و کاربرد مدلهای بهینه سازی مورد توجه مهندسان قرار گرفت. تکنیک های سنتی ریاضی، مانند برنامه نویسی خطی (LP)، برنامه نویسی غیر خطی (NLP)، و برنامه نویسی پویا (DP)، غالبا برای حل مسائل بهینه سازی استفاده می شود. هر سه روش می تواند بهبود مدلهای ساده و ایده آل را تضمین کند. با این حال در مسائل دنیای واقعی اشکالاتی هست از جمله در LP، تلفات قابل توجهی رخ دهد هنگامی که یک مدل خطی از یک مسئله  دنیای واقعی غیر خطی توسعه داده شده است. در DP، افزایش تعداد متغیرها نمایی خواهد بود و باعث افزایش تعداد ارزیابی توابع بازگشتی و هزینه core-memory (حافظه هسته) می شود. در NLP، اگر توابع مورد استفاده در محاسبات مشتق پذیر نباشند، الگوریتم حل ممکن است راه حل بهینه را پیدا نکند. همچنین در انتخاب مقادیر اولیه مورد نیاز به منظور همگرایی تضمین به بهینه کلی و نه به بهینه محلی توجه دقیق مورد نیاز است. به منظور غلبه بر کاستی های تکنیک های ریاضی، تکنیک های بهینه سازی اکتشافی بر اساس شبیه سازی معرفی شده است.

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

از سال 1970، بسیاری از الگوریتم های اکتشافی ایجاد شده اند که ترکیبی از قوانین و تقلید از پدیده های طبیعی بودند. این روشها عبارتند از فولاد شبیه سازی (SA)، جستجوی ممنوع (TS)، و الگوریتم های تکاملی (EA).

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

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

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

الگوریتم های ژنتیکی الگوریتم های جستجو بر اساس در مکانیسم انتخاب طبیعی از جمعیت ژنتیکی است. نظریه های هلند پیشنهاد شد  و بعدها توسط گلدبرگ و دیگران توسعه یافته است.

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

استراتژی های تکامل (ES) برای حل پارامتر مشکلات بهینه سازی توسعه داده شد . ES با استفاده از رتبه بندی قطعی یک مجموعه اولیه از راه حل برای آزمایش و تست جدید انتخاب میکند. یک کروموزوم نشان دهنده یک فرد به عنوان یک جفت از مقادیر شناور است در اینجا، بردار X یک نقطه در فضای جستجو است و بردار دوم  برداری انحراف استاندارد است. عملیات اصلی جهش بصورت زیر نشان داده شده است.

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

برنامه نویسی تکاملی (EP) توسط Fogel و همکاران توسعه داده شده و برای تکامل ماشین های متناهی برای حل وظایف پیش بینی شده تعریف شدند. جداول انتقال حالت در این ماشین ها توسط جهش های تصادفی یکنواخت بر روی الفبای alphabet.مربوطه اصلاح شده اند. الگوریتم از اپراتورهای انتخاب و جهش به عنوان اپراتور اصلی استفاده می کند و نوع انتخاب tournament تصادفی است.

برنامه نویسی ژنتیک (GP) الگوریتم توسعه یافته ای بود که اخیرا توسط Koza توسعه داده شد. او پیشنهاد کرد که برنامه مورد نظر باید خود را در طول دوره روند تکامل رشد دهد. برنامه نویسی ژنتیک شبیه الگوریتم ژنتیک است تفاوت اصلی بین دو الگوریتم ارائه راه حلهاست. برنامه نویسی ژنتیک برنامه های کامپیوتری در LISP یا شمایی از زبان  کامپیوتری به عنوان راه حل ایجاد می کند.، در حالی که الگوریتم ژنتیک یک رشته از اعداد است نشان دهنده راه حل است.

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

الگوریتم جستجوی هارمونی: الگوریتم ابتکاری جدید

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

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

هارمونی موسیقی از نقطه نظر زیبایی شناختی ترکیبی از اصوات شنیده شده ی خوشایند است. هارمونی در طبیعت یک رابطه ویژه میان امواج صوتی با فرکانس های مختلف است. تا به حال فیلسوف یونانی و ریاضیدان فیثاغورس (582 BC-497 پیش از میلاد) و افراد زیادی در مورد این پدیده تحقیق کرده اند. آهنگساز فرانسوی و ژان فیلیپ رامو موسیقی شناس (1683-1764) تاسیس نظریه هارمونی کلاسیک را پایه ریزی کردند. Tirro موسیقی شناس مستندات کاملی از تاریخچه جاز آمریکایی دارد.

همانطور که اجرای موسیقی به دنبال بهترین حالت (هلرمونی فوق العاده) است که توسط تابع ارزیابی زیبایی تعیین می شود، الگوریتم های بهینه سازی به دنبال یک بهترین حالت حداقل هزینه و یا حداکثر سود یا بهره وری تعیین شده توسط تابع ارزیابی هدف هستند. همانطور که برآورد زیبایی  توسط مجموعه ای از اصوات اجرا شده توسط ابزار پیوست تعیین می شود ، تابع ارزیابی هدف نیز توسط مجموعه ای از مقادیر تولید شده توسط متغیرهای جزء تعیین می شود؛ همانطور که صداها برای زیبایی بهتر می تواند می تواند از طریق تمرین بهبود یابدمقتدیر تابع ارزیابی هدف نیز توسط تکرار بهبود می یابد ارائه مختصری از این مشاهدات در جدول 1 نشان داده شده است.

الگوریتم جدید به نام جستجوی هارمونی (HS) نامگذاری شد و مراحل HS به شرح زیر است:

گام اول: مقداردهی اولیه حافظه هارمونی (HM)

گام دوم: بداهه نوازی هارمونی جدید از HM

گام سوم: اگر هارمونی جدید بهتر از حداقل هارمونی در  HM است ، شامل هارمونی جدید در HM ، و حذف مینیمم هارمونی از HM.

گام چهارم: اگر معیار توقف راضی کننده نیست، به گام 2 برو

ساختار حافظه هارمونی (HM) در شکل 1 نشان داده شده است. یک گروه سه نفره متشکل از موسیقی جاز کمانچه، ساکسیفون و صفحه کلید را در نظر بگیرید.

در ابتدا، حافظه است با هارمونی تصادفی پر شده: (C، E، G)، (C، F، A)، و (B، D، G) که توسط تابع ارزیابی زیبایی طبقه بندی شده اند. در این روش بداهه نوازی، سه ابزار هارمونی  جدید را تولید می کنند. برای مثال، (C، D، A): کمانچه برای صداهای {C}   {C از، C، B}؛ برای صداهای ساکسیفون {D} خارج از {E، F، D}؛ و برای صداهای صفحه کلید {A} خارج از  {از G، A، G}.

هر نوت در HM شانس مشابهی برای انتخاب دارد، برای مثال، احتمال انتخاب هر یک از نوتهای E، F یا  D در HM از ساکسیفون 33.3٪ است.

اگر هارمونی جدید (C، D، A) بهتر از هارمونی موجود در HM باشد، هارمونی جدید شامل HM و بدترین هارمونی در این مثال، (B، D، G) از HM حذف شدند. این فرآیند تا زمانی که نتایج رضایت بخش بدست بیاید (تقریبا مطلوب) تکرار می شود.

برای درک بیشتر، مشکللات بهینه سازی در زیر بیان شده:

این مشکل به حداقل رساندن که به راحتی می توانید است پیدا بردار راه حل (2، 3، 1) برای حداقل جهانی است. با این حال، جستجوی هارمونی می یابد راه حل بردار در راه دیگری.

همانطور که در شکل 2a نشان داده شده است، در ابتدا HM ساخت یافته است با تولید مقادیرتصادفی که توسط مقدار تابع هدف طبقه بندی شده اند. در مرحله بعد، هارمونی جدید (1، 2، 3) پس از بررسی بداهه HM:x1 ، را {1} را از {از 2،1، 5} انتخاب می کند؛ X2 {2} را از {2، 3، 3} انتخاب می کند ؛ X3 {3} را از {1، 4، 3} انتخاب می کند. به این دلیل که مقدار تابع هارمونی جدید 9 است، هارمونی جدید است (1، 2، 3) شامل HM و بدترین هارمونی (5، 3، 3) از HM حذف شدند ، همانطور که در  در شکل 2B نشان داده. در نهایت، بداهه جستجوی هارمونی، هارمونی (2، 3، 1)، که دارای مقدار تابع ، حداقل 3است.

البته، بالا فرض شد که تمام بخشهای راه حل سراسری ابتدا در HM موجود است. وقتی این چنین نیست، به عبارت دیگر برای پیدا کردن بهینه سراسری ، الگوریتم جستجوی هارمونی یک پارامتر جدید بنام  حافظه هارمونی با توجه به نرخ (HMCR) وارد می کند که رنج آن از صفر تا یک است. اگر مقدار تولید یکنواخت بین 0 تا 1 رخ می دهد بالاتر از ارزش فعلی HMCR، سپس HS می یابد نتهای تصادفی را در محدوده قابل پخش ممکن بدون در نظر گرفتن HM پیدا کند. HMCR 0.95 بدان معنی است که در گام بعدی، الگوریتم یک مقدار متغیر از HM را با احتمال 95٪ انتخاب می کند.

برای بهبود راه حل ها و فرار از بهینه محلی ، هنوز گزینه دیگری معرفی نشده است. این گزینه تقلید تنظیم گام هریک از الات موسیقی برای ensemble میزان کردن اثر است. برای محاسبه،  مکانیسم تنظیم گام به صورت شیفت به مقادیر مجاور با یک رنج از مقادیر ممکن تعبیه شده است. اگر شش مقادیر ممکن {1، 3، 4، 6، 7، 9} باشد مقدار {6} را می توان به همسایه {4} یا {7} در فرایند تنظیم گام منتقل کرد. میزان تنظیم گام (PAR)  0.1 بدان معنی است که الگوریتم عدد مجاور را با 10٪ احتمال (یک مقدار بالاتر با 5٪ و یا یک مقدار پایین تر با 5٪) انتخاب می کند.

فرض کنید که مجموعه ای از مقادیر ممکن از یک آلات موسیقی (یک متغیر) {C، D، E، F، G} HMCR  0.95 و PAR 0.10 است، و ابزار در حال حاضر {C، E، G} را در HM دارد. در این روند الگوریتم HS، الگوریتم یکنواخت یک نوت از {C، E، G) را با 95٪ احتمال انتخاب می کند  یا یک نوت از {C، D، E، F، G} با 5 درصد احتمال  و {E} را می توان به {D}  یا {F} با 10٪ احتمال  شیفت داد وقتیکه {E} انتخاب شود.

به منظور نشان دادن قابلیت همگرایی جستجوی هارمونی ، اجازه دهید ما جستجوی هارمونی را با پارامترهای آن در نظر بگیریم: اندازه HM (تعداد هارمونی درHM) =HM

تعداد ابزارهای موسیقی (متغیرها) = N

تعداد نتهای ممکن (مقادیر) ابزارهای موسیقی= L

تعداد بهینه نتها (مقادیر) از ابزارهای موسیقی i در HM =Hi ، نرخ حافظه هارمونی  = Hr، و هارمونی  بهینه (بردار بهینه) = (C، E، G) احتمال پیدا کردن هارمونی مطلوب، احتمال (H)Pr عبارت است از:

که PAR در نظر گرفته نشده چون یک اپراتور اختیاری است.

در ابتدا، HM با هارمونی تصادفی پر شده است. اگر هیچ  نت بهینه ای از تمام ابزار های موسیقی در  HM وجود نداشت.

                                                                                    =0 =……..HN      =H2      H1

و

این به آن معنی است که احتمال(H)  Pr خیلی پایین است.

با این حال، اگر طرح هارمونی بهینه مانند (*, E, G), (C, *, G), (C, E, *) بهترین Fitness (بهترین ارزش) را نسبت به نتهای دیگر دارند. تعداد بهینه نتهای از ابزار i در HM، HI با تکرار و تکرار افزایش خواهد یافت. در نتیجه، احتمال پیدا کردن هارمونی مطلوب، (H)Pr افزایش خواهد یافت.

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

با این حال، تفاوت عمده بین GA و HS این است که HS یک بردار جدید از تمام بردارهای موجود (همه هارمونی ها در هارمونی مموری، در حالی که GA بردار جدید تنها از دو بردار موجود (پدر و مادر) ایجاد می شود. علاوه بر این، HS هریک از اجزاء  متغیر را در یک بردار به طور مستقل در نظر می

گیرد  وقتی که یک بردار جدید تولید می کند، اما GA نمی تواند چون باید ساختار ژنها را نگهداری کند.

کاربردهای Hs

در این مقاله سه مسئله ارائه شده برای نشان دادن توانایی الگوریتم جستجوی هارمونی.

مسئله 1:

HS در مسئله فروشنده دوره گرد اعمال (TSP) بکار می رود. هدف TSP  پیدا کردن کوتاه ترین مسیر برای فروشنده دوره گرد است که هر شهرستان را فقط باید یک بار بازدید کند. مشکل این مسئله تعداد زیاد تور یا گشت هاست: (n-1)!/2  برای n شهر است.

در شکل 3 ، 20 شهر ملاقات شده توسط TSP نشان داده شده است. تعداد تورهای ممکن !/2=6.0.8*1016(20-1)

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

توسط HS و با پارامترهای متفاوت 30 بار این عمل اجرا می شود. HMCR=0.85-0.99  و اندازه HM=10-100 7 عدد از این 30 عدد بهینه سراسری را بدست می آورد (حداقل طول= 117) بعد از 20000 تکرار. برای همگرایی سریعتر به بهینه سراسری، دو اپراتور (شهر مجاور)- اپراتور رفتن و اپراتور (شهرستان معکوس) معرفی شده است. (اپراتور شهر مجاور)- اپراتور رفتن باعث می شود که فروشنده نزدیک ترین شهرستان مجاور را ملاقات کند، اپراتور شهرستان معکوس بعث می شود که فروشنده برای مثال، به جای 2-3-1 ، 3-2-1 را ملاقات کند  اگر اولی کوتاهتر از دومی است 21 اجرا توسط این دو اپراتور انجام می شود. بعد از 5000 تکرار ، 11 اجرا از این 21 اجرا کوتاهترین مسیر را بدست می آورد.

مسئله 2

مشکل دوم، در اصل توسط Braken و McCormick و به نقل از Himmelblau است، مشکل به حداقل رساندن نسبتا ساده فشار و شامل متغیرهای پیوسته است. بیان مسئله به صورت زیر است:

Homaifar و همکاران به این مسئله پرداختند با استفاده GA و نتایج GA را با راه حلهای دقیق مقایسه کردند و در نتیجه روش گرادیان کاهش تعمیم یافته (GRG) به دست آمد. Fogel نتایج برنامه نویسی تکاملی را با نتایج بدست آمده از GA مقایسه کرد. مقایسه این روشها با جستجوی هارمونی در جدول 2 نشان داده شده است.

برای محاسبه با استفاده از HS، تعداد تابع ارزیابی هدف عملکرد و ساختار توابع جریمه مشابه GA و EP هستند  تعداد حداکثر ارزیابی (تکرار) به 40،000 بار تنظیم شده است. برای محاسبه جستجوی هارمونی، اندازه HM 30، HMCR    0.5است، و تعداد گامها (تعداد مقادیر ممکن برای هر متغیر) 3،000 است. اجزای X1، و X2 هر دو به طور تصادفی با توزیع یکنواخت در محدوده [-10.0,10.0]  تعریف شدند. پس از انجام نیمی از محاسبات (20،000 تکرار)، رنج به مقادیر ذخیره شده در HM محدود می شود، و محاسبات نیمه دوم دوباره از نو شروع می شود. زمان محاسبه 40،000 تکرار حدود 1 ساعت بر روی یک کامپیوتر پنتیوم 100 مگاهرتز وقت می گیرد. جدول 2 مقایسه راه حل HS را با  راه حل های دیگر نشان می دهد. اولین راه حل HS HS(1)، (اولین بار در HM) در اصطلاح هدف است. به هر حال HS(2) همچنین بهترین راه حل در میان روش های هیوریستیک از  نظر دقت است؛ ردیف سوم در جدول 2 نشان می دهد که اشتباهات نسبی بین نتایج الگوریتم و ارزش عملکرد دقیق است. اگر چه GRG راه حل را نشان می دهد نزدیک ترین مقادیر  هدف را نشان می دهد، آن محدودیت نابرابری (تمام ده راه حل از EP همچنین نقض محدودیت نابرابری) را نقض کرد.

جستجوی هارمونی ثابت می کند نسبت به روشهای دیگر در مسائل متغیر- پیوسته بهتر عمل می کند. اما معتقد است عملکرد بهتر در مسائل ترکیبی مستقل و گسسته است.

کد متلب

clc;
clear;
close all;

%% Problem Definition

CostFunction=@(x) Sphere(x); % Cost Function

nVar=5; % Number of Deciison Variables

VarSize=[1 nVar]; % Decision Variables Matrix Size

VarMin=-10; % Decision Variables Lower Bound
VarMax= 10; % Decision Variables Upper Bound

%% Harmony Search Parameters

MaxIt=10000; % Maximum Number of Iterations

HMS=20; % Harmony Memory Size

nNew=20; % Number of New Harmonies

HMCR=0.5; % Harmony Memory Consideration Rate

PAR=0.1; % Pitch Adjustment Rate

FW=0.02*(VarMax-VarMin); % Fret Width (Bandwidth)

FW_damp=0.995; % Fret Width Damp Ratio

%% Initialization

% Empty Harmony Structure
empty_harmony.Position=[];
empty_harmony.Cost=[];

% Initialize Harmony Memory
HM=repmat(empty_harmony,HMS,1);

% Create Initial Harmonies
for i=1:HMS
HM(i).Position=unifrnd(VarMin,VarMax,VarSize);
HM(i).Cost=CostFunction(HM(i).Position);
end

% Sort Harmony Memory
[~, SortOrder]=sort([HM.Cost]);
HM=HM(SortOrder);

% Update Best Solution Ever Found
BestSol=HM(1);

% Array to Hold Best Cost Values
BestCost=zeros(MaxIt,1);

% Array to Hold Mean Cost Values
MeanCost=zeros(MaxIt,1);

%% Harmony Search Main Loop

for it=1:MaxIt

% Initialize Array for New Harmonies
NEW=repmat(empty_harmony,nNew,1);

% Create New Harmonies
for k=1:nNew

    % Create New Harmony Position
    NEW(k).Position=unifrnd(VarMin,VarMax,VarSize);
    for j=1:nVar
        if rand<=HMCR
            % Use Harmony Memory
            i=randi([1 HMS]);
            NEW(k).Position(j)=HM(i).Position(j);
        end

        % Pitch Adjustment
        if rand<=PAR
            %DELTA=FW*unifrnd(-1,+1);    % Uniform
            DELTA=FW*randn();        % Gaussian (Normal) 
            NEW(k).Position(j)=NEW(k).Position(j)+DELTA;
        end

    end

    % Apply Variable Limits
    NEW(k).Position=max(NEW(k).Position,VarMin);
    NEW(k).Position=min(NEW(k).Position,VarMax);

    % Evaluation
    NEW(k).Cost=CostFunction(NEW(k).Position);

end

% Merge Harmony Memory and New Harmonies
HM=[HM
    NEW];

% Sort Harmony Memory
[~, SortOrder]=sort([HM.Cost]);
HM=HM(SortOrder);

% Truncate Extra Harmonies
HM=HM(1:HMS);

% Update Best Solution Ever Found
BestSol=HM(1);

% Store Best Cost Ever Found
BestCost(it)=BestSol.Cost;

% Store Mean Cost
MeanCost(it)=mean([HM.Cost]);

% Show Iteration Information
disp(['Iteration ' num2str(it) ': Best Cost = ' num2str(BestCost(it))]);

% Damp Fret Width
FW=FW*FW_damp;

end

%% Results

figure;
semilogy(BestCost,’r’,’LineWidth’,2);
hold on;
semilogy(MeanCost,’b:’,’LineWidth’,2);
hold off;
xlabel(‘Iteration’);
legend(‘Best Cost’,’Mean Cost’);

پاسخی بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *