کد الگوریتم ژنتیک در پایتون Python

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

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

الگوریتم ژنتیک واقعی که بر اساس ایده‌ی تکامل بیولوژیکی در طبیعت عمل می‌نمایند، بر روی جمعیتی از راه حل‎‌های بالقوه یا کروموزوم‌ها که هر یک می‌توانند به‌عنوان پاسخی از مسئله تلقی شوند، با اعمال عملگرهای ژنتیکی به جستجوی راه حل نهایی می‌پردازند. در الگوریتم ژنتیکی، بسیاری از مکانیزم‌هایی که در زیست شناسی وجود دارد، نظیر انتخاب ژن برتر، ترکیب ژن‌ها، جهش ژن‌ها، مهاجرت افراد جمعیت، محلی بودن گونه‌ها و … شبیه سازی می‌شوند. در این الگوریتم‌ها، جستجو بر روی مجموعه‌هایی از راه حل‌ها به‌صورت موازی انجام می‌شود، درحالی‌که در روش‌های سنتی جستجو به‌صورت ترتیبی است.

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

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

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

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

کد ژنتیک در پایتون

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

• تابع  SPHERE
• تابع ACKLEY
• تابع SUM SQUARES
•  تابع ROSENBROCK
• تابع SUM OF DIFFERENT POWERS
• تابع ZAKHAROV
• تابع Rastrigin

توابع تست برای ارزیابی الگوریتم های بهینه سازی به‌کار می‌روند که در اینجا ما به این 7 تابع اکتفا کرده‌ایم ولی در سورس کد با 12 نوع تابع مختلف (همانند مقاله) ارزیابی شده است.

همچنین لازم به ذکر است که برای اجرای الگوریتم بهینه سازی روی مسئله مورد نظر تابع هزینه یا Cost Function آن تغییر خواهد کرد و بقیه الگوریتم دست نخورده باقی می‌ماند بنابراین برای اجرای الگوریتم GA در پایتون برای بهینه سازی مسئله خودتان تابع هزینه خود را بر اساس پارامترهای مسئله خود تعریف کنید.

قسمت هایی از سورس کد الگوریتم ژنتیک در پایتون

iters=500
lb=-100
ub=100
dim=30
popSize=50
cp = 1 #crossover Probability
mp = 0.01 #Mutation Probability
keep = 2; # elitism parameter: how many of the best individuals to keep from one generation to the next
    
     
if not isinstance(lb, list):
   lb = [lb] * dim
if not isinstance(ub, list):
   ub = [ub] * dim
        
bestIndividual=numpy.zeros(dim)    
scores=numpy.random.uniform(0.0, 1.0, popSize) 
bestScore=float("inf")
    
ga = numpy.zeros((popSize, dim))
for i in range(dim):
    ga[:, i]=numpy.random.uniform(0,1,popSize) * (ub[i] - lb[i]) + lb[i]
convergence_curve=numpy.zeros(iters)
    
    
    
for l in range(iters):

        #crossover
  ga = crossoverPopulaton(ga, scores, popSize, cp, keep)
           
        #mutation
  mutatePopulaton(ga, popSize, mp, keep, lb, ub)
           
  ga = clearDups(ga, lb, ub)
       
  scores = calculateCost(ga, popSize, lb, ub)
            
  bestScore = min(scores)
        
        #Sort from best to worst
  ga, scores = sortPopulation(ga, scores)

***  توجه  ***

قبل از اجرای سورس کد الگوریتم در محیط پایتون حتماً از نصب پکیج‌‎های مورد استفاده در این سورس کد در Python خود مطمئن شوید. پکیج‌های استفاده شده در این سورس کد numpy و matplotlib می‌باشد که اولی پکیج مربوط به استفاده از آرایه‌ها و ماتریس‌ها در پایتون و دومی مربوط به عملیات‌های نموداری و Plot گرفتن می‌باشد. پیشنهاد ما نصب اسپایدر (Spyder (Python 3.7 است که هم پایتون و پکیج‌های مختلف و هم IDE های مختلفی را همراه با امکان آپدیتشان نصب می‌کند.

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

سورس کد الگوریتم ژنتیک GA در پایتون Python عنوان اثری است که در این پست به آن پرداخته شده است. این سورس کد در پایتون و با IDE اسپایدر (Spyder (Python 3.7 نوشته شده و بصورت کامل توسط گروه پشتیبانی پی استور تست و اجرا شده است. این اثر دارای نشان تضمین کیفیت پی استور می باشد. برای دانلود سورس کد الگوریتم ژنتیک در پایتون آن را خریداری کنید.