Astaraki

بهینه سازی کلونی زنبورها

حرکتی مساعی گونه برای حل مسائل حمل و نقل و جابجایی پیشرفته

چکیده

سیستمهای طبیعی مختلفی به ما یاد میدهند که ارگانیسمهای خارجی بسیار ساده ایی توان تولید سیستمهایی با قابلیت انجام کارهایی بسیار پیچیده به کمک برهم کنشهای پویا با هم را دارند.
متاهیوریستیک (ابرکشف) کلونی زنبورها (BCO) در این مقاله آورده شده است.کلونی مصنوعی زنبورها در پاره ایی نزدیک به هم و در مقایسه با کلونی زنبورهای طبیعی , متفاوت عمل میکنند.
BCO به همان میزان که قابلیت حل مسائل ترکیبی قطعی را دارد , قادر به حل مسائل ترکیبی ایی است که دارای عدم قطعیت نیز میباشند.
توسعه ی الگوریتم کشف کننده ی جدید برای حل مسئله ی Ride-Matching به کمک راه پیشنهاد شده (استفاده از کلونی زنبورها) راهی روشنگر برای نشان دادن قابلیتهای این روش محسوب میشود.

1.معرفی

شمار زیادی از مدلهای مهندسی و الگوریتمهایی که برای حل مسائل پیچیده به کار میرود بر اساس کنترل و مرکزگرایی بنا شده اند.برخی از سیستمهای طبیعی (کلونی های حشرات اجتماعی) به ما یاد میدهند که یک سری ارگانیسمهای ساده ی خارجی قابلیت تولید سیستمهایی را دارند که به کمک بر هم کنشهای پویا قابلیت انجام اعمال بسیار پیچیده را دارند.
گروه زنبورها به خاطر استقلال داخلی کلونی و عملکردهای توزیع شده و سیستم درون سازمانی یکی از بهترین کلونی ها برای توضیح این مسئله شناحته شده است.
در سالهای اخیر محققان برای تولید سیستمهای جدید مصنوعی (در حیطه ی هوش مصنوعی) شروع به تحقیق درباره ی طرز رفتار حشرات اجتماعی کرده اند.
BCO ( Bee Colony Optimization) که مسیر جدیدی را در هوش جمعی بررسی میکند در این مقاله بررسی شده است.هدف اصلی این مقاله بررسی این امکان است که به کمک سیستم مصنوعی زنبورها بتوان قدمی را در پیدا کردن راه حلهایی جامع برای حل مسائلی که با عدم قطعیت مواجه هستند برداشت.
ادامه ی مقاله در قسمتهای دوم و سوم آمده است.قسمت دوم به توضیح BCO میپردازد در حالیکه قسمت سوم به مطالعه ی موضوعی مربوط به مسئله Ride-Matching میپردازد.

.The Bee Colony Optimization : The New Computational Paradigm2

حشرات اجتماعی (زنبورعسل , زنبور معمولی , مورچه ها , موریانه ها) برای میلیونها سال بر روی کره زمین زندگی کرده اند , آشیانه های مختلف و بسیاری از ساخته های پیچیده تر ساخته اند و آذوقه شان را سازماندهی کرده اند.کلونی حشرات اجتماعی بسیار انعطاف پذیر محسوب میشود و به خوبی قابلیت همساز شدن با محیط جدید را دارند.این انعطاف پذیری این امکان را به کلونی میدهد تا بتواند حتی با مواجه شدن با شرایط سخت و مشکلات , به زندگی خود ادامه دهد.
پویاگرایی جمعیت حشرات نتیجه ایی از عملکردها و تعاملات بین حشرات با یکدیگر و با محیط اطراف است.تعاملات بین حشرات بر اساس یک سری عوامل فیزیکی و شیمیایی امکان پذیر شده است.محصول نهایی این تعاملات و عملکردها , رفتار اجتماعی این گونه حشرات محسوب میشود.
مثالی برای چنین رفتارهایی , رقص مورچه ها در هنگام جمع آوری محصول است.مثال دیگری برای این حالت ترشح فنومون (هورمون جنسی) در مورچه هاست که موجب راه گذاری برای مورچه های دیگر خواهد شد.این سیستمهای ارتباطی بین حشرات مختلف موجب به وجود آمدن مقوله ایی به نام "هوش اشتراکی" میشود.به این معنی که حشرات فوق به هنگام قرار گرفتن در کنار یکدیگر دارای فاکتوری هوشمند میشوند که در غیاب یکدیگر قادر به انجام چنین کاری نیستند.

