رتبه موضوع:
  • 0 رای - 0 میانگین
  • 1
  • 2
  • 3
  • 4
  • 5
الگوریتم ژنتیک(Genetic Algorithm)
#1
الگوریتم ژنتیک چیست؟

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

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

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

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

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

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

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

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


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

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

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

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

* بیشترین درجه برازش فرزندان حاصل شود یا دیگر نتایج بهتری حاصل نشود. (در واقع تغییرات تابع برازش کم شود)

* بازرسی دستی.

* ترکیبی از حالات بالا.
پاسخ
#2
الگوریتم ژنتیک یا Genetic Algorithm (GA) در واقع شبیه سازی بقای انسان هست! تا حالا پیش خودتون فکر کردین این همه سال گذشته چطوری انسان ها از بین نرفتن و نسلشون پا برجاس؟ فکر می کنید رمز موفقیتشون چیه؟
[عکس: q1.gif]فکر کنم 183462130973.347928374261010000001 باشه!
[عکس: a.gif] " ... "
انسان ها بقا دارن چون با یه قانون خاصی پیش میرن که واضحه که موفق بوده!
حالا همین قانون رو توی کامپیوتر میشه شبیه سازی کرد! اما چجوری؟
فکر کنید میخوایم جواب این تابع رو بدست بیاریم:

کد پی‌اچ‌پی:
X^e^3*sin(X) + int(-X^X) / 12 

بنظر خیلی پیچیده میاد! شاید با روش های تحلیلی حل نشه و نیاز به محاسبات عددی باشه! یکی از راه ها الگوریتم ژنتیک هست که بعضی اوقات به شکل باور نکردنی سریع به جواب میرسه.
خوب پس من با یه مقدمه ازش شروع می کنم:
[عکس: 3.png]
اولین مرحله اینه که ما یک سری کرومزوم به عنوان جمعیت اولیه بصورت تصادف انتخاب می کنیم. هر کرومزوم یه عدد هست در مبنای دو.
مثلا این کرومزوم هارو به عنوان جمعیت اولیه در نظر می گیریم:
  1. 00001011
  2. 00100010
  3. 01000000
  4. 11100001
  5. 01101100
  6. 00000111
  7. 11001010
  8. 11110000
  9. 00010101
  10. 10000000
  11. 11100100
بعد از اینکه جمعیت اولیه معلوم شد این کرومزوم ها توی تابع Fitness امتحان میشن و بر حسب اینکه به جواب مورد نظر نزدیکن یا نه یه عدد بین صفر تا یک بهشون اختصاص داده میشه که صفر یعنی اصلا بدرد نمی خوره و یک یعنی عالیه!
بر حسب سلامتی کرومزوم ها چند تا از اون ها به عنوان والدین نسل بعدی انتخاب میشن! مرحله ی بعدی مرحله ی Breed هست که طبق فرایند Crossover کرومزوم ها با هم ازدواج می کنن و بچه دار میشن!
[عکس: q2.gif]وااای مگه یه مشت صفرو یکم می تونن با هم ازدواج کنن!
[عکس: a.gif] " یکم صبر کنی میبینی که می تونن! "
خوب حالا فرآیند Crossover چطور انجام میشه؟
از کرومزوم های برگزیده دوتا دوتا انتخاب میشن و فرایند Crossover روی هر زوج بصورت زیر انجام میشه:
  1. First pair:

  2. 00001|011


  3. 00100|010
  4. After crossover:

  5. 00001010


  6. 00100011

در بالا فرآیند Crossover رو برای زوج اول می بینید! همونطور که مشخصه اول هر کزومزوم از بیت 5ام به دو قسمت تقسیم شدن و 5 بیت اول کرومزوم اول با 3 بیت دوم کرومزوم دوم ترکیب شده و برعکس. به این ترتیب دو فرزند جدید بوجود اومد.
همین کار برای بقیه ی کرومزوم ها هم انجام میشه، ممکنه یک کرومزوم دو یا چند بار در فرآیند Crossover بکار برده شه، احتمال شرکت کرومزوم هایی که سلامت بهتری دارند توی فرآیند Crossover بیشتره!
بعد از فرآیند Crossover یک مرحله داریم که احتمال وقوعش خیلی کم هست به نام جهش یا Mutation. توی این فرآیند یک بیت تصادفی از یه کرومزوم تصادفی رو عوض می کنند. مثلا اگر بیت چهارم یک کرومزوم انتخاب بشه در صورتی که صفر باشه اونو یک می کنند یا بلعکس.
  1. First chromosome:
  2. 00001011


  3. After mutation:


  4. 0001
    1011
