سايت مقالات فارسی – تلفیق الگوریتم رقابت استعماری و انتخاب سریع زمان آماده سازی در حل مسأله برنامه ریزی …

پایان نامه های کارشناسی ارشد سری 1

همان‌گونه که بیان شد، در جریان رقابتهای امپریالیستی، خواه‌ناخواه، امپراطوریهای ضعیف به‌تدریج سقوط کرده و مستعمراتشان به دست امپراطوریهای قوی‌تر میافتد. شروط متفاوتی را می‌توان برای سقوط یک امپراطوری در نظر گرفت. در الگوریتم پیشنهادشده، یک امپراطوری زمانی حذف‌شده تلقی میشود که مستعمرات خود را ازدست‌داده باشد. شکل ۳-۱۰ این مسأله را به‌خوبی نشان میدهد. در این شکل، امپراطوری شماره ۴ به علت از دست دادن کلیه مستعمراتش، دیگر قدرتی برای رقابت ندارد و باید از میان بقیه امپراطوریها حذف شود.
۳-۳-۷- همگرایی
الگوریتم موردنظر تا برآورده شدن یک شرط همگرایی و یا تا اتمام تعداد کل تکرارها، ادامه مییابد. پس از مدتی همه امپراطوریها سقوط کرده و تنها یک امپراطوری خواهیم داشت و بقیه کشورها تحت کنترل این امپراطوری واحد، قرار میگیرند. در این دنیای ایده آل جدید، همهی مستعمرات، توسط یک امپراطوری واحد اداره می‌شوند و موقعیتها و هزینههای مستعمرات، برابر با موقعیت و هزینه کشور امپریالیست است. در این دنیای جدید، تفاوتی، نه‌تنها، میان مستعمرات، بلکه میان مستعمرات و کشور امپریالیست، وجود ندارد. به‌عبارت‌دیگر، همهی کشورها، درعین‌حال، هم مستعمره و هم استعمارگرند. در چنین موقعیتی رقابت امپریالیستی به پایان رسیده و به‌عنوان یکی از شروط توقف الگوریتم متوقف میشود.
 
