الگوریتم جستجوی کلونی ویروس — Virus Colony Search

این پست آموزشی، یک الگوریتم ساده و قدرتمند به نام الگوریتم جستجوی کلونی ویروس یا الگوریتم VCS را معرفی خواهد کرد که با استفاده شبیه سازی قواعد حاکم بر عفونت ویروس، استراتژی‌های انتشار برای سلول‌های میزبانی که می‌خواهند زنده بمانند و نحوه انتشار هر کدام از آن‎ها در محیط سلول، انواع مسائل بهینه سازی را حل کرده؛ در حداقل زمان و با صرف حداقل هزینه یا انرژی، رویکرد بهینه مسئله را ارائه می‌دهد. اگر علاقمند هستید تا در مورد الگوریتم VCS بیشتر بدانید؛ در ادامه، با ما همراه باشید.

مقدمه مقاله الگوریتم جستجوی کلونی ویروس

دوستان عزیز، بهینه سازی مبحثی است که امروزه، مورد توجه تمام علوم، از جمله مهندسی، اقتصاد و تجارت قرار گرفته است. چرا که در طول فرآیند طراحی تا اجرای پروژه‌های پیچیده عملی، انواع مسائل Np-hard پیش می‌آید که فقط و فقط به کمک هر کدام از الگوریتم های متاهیوریستیک، می‌توان آن‌ها را حل کرد. مسائلی که با روش‌های اکتشافی کلاسیک، اگر قابل حل باشند؛ باز هم با در نظر گرفتن قواعد بهینه سازی یعنی صرف حداقل هزینه و زمان، دقیق نیستند یا در حال کلی، قابل حل نمی‌باشند.

در معرفی‌های قبلی هم، به این نکته اشاره شد که با رجوع به مکانیسم‌ها و ساز و کارهای طبیعی و اصول یا مفاهیم حاکم بر جهان هستی، می‌توان روش‌های محاسباتی مصنوعی بهینه‌ای تولید کرد که در حل مسائل سخت و پیچیده انواع پروژه‌های علمی و عملی که اغلب غیرقابل حل به نظر می‌رسند؛ استفاده شوند.

خوشبختانه محققان با تکیه بر این اصل، تا امروز یعنی تا اواسط سال ۲۰۲۲، الگوریتم‌های الهام‌گرفته از طبیعت یا (Nurture Inspired | NI) را بررسی کرده و توسعه داده‌اند. به نحوی که در هر کدام از الگوریتم‌های موجود، تقلید از پدیده‌ها یا رفتارهای خاص طبیعت برای مسائل مختلف بهینه‌سازی کاملاً مشهود و قابل لمس می‌باشد.

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

الگوریتم جستجوی کلونی ویروس Virus Colony Search | VCS

در این بخش، برای جلوگیری از سردرگمی شما دوستان عزیز، یک دید کلی از این الگوریتم را ارائه می‌‎دهیم. به این ترتیب که برای توضیح الگوریتم VCS می‌توان گفت این الگوریتم رفتارهای عفونت و انتشار بین ویروس‌ها و سلول‌های میزبان را در محیط سلول شبیه سازی می‌کند. چرا که ویروس برای زنده ماندن و تکثیر باید بر روی سلول میزبان با رفتارهای انتشار و عفونت سکنی گزیند و به این ترتیب، رفتار تکاملی ویروس همیشه در طول فرآیند انطباق با محیط سلولی در حال تغییر، رخ می‌دهد.

پاورپوینت الگوریتم جستجوی کلونی ویروس — Virus Colony Search

کلیک کنید

ویروس چیست؟

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

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

رفتار ویروس در سلول میزبان

همراهان گرامی، همه ما این وضعیت را تجربه کرده‌ایم. امان از زمانی که یک سلول میزبان برای ویروس پیدا شود. دقیقاً عین پاتَک دشمن در زمان جنگ می‌ماند؛ به نحوی که ویروس آن محدوه را آلوده کرده و از بین می‌برد. به بیان دیگر، فرآیند عفونت در سلول میزبان اتفاق می‌افتد.

جالب است بدانید که یک ویروس، تا زمان مرگ سلول میزبان، می‌تواند در داخل آن زنده مانده و خود را تکثیر کند. پس از طی شدن فرآیند عفونت در داخل سلول میزبان، آن سلول جهش یافته شده؛ تبدیل به یک ویروس با فرآیند تولید مثل می‌شود و با الهام از استراتژی‌های تکاملی با الگوریتم تطبیق ماتریکس کوواریانس یا CMA-ES، برای تولید ویروس‌های جدید واقعی ساخته می‌شود.

