ⓘ الگوریتم علف هرز مهاجم از دسته الگوریتم‌های فراابتکاری است و از طبیعت و گیاهان الگو گرفته‌است. این الگوریتم در سال ۲۰۰۶ توسط دو محقق ایرانی به نام‌های احمدرضا م ..

                                     

ⓘ الگوریتم علف هرز مهاجم

الگوریتم علف هرز مهاجم از دسته الگوریتم‌های فراابتکاری است و از طبیعت و گیاهان الگو گرفته‌است. این الگوریتم در سال ۲۰۰۶ توسط دو محقق ایرانی به نام‌های احمدرضا محرابیان و کارو لوکاس در قالب مقاله‌ای به نام A novel numerical optimization algorithm inspired from weed colonization ارائه گردید.

                                     

1. معرفی

یکی از چالش‌های مهمی که مهندسان و طراحان با آن سروکار دارند، مسئلهٔ بهینه‌سازی Optimization است که تا حد امکان نباید نادیده گرفته شود و بنابراین باید حداکثر تلاش در این جهت صورت بپذیرد. در حالی‌که بسیاری از بهینه‌سازی‌ها مبتنی بر الگوریتم‌های بهینه‌سازی شیب‌خیز Optimization gradient-based هستند، امروزه همچنان مسائلی در دنیای مهندسی وجود دارند که راهکار گویا و صریحی برای کنترل متغیرها ندارند و اصطلاحاً پیوسته نیستند. برای حل این مشکلات، راه حلی که پیشنهاد می‌شود این است که به جای استفاده از داده‌های اشتقاقی، از شواهد عینی و همان مقادیر محدودی که داریم استفاده کنیم؛ با اینکه ممکن است سرعت همگرایی در این روش آهسته باشد.

بسیاری از الگوریتم‌ها از طبیعت الهام می‌گیرند که به آنها الگوریتم‌های فرا ابتکاری می‌گوییم؛ از جمله نمونه‌های آن می‌توان به الگوریتم ژنتیک، الگوریتم مسیریابی مورچه، الگوریتم جستجوی ممنوعه و الگوریتم بهینه‌سازی ازدحام ذرات اشاره کرد.

الگوریتم علف هرز مهاجم نیز از رشد علف‌های هرز در یک زمین کشاورزی الهام گرفته‌است. به صورت کلی، هر گیاه و موجودی که در زمین کشاورزی نیازی به وجودش نباشد، علف هرز نامیده می‌شود. یکی از ویژگی‌های بارز علف‌های هرز این است که تطبیق‌پذیر، قوی و سمج هستند و یک تهدید جدّی برای گیاهان در حال رشد در اطراف خود به حساب می‌آیند که به همین دلیل لقب مهاجم را به آن‌ها می‌دهیم؛ از دیگر ویژگی‌هایشان این است که هرچقدر آن‌ها را کوتاه کنیم و آن‌ها را از ریشه بزنیم، سرعت و روند رشد علف‌ها در سری‌های بعد بیشتر و بیشتر خواهد شد. اصطلاحی در این باره وجود دارد که می‌گوید: "علف‌ها همیشه پیروز می‌شوند؛ هر چقدر کشاورزان بیشتر تلاش کنند، آن‌ها بیشتر رشد خواهند کرد."

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

                                     

2. تولید مثل علف‌ها

علف‌ها از آن دسته گیاهانی هستند که می‌توانند با آمیزش یا بدون آن تولید مثل کنند. یکی از نمونه‌های فرایند تولید مثل با آمیزش، استفاده از دانه پاشی است. این علف‌ها برای رشد همانند سایر موجودات به منابع نیاز دارند. با رشد بیشتر این علف‌ها در یک ناحیهٔ مشخص منبع کمتری به آن می‌رسد و ثمردهی برای هر کدام از آن‌ها کاهش می‌یابد.

چند رویکرد برای حفظ بقا در طبیعت وجود دارد که علف‌های هرز از دو رویکرد به صورت ترکیبی برای بقا و تولید مثل خود استفاده می‌کنند. انتخاب r و انتخاب k

انتخاب r {\displaystyle {r}} یا r-selection با شعار زندگی سریع - تولید مثل فوری و مرگ در جوانی:_یکی از راهکارهای حفظ بقا است که در محیط‌های ناپایدار و غیرقابل پیش‌بینی و به‌طور کلی هر جایی که توانایی برای تولید مثل سریع در حالت بیشینه است و منابع محدود است، مناسب است.

انتخاب k {\displaystyle {k}} یا k-selection مبتنی بر شعار زندگی آرام، تولید مثل آهسته و مرگ در پیری است و به‌طور کلی در نقطه مقابل الگوریتم انتخاب r است. این روش بیشتر در محیط‌های پایدار و قابل پیش‌بینی مورد استفاده قرار می‌گیرد. محیط‌هایی با بیشینهٔ سکنه و منابع بسیار محدود به طوری که امکان تولید مثل سریع در آن وجود ندارد و هر واحد برای بقا به تقویت خود می‌پردازد.

                                     

