بهینه سازی مسئله به کمک الگوریتم علف‌های هرز

الگوریتم بهینه‌سازی علف‌های هرز یک الگوریتم بهینه‌سازی عددی، الهام گرفته از رشد علف‌های هرز می‌باشد. این الگوریتم در سال 2006 توسط محرابیان و لوکاس [32] در قالب مقاله‌ای پیشنهاد شد. علف‌های هرز گیاهانی هستند که رشد هجوم آورنده و شدید آن‌ها تهدید مهمی برای گیاهان زراعی محسوب می‌شود. علف‌های هرز بسیار پایدار و تطابق پذیر در مقابل تغییرات محیط می‌باشد. بنابراین با الهام گرفتن و شبیه‌سازی خصوصیات آن‌ها می‌توان به یک الگوریتم بهینه‌سازی قوی رسید.

اکولوژی تولیدمثل علف‌های هرز

علف‌های هرز گیاهانی هستند که در یک منطقۀ جغرافیایی مشخص به شکل سراسری و برجسته رشد  می‌کنند به‌طوری‌که توسط بشر قابل‌حذف و کنترل نیستند. یک ادعایی که در مورد علف‌های هرز وجود دارد این است که علف‌های هرز همیشه برنده هستند. به‌طورکلی دلایل این ادعا را می‌توان به شکل زیر بیان کرد:

  • وجود علف‌های هرز بعد از هزاران سال از کشاورزی
  • وجود علف‌های هرز حتی بعد از استفاده از سموم مختلف
  • ظاهر شدن گونه‌های جدید علف‌های هرز به‌صورت گسترده روی زمین
  • تطبیق با محیط پیرامون خود

ویژگی‌های فوق نشان می‌دهد که علف‌های هرز گیاهانی قوی و مزاحم در کشاورزی هستند. همچنین نشان‌دهندۀ این واقعیت است که علف‌های هرز خود را با محیط تطبیق می‌دهند و برای رشد رفتار خود را تغییر می‌دهند. موفقیت علف‌های هرز، وابسته به اکولوژی و زیست‌شناسی آن‌ها است.

بهینه سازی بر اساس رفتار علف‌های هرز

مراحل الگوریتم بهینه سازی علف های هرز مطابق با رفتار این موجود در طبیعت به صورت زیر می باشد.

مرحلۀ اول: پخش دانه در فضای موردنظر

مرحلۀ دوم: رشد دانه‌ها با توجه به مطلوبیت(زادوولد) و پراکندگی محیطی

مرحلۀ سوم: ادامۀ حیات علف‌هایی با مطلوبیت بیشتر(حذف رقابتی)

مرحلۀ چهارم: ادامۀ پروسه تا رسیدن به گیاهان با بهترین مطلوبیت

جزئیات گام‌های الگوریتم بهینه‌سازی علف‌های هرز

مرحلۀ اول: تولید جمعیت تصادفی اولیه و ارزیابی تابع هدف آن‌ها

در این مرحله هر گیاه تعداد معیّنی دانه تولید می‌کند. تعداد دانه‌ای که هر گیاه مجاز است تولید کند به میزان برازندگی خود و همچنین ماکزیمم و مینیمم برازندگی کولونی علف‌های هرز بستگی داشته و این تعداد با افزایش میزان برازندگی به‌صورت خطّی افزایش خواهد یافت. روشن است که تعداد دانه‌های تولیدشده توسط گیاه وابسته به میزان تناسب گیاه با محیط آن می‌باشد، این ارتباط به‌صورت خطّی است یعنی بهترین جواب از جمعیت جاری بیشترین جواب جدید را به دست می‌دهد و بدترین جواب منجر به تولید کمترین جواب جدید می‌شود. تعداد جواب‌ها بین این دو حد به‌صورت خطّی تغییر می‌کند.

مرحلۀ دوم: تولیدمثل بر مبنای شایستگی و به‌روزرسانی انحراف معیار