2.1 : Bees In Nature

سیستم سازمانی زنبورها بر اساس یک سری قوائد ساده ی خارجی حشرات بنا شده است.با اینکه نژادهای بسیاری از حشرات مختلف بر روی کره ی زمین موجود هستند و همین باعث تفاوتهایی در الگوی رفتاری آنها میشود , ولی با اینحال این سری حشرات اجتماعی را میتوان دارای قابلیت حل مسائل پیچیده دانست.بهترین مثال برای این حالت روند تولید نکتار (شهد) محسوب میشود که در نوع خود یک فرایند ساماندهی شده ی پیشرفته محسوب میشود.هر زنبور ترجیح میدهد که راه قبلی زنبور هم کندوی خود را دنبال کند تا اینکه خود به دنبال گل جدید بگردد.
هر کندوی زنبور عسل دارای مکانی معروف به سالن رقص است که در آنجا زنبورها با انجام حرکتی خاص , هم کندوییهای خود را راضی میکنند تا راه آنها را برای رسیدن به گلها برگزینند.اگر یک زنبور تصمیم بگیرد که به دنبال نکتار برود , با انتخاب زنبور هم کندوی رقاص خود , راه قبلی را دنبال میکند تا به گل برسد.با رسیدن زنبور به گلها و جمع آوری شهد قادر به انجام کارهای زیر است :
الف : منبع غذا را رها کند و دوباره به دنبال زنبور رقصانی بگردد تا بتواند منبعی جدید پیدا کند.
ب : خود به دنبال منابع غذایی جدید بگردد.
ج : در کندو اقدام به رقصیدن کرده و زنبورهای جدیدی را به دنبال خود بکشاند.
بر اساس احتمالات اندازه گیری شده , زنبور اقدام به انجام یکی از حالات بالا میکند .در مکان رقص , زنبورها اقدام به پیشنهاد مکانهای مربوط به جمع آوری نکتار به دیگران میکنند.مکانیزم انتخاب یک زنبور توسط زنبوری دیگر هنوز شناخته شده نیست ولی تا به امروز روشن شده است که این امر بیشتر مربوط به کیفیت نکتار پیدا شده توسط زنبور رقاص است.
لوسیچ و تدوروویچ اولین کسانی بودند که از رویه های پایه و ساده ی زنبوری برای حل کردن مسائل ترکیبی بهینه سازی استفاده کردند.آنها سیستم زنبوری (BS) را معرفی کردند و از آن برای حل مساله ی معروف Travelling Salesman استفاده کردند.در ادامه به استفاده های BCO در حل مسائل پیشرفته اشاره خواهیم کرد.
در کلونی مصنوعی طراحی شده توسط ما شباهتها و تفاوتهایی با کلونهای واقعی زنبورها در طبیعت وجود دارد.در ادامه به معرفی FBS (Fuzzy Bee System) میپردازیم که قادر به حل مسائل ترکیبی *طرح شده توسط انسانها* است.به کمک FBS , Agent ها در ارتباطات با همدیگر از قوانین تقریبی دلیلگرایی و منطق Fuzzy استفاده میکنند.

2.2 : The Bee Colony Optimization Metaheuristic