3. شبیه‌سازی رفتار علف‌ها

رفتار کلونی علف‌ها از الگوریتم زیر پیروی می‌کند:

  • محرومیت رقابتی: اگر علفی بدون فرزند بماند منقرض خواهد شد در غیر این صورت نماینده ای در نسل‌های بعد خواهد داشت و می‌تواند منابع را از آن خود کند؛ بنابراین به نوعی رقابت بر سر جمعیت و فرزندآوری نیازمندیم. که جمعیتمان از حد مشخصی بیشتر نشود. در مراحل اولیه اجرای الگوریتم علف‌ها به سرعت تولید مثل می‌کنند و در فضای مسئله پخش می‌شوند تا اینکه به محدودیت حداکثر جمعیت برسیم. از اینجا به بعد هر علف مطابق روال گفته شده دانه تولید می‌کند و در فضای پیرامون خود پخش می‌کند. سپس همهٔ دانه‌ها و علف‌ها در کنار هم ارزیابی می‌شوند و به اندازهٔ اضافه بر حداکثر جمعیت باید از جمعیت کم شود؛ بنابراین علف‌ها و دانه‌هایی با کمترین شایستگی حذف خواهند شد تا به حداکثر جمعیت برسیم. علف‌هایی با شایستگی بیشتر اجازه زنده ماندن و تولید مثل پیدا می‌کنند. همچنین این الگوریتم به علف‌هایی با شایستگی پایین امکان تولید مثل می‌دهد تا در صورتی که فرزندانش شایستگی بیشتری داشته باشند در کلونی زنده بمانند. این الگوریتم نوعی رقابت برای بقا و تولیدمثل بین علف‌ها ایجاد می‌کند که در نهایت شایسته‌ترین علف‌ها یا همان نزدیک‌ترین گزینه‌ها به جواب نهایی در کلونی می‌مانند.
  • پراکندگی ناحیه‌ای: دانه‌ها با توزیع نرمال با میانگین صفر و انحراف معیار σ {\displaystyle \sigma } توزیع می‌شوند. Δ x i ∼ N 0, σ t 2 {\displaystyle \Delta {x_{i}}\thicksim {N0,\sigma _{t}^{2}}} برای σ {\displaystyle \sigma } یک مقدار اولیه initial و یک مقدار نهایی final در نظر می‌گیریم. در ابتدا پراکندگی مقدار بیشتری دارد که با فرمول σ i t e r = i t e r m a x − i t e r n i t e r m a x n σ i n i t i a l − σ f i n a l + σ f i n a l {\displaystyle \sigma _{iter}={\dfrac {iter_{max}-iter^{n}}{iter_{max}^{n}}}\sigma _{initial}-\sigma _{final}+\sigma _{final}}) به سمت پراکندگی کمتر می‌رود. این فرمول میزان پراکندگی در هر مرحله را نشان می‌دهد. در اینجا به صورت پیوسته تغییر سیاست بقا از انتخاب r {\displaystyle {r}} به انتخاب k {\displaystyle {k}} را مشاهده می‌کنیم.
  • تولید جمعیت اوّلیهInitializing a Population: یک مجموعه از جواب‌های اولیه به صورت تصادفی در فضای مسئله پخش می‌شوند.
  • تولید مثل: هر دانه متناسب با شایستگی خود تولید مثل می‌کند. از آنجا که الگوریتم علف هرز مهاجم از جمله الگوریتم‌های تکاملی می‌باشد، با توزیع بیشتر دانه در فضای نزدیک‌تر به جواب نهایی ما کمک می‌کنند که به حلّ مسئله نزدیک‌تر شویم. هرچقدر دانه‌ها به جواب نهایی نزدیک تر باشند شایستگی آن‌ها بیشتر است و برای ما با ارزش تر محسوب می‌شوند. دانه‌ها یا به‌طور کلی گونه‌هایی که شایستگی بیشتری دارند، برای تولید مثل انتخاب می‌شوند؛ هر چند این فرصت به گونه‌های با شایستگی کمتر نیز داده می‌شود تا تولید مثل کنند و فرصت بقا داشته باشند. همچنین تولیدمثل برای هر علف از فرمول مقابل بدست می‌آید: S = } که در آن S m i n {\displaystyle {S}_{min}} ، حداقل دانه تولیدی و S m a x {\displaystyle {S}_{max}} حداکثر دانه تولیدی است؛ همچنین f m i n {\displaystyle {f}_{min}} کمترین شایستگی و f m a x {\displaystyle {f}_{max}} بیشترین میزان شایستگی و f {\displaystyle {f}} شایستگی علف مورد نظر است.
                                     

4. منابع

  • Dawkings, 1999, Dekker, Jack, 2005. Course works of Agronomy 517: a course on the biology and evolutionary ecology of invasive weeds
  • A novel numerical optimization algorithm inspired from weed colonization