دسته
آرشیو
آمار وبلاگ
تعداد بازدید : 3266
تعداد نوشته ها : 2
تعداد نظرات : 0
Rss
طراح قالب
 یک الگوریتم ژنتیکی برای حل مسئله یافتن کوتاه ترین مسیر وسایز بندی جمعیت ها  چکیده- این مقاله روشی با الگوریتم وابسته به ژنتیک برای حل مسئله یافتن  کوتاه ترین مسیر (SP) ارائه می کند. کروموزوم های به طول متغیر (رشته ها) و ژن های آن ها (پارامتر ها) برای حل این مسئله مورد استفاده قرار  گرفته اند.  عملیات کراس (CrossOver) تکه کروموروم ها (تکه مسیر ها) را در مکان های کراس ناوابسته به محل تعویض کرده و عملیات موتاسیون (mutation) دگرسانی ژنتیک جمعیت را حفظ می کند.  الگوریتم پیشنهادی قادر است تمامی کروموزوم های نا مناسب را با استفاده از یک تابع تعمیر معالجه نماید. موتاسیون و کراس با کمک یکدیگر می توانند قابلیت جستجویی ارائه کنند که نتیجه آن بهبود کیفیت راه حل و تناسب همگرایی می باشد. این مقاله  همچنین یک معادله اندازه گیری سایز جمعیت که راه حلی با کیفیت مطلوب به همراه دارد ارائه می کند. آن بر اساس مدل gambler ruin (gr) می باشد، البته این معادله کمی بیشتر توسعه یافته و کلی سازی شده است.  این معادله اندازه جمعیت، کیفیت راه حل و کاردینال الفبا  و دیگر پارامتر های الگوریتم پیشنهاد شده را به یکدیگر  مرتبط می سازد.  شبیه سازی های رایانه ایی نشان می دهند که الگوریتم ارائه شده راه حلی با کیفیت بهتر (مسیر یابی بهینه) و تناسب همگرایی بالاتری نسبت به دیگر الگوریتم ها دارد. نتایج متناسبا  غیر وابسته به انواع مسائل ( سایز و همبندی شبکه) برای تقریبا تمامی جفت های منبع-مقصد می باشند. بعلاوه، بررسی های شبیه سازی تاکید بر مفید بودن معادله اندازه بندی جمعیت دارند. این معادله  قابلیت مقیاس پذیری با شبکه های بزرگتر را نیز دارد. تصوذ می شود  که از آن می توان برای تعیین اندازه جمعیت صحیح (برای کیفیت مطلوب راه حل) در مسئله مسیر یابی SP استفاده نمود.  I.مقدمهدر شبکه های چند-جهشی، مانند اینترنت و شبکه های ad-hoc (شبکه ویژه) مسیر یابی یکی از مهمترین مسائل می باشد چرا که تاثیری بسیار قابل توجه بر کارایی شبکه دارد [1][2]. یک الگوریتم مسیر یابی ایده آل می بایست در یافتن مسیری بهینه برای انتقال بسته اطلاعاتی در زمانی معین برای برآورد QoS (کیفیت سرویس) خاص [2]-[4] داشته باشد. چندین الگوریتم مسیر یابی برای حا مسئله یافتن کوتاه ترین مسیر (SP) موجود می باشند: الگوریتم breadth first، Dijksta و Belhan-ford چندین نمونه از این الگوریتم ها می باشند [1]. از آنجا که این الگوریتم ها می توانند مسائل SP را در زمان های چند فرازی (polynomial) حل کنند، آنها در فراساختار های ثابت شبکه های بیسیم مواثر خواهند بود. اما، آنها پیچیدگی محاسباتی بالایی در ارتباطات مستقیم (real-time) از خود نشان می دهند که قابل قبول نمی باشد. همبندی های آن شبکه های در پایین شرح داده شده است [3][4]. ما شبکه های سیار ad-hoc را سیستم های مد نظر قرار داده ایم چرا که آنها نسل جدید شبکه های بیسیم می باشند. از آنجا که تمامی گره ها با همکاری با یکدیگر متصل بودن شبکه را بدون یاری جستن از هیچ گونه شبکه فراساختار ثابت فراهم می کنند، تغییرات دینامیک در همبندی شبکه ممکن می باشد. یک مسیر بهینه (کوتاه ترین) باید در زمانی کوتاه (چندین ) محاسبه شود تا بتوان از سرویس هایی با محدودیت زمانی مانن صوت، تصویر و کنفرانس تلفنی پشتیبانی نمود [4][2]. الگوذیتم های اشاره شده قادر به برآورد این الزامات (real-time) نمی باشند. در بیشتر شبکه های سویچ بسته های اطلاعاتی، توعی محاسبه SP توسط الگوریتم های مسیر یابی در لایه شبکه به کار گرفته می شود [2][4]. در خصوص، پیوند های شبکه وزن گیری می شوند و این این اوزان ظرفیت فرستندگی پیوند، تراکم شبکه، حالت تخمینی شبکه مانند تاخیر بسته HOL و یا خرابی پیوند را نشان می دهند. مسئله SP را می توان فرمول نویسی کرد برای یافتن حداقل هزینه مسیر که حاوی گره های منبع و مقصد می باشند. به بیانی  دیگر، مسئله مسیر یابی SP متشکل از مسئله کلاسیک بهینه سازی ترکیبی در طراحی ها و بافت های گوناگون [2][7] می باشد. از آنجا که شبکه های عصبی (NN) [2]-[4] و الگوریتم های ژنتیکی (GA) (و دیگر الگوریتم های تکاملی) [5]-[16] ادعا بر داشتن راه حل هایی  به این گونه مسائل پیچیده دارند، آن ها با موفقیت  در شرایط مختلف به کار برده شده اند. در سوی دیگر، NN  و GA ها شاید نامزد های مناسبی برای پشتیبانی از  برنامه های کاربردی real-time در شبکه های ad-hoc سیار نباشند چرا که آن ها در کل مقدار بسیاری تکرار در بر دارند. البته بر پا سازی سخت افزاری NN و یا GA ها بسیار سریع می باشد. بعلاوه اندازه شبکه تاثیری بر آن ها ندارد [4][13] و کیفیت راه حل باز گردانده شده توسط NN، بسته به ویژگی های به ارث برده شده آن ها دارد. GA ها در این زمینه انعطاف پذیر می باشند. کیفیت (راه حل) را می توان به عنوان تابعی از جمعیت تنظیم کرد. بعلاوه سخت افزار NN اندازه محدودی دارد: آن نمی تواند با شبکه هایی با اندازه فرض به علت وجود محدودیت های فیزیکی سازگاری یابد. در سوی دیگر سخت افزار ها GA، با شبکه هایی که حتی شاید در حافظه جای نگیرند، مقیاس پذیر است. علت آن استفاده از GA موازی در چندین گره می باشد.  بنابر این GA ها (به خصوص به مار گیری سخت افزاری) از این جهت بسیار قابل قبول می باشد. A. بررسی الگوریتم های SP بر پایه GA.محققان GA را در مسئله مسیر یابی [5]-[7] SP، مسئله مسیر یابی Multicast (ارسال یکزمان به چندین مقصد) [9][8]، مسئله تخصیص پهنای باند [10] ATM، مسئله انتساب ظرفیت و جریان (CFA) [11] و مسئله مسیر یابی دینامیک [12] به کار برده اند. مشاهده شده است که تمامی این مسائل را می توان با استفاده از ترکیبی بهینه سازی شده فرمول دهی نمود.  الگوریتم Munemoto عملا برای محیط های سیمی و بیسیم مناسب است. آن از کروموزوم هایی با طول های مختلف برای حل مسائل استفاده می نماید. مکان های کراس (نقاط) loci می باشند (مکان گره های در یک مسیر)، که در اینجا ژن های مشابه (گره ها) در هز دو کروموزوم انتخاب شده (مسیر ها) در یک مکان یافته می شوند. بنابر این شرایطی به وجود می آید که در آن فقط چندین مکان کراس قابل  استفاده برای جستجوی راه حل های مناسب می باشد.  به بیان دیگر، کراس کاملا وابسته به مکان ها می باشد. مسلما ژن های مشابه باید از یک مکان هندسی برای انجام کراس استفاده نمایند. مجموعه مکان های نامزد برای کراس "مکان های ممکن برای کراس" نام دارند. یک مکان هندسی به صورت تصادفی انتخاب می شود برای  ایفای نقش  به عنوان مکان کراس و معاوضه کروموزوم های مولد. در فاز موتاسیون، یک ژن (گره موتاسیون) به صورت تصادفی از کروموزوم انتخاب می شود. یک ژن دیگر از کروموزوم مستقیما متصل به گره موتاسیون به صورت تصادفی انتخاب می شود و یک کروموزوم  موتاسیون شده با ترکیب هر تکه از کروموزوم های دیگر (تکه مسیر) با استفاده از الگوریتم Dijksta تولید می شود. لازم به ذکر است که یک تکه مسیر اشاره به کوتاه ترین مسیر از گره منبع به گره منتخب و دیگر اشاره به کوتاه ترین مسیر از گره منتخب به گره مقصد دارد. اما، الگوریتم نیاز به جمعیت نسبتا بالایی برای داشتن راه حلی بهینه، به دلیل محدودیت هایی که در مکانیسم کراس موجود است، دارد. بعلاوه آن برای شبکه های بزرگ و ارتباطات مستقیم مناسب نیست چرا که الگوریتم Dijksta هزینه های محاسباتی منع کننده ایی داراست.Inagki [6] الگوریتمی پیشنهاد کرده است که از کروموزوم هایی با سایز ثابت (تعیینی) استفاده می کنند. کروموزوم ها در یک الگوریتمک ترتیبی از اعداد (integer) بوده و هر ژن گویای شناسه گره ایی است که به صورت تصادفی از مجموعه گره های متصل به گره منطبق به عدد مکان هندسی انتخاب می شود. تمامی کروموزوم ها طول برابر و ثابتی دارند. در فاز کراس یکی از ژن ها (از دو کروموزوم مولد) در مکان هندسی  شناسه گره آغازگر انتخاب و در مکان هندسی مولود قرار داده می شود. یکی از ژن ها سپس به صورت تصادفی در مکان هندسی عدد قبلا انتخاب شده یک ژن انتخاب می شود. این فرایند تا زمان یافت گره مقصد ادامه می یابد. جزئیات موتاسیون در الگوریتم توضیح داده نشده اند. الگوریتم نیازمند جمعیت زیادی  برای به دست آوردن راه حلی بهینه و با کیفیت بالا می باشد که دلیل آن مکانیسم بی ثبات کراس است. بعضی از مولود ها می توانند کروموزوم هایی تولید کنند که مشابه با کروموزوم های اولیه بوده و در نتیجه فرایند تکامل را عقب بیاندازند. چندین GA وجود دارند که به حل مشکلات مسیر یابی می پردازند، مانند مسائل multiple destination (چندین مقصد)  و مسیر یابی  ارسال همزمان (multicast) [7]-[9]. آن روش ها فراتر از طیف این مقاله می باشند. البته، الگوریتم های unicast و الگوریتم تک مقصدی  مانند الگوریتمی که در اینجا پیشنهاد شده است را می توان  توسعه داده و در نتیجه آن ها را شامل شد.  B. بررسی معادله سایز جمعیتسایز جمعیت که راه حلی بهینه و با سرعت زیاد را گارانتی می کند موضوع  یک سری تحقیقات شدید می باشد [12][22]. جمعیت های زیاد معمولا راه حلی بهتر دارا می باشند اما هزینه محاسباتی نیز بیشتر است. Holland[7] مسئله k-armed bandit را  به عنوان پشتوانه تئوریک GA ها مورد بررسی قرار داد. Macreddy و Wolpert[18] خطایی ریاضیاتی در تحلیل Holland نشان داده و جایگزینی تسهیل یافته تر که مستقیما قابل استفاده در تئوری بهینه سازی می باشد ارائه کرده اند. De Jong et al[19] یک معادله سایز بندی جمعیت بر اساس سیگنال و ویژگی صواهای زائد مسئله k-armed bandit  پیشنهاد کرده است. اگرچه نتایج به صورت مجزا نقش تناسب سیگنال-به-صدای زائد را در تخمین سایز جمعیت  نشان می داد، نتایج نادیده گرفته شدند [22][21].Goldberg et al [20] اولین معادله سایز بندی جمعیت بر پایه متغیر بودن شایستگی را تولید نمود. Goldberg et al[21] معادله را به عنوان محدوده ایی محافظه کارانه بر کیفیت GA ها افزود. معادله سایز بندی جمعیت تصمیم گیری صحیح آماری را در میان بلوک های سازنده در حال رقابت مقدور می سازد. رابطه  سایز بندی جمعیت دقت حقیقی هم گرایی GA را تا زمانی که تمامی منابع عمده صداهای زائد جنبی  در محاسبه به حساب آیند به صورت محافظه کارانه محدود می کند. Harik et al [23] همچنین معادله سایزبندی جمعیت توسعه داده است که از مسئله random walk الهام می گیرد: به خصوص مسئله gr. با استفاده از مسائل آزمایشی از آسان تا دشوار، دقت مدل مشخص شده، البته فعالیت آن، محدود به کروموزوم هایی با طول محدود بوده و بعلاوه آن نیاز به اطلاعات تصادفی مانند متغیر بودن سزاواری (صدای زائد) و مقدار تفاوت مورد انتظار سزاواری  (سیگنال) بین بهترین و یکی پیش از بهترین بلوک های سازنده (BB)، گسستی و یا ترسیمی می باشد. البته این اطلاعات ممکن است  در بسیای ار مسائل عملی مانند مسائل مسیر یابی و یا زمان بندی موجود نباشند. C. اهداف و سامان دهیدر این مقاله، ما یک GA جدید برای حل مسئله مسیر یابی SP پیشنهاد می کنیم. کروموزوم هایی با طول های متغیر به کار گرفته شده اند. گره های  معرفی کنند آن ها در یک مسیر بین  جفتی برگزیده شده از گره های منبع و مقصد می باشند. عملیات کراس تکه کروموزوم ها (تکه مسیر) تعویض و موتاسیون تکه کروموزوم ها تکه ایی جدید معرفی می کنند (تکه مسیر).  نبود وابستگی مکانی از جهت مکان های کراس کمک به حفظ دگر سانی جمعیت می کند. بعلاوه، یک تابع ساده تعمیر برای مدیریت کروموزوم هایی نامناسب پیشنهاد شده است. این مقاله  همچنین یک معادله سایز بندی جمعیت معرفی می کند که برای GA پیشنهادی راه حلی با کیفیت مطلوب فراهم می کند. آن بر اساس مدل gr که در [22] مورد بحث قرار گرفت می باشد. البته، معادله در این مقاله کمی بیشتر توسعه یافته و کلی سازی شده است.  آن رابطه های بین سایز جمعیت و کیفیت راه حل و کاردینالی آلفابت و دیگر عوامل GA پیشنهادی را نمایان می سازد.باقی این مقاله بدین گونه سامان دهی شده است: در قسمت 2، GA پیشنهادی برای مسئله یافتن کوتاه ترین مسیر شرح داده شده است. یک معادله سایز بندی جمعیت در قسمت 3 مشتق می شود. در قسمت 4، الگوریتم پیشنهادی و چندین الگوریتم موجود در چندین شبکه با هزینه پیوند، سایز شبکه و همبندی فرض به مار گرفته می شوند.  در ادامه یک بررسی مقایسه ایی خواهیم داشت. بعلاوه، این قسمت صحت معادله سایز بندی جمعیت را با استفاده از بررسی شبیه سازی ها نشان می دهد. سپ با خلاصه و نتیجه گیری این مقاله به پایان می رسد.2. GA پیشنهادی برای مسئله مسیر یابی SP.همبندی زیرین شبکه های چند جهشی را با گراف  نشان می دهند که در اینجا N مجموعه ایی از N گره (راس ها) و A مجموعه ایی از پیوند های آن (قوس، لبه) [1]-[4] می باشد. یک هزینه  به هر پیوند  منتسب است. هزینه ها با ماتریس هزینه  مشخص شده اند که  نشانگر هزینه ارسال یک بسته به هر پیوند  می باشد. گره های منبع و مقصد با S و D به ترتیب نشان داده می شود. هر پیوند، یک نشانگر اتصال به پیوند  دارد که نقش کروموزوم  با ارائه اطلاعات در مورد آن که آیا پیوند از گره i به گره j در مسیر می باشد یا که خیر است.آن را به این گونه می توان تعریف کرد:   = 1 اگر پیوند از گره i به گره j در مسیر موجود است0 در غیر این صورت.(1)  مسلم است که تمامی عناصر مورب  باید 0 باشند. استفاده از تعاریف بالا، مسئله مسیر یابی SP را می توان با مسئله ترکیبی بهینه سازی فرموله کرده و تابع مورد نظر را (2a) حداقل نمود، بدین طریق:  محدودیت (2b) اطمینان کسب می کند که نتایج محاسبه شده در حقیقت یک مسیر بین منبع و مقصد مورد نظر می باشد (بدون ایجاد حلقه loop). A. نمایانگر سازی ژنتیکیک کروموزوم GA پیشنهادی متشکل از ترتیبی از اعداد مثبت که شناسه هایی از گره هایی که از بین آن ها مسیر قابل عبور است می باشد. هر مکان هندسی کروموزوم نشانگر ترتیبی از یک گره در مسیر است (با ژن مکان هندسی نشان داده می شود). ژن مکان هندسی در ابتدا همواره برای  گره منبع  رزرو شده است. طول کروموزوم متغیر است اما نباید از طول حداکثر N بیشتر باشد، که N کل تعداد گره ها در یک شبکه است، از آنجا که آن نیاز به بیش از تعداد N گره برای شکل دهی یک مسیر ندارد. یک کروموزوم (در مسیر) مسئله را با لیست کردن شناسه گره ها از منبع به گره مقصد بر اساس پایگاه داده های اطلاعات همبندی شبکه حل می کند. این اطلاعات را می توان به آسانی به دست آورده و در حالت real time مدیریت نمود، با مسیر یابی پروتکل هایی مانند RIP [23], OSFP [24], DSDV [25], DSR [26], و VCRP [27] در محیط های سیمی و بدون سیم، اما مکانیسم های پر جزئیات و دیگر مسائل بحث آفرین در طیف این مقاله نمی باشد. ذکر شده است که پایگاه داده های اطلاعات همبندی شبکه را می توان به سادگی و با سرعت با استفاده از این گونه پروتکل های نسیر یابی ساخت. شکل 1. مثالی از رد مسیر یابی و الگوی کد بندی آن یک مثال از کد بندی کروموزوم (رد مسیر یابی) از گره S به گره D در شکل 1 نشان داده شده است. کروموزوم لیستی از گره ها در مسیر ساخته شده  می باشد. در شکل 1، L نشانگر تعداد گره های سازنده یک مسیر می باشد. ژن اولین شکل هندسی گره منبع را کدبندی می کند و ژن شکل هندسی دوم به صورت تصادفی و یا اتفاقی از گره های متصل به گره منبع (s) که با آلل ژن جلویی نشان داده شده است، انتخاب می شود.  یک گره انتخابی از پایگاه داده های اطلاعات همبندی حذف می شود، برای اجتناب از این که یک گره دوبار انتخاب نشود و در نتیجه از ایجاد حلقه (loop) در مسیر جلوگیری شود. این فرایند تا زمان یافتن گره مقصد ادامه می  یابد: ذکر شده است که کد بندی فقط زمانی ممکن است که هر مرحله از مسیر از یک پیوند فیزیکی در شبکه عبود کند. B.مقدار دهی اولیه جمعیتدر کل، دو مطلب باید برای مقدار دهی اولیه GA مورد توجه  قرار گیرد. سایز اولیه جمعیت و فرایند مقدار دهی اولیه جمعیت [14][15]. فرض بر آن است که اندازه جمعیت نیاز به افزایش به صورت تصاعدی با پیچیدگی مسئله (طول کروموزوم) دارد تا بتوان راه حل های مناسبی تولید نمود. با این وجود مطالعات اخیر نشان داده اند که نتایجی قابل قبول را می توان با سایز های بسیار کوچکی از جمعیت  نیز به دست آورد. برای خلاصه سازی، جمعیت زیاد مفید است اما نیازمند هزینه گزافی از لحاظ زمانی و حافظه [14]-[22] می باشد. همان طور که انتظار می رود، تصمیم گیری سایز جمعیت مناسب برای داشتن راندمانی بالا حیاتی است. دوم، راه حل هایی برای تولید جمعیت اولیه وجود دارد: مقدار دهی اولیه تصادفی و اتفاقی. اگر چه این یعنی سزاواری مقدار دهی اولیه اتفاقی بالا است و ممک است به GA در یافتن راه حل کمک کرده و آن را تسریع بخشد، آن ممکن است فقط قسمت کوچکی از فضای راه حل های موجود را جستجو کرده و راه حلی  سراسری و بهینه به دلیل نبود تنوع در جمعیت بیابد [15]. بنابر این، مقدار دهی اولیه تصادفی در این مقاله تحت تاثیر قرار گرفته به گونه ایی که جمعیت اولیه با روش کد بندی توضیح داده شد در قسمت 2A تولید می شود. به صورت فیزیکی، مقدار دهی تصادفی ژن هایی از پایگاه داده های اطلاعاتی همبندی به طریقی تصادفی در حین فرایند کدبندی انتخاب می کند. این ممکن است که الگوریتم به گره ایی برخورد کند که به تمامی همسایگان آن قبلا سرکشی شده است. در این مورد، کروموزوم نامناسب تجدید و مجددا مقدار دهی اولیه می شود. این شاید یک انحراف تبعیضی ایجاد کند که در آن بعضی تکه مسیر ها امکان بیشتری  برای تولید داشته باشند. البته، گرایش های ناچیز تاثیر چندانی بر کارایی الگوریتم ندارند. C. تابع شایستگیتابع سایشتگی کروموزوم ها را بر حسب نشانکر های فیزیکی تفسیر کرده و سزاواری  آن ها را بر حسب خصوصه مطلوب بودن در راه حل [7][17] ارزیابی می کند، اما تابع شایستگی باید به درستی کیفیت کروموزوم ها در جمعیت را اندازه گیری نماید. تعریف تابع شایستگی، بنابراین، بسیار حیاتی می باشد [15]. تابع شایستگی در مسئله مسیر یابی SP بسیار واضح است چرا که محاسبه SP برابر یافتن کم هزینه ترین مسیر می باشد.  بنابر یک تابع شایستگی که شامل راندمان بالای محاسباتی و دقت بالا باشد بدین گونه تعریف شده است: که  نشانگر مقدار شایستگی کروموزوم،  طول کروموزوم i و  نشانگر شکل هندسی j در کروموزوم i و C هزینه پیوند بین گره ها می باشد.تابع شایستگی GA ها کلا تابع هدف می باشد که نیاز به بهینه سازی دارد. [7][14][15]. به طریقی، تابع شایستگی [(3)] می تواند کاملا منعکس کننده تابع هدف [(2a)] تصور شود. تابع شایستگی ارزش بیشتری دارد زمانی که ویژگی های شایستگی کروموزوم بهتر از دیگران باشد. بعلاوه تابع شایستگی یک معیار برای انتخاب کروموزوم ها فراهم می کند. D. انتخاب: اپراتور انتخاب (تولید مثل) به منظور بهبود متوسط کیفیت جمعیت  با دادن شانس بیشتر تکثیر به کروموزومی که کیفیتی بالاتری دارد این عمل را به انجام می رساند [14][15]. انتخاب در نتیجه تمرکز به جستجوی ناحیه هایی با شانس بهتر در فضای جستجو دارد. فشار انتخاب الگوی انتخاب را مشخص می کند. آن نسبت احتمال انتخاب بهترین کروموزوم در جمعیت به متوسط کروموزوم ها تعریف شده اند. بنابراین، نتیجه فشار بالای انتخاب رسیدن سریع جمعیت به حالت متوسط و در نتیجه کاهش تنوع ژن ها دارد (همگرایی به راه حل تقریبا بهینه). در حال حاضر دو نوع الگوی انتخاب مورد استفاده قرار می گیرد: الگوی سازوار و اردینال (رتبه ایی) [15][14]. هر دو الگوی انتخابی زمانی که فشار انتخاب مناسب نباشد صدمه می بینند (پایین و یا بالا).انتخاب سازوار کروموزوم هایی بر اساس مقدار شایستگی آن ها در تناسب با شایستگی دیگر کروموزوم ها در جمعیت انتخاب می کند. آن در کل بیشتر تحت تاثیر فشار انتخاب قرار می کیرد. بنابر این یک تابع مقیاس پذیر برای توزیع مجدد دامنه شایستگی جمعیت به منظور وفق به فشار انتخاب به کار گرفته می شود. مثال این گونه انتخاب شامل دو  انتخاب roulette wheel، انتخاب باقیمانده اتفاقی و انتخاب سراسری اتفاقی می باشد. الگوهای بر اساس معمول کروموزوم هایی بر پایه رتبه آن ها در جمعیت و نه شایستگی انتخاب می کنند. کروموزوم ها طبق مقادیر شایستگی خ.د رتبه دهی می شوند. ذکر شده است که فشار انتخاب (شدت) مجزا از توزیع شایستگی جمعیت بوده و فقط بر پایه رتبه نسبی در جمعیت می باشد. از آنجا که فشار انتخابی درجه ایی است که در آن کروموزوم های بهتر مورد تبعیض قرار می گیرند، آن GA ها را به سوی شایستگی بهتر جمعیت در نسل های موفق می برد. البته، آن ممکن است بد سرشت شود زمانی که فشار انتخابی سطحی مناسب ندارد. به بیانی دیگر، ممکن است آن از قشار بالای انتخابی لطمه ببیند.  الگوهای ، ،  (کوتاه سازی)،  (رتبه دهی خطی) از نوع انتخابی ordinal (ترتیبی/رتبه ایی) می باشند. معمولا سایز Tournament حدود 5 برابر 2 جفتی می باشد و فشار انتخاب را تنظیم می کند: فشار انتخابی با بزرگ شدن سایز Tournament افزایش می یابد[22][15].به یاد آورید که فشار انتخابی متوسط شایستگی مورد انتظار جمعیت بعد از انتخاب می باشد. هر چه فشار انتخاب بیشتر شود، احتمال تصمیم گیری اشتباه به صورت تصاعدی افزایش می یابد (اگرچه همگرایی GA ها می تواند پر سرعت باشد [22]).بنابر این  انتخاب جفتی Tournament بدون جایگزینی برای GA پیشنهادی به کار گرفته شده است: دو کروموزوم انتخاب شده و کروموزومی که مناسب تر است انتخاب می شود. البته یک کروموزوم نباید دوبار به عنوان مولد انتخاب شود. E. کراس (CrossOver)کراس راه حل صحیح را بررسی می کند تا بتواند بهترین را انتخاب کند [14][15]. لز لحاظ فیزیکی، کراس در مسئله مسیر یابی SP نقش معاوضه هر قسمت مسیر دو کروموزوم انتخابی را به گونه ایی که هر مولد تولید شده توسط کراس فقط بیانگر یک مسیر می باشد بازی می کند. این انتخاب کراس یک-نقطه را به عنوان الگوی مناسبی برای GA پیشنهادی دیکته می کند. یک تکه مسیر گره منبع را به گره میانی متصل کرده و تکه مسیر دیگر گره میانی را به گره مقصد متصل می کند. کراس بین دو مولد مسلط منتخب با این فرایند انتخاب، احتمال بالاتری در تولید اولاد هایی که نشان های مسلط بودن دارند را دارد. اما مکانیسم کراس برابر با کراس معمول تک-نقطه ایی نمی باشد. در الگوی پیشنهادی، دو کروموزوم منتخب برای کراس باید حداقل یک ژن مشابه (گره) داشته باشند بجز برای گره های منبع و مقصد و الزامی وجود ندارد که آن ها در یک مکان هندسی قرار گیرند. یعنی، کراس اتکا بر مکان گره ها در مسیر ندارد. شکل 2(a) و (b)  شبه کد  و مثالی از فرایند کراس را به ترتیب نشان می دهد.همان طور که در شکل 2(b) نشان داده شده است، یک مجموعه از جفت های نظیر های گره ها که در دو کروموزوم بوده اما با بی ثباتی مکانی همراه هستند ابتدا شکل می گیرد. مثال (3،2) و (5،4). این گونه جفت ها همچنین مکان های احتمالی برای کراس خوانده می شوند. سپس، یک جفت  (3،2) به صورت تصادفی انتخاب شده و مکان هندسی هر گره محل کراس کروموزوم ها می شود. نقاط کراس دو کروموزوم می توانند متفاوت باشند. شکل2a. شبه کد کراس این در تضاد با مدل به کار گرفته شده در الگوریتم  Munemoto[5] می باشد. هر قسمت مسیر معاوضه و سرهم می شود و در نتیجه  دو مسیر جدید ساخته می شود. امکان ایجاد حلقه (loop) در حین کراس وجود دارد. به این دلیل یک اقدام  متقابل می بایست در این زمینه انجام شود: تناسب هم گرایی و کیفیت راه حل. البته  این گونه کروموزروم ها (مسیر هایی به همراه حلقه)  بعد از گذشت چندین نسل از بین می روند چرا که این گونه نشان ها مقدار شایستگی را از بد به بدتر کاهش می دهد. تابع تعمیر و جریمه معمولا اقدامات متقابلی بر عهده دارند. این مسئله در قسمت 2-G شرح داده شده است.    F. موتاسیونجمعیت با تغییری حقیقی و یا جایگزینی یکی از ژن های کروموزوم های نامزد و در نتیجه از بهینه ایی محلی [14][15] موتاسیون می شود. از لحاظ فیزیکی، آن یک تکه مسیر جایگزین از گره موتاسیون تا گره مقصد در GA ارائه شده تولید  می کند. اطلاعات پایگاه داده های همبندی بدین منظور به کار گرفته می شود. البته موتاسیون ممکن است موجب به وجود آمدن گرایش  به سوی ناچگالی، به دلایلی که قبلا اشاره شد، شود (قسمت 2B). البته این تبعیض را می توان نادیده گرفا. این مسئله در زیر توضیح داده شده است.  ابتدا موتاسیون باعث افزایش در احتمال به وجود آمدن این تبعیض می شود. دوم، انتخاب و کراس به شدت طریق انجام عملیات این گرایش را تحت تاثیر قرار می دهند. البته، این تاثیرات توئم با ضرر تقریبا کلا از بین می روند. بعلاوه این گرایش زمانی که کمک به یافتن یک راه حل بهینه می کند، شاید هیچ تاثیر منفی به وجود نیاورد. شکل 3 نشانگر فرایند کلی عملیات موتاسیون می باشد. همان طور که در شکل 3(b) نیز می توان مشاهده کرد، برای آن که بتوان یک موتاسیون به انجام رسانید در ابتدا یک ژن (گره N) به صورت تصادفی از کروموزوم (نقطه موتاسیون) انتخاب می شود. یکی از گره ها که مستقیما به نقطه موتاسیون به گره اول متصل هستند به عنوان تکه مسیر جایگزین به صورت تصادفی انتخاب می شود. باقی عملیات همانند آنچه در قسمت 2A و 2B گفته شد به انجام می رسد. البته گره هایی که قبلا در قسمت بالایی مسیر بودند باید از پایگاه داده ها حذف شوند با در مسیز جدید از یک گره دوبار استفاده نشود. تکه مسیر بالایی نشانگر قسمت باقی مانده مسیر قبلی بعد از موتاسیون می باشد. آن تکه کروموزومی است که از ژن اول به ژن میانی در نقطه موتاسیون کشیده شده است.شکل2(b) نمونه ایی از عملیات کراس G.تابع تعمیرهمان طور که قبلا اشاره شد، عملیات کراس ممکن است به وجود آمدن کروموزوم های نا مناسب را سبب شود که محدودیت های 2b را زیر پا گذاشته و حلقه هایی در مسیر به وجود آورد. لازم به ذکر است که هیچ کدام از کروموزوم های جمعیت اولیه و یا بعد از موتاسیون نا مناسب هستند چرا که زمانی که یک گره انتخاب شد، آن از نامزد گره های تشکیل دهنده باقی مسیر حذف می شود.دو استراتژی این چنینی برای مدیریت کروموزوم های نامناسب وجود دارد: یکی تعمیر آن ها و دیگر داشتن جریمه [15] برای آنها می باشد. اگر چه روش تعمیر عمدتا مورد استفاده قرار می گیرد، معالجه کروموزوم های نامناسب همواره آسان نمی باشد. یک روش کلاسیک از تابع جریمه استفاده می نماید. لازم به ذکر است که تابع جریمه نقش حیاتی دارد برای کسب اطمینان از همگرایی و کیفیت بالای راه حل. امل نمی توان به آسانی یک تابع جریمه مناسب به دست آورد. بعلاوه، این تکنیک ممکن است چندین کروموزوم مناسب را نیز قربانی کند چرا که کروموزوم های نامناسب ممکن است در GA پیشنهاد شده ادامه به تولید نمایند. خوشبختانه، مکانیسمی که ژن های مرگبار (حلقه ساز) را حذف می کند می تواند تمامی کروموزوم های نامناسب را در GA پیشنهادی معالجه نماید. شکل3a: شبه کد موتاسیون تابع تعمیر بدون افزایش هزینه محاسباتی حلقه ها را یافته و از مسیر حذف می کند. تابع تعمیر پیشنهادی در شکل 4(a) شرح داده شده است و مثالی از آن نیز در شکل 4(b) موجود می باشد. در شکل 4(b) یکی از مولد های تولید شده بعد از عملیات کراس نامناسب می گردد چرا که مسیر شامل حلقه  است. تابع تعمیر حلقه را با جستجوی ساده که در شکل 4(a) شرح داده شد شناسایی می کند. تابع در L، طول کروموزوم خطی می باشد. بعد از آن، ژن های مرگبار (که تشکیل حلقه می دهند) که محدودیت ها را زیر پا می گذارند، پاک می شوند.  آن گره ها در این مثال  هستند. 3.سایز بندی جمعیتدر این قسمت، سایز جمعیت (تعداد کروموزوم ها* که کیفیت خاصی از راه حل را تضمین می کند مورد تحقیق قرار می گیرد، با به کار گیری مسئله gr که ابتدا توسط Harik[22] مورد توجه قرار گرفت. پرسش چگونگی انتخاب سایز مناسب چمعیت برای دامنه ایی خاص دشوار بوده و محققان را  دچار مشکل کرده است. اگر اندازه جمعیت بسیار کم باشد، احتمال آن که GA راه حل هایی با کیفیت بالا بیابد کم است. البته اگر سایز جمعیت بیش از حد زیاد باشد، سرعت همگرایی GA کم خواهد بود. Harik[22] تشابهات مسئله gr و مکانیسم انتخاب GA ها را برای یافتن سایز مناسبی از جمعیت که راه حلی با کیفیت مطلوب به همراه دارد را مورد بررسی قرار داده است. قسمت رتبه گذاری خطی تلویحا تصور شده است چرا که  مدل تصمیم گیری [21] (که نتیجه مستقیم [22] است) تحت این الگوی انتخابی بسیار مناسب است. ضمنا همچنین تصور شده است که موتاسیون اپراتور  برتر نمی باشد چرا که آن همراه BB ها را مختل می کند.  برای آن که بتوان از نتایج او استفاده نمود، چندین متغیر دامنه-وابسته باید شناخته باشند، مانند سیگنالی که با تفاوت شایستگی  بین BB بهترین و یکی بعد از بهترین و صدای اضافی که با تغییر شایستگی rms متعلق به BB که تحت نظر است و تعداد BB ها در یک رشته (String) تعریف شده است. معادله سایز بندی جمعیت، بنابراین، برای استفاده در مسئله مسیر یابی SP مناسب نیست چرا که GA کروموزوم هایی با طول متفاوت دارد. بعلاوه، تناسب سیگنال به صدای زائد (SNR)، مهمترین قسمت فعالیت های او، معمولا در این گونه مسائل شناخته شده نیست. شکل3b. مثالی از فرایند موتاسیون  مدل تصمیمی Harikنتایج زیر از مدل Harik انتخابی منشا می گیرد. رقابتی بین کروموزوم  که شامل BB بهینه،  (با حداقل شایستگی  و تغییرات شایستگی  ) و یک کروموزوم  با یکی پیش از بهترین BB،  (با حداقل شایستگی  و تغییرات شایستگی ) می باشد تصور کنید. احتمال تصمیم گیری صحیح بین دو کروموزوم برابر احتمال آن است که شایستگی  بیش از شایستگی  باشد: احتمال آن که . فاصله بین شایستگی حداقل کروموزوم با  و حداقل شایستگی کروموزوم با  با  نشان داده می شوند.  با تصور آن که شایستگی یک تابع افزونی تاثیر شایستگی تمامی BB ها است،  و  معمولا توزیعی می باشند (با تئوری محدودیت مرکزی).  
دسته ها :
يکشنبه نهم 1 1388
X