در BCO , مامورهایی که ما به آنها "زنبور مصنوعی" میگوییم با همدیگر اجتماع میکنند تا بتوانند قادر به حل مسائل مشکلتر باشند.تمامی زنبورهای مصنوعی در ابتدای فرایند جستجو , در کندوی اصلی قرار دارند.در فرایند جستجو نیز , زنبورهای مصنوعی به طور کاملا مستقیم با یکدیگر ارتباط برقرار میکنند.هر زنبور مصنعوی یک سری حرکات محلی خاص انجام داده و به کمک آنها قادر خواهد بود تا راه حلی را بری مشکل فعلی خود پیدا کند.
این زنبورها تک تک راه حلهای کمکی و زیرپایه ایی را ارائه میدهند تا در آخر با ادغام این راه حلها , راه حل اصلی برای حل مسئله ی ترکیبی به دست بیاید.
روند جستجو از تکرارهای پشت سر هم تشکیل شده است.اولین تکرار زمانی پایان میابد که اولین زنبور راه حل زیر پایه ی خود را برای حل مسئله ی اصلی ارائه دهد.
بهترین راه حل زیرپایه در خلال اولین تکرار انتخاب شده و پس از آن , تکرار دوم شروع خواهد شد.در تکرار دوم , زنبورهای مصنوعی شروع به پیدا کردن راه حلی جدید برای مسئله ی زیر پایه میکنند و...
در پایان هر تکرار حداقل یک و یا چند راه حل ارائه شده وحود دارد , که آنالیست مقدار همگی آنها را مشخصی میکند.
به هنگام حرکت در فضا , زنبورهای مصنوعی ما یکی از دو حرکت "حرکت به سمت جلو" و یا "حرکت به سمت عقب" را انجام میدهند.
به هنگام "حرکت به سمت جلو" زنبورها راه و روشهای جدیدی را برای حل مسئله پیدا میکنند.آنها اینکار را به کمک یک سری جستجوهای شخصی و اطلاعات بدست آمده ی گذشته انجام میدهند.
بعد از آن , زنبورها عمل "حرکت به سمت عقب" را انجام میدهند که همان برگشتن به کندوی اصلی است.در کندو همگی زنبورها در یک فرایند "تصمیم گیری" شرکت میکنند.ما در نظر میگیریم که هر زنبوری قابلیت درک و دریافت اطلاعات زنبورهای دیگر را بر اساس کیفیت دارد.به کمک این روش , زنبورها این قابلیت را دارند که با استفاده از اطلاعات دیگران , راههای بهتر حل مسئله را پیدا کنند.
براساس اطلاعات جدیدی که در مورد کیفیت راه حل به دست می آید , زنبور میتواند تصمیم بگیرد که :
الف) منبع راه حل خود را رها کرده و در سالن رقص به دنبال کسی بگردد که منبعی با کیفیت بیشتر در اختیار دارد.
ب) بدون اینکه کسی را جذب کند , دوباره به سراغ منبع راه حل خود برود.
ج)در سالن رقص با انجام حرکاتی خاص (رقصیدن) سعی در جمع کردن زنبورهای دیگر به دور خود داشته باشد.
بر اساس میزان کیفیتی که زنبور از منبع خود به دست می آورد , فاکتوری به نام "وفاداری" در وی بوجود می آید که در واقع همان وفاداری به راهی است که خود زنبور انتخاب کرده است.بار دومی که زنبورهای مصنوعی برای پیدا کدن راه حل مسئله به حرکت در می آیند , اینبار سعی در پیدا کردن راههای جدیدی برای حل مسوله دارند و بعد از اینکار دوباره عمل "حرکت به سمت عقب" را انجام داده و به کندو برمیگردند و دوباره در کندو در بحثی که در مورد پیدا کردن بهترین راه شکل گرفته , شرکت میکنند.
این روند زمانی پایان میابد که یک راه حل تقریبا کامل برای مسئله پیدا شود.
مثل برنامه نویسی پویا , BCO نیز میتواند مسائل ترکیبی بهینه سازی را در هر مرحله (تکرار) به میزانی حل کند.هر کدام از مراحل مشخص شده دارای یک مقدار بهینه سازی خاص است.بگذارین اشاره کنیم که :
ST={st1 + st2 + … + stm}
همانطور که میبینید هر Stage (مرحله) شامل یک سری مراحل از قبل انتخاب شده است.در ادامه میبینید که به کمک کمیت B ما تعدا زنبورهایی را که در این فرایند شرکت میکنند را مشخص میکنیم و به کمک I , تعداد کل مراحل (تکرار) هایی را که انجام میپذیرند را نشان میدهیم.مجموعه ی تمامی راه حلهای زیرپایه را نیز به کمک Sj نشان میدهیم که در آن j دارای مقادیر 1 تا m میباشد.

