الگوريتم ژنتيك و فرايند بهينه سازي ...

وقتي اولين بار سر كلاس اسم الگوريتم ژنتيك شنيدم خيلي برام عجيب بود كه اين موضوع چه رابطه اي با درس هوش مصنوعي داره طبق جستجوهايي كه انجام دادم مقاله اي كه در سايت ويكي پديا نظرمو جلب كرد كه خيلي خوب اين موضوع رو توضيح ميده و به پيشنهاد استادم تصميم گرفتم اين مطلب رو براي شما دوستان عزيز هم قرار بدم....

مقدمه

هنگامی که لغت تنازع بقا به کار می‌رود اغلب بار ارزشی منفی آن به ذهن می‌آید. شاید همزمان قانون جنگل به ذهن برسد و حکم بقای قوی‌ترها!

البته همیشه هم قوی‌ترین‌ها برنده نبوده‌اند. مثلاً دایناسورها با وجود جثه عظیم و قوی‌تر بودن در طی روندی کاملاً طبیعی بازیِ بقا و ادامه نسل را واگذار کردند در حالی که موجوداتی بسیار ضعیف‌تر از آنها حیات خویش را ادامه دادند. ظاهراً طبیعت، بهترین‌ها را تنها بر اساس هیکل انتخاب نمی‌کند! در واقع درست‌تر آنست که بگوییم طبیعت مناسب ترین‌ها (Fittest) را انتخاب می‌کند نه بهترین‌ها.

قانون انتخاب طبیعی بدین صورت است که تنها گونه‌هایی از یک جمعیت ادامه نسل می‌دهند که بهترین خصوصیات را داشته باشند و آنهایی که این خصوصیات را نداشته باشند به تدریج و در طی زمان از بین می‌روند.

مثلا فرض کنید گونه خاصی از افراد، هوش بیشتری از بقیه افرادِ یک جامعه یا کولونی دارند. در شرایط کاملاً طبیعی، این افراد پیشرفت بهتری خواهند کرد و رفاه نسبتاً بالاتری خواهند داشت و این رفاه، خود باعث طول عمر بیشتر و باروری بهتر خواهد بود (توجه کنید شرایط، طبیعیست نه در یک جامعه سطح بالا با ملاحظات امروزی؛ یعنی طول عمر بیشتر در این جامعه نمونه با زاد و ولد بیشتر همراه است). حال اگر این خصوصیت (هوش) ارثی باشد بالطبع در نسل بعدی همان جامعه تعداد افراد باهوش به دلیل زاد و ولد بیشترِ این‌گونه افراد، بیشتر خواهد بود. اگر همین روند را ادامه دهید خواهید دید که در طی نسل‌های متوالی دائماً جامعه نمونه ما باهوش و باهوش‌تر می‌شود. بدین ترتیب یک مکانیزم ساده طبیعی توانسته است در طی چند نسل عملاً افراد کم هوش را از جامعه حذف کند علاوه بر اینکه میزان هوش متوسط جامعه نیز دائماً در حال افزایش است.

بدین ترتیب می‌توان دید که طبیعت با بهره‌گیری از یک روش بسیار ساده (حذف تدریجی گونه‌های نامناسب و در عین حال تکثیر بالاتر گونه‌های بهینه)، توانسته است دائماً هر نسل را از لحاظ خصوصیات مختلف ارتقاء بخشد.

البته آنچه در بالا ذکر شد به تنهایی توصیف کننده آنچه واقعاً در قالب تکامل در طبیعت اتفاق می‌افتد نیست. بهینه‌سازی و تکامل تدریجی به خودی خود نمی‌تواند طبیعت را در دسترسی به بهترین نمونه‌ها یاری دهد. اجازه دهید تا این مسأله را با یک مثال شرح دهیم:

پس از اختراع اتومبیل به تدریج و در طی سال‌ها اتومبیل‌های بهتری با سرعت‌های بالاتر و قابلیت‌های بیشتر نسبت به نمونه‌های اولیه تولید شدند. طبیعیست که این نمونه‌های متأخر حاصل تلاش مهندسان طراح جهت بهینه‌سازی طراحی‌های قبلی بوده‌اند. اما دقت کنید که بهینه‌سازی یک اتومبیل، تنها یک "اتومبیل بهتر" را نتیجه می‌دهد.