این فرایند تو واقعیت هم وجود داره مثلا در یک آدم جهشی به وجود میاد و نابغه میشه یا در یه آدم دیگه جهش بوجود میاد و ناقص میشه! در الگوریتم ژنتیک هم همینطوره، یک جهش ممکنه کاملا مفید یا کاملا مضر باشه.
بعد از این مرحله دوباره کرومزوم های جدید به جمعیت اولیه برای نسل بعد بر می گردند و این فرآیند ها تکرار میشه تا با یک تلورانسی به جوابی که می خوایم نزدیک شیم! این روش در مقایسه با بقیه ی روش های آزمایش و خطا خیلی پیشرفته تره و خیلی وقت ها بسیار سریعتر به نتیجه ی مطلوب میرسه!
انشاالله در آینده ی نه چندان دور یک مثال هم برای این مبحث از هوش مصنوعی رو بررسی می کنیم.

منبع
[عکس: matlabOpencv.gif]

« کلاس های آموزش پردازش تصویر با نرم افزار متلب »

جهت کسب اطلاعات بیشتر با شماره تلفن 09130130252 تماس حاصل فرمائید.


«جهت مشاهده سرفصل این دوره کلیک نمایید»
پاسخ
سپاس شده توسط kimiya_496 ، siryahya
#3
سلام
آیا شما کد ژنتیک یا هر الگوریتم ابتکاری دیگه ای که در مورد مذاکره باشه رو دارید یا دیدید؟
مرسی
پاسخ
سپاس شده توسط siryahya
#4
سلام
این تاپیک رو ببینید:
سورس کد مسئله هشت یا n وزیر با الگوریتم ژنتیک با #C
[عکس: matlabOpencv.gif]

« کلاس های آموزش پردازش تصویر با نرم افزار متلب »

جهت کسب اطلاعات بیشتر با شماره تلفن 09130130252 تماس حاصل فرمائید.


«جهت مشاهده سرفصل این دوره کلیک نمایید»
پاسخ
سپاس شده توسط
#5
مرسی. ولی 8 وزیر با مذاکره فرق داره. من دنبال بحث مذاکره و چانه زنی هستم با ژنتیک.
پاسخ
سپاس شده توسط
#6
سلام
کد nوزیر را با الگوریتم ژنتیک در محیط matlab  به صورت سورس کامل میخواستم کسی از دوستان میتونه کمکم کنه؟
پاسخ
سپاس شده توسط
#7
با سلام
عامیانه توضیح دادنتون خیلی جالب و رسا بود
ممنونم
پاسخ
سپاس شده توسط
#8
خیلی الگوریتم جذابیه .




www.idehshot.com
پاسخ
سپاس شده توسط


موضوعات مشابه ...
موضوع نویسنده پاسخ بازدید آخرین ارسال
  سورس کد و آموزش های الگوریتم کلونی مورچه ها(Ant Colony Algorithm) مهرداد عباسی 31 59,823 01-25-2014, 02:36 PM
آخرین ارسال: najafi123
Smile الگوریتم های دوز بازی laleh62 0 2,652 10-04-2013, 06:14 PM
آخرین ارسال: laleh62
  حل مسئله جورچین با الگوریتم ژنتیک bdb 3 5,926 05-24-2013, 06:00 PM
آخرین ارسال: bdb
  پیاده سازی مسئله 8 وزیر با استفاده از الگوریتم ABC sharokh 2 6,783 12-10-2012, 05:20 PM
آخرین ارسال: FATEMEH1369
  سورس کد مسئله هشت یا n وزیر با الگوریتم ژنتیک با #C مهرداد عباسی 18 44,629 11-23-2012, 10:21 AM
آخرین ارسال: مهدی ابراهیمی
  الگوریتم کلونی زنبور عسل مصنوعی Artificial Bee Colony (ABC) Algorithm مهدی ابراهیمی 6 19,323 05-23-2012, 09:54 PM
آخرین ارسال: مهدی ابراهیمی

پرش به انجمن:


کاربران در حال بازدید این موضوع: 1 مهمان