در این مرحله، یک سؤال مهم برای بیشتر دانشجویان پیش می‌آید و آن هم این است که در این میان، نقش سیستم ایمنی میزبان چیست؟ باید به اطلاع تان برسانم؛ درست است که سیستم ایمنی بدن، وظیفه محافظت از سلول میزبان در برابر عفونت یا تخریب را بر عهده دارد ولی ویروس‌هایی که توانایی بهتری دارند و قوی‌تر عمل کرده‌اند؛ برای نسل بعدی ذخیره می‌شوند. در غیر این صورت است که توسط سیستم ایمنی میزبان، حذف خواهند شد.

قوانین حاکم بر الگوریتم جستجوی کلونی ویروس

به بخش اصلی الگوریتم جستجوی کلونی ویروس، رسیده‌ایم. درحالت کلی، الگوریتم متاهیوریستیک VCS از سه استراتژی اساسی و مهم تشکیل شده است که در ادامه به آن‌ها اشاره خواهد گردید.

1. روش گام تصادفی گاوسی برای انتشار ویروس جهت بهبود ویژگی‌ها.
2. عملیات CMA-ES برای عفونت سلول‌های میزبان جهت افزایش عملکرد اکتشاف.
3. استراتژی تکامل برای پاسخ ایمنی جهت استفاده کامل از ویروس‌های بدتر برای بهبود کارایی جستجو.

به زبان ساده، عملکرد الگوریتم VCS در فرآیند یافتن پاسخ بهینه مسائل مورد بررسی، با تبعیت از پنج قانون ساده، انجام می‌شود:

1. در ابتدا، دو گروه مختلف کلونی ویروس Vpop و کلونی سلول میزبان Hop، مورد استفاده قرار می‌گیرند.
2. هر ویروس، در طول فرآیند انتشار، یک عضو تصادفی جدید ایجاد خواهد نمود.
3. هر ویروس، باید یک سلول میزبان را آلوده کند.
4. تکثیر هر ویروس بر اساس تخریب سلول میزبان برای به دست آوردن مواد مغذی است و باید انجام گیرد.
5. آخرین قانون هم تعیین می‌کند که با توجه به محافظت سیستم ایمنی میزبان، بهترین ویروس‌ها در هر نسل باقی بمانند و بقیه ویروس‌ها هم باید به تکامل برسند تا به حیات خود ادامه دهند؛ در غیر این صورت، از بین خواهند رفت.

فرآیند انتشار ویروس

با اندکی تحقیق در محیط اطرافمان، به این نکته پی خواهیم برد که ویروس‌ها در برخی از محیط‌های خاص مانند هوا، آب یا سیستم‌های گردش خون گروهی از ارگانیسم‌ها وجود دارند و زندگی می‌کنند. فعالیت اصلی ویروس در این مرحله، همان پدیده راه رفتن تصادفی که در برخی محیط‌‌ها رخ می‌دهد؛ است و تا زمانی که سلول میزبان را جستجو کند؛ این پدیده، ادامه پیدا خواهد کرد. شاید از خودتان بپرسید که چرا راه رفتن تصادفی؟! در پاسخ به این سؤال باید بگویم که برای بهبود عملکرد بهره برداری و اجتناب از بهینه محلی، این روش انتخاب شده و انتشار ویروس‌ها به صورت زیر، به وسیله محققان این حوزه، فرموله گردیده است.

در فرمول بالا، i شاخص تصادفی انتخاب شده و مقدار آن در بازه اعداد طبیعی تعریف می‌شود. در واقع می‌توان گفت که N، اندازه جمعیت است. در ادامه، G بهترین راه حل نسل g فرض گردیده و r و r2 مقادیر تصادفی انتخاب شده از [۰، ۱] می‌باشند.

فرآیند شکل گیری عفونت در سلول میزبان

بله دوستان عزیز! به بررسی فرآیند دردناک طبیعت، می‌پردازیم. واقعیت اصلی در مورد ویروس این است: هنگامی که یک سلول میزبان آلوده شود؛ تا زمان مرگ توسط ویروس مورد حمله قرار گرفته و از بین می‌رود. در واقع، این فرآیند را می‌توان به عنوان فرآیند روابط متقابل، این گونه توضیح داد که سلول میزبان عناصر ضروری را فراهم می‌کند و ویروس به جای آن، مواد مضر را متابولیزه می‌نماید تا منجر به مرگ سلول میزبان شود اما در نهایت، سلول میزبان به یک ویروس جدید جهش می‌یابد.