اما آیا می‌توان گفت اختراع هواپیما نتیجه همین تلاش بوده است؟ یا فرضاً می‌توان گفت فضاپیماها حاصل بهینه‌سازی طرح اولیه هواپیماها بوده‌اند؟

پاسخ اینست که گرچه اختراع هواپیما قطعاً تحت تأثیر دستاورهای صنعت اتومبیل بوده است؛ اما به‌هیچ وجه نمی‌توان گفت که هواپیما صرفاً حاصل بهینه‌سازی اتومبیل و یا فضاپیما حاصل بهینه‌سازی هواپیماست. در طبیعت هم عیناً همین روند حکم‌فرماست. گونه‌های متکامل‌تری وجود دارند که نمی‌توان گفت صرفاً حاصل تکامل تدریجی گونه قبلی هستند.

در این میان آنچه شاید بتواند تا حدودی ما را در فهم این مسأله یاری کند مفهومیست به نام تصادف یا جهش.

به عبارتی طرح هواپیما نسبت به طرح اتومبیل یک جهش بود و نه یک حرکت تدریجی. در طبیعت نیز به همین گونه‌است. در هر نسل جدید بعضی از خصوصیات به صورتی کاملاً تصادفی تغییر می‌یابند سپس بر اثر تکامل تدریجی که پیشتر توضیح دادیم در صورتی که این خصوصیت تصادفی شرایط طبیعت را ارضا کند حفظ می‌شود در غیر این‌صورت به شکل اتوماتیک از چرخه طبیعت حذف می‌گردد.

در واقع می‌توان تکامل طبیعی را به این‌صورت خلاصه کرد: جست‌وجوی کورکورانه (تصادف یا Blind Search) + بقای قوی‌تر.

حال ببینیم که رابطه تکامل طبیعی با روش‌های هوش مصنوعی چیست. هدف اصلی روش‌های هوشمندِ به کار گرفته شده در هوش مصنوعی، یافتن پاسخ بهینه مسائل مهندسی است. بعنوان مثال اینکه چگونه یک موتور را طراحی کنیم تا بهترین بازدهی را داشته باشد یا چگونه بازوهای یک ربات را متحرک کنیم تا کوتاه‌ترین مسیر را تا مقصد طی کند (دقت کنید که در صورت وجود مانع یافتن کوتاه‌ترین مسیر دیگر به سادگی کشیدن یک خط راست بین مبدأ و مقصد نیست) همگی مسائل بهینه‌سازی هستند.

روش‌های کلاسیک ریاضیات دارای دو اشکال اساسی هستند. اغلب این روش‌ها نقطه بهینه محلی (Local Optima) را بعنوان نقطه بهینه کلی در نظر می‌گیرند و نیز هر یک از این روش‌ها تنها برای مسأله خاصی کاربرد دارند. این دو نکته را با مثال‌های ساده‌ای روشن می‌کنیم.

بهینه محلی و بهینه کلی

به بالا توجه کنید. این منحنی دارای دو نقطه ماکزیمم می‌باشد. که یکی از آنها تنها ماکزیمم محلی است. حال اگر از روش‌های بهینه‌سازی ریاضی استفاده کنیم مجبوریم تا در یک بازه بسیار کوچک مقدار ماکزیمم تابع را بیابیم. مثلاً از نقطه 1 شروع کنیم و تابع را ماکزیمم کنیم. بدیهی است اگر از نقطه 1 شروع کنیم تنها به مقدار ماکزیمم محلی دست خواهیم یافت و الگوریتم ما پس از آن متوقف خواهد شد. اما در روش‌های هوشمند، به ویژه الگوریتم ژنتیک بدلیل خصلت تصادفی آنها حتی اگر هم از نقطه 1 شروع کنیم باز ممکن است در میان راه نقطه A به صورت تصادفی انتخاب شود که در این صورت ما شانس دست‌یابی به نقطه بهینه کلی (Global Optima) را خواهیم داشت.