علف‌های هرز ممکن است با استفاده یا بدون استفاده از سلول‌های جنسی تولیدمثل انجام دهند که این امر بستگی به نوع گیاه دارد. تولیدمثل جنسی با استفاده از بذرها (دانه[1]) یا هاگ‌ها انجام می‌شود. در تولیدمثل جنسی یک گیاه متولّد می‌شود و از زمانی که تخم به‌وسیلۀ گرده باربر می‌شود و به شکل یک‌دانه در گیاه والد درمی‌آید، زندگی خود را آغاز می‌کند. سپس آن دانه توسط باد، آب ، حیوانات و غیره پراکنده (پراکندگی محیطی) می‌شود. تاز مانی که دانه می‌تواند فضا و فرصتی برای رشد بیابد. دانه‌های مناسب زمانی که شرایط خوب باشد جوانه‌زده و شروع به رشد می‌کنند. آن‌ها در تعامل با سایر گیاهان همسایه به روییدن خود ادامه می‌دهند تا زمانی که به گیاهانی بالغ تبدیل شوند. در مرحلۀ نهایی زندگی، آن‌ها نیز به‌نوبۀ خود به گیاهان گل‌دار تبدیل‌شده و دانه تولید می‌کنند.

مرحلۀ سوم: حذف رقابتی

اگر یک گیاه تولیدمثل نداشته باشد از بین خواهد رفت. بنابراین به یک رقابت بین گیاهان برای محدود کردن حداکثر تعداد گیاهان در کولونی نیاز است. بعد از تولید دانه‌ها در اطراف هر علف، فقط می‌توانیم به تعداد بیشینه گیاه از پیش تعیین‌شده (Pmax) از مجموع علف‌ها و دانه‌ها را به نسل بعدی انتقال دهیم. گیاهانی که شانس بقاء یافته‌اند مجدداً بازتولیدشده و مراحل فوق را تکرار می‌کنند و به‌این‌ترتیب پاسخ‌های به‌دست‌آمده در هر تکرار از برازندگی بیشتری برخوردار است. این مکانیزم به گیاهان با تناسب پایین شانس تولیدمثل می‌دهد، و اگر دانه‌های تولیدشده توسط آن‌ها تناسب خوبی در کولونی داشته باشند آن‌وقت می‌توانند زنده بمانند. هنگامی‌که تعداد تکرارها به حداکثر تعداد مجاز برسد این الگوریتم متوقّف می‌شود. البته تعداد بیشینۀ گیاه از پیش تعیین‌شده می‌تواند با تعداد جمعیت اولیه برابر باشد که در این صورت یکی از پارامترهای الگوریتم حذف می‌شود.

مرحلۀ چهارم: چک کردن شرایط خاتمه

انواع شرایط خاتمه در روش‌های فرا ابتکاری:

  • رسیدن به حداقل قابل قبولی از پاسخ

در این مورد که یکی از شرط‌های توقف می‌باشد فرض کنید که کلّاً هزینه‌های یک شرکت 1000 واحد پولی می‌باشد و مدیر شرکت تمایل دارد این هزینه به 800 واحد کاهش یابد که البته این مورد از دیدگاه مدیریت مقداری مطلوب است. قابل‌توجه است که مقدار 800 نقطۀ بهینه نیست و ممکن است مقدار تابع هدف کمتر از 800 واحد نیز بشود. برای مثال در شکل2، نقطۀ A نقطۀ مطلوب از دیدگاه مدیریت را نشان می‌دهد که یکی از شرط‌های توقف می‌باشد.

  • سپری شدن زمان/ تکرار معین

در این مورد برای به پایان رساندن الگوریتم یک‌میزان تکرار برای الگوریتم معرفی می‌کنیم. مثلاً در تکرار 100 الگوریتم به اتمام رسیده و تکرارهای بعد از 100 را نیاز نداریم، هرچند که ممکن است مقدار تابع هدف بعد از تکرار معیّن بهبود یابد.

  • سپری شدن زمان/ تکرار معین بدون مشاهدۀ بهبود فراوان درنتیجه

اگر در مواردی بعد از اجرای الگوریتم در تکرارهای پی‌درپی مقدار تابع هدف بهبود نیابد یا به میزان غیرقابل‌توجه بهبود یابد الگوریتم متوقف می‌شود. مثلاً اگر با n بار تکرار از نقطۀ a تا b بهبود نیابد یا به میزان ناچیز که قابل‌توجه نباشد بهبود یابد الگوریتم متوقف می‌شود. در شکل4، تکرار a تا تکرار b مقدار تابع هدف ثابت می‌باشد که باعث می‌شود الگوریتم متوقف شود.

[1]Seed

مشاهده همه 2 نتیجه