در زیر کد پیش ساخت BCO را مشاهده میکنید :

الف) شروع : مشخص کردن تعداد زنبورها (B) و تعداد تکرارها (I). مشخص نمودن تعداد مراحل (ST).پیدا کردن هر گونه راه حل قابل حل x از مسئله.
این راه حل در واقع بهترین و اولین راه حل انتخاب توسط ما خواهد بود.

ب) Set i:=1 , Until i=I و تکرار کن مراحل بعدی را

ج) Set j:=m , Until j=m و تکرار کن مراحل بعدی را

حرکت به سمت جلو : رفت : به زنبورها این امکان را میدهد که از کندو بیرون آمده و قابلیت انتخاب B راه حل را از مجموعه ی راه حلهای زیرپایه Sj در STj داشته باشند.

حرکت به سمت عقب : برگشت : تمامی زنبورها را به کندو برمیگرداند.به زنبورها این اجازه را میدهد که اطلاعات خود را در مورد کیفیت راه حلهای دیگران و خود به اشتراک بگذارند و بدین طریق تصمیم بگیرند که منبع خود را رها کرده یا بدنبال کسی دیگر بیفتند یا به تنهایی به منبع خود برگردند و یا با رقصیدن دیگران را مشتاق دنبال کردن منبع خود کنند.

Set j:=j+1

د)اگر بهترین راه حلی (Xi) که در I امین تکرار بدست آمد , بهتر از بهترین راه اخیر بدست آمده بود , آنگاه فاکتور بهترین راه حل را به روز میکنیم : X:=xi

ه) 1Set i:=i+


بطور کل حرکتهای جلویی و عقبی در BCO میتوانند نقش فرعی را بگیرند به این معنی که تا زمانیکه یکی از فاکتورهای مهم کامل نشده است , این دو به کار خود ادامه دهند.این فاکتور مهم به عنوان مثال میتواند "بیشترین مقدار رفت و برگشت ها" و یا برخی دیگر از موارد مورد نظر توسط خود اپراتور باشد.
در BCO , زیر مدلهای مختلفی که به توصیق چگونگی حالات زنبورها میپردازد و یا منطق گرایی آنها را مشخص میکند به راحتی قابلیت توسعه و تست شدن را دارند.به این معنی که الگوریتمهای متفاوتی از BCO را میتوان طراحی کرد.
این مدلها میتوانند به توصیف چگونگی ترک کردن منبع اولیه توسط زنبورها , ادامه دادن رفت و برگشت بین کندو و منبع توسط زنبور و یا چگونگی رقصیدن زنبور برای جمع کردن دیگر زنبورها به دود خود را توضیح دهند.

2.3 : The Fuzzy Bee System

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

الف) راه حل زیرپایه ی بعدی که باید به راه حل اصلی اضافه شود چیست ؟
ب) آیا باید راه حل زیرپایه ی فعلی را رها کرد و به دنبال راه حل زیرپایه ی جدیدی رفت ؟
ج)آیا باید به گسترش راه حل زیرپایه ی فعلی ادامه داد ولی فعلا بدنبال دیگر زنبورها نرفت ؟

