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

مهاجم (^[۱]به انگلیسی Forward)

معرفی[ویرایش]

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

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

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

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

تولید مثل علف‌ها[ویرایش]

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

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

انتخاب ${r}$ (یا r-selection) با شعار زندگی سریع، تولید مثل فوری و مرگ در جوانی است. یکی از راهکارهای حفظ بقا است که در محیط‌های ناپایدار و غیرقابل پیش‌بینی و به‌طور کلی هر جایی که توانایی برای تولید مثل سریع در حالت بیشینه است و منابع محدود است، مناسب است.^[۲]

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

شبیه‌سازی رفتار علف‌ها[ویرایش]

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

تولید جمعیت اوّلیه(Initializing a Population): یک مجموعه از جواب‌های اولیه به صورت تصادفی در فضای مسئله پخش می‌شوند.
تولید مثل: هر دانه متناسب با شایستگی خود تولید مثل می‌کند. از آنجا که الگوریتم علف هرز مهاجم از جمله الگوریتم‌های تکاملی می‌باشد، با توزیع بیشتر دانه در فضای نزدیک‌تر به جواب نهایی ما کمک می‌کنند که به حلّ مسئله نزدیک‌تر شویم. هرچقدر دانه‌ها به جواب نهایی نزدیک تر باشند شایستگی آن‌ها بیشتر است و برای ما با ارزش تر محسوب می‌شوند. دانه‌ها یا به‌طور کلی گونه‌هایی که شایستگی بیشتری دارند، برای تولید مثل انتخاب می‌شوند؛ هر چند این فرصت به گونه‌های با شایستگی کمتر نیز داده می‌شود تا تولید مثل کنند و فرصت بقا داشته باشند.
تولیدمثل دانه‌ها بر حسب میزان شایستگی
همچنین تولیدمثل برای هر علف از فرمول مقابل بدست می‌آید: ${S}=[{S_{min}+({S_{max}-S_{min}})}\times {\frac {{f}-{f_{worst}}}{f{best}-f_{worst}}}]$ که در آن ${S}_{min}$ ، حداقل دانه تولیدی و ${S}_{max}$ حداکثر دانه تولیدی است؛ همچنین ${f}_{min}$ کمترین شایستگی و ${f}_{max}$ بیشترین میزان شایستگی و ${f}$ شایستگی علف مورد نظر است.
پراکندگی ناحیه‌ای:دانه‌ها با توزیع نرمال با میانگین صفر و انحراف معیار $\sigma$ توزیع می‌شوند. $\Delta {x_{i}}\thicksim {N(0,\sigma _{t}^{2})}$ برای $\sigma$ یک مقدار اولیه (initial) و یک مقدار نهایی (final) در نظر می‌گیریم. در ابتدا پراکندگی مقدار بیشتری دارد که با فرمول ( $\sigma _{iter}={\dfrac {(iter_{max}-iter)^{n}}{(iter_{max})^{n}}}(\sigma _{initial}-\sigma _{final})+\sigma _{final}$ ) به سمت پراکندگی کمتر می‌رود. این فرمول میزان پراکندگی در هر مرحله را نشان می‌دهد. در اینجا به صورت پیوسته تغییر سیاست بقا از انتخاب ${r}$ به انتخاب ${k}$ را مشاهده می‌کنیم.
تغییرات پراکندگی دانه از علف بر حسب زمان
محرومیت رقابتی: اگر علفی بدون فرزند بماند منقرض خواهد شد در غیر این صورت نماینده ای در نسل‌های بعد خواهد داشت و می‌تواند منابع را از آن خود کند؛ بنابراین به نوعی رقابت بر سر جمعیت و فرزندآوری نیازمندیم. که جمعیتمان از حد مشخصی بیشتر نشود. در مراحل اولیه اجرای الگوریتم علف‌ها به سرعت تولید مثل می‌کنند و در فضای مسئله پخش می‌شوند تا اینکه به محدودیت حداکثر جمعیت برسیم. از اینجا به بعد هر علف مطابق روال گفته شده دانه تولید می‌کند و در فضای پیرامون خود پخش می‌کند. سپس همهٔ دانه‌ها و علف‌ها در کنار هم ارزیابی می‌شوند و به اندازهٔ اضافه بر حداکثر جمعیت باید از جمعیت کم شود؛ بنابراین علف‌ها و دانه‌هایی با کمترین شایستگی حذف خواهند شد تا به حداکثر جمعیت برسیم. علف‌هایی با شایستگی بیشتر اجازه زنده ماندن و تولید مثل پیدا می‌کنند. همچنین این الگوریتم به علف‌هایی با شایستگی پایین امکان تولید مثل می‌دهد تا در صورتی که فرزندانش شایستگی بیشتری داشته باشند در کلونی زنده بمانند. این الگوریتم نوعی رقابت برای بقا و تولیدمثل بین علف‌ها ایجاد می‌کند که در نهایت شایسته‌ترین علف‌ها یا همان نزدیک‌ترین گزینه‌ها به جواب نهایی در کلونی می‌مانند.

شبه‌کد الگوریتم[ویرایش]

تصویر زیر فلوچارت الگوریتم را نشان می‌دهد:

همچنین شبه کد الگوریتم به صورت زیر است:

# W: is the count for the initializing population
# T: the maximum number of generations
initialize a random population
for  iter = 1 to T:
    w = objective function
    Compute maximum and minimum fitness in ecology
    for w in range(W) :
        compute the number of seeds of w, in response to its fitness
        distribute the generated seeds over the search space with normal distribution
        add generated seeds to the W
    if abs(W) > P_max:
        sort the W in descending order of their fitness
        truncate population of weeds whoose fitness are smaller

منابع[ویرایش]

↑ Mehrabian, A. R.; Lucas, C. (2006-12-01). "A novel numerical optimization algorithm inspired from weed colonization". Ecological Informatics (به انگلیسی). 1 (4): 355–366. doi:10.1016/j.ecoinf.2006.07.003. ISSN 1574-9541.
↑ ^۲٫۰ ^۲٫۱ Jack Dekker (12 December 2008). "The Evolutionary Ecology of Weeds and Invasive Plants" (PDF) (به انگلیسی). Archived from the original (PDF) on 23 February 2009.

[1] Mehrabian, A. R.; Lucas, C. (2006-12-01). "A novel numerical optimization algorithm inspired from weed colonization". Ecological Informatics (به انگلیسی). 1 (4): 355–366. doi:10.1016/j.ecoinf.2006.07.003. ISSN 1574-9541.

[:0-2] ۲٫۰ ^۲٫۱ Jack Dekker (12 December 2008). "The Evolutionary Ecology of Weeds and Invasive Plants" (PDF) (به انگلیسی). Archived from the original (PDF) on 23 February 2009.

[۱]

[۲]