جایابی خازن در شبکه با الگوریتم ژنتیک
الگوریتم ژنتیک یک روش آمـاری بـرای بهینـه سـازی و جسـتجو اسـت ویژگیهـای خاص این الگوریتم باعث می شود که نتـوانیم آن را جسـتجوگر تصـادفی سـاده قلمداد کنیم . در واقع ایده اولیه این روش از نظریه تکامل داروین الهام گرفتـه شده است و کاربرد آن بر اساس ژنتیک طبیعی استوار مـی باشـد . اصـول اولیـه الگوریتم ژنتیک توسط J.Holland وهمکارانش در دانشـگاه میشـیگان در سـال 1962 ارائه شد .
آنـان در تحقیقـات خـود بـه فراینـد سـازگاری در سیسـتم هـای طبیعی توجه نمودند و بـرای مدلسـازی آن در سیسـتم هـای مصـنوعی کـه بایـد دارای توانایی های اصلی سیستم های طبیعی باشند تـلاش نمـوده انـد . نتیجـه این تلاشها, پیدایش الگوریتم ژنتیک بود.
خاصیت الگـوریتم ژنتیـک
خاصیت هم الگـوریتم ژنتیـک , مقـاوم بـودن آن اسـت , بـه طوریکـه در آن ,یـک تعادل انعطاف پذیری بـین کـارایی و خصوصـیات لازم , بـرای بقـادر محـیط هـا و شـرایط گونـاگون وجـود دارد بـه طـور کلـی هـر چـه سیسـتم مصـنوعی از نظـر مقاومت در درجه بالاتری باشد, هزینـه طراحـی مجـدد آن کـاهش یافتـه و حتـی حذف می گردد. در واقع چنانچه میزان سـازگاری سیسـتمی افـزایش یابـد , قـادر خواهد بود که با قدرت بیشتر و به نحو مطلوب تری به کار بپردازد .
در سیستم های بیولوژیک میزان انعطاف پذیری , مقاومت وکارایی به شکل شگفت انگیزی , زیاد است . سازگاری , بقـا , خـود ترمیمـی , هـدایت و تولیـد مثـل از ویژگیهـای خاص سیستم های طبیعی و بیولوژیک هستند که مهندسان درصد هستند تا در سیستم های مصنوعی از آنهاتقلید کنند. اما بطور کلی جایی که کار کرد مقـاوم مورد نیاز باشد, طبیعت بهتر عمل خواهد کرد
مفاهیم اولیه در الگوریتم ژنتیک
الف: کد کردن
الگوریتم ژنتیک به جای اینکه بر روی پارامترها یا متغیرهـای مسـاله کـار نـد , بـا شکل کد شده آنها به طور مناسب , سرو کار دارد. متداولترین روش کد گذاری , استفاده از اعداد باینری است .در این روش , پارامترها به دنباله هـای مناسـب از اعدا 0و1 جایگزین می شوند.
از روشهای دیگر کـد گـذاری در الگـوریتم ژنتیـک , می توان روش Grey , کد گذاری در پایه هـای غیـر از 2 و کدگـذاری بـر اسـاس مرتبه 1 را نام برد . تعداد بیتهایی که برای کدگذاری متغیرهـا اسـتفاده مـی شـود , بسـته بـه دقـت مورد نظر برای جوابها , محدوده تغییرات پارامترها و رابطه بین متغیرهابستگی دارند . در سالهای اخیر, روشهای کد گذاری باینری عموماً منسوخ شده و متداول اینست که همان متغیرهای مساله را مستقیماً در الگوریتم وارد کنند
ب: کروموزم
رشته یا دنباله ای از بیت ه ( ا به شکل کد شده ) که یک جواب ممکن ( مناسـب یا نامناسب) از مساله مورد نظر می باشد , را کروموزم مـی گوینـد . در حقیقـت بیتهای یک کروموزم , نقش ژن ها در طبیعت را بازی میکنند هر بیـت , متغیـری گسسته است که از یک مجموعه Qعضوری انتخاب می شود چنانچه از کد گذاری باینری استفاده شود, هر بیت یکی از دو مقدار 1و0 را می پذیرد و بنـابراین 2= Qمی باشد
ج جمعیت
مجموعه ای از کروموزومها را جمعیت گویند. یکی از ویژگیهای الگـوریتم ژنتیـک اینست که به جای تمرکز بر روی یک نقطه از فضای جستجو یا یک کروموزم, بـر روی جمعیتی از کروموزومها کار می کند بدین ترتیـب در هـر مرحلـه , الگـوریتم دارای جمعیتی از کروموزومها که خواص مورد نظر را بهتر از جمعیت مرحله قبل دارامی باشد .
د مقدار برازندگی
مناسب بودن یـا نبـودن جـواب , بـا معیـاری کـه از تـابع هـدف بدسـت مـی آیـد , سنجیده می شود . هر چقدر یک جواب مناسب تر باشد , مقدار برازندگی بزرگتـر دارد . بـرای آنکـه شـانس بقـای چنـین جـوابی بیشـتر باشـد , احتمـال بقـای آن , متناسب با مقدار برازندگی آن در نظر گرفته می شود .
بنابراین کروموزومی کـه برازنده تر است با احتمال بیشتری در تولیـد فرزنـدان شـرکت مـی کنـد ودنبالـه های بیشتری از آن به وجود می آید . به عنوان مثال چنانچه هدف پیشینه کـردن یک تابع باشد , مقدار برازندگی , یک تابع صعودی از تابع هـدف در نظـر گرفتـه می شود و اگر هدف یافتن مقدار کمینه یا تابع باشد, عدد برازندگی , یـک تـابع نزولی از آن قرار داده می شود.
عملگرد جایابی
این عملگر بر روی یک جفت از کروموزومها عمل می کنـد و میتوانـد بـه صـورت تک نقطه ای , چند نقطه ای و یکنواخت باشد. عملگر جابجایی تک نقطه ای , دو کرومـوزوم را بـه طـور تصـادفی از یـک نقطـه شکسـته و بخشـهای شکسـته دو کروموزوم را جابجا می کند و بدین ترتیب دو کروموزم جدید بدسـت مـی آیـد . به کروموزومهای اولیه , کروموزومهای « والد» و به کروموزومهای حاصل شـده از عمل جابجایی , کروموزومهای « فرزند» گویند
عملگر جهش
این عملگر روی هر یک از کروموزوم های حاصل از عمـل جابجـایی عمـل میکنـد . بدین ترتیب که به ازای هـ ر بیـت از کرومـوزوم , یـک عـدد تصـافدی تولیـد مـی گردد. اگر مقدار این عدد تصـادفی از مقـدار Pm ( احتمـال انجـام عمـل جهـش ) کمتر باشد , در آن بیت عمل جهش انجام می شودودر غیـر ایـن صـورت , در آن بیت عمل جهش انجام نمی گیرند. عمل جهش در هـر بیـت بـا تولیـد تصـادفی عدد 0و1 جایگزینی آن به جای بیت مورد جهش انجام می گیرد
به این ترتیب دیده می شود که این الگـوریتم فرضـیه تکامـل تـدریجی را بـرای بهبود بخشیدن یک سری از نقاط فضای جستجو به سمت یک نقطه بهینه بکـار می گیرد به این ترتیب کـه بهتـرین عناصـر جمعیـت از لحـاظ برازنـدگی (یعنـی عناصـری کـه بهتـرین نتیجـه را دارنـد ) را انتخـاب مـی کنـد و عملیـات ترکیـب , اخـتلاط و جهـش را روی آنهـا انجـام دهـد تـا یـک مجموعـه دیگـر بـا برازنـدگی بهترتولید کند . بکارگیری الگوریتم ژنتیـک بسـیار سـاده اسـت و ایـن قابلیـت را دارد که نقطه بهینه مطلق را بیابد .
مراحل اجرای الگوریتم ژنتیک بصورت زیر است :
1-ابتدا تعداد مناسبی از زوج کروموزومها بر اساس میـزان برازنـدگی آنهـا انتخاب می شوندتا در مراحل بعدی مورد استفاده قـرار گیرنـد . کروموزومهـایی که دارای عدد برازندگی بالایی هستند ممکن است چندین بـار در مراحـل تولیـد انتخاب شوند
2- عملگر جابجایی با احتمال PC بر روی کروموزوم های والدین عمـل کـرده و با ترکیب آنها کروموزومهای جدیدی را تولید می کند . Pm بر روی کروموزوم های حاصل از عمل جابجایی
3- عمل جهش با احتمال انجام شده و بـا تغییـر مقـادیر کروموزومهـا , راهـی بـرای ورود اطلاعـات جدیـد فراهم می کند .
4- بـه منظـور ارزیـابی فرزنـدان , مقـدار برازنـدگی کرومـوزوم هـای جدیـد محاسبه می گردد. معیار برازندگی معمولا تابع هدف می باشد
5- جمعیت جدید برای ورود به مرحله بعد الگوریتم انتخاب می گـردد . ایـن عمل با مقایسه مقدار برازندگی کروموزومها انجام می شود .
6- در این مرحله همه افراد جمعیت جدید , مورد ارزیـابی قـرار مـی گیـرد و چنانچه شرایط خاتمه الگوریتم فراهم شده باشد الگوریتم پایان می پذیرد و در غیراینصورت جمعیت به عنوان جمعیت اولیه برای مرحله بعد مورد استفاده قـرار می گیرد.