بسیاری از مدلهای تصمیم گیری بر اساس ابزارهای مدلینگ مختلفی به وجود آمده اند.این حالات کاملا منطقی و عقلی هستند و بر اساس این اطلاعات بوجود آمده اند که ماموران تصمیم گیر (Decision Maker Agents) مامورانی با داشتن بیشترین اطلاعات هستند و همیشه بهترین راه حل را برای پایان دادن به حل مسئله در نظر میگیرند.برای اینکه بتوان مدلهای حل مسئله ی مختلفی را بوجود آورد محققان شروع به استفاده از راههای بی قاعده تری کردند.

مفهوم ساده ی منطق فازی (Fuzzy) که توسط "زاده" معرفی شد قابلیت بهتری در توضیح مسائلی که با عدم قطعیت ادغام شده اند را دارد.با توجه به اطلاعات فوق , ما در انتخاب اینکه منطق زنبورها بر چه اساسی صورت میگیرد , از منطق فازی استفاده میکنیم.زنبورهای مصنوعی ما از منطق گرایی تقریبی و منطق فازی برای انجام اعمال خود استفاده میکنند.
به هنگام دادن راه حلهای زیرپایه ی جدید به زنبور مصنوعی , زنبور حالتهای زیر را برای برقراری ارتباط با راه حل زیرپایه ی فوق در نظر میگیرد : کم جاذبه , جذاب , خیلی جذاب
همچنین ما در نظر میگیریم که یک زنبور مصنوعی میتواند مقادیر خاصی را مانند "کوتاه" , "متوسط" و "بلند" و یا "ارزان" , "متوسط" و "گران" در نظر بگیرد.

2.3.1 : Calculating The Solution Component Attractiveness and Choice Of The Next Solution Component To Be Added To The Partial Solution

الگوریتم منطق تقریبی برای حل کردن مسئله ی جذابیت , از قوانین زیر تشکیل شده است :

اگر مقادیر بدست آمده از راه حل زیر پایه خیلی خوب باشد
آنگاه راه حل بدست آمده خیلی جذاب است.

هدف و امتیاز اصلی استفاده از از این الگوریتم این است که حتی با وجود اینکه اطلاعات به دست آمده ممکن است فقط اطلاعات تقریبی باشند (و نه قطعی) , میتوان میزان جذابیت راه حل زیرپایه را به راحتی مشخص کرد.بگذارید با در نظر گرفتن به عنوان میزان جذابیت راه حل زیرپایه ی i به توضیح میزان احتمال وقوع بپردازیم :
احتمال برای راه حل زیر پایه ی i که به راه حل اصلی الحاق میشود برابر است با نسبت میزان جذابیت تقسیم بر تمامی جذابیتهای راه حلهای زیر پایه ی دیگر :

برای اضافه کردن راه حلهای جدید به راه حل اصلی , زنبورها از نوعی انتخاب به نام Roulette Wheel Selection استفاده میکنند.

2.3.2: Bee's Partial Solutions Coparison Mechanism

در توصیف مکانیزم مقایسه ی راه حلهای زیر پایه ی زنبور , ما موضوع "بدی راه حل زیرپایه" را معرفی میکنیم که برابر است با :

کمیتهای بالا به صورت زیر تعریف میشوند :
: بدی راه حل زیرپایه به وسیله ی k امین زنبور
: مقادیر تابع مفعولی از راه حل زیرپایه ایی که به وسیله ی ن امین زنبور کشف شده
: مقادیر تابع مفعولی از بهترین راه حل زیرپایه ی کشف شده از ابتدای روند جستجو تاکنون
: مقادیر تابع مفعولی از بدترین راه حل زیرپایه ی کشف شده از ابتدای روند جستجو تاکنون