در مورد نکته دوم باید بگوییم که روش‌های ریاضی بهینه‌سازی اغلب منجر به یک فرمول یا دستورالعمل خاص برای حل هر مسئله می‌شوند. در حالی که روش‌های هوشمند دستورالعمل‌هایی هستند که به صورت کلی می‌توانند در حل هر مسئله‌ای به کار گرفته شوند. این نکته را پس از آشنایی با خود الگوریتم بیشتر و بهتر خواهید دید.

الگوریتم ژنتیک چیست؟

الگوریتم‌های ژنتیک از اصول انتخاب طبیعی داروین برای یافتن فرمول بهینه جهت پیش‌بینی یا تطبیق الگو استفاده می‌کنند. الگوریتم‌های ژنتیک اغلب گزینه خوبی برای تکنیک‌های پیش‌بینی بر مبنای رگرسیون هستند.

برای مثال اگر بخواهیم نوسانات قیمت نفت را با استفاده از عوامل خارجی و ارزش رگرسیون خطی ساده مدل کنیم،این فرمول را تولید خواهیم کرد : قیمت نفت در زمان t = ضریب 1 نرخ بهره در زمان t + ضریب 2 نرخ بیکاری در زمان t + ثابت 1 . سپس از یک معیار برای پیدا کردن بهترین مجموعه ضرایب و ثابت‌ها جهت مدل کردن قیمت نفت استفاده خواهیم کرد. در این روش 2 نکته اساسی وجود دارد. اول این که روش خطی است و مسئله دوم این است که ما به جای اینکه در میان "فضای پارامترها" جستجو کنیم، پارامترهای مورد استفاده را مشخص کرده‌ایم.

با استفاده از الگوریتم‌های ژنتیک ما یک ابر فرمول یا طرح، تنظیم می‌کنیم که چیزی شبیه "قیمت نفت در زمان t تابعی از حداکثر 4 متغیر است" را بیان می‌کند. سپس داده‌هایی برای گروهی از متغیرهای مختلف، شاید در حدود 20 متغیر فراهم خواهیم کرد. سپس الگوریتم ژنتیک اجرا خواهد شد که بهترین تابع و متغیرها را مورد جستجو قرار می‌دهد. روش کار الگوریتم ژنتیک به طور فریبنده‌ای ساده، خیلی قابل درک و به طور قابل ملاحظه‌ای روشی است که ما معتقدیم حیوانات آنگونه تکامل یافته‌اند. هر فرمولی که از طرح داده شده بالا تبعیت کند فردی از جمعیت فرمول‌های ممکن تلقی می‌شود.

متغیرهایی که هر فرمول داده‌شده را مشخص می‌کنند به عنوان یکسری از اعداد نشان داده‌شده‌اند که معادل [دی ان ای|دی.ان.ای](DNA) آن فرد را تشکیل می‌دهند.

موتور الگوریتم ژنتیک یک جمعیت اولیه از فرمول ایجاد می‌کند. هر فرد در برابر مجموعه‌ای از داده‌های مورد آزمایش قرار می‌گیرند و مناسبترین آنها (شاید 10 درصد از مناسبترین‌ها) باقی می‌مانند؛ بقیه کنار گذاشته می‌شوند. مناسبترین افراد با هم جفتگیری (جابجایی عناصر دی ان ای) و تغییر (تغییر تصادفی عناصر دی ان ای) کرده‌اند. مشاهده می‌شود که با گذشت از میان تعداد زیادی از نسلها، الگوریتم ژنتیک به سمت ایجاد فرمول‌هایی که دقیقتر هستند، میل می‌کنند. در حالی که شبکه‌های عصبی هم غیرخطی و غیرپارامتریک هستند، جذابیت زیاد الگوریتم‌های ژنتیک این است نتایج نهایی قابل ملاحظه‌ترند. فرمول نهایی برای کاربر انسانی قابل مشاهده خواهد بود، و برای ارائه سطح اطمینان نتایج می‌توان تکنیک‌های آماری متعارف را بر روی این فرمول‌ها اعمال کرد. فناوری الگوریتم‌های ژنتیک همواره در حال بهبود است و برای مثال با مطرح کردن معادله ویروس‌ها که در کنار فرمول‌ها و برای نقض کردن فرمول‌های ضعیف تولید می‌شوند و در نتیجه جمعیت را کلاً قویتر می‌سازند.

