براي طراحي شبكه اتوبوسراني، پوشش جمعيتي بيشتر در سطح شهر يك ملاك اصلي است. بدين معني كه شبكه‌اي كه مقدار تقاضای بيشتري از شهر را پوشش بدهد، شبكه برتري است. اما با چنين هدفي، پاسخ مسأله اين است كه در تمام خيابانها و براي همه ناحيه‌ها خط اتوبوسراني درنظر گرفته شود، زيرا در اين صورت پوشش به حداكثر خود مي‌رسد. ولي چنين كاري از نظر بودجه و اجرايي امكانپذير نيست. از اين رو، بايد محدوديت بودجه نيز در اين مسأله ديده شود. براي اين منظور هزينه‌هاي شبكه اتوبوسراني بصورت تابعي از طول شبكه تعريف شده است. بدين ترتيب، منفعت تصميم به صورت پوشش بيشتر در سطح شهر، و هزينه آن به صورت تابعي از طول شبكه تعريف مي‌شود. در محاسبه پوشش شبكه اتوبوسراني چنانچه دو خط در قسمتي از مسير خود با يكديگر مشترك باشند (میزان همپوشانی) – از خيابانهاي يكساني عبور كنند – پوشش جمعيتي مربوط به آن خيابان براي آن شبكه فقط يك بار محاسبه مي‌شود. در واقع اين دو خط اتوبوسراني داراي پوشش مشترك هستند. بدين ترتيب، الگوريتم خطوطي را انتخاب مي‌كند كه داراي سه ويژگي زير باشند:
– از مناطق پرجمعيت شهر عبور كنند و در سطح شهر گسترش خوبي داشته باشند.
– تا مرز امكان كمترين مقدار همپوشاني بين خطوط مختلف شبكه اتوبوسراني وجود داشته باشد.
– کمترين هزينه کل ( طول خط) را داشته باشد.
الگوريتم ژنتيك از ميان خطوط اتوبوسراني نامزد انتخاب (30 خط)، تعدادي خط را برمي‌گزيند كه تابع هدف مسأله را بيشينه سازند.
كاربرد الگوريتم ژنتيك براي مسأله طراحي شبكه اتوبوسراني
در اين قسمت چگونگي كاربرد الگوريتم ژنتيك و اجزاي اين الگوريتم براي حل مسأله طراحي شبكه اتوبوسراني تشريح مي‌شود.
1- تعريف كروموزوم و ژن
در مسأله مورد نظر، هر ژن نماينده يك خط اتوبوسراني است. اين ژن يكي از دو مقدار 0 يا 1 را مي‌پذيرد، كه عدد 1 بمنزله انتخاب خط اتوبوسراني و عدد 0 بمعني عدم انتخاب آن مي‌باشد. به همين سبب 30 ژن, معرف 30 خط اتوبوسراني نامزد درنظر گرفته شده است. ترتيب ژنها مطابق با ترتيب خطوط اتوبوسراني است، يعني ژن شماره i- ام مربوط به خط شماره i- ام است، كه در آن i بين 1 تا 30 مي‌باشد. هر 30 ژن تشكيل يك كروموزوم را مي‌دهند. پس در هر كروموزوم همه خطوط اتوبوسراني موجود مي‌باشند، كه اگر مقدار ژن مربوطه به هر خط برابر 1 باشد، يعني خط ياد شده انتخاب شده است، و چنانچه مقدار آن برابر 0 باشد به منزله عدم انتخاب آن خط مي‌باشد. بدين ترتيب، هر كروموزوم معرف يك شبكه اتوبوسراني است، كه خطهاي آن توسط ژنهاي کروموزوم که داراي عدد 1 هستند معين مي‌شود.
براي اين مسأله اندازه جمعيت (تعداد كروموزومهاي هر نسل) و همچنین مقدار عملگرهای ادغام و جهش مشخص نشده است.
براي نخبه‌گرايي شبكه اتوبوسراني برتر هر نسل كه داراي بيشترين مقدار تابع هدف هستند، شناسايي شده و مستقيماً به نسل بعدي منتقل مي‌شوند. البته، اين شبكه‌ها در عملگرهاي ترکيب و جهش شركت مي‌كنند، ولي با اين كار بهترين جواب هر نسل حداقل مانند بهترين جواب نسل پيش از خود باقي مي‌ماند.
2- تابع هدف در الگوريتم ژنتيك
و
Dj= تقاضای خط j ام
D k,j= میزان همپوشانی خط j با خط k با فرض k < j
Li= طول خط j ام
i = شبکه i که در واقع یکی از کروموزوم ها است و هر ژن معرف یک خط است که شماره هر ژن، معادل شماره خط در اطلاعات موجود است. در صورتی که خط مورد نظر j در شبکه i موجود باشد، مقدار ژن مربوطه 1 و در صورت عدم وجود خط j در شبکه i، مقدار ژن مربوطه صفر لحاظ می شود. بنابراین:
