بخشی از مقاله
الگوريتم هاي ژنتيكي به كاربره شده در مديريت ترافيك هوايي
افزايش ترافيك هوايي، از زمان شروع تجارت هوايي، باعث مشكل اشباع در فرودگاهها، يا مكانهاي فضايي شده است. در حالي كه هواپيماها ارتقاء مي يابند و اتوماتيك تر مي شوند. اما هنوز كنترل ترافيكي بر پايه تجربيات انسان است. مطالعه حاضر ، دو مشكل مديريت ترافيك هوايي (ATM) را به جزء بيان مي كند، كه براي آنها راه حل هاي بر پايه الگوريتم ژنتيكي وجود دارد. اولين كاربرددر رابطه با مشكل enroute است و دومين كاربرد در مورد مشكلات مديريت ترافيكي در سكوهاي فرودگاهها است.
9.1) راه حل درگيريهاي Enroute = كنترل ترافيك هوايي (ATC) مي تواند توسط يك سرس از فيلترها نشان داده شود، جايي كه هر فيلتر يك ؟ خاص دارد و افق هاي خاص محيطي و موقتي را اداره مي كند. 5 سطح (لِوِل) قابل تشخيص است. در دوره طولاني (بشتر از 6 ماه) ترافيك در يك روش ميكروسكوپي مي تواند برنامه ريزي شود. براي مثال مردم با يك نمودار ترافيكي روبرو هستند كه اندازه هاي كميته ، كه برنامه هاي ساعتي و موافقت با ارتش را مورد توجه قرار داده است، به كاربرده مي شود براي فرهنگ هواپيمايي در زمانهاي اوج يعني بعد ظهر جمعه.
در دوره كوتاهتر ، معمولاً در مورد تنظيمات قبل ، صحت مي شود. اين مورد شامل برنامه ريزي كردن روز ترافيك ، يك يا دو روز قبل تر مي شود. در اين مرحله ، اشخاص ايدة مشخصي درباره بيشتر برنامه ي پرواز و ظرفيت كنترل هر مركز دارند. حداكثر جريان هواپيما كه مي تواند يك قطر را سوراخ كند. ظرفيت قطر ناميده مي شود. اين عمل توسط CFMU3 انجام مي شود. ترافيك ميان آتلانتيك براي مثال در اين مرحله مورد توجه قرار مي گيرد. راههاي هوايي، تنظيم ساعت هاي
پرواز و حالت هوا مورد توجه قرار مي گيرد. به طور كل اين شغل توسط FMP4 در هر مركز صورت مي گيرد. آخرين فيلتر ، فيلتر تاكتيكال است كه با كنترل داخل يك قطر بستگي دارد. زمان متوسطي كه يك هواپيما در يك بخش صرف مي كند حدود 15 دقيقه است. اينجا ميزان رويت كنترل كننده كمي بالاتر از ميزان دريافت طرحهاي پرواز است چند دقيقه قبل از ورود هواپيما به بخش. كنترل كننده وظيفه چك كردن، حل اختلافات و همپايه بودن با بخش هاي همسايه را تضمين مي كند. در اين حالت تعيين تعريف برخورد مطلوب است. دو هواپيما با هم برخورد دارندوقتي كه فاصله جدايي افقي بين آنها كمتر 5 مايل باشد و تفاوت انها در ارتفاع كمتر از 1000 فيت باشد. روش هايي كه توسط كنترل كننده براي حل اين برخورد به كار مي رود بر پايه مسائل زير است.
بر روي تجارب قبلي و هر دانش خلاقي. وقتي كه چند جفت از هواپيماها در اختلاف مشابهي با هم تماس دارند، آنها با ساده كردن مشكلات شروع مي كنند كه فقط اختلافات ابتدايي را داشته باشند.
براي حل فيلتر اضطراري به نظر نمي رسد كه مداخله كند به جز مواردي كه سيستم كنترل دچار نقض شده يا اينكه ضعيف شده است. براي كنترل كننده ، آشيانه اطمينان مسير هر هواپيما را با افق موقت چند دقيقه ايي پيش بيني مي كنند. از موقعيت هاي رادار و الگوريتم هاي ادامه دار استفاده مي كند و يك اخطار را در لحظه برخورد بوجود مي آورد. اين يك راه حلي را براي برخورد پيشنهاد نمي كند. به طور كل TCAS به نظر مي رسد كه از چنين تصادفي جلوگيري
كند. پيش بيني موقت كمتر از يك دقيقه است (بين 25 تا 40 ثانيه) بنابر اين بسيار دير است براي كنترل كننده مانور هواپيما را، همانطور كه تخمين زده شده كه نياز به حداقل زمان 1 تا 2 دقيقه براي آناليز كردن موقعيت دارد راه حلي را پيدا كنند و آنرا به هواپيماها اطلاع دهند. به طور عمومي TCAS، هواپيماي اطاف را جستجو مي كند و به خلبان براي حل برخورد پيشنهاداتي مي كند. اين فيلتر بايد برخورد غير قابل پيش بيني را حل مي كند، براي مثال وقتي كه يك هواپيما
از سطح پرواز خود بالاتر رفته است يا يك مشكل تكنيكي كه به طور قابل توجهي ارتفاع آنرا پايين آورده است. كاربردهاي پيشنهاد شده در اين بخش با فيلتر تاكتيكال ارتباط دارند: دانستن موقعيت هواپيما در لحظه حاضر و موقعيت بعدي آنها، را بوجود نمي آورد. راه حل براي پايه چندين تصور است. يك هواپيما نمي
تواند سرعت خود را تغيير دهد (يا بسيار آرام بايد اين كار را بكند) مگر در مواقع فرود. نبايد اينطور تصور شود كه يك هواپيما با سرعت اني پرواز مي كند، به غير مواردي كه سطح بندي مي شود و هيچ بادي وجود ندارد. به علاوه در طول فرود و بلند شدن ، مسير آن يك خط صاف نيست. هواپيماها در مسير چرخش خود در فشار هستند. به طور عمومي خلبانها مانور افقي را به عمودي ترجيح مي دهند مگر در هنگام بلند شدن يا نشستن. اگر چه امروزه خلبانهاي اتوماتيك قرتمندتر از خلبانهاي انساني هستند (در موقعيت هاي نرمال پرواز) براي مواقعي كه حقيقي به نظر مي رسد توجه كردن به اين مسيرها كه توسط انسانها قابل
دسترسي نيست.
خلبان. نامطمئني بين سرعت فرود آمدن و بلند شدن بسيار زياد است (بين 10% و 50% سرعت عمودي). در طول مسافرت ، نااطميناني در سرعت كاهش مي يابد. بعد از آن ، نا اطميناني به همراه گذشت زمان بيشتر نمي شود، همانطور كه يك هواپيما، ارتفاع خود را كاملاً خوب نگه داشته است. تقريباً غير ممكن است كه به دنبال راه حل هاي آناليتكي براي حل مشكل برخورد باشيم . اما، اصلي ترين مشكل از پيچيدگي مشكل بوجود مي آيد. بخش اول اين فصل ، به معرفي بعضي از توضيحات مي پردازد كه حل مشكل برخورد براي ما قابل فهم تر مي كند و بخش دوم به تاريخچه ايي كوتاه از الگوريتمهاي آزمايش شده براي اين مشكل و محدوديتهاي آن مي پردازد. قسمت سوم مدلهاي مشكل را به جزء بررسي مي كند و پيشرفت الگوريتم ژنيتكي براي حل مشكل در بخش چهارم وجود دارد كه با آمارهاي ؟ بدست آمده دنبال مي شود.
1.1.9) پيچيدگي حل مشكل برخورد= يك برخورد را مي توان به صورت زير توضيح داد:
يك برخورد يعني برخوردي بين دو هواپيما در طول يك زمان داده شده از مسير پيش بيني شده، گرفتن نااطمينانيها در مسير.
كلاسهاي معادل مربوطه به عنوان دسته و مجموعه برخورد هواپيما يا مجموعه ايي از اندازه n مي تواند شامل شود به برخوردهاي قوي n. توجه كردن به فقط هواپيماي افقي ، نشان مي دهد كه تمام راه حل هاي قابل قبول شامل 2n(n-1) اجزاي مرتبط، تحت اين تصور كه يك متر مناسب به كاربرده شده كه نياز دارد به
اجراهاي زيادي از الگوريتم جستجو بنابر اين براي مجموعه هواپيماي 6،32768 عضو متصل پيشنهاد مي شود. در حقيقت اگر عملكرد هواپيما مورد توجه قرار گيرد، تمام اجزاي مرتبط لازم نيست كه مورد بررسي قرار گيرد. با آرام كردن محدوديت هاي جدا كننده، مشكل شبيه يك مشكل جهاني مي شود كه حداقل شامل بهينه هاي داخلي مي شود مانند اجزاي متصل. اضافه كردن بعد عمودي خصوصيت تركيبي مشكل را كم نمي كند.
2.1.9) وجود مترهاي حل كننده:
اولين پروژه اتوماتيك كنترل ترافيك ، آمريكايي بود و در شروع دهه 80 بوجود امد، اما قادر به حل مجموعه سايز 3 يا بيشتر نبود. پروژه اروپايي ARC2000 يك متر از نارساييهاي ممتر لوله چهار بعدي را پيشنهاد كرد كه مسير n+1+h هواپيما در محيط n كه قبلاً مسيرش محاسبه شده بود. ارتقاء دهد.
اين مدلها شكيات را مورد توجه قرار ندادند و قادر نبودند با حجم عظيم ترافيك مواجه شوند. در نهايت پروژه تجربي اروپايي FREER در سال 1995 كامل شد. و پيشنهاد كرد كه مي تواند برخورد هواپيماها را حل كند. مشكل همپايه بودن بين هواپيماها با به كار بردن قوانين قبلي هدايت مي شد ، كه مانند استفاده كردن از ؟ تكراري مانند ARC2000 بود، كه قادر به مواجه شدن با مجموعه هاي بزرگتر نبود.
روش هاي تئوري : در ميان تئوريهاي به كار برده شده براي حل مشكل ، ما ابتدا مي توانيم به تكنيك هاي Zeghal اشاره كنيم. با توجه به اين روش، هواپيما توسط اهدافش جذب مي شود و توسط هواپيماي نزديك برگردانده مي شود. متد وقتي كه تراكم كم است، خوب عمل مي كند، اما وقتي ترافيك زياد است بهم ريخته عمل مي كند. به علاوه ، مدل تصور مي كند كه پروازها كاملاً اتوماتيك هستند، همانطور كه مسيرها مي توانند دائماً تغيير يابند. روش هاي مشابه كه از
زمينه هاي قوي استفاده مي كردند توسط عدم هوانوردي سازمان Berkeley آزمايش شد، اما در آن زمان آنها قادر به حل بيشتر از سه مجموعه هواپيما نبودند. اين روش بسيار شبيه بود به عملكرد نشان داده شده توسط شبكه هايي كه مترهاي آزمايش بر پايه LOG (CENA-ENAC) بودند كه نمي توانستند به مجموعه هاي پيچيده افزايش يابند. بلاخره ، ميان روش هاي جهاني براي مجموعه هاي پيچيده، اولين كار اصلي توسط (فردن)Feron انجام شد. او از برنامه هاي معين
براي تعيين كردن مسير راه حل براي هر جفت از هواپيماهاي برخوردشده استفاده كرد: پس يك متد ارتقاء دهنده محدب كه شامل محدوديت هاي محدب مي شد به كار برده شد براي محاسبه كردن مانور. به هر حال اين روش در تمام موارد راه حل قابل قبولي را ارائه نمي داد. اضافه كردن صداي رَندُم به پيشرفت سرعت موفقيت كمك كرد. محدودة سادة مدل انتخاب شده، محدودة كوچكي را براي كاربرد موفق آن در موقعيت هاي پيچيده فراهم كرد. در نهايت LOG محدوديت ها و شاخه هاي فاصله را آزمايش كرد، كه مي توانست مشكل را در دسته هاي كوچك حل كند. اما قادر در نبود آن را براي دسته هاي بيشتر گسترش دهد. تا اين تاريخ فقط الگوريتم ژنتيكي توانست مجموعه هاي بزرگ را در زمان قابل قبول حل كند .
3.1.9) مدل كردن مشكلات با توجه به شبهات:
اول از همه يك زمان جستجو TW توضيح داده مي شود و يك تقليد كننده موقعيت آيندة هواپيما را در قالب زمان ارزيابي مي كند. اين تقليد كننده شبهات در سرعت افقي و عمودي هواپيما را مورد توجه قرار مي دهد همانطور كه در شكل 1-9 نشان داده شده است. در هواپيماي افقي ، هواپيما توسط يك نقطه در لحظه شروع ارائه مي شود. در مدت زمانع اين نقطه ، بخشي مي شود كه در طول آن به طور افزايش ادامه مي يابد. وقتي مسير عوض مي شود (t=4 در)
بخش ناقض مي شود در حالي كه مسير (بردار) جديد سرعت را دنبال مي كند. هواپيما پس توسط يك شكل چهار گوش هواپيمانشان داده مي شود. به كار بردن يك تغيير جديد (t=7 در) شكل چهار گوش هواپيما را به شش گوش تغيير مي دهد و به تعبير عامتر به بردار (مسير). در هواپيماي عمودي يك سيلندر مي تواند توضيح داده شود كه ارتفاع آن با زمان افزايش مي يابد. وقتي كه هواپيما به سطح مطلوب پرواز مي رسد (t=8 در) بالاي سيلندر ، ارتفاع آنرا ديگر تغيير نمي دهد و انتهاي سيلندر شروع به بالا رفتن مي كند، تا زماني كه سطح پرواز مي رسد.
جستجو برخورد:
براي جستجوي برخوردهاي قوي بين هواپيماها ، لازم است كه در هر زمان، فاصله افقي بين مسيرها و فاصله عمودي بين سيلندرهايي كه دو هواپيما را نشان مي دهد، اندازه بگيريم. برخورد وقتي اتفاق مي افتد كه استاندارهاي عمودي و افقي به طور همزمان ؟ مي كنند.
مدل كردن مانور براي اجتناب:
براي احترام گذاشتن به هر دو خلبان و نحوه انجام هواپيماها مانور ساده ايي را توضيح مي دهيم: در هواپيماي افقي، مانور يك تغيير بالايي از 10 و 20 تا 30 درجه به راست و يا چپ است ، كه در زمان t=0 شروع مي شود و در زمان t=1 تمام مي شود. در هواپيماي عمودي مانور پيشنهاد مي كند با توجه به حالت پرواز كه در آن حالت هواپيما قرار دارد. بنابر اين همانطور كه در شكل 9.2 نشان داده شده، وقتي هواپيما بالا مي رود، مي تواند بالا رفتن خود را در t=0 نگه دارد و دوباره آنرا در t=1 شروع كند. در حالت گردش و سفر ، مي تواند به پايين ترين سطح پرواز پايين آيد (1000 فيت پايين) در زمان t=0 و به اولينسطح پرواز در زما t=1 بپيوندد. وقتي هواپيما بيشتر از 50 نُتيكال از فرودش ، پايين تر است ، مي تواند فرودش را در زمان t 0 پيش بيني كند و فرود را در زمان t1 نگه دارد كه به مسير فرود خود بپيوندد. براي اينكه مانور قابل بدست آوردن باشد فقط يك مانور در هر زمان به خلبان داده مي شود. مانور جديد فقط وقتي به او پيشنهاد مي شود كه اوليد مانور تمام شده باشد. بنابر اين يك مانور توسط گونه مدل مي شود. نوع اول عيني است كه نوعي از مانور را نشان مي دهد (درجه 30-و20- و10-.30 و20 و10 ) يا مانور عمودي دو نوع ديگر t0 وt1 انواعي هستند كه شروع و پايان مانور را نشان مي دهند.
مديريت زمان واقعي:
راه حل انجام مي شود در زمان پيش بيني شده TW (بين 10 تا 15 دقيقه) و موقعيت هر ؟ دقيقه Updeate مي شود (2 تا 3 دقيقه در عمل). شكل 3-9 مدل زمان واقعي را نشان مي دهد. سه دور در محدودة زماني وجود دارد. نوع اول، طول زمان؟ دقيقه است كه زمان قفل شده ناميده مي شود. هيچ تغيير مسيري در اين دوره صورت نمي گيرد. در حقيقت در طول مدت لازم براي تخمين زدن موقعيت هواپيما پرواز خود را ادامه مي دهد. بنابر اين تغيير مسير ممكن نيست. دورة بعدي دورة نهايي ناميده مي شود، براي اينكه ترتيب مانور نمي تواند در طول تكرار بعدي تغيير يابد. آخرين دوره، دورة مانور پيش بيني شده است. اين مي تواند در طول تكرار بعدي در نظر گرفته شوند.
تقليد كننده ترافيكي:
تقليد كننده كنترل كندة ترافيك CATS يك تقليد كنندة آماري است كه از يك مدل جدولي براي پرواز دادن هواپيما ها استفاده مي كند. كه طرح پروازها را براي يك روز ترافيكي مورد توجه قرار مي دهد. هر ؟ دقيقه (2 تا 3 دقيقه در عمل) تقليد كننده مسير را براي TW دقيقه هاي بعدي پيش بيني مي كند. تقليد كننده برخوردها را براي هر جفت بررسي مي كند و سپس مجموعه ايي از هواپيماهاي در برخورد را مي سازد. هر مجموعه توسط يك حل كننده، حل مي شود كه از
الگوريتم ژنتيكي استفاده مي كند كه بري هواپيما مانور را پيشنهاد مي كند. يك پيش بيني ديد براي مسير، انجام شده است به خاطر اينكه برخوردهاي ممكن بين دو هواپيما را كه به مجموعه مشابه به تعليق ندارند، وقتي دو هواپيما از دو مجموعه متفاوت در برخورد هستند، دو مجموعه به هم پيوسته مي شوند و يك راه حل جديد انجام مي شود. اگر يك هواپيما كه در مسير برخورد نيست ، با مجموعه هواپيماها مداخله كند، با مجموعه تركيب مي شود و در راه حل جديدي عمل خواهد كرد. مرحله چندين بار تكرار مي شود، به تعداد دفعاتي كه برخوردها بين هواپيماها كه متعلق به يك مجموعه نيستندع باقي مي ماند.
4.1.9) استفاده از الگوريتم ژنتيك= كاربرد براي اينكه براي هر مجموعه ارتقاء يابد چندين موضوع را مورد توجه قرار مي دهد به خاطر اينكه تمام جداييها بين هواپيما تضمين شود. تاخير كم شود، تعداد مانورها كم شود و همچنين تعداد هواپيماهاي زير آن زمان مانورها كم شود بنابر اين هواپيما در زمان كمي آزاد مي شود.
توصيف كلي= الگوريتم ژنتيكي به كاربرده شده ، الگوريتمي ساده است همانطور كه Goldberg 1994 توضيح داده شده است. جمعيت (تعداد) اوليه از سه متغير به صورت رَندم بوجود مي آيد. پس تناسب هر شخص ارزيابي مي شود. بنابراين بهترين افراد توليد مي شود و با توجه به ميزان تطابق آنها انتخاب مي شوند. يك قسمت جمعيت 50% سپس تعداد مشخصي از افراد تحت تغيير قرار مي گيرند 15% . تغيير به طور كل، دو شكل براي تقسيم كردن اپراتور ساده مي باشد. دو مانور برابر به نظر مي رسند اگر هر دوي آنها در مسير افقي يا عمودي باشند، در حالت بعدي اگر آنها به جهت مشابه هدايت شوند. براي اندازه گيري فاصله بين دو شكل ، تعداد مانور مختلف شمرده مي شود. يك پُرسة (Process) اليتزم به كاربرده مي شود: در هر سنل، بهترين افراد گروه ، نگهداري مي شوند بنابر اين آنها در طول تغيير ، ناپديد نمي شوند.
با توجه كردن به نيازهاي موقت تحميل شده توسط زمان واقعي مديريت ترافيكي فاكتور پاياني به كاربرده شده در توقف ارتقاي مراحل در پايان تعداد مشخصي از نسلها شامل مي شود. اما اين عدد به طور افزايش باقي مي ماند اگر الگوريتم قادر به پيدا كردن راه حل بدون برخورد نباشد. (بيشترين عدد سنل ها به 40 مي باشد)
تأثير افق = حل كننده فقط يك ديد كوتاه از مسير هواپيما دارد. با ارزش كدر بردي كه به سادگي شامل مي شود در محدود كردن تأخير بوجود آمده توسط يك مانور ، حل كننده بعضي اوقات يك برخورد را ماوراي پنجره موقتي ، بدون حل آن به تعويض مي اندازد. براي مواجه شدن با تأثير افق شخص مي تواند تأثير راه حل يك برخورد را اندازه بگيرند و كاربرد مناسب و الگوريتم را براي حل برخورد ، تغيير دهد.