الگوریتم منطق تقریبی برای تعیین بدی راه حل زیرپایه از قوانینی به شکل زیر تشکیل شده است :
اگر راه حل کشف شده بد بود
آنگاه وفاداری کم خواهد شد.
زنبورها از منطق تقریبی و مقایسه ی راه حلهای زیرپایه ی کشف شده شان با بهترین راه حل زیرپایه , و مقایسه ی راه حلهای زیرپایه کشف شده با بدترین راه حلها از آغاز روند جستجو استفاده میکند.
در این روش حقایق تاریخی که بوسیله ی تمامی اعضای کلونی زنبور بوجود آمده اند تاثیر قابل توجهی بر راههای آینده ی جستجو دارند.

2.3.3 : Bee's Decision About Recruiting The Nestmates

از زمان شروع زندگی زنبورها و یا بهتر از بگوییم از زمان شروع زندگی حشرات اجتماعی , احتمال رخدادی است که در آن زنبور به پرواز در طول همان مسیر بدون گرفتن همراه ادامه دهد. احتمال بسیار کمی است ( <<1).
زنبورها تا محل رقص پواز میکنند و با احتمالی برابر با میرقصند.این نوع ارتباط بین زنبورها منجر به ساخته شدن فاکتوری به نام "هوش جمعی" میکند.
در اینحالت هنگامی که زنبور تصمیم میگیرد که همان مسیر را پرواز نکند , آن زنبور به سالن رقص رفته و از دیگر زنبورها پیروی خواهد کرد.

2.3.4 : Calculating The Number Of Bees Changing The Path

هر راه حل زیرپایه که در ناحیه ی رقص اعلان شده , دو ویژگی اصلی داشته است :
الف) مقادیر تابع مفعولی
ب) تعداد زنبورهایی که آن راه حل زیرپایه را اعلان کرده اند
این تعداد یک تعیین کننده ی خوب برای دانش دسته جمعی زنبورهاست.این فرایند نشان میدهد که چگونه کلونی زنبوری راه حل زیرپایه ی خاصی را در نظر میگیرد.
الگوریتم منطق تقریبی برای معین کردن جذابیت راه حل زیرپایه ی اعلان شده از قوانین زیر تشکیل شده است :

اگر طول راه اعلان شده کوتاه باشد و تعداد زنبورهای اعلان کننده کم باشد
آنگاه جذابیت راه حل زیرپایه متوسط است.

جذابیت محاسبه شده ی راه در این روش میتواند مقادیری بین 0 و 1 را اختیار کند.هر چقدر مقدار محاسبه زیادتر باشد , راه حل اعلان شده جذابیت بیشتری دارد.زنبورها کم و بیش به راه اولیه و قدیمی خود وفادارند , همزمان راه های اعلان شده ی جدید جذابیت کم و بیشی برای آنها خواهد داشت.
بعنوان مثال بیایید دو راه فرضی را و بنامیم.ما با تعداد زنبورهایی را که راه را ترک کرده اند و به جفتهایی ملحق شده اند که در طول راه پرواز میکنند , را مشخص میکنیم.
الگوریتم منطق تقریبی برای محاسبه ی تعداد زنبورهای جابجا شده شامل قوانینی به فرم زیر است :
اگر وفاداری زنبورها به راه پایین باشد و جذابیت راه بالا باشد
آنگاه تعداد زنبورهای جابجا شده از راه به راه بعدی بالا است.
در این روش تعداد زنبورهایی که در طول یک مسیر خاص پرواز میکنند , قبل از رفت بعدی تغییر داده شده.با استفاده از دانش اجتماعی و به اشتراک گذاری اطلاعات , زنبورها بر مسیرهای تضمین شده ی جستجو تمرکز میکنند , و مسیرهای کمتر تضمین شده را کم کم ترک میکنند.

4 : Case Study : The Ride-Matching Problem

