بخشی از مقاله
چکیده
رفت و آمد با استفاده ازوسایل حمل ونقل عمومی یکی از مسائلی است که عمومی شدن آن در جامعه تأثیرات زیادي بر کاهش آلودگی هوا و ترافیک دارد. در این میان یافتن بهترین مسیر بر اساس سلایق گوناگون مردم و با توجه به ثابت بودن شبکه حمل و نقل شهري مسأله مهمی است که روزانه بسیاري از مردم در شهرها با آن مواجه هستند.
یافتن مسیر بهینه بر اساس پارامترهاي مختلفی همچون هزینه سفر، زمان سفر، مسافت پیموده شده یا طول مسیر و نیز زمان انتظار در ایستگاهها جهت سوار شدن به وسایل نقلیه، تعداد تغییر در مسیر و تعویض وسیله نقلیه یا هر نوع ترکیبی از موارد بالا به دلخواه کاربر، مسأله اي است که در این مقاله مورد بررسی قرار گرفته است که میتواند راه حل مناسبی براي حل این مشکل در سیستم حمل و نقل عمومیباشد. جهت تحقق این امر در مقاله حاضر از روش الگوریتم ژنتیک به دلیل سادگی و سرعت بالاي آن در تحلیل شبکه هاي با ابعاد بزرگ، براي ترکیب 5 پارامترمذکور، مطابق نظر کاربر، بهره گرفته شده است. مقایسه نتایج حاصل از اعمال شروط مختلف بر تعیین مسیر بهینه، نشانگر کارائی این روش در تصمیم گیري ها می باشد.
-1 مقدمه
امروزه با افزایش آلودگی هوا و نیز با توجه به گسترده بودن شبکه هاي حمل و نقل عمومی داخل شهري اعم از شبکه هاي اتوبوس رانی و مترو، نیاز به گسترش استفاده از این شبکه هاي عمومی به جاي وسایل نقلیه شخصی احساس می گردد .[1] یکی از مشکلات اصلی در این راستا تأمین نیازهاي استفاده کننده به صورت دلخواه و سلیقه اي براي هر کاربر می باشد که بدین منظور نیاز به یک سیستم جهت ارائه مسیر مناسب بنا به درخواست و نیاز کاربران است .[2]
این سلایق می تواند محدودیتهایی مثل هزینه سفر، زمان سفر، مسافت پیموده شده یا طول مسیر و نیز زمان انتظار در ایستگاهها جهت سوار شدن به وسایل نقلیه، تعداد تغییر در مسیر و تعویض وسیله نقلیه یا هر نوع ترکیبی از موارد بالا باشد. براي شبکه هائی که وسعت آنها کمتر است حل این مسئله شاید ساده تر باشد ولی هنگامیکه شبکه گسترده می شود با افزودن هر ایستگاه ویا خطوط ارتباطی، تعداد زیادي مسیر جدید براي رسیدن به مقصد ایجاد می گردد که ممکن است با توجه به خواست کاربر مسیر بهتري باشد.
بدین منظور جهت انتخاب مسیر بهینه - از نظر کاربر - بایستی تمام مسیرها بررسی گردد و مناسبترین مسیر انتخاب و به کاربر معرفی گردد. اما مشکل اساسی در جستجوي مسیرها وسعت شبکه می باشد که با افزایش آن روش جستجوي مستقیم و تک تک تمام راههاي ممکن با مشکل مواجه شده و با تعداد زیادي مسیر روبه رو می شویم و این باعث کاهش کارائی روش مذکور می شود .[3]
در این میان روشهاي دیگر جستجو وجود دارد که تمام فضا را به صورت تک تک جستجو نمی کنند بلکه به صورت موازي با چند سري مسیر کار جستجو را آغاز کرده و این مسیرها با توجه به میزان مناسب بودنشان با یکدیگر ترکیب شده و در واقع اطلاعات خود را با هم ترکیب می کنند و به جواب اصلی مسأله نزدیک می شوندو نیازي به جستجوي تمام حالات ممکن نیست .[4]
پس این روشهاي جستجوي هوشمند براي شبکه هاي گسترده نیز می توانند پاسخگو باشند که یکی از این روشها استفاده از الگوریتم ژنتیک است که به عنوان یک روش هوشمند می تواند در حل مسائلی مانند مسیریابی بهینه براي کاربردهاي گسترده مناسب باشد. در این مقاله روشی بر اساس الگوریتم ژنتیک جهت مسیریابی بهینه با در نظر گرفتن پارامترهاي هزینه سفر، زمان، طول مسیر، تعداد تغییر مسیر، زمان انتظار در ایستگاهها ارائه گردیده است که روي یک شبکه نمونه بررسی و نتایج در این مقاله آورده شده است.
-2 مروري بر الگوریتم ژنتیک
الگوریتم ژنتیک یک الگوریتم مبتنی بر هوش مصنوعی می باشد که از چند بخش اصلی به شرح زیر تشکیل شده است:
جمعیت اولیه: جمعیت اولیه در واقع یکسري از جوابهاي مسئله است - کروموزوم ها - که به صورت اولیه وارد الگوریتم می شوند و یا می توانند به صورت تصادفی ایجاد گردند .[5] تعداد جمعیت اولیه بستگی به پیچیدگی و نوع مسأله دارد که بسته به آن تعداد جوابهائی که به صورت موازي باید در هر نسل ایجاد و مورد بررسی قرار گیرند معین می گردد .[6]
کروموزوم: کروموزوم ها از تعدادي ژن تشکیل شده اند که هر کدام از ژنها یک زیر مسیر از مسیر واقعی را ایجاد می کند - شکل. - 1 کروموزوم رشته اي است که مسیري را بین مبدأ و مقصد ایجاد می کند. این مسیر می تواند مناسب یا نامناسب و حتی غیر ممکن باشد بدین معنی که ممکن است مسیر - کروموزوم - از چند زیر مسیر - ژن - تشکیل شده باشد که این زیر مسیرها پیوسته نباشند به عنوان نمونه در شبکه اي مانند شکل 2، اگر براي رسیدن از نقطه 2 به 4 مسیر اول - ژن اول کروموزوم - ، مسیر 2 به 8 و مسیر دوم - ژن دوم کروموزوم - ، مسیر 9 به 4 باشد، با وجود اینکه نقطه ابتدا و انتها صحییح است، این مسیر درستی نمی تواند باشد زیرا باید مقصد یک زیر مسیر بر مبدأ زیر مسیر بعدي منطبق باشد تا بتوان پیوستگی را در شبکه حفظ کرد.
البته در مراحل بعدي توالی زیر مسیرها بررسی شده و مسیرهاي غیر پیوسته شناسائی و ارزش کمتري می گیرند و در نسل هاي بعدي از بین رفته و تبدیل به مسیرهاي درست و منطقی می شوند. تعداد ژن هاي کروموزوم بستگی به نوع مسأله دارد که در مورد مسیریابی چون تعداد زیر مسیرهاي تشکیل دهنده مسیر کامل همیشه از تعداد کل نقاط - نودهاي شبکه - منهاي یک، کمتر است پس براي هر کروموزوم یکی کمتر از تعداد کل نودهاي موجود در شبکه، ژن در نظر گرفته شده است که البته اگر با زیر مسیرهاي کمتري به مسیر اصلی برسیم، بقیه ژنهاي دنباله کروموزوم مقدار صفر می گیرند.
روش آدگذاري : روش کدگذاري به نوع ژنهاي کروموزوم بستگی دارد و بسته به اینکه هرژن چه نوع داده اي می تواند داشته باشد، تغییر می کند .[5] براي مثال می توان همه ژنهاي یک کروموزوم را به صورت باینري - صفر و یک - کدگذاري کرد ویا به صورت اعداد صحیح و یا متناسب با دامنه مقادیري که یک ژن میتواند بگیرد یک مجموعه تعریف شود. در این تحقیق کدگذاري به صورت اعداد صحیح صورت پذیرفته است زیرا هر یک از ژنها نشانگر یک زیر مسیر با شماره منحصر به فرد است.
انتخاب: در مرحله انتخاب به هر یک از کروموزوم هاي جمعیت اولیه با توجه به میزان مناسب بودن و اینکه چقدر با شرایط مورد انتظار کاربر، بر اساس تابع هزینه تعریف شده که در بخشهاي بعدي بیان می گردد، مطابقت دارند، یک عدد برازندگی داده تعلق می گیرد سپس بر اساس این عدد برازندگی که نشان دهنده میزان خوب بودن مسیر مورد نظر است، به یکی از روشهاي زیرکروموزوم ها انتخاب و به عنوان کروموزومهاي والد نسل بعد انتخاب می گردند. :1 انتخاب به روش ساختار چرخ رولت : - Roulette Wheel Selection - در این روش ارزش نسبی براي هر کروموزوم در نظر گرفته می شود که این ارزش با رابطه1 محاسبه و به کروموزوم مربوطه نسبت داده می شود. در این رابطه f مقدار تابع برازندگی کروموزوم است.
