بخشی از مقاله
چکیده
الگوریتم تکاملی متعددی برای حل مسائل پیچیده با الهام گرفتن از طبیعت گسترش یافتهاند. SGA-NGA1 از نوع مهاجر در چند جمعیت با زمینه GA2 میباشد، که پارامترهای فردی نامناسب و انتخاب پارامترهای تطبیقی مهاجر آن، از اهمیت یکسانی برخوردار است. مسئله مهم در این روش، که در بسیاری از کاربردهای زندگی واقعی اعمال شدهاند. و NGA نسبت به SGA قابلیت اعتماد نتایج، از لحاظ همگرایی کارآمدتر هستند. NGA یکی از انواع GA چند جمعیتی است که در آن اشخاص بر مبنای سازگاریشان مهاجرت به گروه دیگر میکنند.
ثابت شده است که این امر با حفظ تنوع جمعیتی، که به اشخاصی که دارای سازگاری کمی هستند نیز اهمیت میدهد، که در بهبود عملکرد جمعیت واحد GA بسیار موثر است. در این تحقیق به منظور دستیابی به رفتار NGA را با آزمایش توابع ریاضی به طور برجسته نشان میدهد و برای مقایسه عملکردش با SGA، توابع مهم مورد استفاده در بهینهسازی استفاده شدهاند و نتایج عملکرد خوب NGA را نسبت به SGA در مورد سرعت همگرایی و بهترین مقادیر بهینه شده بهتر اثبات میکند، که با شبیهسازی نرمافزار به اثبات رسیده است.
-1 مقدمه
-1-1 بیان مسأله
امروزه با پیشرفت سریع دانش، بهینه سازی از اهمیت بالایی در علوم مهندسی برخودار است و کاربرد گستردهای در بخشهای مختلف پیدا کرده است. یکی از ابزارهای مناسب برای بهینه سازی، الگوریتم ژنتیک است که شاخهای از محاسبات تکاملی محسوب میشود که در هوش مصنوعی به سرعت در حال رشد و پیشرفت هستند. در الگوریتم ژنتیکی استاندارد - - SGA انواع مدلها و مکانیزمهای انتخابی مانند، گزینش چرخ رولت، گزینش بر اساس رتبه، گزینش تورنومنت و غیره وجود دارد، که بر اساس نوع کاربرد اعمال میشوند. هدف این مکانیزمهای گزینش، انتخاب منحصر به فرد و بسیار مناسب در تناسبهای متفاوت برای هدف جفت کردن است.
انتخابهای نامناسب شانس بسیار کمی برای جفت شدن دارند و تنوع را در جمعیت کاهش میدهند. افراد جمعیت بر اساس مقدار سازگاریشان به گروههایی متفاوت، گروهبندی میشوند. افراد، در یک گروه با یکدیگر جفت میشوند. اینجا دوباره، انواع مختلف مکانیزمهای گزینش، در هر گروه قابل استفاده است. اگر فرزندی با سازگاری بهتری بوجود آید، گروه خود را ترک کرده و به گروه دیگر میپیوند. در این الگوریتم، اکثر اصول الگوریتم ژنتیکی استاندارد اجرا میشود به جز اینکه، افراد میتوانند بین گروههای مختلف در جمعیتی که در آن گروهبندی شدهاند مهاجرت کنند. روش گزینش اجرا شده در الگوریتم ژنتیکی مهاجر - - NGA، اصرار به جفت کردن درون همان گروه دارد بدین معنی که شانسهای یکسان برای جفت شدن حتی با ضعیف ترین بخش جمعیت فراهم است.
این به الگوریتم ژنتیکی مهاجر امکان نگه داشتن افراد متنوع در یک جمعیت را میدهد، همچنین همگرایی سریعتری را تضمین میکند. NGA یکی از انواع GA چند جمعیتی بوده است که در آن اشخاص بر مبنای سازگاریشان مهاجرت از یک گروه به دیگر ادامه میدهند. ثابت شده است که این امر با حفظ تنوع جمعیتی، که به اشخاصی که دارای سازگاری کمی هستند نیز اهمیتی یکسان میدهد، در بهبود عملکرد جمعیت واحد GA بسیار موثر است.
الگوریتمهای ژنتیکی چند جمعیتی - - MGA در همگرایی سریعتر بهتراند، زیرا هر جمعیت زیرمجموعه به طور مستقل از دیگری نمو میکنند - . - Munetomo et al, 1993, Kojima et al, 2008 عملکرد MGA به شدت تحت تأثیر انتخاب صحیح پارامترهاست، مانند توپولوژی اتصال، روش مهاجرت، نرخ مهاجرت، و مقدار جمعیتها . - Cantu-Paz 1999, Lin et al, 2004 - تعداد نسلها را جهت پیدا کردن راه حلهای بهینه یا نزدیک به بهینه کوتاهتر میکنند. همچنین بسیار مقاوم در برابر همگرایی زودرس است. تعدادی از الگوریتمهای ژنتیکی چند جمعیتی در تحقیقات معرفی شدهاند که برخی از آنها در این تحقیق ارائه شدهاند.
-2-1 پیشینه تحقیق
همگرایی الگوریتم ژنتیک مهاجر در محک توابع ریاضی از نوع مهاجرت در چند جمعیت با زمینه الگوریتم ژنتیکی معرفی شد - . - Sathya and Radhika, 2013 و در مهاجرت پس از هر نسل اتفاق میافتد و یک کپی از بهترین افراد در هرجمعیت زیر به همه همسایهها ارسال میشود . - Leuze et al, 1987 - گروسو - Grosso, 1 1985 - از 5 جمعیت زیر استفاده کرد و افراد را با نرخ مهاجرت ثابت تغییر داد و اثبات کرد که مهاجرت به شدت بر عملکرد GA مؤثر است. یک GA چند جمعیتی مبتنی بر استراتژی مهاجرت بی نظم - Chen et al, 2004 - مهاجرت آسنکرون از افراد را در طول تکامل موازی اعمال میکند و امنیت آن را در مقابل همگرایی زودرس اثبات میکند. تعدادی مکانیزم نیز برای جلوگیری از جفت شدن افراد قبلاً ارائه شد .
- Gorges-Schleuter, 1992 - به طور کلی از جفت شدن افراد مشابه جلوگیری شده است با این تصور که والدین مشابه فرزندانی مشابه تولید میکنند، که از ایجاد تنوع در جمعیت جلوگیری میکند. بوکر 2 - Booker, 1982 - و گلدبرگ - Goldberg and Deb, 3 1991 - روشهای مختلفی را بررسی کردهاند که در آنها یک برچسب زوج شدن به هر فرد اضافه میشود. برچسب میبایست قبل از اینکه اجازه عبور داده شود تطبیق داده شود. محدودیت زوج شدن دیگری توسط اسپیرس 4 - Spears, 1994 - معرفی شد که یک توپولوژی حلقه تک بعدی اضافه میکند و زوج شدن با همسایهها را با برچسبهای مشابه محدود میکند.
برای نگهداشتن تنوع افراد در یک جمعیت، از مهاجرت نیز قبلا استفاده شده است . - Rebaudengo and Reorda 1993, Power et al, 2005 - اما با الگوریتمهای ژنتیکی موازی مانند مثالی در ژنیتور 52 نوشته وایتلی6 - Whitley and Kauth, 1988 - که افراد از یک پروسه به دیگری مهاجرت میکنند. بر طبق تنس - Tanese, 7 1987, Tanese, 1989 - در الگوریتمهای ژنتیکی برای ایجاد تنوع جمعیت بیشتر ترکیب مهاجرت گزارش شده است.
اگرچه انواع زیادی از الگوریتمهای ژنتیکی چند جمعیتی وجود دارد، اما هنوز مسئله گزینش بایاس موجود در الگوریتمهای ژنتیکی حل نشده است. انواع مختلف مکانیزمهای گزینشی و اپراتورهای ژنتیکی برای هدایت روش تطبیقی تصادفی الگوریتم ژنتیکی جهت بررسی همه راههای ممکن استفاده شدهاند. مکانیزم گزینشی ساده الگوریتم ژنتیکی راه حل هایی با سازگاری بیشتر را تکرار میکند و راه حل هایی با سازگاری کمتر که منجر به همگرایی جمعیت میشود را دور میاندازد. برای مثال، بریندال - Brindle, 1981 - 8 عملکرد نامرغوب از گزینش چرخ رولت9 را توسط توابع تست متعددی اثبات کرده است. همچنین، بیکر - Baker, 1987 - 10 روشهای گزینش مناسب سازگاری مختلف را آنالیز کرده است.
