AIcode مرجع تخصصی هوش مصنوعی

<aicode>

 

 

 

 

 

در بسیاری از مسائل مهندسی و علوم معمولا با تابع هدفی روبرو هستیم که می‌خواهیم آن را بهینه نماییم. مسائل مهندسی با روش‌های متفاوتی مورد تحلیل قرار می‌گیرند. روش‌های تحلیلی، روش مضارب لاگرانژ (Langrange Multipliers Method) و حساب تغییرات (Calculus Of Variation) و شیوه‌های عددی (Numerical Methods) مانند روش‌های مبتنی بر گرادیان (Gradient Based Methods) و روش‌های تاع جریمه‌ای (Penalty Function) را شامل می‌شوند. در حالت کلی مسائل مهندسی را می‌توان در چارچوب مسائل برنامه ریزی ریاضی به روش‌های مبتنی بر گرادیان و روش‌های جستجوی مستقیم تقسیم نمود، که در روش اول مشتقات تابع هدف و قیدها به همراه مقادیر ان تابع برای یافتن طرح بهینه به کار گرفته می‌شود. در برخی از مسائل مهندسی استفاده از روش‌های مبتنی بر گرادیان تابع هدف امکان پذیر است ولی در تعدادی از مسائل یا نمیتوان از این روش استفاده کرد و یا به کارگیری آن‌ها به سادگی امکان پذیر نخواهد بود. از دیدگاه دیگر می‌توان این روش‌ها را در گروه روش‌های قطعی (Deterministic) و یا غیر تصادفی، و روش‌های تصادفی (Stochastic) جای داد. منظور از روش‌های تصادفی روش‌هایی است که از نمونه برداری تصادفی در فضای جستجو یا مدل‌های تصادفی تابع هدف استفاده می‌کنند. که در سال‌های اخیر توجه زیادی را به خود جلب کرده اند و این به دلیل ارائه روش‌های موثری در حل مسائل بهینه سازی مشکل و امکان دستیابی به نقاط بهینه کلی می‌باشد. از طرف دیگر بیشتر روش‌های غیر تصادفی دارای این اشکال هستند که به محض رسیدن به اولین نقطه بهینه محلی متوقف شده و توانایی خروج از این نقطه و حرکت به سوی نقاط دیگر و در نهایت نقطه بهینه مطلق را ندارند.