شبکه های راه شهری در بیشتر کشورها به طرز شدیدی متراکم شده و در نتیجه زمان سفر درون شهری زیاد شده , تعداد توقفها افزایش یافته , وقفه های پیش بینی نشده , هزینه ی سفر درون شهری , مزاحمت برای رانندگان و مسافران و نیز آلودگی هوا , سطح صدای ناهنجار و تعداد تصادفات ناشی از ترافیک افزایش یافته است.
افزایش ظرفیت شبکه ی ترافیکی به وسیله ی ساختمانها و جاده های بیشتر در حالیمه هزینه های زیادی دارد , آسیبهای محیطی زیادی نیز دارد.استفاده ی موثرتر از منابع موجود برای حمایت از رشد تقاضای سفر ضروری است.
RideSharing یکی از تکنیکهای شناخته شده ی مدیریت رشد سفر (TDM) است که توصیه به شریک شدن دو یا چند نفر (با دو یا چند مبدا و مقصد) در یک وسیله ی نقلیه میکند.تمام رانندگانی که در RideSharing شرکت کردند به اپراتور اطلاعات زیر را در مورد تکنیک سفر اشاره شده , ارائه دادند :

الف) ظرفیت وسیله ی نقلیه (دو , سه و یا چهار نفر).
ب) روزهایی از هفته که هر فرد برای شرکت در RS حاضر است.
ج) مبدا سفر برای هر روز هفته.
د) مسافت سفر برای هر روز هفته.
ه)مقصد مورد نظر و/یا زمان رسیدن برای هر روز هفته

مسئله ی RS که در این مقاله به آن اشاره شده میتواند به روش زیر تعریف شود :
مسیریابی و زمان بندی وسایل نقلیه و مسافران برای تمامی هفته در "بهترین روش ممکن".
موارد زیر توابع پتانسیل مفعولی هستند :

الف) کمینه کردن کل مسافتی که توسط تمامی اعضای شرکت کننده پیموده میشود
ب) کمینه کردن وقفه ی کل
ج) برابر کردن نسبی بهره برداری از وسایل نقلیه

ما وقتی از مسئله ی بهینه سازی ترکیبی معین استفاده میکنیم که مقصد در نظر گرفته شده یا زمان رسیدن هر دو ثابت هستند (برای مثال "من میخواهم راس ساعت 8 صبح سوار شوم") , به بیان دیگر در بسیاری از حالتهای زندگی واقعی مقصد در نظر گرفته شده و/یا زمان رسیدن , از منطق فازی طبعیت میکند (برای مثال "من میخواهم حدود ساعت 8 صبح سوار شوم") , در اینحالت با مسئله ی RS باید به عنوان مسئله ی بهینه سازی ترکیبی *دارای عدم قطعیت* رفتار کرد.

3.1 : Solving The Ride-Matching Problem By The Fuzzy Bee System

