ساعدنیوز
ساعدنیوز

الگوریتم ژنتیک و کاربردهای آن

  یکشنبه، 21 آذر 1400   زمان مطالعه 8 دقیقه
الگوریتم ژنتیک و کاربردهای آن
الگوریتم ژنتیک-(Genetic Algorithm - GA) تکنیک جستجویی در علم رایانه برای یافتن راه‌حل تقریبی برای بهینه‌سازی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتمهای تکامل است که از تکنیکهای زیست‌شناسی مانند وراثت و جهش استفاده می‌کند.

الگوریتم های ژنتیک (به انگلیسی: Genetic algorithm) تکنیک جستجو در علم رایانه برای یافتن راه حل تقریبی برای بهینه سازی مدل، ریاضی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتم های تکاملی است که از تکنیک های زیست شناسی فرگشتی مانند وراثت، جهش زیست شناسی و اصول انتخابی داروین برای یافتن فرمول بهینه جهت پیش بینی یا تطبیق الگو استفاده می شود. الگوریتم های ژنتیک اغلب گزینه خوبی برای تکنیک های پیش بینی بر مبنای رگرسیون هستند. در مدل سازی الگوریتم ژنتیک یک تکنیک برنامه نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مسئله استفاده می کند. مسئله ای که باید حل شود دارای ورودی هایی می باشد که طی یک فرایند الگوبرداری شده از تکامل ژنتیکی به راه حل ها تبدیل می شود سپس راه حل ها به عنوان کاندیداها توسط تابع برازش یا تابع برازندگی (Fitness Function) مورد ارزیابی قرار می گیرند و چنانچه شرط خروج مسئله فراهم شده باشد الگوریتم خاتمه می یابد. به طور کلی یک الگوریتم مبتنی بر تکرار است که اغلب بخش های آن به صورت فرایندهای تصادفی انتخاب می شوند که این الگوریتم ها از بخش های تابع برازش، نمایش، انتخاب و تغییر تشکیل می شوند.

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

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

الگوریتم ژنتیک (GA)، یک الگوریتم جستجوی ابتکاری انطباق پذیر است که بر مبنای ایده های تکاملی انتخاب طبیعی و ژنتیک طراحی شده است. به این ترتیب این الگوریتم نمایانگر استفاده ی هوشمند از یک الگوریتم جستجوی تصادفی برای حل مسائل بهینه سازی می باشد. اگرچه الگوریتم های ژنتیک از پدیده هایی تصادفی استفاده می کنند اما خودشان به هیچ وجه تصادفی نیستند بلکه، آن ها از اطلاعات تاریخی موجود برای هدایت عملیات جستجو به منطقه ای با عملکرد بهتر در فضای جستجو استفاده می کنند. روش های اصلی الگوریتم ژنتیک به گونه ای طراحی شده اند تا بتوانند فرآیند های ضروری برای تکامل در سیستم های طبیعی را شبیه سازی کنند. از جمله مهمترین این فرآیند ها، آن هایی هستند که از قوانینی که اولین بار توسط چارلز داروین و با نام “بقای اصلح”(Survival Of The Fittest) مطرح شد، پیروی می کنند. علت این امر آن است که در طبیعت، رقابت میان موجودات زنده برای دستیابی به منابع کمیاب منجر به غلبه اصلح ترین موجودات بر موجودات ضعیف تر می شود.

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

الگوریتم ژنتیک به دلیل قدرت و دوام بیشتر نسبت به سایر روش های مبتنی بر هوش مصنوعی، بهتر است. بر خلاف سیستم های هوش مصنوعی قدیمی تر، الگوریتم ژنتیک با تغییر اندک مقادیر ورودی و یا با وجود مقادیر قابل توجهی از نویز در سیستم به راحتی قطع نمی شود. علاوه بر این، در جستجوی یک فضای حالت بزرگ، فضای حالت Multimodal و یا یک رویه چند بعدی، استفاده از الگوریتم ژنتیک مزیت های بسیار بیشتری نسبت به روش های جستجوی متداول در سایر تکنیک های بهینه سازی مانند برنامه ریزی خطی، جستجوی تصادفی و یا روش های جستجوی اول عمق، اول سطح و یا praxis دارد.

روش های نمایش