مختصراً گفته می‌شود که الگوریتم ژنتیک (یا GA) یک تکنیک برنامه‌نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مسئله استفاده می‌کند. مسئله‌ای که باید حل شود ورودی است و راه حلها طبق یک الگو کدگذاری می‌شوند که تابع fitness نام دارد و هر راه حل کاندید را ارزیابی می‌کند که اکثر آنها به صورت تصادفی انتخاب می‌شوند.

الگوریتم ژنتیک (GA) یک تکنیک جستجو در علم رایانه برای یافتن راه حل بهینه و مسائل جستجو است. الگوریتم‌های ژنتیک یکی از انواع الگوریتم‌های تکاملی‌اند که از علم زیست‌شناسی مثل وراثت، جهش، [انتخاب ناگهانی(زیست‌شناسی)|انتخاب ناگهانی]، انتخاب طبیعی و ترکیب الهام گرفته شده.

عموماً راه‌حلها به صورت 2 تایی 0 و 1 نشان داده می‌شوند، ولی روشهای نمایش دیگری هم وجود دارد. تکامل از یک مجموعه کاملاً تصادفی از موجودیت‌ها شروع می‌شود و در نسلهای بعدی تکرار می‌شود. در هر نسل، مناسبترین‌ها انتخاب می‌شوند نه بهترین‌ها.

یک راه‌حل برای مسئله مورد نظر، با یک لیست از پارامترها نشان داده می‌شود که به آنها کروموزوم یا ژنوم می‌گویند. کروموزوم‌ها عموماً به صورت یک رشته ساده از داده‌ها نمایش داده می‌شوند، البته انواع ساختمان داده‌های دیگر هم می‌توانند مورد استفاده قرار گیرند. در ابتدا چندین مشخصه به صورت تصادفی برای ایجاد نسل اول تولید می‌شوند. در طول هر نسل، هر مشخصه ارزیابی می‌شود وارزش تناسب (fitness) توسط تابع تناسب اندازه‌گیری می‌شود.

گام بعدی ایجاد دومین نسل از جامعه است که بر پایه فرآیندهای انتخاب، تولید از روی مشخصه‌های انتخاب شده با عملگرهای ژنتیکی است: اتصال کروموزوم‌ها به سر یکدیگر و تغییر.

برای هر فرد، یک جفت والد انتخاب می‌شود. انتخاب‌ها به گونه‌ای‌اند که مناسبترین عناصر انتخاب شوند تا حتی ضعیفترین عناصر هم شانس انتخاب داشته باشند تا از نزدیک شدن به جواب محلی جلوگیری شود. چندین الگوی انتخاب وجود دارد: چرخ منگنه‌دار(رولت)، انتخاب مسابقه‌ای (Tournament) ،... .

معمولاً الگوریتم‌های ژنتیک یک عدد احتمال اتصال دارد که بین 0.6 و 1 است که احتمال به وجود آمدن فرزند را نشان می‌دهد. ارگانیسم‌ها با این احتمال دوباره با هم ترکیب می‌شوند. اتصال 2 کروموزوم فرزند ایجاد می‌کند، که به نسل بعدی اضافه می‌شوند. این کارها انجام می‌شوند تا این که کاندیدهای مناسبی برای جواب، در نسل بعدی پیدا شوند. مرحله بعدی تغییر دادن فرزندان جدید است. الگوریتم‌های ژنتیک یک احتمال تغییر کوچک و ثابت دارند که معمولاً درجه‌ای در حدود 0.01 یا کمتر دارد. بر اساس این احتمال، کروموزوم‌های فرزند به طور تصادفی تغییر می‌کنند یا جهش می‌یابند، مخصوصاً با جهش بیت‌ها در کروموزوم ساختمان داده‌مان.

این فرآیند باعث به وجود آمدن نسل جدیدی از کروموزوم‌هایی می‌شود، که با نسل قبلی متفاوت است. کل فرآیند برای نسل بعدی هم تکرار می‌شود، جفت‌ها برای ترکیب انتخاب می‌شوند، جمعیت نسل سوم به وجود می‌آیند و .... این فرآیند تکرار می‌شود تا این که به آخرین مرحله برسیم.

