اینم یه تجربه پراکنده دیگه!
من اگه خدا قبول کنه سالها پیش فوق لیسانس خوندم و کلی پروژه به درد بخور و به درد نحور انجام دادم که بعد از فوق خیلی دوست داشتم اونها رو یه جایی به اشتراک بگذارم ولی نشده. حالا تصمیم گرفتم اولینش رو که در مورد الگوریتم bfso هست اینجا بگذارم که در پاییز ۸۸ برای پروژه درس هوش مصنوعی پیشرفته
ارائه اش کردم. این شما و اینم اولین گزارش پروژه
چکیده:
بهینه‌سازی تجمعی غذایابی باکتری‌ها۱ به عنوان یک الگوریتم بهینه‌سازی عمومی شناخته شده و در زمینه بهینه‌سازی توزیع شده و کنترل کاربرد دارد. این الگوریتم از رفتار غذایابی اجتماعی باکتری ای کویل۲ الهام گرفته شده است. این روش در حال حاضر مورد توجه محققان زیادی قرار گرفته است. این محبوبیت بخاطر قدرت الگوریتم در حل مسائل بهینه‌سازی واقعی است که در کاربردهای گوناگون با آنها روبرو هستیم. مسائل بیولوژیک رفتار غذایابی این باکتری بصورت خاصی تقلید شده و الگوریتم ساده ای برای بهینه سازی پیشنهاد شده است. در این گزارش بصورت ساده و روشن به بررسی این الگوریتم پرداخته و سپس این الگوریتم را برای مسائل بهینه سازی با یک یا چند روش بهینه سازی دیگر مقایسه می‌شود.
۱- مقدمه
الگوریتم بهینه‌سازی تجمعی غذایابی باکتری‌ها توسط پسینو معرفی گردید[۱]، یکی از جدیدترین الگوریتم‌های بهینه‌سازی ایده گرفته شده از طبیعت است. در پنج دهه اخیر الگوریتم‌های بهینه سازی همانند الگوریتم ژنتیک، برنامه نویسی تکاملی، استراتژی تکامل که از تئوری تکامل و ژنتیک طبیعی ایده گرفته‌شده‌اند در صدر الگوریتم‌های بهینه‌سازی قرار داشته‌اند. اخیراً الگوریتم‌های تجمعی ۳همانند الگوریتم بهینه‌سازی ذرات[۲]، بهینه‌سازی کلونی مورچه‌ها کارایی خود را در این زمینه نشان داده اند. پسینو نیز با توجه به روند این الگوریتم‌ها BFSO را توسعه داد[۱]. ایده اصلی در طراحی این الگوریتم استفاده از استراتژی غذایابی باکتری ای کویل در بهینه‌سازی چند توابع با چند بهینه بوده است. باکتری بدنبال غذا بگونه‌ای جستجو کرده که به بیشینه انرژی در واحد زمان دست یابد. هر باکتری همچنین با دیگر باکتری‌ها با فرستادن سیگنال‌هایی ارتباط بر قرار می‌کند. باکتری با توجه به این دو فاکتور تصمیم اتخاذ می‌کند. روندی که در آن باکتری با قدم‌های کوچک به دنبال غذا میگردد را کموتاکیس۴ نامیده می‌شود. ایده کلیدی BFSO تقلید از حرکات کموتاکتیکی۵ یک باکتری مجازی در فضا جستجوی مساله است.
از بادی امر، BFSO توجه محققان زیادی را با زمینه‌های گوناگون به خود جلب کرده است. محققان سعی در تلفیق این روش با الگوریتم‌های دیگر به منظور بررسی ویژگی‌های جستجوی محلی و عمومی داشته‌اند. تا کنون این الگوریتم در مسائل گوناگون بکار گرفته شده و کارایی خود را نسبت به دیگر روش‌ها به اثبات رسانده است[۳].
۲- استراتژی‌های غذایابی
۲-۱- عناصر تئوری غذایابی
تئوری غذایابی بر این فرض بنا نهاده شده است که حیوانات بگونه‌ای به دنبال مواد غذایی رفته و آنرا بدست می‌آورند که نسبت انرژی به زمان را بیشنه کنند. این بیشینه سازی احتمال بقا را افزایش داده و به حیوان امکان بیشتری برای انجام اعمال حیاتی(جنگ، جفت‌گیری و …) را می‌دهد. این استراتژی در گونه‌های گوناگون متفاوت است. به عنوان مثال گیاه‌خواران غذا را به آسانی می‌یابند ولی غذا انرژی کمی دارد. بالعکس گوشت خواران در یافتن غذا با مشکلات بیشتری مواجه هستند ولی غذایی که بدست می‌آورند انرژی بیشتری دارد. محدودیت‌های زیادی از طرف محیط همانند عوارض طبیعی(رودخانه و کوه و ..)، نحوه پخش غذا، وجود و عدم وجود شکارچی و … و همچنین از طرف ویژگی‌های بیولوژیکی موجودی که به دنبال غذاست در این بهینه سازی موثر است. گاهی منابع غذایی بصورت مجتمع است به عنوان مثال یک دریاچه. پس هدف غذایابی یافتن این گونه مکان‌هاست. در تئوری غذایابی، این مساله به عنوان یک مساله بهینه سازی مطرح شده و جواب آن یک سیاست بهینه برای تصمیم گیری در غذایابی است[۱].
۲-۲- روش‌های جستجو برای غذا یابی
برای بررسی روش‌های جستجو غذایابی مساله به دو بخش تقسیم می‌شود. ابتدا مهاجم(غذایابنده) بایستی منبع غذا را یافته و سپس آنرا تعقیب کرده و به گروه حمله می‌کند. اهمیت بخش‌های مختلف این روند به رابطه مهاجم و دسته بستگی دارد. بعضی دسته‌ها بزرگند پس مهاجم نیاز به انرژی بیشتری برای شکار دارند اما در عوض به سادگی پیدا می‌شوند[۱].
دو استراتژی جستجو در حیوانات وجود دارد: گشت زدن و کمین کردن. در حالت گشت زدن، مهاجم به دنبال دسته غذایی بصورت ثابت محیط را جستجو می‌کند(ماهی تن و شاهین‌ها از این روش استفاده می‌کنند). در حالت کمین، مهاجم در یک نقطه ثابت می‌ماند و منتظر رد شدن دسته از محدوده حمله خود می‌شود(برخی از مارها از این روش استفاده می‌کنند). اما جستجو به دنبال غذا در بسیاری از گونه‌ها مابین کمین و گشت زدن قرار دارد. به این گونه جستجو، جستجوی افتان و خیزان۶ نیز می‌گویند. در این حالت مهاجم بصورت متناوت گشت زده و در کمین غذا می‌نشیند. ممکن است با گذشت زمان بعد از کمین، جهت حرکت خود را تغییر دهد. برای نشان دادن این حالت میزان حرکت در طول زمان برای این استراتژی‌های جستجو در شکل ۱ نشان داده شده است[۱].
شکل ۱- حالات جستجوی متفاوت در غذایابی[۱] |
|---|
جستجوی افتان و خیزان می‌تواند براساس تغییرات محیط خود را تطبیق داده و به حالت گشت زدن ویا کمین کردن بسته به شرایط محیطی تبدیل گردد.
۲-۳- رفتار اجتماعی در غذایابی
رفتارهای غذایابی که مورد بررسی قرار گرفت تنها در مورد حیوانات بصورت فردی بود. غذایابی گروهی نیز به قطع نسبت به غذایابی تکی دارای مزایایی است. در غذایابی گروهی وجود راه ارتباطی میان افراد ضروری است. مزایای غذایابی گروهی در زیر آمده است.
- حیوانات بیشتری به جستجوی غذا هستند پس احتمال یافتن غذا افزایش می‌یابد. وقتی حیوانی غذا می‌یابد، می‌تواند گروه را از محل این قضا آگاهی دهد. پیوستن به گروه در این حالت می‌تواند دسترسی به مرکز اطلاعاتی را تامین کرده و به بقای فرد کمک کند.
- امکان بیشتر برای برآمدن از پس گروه‌های بزرگتر غذایی.
- حفاظت در قبال مهاجمان ناخواسته می‌تواند توسط گروه تامین شود.
گاهی مناست تر است به گروه به عنوان مکانی برای بروز هوش تجمعی۷ نگریست. این هوش تجمعی منجر به غذایابی بهتر برای هریک از اعضای گروه می‌شود(دست آوردها نزاع‌های درون گروهی بر سر غذا را پوشش می‌دهد زیرا در گروه غذای بیشتری نسبت به حالتی که همکاری وجود ندارد بدست می‌آید). مثالی از این نمونه غذایابی در گرگ‌ها، پرندگان، زنبور عسل و مورچه‌ها به چشم می‌خورد[۱].
گونه‌های اولیه با همکاری در گروه می‌توانند به گونه‌های بالاتری برای غذایابی دست یابند. افراد گونه‌های بالاتر اما بصورت طبیعی قدرت درک و شناخت بیشتری داشته که به معنای توانایی غذایابی مناسب‌تر است. در این گونه موجودات آنها توانایی‌های خاصی دارند که به عنوان مثال می‌توان به توانایی شناخت نقاط حساس محیط، شناخت ویژگی‌های گروه غذایی و .. . اشاره کرد[۱].
۲-۴- غذایابی در باکتری ای کویل
در هنگام غذایابی باکتری، حرکت۸ توسط مجموعه از فلاژل‌ها۹ با قابلیت کشش انجام می‌شود. فلاژل‌های این امکان را برای باکتری ای کویل فراهم می‌آورد که چرخیده۱۰ یا شنا کند. این دو عمل در زمان غذایابی انجام می‌شود. وقتی فالاژل‌های به سمت عقربه‌های ساعت می‌گردند باعث چرخش سلول می‌شود. چرخش در محیط‌های سمی(عدم وجود غذا) و یا هنگامی که غذا یافت شده است به چشم می‌خورد کمتر است. با چرخش فلاژل‌ها عکس عقربه‌های ساعت، باکتری باسرعت قابل توجهی شنا می‌کند. با توجه به این اعمال باکتری علاقمند به یافتن غذای افزاینده و فرار از محیط‌های سمی است. به طور کلی باکتری در محیط‌های دوستانه طولانی تر عمل می‌کند. در شکل ۱ نحوه این چرخش و چگونگی آن آمده است[۳].
شکل ۱- چرخش، حرکت و رفتار چموماتیک باکتری[۱] |
|---|
در هنگامی که غذای کافی وجود داشته باشد، طول این باکتری افزایش یافته و در دمای مناسب به دو کپی خود تبدیل می‌شود. این عمل باعث بوجود آمدن عمل تولید مجدد در الگوریتم توسط آقای پوسینو گردید. با توجه به وقوع تغییرات ناگهانی محیطی و یا حمله، پیشرفت چموماتیک ممکن است از بین رفته و یا اینکه گروهی از باکتری‌های به نقطه دیگری منتقل شوند. این اتفاق از بین رفتن و یا پخش شدن در باکتری واقعی اتفاق می‌افتد.
۳- الگوریتم غذایابی تجمعی باکتری یا bfso
با فرض اینکه در پی یافتن کمینه تابع (J(theta)) هستیم که در آن (theta in R^{p}) و تعریف ریاضی گرادیان این تابع در دسترس نیست. الگوریتم بهینه سازی غذایابی تجمعی باکتری چهار رفتار باکتری‌های واقعی را به منظور حل این مساله شبیه سازی کرده که شامل چموماتیک، تجمعی بودن، تولید مجدد و ازبین رفتن و توضیع است. هر باکتری در این الگوریتم جوابی برای مساله است که به منظور یافتن جواب بهینه مساله روی سطح تابع حرکت می‌کند(شکل ۱).
فرض می‌شود که هر مرحله چموماتیک یک چرخش به همراه یک چرخش دیگر و یا شناست. اگر j اندیس مرحله چموماتیک باشد و k اندیس مرحله بازترکیبی l اندیس مرحله ازبین رفتن پخش شدن باشد می‌توان تعاریف زیر را بیان کرد
P: ابعاد فضای جستجو
S: حداکثر تعداد باکتری ها
(N_{c}): تعداد قدم‌های چموماتیک
(N_{S}): طول شنا کردن
(N_{text{re}}) : تعداد قدم‌های تولید مجدد
(N_{text{ed}}): تعداد قدم‌های ازبین رفتن و پخش شدن
(P_{text{ed}}): احتمال از بین رفتن و پخش شدن
(Cleft( i right)): اندازه گامی که در جهت تصادفی برداشته می‌شود
شکل ۱- مساله موردی و مکانی که باکتری‌ها در آن قرار دارند[۳] |
|---|
(Pleft( j,k,l right) = left{ theta^{i}left( j,k,l right)|i = 1,2,ldots,S right}) مجموعه نقاط نشاندهنده هر فرد جمعیت در j امین مرحله چموماتیک، k امین مرحله تولید مجدد و l امین مرحله از بین رفتن و پخش شدن است. همچنین (Jleft( i,j, k,l right)) میزان هزینه باکتری i ام در j امین مرحله چموماتیک، k امین مرحله تولید مجدد و l امین مرحله از بین رفتن و پخش شدن است. درجمعیت‌های واقعی تعداد باکتری‌های می‌تواند بسیار بزرگ بوده اما ابعاد ۳ است. در قسمت پایین چهار مرحله اساسی این الگوریتم بصورت خلاصه ارائه میگردد.
- چموماتیک: این مرحله حرکت باکتری ای کویل با استفاده از چرخش و شنا تولید شده توسط فلاژل‌ها را شبیه‌سازی می‌کند. بصورت بیولوژیک یک باکتری ای کویل می‌تواند به دو طریق حرکت کند. می‌تواند در بازه زمانی در یک جهت حرکت کرده و یا بچرخد و در طول حیات خود مابین این دوحالت یکی را انتخاب کند. اگر (theta^{i}left( j,k,l right)) نشاندهنده i ام در j امین مرحله چموماتیک، k امین مرحله تولید مجدد و l امین مرحله از بین رفتن و پخش شدن و (Cleft( i right)) طول حرکت در یک جهت تصادفی(ناشی از چرخش) باشد مکان باکتری در مرحله چموماتیک بعد از رابطه زیر محاسبه میگردد:
| (۴) | (theta^{i}left( j + 1,k,l right) = theta^{i}left( j,k,l right) + Cleft( i right)*frac{Deltaleft( i right)}{sqrt{Delta^{T}left( i right)Deltaleft( i right)}}) |
|---|
در این رابطه (Deltaleft( i right)) نشاندهنده جهت تصادفی بدست آمده از چرخش است که برداری است با اعضایی در بازه (leftlbrack – 1,1 rightrbrack).
- رفتار تجمعی: رفتارهای جالبی در میان بسیاری از گونه‌های متحرک از جمله باکتری ای کویل مشاهده شده است که آن تولید الگو‌های پیچیده و ثابت از نظر زمان و مکان (تجمع) در محیط‌های غذایی شبه جامد است. گروهی از سلول‌های ای کویل در حالتی که تنها یک گیرنده دارند خورد را به سمت حداکثر گرادیان سوق می‌دهند. همچنین سلول‌ها ماده‌ای از خود ترشح کرده که دیگران را تحریک (جذب یا دفع) کرده و به تجمع گروه کمک می‌کند. این گروه چگال از باکتری‌ها با داشتن الگویی متمرکز حرکت می‌کنند. ارتباط میان سلولی باکتری می‌تواند بصورت زیر معرفی گردد
| (۴) | (J_{text{cc}}left( theta,Pleft( j, k,l right) right) = Sigma_{i = 1}^{S}J_{text{cc}}left( theta,theta^{i}left( j,k,l right) right) = sum_{i = 1}^{S}{- d_{text{attract}}expleft( – w_{text{attract}}sum_{m = 1}^{p}left( theta_{m} – theta_{m}^{i} right)^{2} right)} + sum_{i = 1}^{S}{h_{text{repell}}expleft( – w_{text{repell}}sum_{m = 1}^{p}left( theta_{m} – theta_{m}^{i} right)^{2} right)}) |
|---|
که در این رابطه (J_{text{cc}}left( theta,Pleft( j, k,l right) right)) تابع هدفی است که به مقدار واقعی افزوده می‌شود. این تابع متغیر با زمان است. مقادیر (d_{text{attract}})، (w_{text{attract}})،(h_{text{repell}}) و (w_{text{repell}}) بسته به مساله بایستی بصورت مناسبی انتخاب شوند[۱].
- تولید مجدد: بنصف اکتری‌هایی با حداقل سلامت مرده و باکتری‌هایی که سالم‌ترند تبدیل به دو باکتری می‌شوند که در همان نقطه قرار دارد. این باعث حفظ اندازه جمعیت می‌شود.
- از بین رفتن و پخش شدن: بصورت کم کم یا آنی تغییراتی در محیطی که باکتری زندگی می‌کند رخ می‌دهد. این تغییرات ممکن است بخاطر تغییر دما باشد. با توجه به این تغییرا ت بخش از باکتری‌ها ممکن است کشته شده و یا به جای دیگری بروند. برای شبیه سازی این مفهوم در الگوریتم برخی از باکتری‌های با احتمال کمی از بین رفته و در جای دیگری از محیط بصورت تصادفی مقدار دهی می‌شوند.
شبه کد این الگورتیم در زیر آمده است.
|
الگوریتم بهینه‌سازی تجمعی غذایابی باکتری:
پارامترها: {قدم اول} مقدار دهی به پارامترها الگوریتم : P،S،(N_{c})، (N_{S})،(N_{text{re}})، (N_{text{ed}})، (P_{text{ed}})،(Cleft( i right)) الگوریتم: {قدم دوم} حلقه از بین رفتن پخش شدن: l=l+1 {قدم سوم} حلقه تولید مجدد: k=k+1 {قدم چهارم} حلقه چموماتیک: i=i+1 {الف} برای هریک از باکتری ها قدم چموماتیک را بصورت زیر انجام بده {ب} هزینه باکتری را محاسبه کن، میزان تاثیر باکتری‌های دیگر را به این هزینه اضافه کن {ج}این مقدار را به عنوان آخرین هزینه باکتری ذخیره کن {د} چرخش: برای چرخش یک بردار تصادفی تولید کن {ه} حرکت: به جهت تصادفی تولید شده با گام مشخص شده حرکت کن {و} مقدار هزینه و هزینه القا شده از سایرین را محاسبه کن {ز} شنا: اگر تعداد تکرارهای شنا از حدی نگذشته است و هزینه رو به کاهش دارد به سمت تولید شده حرکت کن {ح} به سراغ باکتری دیگر برو {قدم پنجم} اگر مراحل چموماتیک تمام نشده به قدم ۴ بازگرد {قدم ششم} تولید مجدد: {الف} سلامت باکتری که برابر مجموع هزینه‌ها در مراحل چموماتیک است را محاسبه کن {ب} باکتری‌های با بیشترین میزان هزینه مرده و بهترین باکتری ها دو نیمه می‌شوند. {قدم هفتم} اگر مراحل تولید مجدد تمام نشده به قدم ۳ بازگرد. {قدم هشتم} ازبین بردن پخش: برای هریک از اعضا به احتمال مشخص را پخش کن. بدین معنا که باکتری را با یک باکتری تصادفی تولید شده جایگزین کن. {قدم نهم} اگر مراحل از بین بردن و پخش به اتمام نرسیده با قدم ۲ برگرد در غیر اینصورت اتمام الگوریتم |
|---|
۴- نتایج شبیه سازی و مقایسه با الگوریتم PSO
این بخش بررسی رفتار این الگوریتم در قبال الگوریتم بهینه سازی ذرات می‌پردازد. این دو الگوریتم توسط نویسنده این گزارش در محیط برنامه نویسی MATLAB پیاده سازی شده و با یکدیگر در مسائل بهینه سازی متفاوت مقایسه میگردد.
برای مقایسه رفتار این سه الگوریتم سه تابع برای بهینه سازی در نظر گرفته شده است که شکل‌های آنها در زیر آمده است. این توابع بگونه‌ای انتخاب شده اند که دارای حالات مختلف از نظر داشتن کمینه باشند. بدین ترتیب که تابع اول تقریبا به تعداد مساوی کمینه محلی داشته. تابع دوم تنها یک کمینه محلی داشته و تابع سوم کمینه‌های بسیاری دارد. این توابع برای بررسی رفتار جستجوی محلی و جستجوی عمومی الگوریتم مفید خواهند.
شکل ۱- تابعی تولید شده از جمع چند تابع نمایی |
|---|
شکل ۱- تابع هایپربولیک |
شکل ۱- تابع ترکیبی نمایی و مثلثاتی |
نتایج بدست آمده با استفاده از روش PSO در شکل ۱،شکل ۱ و شکل ۱ و نتایج بدست آمده از الگوریتم BFSO در شکل ۱، شکل ۱ و شکل ۱ قابل مشاهده است. برای الگوریتم PSO محل ذرات در طول تکرارهای انجام شده نمایش داده‌شده است. برای الگوریتم BFSO برای هریک از مراحل تولید مجدد(۴ مرحله) و ازبین رفتن و پخش یک نمودار از تمامی جمعیت ارائه شده است.
شکل ۱- نتایج PSO برای تابع اول |
|---|
شکل ۱- نتایج PSO برای تابع دوم |
شکل ۱- تابعی نتایج PSO برای تابع سوم |
 