الگوریتم ژنتیک یک روش بهینه سازی الهام گرفته از طبیعت است که می‌توان در طبقه بندی‌ها، آن را به عنوان یک روش عددی، جستجوی مستقیم و تصادفی معرفی کرد. این الگوریتم، الگوریتمی مبتنی بر تکرار است و اصول اولیه آن از علم ژنتیک اقتباس گردیده است و با تقلید از تعدادی از فرایندهای مشاهده شده در تکامل طبیعی اختراع شده است و به طور موثری از معرفت قدیمی موجود در یک جمعیت استفاده می‌کند، تا حل‌های جدید و بهبود یافته را ایجاد کند. این الگوریتم در مسائل متنوعی نظیر بهینه سازی، شناسایی و کنترل سیستم، پردازش تصویر و مسائل ترکیبی، به کار می‌رود.
چنانکه می‌دانیم علم ژنتیک، علمی است که درباره ی چگونگی وراثت و انتقال صفحات بیولوژیکی از نسلی به نسل بعد صحبت می‌کند. عامل اصلی انتقال صفحات بیولوژیکی در موجودات زنده کروموزوم (Chromosome) و ژن‌ها (Gene) می‌باشند و نحوه عملکرد آن‌ها به گونه ای است که در نهایت ژن‌ها و کروموزوم‌ها باقی مانده موجودات اصلح و برتر می‌باشد. این الگوریتم برای بهینه سازی، جستجو و یادگیری ماشین مورد استفاده قرار می‌گیرد. اساس این الگوریتم قانون تکامل داروین «بقا بهترین» است که می‌گوید موجودات ضعیف تر از بین می‌روند و موجودات قوی تر باقی می‌مانند. در واقع تکامل، فرایندی است که روی رشته‌ها صورت می‌گیرد، نه روی موجودات زنده‌ای که معرف موجودات رشته است. در واقع قانون انتخاب طبیعی (Natural Selection) برای بقا می‌گوید که هرچه امکان تطبیق موجود بیشتر باشد بقای موجود امکان پذیر تر است و احتمال تولید مثل بیشتری، برایش وجود دارد. این قانون براساس پیوند بین رشته‌ها و عملکرد ساختمان‌های رمز گشایی شده آن‌ها می‌باشد.
الگوریتم ژنتیک به دلیل تقلید نمودن از طبیعت دارای چند اختلاف اساسی با روش‌های جستجوی مرسوم می‌باشد که در زیر به تعدادی از آن‌ها اشاره می‌کنیم.
الگوریتم ژنتیک با رشته‌های بیتی کار می‌کند که هر کدام از این رشته‌ها کل مجموعه متغیرها را نشان می‌دهد، حال آن که بیشتر روش‌ها به طور مستقل با متغیرهای ویژه برخورد می‌کنند.
الگوریتم‌های ژنتیک برای راهنمایی جهت جستجو براساس مکانیزم و ژنتیک طبیعی ذکر شده در بالا، عمل می‌نمایند. این الگوریتم‌ها مناسب ترین رشته‌ها را از میان اطلاعات تصادفی سازمان دهی شده انتخاب می‌کنند. در هر نسل، یک گروه جدید رشته‌ها با استفاده از بهترین قسمت‌های دنباله‌های قبلی و بخش جدید اتفاقی برای رسیدن به یک جواب مناسب به وجود می‌آیند. با وجود این که الگوریتم‌ها تصادفی هستند، ولی در زمره الگوریتم‌های تصادفی ساده نیستند. آن‌ها به طور کارامدی به اکتشاف اطلاعات گذشته در فضای جستجو می‌پردازد تا در یک نقطه جستجوی جدیدی با پاسخ‌های بهتر، به سمت بهترین جواب پیش می‌روند. هنگام پیشامد سازی (Randomization) الگوریتم‌های ژنتیک عمل پیشامد سازی ساده را نمیپیمایند بلکه آن‌ها داده‌های پیشین را با تفکر جستجوی جدید برای رسیدن پیشرفت مورد نظر، توام می‌کنند.
الگوریتم ژنتیک در هر تکرار چند نقطه از فضای جستجو را در نظر می‌گیرد، بنابرین شانس اینکه به یک ماکزیمم محلی همگرا شود کاهش می‌یابد. در بیشتر روش‌های جستجو مرسوم (روش گرادیان)، قاعده حاکم تصمیم به این صورت عمل می‌کند که از یک نقطه به نقطه ی دیگر حرکت می‌کند. این روش‌ها می‌توانند در فضاهای جستجو دارای چند بیشنه ی خطرناک باشند. زیرا ممکن است آن‌ها به یک ماکزیمم محلی همگرا شوند. لیکن الگوریتم ژنتیک جمعیت‌های کاملی از رشته‌ها (نقاط) را تولید می‌کند سپس هر نقطه را به صورت انفرادی امتحان می‌کند و با ترکیب محتویات آن‌ها، یک جمعیت جدید را که شامل نقط بهبود یافته است، تشکیل می‌دهد. صرف نظر از انجام یک جستجو، ملاحظه همزمان تعدادی نقطه در الگوریتم ژنتیک، آن‌ها را با ماشین‌های موازی قابل تطبیق می‌سازد، زیرا در اینجا تکامل هر نقطه یک فرایند مستقل است. لذا الگوریتم ژنتیک فقط نیاز به اطلاعاتی در مورد کیفیت حل‌های ایجاد شده به وسیله ی هر مجموعه از متغیرها دارد. در صورتی که بعضی از روش‌های بهینه سازی نیاز به اطلاعات یا حتی نیاز به شناخت کامل از ساختمان مسئله و متغیرها دارند.
چون الگوریتم ژنتیک نیاز به چنین اطلاعات مشخصی از مسئله ندارد بنابرین قابل انعطاف تر از بیشتر روش‌های جستجو است. همچنین الگوریتم ژنتیک از روش‌های جستجوی نوعی، که برای راهنمایی جهت روش‌های جستجویشان از انتخاب تصادفی استفاده می‌کنند، متفاوت است، زیرا اگرچه برای تعریف روش‌های تصمیم گیری از تصادف و شانس استفاده می‌کند، ولی در فضای جستجو به صورت تصادفی قدم نمیزند.
فرض کنید یک مجموعه مرجع U و زیر مجموعه‌های S1، S2، . . . ، Sn از این مجموعه مرجع مفروض است. هدف پیدا کردن حداقل تعداد از این زیرمجموعه‌هاست که اجتماع آنها برابر مجموعه U می‌باشد. این مساله یک مساله NP می‌باشد و بنابراین راه حل پند جمله ای برای آن وجود ندارد. در این نوشتار هدف به کارگیری الگوریتم ژنتیک برای حل این مساله است.

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