شرایط خاتمه الگوریتم‌های ژنتیک عبارتند از:

به تعداد ثابتی از نسل‌ها برسیم.

بودجه اختصاص داده‌شده تمام شود(زمان محاسبه/پول).

یک فرد(فرزند تولید شده) پیدا شود که مینیمم (کمترین) ملاک را برآورده کند.

بیشترین درجه برازش فرزندان حاصل شود یا دیگر نتایج بهتری حاصل نشود.

بازرسی دستی.

ترکیبهای بالا.

روش های نمایش

قبل از این که یک الگوریتم ژنتیک برای یک مسئله اجرا شود، یک روش برای کد کردن ژنوم‌ها به زبان کامپیوتر باید به کار رود. یکی از روش‌های معمول کد کردن به صورت رشته‌های باینری است: رشته‌های 0و1. یک راه حل مشابه دیگر کدکردن راه حل‌ها در آرایه‌ای از اعداد صحیح یا اعشاری است، که دوباره هر جایگاه یک جنبه از ویژگی‌ها را نشان می‌دهد. این راه حل در مقایسه با قبلی پیچیده‌تر و مشکل‌تر است. مثلاً این روش توسط استفان کرمر، برای حدس ساختار 3 بعدی یک پروتئین موجود در آمینو اسید‌ها استفاده شد. الگوریتم‌های ژنتیکی که برای آموزش شبکه‌های عصبی استفاده می‌شوند، از این روش بهره می‌گیرند.

سومین روش برای نمایش صفات در یک GA یک رشته از حروف است، که هر حرف دوباره نمایش دهنده یک خصوصیت از راه حل است.

خاصیت هر 3تای این روش‌ها این است که آنها تعریف سازنده‌ایی را که تغییرات تصادفی در آنها ایجاد می‌کنند را آسان می‌کنند: 0 را به 1 وبرعکس، اضافه یا کم کردن ارزش یک عدد یا تبدیل یک حرف به حرف دیگر.

توضیحات بالا در شکل قابل مشاهده است

یک روش دیگر که توسط John Koza توسعه یافت، برنامه‌نویسی ژنتیک (genetic programming)است. که برنامه‌ها را به عنوان شاخه‌های داده در ساختار درخت نشان می‌دهد. در این روش تغییرات تصادفی می‌توانند با عوض کردن عملگرها یا تغییر دادن ارزش یک گره داده شده در درخت، یا عوض کردن یک زیر درخت با دیگری به وجود آیند.

عملگرهای یک الگوریتم ژنتیک

در هر مسئله قبل از آنکه بتوان الگوریتم ژنتیک را برای یافتن یک پاسخ به کار برد به دو عنصر نیاز است:در ابتدا روشی برای ارائه یک جواب به شکلی که الگوریتم ژنتیک بتواند روی آن عمل کند لازم است. در روش سنتی یک جواب به صورت یک رشته از بیتها، اعداد یا نویسهها نمایش داده می‌شود.دومین جزء اساسی الگوریتم ژنتیک روشی است که بتواند کیفیت هر جواب پیشنهاد شده را با استفاده از توابع تناسب محاسبه نماید. مثلاً اگر مسئله هر مقدار وزن ممکن را برای یک کوله پشتی مناسب بداند بدون اینکه کوله پشتی پاره شود، (مسئله کوله پشتی را ببینید) یک روش برای ارائه پاسخ می‌تواند به شکل رشته ای از بیتهای ۰ و۱ در نظر گرفته شود, که ۱ یا ۰ بودن نشانه اضافه شدن یا نشدن وزن به کوله پشتی است.تناسب پاسخ، با تعیین وزن کل برای جواب پیشنهاد شده اندازه گیری می‌شود.

شبه کد

1 Genetic Algorithm
2 begin
3      Choose initial population
4      repeat
5          Evaluate the individual fit nesses of a certain proportion of the population
6          Select pairs of best-ranking individuals to reproduce
7          Apply crossover operator
8          Apply mutation operator
9      until terminating condition
10 end

شمای کلی شبه کد

ایده اصلی