شکل ۱- نتایج BFSO برای تابع اول |
شکل ۱- نتایج BFSO برای تابع دوم |
شکل ۱- تابعی نتایج BFSO برای تابع سوم |
با بررسی اشکال مربوط به BFSO و شکل مربوط به PSO برای تابع اولی متوجه می‌شویم که الگوریتم PSO تمامی نقاط فضای جستجو را بررسی نکرده و تنها توانسته دو کمینه محلی را بیابد و این در صورتی است که الگوریتم BFSO توانایی یافتن وبررسی تمامی کمینه‌های محلی را دارد. در تابع دوم نیز این خاصیت الگوریتم BFSO بیشتر به چشم می‌خورد و مویدی بر ادعای قبلی در مورد عمومی تر بودن جستجوی این الگوریتم نسبت به PSO دارد.
مراجع
[۱] Liu Yanfei and K. M. Passino, “Biomimicry of Social Foraging Behavior for Distributed Optimization: Models, Principles, and Emergent Behaviors,” Journal of Optimization Theory and Applications, vol. 115, pp. 603-628, Dec. 2002.
[۲] R. Eberhart and J. Kennedy, “A new optimizer using particle swarm theory,” in Proceedings of the Sixth International Symposium on Micro Machine and Human Science, 1995, pp. 39 – 43.
[۳] Sambarta Dasgupta, Swagatam Das, A. Abraham, and A. Biswas, “Bacterial Foraging Optimization Algorithm: Theoretical Foundations, Analysis, and Applications,” in Foundations of Computational Intelligence Volume 3: Global Optimization: Springer Verlag, 2009, pp. 23-55.
نوشته آرشیو دروس: الگوریتم بهینه‌سازی غذایابی باکتری یا bfso اولین بار در تجربه های پراکنده پدیدار شد.
