که هر کدام از بخشی از فرایند ایمنی الگوبرداری شدهاند در طی سالها ایجاد شده است. در یک تقسیمبندی کلی الگوریتمهای ایمنی ارائه شده را میتوان در سه دسته الگوریتم ایمنی تولید انتخابی97، شبکه ایمنی98 و جستجوی منفی99 تقسیم کرد. الگوریتم ایمنی مصنوعی با رویکرد تولید انتخابی عموما در مسائل تعیین توالی بهینه و زمانبندی مورد استفاده قرار میگیرد حال آنکه دو رویکرد بعدی عموما برای مسائل تشخیص عوامل مخرب و مسائل خوشهبندی100 یا جستجوی الگو101 مورد استفاده قرار میگیرند. در تحقیق پیش رو نیز رویکرد تولید انتخابی الگوریتم ایمنی مصنوعی مورد استفاده قرار گرفته است لذا از این پس عبارت الگوریتم سیستم ایمنی مصنوعی به اختصار به جای عبارت رویکرد تولید انتخابی الگوریتم سیستم ایمنی مصنوعی به کار میرود.
الگوریتم سیستم ایمنی مصنوعی فرایند جستجوی خود را با جامعهای از آنتیبادیهای تصادفی که در واقع نشان دهنده جوابهای شدنی هستند آغاز میکند. در الگوریتم ایمنی مصنوعی آنتیژن تابع هدف را نمایندگی میکند. لذا هر کدام از جوابها از نظر میزان تطابق102 با تابع هدف مورد ارزیابی قرار میگیرند و در نهایت جوابها براساس میزان تطابقشان با تابع هدف که همان میزان برازندگی103 در الگوریتم ژنتیک است مرتب میشوند. پس از آن تعدادی مشخص از بهترین جوابها انتخاب شده و براساس رابطهای که بسته به نوع مسئله تعریف میشود، از هر جواب بسته به میزان تطابق آن تکثیر104 میشود. یعنی هرچه تطابق بیشتر باشد تعداد تکثیر نیز بیشتر میشود. در مرحله بعد هر جواب بسته به میزان تطابق خود تحت عملگر جهش105 قرار میگیرد، یعنی هر چه تطابق یک جواب بیشتر باشد میزان جهش کمتر خواهد بود. در نهایت میزان تطابق جوابهای جهش یافته بررسی شده و به تعدادی که در مراحل قبل بهترین جوابها برگزیده شده بودند، از بهترین جوابهای جهش یافته برداشته میشود و با همان تعداد از بدترین جوابهای جامعه مرجع جایگزین میگردد. این رویه تا فرارسیدن شروط توقف106 ادامه مییابد.
الگوریتم سیستم ایمنی مصنوعی به دلیل ساختار خود نقاط قوتی را در مقابل سایر الگوریتمها دارا است. از آنجا که این الگوریتم همزمان دستهای از جوابها را مورد بررسی قرار میدهد توانایی جستجوی همزمان نقاط متفاوتی از فضای حل را دارا میباشد و این مسئله توانایی الگوریتم برای رسیدن به بهینه کلی را افزایش داده و از به دام افتادن الگوریتم در بهینه موضعی جلوگیری میکند. به علاوه از آنجا که این الگوریتم فاقد عملگر تقاطع107 است در شرایط مساوی سرعت بالاتری نسبت به الگوریتم ژنتیک داشته و نیز از آنجا که عملگرهای بازتولید و جهش نیز در این الگوریتم تابعی از میزان تطابق جواب هستند سرعت همگرایی آن نسبت به الگوریتم ژنتیک بیشتر است.
4-2-1. شمای کلی الگوریتم سیستم ایمنی مصنوعی
فرایند اجرای الگوریتم تولید انتخابی سیستم ایمنی مصنوعی مطابق شبه برنامه زیر است:
تولید جامعه اولیه آنتیبادیها(جوابها) به صورت تصادفی.
محاسبه میزان تطابق جوابهای تولید شده با آنتیبادی(تابع هدف) و مرتب کردن جامعه اولیه براساس میزان تطابق جوابها.
انتخاب تعدادی مشخص از بهترین جوابها.
تکثیر جوابهای انتخاب شده براساس میزان تطابق آنها.
اعمال جهش روی جوابهای تکثیر شده.
محاسبه میزان تطابق جوابهای جهش یافته با تابع هدف و مرتبسازی آنها براساس میزان تطابق.
جایگزین کردن تعدادی مشخص از بهترین جوابهای تولید شده با بدترین جوابهای جامعه جاری.
بررسی شروط توقف. چنانچه شرط توقف برقرار نبود، مرحله 2.
4-2-2. مفاهیم الگوریتم تولید انتخابی سیستم ایمنی مصنوعی و نحوه بکارگیری آنها
هر رویه حل شامل اصول و مفاهیمی است که فرایند جستجو را تشکیل میدهند. مفاهیم پایهای الگوریتم سیستم ایمنی مصنوعی به شرح زیر است:
کدگذاری108 جواب
تولید جامعه اولیه
تابع تطابق
عملگر تکثیر
عملگر جهش
شروط توقف
4-2-2-1. کدگذاری جواب
به نحوه نمایش جواب در هر الگوریتم کدگذاری جواب میگویند. کدگذاری باعث افزایش کارایی الگوریتم و امکان انجام روانتر و کاراتر عملگرهای الگوریتم را بر جواب فراهم میکنند. معمولا کدگذاری به یکی از روشهای ترتیبی، ارزشی و یا درختی انجام میشود که بسته به نوع مسئله هر یک میتوانند مزایا و معایب خود را داشته باشند. اما ممکن است روشهای جدید دیگری نیز برای کدگذاری در مسئلهای خاص مورد استفاده قرار بگیرد. اصلیترین نکته در انتخاب یک روش کدگذاری تولید جواب موجه109 توسط آن روش کدگذاری است به طوریکه پس از اعمال عملگرها، جواب از حالت موجه خارج نشود. در صورتی که چنین چیزی امکانپذیر نباشد باید مرحله اصلاح جواب کدگذاری شده و برطرف کردن مسئله ناموجه بودن آن به فرایند الگوریتم اضافه شود. بدیهی است که افزودن چنین مرحلهای از کارایی الگوریتم خواهد کاست. در حالت کلی روشهای کدگذاری در الگوریتم سیستم ایمنی مصنوعی شبیه به الگوریتم ژنتیک است با این تفاوت که رشته جواب در الگوریتم ژنتیک کروموزوم110 نامیده میشود در حالی که این رشته در الگوریتم سیستم ایمنی مصنوعی آنتیبادی نام دارد.
روش کدگذاری انتخاب شده برای مسئله مورد بررسی روشی مستقیم و مبتنی بر روش ترتیبی است. منظور از مستقیم این است که هر رشته جواب اطلاعات کامل یک جواب را ارائه میدهد و هر بخش از رشته با بخشی از جواب متناظر است.
پیش از این در فصول دو و سه به طور مفصل به تشریح ویژگیهای مسئله پرداخته شده است. هر بس
ته سفارشی پس از پذیرفته شدن باید برای پردازش برنامهریزی شود. بنابراین هر کار موجود در بسته سفارشی تایید شده دارای سه ویژگی است که باید در رشته جواب آورده شوند: شماره کار در بسته سفارشی، نوع محصول آن و شماره بسته سفارشی. برهمین اساس کدگذاری جواب در مسئله مورد بررسی مطابق شکل زیر است.
شکل(4-1) نحوه نمایش جواب حالتی از مسئله است که در آن 3 بسته سفارشی به کارخانه تحویل شده است. بستههای شماره 1و3 رد شدهاند و تنها بسته شماره 2 و تولیدات ثابت کارخانه باقی مانده است. در چنین حالتی سطر اول ماتریس جواب، نشان دهنده شماره هر کار در سفارش مربوط به خود است. سطر دوم نوع محصول آن کار را نشان میدهد، در این مثال سیستم تولیدی حداقل توان تولید سه نوع محصول را دارد و در نهایت سطر آخر شماره بسته سفارشی آن کار را مشخص میکند. برای سهولت در کدنویسی، کارهای ثابت کارخانه شماره سفارش n+1 را به خود میگیرند که در آن n تعداد بستههای سفارشی را نشان میدهد. در نتیجه این نحوه کدگذاری، هر ستون از ماتریس جواب، اطلاعات یک کار را ارائه میدهد.
4-2-2-2. تولید جامعه اولیه
(4-1)
maxgen=size ofsolution×10
تولید جامعه اولیه مرحلهای مشترک بین تمامی الگوریتمهایی است که روش جستجوی برپایه جمعیت دارند. جامعه اولیه که دارای تعدای مشخص از جوابها است اغلب به صورت تصادفی تولید میشود مگر اینکه رویه متفاوتی برای آن تعریف شده باشد. در این الگوریتم نیز ابتدا بستههای تایید شده تعیین شده و سپس جوابهایی تصادفی برپایه همین بستهها تولید شده و به عنوان جامعه اولیه در نظر گرفته میشوند. این رویکرد که ابتدا فضای حل مسئله به تمامی حالات ممکن برای پذیرش بستههای سفارشی افراز111 میشود یکی از نوآوریهای پژوهش پیش رو است و باعث جستجوی دقیقتر هر بخش میگردد. برای مثال اگر تعداد بستههای سفارشی سه عدد باشد، فضای حل به 23 یعنی 8 بخش افراز میشود(شکل 4-2). در واقع گویی برای هر بخش یک بار الگوریتم سیستم ایمنی مصنوعی اجرا میگردد. از آنجا که با افزایش تعداد بستههای سفارشی پذیرفته شده فضای حل آن بخش نیز گستردهتر میگردد، تعداد تکرارهایی که به عنوان شرط توقف در نظر گرفته میشود نیز با افزایش تعداد بستههای سفارشی پذیرفته شده افزایش مییابد. جهت پیادهسازی این مفهوم، تعداد تکرارهای الگوریتم در هریک از افرازهای فضای حل توسط رابطه زیر محاسبه میگردد:
در این رابطه، maxgen تعداد تکرارها را نشان میدهد و size ofsolution مجموع کارهای موجود در سفارشات پذیرفته شده را محاسبه میکند(با احتساب کارهایی که جهت ذخیرهسازی تولید میشوند).
همانطور که در شکل(4-2) مشاهده میشود به دلیل اینکه تولیداتی که به منظور ذخیره در انبار تولید میشوند همیشه جز ثابت زمانبندی تولید هستند، لذا در حالتی که هیچ یک از سفارشات پذیرفته نشوند نیز بخشی از فضای حل به تولیدات ثابت تخصیص مییابد.