در دهه هفتاد میلادی دانشمندی از دانشگاه میشیگان به نام جان هلند ایده استفاده از الگوریتم ژنتیک را در بهینه‌سازی‌های مهندسی مطرح کرد. ایده اساسی این الگوریتم انتقال خصوصیات موروثی توسط ژن‌هاست. فرض کنید مجموعه خصوصیات انسان توسط کروموزوم‌های او به نسل بعدی منتقل می‌شوند. هر ژن در این کروموزوم‌ها نماینده یک خصوصیت است. بعنوان مثال ژن 1 می‌تواند رنگ چشم باشد، ژن 2 طول قد، ژن 3 رنگ مو و الی آخر. حال اگر این کروموزوم به تمامی، به نسل بعد انتقال یابد، تمامی خصوصیات نسل بعدی شبیه به خصوصیات نسل قبل خواهد بود. بدیهیست که در عمل چنین اتفاقی رخ نمی‌دهد. در واقع بصورت همزمان دو اتفاق برای کروموزوم‌ها می‌افتد. اتفاق اول جهش (Mutation) است. "جهش" به این صورت است که بعضی ژن‌ها بصورت کاملاً تصادفی تغییر می‌کنند. البته تعداد این گونه ژن‌ها بسیار کم می‌باشد اما در هر حال این تغییر تصادفی همانگونه که پیشتر دیدیم بسیار مهم است. مثلاً ژن رنگ چشم می‌تواند بصورت تصادفی باعث شود تا در نسل بعدی یک نفر دارای چشمان سبز باشد. در حالی که تمامی نسل قبل دارای چشم قهوه‌ای بوده‌اند. علاوه بر "جهش" اتفاق دیگری که می‌افتد و البته این اتفاق به تعداد بسیار بیشتری نسبت به "جهش" رخ می‌دهد چسبیدن ابتدای یک کروموزوم به انتهای یک کروموزوم دیگر است. این مسأله با نام Crossover شناخته می‌شود. این همان چیزیست که مثلاً باعث می‌شود تا فرزند تعدادی از خصوصیات پدر و تعدادی از خصوصیات مادر را با هم به ارث ببرد و از شبیه شدن تام فرزند به تنها یکی از والدین جلوگیری می‌کند

روش های انتخاب

روش‌های مختلفی برای الگوریتم‌های ژنتیک وجود دارند که می‌توان برای انتخاب ژنوم‌ها از آن‌ها استفاده کرد. اما روش‌های لیست شده در پایین از معمول‌ترین روش‌ها هستند.

انتخاب Elitist

مناسب‌ترین عضو هر اجتماع انتخاب می‌شود.Elitist Selection

انتخاب Roulette

یک روش انتخاب است که در آن عنصری که عدد برازش (تناسب) بیشتری داشته باشد، انتخاب می‌شود.

Roulette Selection

انتخاب Scaling

به موازات افزایش متوسط عدد برازش جامعه، سنگینی انتخاب هم بیشتر می‌شود و جزئی‌تر. این روش وقتی کاربرد دارد که مجموعه دارای عناصری باشد که عدد برازش بزرگی دارند و فقط تفاوت‌های کوچکی آن‌ها را از هم تفکیک می‌کند.Scaling Selection

انتخاب Tournament

یک زیر مجموعه از صفات یک جامعه انتخاب می‌شوند و اعضای آن مجموعه با هم رقابت می‌کنند و سرانجام فقط یک صفت از هر زیرگروه برای تولید انتخاب می‌شوند.Tournament Selection

بعضی از روش‌های دیگر عبارتند از:Hierarchical Selection ,Steady-State Selection ,Rank Selection ,Tournament Selection

کروموزوم (الگوریتم ژنتیک)

در الگوریتم ژنتیک، یک کروموزوم (که گاهی genome نیز نامیده می‌شود) مجموعه‌ای از پارامترهاست به طوری که یک راه حل پیشنهادی را برای مساله‌ای که الگوریتم ژنتیک سعی در حل آن دارد، تعریف می‌نماید.

طراحی کروموزوم