بیایید هر مسافری که در RS شرکت کرده است را بعنوان یک گره در نظر بگیریم (شکل 2).ما مسئله مان را به مراحلی تجزیه میکنیم.اولین سرنشین ماشین (راننده) مرحله ی اول معرفی میشود , دومین مسافری که به RS ملحق میشود (مرحله ی دوم) و...
در طی رفت زنبور تعداد معینی از گره ها را بازدید خواهد کرد , یک راه حل زیر پایه ایجاد میکند و پس از آن به کندو (یعنی گره ی O) برمیگردد.
در کندو زنبور در روند تصمیم گیری شرکت خواهد کرد.زنبورها تمام راه حلهای زیر پایه ی تولید شده را مقایسه میکنند.بر مبنای کیفیت راه حلهای زیرپایه ی تولید شده , هر زنبور تصمیم میگیرد که آیا مسیر تولید شده را ترک ند و زنبور سرگردان شود , یا به پرواز در طول مسیر کشف شده بدون گرفتن همراه ادامه دهد , یا برقصد و بدینگونه همراهی بگیرد قبل از آنکه به مسیر کشف شده بازگردد.
بسته به کیفیت راه حل زیر پایه ی تولید شده , هر زنبور سطح معینی از وفاداری را به راه قبلی کشف شده دارد.بعنوان مثال زنبورهای B1 و B2 و B3 در فرایند تصمیم گیری شرکت میکنند.پس از مقایسه ی تمام راه حلهای زیرپایه ی تولید شده , زنبور B1 تصمیم میگیرد راه فعلی را ترک کرده و به زنبور B2 ملحق شود.
زنبورهای B1 و B2 با هم در طول مسیری که به وسیله ی زنبور B2 تولید شده , پرواز میکنند.
هنگامی که به انتهای مسیر رسیدند آنها آزاد هستند تا تصمیمی فردی درباره ی گره ی بعدی که باید بازدید شود بگیرند.
زنبور B3 به پرواز در طول مسیر بدون گرفتن همراه ادامه میدهد(شکل 3).در این روش زنبورها دوباره عمل رفت را انجام میدهند.در طی دومین رفت زنبورها تعداد کمی گره ی بیشتر (نسبت به اولین بار) را ملاقات میکنند , راه حلهای زیرپایه ی تولید شده ی قبلی را توسعه میدهند و پس از آن دوباره عمل برگشت را اجرا میکنند و به کندو (گره ی O) بازمیگردند.
در کندو دوباره زنبورها در فرایند تصمیم گیری شرکت میکنند , تصمیم میگیرند , سومین رفت را اجرا میکنند و ...
تکرار هنگامی تمام میشود که زنبورها تمامی گره ها را بازدید کرده باشند.هنگام انتخاب گره ی بعدی که باید در رفت بعدی بازدید شود , زنبور گره ی خاصی را بعنوان "کمتر جذاب" , "جذاب" و "خیلی جذاب" در نظر میگیرد که وابسته به نزدیکی مکانی یا زمانی بین دو درخواست از دو مسافر است.
ما این نزدیکی ها را "فاصله ی مکانی در مبدا" , "فاصله ی مکانی در مسافت" و "فاصله ی زمانی در ورود به مقصد" مینامیم.
ما در نظر میگیریم که زنبور مصنوعی میتواند فاصله ی خاصی بین دو گره را با عنوانهای "کوتاه" , "متوسط" و "طولانی" شناسانی کند.
الگوریتم منطق تقریبی جذابیت گره را با قوانین زیر تعیین میکند :

اگر فاصله ی مکانی در مبدا کوتاه باشد و فاصله ی مکانی در مسافت کوتاه باشد و فاصله ی زمانی ورود کوتاه باشد
آنگاه جذابیت گره بالا است.

بدی راه (که در دومین معادله تعریف شد) در ارتباط با الگوریتم منطق تقریبی برای تعیین وفاداری زنبور به راه کشف شده استفاده میشود.الگوریتم منطق تقریبی برای تعیین جذابیت مسیر پیشنهاد شده از قوانین زیر تبعیت میکند :

اگر طول مسیر پیشنهادی کوتاه باشد و تعداد زنبورهایی که آن راه را پیشنهاد داده اند کم باشد
آنگاه جذابیت آن راه متوسط است.

3.2 : Numerical Experiment

ما مدل پیشنهادی را برای RS شهر Trani (شهر کوچک و زیبایی در جنوب ایتالیا) تا شهر Bari (مرکز منطقه ی Puglia) امتحان کردیم.ما اطلاعات مربوط به 97 مسافر که خواستار شرکت در پروژه ی RideSharing بودند را جمع آوری کرده و برای سادگی مسئله ظرفیت هر اتومبیل را چهار نفر در نظر گرفیم.در اینحالت الگوریتم 24*4 = 96 نفر از 97 نفر را برای ساختن بهترین راه کنار میگذارد.ما از کندویی با 15 زنبور , که سریعا (و یکبار) کندو را ترک میکنند استفاده کردیم.زنبورها فقط 6 مسیر غذایابی را پیدا کردند , و دیگر مسیرها رها شدند.

__________________

تعرفه ارزان تبلیغات در اولین و بزرگترین سایت هوش مصنوعی ایران !
با بیش از صد و چهل هزار کاربر!