قبل از این که یک الگوریتم ژنتیک برای یک مسئله اجرا شود، یک روش برای کد کردن ژنوم ها به زبان کامپیوتر باید به کار رود. یکی از روش های معمول کد کردن به صورت رشته های باینری است: رشته های ۰ و ۱. یک راه حل مشابه دیگر کد کردن راه حل ها در آرایه ای از اعداد صحیح یا اعداد اعشاری است. سومین روش برای نمایش صفات در یک GA یک رشته از حروف است، که هر حرف دوباره نمایش دهنده یک خصوصیت از راه حل است. خاصیت هر سه روش این است که آن ها تعریف سازنده ای را که تغییرات تصادفی در آن ها ایجاد می کنند را آسان می کنند: ۰ را به ۱ و برعکس، اضافه یا کم کردن ارزش یک عدد یا تبدیل یک به صفر یا برعکس. یک روش دیگر که توسط John Koza توسعه یافت، برنامه نویسی ژنتیک است؛ که برنامه ها را به عنوان شاخه های داده در ساختار درخت نشان می دهد. در این روش تغییرات تصادفی می توانند با عوض کردن عملگرها یا تغییر دادن ارزش یک گره داده شده در درخت، یا عوض کردن یک زیر درخت با دیگری به وجود آیند.

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

در هر مسئله قبل از آنکه بتوان الگوریتم ژنتیک را برای یافتن یک پاسخ به کار برد به دو عنصر نیاز است:در ابتدا روشی برای ارائه یک جواب به شکلی که الگوریتم ژنتیک بتواند روی آن عمل کند لازم است. در دومین جزء اساسی الگوریتم ژنتیک روشی است که بتواند کیفیت هر جواب پیشنهاد شده را با استفاده از توابع تناسب محاسبه نماید.

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

در دهه هفتاد میلادی دانشمندی از دانشگاه میشیگان به نام جان هلند ایده استفاده از الگوریتم ژنتیک را در بهینه سازی های مهندسی مطرح کرد. ایده اساسی این الگوریتم انتقال خصوصیات موروثی توسط ژن هاست. فرض کنید مجموعه خصوصیات انسان توسط کروموزوم های او به نسل بعدی منتقل می شوند. هر ژن در این کروموزوم ها نماینده یک خصوصیت است. به عنوان مثال ژن ۱ می تواند رنگ چشم باشد، ژن ۲ طول قد، ژن ۳ رنگ مو و الی آخر. حال اگر این کروموزوم به تمامی، به نسل بعد انتقال یابد، تمامی خصوصیات نسل بعدی شبیه به خصوصیات نسل قبل خواهد بود. بدیهیست که در عمل چنین اتفاقی رخ نمی دهد. در واقع به صورت هم زمان دو اتفاق برای کروموزوم ها می افتد. اتفاق اول جهش (Mutation) است. «جهش» به این صورت است که بعضی ژن ها به صورت کاملاً تصادفی تغییر می کنند. البته تعداد این گونه ژن ها بسیار کم می باشد اما در هر حال این تغییر تصادفی همانگونه که پیشتر دیدیم بسیار مهم است؛ مثلاً ژن رنگ چشم می تواند به صورت تصادفی باعث شود تا در نسل بعدی یک نفر دارای چشمان سبز باشد. در حالی که تمامی نسل قبل دارای چشم قهوه ای بوده اند. علاوه بر «جهش» اتفاق دیگری که می افتد و البته این اتفاق به تعداد بسیار بیشتری نسبت به «جهش» رخ می دهد چسبیدن دو کروموزوم از طول به یکدیگر و تبادل برخی قطعات بین دو کروموزوم است. این مسئله با نام Crossover شناخته می شود. این همان چیزیست که باعث می شود تا فرزندان ترکیب ژن های متفاوتی را (نسبت به والدین خود) به فرزندان خود انتقال دهند.

روش های انتخاب الگوریتم ژنتیک

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

  • انتخاب Elitist

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

  • انتخاب Roulette

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

  • انتخاب Scaling

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

  • انتخاب Tournament

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

بعضی از روش های دیگر عبارتند از:

  1. Hierarchical Selection
  2. Steady-State Selection
  3. Rank Selection

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

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

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

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

دیدگاه ها
  دیدگاه ها
