بخشی از مقاله
چکیده - یکی از الگوریتم های مورد استفاده در بحث بهینه سازی الگوریتم ذرات است که بر اساس الگویی غذا یابی پرندگان و ماهیان عمل می کند. در الگوریتم ذرات یا پرندگان، از مکانیزیم مکان فعلی و سرعت ذرات استفاده می شود. یکی از مشکلات این الگوریتم، از دست دادن تنوع در جمعیت ذره ها است. برای حل این مشکل در این مقاله یک راهکار جدید ترکیبی با استفاده از الگوریتم ژنتیک ارائه شده است. عملکرد روش پیشنهادی بر روی تابع استاندارد,مورد آزمایش قرار گرفته می شود. علاوه براین، نتایج بهینه سازی برای روش پیشنهادی با سایر روشها، مورد ارزیابی قرار می گیرد.
-1مقدمه
بهینه سازی بدین مفهوم است که در بین پارامترهای یک تابع به دنبال مقادیری باشیم که تابع را کمینه یا بیشینه می نمایند. کلیه مقادیر مناسب جهت این امر را، راه حل های ممکن و بهترین مقدار از این مقادیر را راه حل بهینه می نامند. الگوریتم های بهینه سازی هر دو نوع مسائل بیشینه سازی و کمینه سازی را پوشش می دهند. به این علت که هر مسأله بیشینه سازی قادر به تبدیل به مسائل کمینه سازی می باشد.گونه های زیادی از الگوریتمهای تکاملی وجود دارند. از جمله این الگوریتم-های تکاملی می توان به تپه نوردی [1]، شبیه سازی تابکاری فلزات [2]، جستجوی [Tabu [3، الگوریتم های تکاملی، بهینه سازی گروه ذرات، کلونی مورچه ها [4]، کلونی زنبورها [5] و الگوریتم دسته ماهی های مصنوعی اشاره نمود.
یکی از مشکلات الگوریتم بهینه سازی ذرات این است که در همان تکرارهای اولیه ممکن است ذرات به سمت بهترین نقطه پیدا شده حرکت کنند و الگوریتم دچار همگرایی زودرس شود و بسیاری از فضای مسئله مورد جستجو قرار نگیرد. در نتیجه روشهای بهینه سازی که از الگوریتم بهینهسازی ذرات استاندارد استفاده میکنند ممکن است قادر به پیدا کردن بهینه سراسری نباشند. در نتیجه برای ارائه یک روش بهینه سازی که به صورت بهینه قادر به پیدا کردن بهینه محلی باشد لازم است که الگوریتم بهینهسازی ذرات اصلاح شود. برای این کار در این تحقیق تلاش میشود از یک نسخه بهبود یافته از الگوریتم بهینهسازی ذرات استفاده شود. عملگر جهش است استفاده شده در این تحقیق عملکرد بهینه سازی را بهبود میبخشد. عملگر جهش الگوریتم ژنتیک از همگرایی زودرس در الگوریتم بهینهسازی ذرات جلوگیری کرده و باعث میشود که تمام فضای جستجو مورد بررسی قرار گیرد و بهینه سراسری با احتمال بیشتری پیدا شود.
دراین مقاله چالشهای موجود در زمینه بهینه سازی ذرات بررسی شده و برای حل این مشکلات و چالشها,با استفاده از الگوریتم بهینه سازی ذرات و الگوریتم ژنتیک یک روش جدید برای بهبود بهینه سازی ارائه می شود.مهم ترین و اصلی ترین نوآوری این تحقیق ارائه یک الگوریتم بهبود یافته برای الگوریتم بهینه سازی ذرات است ,که دارای عملکرد اضافی مانند جهش است .این عملگرها از همگرایی زودرس الگوریتم ژنتیک جلوگیری کرده و عملکرد آن را بهبود می بخشند. در ادامه این مقاله و در بخش 2، روشهای پیشتر ارائه شده برای بهبود الگوریتم های تکاملی مورد مطالعه قرار خواهند گرفت، در بخش 3، روش پیشنهادی مبتنی بر الگوریتم ژنتیک برای بهود الگوریتم بهینه سازی موج بیان میگردد. در بخش 4، به ارزیابی روش پیشنهادی و بررسی عملکرد آن پرداخته میشود. و در نهایت در بخش 5 نتیجهگیری و جمعبندی کلی انجام خواهد شد.
-2مروری بر کارهای پیشین
از بین چالش های موجود در الگوریتم های تکاملی مهمترین چالش مسئله از دست دادن تنوع می باشد به همین دلیل در این بخش کارهایی که در گذشته برای حل این مشکل ارائه شده است مورد بررسی قرار می گیرد.ذرات کوانتوم در [8] به عنوان ابزاری برای حفظ سطح خاصی از تنوع در یک گروه ارائه شده اند، آن ها از مدل های اتمی، تأثیر می پذیرند. در یک اتم کلاسیک، تعدادی از الکترون ها در فاصله های مختلف بر حول کره کوچکی از نوکلئون ها - پروتون یا نوترون موجود در هسته - می چرخند. این تصور در اتم کوانتوم تغییر پیدا می کند. الکترون ها در مسیرهای قطعی و معین نمی چرخند بلکه در یک توده ی احتمالی در اطراف هسته، توزیع می شوند.اتم PSOشامل یک هسته با ذرات عادی PSO می باشد.
به جز MPSOکه از گروه های ثابت با تعداد ذرات ثابت در هر گروه استفاده می کند SPSO [9] قادر به توزیع دینامیکی ذرات به گروه ها می باشد. این روش توسط روش پاکسازی که در ارائه شده تأثیرمی پذیرد SPSO .بر مبنای مفهوم »اجزاء« طراحی شد [9] .تعریف اجزاء وابسته به پارامتر r_s می باشد که شعاع اندازه گیری شده با فاصله اقلیدسی از مرکز اجزا به مرز آن را نشان می دهد. مرکز یک جزء species seed نامیده می شود. الگوریتم [10] از دو جمعیت با اندازه برابر برای شنا سایی و دنبال کردن بهینه متحرک در محیط های پویا استفاده می کند که یکی از این جمعیت ها مسئول حفظ تنوع در فضای جستجو می باشد و جمعیت دیگر مسئول پیدا کردن بهینه سراسری می باشد حفظ تنوع در جمعیت با به کار بردن الگوریتم تفاضلات تکاملی مبتنی بر ازدحام[11] که برای بهینه سازی چند هدفه به کار می رود صورت می پذیرد در حالیکهPSO مستقیما برای پیدا کردن بهینه سراسری مورد استفاده قرار می گیرد.
الگوریتم CRDEیک الگوریتم کارا برای پیدا کردن چندین بهینه در محیط های ایستا می باشد تفاضلات تکاملی مبتنی بر ازدحام توسعه یافته الگوریتم تفاضلات تکاملی [12] با اضافه کردن یک طرح ازدحام می باشد. تنها اصلاح صورت گرفته در الگوریتم تفاضلات تکاملی در شیوه جایگزین کردن فرزندان با والدین می باشد معمولا یک والد فرزند خود برای جانشین شدن برای خود تولید می کند در حالیکه در CRDE فرزندان جانشین آن فرد از جمعیت می شوند که شباهت - نزدیکی - بیشتری با آن داشته باشند در صورتیکه مقدار برازندگی آن بهتر باشد.
ایده اصلی در رویکرد [13] بهره گیری از تعاملات محلی در اتوماتای سلولی و تقسیم کردن جمعیت ذرات در داخل سلول های اتوماتای سلولی می باشد هر گروه برای یافتن بهینه محلی تلاش می کند که این کار باعث پیدا کردن بهینه سراسری می گردد.در روش های چند گروهی قبلی به منظور جلو گیری از قرار گیری بیش از یک گروه بر روی یک قله فاصله بین گروه ها محاسبه می شود تا دو گروه در داخل شعاع فعالیت یکدیگر قرار نگیرند و در صورتیکه این اتفاق بیفتد آن گروه که دارای برازندگی کمتری است از فضای جستجو خارج می گردد اما در این روش این هزینه محاسباتی با استفاده از اتوماتای سلولی حذف شده است.
-3روش پیشنهادی
نقطه قوت این الگوریتم عدم نیاز به یک کنترل سراسری میباشد. هر ذره - عامل - در این الگوریتمها خود مختاری نسبی دارد که میتواند در سراسر فضای جوابها حرکت کند و میبایست با سایر ذرات همکاری داشته باشد [15] یکی از الگوریتمهای مشهور هوش جمعی بهینهسازی ازدحام ذرات میباشد که به طور گسترده در مسائل بهینهسازی برای پیدا کردن بهینه سراسری مورد استفاده قرار میگیرد. این الگوریتم یک روش سراسری کمینهسازی است که با استفاده از آن میتوان با مسائلی که جواب آنها یک نقطه یا سطح در فضای n بعدی میباشد،برخورد نمود.
در اینچنین فضایی یک سرعت ابتدایی به آنها اختصاص داده میشود، همچنین کانالهای ارتباطی بین ذرات در نظر گرفته میشود. سپس این ذرات در فضای پاسخ حرکت میکنند، و نتایج حاصله بر مبنای یک »ملاک شایستگی« پس از هر بازهی زمانی محاسبه میشود. با گذشت زمان، ذرات به سمت ذراتی که دارای ملاک شایستگی بالاتری هستند و در گروه ارتباطی یکسانی قرار دارند، شتاب میگیرند. علیرغم اینکه هر روش در محدودهای از مسائل بهخوبی کار میکند، الگوریتم بهینهسازی ذرات روش در حل مسائل بهینهسازی پیوسته موفقیت بسیاری از خود نشان داده است.
هر ذره با دنبال کردن ذرات بهینه در حالت فعلی، به حرکت خود در فضای مسئله ادامه میدهد. آغاز الگوریتم بهینهسازی ذرات به این شکل است که گروهی از ذرات به صورت تصادفی به وجود میآیند و با به روز کردن نسلها سعی در یافتن راهحل بهینه مینمایند. در هر گام، موقعیت و سرعت هر ذره بهروز میشود. برای این کار از دو مورد استفاده میشود. اولین مورد، بهترین موقعیتی است که تاکنون ذره موفق به رسیدن به آن شده است که با نام pbest موقعیت مذکور شناخته و نگهداری شده و توسط الگوریتم مورد استفاده قرار میگیرد و دومین مورد بهترین موقعیتی است که تاکنون توسط جمعیت ذرات به دست آمده است. این موقعیت با gbestنمایش داده میشود. در الگوریتم بهینهسازی ذرات هر ذره در فضای جستجوی با بردار نمایش داده میشود که D ابعادمسئله را نشان میدهد.
همچنین این ذره دارای سرعت v است که با بردار 2 1 نشان داده میشود. که در اینجا D ابعاد مسئله را نشان میدهد. در هر تکرار پس از یافتن بهترین مقادیر - pbest و - gbest ، بردار سرعت و مکان هر ذره با استفاده از معادلات زیر بهروز میشود. که در اینجا یک وزن ورودی است که میزان تأثیر سرعت در تکرار قبلی بر سرعت فعلی را مشخص میکند، همچنین، C_1و C_2دو مقدار تصادفی بین صفر و یک هستند. در الگوریتم ارائه شده شبه کد الگوریتم بهینهسازی ازدحام ذرات نشان داده شده است.
روش بهینهسازی اجتماع ذراتذاتاً دارای سرعت همگرایی بالایی میباشد. از آنجایی که تمام ذرات در فضای جستجو به سمت بهترین موقعیتی که در طول مسیر حرکتشان یافتهاند، شتاب میگیرند، در همان تکرارهای اولیه الگوریتم، ذراتی که در ابتدای کار در فضای جستجو پراکنده بودهاند، به سرعت به همدیگر و به نقطه بهینهای که توسط الگوریتم یافته شده است نزدیک میشوند و در نتیجه از سرعت و پراکندگی آنها به شدت کاسته میشود. در مسائل بهینهسازی با بعد بالا و پیچیده،معمولاً سرعت همگرایی بالا باعث همگرایی زودرس میشود که نتیجه آن این است که الگوریتم در یک نقطه بهینه محلی متوقف میشود. در چنین مواردی لازم است الگوریتم وقت بیشتری را صرف جستجوی نقطه بهینه کند. برای غلبه بر این مشکل میتوان پراکندگی ذرات در فضای جستجو را کنترل کرد و اگر ذرات خیلی به یکدیگر نزدیک شدند، شروع به پراکنده کردن آنها کرد. در این تحقیق از عملگر جهش ژنتیکی برای رسیدن به هدف مورد نظر استفاده شده است.
الگوریتم بهبود یافته بهینهسازی ذرات به این صورت عمل میکند که در هر تکرار تعدادی از ذرات را به تصادف انتخاب کرده و به تصادف موقعیت این ذره را تغییر میدهد. با این کار از همگرایی زودرس الگوریتم بهینهسازی ذرات جلوگیری شده و سبب میشود که تمام فضای مسئله به صورت کاملتر جستجو شود. این عملگر جهش باعث افزایش کارایی جستجوی الگوریتم بهیهسازی ذرات میشود و دقت الگوریتم بهینهسازی ذرات و بهینگی آن را نیز افزایش خواهد داد. پس از اتمام عمل بروز رسانی مکان ذرات و سرعت ذرات، عملگر جهش بر روی کروموزومها اثر داده میشود. این عملگر یک ژن از یک ذره را به طور تصادفی انتخاب نموده و سپس محتوای آن ژن را تغییر میدهد. اگر ژن از جنس اعداد دودویی باشد، آن را به وارونش تبدیل میکند و چنانچه متعلق به یک مجموعه باشد، مقدار یا عنصر دیگری از آن مجموعه را به جای آن ژن قرار میدهد.
