بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
الگوریتم چرخه آب طبیعی تطبیقی
خلاصه
الگوریتم های فراابتکاری برای حل مسائل دشوار و بهینه سازی جواب های بدست آمده کارایی زیادی دارند. بسیاری از این روش ها الهام گرفته از فرایندهای طبیعی می باشند مانند الگوریتم ژنتیک، پرندگان، مورچه ها و بازپخت شبیه سازی شده. در این مقاله یک الگوریتم بهینه سازی جدید مبتنی بر چرخه آب در طبیعت با تکنیک دستکاری پارامترهای آن ارائه شده و نتایج با تعدادی از توابع آزمون و یک مسئله مهندسی ارزیابی گردیده است.
کلمات کلیدی: الگوریتم های فراابتکاری، بهینه سازی، چرخه آب طبیعی، دستکاری پارامتر، سیستم استنتاج فازی، مدل فازی ممدانی، الگوریتم چرخه آب طبیعی تطبیقی.
.1 مقدمه
روش ها و الگوریتم های فراابتکاری در حل مسائل بهینه سازی بسیار موفق بوده و در ده های اخیر موارد استفاده از آنها بیشتر شده است. الگوریتم های فرامکاشفه ای با الهام گرفتن از یک پدیده طبیعی این امکان را می یابند که فضای جستجوی بسیار بزرگ طیف وسیعی از مسائل بهینه سازی پیچیده را به صورت بسیار هوشمندانه مورد کاوش قرار دهند.[1] برخی از الهام های طبیعی که بر اساس آنها یک الگوریتم فرامکاشفه ای طراحی شده است عبارتند از:تکامل موجودات در طی نسل ها، فرآیند سرد شدن یا تبرید در فلزات ، زندگی مورچه ها در یک کلونی ، حرکت گروهی پرندگان و سیستم ایمنی در بدن انسان. این روش ها دارای متغیرهای زیادی هستند که انتخاب مقادیر مناسب برای متغیرها منجر به تولید جوابهای بهینه تر شده و کارایی الگوریتم را افزایش می دهد.[1] استراتژیها و روشهای مختلفی برای دستکاری پارامترها وجود داشته که باعث بهبود عملکرد می گردد. از آنجا که تعداد پارامترها در روش های مکاشفه ای زیاد بوده عملا دستکاری آنها وقت گیر و از نظر زمانی هزینه بر است. ضمن اینکه برخی پارامترها با هم مرتبط بوده و تغییر در یکی منجر به تغییر در یک یا چند متغیر دیگر می شود.[2] همچنین باید توجه نمود دستکاری پارامترها به شدت به مسئله بهینه سازی مربوط است و نمی توان برای همه مسائل بهینه سازی یک شیوه تغییر پارامتر را بکار برد. در تعیین پارامترها با مشکلات عمده ای مواجه هستیم. بعنوان نمونه بدلیل اینکه تعیین دقیق تر مقادیر نیازمند اجراهای زیاد یک متاهیوریستیک می باشد این کار عملا کار وقت گیر بوده و زمان زیادی را هدر خواهد داد. رفتار فرامکاشفه ای ها کاملا ناشناخته بوده و پیچیده و غیرخطی است و از آنجا که پارامترها باهم مرتبط هستند تعیین دقیق مقادیر آنها کاری دشوار و مهم است.[3] همچنین طبیعت تصادفی بودن فرا ابتکاری ها یک فاکتور کلیدی برای تعیین پارامترهاست. در روشهای فرا ابتکاری با دو نوع پارامتر مواجه می شویم : پارامترهای قطعی یا حتمی که شامل زیربرنامه یا توابع مربوط به الگوریتم مانند روش انتخاب مثل چرخ رولت ، تورنمنت و ... و یا نوع روش جهش یا ترکیب می باشد و پارامترهای عددی مانند سایز جمعیت ، نرخ جهش و .[4]... پارامترهای عددی فضای جستجو را مشخص کرده و می توان برای تعیین فاصله بین دو مقدار معیاری را بیان نمود. اما در پارامترهای از نوع قطعی نمی توان فاصله بین دو مقدار را اندازه گرفت. دستکاری پارامترها بطور کلی در دو دسته پردازش های قبل از اجرا ( استاتیک) و پردازش های در حین اجرا(دینامیک) قرار می گیرند.[4]نمونه ای از الگوریتم های فراابتکاری الگوریتم ژنتیک بوده شامل دو دسته متغیر است که در برخی منابع[4-5]از دسته اول بعنوان پارامترهای استاتیک یا کمی و از دسته دوم بعنوان پارامترهای دینامیک یا کیفی نام برده می شود. در جدول 1 تعدادی ازآن ها نشان داده شده است. روش های در حین اجرای الگوریتم بصورت پویا مقادیر متغیرها را تغییر داده اما منجر به افزایش بار محاسباتی و در نتیجه افزایش زمان اجرا می شوند. روش های پویا امکان انعطاف و تغییر پذیری بیشتری را داده و در بررسی های وجودم غالباً از روش های پویا استفاده می شود.
جدول -1 پارامترهای کیفی و کمی درالگوریتم فراابتکاری ژنتیک
شایان ذکر است در حل بسیاری از مسائل برای بهتر کردن یک متغیر باید منابع یا شرایطی را از دست بدهیم مثلا برای بهتر کردن نتیجه، بار محاسباتی و زمان اجرا افزایش یافته و توان مصرفی بالا می رود . در نتیجه همواره باید مصالحه بین شرایط و پارامترها با توجه به منابع موجود و شرایط مسئله درنظر گرفته شود.[6] مقالات و منابع زیادی درباره تغییر مقادیر پارامترها در روش های فرا ابتکاری وجود دارند. بطور کلی متدهای دستکاری شامل طبقه بندی های مختلفی می باشند: [3] تنظیم دستی : این روش قدیمی ترین نوع مقدار دهی به پارامترها بر اساس تحقیقات پیشین می باشد.
تنظیم با قیاس : در این دسته، پارامتر با مقایسه و شباهت با نتایج ارزیابی های قبلی مقدار دهی می شود. مثلا نرخ جهش برابر یک تقسیم بر طول کروموزم خواهد بود. ( ( 1/L
روش های آزمایشی و تجربی : روش ها با انجام ارزیابی ها و تست های مختلف در حالت رقابت گونه، مقدار صحیح پارامتر را انتخاب خواهد کرد.
روش های ترکیبی : این روش شامل ترکیب نتایح بدست آمده از روش تجربی و جستجوی محلی است.
.2 الگوریتم چرخه آب طبیعی*
این الگوریتم که از چرخه آب موجود در طبیعت الهام گرفته شده است عمدتا برای مسائل کمینه سازی مورد استفاده قرار گرفته و جواب های بسیار خوبی را تولید می نماید.در این الگوریتم جوابها به سه دسته مسیل ها ،رودخانه ها و دریا تقسیم می شوند.[7]بهترین جواب بنام دریا و جوابهای بهتر بعدی بعنوان رودخانه شناسایی می گردند.در اجراهای پی در پی جواب ها به سمت نقاط بهتر و در نهایت به سمت دریا حرکت می کنند.موقعیت هر جواب با توجه به روابط موجود به سمت بهترین جواب تغییر می یابد.برای جلوگیری از گیر افتادن در بهینه محلی فرایند بارش اتفاق افتاده که با اعمال عملگر جهش فضای جستجو را تغییر می دهد.ماتریس جمعیت اولیه بصورت زیر خواهد بود.
در الگوریتم چرخه آب طبیعی پارامترها بصورت زیر است : :N تعداد متغیر های طراحی (بعد مسئله) است.
برای شروع الگوریتم بهینه سازی یک جمعیت اولیه تصادفی از یک ماتریس به سایز NPOP*N تولید میشود.
: NPOP تعداد کل اعضای جمعیت می باشد.هر کدام از مقادیر متغیر تصمیم گیری میتواند یک مقدار اعشاری (حقیقی) پیوسته یا گسسته باشد. (X1, X2 ,…XN) هزینه یک جریان با ارزیابی تابع هزینه (C) میشود. در مرحله اول جریان های مسیل ها یاSTREAM ایجاد میشوند یک تعداد از NSR از بهترین جواب ها (مقادیر کمینه) بعنوان دریا و رودخانه ها انتخاب میشوند.
جریانی که کمترین مقدار را در بین دیگران دارد بعنوان دریا در نظر گرفته میشود.[7] در حقیقت NSR مجموع تعداد رودخانه ها (که یک پارامتر کاربری است) و یک دریای تک است.[7]باقیمانده جمعیت (جریان هایی که به رودخانه ها یا مستقیماً به دریا راه دارند). مقدار آب وارد شده به رودخانه یا دریا از یک جریان به جریان دیگر متفاوت است علاوه بر این جریان رودخانه به دریایی که در سراشیبی است راه می یابند. با توجه به مفهوم WCA رودخانه ها و دریا ، مسیل ها را بعنوان یک جز متحرک جواب ها را به سمت بهترین و بهتر جذب میکند.[7] در واقع دریا و رودخانه ها ،مسیل را بر اساس شدت جریان بر میگرداند. بنابراین یک دریا بهترین جواب برای جمعیت فعلی است. در حقیقت WCA مفهوم حرکت غیر مستقیم از مسیل ها به رودخانه ها و رودها به دریا ( بهترین جواب بهینه بدست آمده موقتی) را به کار میگیرد.
تغییر موقعیت جوابها در شکل 1و روابط مربوطه در زیر داده شده است.[7]
وجود تعداد پارامترهای زیاد در الگوریتم های فرا ابتکاری پژوهشگران را بر آن داشت تا با تغییر مقادیر و تطبیق دهی متغیرها به نتایج قابل قبولی دست یابند. تغییر مناسب پارامترهای کنترلی بر کارایی الگوریتم اثر دارد. در اینجا منظور از کارایی، کیفیت راه حل های پیدا شده و زمان رسیدن به این راه حل ها می باشد. بعنوان مثال در الگوریتم مورچه ها تعداد مورچه ها تاثیر واضحی بر روی پیچیدگی محاسباتی دارند.[1] عامل دیگر در این الگوریتم حداکثر تعداد تکرار است که بر کیفیت جواب بدست آمده اثر قابل ملاحظه ای خواهد داشت. بطور مشابه در الگوریتم بهینه سازی اجتماع ذرات یا PSO نیزتغییر در پارامترهای تعداد ذرات و تعداد تکرار و ضرایب شتاب c1,c2 بهمراه بردارهای r1,r2 بر کارایی الگوریتم اثر می گذارد.
.3استنتاج فازی
در دنیای امروز محققان و اندیشمندان علوم مختلف در تحقیقات خود در پی روشها و الگوهای کارآمد در جهت بهبود سطح زندگی بشر هستند.[8] دشواری ها و ارائه مفاهیم نادقیق در قالب عبارات ریاضی کلاسیک ، انگیزه و هدف خوبی برای ابداع روشی نو در بیان مفاهیم فراهم نمود. نظریه مجموعه های فازی که اولین بار توسط پروفسور لطفی زاده مطرح شد، موثرترین و پرکاربردترین روشی است که تا به امروز برای تحقق این هدف بنیان گذاری شده است.[8] سیستمی که یک نگاشت از ورودی به خروجی را با استفاده از منطق فازی فرمول بندی می نماید به نام سیستم استنتاج فازی یا FIS * نامیده می شود.از سیستم استنتاج فازی بعنوان سیستم مبتنی بر قاعده ها نیز نام برده می شود.[8] یک سیستم استنتاج فازی مبتنی بر پنج بخش اصلی است : مجموعه قوانین، توابع عضویت، تصمیم گیرنده فازی، رابط فازی سازی و غیر فازی سازی.
.1-3 مدل فازی ممدانی †
در مدل فازی ممدانی که توسط پروفسور ممدانی((1975 ابداع شد هم قسمت مقدم و هم قسمت نتیجه در قواعد بصورت فازی است.بسیاری از FIS ها از نوع ممدانی هستند که در این نوع ، اعضای مجموعه فازی خروجی را پیش بینی می کنند.
در این مدل مجموعه قوانین بصورت ماتریسی از اعداد نوشته شده که مقادیر اعداد بیانگر سطح فازی ورودی و خروجی می باشد.نکته قابل ذکر آنکه در صورت استفاده از تابع and، ستون آخر ماتریس مربوطه عدد1 و در صورت استفاده از تابع or ستون آخر با عدد 2 درج می شود.بعنوان مثال اگر ماتریس یک رابطه فازی با دو ورودی بصورت زیر باشد، آنگاه بیان عبارت سطر اول آن در مدل ممدانی بصورت" اگر ورودی اول در سطح بالا و ورودی دوم نیز در سطح بالا باشد آنگاه خروجی در سطح بالاست" خواهد بود. [9]
.4 الگوریتم چرخه آب طبیعی تطبیقی*
دستکاری و کنترل پارامترها بصورت دینامیک موجب دست یابی به جواب های بهتری خواهد شد.با توجه به جدید بودن الگوریتم چرخه آب طبیعی و بررسی متغیرهای آن می توان با دستکاری پارامترهای موجود در این روش مانند پارامتر c که عددی تصادفی بین صفر و یک می باشد و نیز پارامتر dmax موقعیت جدید هر ذره را بصورت پویا و با استفاده از سیستم های استنتاج فازی تعیین نمود که منجر به تولید نتایج بهتری خواهد شد.
سیستم فازی پیشنهادی با توجه به تعداد تکرار در الگوریتم چرخه آب طبیعی، دو متغیر مذکور را تغییر داده و بصورت مدل فازی ممدانی است.در این مدل برای متغیر تعداد تکرار از تابع عضویت مثلثی در سه سطح و برای متغیرهای وdmax از تابع عضویت گاوسی و در سه رنج استفاده شد.
5. شبیه سازی و ارائه نتایج تجربی
برای ارزیابی الگوریتم پیشنهادی از چهار تابع آزمون و یک مسئله مهندسی استفاده شده است. سنجشها با مقایسه الگوریتم چرخه آب تطبیقی( ( AWCA با الگوریتم چرخه آب و تعدادی از روش های فرا ابتکاری دیگر مقایسه و نتایج به شرح زیر ارائه گردید.
.1-5 ارزیابی بر روی مسئله اول
تابع ریاضی که در اینجا بررسی و تست گردید بصورت زیر است.[7]
با قیود
نتایج در جدول 2 نشان داده شده است.
جدول -2 نتایج بدست آمده درمسئله اول
همان طور که مقادیر محاسبه شده نشان می دهد، جواب بهینه در روش الگوریتم پیشنهادی از سایر روش ها بهتر می باشد. در شکل 2 نمودار مربوط به تعداد تکرار و تابع ارزیابی برای الگوریتم AWCA و درشکل 3برای الگوریتم WCA نشان داده شده است.
.2-5 ارزیابی بر روی مسئله دوم
تابع ریاضی که در اینجا بررسی و تست گردید بصورت زیر است.[7]
با قیود