طراحی یک کروموزوم و پارامترهای آن به نیازهای خاص مساله‌ای که باید حل شود بستگی دارد. به عنوان مثال فرض کنید مساله ما پیدا کردن عدد یک صحیح بین 0 تا 255 می‌باشد به طوری که مقدار تابع f(x) = x * x بیشینه (ماکزیمم) گردد. (معمولا این نوع مسایل توسط الگوریتم ژنتیک حل نشده و توسط روش‌های عددی حل می‌شوند. این تنها یک مثال ساده می‌باشد.) راه حل‌های ما اعدادی بین 0 تا 255 می‌باشند به طوری که هر یک از این راه حل‌ها را می‌توان با یک رشته 8 بیتی نمایش داد. بنابراین ما باید از یک رشته 8 بیتی به عنوان کروموزوم استفاده نماییم. حال اگر یک کروموزوم در جمعیت نمایش دهنده مقدار 155 باشد، آن کروموزوم باید به شکل 10011011 باشد. یک مساله واقعی در این مورد می‌تواند مساله فروشنده دوره گرد باشد. در این مساله به دنبال ترتیبی از سفر به شهرهای مختلف می‌گردیم به طوری که فروشنده کوتاه‌ترین مسیر را طی نماید. فرض کنید شش شهر A, B, C, D, E و F وجود دارند. یک روش مناسب برای طراحی کروموزوم مساله فوق ترتیبی است که شهرها ملاقات می‌شوند. به عنوان مثال ترتیبی که یک کروموزوم می‌تواند در این جمعیت داشته باشد می‌تواند شبیه DFABEC باشد.

در الگوریتم ژنتیک باید دو عملگر جهش و ادغام برای یک کروموزوم پیاده‌سازی گردند.

تعریف بهینه سازي و الگوریتم فرآیند بهینه سازي