شکل ۳-۱۰- سقوط امپراطوری ضعیف؛ امپراطوری شماره ۴، به علت از دست دادن کلیه مستعمراتش، دیگر قدرتی برای رقابت ندارد و باید از میان بقیه امپراطوریها حذف شود. ]۳۷ [
شبه کد مربوط به الگوریتم پیشنهادی در قسمت زیر آمده است.
۱-چند نقطه تصادفی روی تابع انتخاب کرده و امپراطوریهای اولیه را تشکیل بده.
۲- مستعمرات را به سمت کشور امپریالیست حرکت بده (سیاست همسان‌سازی)
۳-اگر مستعمره‌ای در یک امپراطوری، وجود داشته باشد که هزینه‌ای کمتر از امپریالیست داشته باشد؛ جای مستعمره و امپریالیست را باهم عوض کن.
۴-هزینه‌ی کل یک امپراطوری را حساب کن (با در نظر گرفتن هزینه‌ی امپریالیست و مستعمراتشان).
۵-یک مستعمره از ضعیف‌ترین امپراطوری انتخاب کرده و آن را به امپراطوری ای که بیشترین احتمال تصاحب را دارد، بده.
۶- امپراطوریهای ضعیف را حذف کن.
۷- اگر تنها یک امپراطوری باقی‌مانده باشد، توقف کن وگرنه به ۲ برو.
۳-۴- الگوریتم رقابت استعماری اصلاحی
چون ICA یک روش تکاملی است، پس در ابتدا باید بهوسیله تعدادی کشور (جمعیت اولیه) شروع کار کند. بنابراین p جمعیت اولیه تصادفی برای مسأله ایجاد میشود و مقادیر تابع هدف f(i)، کشورهایی که دارای مقادیر تابع هدف کمتر برای مسأله مربوطه هستند، به‌عنوان کشورهای استعمارگر در نظر گرفته میشوند و با جابجایی، اندیسهای ۱ تا m جمعیت اولیه را تشکیل میدهند. سپس به هرکدام از کشورهای استعمارگر، تعدادی مساوی از کشورهای مستعمره اختصاص مییابند به‌علاوه، به علت خاصیت تابع جزء صحیح، بقیه کشورها نیز به قویترین امپراطوری اختصاص مییابند. باید توجه داشت که اختصاص یافتن هر کشور مستعمره به کشور استعمارگر بهطور تصادفی و با احتمال برابر است. طبق حالت طبیعی که وجود دارد باید کشورهای مستعمره ازلحاظ فرهنگی و اجتماعی به سمت کشورهای استعمارگر با استفاده از تابع جذب حرکت کنند. بنابراین در این الگوریتم]۳۸ [ از روش نزدیکترین همسایه تصادفی(بهبود دهنده دونقطهای) برای تابع جذب استفاده میشود. با توجه به شکل ۳-۱۱ اگر در این روش [۴ ۲ ۵ ۳ ۱] نشاندهنده کشور مستعمره و [۵ ۲ ۱ ۴ ۳] نشاندهنده کشور استعمارگر باشد، برای مسأله توالی پرواز با ۵ مشخصه الگوریتم از اولین گره کشور مستعمره که ۱ است، شروع به حرکت میکند. سپس i=1 در نظر گرفته میشود و همسایههای ملاقات نشده ۱ در دو کشور با گرههای ۴،۳ و ۲ را درمجموعه S قرار میدهد. حال، اگر c(ij) نشاندهنده فاصله بین دو گره i و j باشد، آنگاه گرههای متعلق به S به‌احتمال v(j) مورد ملاقات قرار میگیرند.
(۳-۱۱)
فرض کنیم گره ۲ برگزیده شود؛ پس در جمعیت اولیه تاکنون [ – – ۲ ۱] به وجود میآید. بهعلاوه برای ۲، سه گره ۴، ۱ و ۵ به‌عنوان همسایه محسوب میشوند؛ اما چون قبلاً ۱ مورد ملاقات قرارگرفته شده است، از بین ۴ و ۵ که مجموعه S را تشکیل میدهند، نزدیکترین همسایه تصادفی انتخاب میگردد (باید توجه کرد که اگر مجموعه S در مرحلهای تهی شد، آنگاه گرههای تاکنون ملاقات نشده در آن قرار میگیرند). این روش سبب میگردد که به علت ممنوع شدن انتخاب کشورهای قبلاً ملاقات شده، حتماً یک جواب شدنی برای مسأله به دست آید. باید توجه کرد که جواب به‌دست‌آمده در صورتی جایگزین جواب کشور مستعمره میشود که دارای مقدار تابع هدف بهتر باشد. از طرف دیگر استفاده از این روش سبب میگردد که علاوه بر اینکه کیفیت مقادیر تابع هدف کشورهای مستعمره طبق این روال افزایش یابد، تنوع کشورهای مستعمره به علت ساختار تصادفی تابع جذب حفظ شود.
شکل ۳-۱۱ گراف همسایگی با پنج گره
بعدازاینکه تابع جذب برای همه کشورهای مستعمره نسبت به کشورهای استعمارگر انجام شد،p درصد از کشورهای مستعمره دچار انقلاب میشوند. برای این عمل از روش بهبوددهنده استفاده میشود. این روش، بر اساس انتخاب دو گره از مسأله و تعویض آن‌ها باهم کار میکند. باید توجه کرد که p درصد کشورهای هر امپراطوری بهتصادف انتخاب و این روش روی آن‌ها انجام میشود. حال، جواب‌های جدید به‌دست‌آمده از انقلاب به همراه کشورهای مستعمره امپراطوری j-ام در نظر گرفته میشوند و بهترین جوابها بهعنوان کشورهای مستعمره امپراطوری j-ام انتخاب میشوند. بعدازاینکه مقدار تابع هدف برای تمامی کشورهای مستعمره به دست آمد، امکان دارد که این کشورها دارای تابع هدف بهتری نسبت به کشورهای استعمارگر امپراطوری خود شوند. بنابراین بهترین کشورهای مستعمره در هر امپراطوری انتخاب‌شده و در صورت داشتن تابع هدف بهتر، جایگزین کشور استعمارگر میشوند.
توجه به این نکته ضروری است که در اجرای الگوریتم دو متغیر وجود دارند که مقادیر بهترین جواب و مقدار تابع هدف را ذخیره میکنند. این دو متغیر بعد از بروز شدن استعمارگرها بررسی میشوند.
در این مرحله بهترین جواب و مقدار تابع هدف کشورهای استعمارگر انتخاب‌شده و الگوریتم بهبوددهنده سهگانه بر روی آن انجام میشود و سپس مقدار به‌دست‌آمده اگر از بهترین مقدار به‌دست‌آمده در تکرارهای قبلی بهتر باشد، آن جواب و مقدار تابع هدف جایگزین میشوند. با توجه به شکل ۳-۱۲روش بهبوددهنده سهگانه بر اساس حذف کردن سه یال از تور و متصل کردن دوبارهی مشخصهای انجام میگیرد.
(۳) (۲) (۱)
شکل ۳-۱۲ بهبوددهنده سهگانه
در مرحله بعدی قدرت هر امپراطوری باید سنجیده شود تا بدین ترتیب مشخص گردد کدام امپراطوری از قدرت بیشتری برخوردار است. حال که قدرت امپراطوریها مشخص شد، باید هر امپراطوری دارای تابع هدف قدرت خود را با از دست دادن مستعمرات خود از دست بدهد. بنابراین ضعیفترین کشور از ضعیفترین امپراطوری انتخاب‌شده و به یکی دیگر از امپراطوریها ملحق میشود. باید توجه کرد که این الحاق همیشه به بهترین امپراطوری تعلق نمیگیرد. بنابراین هر امپراطوری که دارای قدرت بیشتری باشد با احتمال بیشتری این کشور مستعمره را تصاحب میکند. بهعلاوه، در اینجا اگر ضعیفترین امپراطوری هیچ مستعمرهای نداشته باشد، آنگاه آن امپراطوری حذف میشود و کشور استعمارگر به قویترین امپراطوری انتقال مییابد. در غیر این صورت الگوریتم دوباره تکرار میگردد (هر مستعمره به سمت کشور استعمارگر خود حرکت میکند) تا اینکه شرط پایانی حلقه برقرار گردد. برای شرایط پایانی حلقه در اینجا از دو شرط استفاده میشود که به‌طور همزمان در پایان هر تکرار الگوریتم موردبررسی قرار میگیرد. این دو شرط تکرار الگوریتم به تعدادی معین t بار و باقی ماندن فقط یک امپراطوری میباشند. حال، هرکدام از این دو شرط در هر زمان اتفاق بیفتد الگوریتم به پایان میرسد و بهترین جواب و مقداری که تاکنون به‌دست‌آمده است بهعنوان بهترین جواب و مقدار معرفی میگردد.

۳-۵- الگوریتم‌های ترکیبی به‌کاررفته

برای شروع در حل مسأله، مجموع تأخیرات وزندار با استفاده از الگوریتم سازندهی Earliest Ready Time(ERT) بکار میرود. از طرفی راهکار ATCS بهبودیافته و الگوریتم Adapted Apparent Tardiness Cost with separation and Ready Times(AATCSR) جهت تطبیق زمانهای آمادهسازی، خاتمه و زمانهای جدایی وابسته به‌توالی ارائه شده است.
با توجه به شکل ۳-۱۳ و با استفاده از الگوریتم ERT(Earliest Ready Time) پروازها به‌منظور افزایش ترتیب زمان آمادهسازی، به باند پروازی مشخصی هدایت میشوند. در زمان t وقتی‌که باند پروازی مشخصی خالی می‌شود آن پروازی برای استفاده از آن باند مشخص میشود که ERT آن زمان زودتری برای عملیات روی آن باند را نشان میدهد. چنین رهیافتی در نوشتههای Tsia, Lee, 1996 و Jeong, Kim,2008 مورداستفاده قرارگرفته و نتایج خوبی را نشان داده است. از طرفی منطق موجود در هیوریستیک معمول بکار رفته در پایانه فرودگاه، FCFS، به این الگوریتم نزدیک است.
یکی دیگر از الگوریتم‌های توسعه داده‌شده و کارا در این زمینه الگوریتم Adapted Apparent Tardiness Cost with Separation and Ready Times(AATCSR) میباشد که اساس و مبنای محاسبات آن حفظ نمایه اولویت برای پروازهای منتظر برنامهریزی است. این الگوریتم هیوریستیکی به‌صورت پویا می‌باشد بهطوریکه بعد از آغاز عملیات توسط پرواز مشخصی، سایر پروازها بر طبق نمایه اولویت و با استفاده از معادله زیر اولویتبندی مجدد میشوند.
(۳-۱۲)
در معادله ۳-۱۲  یعنی اولویت هواپیمای j-ام در زمان tام به‌طوری‌که K مربوط به هواپیمای آخری است که بر روی باند موردنظر عملیات داشته است.
متغیر t: زمان تصمیمگیری
: فاکتور متغیر برای تشخیص فوریت پرواز بر اساس زمان آمادهسازی
: زمانهای جدایی دو پرواز
: زمان هدف
:  زمان خاتمه
شکل ۳-۱۳ فلوچارت راهکار پیشنهادی

۴- ارزیابی سیستم

۴-۱- مقدمه

با گسترش روزافزون علم در حوزههای مختلف مؤسسههای معتبر بینالمللی شروع به فعالیت کردهاند. در صنعت هوانوردی نیز همگام با سایر صنایع این شرکتها و مؤسسهها چه در بخش خصوصی و چه در بخش دولتی در حال فعالیت هستند. برای تحقیق و ارائه سند معتبر نیاز است تا زمینه فعالیت بهروز و موردتوجه اکثر متخصصان آن حوزه باشد خصوصاً اگر معضل و مشکل قابل‌طرح دریکی از این مؤسسههای معتبر علمی و پژوهشی باشد. در علم هوانوردی و بخصوص مدیریت ترافیک هوایی می‌توان به سازمان و یا نهادهایی مثل Eurocontrol، NTSB(National Transportation Safety Board)، IATA(International Air Transport Association)، FAA(Federal Aviation Administration)، ICAO(International Civil Aviation Organization)، DLR(German Aerospace Center)، IFATCA(International Federation of Air Traffic Controllers’ Associations) اشاره کرد. برای بهبود روند تحقیق لازم دانستیم تا حین کار از آخرین اطلاعات و تحقیقاتی که در این مؤسسهها درزمینهٔ ASP انجام میگیرد مطلع شویم تا بتوانیم روش کارا و موفق‌تری ارائه داد. ضمن اینکه آخرین مقالات معتبر در این زمینه که در نشریات و اجلاس‌های معتبر بین‌المللی چاپ میشود نیز موردبررسی و مقایسه قرارگرفته است ازجمله می‌توان به کار Rabadi ]39 [در سال ۲۰۱۲ و کار Hancerligullari ]8 [در سال ۲۰۱۳ اشاره کرد که مسأله ASP را برای پروازهای ورودی و خروجی با استفاده از چند باند پروازی با در نظر گرفتن زمانهای آمادهسازی، هدف، خاتمه و زمانهای جدایی وابسته به‌توالی در نظر گرفته است.

۴-۲- مدل‌سازی روش پیشنهادی

برای مدل‌سازی این مسأله موارد زیر را در نظر میگیریم:

NAC تعداد هواپیمایی که طبق برنامهریزی انجام‌شده برای نشستن در فرودگاه موردنظر میآیند
NR شماره باند مورداستفاده در مدت‌زمان مشخص
Tمدت‌زمان مشخص

برای دانلود متن کامل پایان نامه به سایت zusa.ir مراجعه نمایید.