روش CMA-ES یک الگوریتم تکاملی است که طی آن، نه تنها جهش انجام می‌گیرد؛ بلکه روابط تعاملی بین افراد با سازگاری ماتریس کوواریانس یا CMA در نظر گرفته می‌شود. فراموش نشود که یک ماتریس کوواریانس کامل، از یک توزیع نرمال جستجو یا جهش، تطبیق می‌یابد. بنابراین، این روش برای توصیف رفتار میزبان کاملاً مناسب بوده و به منظور انعکاس روابط متقابل بین ویروس‌ها و سلول‌های میزبان، مراحل اصلی آن را می‌توان به صورت زیر، تعریف کرد:

پاسخ سیستم ایمنی

با توجه به عملکرد سیستم ایمنی سلول میزبان، ویروس‌هایی که عملکرد بهتری دارند؛ توانایی خود را برای نسل بعدی حفظ خواهند نمود اما باز هم این امکان وجود دارد که ویروس‌های بدتر هم جان سالم به در ببرند به این ترتیب، خود را به تکامل برسانند تا از قافله جا نمانده و بتوانند به بقای خود ادامه دهند. در ادامه، مراحل زیر برای درک تکامل ویروس‌ها آورده شده است.

• رتبه‌های عملکرد Pr را با توجه به ارزش تناسب در کلونی ویروس Vpop محاسبه خواهد شد.

در جایی که N اندازه جمعیت Vpop است؛ رتبه i به معنای رتبه تناسب اندام نفر iام در مرحله از Vpop است.

• در ادامه، افراد Vpop را با رعایت کردن قواعد زیر، بروز رسانی خواهیم کرد.

در نظر داشته باشید که مکانیسم‌های تولید جمعیت جدید که توسط فرآیندهای رفتاری بالا به دست آمده است؛ ممکن است به عبور از مرز جستجو منجر شود. بنابراین، روش بررسی مرز برای کنترل مرز جستجو، استفاده می‌شود. که در آن Up و Low به ترتیب کران‌های بالا و پایین هستند.

الگوریتم جستجوی کلونی ویروس

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

برای فهم بیشتر این الگوریتم، باید به اطلاع تان برسانم که در طول فرآیند پیاده سازی VCS، در هر نسل و برای هر ویروس، یک بردار انتشار ویروس Vpop’i با روش پیاده‌روی تصادفی گاوسی تولید می‌شود. سپس مرزهای جستجوی جمعیت جدید مورد بررسی قرار گرفته و Vpop بر اساس مقادیر تابع هدف بروز رسانی می‌گردد. پس از آن، ناقل عفونت سلول میزبان Hpop توسط افراد Vpop ایجاد شده و بهترین افراد برای محاسبه X و سایر پارامترها طبق روش CMA-ES انتخاب خواهند شد.

در ادامه، محدوده جستجوی جمعیت جدید بررسی شده و V بروز رسانی خواهد گردید. در نهایت، فرآیند پاسخ ایمنی، به تکامل ویروس‌ها کمک می‌کند و اگر رتبه افراد در Vpop بدتر از دیگران باشد؛ با احتمال بیشتری به تکامل رسیده و جهش خواهند یافت. همان طور که قبلاً هم گفته شد؛ پارامتر Pr، برای محاسبه رتبه‌های عملکرد استفاده می‌شود.

کلام آخر در رابطه با الگوریتم جستجوی کلونی ویروس

دوستان گرامی، در خلاصه آن‌چه گفته شد؛ می‌توان گفت که روش پیشنهاد شده، از سه رفتار اصلی و الهام گرفته شده از طبیعت، استفاده می‌نماید. این سه رفتار، عبارتند از: انتشار ویروس‌ها، عفونت سلول‌های میزبان و پاسخ ایمنی. در ابتدا، هر ویروس در داخل کلونی، وظیفه انتشار را ایفا می‌کند.

فرآیندی که با روش پیاده‌روی تصادفی گاوسی برای تولید ویروس جدید و در اطراف موقعیت فعلی خود انجام می‌‌گردد. سپس، فرآیند عفونت سلول میزبان را بر اساس روش CMA-ES شبیه سازی نموده و در آخرین مرحله، با ایجاد برخی ویروس‌های بدتر بر اساس رویکرد آماری، پدیده‌های پاسخ ایمنی سیستم سلول میزبان را تقلید می‌‍کند.

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