الگوریتم ژنتیک، به عنوان ی الگوریتم محاسباتی بهینه سازی، با در نظر گرفتن مجموعه ای از نقاط فضای جواب در هر تکرار محاسباتی، به نحو مؤثری نواحی مختلف فضای جواب را جستجو می‌کند. در مکانیرم جستجو اگرچه مقدار تابع هدف تمام فضای جواب محاسبه نمیشود، ولی مقدار محاسبه شده تابع هدف برای هر نقطه، در متوسط گیری آماری تابع هدف برای هر نقطه، در متوسط گیری آماری تابع هدف در کلیه زیر فضاهایی که آن نقطه بدان‌ها وابسطه بوده، دخالت داده می‌شود و این زیر فضاها به طور موازی از نظر تابع هدف متوسط گیری آماری می‌شوند. این مکانیزم را توازی ضمنی (Implicit Parallelism) می‌گویند. این روند باعث می‌شود که جستجوی فضا به نواحی که متوسط آماری تابع هدف در آن‌ها زیاد بوده و امکان وجود نقطه بهینه در آن‌ها بیشتر است، سوق پیدا کند. چون در این روش بر خلاف روش‌های تک مسیری، فضای جواب به طور همه جانبه جستجو می‌شود، امکان کمتری برای همگرایی به یک نقطه بهینه محلی وجود خواهد داشت. امتیاز دیگر این الگوریتم آن است که هیچ محدودیتی برای تابع بهینه شونده، مثل مشتق پذیری یا پیوستگی لازم ندارد و در روند جستجو خود تنها به تعیین مقدار تابع هدف در نقاط مختلف نیاز دارد و هیچ اطلاعات کمکی دیگری، مثل مشتق تابع را استفاده نمیکند. لذا می‌توان در مسائل مختلف اعم از خطی، پیوسته یا گسسته استفاده می‌شود و به سهولت با مسائل مختلف قابل تطبیق است.
در هر تکرار هر یک از رشته‌های موجود در جمعیت رشته‌ها، رمزگشایی شده و مقدار تابع هدف برای آن بدست می‌آید. براساس مقادیر بدست آمده تابع هدف در جمعیت رشته‌ها، به هر رشته یک عدد برازندگی نسبت داده می‌شود. این عدد برازندگی احتمال انتخاب را برای هر رشته تعیین خواهد کرد. براساس این احتمال انتخاب، مجموعه ای از رشته‌ها انتخاب شده و با اعمال عملکردهای ژنتیکی روی آن‌ها رشته‌های جدیدی جایگزین رشته‌هایی از جمعیت می‌شوند تا تعداد جمعیت رشته‌ها در تکرار محاسباتی مختلف ثابت باشد.
مکانیزم‌های تصادفی که روی انتخاب و حذف رشته‌ها عمل می‌کنند به گونه ای هستند که رشته‌هایی که عدد برازندگی بیشتری دارند، احتمال بیشتری برای ترکیب و تولید رشته‌های جدید داشته و در مرحله جایگزینی نسبت به دیگر رشته‌ها مقاوم تر هستند. بدین لحاظ جمعیت دنباله‌ها در یک رقابت براساس تابع هدف در طی نسل‌های مختلف، کامل شده و متوسط مقدار تابع در جمعیت رشته‌ها افزایش می‌یابد.
به طور کلی در این الگوریتم ضمن آنکه در هر تکرار محاسباتی، توسط عملکردهای ژنتیکی، نقاطی جدید از فضای جواب مورد جستجو قرار می‌گیرند؛ توسط مکانیز انتخاب، روند جستجو نواحی از فضا را که متوسط آماری تابع هدف در آن‌ها بیشتر است، کنکاش می‌کند. براساس سیکل اجرایی فوق، در هر تکرار محاسباتی، سه عملگر اصلی روی رشته‌ها عمل می‌کند. این سه عملگر عبارت اند از دو عملگر ژنتیکی و عملگر انتخاب تصادفی.
گلد برگ (Goldberg) الگوریتم ژنتیکی‌هالند را با عنوان الگوریتم ژنتیک ساده (SGA) معرفی می‌کند. الگوریتم ژنتیک را از الگوریتم ژنتیک طبیعی اقتباس کردند :
بدن همه موجودات زنده از سلول‌ها تشکیل شده است. و در هر سلولی دسته کروموزوم‌های یکسانی وجود دارد. کروموزوم‌ها رشته ای از DNA هستند که در واقع الگویی برای تمام بدن هستند. هر کروموزمی‌ محتوی دسته‌هایی از DNA است که ژن نامیده می‌شود. و هر ژنی پروتئین خاصی را رمز گذاری می‌کند. اساساً می‌توان گفت که هر ژن، ویژگی خاصی (مثلاً رنگ چشم) را رمز گذاری می‌کند. حالت‌های مختلف یک خصیصه (آبی، قهوه ای) آلل (Allele) نامیده می‌شود.هر ژنی موقعیت خاص خود را بر روی کروموزم دارد. که این موقعیت لوکاس (Locus) نامیده می‌شود. مجموعه کاملی از مواد ژنتیکی (همه کروموزوم‌ها) ژنوم نامیده می‌شود. دسته خاصی از ژن‌های موجود در ژنوم، ژنوتیپ (Genotype) نامیده می‌شود. ژنوتیپ به همراه تغییرات پس از تولد، پایه و اساس فنوتیپ (Phenotype) موجود زنده (ارگانیزم)، ویژگی‌های فیزیکی و ذهنی از قبیل رنگ چشم و هوش و غیره است.
در تولید مثل، ابتدا ترکیب یا تغییر (Crossover) اتفاق می‌افتد. ژن‌های والدین برای ایجاد کروموزوم‌های جدید ترکیب می‌شوند. سپس جنین تشکیل یافته دچار تغییر می‌شود. جهش به این معناست که عناصر DNA کمی تغییر می‌کنند، و این تغییرات اغلب نتجه نسخه برداری غلط از ژن‌های والدین است. میزان شایستگی (Fitness) موجود زنده (جنین) بواسطه بقای آن اندازه گیری می‌شود.
در الگوریتم ژنتیک، مجموعه ای از متغیرهای طراحی را توسط رشته‌هایی با طول ثابت (Fixed Length) یا متغیر (Variable) کد گذاری می‌کنند که در سیستم‌های بیولوژیکی آن‌ها را کروموزوم یا فرد (Individual) می‌نامند. به متغیری که باید بهینه شود ژن، و اگر از دامنه مجازش مقدار دهی شود. را آلل گویند. هر رشته یک نقطه پاسخ در فضای جستجو را نشان می‌دهد. به ساختمان رشته‌ها یعنی مجموعه ای از پارامترها که توسط یک کروموزوم خاص نمایش داده می‌شود، ژنوتیپ و به مقدار رمزگشایی آن فنوتیپ می‌گویند. الگوریتم‌های وراثتی فرایندهای تکراری هستند، که هر مرحله تکراری را نسل و مجموعه‌هایی از پاسخ‌ها در هر نسل را جمعیت نامیده اند.
الگوریتم‌های ژنتیک، جستجوی اصلی را در فضای پاسخ به اجرا می‌گذارند. این الگوریتم‌ها با تولید نسل (Seeding) آغاز می‌شوند که وظیفه ایجاد مجموعه نقاط جستجوی اولیه به نام جمعیت اولیه (Initial Population) را بر عهده دارند و به طور انتخابی یا تصادفی تعیین می‌شوند. از آن جایی که الگوریتم‌های ژنتیک برای هدایت عملیات جستجو به طرف نقطه بهینه از روش‌های آماری استفاده می‌کنند، در فرایندی که به انتخاب طبیعی وابسته است، جمعیت موجود به تناسب برازندگی (Fitness) افراد آن برای نسل بعد انتخاب می‌شود.
سپس عملگرهای ژنتیکی شامل (Selection) ، پیوند، جهش و دیگر عملگرهای احتمالی اعمال شده و جمعیت جدید به وجود می‌آید. پس از آن، جمعیت جدیدی جایگزین جمعیت پیشین می‌شود و این چرخه ادامه می‌یابد. معمولا جمعیت جدید برازندگی بیشتری دارد. این بدان معناست که از نسلی به نسل دیگر جمعیت بهبود می‌یابد. هنگامی جستجو نتیجه بخش خواهد بود که به حداکثر نسل ممکن رسیده باشیم یا همگرایی حاصل شده باشد و یا معیارهای توقف براورده شده باشند.

تبلیغات AIcodeMahak

AIcode مرجع تخصصی آموزش مهندسی کامپیوتر و هوش مصنوعی

تماس با ما

ايميل: info@aicode.ir

عضویت در خبرنامه AIcode