استفاده از الگوريتم ژنتيك در مسائل كوتاهترين مسير چند معياره بر پايه سيستمهاي اطلاعات
استفاده از الگوريتم ژنتيك در مسائل كوتاهترين مسير چند معياره بر پايه سيستمهاي اطلاعات مكاني
عنوان (انگلیسی): Analysis of GIS-based Genetic Algorithm in Multi-Objective Route Selection
کلمات کلیدی :
الگوريتم ژنتيك چند هدفه،سيستمهاي اطلاعات مكاني،كوتاهترين مسير چند معياره،GIS،Network Analysis،Multi،criteria Shortest Path Problems،objective Genetic Algorithm
کلمات کلیدی (انگلیسی):
الگوريتم ژنتيك چند هدفه,سيستمهاي اطلاعات مكاني,كوتاهترين مسير چند معياره,GIS,Network Analysis,Multi,criteria Shortest Path Problems,objective Genetic Algorithm
چکیده:
مسائل كوتاهترين مسير چند معياره1(MSPP) از جمله مسائل NP-Hard قلمداد مي‌شوند. درMSPP با در نظر گيري معيارهاي مستقل با درجه اهميت مساوي؛ ارائه يك راه‌حل بهينه منحصربفرد كه بهينه كننده تمام معيارها بصورت همزمان باشد، بندرت در واقعيت امكان پذير است و در نتيجه ناچار به محاسبه‌ي تقريبي از بهينه كلي خواهيم بود. تعدادي از روشهاي تقريبي مسيريابي براي حل اين دسته از مسائل پيشنهاد شده‌اند اما پيچيدگي زماني اين روشها باعث شده است كه از مطرح شدن آنها بعنوان يك راه‌حل عملي در شبكه‌هاي بزرگ جلوگيري شود. در طول دهه‌هاي گذشته الگوريتم ژنتيك2(GA) در حل مسائل پيچيده بهينه‌سازي چند هدفه به خوبي عمل كرده‌است. در اين مقاله يك الگوريتم ژنتيك در محيط سيستمهاي اطلاعات مكاني3(GIS) براي MSPP با در نظر گرفتن معيارهاي مستقل با درجه اهميت مساوي ارائه شده است. نتايج بدست آمده از تجزيه و تحليل كارهاي عملي انجام شده، حاكي از قابليت الگوريتم ژنتيك پيشنهادي در جستجوي فضاي مساله، توليد يك مجموعه‌ي بزرگ از مسيرهاي پيشنهادي و تكامل بسوي تقريبي با كيفيت خوب از جواب هاي بهينه در MSPP مي‌باشند.
چکیده (انگلیسی):
Multi-criteria shortest path problems (MSPP) are called as NP-Hard. For MSPPs, a unique solution for optimizing all the criteria simultaneously will rarely exist in reality. Algorithmic and approximation schemes are available to solve these problems; however, the complexity of these approaches often prohibits their implementation on real-world applications. This paper describes the development of a geospatial information system (GIS)-based genetic algorithm (GA) approach to MSPP on simple networks with multiple independent criteria. The GA approach is shown to explore the underlying network space, generate large candidate path sets, and evolve high quality approximations to the optimal MSPP solution(s) adequately
|