مطلب مرتبط :   پایان نامه با کلمات کلیدیسلسله مراتب، استان اصفهان، ورزشکاران

4-2-2-3. تابع تطابق
تابع تطابق در الگوریتم ایمنی مصنوعی یا معادل آن تابع برازندگی در الگوریتم ژنتیک معیار سنجش کیفیت جوابها در الگوریتم است. هر چه تابع تطابق عدد بزرگتری را نشان دهد نشان از بهتر بودن جواب دارد. در مسائل با تابع هدف ماکزیممسازی تابع تطابق را میتوان همان تابع هدف در نظر گرفت اما در مسائل مینیممسازی، تابع تطابق عموما تابعی از تابع هدف مسئله است به گونهای که بتواند ارزش آن را معکوس کند. برهمین اساس، تابع تطابق در تحقیق پیش رو به صورت وارون تابع هدف تعریف شده است (تطابق تابع=1⁄(هدف تابع)). بر طبق این عبارت تابع هدف کوچکتر مقدار تابع تطابق بزرگتر را نتیجه میدهد.
4-2-2-4. عملگر تکثیر
عملگر تکثیر در الگوریتم سیستم ایمنی مصنوعی وظیفه تکثیر بهترین جوابهای جامعه را در هر تکرار بر عهده دارد. برخلاف الگوریتم ژنتیک، عمل تکثیر در الگوریتم سیستم ایمنی مصنوعی تابعی از میزان تطابق جواب است. به عبارت بهتر، هرچه تطابق یک جواب با تابع هدف بیشتر باشد، به طور طبیعی خواهان آن خواهیم بود که تاثیر آن جواب در فرایند جستجو را افزایش داده و مسیر جستجو را به سمت آن جواب سوق دهیم. اینکار در الگوریتم سیستم ایمنی مصنوعی توسط دو عملگر تکثیر و جهش انجام میشود که در مورد عملگر دوم در بخش بعد توضیح داده میشود اما عملگر تکثیر با افزایش تعداد تکثیر از آن جواب تاثیر آن را در فرایند جستجو افزایش میدهد. به منظور پیادهسازی این مفهوم، جوابهای انتخاب پس، پس از انتخابطابقرین جوابز آن جواب تاثیر آن را در فرایند جستجو افزایش میسیر جستجو را به سمت آن جواب سوق دهیم. اینشده به ترتیب میزان تطابق مرتب میشوند به طوریکه بهترین جواب اول قرار بگیرد. پس از آن از هر جواب به اندازه(n_c-k+1) عدد تکثیر میشود. در این عبارت n_c تعداد جوابهای انتخاب شده است و k شماره هر جواب پس از مرتبسازی است، برای مثال شماره بهترین جواب 1 است. طبق این عبارت از جوابهای بهتر به میزان بیشتری تکثیر میشود و در مجموع تعداد جوابهای تکثیر شده برابر با ( (n_c×(n_c+1))/2) خواهد بود.
4-2-2-5. عملگر جهش
یکی از گامهای اساسی در فرایند جستجوی اغلب الگوریتمهای فراابتکاری تولید جواب همسایگی است. این فرایند امکان حرکت در فضای جواب را فراهم میآورد. نحوه حرکت، طول گام و سایر مشخصات حرکت از عوامل بسیار تاثیرگذار در کارایی الگوریتم هستند. وظیفه تولید جواب همسایگی در الگوریتم سیستم ایمنی مصنوعی بر عهده عملگر جهش است. جهش عبارت است از تغییری نسبتا کوچک در بخشی از جواب. این عملگر عموما به یکی از روشهای رایج اعمال جهش در الگوریتم
ژنتیک نظیر انتقال112، جابجایی113 یا معکوسسازی114 عمل میکند. تنها تفاوت آن با الگوریتم ژنتیک که اتفاقا تاثیر نسبتا زیادی بر کارایی آن دارد شدت اعمال آن است. در الگوریتم سیستم ایمنی مصنوعی شدت اعمال جهش بر روی یک جواب تابعی از میزان تطابق آن جواب با تابع هدف است، به این معنا که هرچه میزان تطابق بیشتر باشد به طور طبیعی تمایل به ایجاد تغییر در آن جواب کاهش مییابد.
جهت پیادهسازی این مفاهیم در تحقیق پیش رو، از دو رویه رایج اعمال جهش به نامهای انتقال و جابجایی با احتمال برابر استفاده شده است که عبارتند از:
عملگر انتقال: دو ستون از ماتریس جواب به تصادف انتخاب میشوند و ستون اول به مکان بعد از ستون دوم انتقال مییابد.
عملگر جابجایی: دو ستون از ماترس جواب به تصادف انتخاب میشوند و هرکدام به محل دیگری منتقل میگردد.
عملگر جهش در الگوریتم سیستم ایمنی مصنوعی بر روی تمامی جوابهایی تکثیر شده در مرحله عملگر تکثیر(4-2-2-4) اعمال میگردد. از آنجا که هر جواب تکثیر شده میزان انطباقی دقیقا برابر با والد خود دارد لذا به محاسبه دوباره مقادیر انطباق نیازی نیست و تنها باید جوابهای تکثیر شده را براساس میزان انطباقشان مرتبسازی کرد.
برای هر جواب تکثیر شده فرایند زیر طی میشود:
چنانچه جواب انتخاب شده در نیمه اول جوابهای تکثیر شده قرار داشت(جز 50% جوابهای بهتر بود)، مراحل دو تا سه به تعداد 3/1(یک سوم) سایز جواب انجام شود و در غیر اینصورت به تعداد 2/1(یک دوم) سایز جواب(سایز جواب یعنی تعداد کارهای موجود در آن جواب).
یکی از روشهای انتقال یا جابجایی اعمال شود.
چنانچه دفعات اعمال جهش به تعداد مورد نظر نرسیده باشد، مرحله دو، در غیر اینصورت توقف.
محاسبه تابع انطباق.
لازم به ذکر است که اعداد 2/1 و 3/1 اشاره شده در مرحله 1 طی آزمونهای تجربی و با سعی و خطا تعیین شدهاند.
4-2-2-6. شروط توقف
معیار یا معیارهای توقف جز مشترک تمامی الگوریتمهای فراابتکاری است. معیارهای توقف شرایطی را که در صورت براورده شدن آنها الگوریتم از ادامه کار بازمیایستد را تعیین میکنند. این شرایط عموما به سه صورت زیر مطرح میگردند:
تعداد تکرار مشخص
زمان پردازش مشخص
تعداد تکرار یا مدت زمان مشخصی که در آن الگوریتم نتواند در جواب بهبودی حاصل کند.
از آنجا که با توجه به توضیحات داده شده در بخش(4-2-2-2)، با افزایش تعداد بستههای سفارشی پذیرفته شده فضای جواب نیز گسترش مییابد، لذا لازم است معیار توقف نیز به گونهای تعیین گردد که امکان جستجوی بیشتر را برای فضاهای حل بزرگتر فراهم کند. بر همین اساس معیار توقف تعیین شده در پیادهسازی این الگوریتم تعداد تکرار در نظر گرفته شده است. تعداد تکرار در هر افراز از فضای جواب مطابق عبارت زیر تعیین میگردد.
(4-2)
iteration=size of solution×10
در این عبارت iteration تعداد تکرار به ازای هر افراز فضای حل را نشان میدهد، size of solution مجموع تعداد کارهای سفارشات پذیرفته شده و کارهای تولید برای ذخیره را نشان میدهد.
لازم به ذکر است که عبارت فوق(4-2) به کمک سعی و خطا و بررسی نمودارهای همگرایی و شرایط مختلف حاصل شده است.
شبه برنامه الگوریتم سیستم ایمنی مصنوعی پیادهسازی شده برای مسئله مورد بحث در شکل (4-3) ارائه شده است.
4-3. الگوریتم تبرید شبیهسازی شده با رویکرد ابری
الگوریتم تبرید شبیهسازی شده یک روش جستجوی تصادفی است که بر اساس استراتژی تکرار مونت کارلو115 عمل

مطلب مرتبط :   دانلود مقاله با موضوعارزیابی عملکرد، تابع تولید، تئوری فازی، قابلیت مقایسه

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