منبع پایان نامه ارشد درمورد بهینه سازی، انعطافپذیری

با سرعت مشخصی از کندو خارج میشود؛ زنبورهای نر ملکه را تعقیب میکنند و آنهایی که به ملکه میرسند موفق به جفتگیری با ملکه میشوند، ولی بعد از عمل جفتگیری میمیرند. ملکه تا زمانی که حجم محفظه اسپرم گنجایش داشته باشد به پرواز ادامه میدهد؛ همین که حجم آن به اندازه مورد نظر رسید، در صورتیکه انرژی پرواز داشته باشد، به کنـدو بازمیگردد. احتمال توانـایی جفتگیری هر زنبـور نر با فرمول زیر شبیهسازی میگردد:
(3-3)
، عبارت است از احتمال اضافه شدن اسپرم زنبور نرِ به حجم محفظهی اسپرم ملکهو یا احتمال یک جفتگیری موفق میباشد. قدر مطلق اختلاف بین تابع هدف زنبور نر و تابع هدف ملکه میباشد. سرعت ملکه در لحظه میباشد. این بدان معنا است که در ابتدای پرواز، که سرعت ملکه جهت جفتگیری زیاد است و چنانچه تابع برازش زنبور نر نیز مناسب باشد، بهطوریکه به مقدار تابع برازش ملکه نزدیک گردد آنگاه احتمال جفتگیری مناسب زیاد است. به تدریج، سرعت و انرژی ملکه کاهش مییابد. این موضوع با فرمول زیر نشان داده میشود:
(3-4)
مراحل اجرای این الگوریتم در زیر آورده شده است:
در شروع پرواز، ملکه، که همان جواب برتر میباشد، زنبورهای نر را به طور تصادفی جهت تولید بچههای جدید، انتخاب مینماید.
بچه زنبورهای جدید با جابجایی ژنهای نر با ژنهای ملکه ایجاد میشوند.
از زنبورهای کارگر جهت ارتقاء نسل استفاده میگردد.
تابع برازش زنبور کارگر با توجه به میزان پیشرفت در نسل زنبورها مرتب میگردد.
بچه زنبورهای برتر در حین انجام این فرآیند در صورت برتری نسبت به ملکه، جایگزین آن میشوند[42].
3-3-3- الگوریتم مورچگان
یک آزمایش بیولوژیکی معروف به نام آزمایش پل دوگانه منبع مؤثری برای طرح اولین الگوریتم ACO بود. آزمایش پل دو طرفه برای بررسی تأثیر ردپای فرومون و رفتار حاصله مورچهها طراحی شده بود. در این آزمایش، یک پل دوطرفه با دو شاخه دارای طولهای متفاوت لانه این مورچهها را به یک منبع غذایی متصل می کرد (شکل 3-4). شاخهی بلند این پل دو برابر شاخه کوتاهتر آن بود. در حین اجرای این آزمایش چنین کشف شد که بعد از چند دقیقه تقریباً اکثر مورچه ها از شاخهی کوتاهتر پل استفاده میکنند. شرح و توضیح این رفتار به این واقعیت مربوط می شود، که مورچهها فرومون را در طول مسیرشان به جای می گذارند. احتمالاً مورچههایی که به طور تصادفی واتفاقی شاخهی کوتاهتر پل را انتخاب میکنند، زودتر به منبع غذایی میرسند. وقتی که آنها به لانه برمیگردند، اثر فرومون بر روی شاخهی کوتاهتر را بو میکنند. بنابراین، عبور از این شاخه را ترجیح میدهند. فرومون بر روی شاخهی کوتاهتر، سریعتر از شاخهی درازتر جمع و انباشته میشود و بنابراین، بعد از مدت زمان کمی غلظت و تراکم فرومون بر روی شاخهی کوتاهتر بیشتر شده و تقریباً اکثر مورچهها شاخهی کوتاهتر را انتخاب میکنند. . به این ترتیب، با گذشت زمان میزان مادهی شیمیایی در مسیر درست بیشتر و در مسیر نامناسب به کلی از بین میرود و تعداد مورچههایی که جذب مسیر مستقیم میشوند، افزایش مییابد و جستجو در سایر مسیرها متوقف میگردد.
شکل 3-4 آزمایش پل دوگانه
دوریگو و همکارانش تحت تأثیر این آزمایش ACO را ارائه دادند. در سالهای اخیر، این الگوریتم برای مسائل کاربردی مختلف و برای انواع مسائل مربوط به بهینه سازی ترکیبی مثل بهینه سازی چند منظوره و دینامیک، استفاده شده است. در ادامه مراحل این الگوریتم به صورت مختصر آورده شده است.
ابتدا جمعیت اولیه به صورت تصادفی تولید میگردد، همچنین مقدار اولیهی فرومون تعیین میشود. سپس سازگاری کلیهی مورچهها بر پایهی تابع هدف ارزیابی شده و با ارزیابی تک به تک مورچهها، فرومون به مسیر خاص شامل این مورچهها اضافه میگردد. بعد از آن مورچهها با توجه به سطح فرومون توزیع میگردند. در نهایت این فرآیند تا دستیابی به حداکثر مورچهها یا عدم بهبود جواب ادامه مییابد. شایان ذکر است که در هر تکرار بهترین مسیر در حافظه ذخیره میگردد و بهترین آن، جواب نهایی مسأله خواهد شد[43]،[44].
3-3-4- الگوریتم الگوی جستجوی ممنوع
ارائه این الگوریتــم به صورت امروزی در سال ۱۹۸۶ توســــط گلاور47 انجام گرفت؛ که به لحاظ انعطافپذیری با دیگر تکنیکهای موجود میتواند رقابت نماید. در این روش جهت حل مسأله به صورت هوشمند، نیازمند به حافظهی قابل انعطاف و جستجوی واکنشی (آگاهانه) است. همچنین، امکان پیادهســازی در فضای حل به صورت کم هزینه و مؤثر را فراهم میکند. بهینههای محلی با توجه به جمعآوری اطلاعات انتخاب میگردند. شایان ذکر است الگوریتم الگوی جستجوی ممنوع، با طرحهای بدون حافظهای که به طور عمده به عملیات نیمه تصادفی تکیه دارند و به نوعی نمونه برداری انجام می دهند؛ متفاوت است. مثالهایی از روشهای بدون حافظه، روش‌های معروف الگوریتم ژنتیک و روش آبکاری فولاد هستند که به نوعی از علوم فیزیک و زیست شناسی منشأ گرفتهاند.
در واقع ایدهی اصلی، از آنجا نشأت میگیرد که انتخاب یک جواب بد، ممکن است منجر به جوابی بهتر از یک انتخاب تصادفی خوب گردد. در سیستمی که از حافظه استفاده میکند یک انتخاب بد ممکن است راهنمای مفیدتری برای چگونگی تغییر جواب به صورت مفید باشد. برای جلوگیری از قرارگرفتن در جوابهای بهینهی محلی و پیدا کردن جواب بهینهی سراسری، در این روش حرکت در فضای جواب فقط به پاسخهای بهتـر محـدود نمیشود، بلکـه در بین همسایگیهای بهدست آمده، بهترین جواب از نظر حداقل کردن تابع هدف انتخاب می شود. سپس این جواب که در بین همسایگیهای نقطه شروع شرایط بهتری نسبت به سایر جوابها دارد، بهعنوان نقطهی شروع برای مرحلهی بعدی در نظر گرفته میشود و این عملیات مجدداً تکرار میشود. به این نکته باید توجه کرد که ممکن است نقطهی انتخابی از نقطهی شروع در هر مرحله بهتر نباشد. علاوه بر این، جهت جلوگیری از جوابهای تکراری و قرار نگرفتن الگوریتم در یک حلقهی بسته، حرکت انتخابی در لیست حرکتهای ممنوع قرار میگیرد. این فرآیند، به یک جواب بهینهی نسبی منتهی میگردد. همچنین، بایستی توجه داشت بهمنظور اینکه الگوریتم در یک نقطهی بهینه نسبی متوقف نگردد، هر حرکت ممنوع بعد از چند مرحله تکرار دوباره مجاز میگردد یا اینکه با در نظر گرفتن ماهیت مسأله، فضای جستجو تغییر داده میشود. با تکرار این دو فرآیند در نهایت الگوریتم به جواب بهینه مطلق، همگرا میگردد [45].
3-3-5- الگوریتم آبکاری فولاد
در سال 1983 کریک پاتریک48 با شبیهسازی بین حداقل نمودن تابع هدف یک مسأله و سرد کردن جسم تا زمان رسیدن آن به حالت انرژی پایه، الگوریتم شبیهسازی سرد شدن را بهوجود آورد.
واژهی آنیلینگ به معنای گرم کردن جسم میباشد ولی در اصطلاح یک فرآیند فیزیکی برای بالا بردن دمای جسم تا رسیدن به نقطهی ذوب میباشد و سپس به تدریج سرد کردن تا انرژی جسم به حداقل برسد. سیمولیتد نیز در لغت به معنی شبیهسازی کردن و در اصطلاح بازسازی رفتار یک فرآیند با توجه به یک سری فرضیات با اطلاعات معلوم یا فرضی است.
در ابتدا یک نقطهی دلخواه از فضای جستجو به طور تصادفی انتخاب و تابع هدف در آن محاسبه میشود. لازم به ذکر است که جواب اولیـه جزء پارامتـرهای مهم این الگوریتـم میباشد که نقش بهسزایی را ایفا مینماید و بسته به نوع مسأله تغیر میکند. همچنین، مکانیزم ایجاد همسایگی، پارامتر مهمی میباشد که در رسیدن به جواب بهینه بسیار مؤثر خواهد بود. بعد از انتخاب این دو پارامتر، به سیستم یک دمای اولیه، متناظر با انرژی جنبشی نسبت داده میشود. انتخاب مقدار دمای اولیه دلخواه است اما بسته به اینکه تابع در نقطهی شروع چه رفتاری دارد انتخاب میگردد؛ مثلاً اگر تابع دارای تغییرات کمی است دمای کمتر انتخاب میگردد تا قابلیت تحرک کمتر باشد و اگر تابع دارای تغییرات زیاد (شیب تند) باشد دمای بیشتری در نظر گرفته میشود تا امکان حرکت و خارج شدن از مینیممهای محلی بیشتر شود. سپس یک نقطه از فضای اطراف بهعنوان گزینه برای قدم بعدی انتخاب میگردد. این نحوهی انتخاب بستگی به مسأله دارد. برای حرکت به سمت نقطهی جدید اینگونه تصمیمگیری خواهد شد، اگر جواب بهتر شد حرکت ادامه یابد و اگر نه با احتمالبه سمت نقطهی جدید برود. احتمالبا توجه به دمای سیستم و تغییر در اندازهی تابع هدف و اختلاف بین نقطهی مبدأ و مقصد انتخاب میشود. برای احتمال ذکر شده، اغلب از دو تابع مختلف استفاده میگردد، این توابع عبارتند از:
الف) تابع متروپلیس49
(3-5)
ب) تابع بولتزمن50
(3-6)
در این رابطه عددی ثابت است که در اغلب مسایل 1 در نظر گرفته میشود. به ، دمای محیط میگویند و همان طور که دیده میشود کاملاً مانند دمای محیط در عمل آنیلینگ جسم جامد کار میکند. کمیت، در ابتدای مسئله برابر مقدار خاصی در نظر گرفته میشود و سپس بهتدریج در ادامهی مسئله کاهش مییابد. بدین صورتکه با کاهش احتمال پذیرش جوابهایی که تابع هدف را زیاد میکنند؛ کم میشود. الگوریتم چند بار در دمای تکرار شده، سپس از دمای محیط کاسته میشود. معمولاً مسایل کاهش دما با رابطه 7- 3 نمایش داده میشود. که بیانگر سرعت سرد کردن است و شمارندهی تکرار می باشد.
(3-7)
در نهایت، الگوریتم تا آنجا ادامه مییابد که به شرایط نهایی(عدم پیشرفت، محدودیت زمانی، محدودیت تکرار الگوریتم) برسد[46]،[47].
3-3-6- الگوریتم خفاش
خفاش تنها پستانداری است که توانایی پرواز دارد و از قابلیت پژواک echolocation برخوردار است. آنها حدود بیست درصد از گونههای پستانداران را تشکیل میدهند و شامل 996 گونه متفاوت هستند. اغلب آنها این قابلیت را با درجهی مشخصی استفاده میکنند. در این میان میکرو خفاشها مشهورترین گونهای هستند که بهطور وسیعی از این قابلیت به منظور شناسایی شکار، اجتناب از برخورد با موانع و یافتن شکاف محل خواب در تاریکی استفاده میکنند.
این خفاشها پالسهای صوتی با فرکانس پایین ساطع کرده و منتظر انعکاس آن از اشیاء اطراف میمانند. پالسها از نظر ویژگی با یکدیگر متفاوت میباشند و این مسأله به گونهی آنها بستگی دارد. بسیاری از خفاشها از سیگنالهای کوتاه و با فرکانسهای متفاوت استفاده میکنند تا در اطرف یک اکتاو حرکت کنند. در حالی که بقیه از سیگنالهایی با فرکانس ثابت برای echolocation استفاده میکنند. پهنای باند سیگنال با توجه به گونهی آنها تغییر میکند و اغلب با استفاده از هارمونیکهای بیشتر افزایش مییابد.
شکل 3- 5 استفاده از پژواک برای پیدا کردن شکار توسط یک خفاش
برای ساده تر شدن کار از فرضیات زیر استفاده میشود:
• تمامی خفاشها از Echolocation برای تشخیص فاصله استفاده میکنند و همچنین آنها تفاوت بین غذا و شکار و موانع را میتوانند تشخیص دهند.
• خفاشها بهطور تصادفی از سرعت vi در موقعیتxi با فرکانس fmin ، طول موج متغیرλ و بلندی صداA0 برای جستجوی شکار استفاده میکنند. آنها بهطور اتوماتیک می توانند طول موج یا فرکانس پالسهای ساطع شده و نرخ ساطع شدن پالس r را بر حسب میزان نزدیکی به شکار تنظیم کنند.
• فرض میشود بلندی صدا از مقدار مثبت بزرگ A0 تا مقدار ثابت حداقل Amin تغییر میکند.
• فرکانس در بازه [0,fmax] در نظر گرفته میشود. فرکانسهای بالاتر طول موج کمتری دارند و مسیر کوتاهتری را طی میکنند. برای خفاشها، بازهی نوعی حدود چند متر است. نرخ ارسال پالس یا r

مطلب مرتبط :   منبع پایان نامه ارشد درموردخوشه بندی، بهینه سازی، دسته بندی

دیدگاهتان را بنویسید