پربحث های هفته   
سوژه شدن موجودی حساب هوش پران مشتری مغازه موبایل فروشی+عکس/ تا حالا این همه عدد رو کنار هم ندیده بودم که امروز دیدم🙄 (771 نظر) میزبانی حسن روحانی از سیاستمداران و اقوام در مراسم عید دیدنی در منزل زیبا و ایرانی پسندش+ عکس/ چه مبلمانی، چه فرش هایی، از همه مهمتر چه خونه دلبازی😍 (412 نظر) مراسم سلام عید نوروز و اهداء سکه توسط فرح پهلوی به همسران مقامات دولتی +عکس/ ولخرجی زن تازه به دوران رسیده زمانی که مردم غرق در فقر و بدبختی بودند! (391 نظر) خلاقیت خنده دار یک ایرانی برای گرم کردن آب حماسه ساز شد/ خسته نباشی هم وطن+ عکس (254 نظر) تلاوت زیبا و دلنشین سوره شمس توسط رهبر معظم انقلاب+ویدئو (245 نظر) تصویری از عیادت نجم الدین شریعتی، مجری برنامه سمت خدا از رهبر معظم انقلاب و استقبال گرم ایشان (206 نظر) صبحانه مفصل و رنگارنگ دو نفره رضا گلزار و آیسان خانوم+عکس/از خاویار گرفته تا آواکادو و انار وحشی... (201 نظر) روایتی از هواپیمایی که برای آوردن یک روبان عروسی برای فرح پهلوی از تهران به پاریس رفت! (178 نظر) حضور علی دایی در رستوران شیک فریبا نادری به صرف افطار+عکس/ ذوق و خوشحالی خانم بازیگر از حضور شهریار ایران در رستورانش (165 نظر) رونمایی منوچهر هادی از خواهر و شوهر خواهر پزشکش+ عکس/ به قولی مخ خانواده ایشون هستن که پسرش هم دکتره (159 نظر) خلاقیت منحصر به فرد پسر مشهدی با ساخت تریلی حماسه آفرید/ هیلتر هم مغز اینو نداشت!+عکس (145 نظر) دو پادشاه یکی از ایران (ناصرالدین شاه) و دیگری از ژاپن (میجی) در یک زمان به اروپا رفتند/ تفاوت ها را بنگرید (139 نظر) خلاقیت خنده دار راننده شمالی، با نوشته جالب پشت کامیون حماسه ساز شد/ آخه لامصب جای این چیزا پشت ماشینه؟!🤣 (127 نظر) خلاقیت تحسین برانگیز یک برند خارجی در اختراع کیف برای نون بربری/ مشکل حمل و نقل بربری هم حل شد خدارو شکر😂+عکس (132 نظر) خواهر یکتا ناصر سکوتش را شکست (130 نظر)
دیگران می‌خوانند   
دورهمی خانوادگی سپیده بزمی پور و دوستانش در یک ویلای متروکه! +عکس فیلم آخرین افطاری رهبر معظم انقلاب در کنار امام خمینی (ره) مانتو ژاکارد و مزونی یکتا ناصر+عکس/ عجب رنگ دلبری داره این مانتو! دانشجویان خارجی در بدو ورود به دانشگاه‌های ایران باید زبان فارسی یاد بگیرند 4 بازیگر فوت شده‌یِ سریال خانه به دوش پس از پایان فیلمبرداری+عکس/ روحشون شاد و یادشون گرامی هنرنمایی و انتقاد ایرج نوذری از تغییر لحن برخی افراد در آنتن زنده+ویدئو/ فقط خنده های المیرا شریفی مقدم😂 حضور رهبر معظم انقلاب در مراسم عقد مهدی هاشمی فرزند مرحوم هاشمی رفسنجانی+عکس/ خجالتی بودن داماد در تصویر مشهوده پیشنهادات وسوسه برانگیز مریم رجوی و مسعود رجوی به اسرا چه بود؟ (عکس) پاسخ خنده دار دانش آموز به سوال ادبیات در ورقه امتحانی/ کاش کتابو یه ورق میزدی!! عیدی دادن ناصرالدین شاه سوژه شد /هیچ وقت آن‌قدر شاهزاده ندیده بودیم! خلاقیت خنده دار یک بانوی اهل فن ایرانی در استفاده کاربردی از دریل حماسه آفرید/ هم کدبانو هم فنی +عکس خلاقیت منحصربفرد در طراحی راه پله با الهام از میوه ها/ چشم نمیشه ازشون برداشت + عکس تصویری از پسر شهاب حسینی بازیگر قباد در سریال شهرزاد که از خودش بزرگتر است/به شهاب حسینی نمیخوره پسری به این بزرگی داشته باشه (ویدئو) تجربهٔ شیرین مرگ در کودکی و دیدن رنگ‌هایی از جنس نور/ استاد محمود فرشچیان در برنامهٔ زندگی پس از زندگی روایت می‌کند بیوگرافی و زندگینامۀ دکتر آذر اندامی باکتری‌شناس و کاشف واکسن شبه وبای التور در ایران نگاهی به چیدمان شیک هفت سین کریم باقری اسطوره فوتبال/ چه خونه زندگی داره+عکس خوانندگی بی‌نظیر شرکت کننده خوش صدای صداتو با آهنگ اصیل ایرانی/ چقدر فوق العاده سنتور میرنه+ویدیو جشن تولد ساده و خلوت بهرام افشاری بهتاش سریال پایتخت درکنار نوید محمدزاده و رفیق فابش+عکس (فیلم) خلاقیت جالب و جنجالی راننده اسنپ در محیط داخلی خودرو که غوغا کرده!/راننده خوش ذوق! (عکس) عاشقانه شاهرخ استخری و همسرش در ایام عید/ این دو زوج جنجالی هرروز جوان‌تر از دیروز می‌شوند! (عکس) پریناز ایزدیار بازیگر نقش جیران ناصرالدین شاه با این عکس‌های زیبا نوروز را جشن گرفت! سفره های مجلل افطاری و سحری شاه خوش اشتهای قاجار برای درباریان و همسرانش/ چلو کباب و آبگوشت و ...+عکس نوشته قشنگ و تحسین برانگیز روی شیشه یک مغازه‌ بستنی فروشی جلب توجه کرد!!/بزرگ منشی و خوب بودن به دارایی انسان نیست به قلب مهربان و بخشندگی اوست! افطاری ساده و خوشمزه ستاره سادات قطبی مجری پرانرژی در ماه رمضان+عکس خلاقیت خنده دار و حماسه ساز یک متورسوار ایرانی برای حمل بار/ هنر نزد ایرانیان است و بس+عکس رونمایی از عکس سرعقد حامد آهنگی و خانومش لحظه انداختن حلقه ازدواج / از اولش هم انقدر خوش خنده بوده😂 تهران گردی رضا قوچان نژاد، شوهر خواهر خوشتیپ و باکلاس ساره بیات همراه با پسرش+عکس (فیلم) افطاری ساده و صمیمی در بیت رهبری و پذیرایی دوستانه رهبر معظم انقلاب از مهمانان/ یک لقمه نان با دل خوش بیوگرافی حامد سلطانی مجری اعجوبه ها و سال تحویل/ همسر اول دوم و علت تصادف + فیلم و عکس‌های جذاب و دیدنی (عکس) چیدمان مبلمان استیل و سلطنتی خونه وریا غفوری و همسر چشم رنگی اش در یک جشن تولد عاشقانه/ ماشالا چقدر به هم میان😍 آمار تلفات حمله اسرائیل به حلب سوریه + جزئیات دیزاین شیک کیک حامد سلطانی مجری برنامه سال تحویل با یک عکس عاشقانه برای سالگرد ازدواجشان+عکس بارش باران و کاهش دمای برخی استانها گام های استوار دولت در مسیر «جهش تولید»؛ غول‌های صنعت به میدان بازگشتند (عکس) ابتکار خنده دار جوان ایرانی در پیوند موفقیت آمیز درب بازکن نوشابه به در ماشین/ سلطان مدیریت بحران😂👌 پرهیز از تخریب در انتخابات، همواره مورد تاکید رهبری بوده است عزای خانواده شیرازی به جشن تبدیل شد + جزئیات (عکس) خلاقیت خنده دار یک ایرانی در نصب شیر آب روشویی به پراید/ لامصب از مغزش بهینه استفاده کرده😂 انتشار اولین عکس از رهبر معظم انقلاب با لباس محلی سیستان و بلوچستان 10 آقازاده ای که تاکنون پای میز محاکمه رفته اند / اجرای عدالت حتی برای فرزندان هاشمی رفسنجانی، آیت الله جنتی و ....
تیتر امروز   
دانشجویان خارجی در بدو ورود به دانشگاه‌های ایران باید زبان فارسی یاد بگیرند آمار تلفات حمله اسرائیل به حلب سوریه + جزئیات بارش باران و کاهش دمای برخی استانها گام های استوار دولت در مسیر «جهش تولید»؛ غول‌های صنعت به میدان بازگشتند پرهیز از تخریب در انتخابات، همواره مورد تاکید رهبری بوده است عزای خانواده شیرازی به جشن تبدیل شد + جزئیات 10 آقازاده ای که تاکنون پای میز محاکمه رفته اند / اجرای عدالت حتی برای فرزندان هاشمی رفسنجانی، آیت الله جنتی و .... علی دایی 4 برادر خوش تیپ و عجیب‌تر از خود دارد؛ افسانه 5 برادران خانواده شهریار توصیه به استعفای سفیر ایران در باکو به خاطر مصاحبه با یک خبرنگار با پوشش زننده از سوی رسانه اصولگرا پاداش 4 میلیارد تومانی برای بچه‌دار شدن خبرساز شد حواشی داغ امروز جمعه 10 فروردین 1403 / یادگاری عجیب علیرضا جهانبخش برای دختر هلندی! 4 بازیگر فوت شده‌یِ سریال خانه به دوش پس از پایان فیلمبرداری+عکس/ روحشون شاد و یادشون گرامی پیشنهادات وسوسه برانگیز مریم رجوی و مسعود رجوی به اسرا چه بود؟ عیدی دادن ناصرالدین شاه سوژه شد /هیچ وقت آن‌قدر شاهزاده ندیده بودیم! بیوگرافی حامد سلطانی مجری اعجوبه ها و سال تحویل/ همسر اول دوم و علت تصادف + فیلم و عکس‌های جذاب و دیدنی