Journal of Geomatics Science and Technology

fa یافتن کوتاهترین مسیر شبکه با استفاده از الگوریتم بهینه سازی فاخته در سیستم اطلاعات مکانی Finding Shortest Path in a Network by Using Cuckoo Optimization Algorithm and GIS سامانه های اطلاعات مکانی GIS پژوهشي Research امروزه مسیریابی در شبکههای شهری با افزایش حجم اتومبیلها و نیز محدودیتهای ترافیکی گوناگون امری ضروری محسوب میشود. روشی که در این پژوهش به منظور حل مسأله کوتاهترین مسیر برای نخستین بار پیشنهاد شده است، استفاده از الگوریتم بهینهسازی فاخته میباشد. علت انتخاب این الگوریتم، جدید بودن و نیز پاسخ مناسبی است که این الگوریتم برای حل مسأله مسیریابی، نسبت به سایر الگوریتم&zwj;های فراابتکاری داده است. در این راستا و برای انجام مسیریابی، با ایجاد تغییراتی در نسخه دودویی الگوریتم فاخته، از الگوریتم یاد شده استفاده گردید. بدین منظور، برای ایجاد جمعیت اولیه از یک روش کنترل شده استفاده شد، که از ایجاد جمعیتهای تصادفی که درصد بسیار ناچیزی از آنها ممکن است مسیری را تشکیل دهند، جلوگیری میکند. به این صورت که متغیرهای جمعیت که در واقع همان نقاط شبکه و موقعیتهای فاختهها هستند، به صورت تصادفی انتخاب نشده بلکه به صورت کنترلشده انتخاب میشوند و انتخاب نقاط بعدی از میان نقاطی است که با نقطه مورد نظر ارتباط دارند. در تمام مراحل اجرای الگوریتم، موقعیت فاختهها به صورت اعداد باینری درمیآیند و اگر نقطهای در مسیر حضور داشته باشد عدد یک و در غیر اینصورت عدد صفر میگیرد. در فاز مهاجرت فاختهها نیز، از یک تابع سیگموید استفاده شده است که موقعیت جدید فاختهها را به بازهی بین صفر و یک برده و در نتیجه موقعیتهای جدید نیز تبدیل به اعداد صفر و یک میشوند. به منظور آزمون میزان کارایی الگوریتم پیشنهادی، از سه نوع شبکه فرضی، محلی و واقعی استفاده شده است. نتیجه اجرای این الگوریتم در دو نوع شبکه فرضی و محلی با تعداد نقاط ۲۰ و ۳۱، نتیجهای مشابه یک الگوریتم قطعی بود، اما در شبکهای که بخشی از یک شبکه شهری واقعی بود و از ۶۱۷ نود و ۹۹۵ یال تشکیل شده بود، با اختلاف اندکی بهتر از الگوریتم قطعی، توانست مسیر بهینه را نشان دهد. نتایج حاصله نشان داد که این الگوریتم توانایی انجام مسیریابی در شبکه را دارا میباشد و با ایجاد تغییراتی بر اساس ساختار شبکه، میتواند برای دادههای بزرگ و شبکههای واقعی شهری مورد استفاده قرار گیرد. Nowadays with the rapid rate of urban development and increasing volume of vehicles and traffic restrictions, routing in urban networks is not only necessary but essential. Management of such massive volume of data makes the need to for GIS with capabilities to conduct spatial data analysis inevitable. People often, when deciding to start a journey from one location to another, consider not only which route and means of transportation will save them time, but also which are the most inexpensive and cost effective. Hence, they outline the issue as a question in their mind, and based on the criteria, seek to find the optimal solution. The same behavior occurs in a different routing system. Finding the most optimal, efficient and shortest route is one of the key pillars in route finding for which finding the right solutions could lead to answering other questions on the issue. In fact, for a more in depth level of analysis, the answer to this question is essential; Finding the shortest path possible from a starting point or origin, to an ending point or destination. Metaheuristic algorithms are estimating algorithms, that are able to find optimal or almost optimal solutions in a reasonable time.  The showcased methodology in this research for solving the optimal route is recommended for the first time and is the Cuckoo Optimization Algorithm. The reason for choosing this algorithm, is the fact that it is a new method that provides appropriate solutions for different problems than other meta-heuristic algorithms. Route finding which is by nature a discrete problem, is managed by changes in binary version of this algorithm.  In setting up the first population, a controlled approach was used to prevent the creation of random populations, that only a few of them could create routes. In this method, population variables that are basically the same network points and situations of each cuckoo are not randomly selected. These variables are selected in a controlled system. Meaning, selection of each next node is from those that are connected to it. While implementation of the algorithm, cuckoo’s locations are converted to binary numbers, if a node exists in the route it will become 1 and if not 0. A Sigmoid Function is used in the migration phase of the Cuckoo. In this phase the new location of Cuckoo stands between the range of zero and one, and other locations are converted to zero and one. To test the recommended algorithm, three network are used; hypothetical, local and real networks. The result of running this algorithm in 2 hypothetical and local networks with 20 and 31 nodes was the same result of a deterministic algorithm. However, in a network, that was part of a real network and composed of 617 nodes and 995 arcs, it could indicate the optimal route slightly better than that of deterministic algorithm. The results showed that the algorithm is capable of routing in the network and with some changes on the structure of the network can be used on networks with large data. یافتن کوتاهترین مسیر در شبکه, سیستم اطلاعات مکانی, الگوریتم بهینه سازی فاخته, کدگذاری دودویی, جمعیت کنترل شده Finding Shortest Route in Network, Geographical Information System (GIS), Cuckoo Optimization Algorithm, Binary Encoding, Controlled Population 231 239 http://jgst.issgeac.ir/browse.php?a_code=A-10-33-3&slc_lang=fa&sid=1 A. Sargolzaei عالیه سرگلزائی Sargolzaee_a@yahoo.com 10031947532846005251 10031947532846005251 No بدون سازمان A. R. Vafaeinejad علیرضا وفائی نژاد a_vafaei@sbu.ac.ir 10031947532846005252 10031947532846005252 Yes Shahid Beheshti University دانشگاه شهید بهشتی