2-1 بهینه سازي چیست ؟
هدف بهینه سازي ، مطمئن ساختن شبکه از عملکردش در کارائی بهینه در محدوده است اندارد کیفیت سرویسی (QOS) ازقبل تعریف شده، می باشد.
یک شبکه بهینه با اعمال رویه هایی جهت حل مشکلاتی که از طریق آنالیز پارامترهاي مونیتور شده توسط بخش مدیریت عملکرد (Performance Management)، مشخص شده، بدست می آید.
دلایل اصلی براي اینکه فرآیند بهینه سازي ،حتمأ باید در شبکه انجام شود عبارتست از:
• نگهداشتن کیفیت سرویس در وضعیت فعلی یا افزایش آن
• استفاد بهینه ازمنابع موجود درشبکه بجاي افزایش بیهوده منابعی که بدون کارکرد درست به شبکه جهت توسعه افزوده می شوند.
• حل مشکلات شبکه و پاسخ به شکایات مردمی
• جذب مشتري جدید با ارائه سرویس بهتر
2-2 اهداف بهینه سازي
هدف اصلی بهینه سازي یک شبکه، افزایش مجموع کیفیت شبکه در حال حاضر شبکه موبایل است . این افزایش کیفیت با استفاده ازآیتم هاي زیر بدست می آید.
• شناسایی مشکلات شبکه با استفاده از انالیز (Key Performance Indicator) KPIکه این مبحث در فصل پنجم بتفصیل آمده است.
• جدا سازي منابعی که داراي Performance پائین هستند.
• تصحیح مشکلات شناسایی شده با استفاده از روشها و الگوریتمهاي بهینه سازي که بطور خلاصه دربخشهاي بعدي گفته می شود.
• اطمینان از عملکرد شبکه که باید کیفیت سرویس (QOS) آن بالاتر از حد استاندارد از قبل تعریف شده باشد.
• ساختن شبکه اي با کارایی وکیفیت بالا که بتوان براحتی شبکه را با حداقل منابع وکیفیت بالا توسعه داد.
3-2 دلایل بهینه سازي
- تصحیح نقاط شناسایی شده در شبکه که داراي راندمان پائین و عدم کارایی لازم هستند .مانند نقاطی از شبکه که داراي Drop call یا Handover Fail یا Tch Congestion یا Congestion Sdcch بالایی هستند و با استفاده از الگوریتم بهینه سازي به حد قابل قبول واستاندارد GSM رساند.
- آماده سازي براي پیاده سازي و اجرا سرویس هاي جدید .
- افزایش راندمان شبکه براي دستیابی به نیازهاي تجاري و رقابتی .
- اعمال تغییرات سنجیده در پارامترهاي عملیاتی شبکه.
4-2 الگوریتم بهینه سازي
- اطلاعات ورودي از شبکه موبایل
• داشتن طرح سایت BTS(طرح فرکانس ، ارتفاع، زاویه ، نوع آنتن ، مکان سایت ، تیلت آنتن و...)
• تهیه KPI شبکه براي یک دوره حداقل 10 روزه و بررسی و آنالیز آن
• درایو تست در شبکه در دو مد Dedicated و Idle
Logfile هاي استخراج شده از عناصر شبکه (BSC,MSC,OMC)
- پردازش جهت بهینه سازي شبکه
• تهیه نرم افزاري جهت آنالیز ها Logfile هاي استخراج شده از عناصر شبکه که این Logfile ها شامل dump همسایگی ، توان خروجی TRXها ودر کل ،کلیه پارامترهاي شبکه
• ارئه راهکارهاي مناسب وعلمی بوسیله تنظیم پارامترهاي شبکه جهت حل مشکلاتی مانند Handover failure ، Congestion ، Drop call، Over shooting، Unbalance Traffic ، H.W problem
• اعمال فیچرهایی براي استفاده بهینه از Resource هاي شبکه و ایجاد شبکه اي با کیفیت بالا و ارائه سرویسهاي دیتا و بالانس ترافیکی
• لیست فیچرها :
(syntisizer Frequency Hopping , Cell load sharing , C2 parameter for micro site , sdcch Dynamic Allocation,…)
بکارگیري فیچر Half rate براي افزایش کانال ترافیکی با همان منابع موجود.
Tools هایی که براي طراحی و بهینه سازي مورد استفاده قرار می گیرد عبارتند از:
• TEMS Investigation براي Drive Test و مونیتور کردن وضعیت شبکه از نظر کیفیت و لول سیگنال و C/I و تداخل
• Optima براي تهیه KPI(key Performance Indicator)
• Asset براي طرح فرکانسی و پوشش اولیه
• Site master براي اندازه گیري میزان برگشتی موج در آنتن براي باند GSM
شاخص ها عبارتند از:
- کیفیت سرویس QOS
- نسبت موج کاریر اصلی به تداخل C/I
- SQI (sample Quality Indicator)
- Call Setup Success Rate
- Drop Call_Rate
- HO_ Failure
- Ho_success
- SDCCH_Congestion
- TCH_Congestion
- Sdcch Access Rate
- TCH_Assign_Failure
- TCH_RF_Loss
- TCH Traffic
- ......
همه شاخصهاي فوق با استفاده از فرمول هایی که در فصل پنجم آمده است محاسبه میشوند و وضعیت راندمان شبکه را از نظر ترافیکی وکیفیت مشخص میکنند .
کیفیت سرویس دهی مطلوب بر اساس معیارهاي تعیین شده :

کد PHP:
Call Setup Successful Rate (CSSR) > 90%
Drop Call Rate (DCR) < 3 %
HandOver Successful Rate (HSR) > 90%
TCH Congestion < 5%
SDCCH Congestion < 0.5%

2-5 : مدیریت عملکرد وبهینه سازي
هدف از بهینه سازي شبکه رادیویی ، اپتیمم نمودن اکارایی شبکه سلولار می باشد .

شكل (1-2) : فلوچارت رویه مدیریت عملکرد و بهینه سازي

شكل (2-2) : فرایند و خط مشی بهینه سازي

شكل (3-2) : فاز بررسی شبکه براي فرایند بهینه سازي

الگوريتم ژنتيك و فرايند بهينه سازي ...

انتخاب Elitist

انتخاب Roulette

انتخاب Scaling

انتخاب Tournament

مطالب مشابه :

الگوریتم ژنتیک چیست ؟

الگوریتم ژنتیک چیست؟

الگوریتم ژنتیک

مسئله کوله پشتی چیست؟

الگوریتم ژنتیک چیست؟

الگوريتم مورچگان چیست؟ توضیح با یک مثال ساده

ژنتیک و اصلاح نباتات

الگوریتم ژنتیک

الگوريتم ژنتيك و فرايند بهينه سازي ...