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

در این آموزش تکنیک‌ بهینه‌سازی الگوریتم ژنتیک در پایتون را بر اساس یک مثال ساده پیاده‌سازی می‌کنیم. سعی ما بر این است که خروجی معادله را حداکثر کنیم. در این آموزش از اعداد اعشاری برای نمایش ژن‌ها، عملگر برش (one point crossover) و عملگر جهش (uniform mutation) استفاده شده است.

بررسی اجمالی الگوریتم ژنتیک

روندنما‌ (Flowchart) الگوریتم ژنتیک در تصویر زیر قابل مشاهده است. هر گام را به تفصیل در ادامه توضیح می‌دهیم.

روش‌های مختلفی جهت نمایش (representation) ژن‌ها وجود دارد مانند: نمایش به صورت باینری، اعشار، صحیح و غیره. با هر نوع از این نمایش‌ها رفتار مختلفی می‌شود.

عملگر جهش نیز انواع مختلفی دارد از جمله bit flip، swap، inverse، uniform ،non-uniform ،Gaussian shrink و غیره.

همچنین عملگر برش نیز انواع مختلفی دارد از جمله blend، one point، two points، uniform و غیره.

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

همچنین در نظر داشته باشید در این مقاله فرض شده است که خواننده فهم و درک کافی از چگونگی اجرا الگوریتم ژنتیک دارد در غیر اینصورت پیشنهاد می‌شود مقالات زیر را مطالعه کنید:

LinkedIn: https://www.linkedin.com/pulse/introduction-optimization-genetic-algorithm-ahmed-gad/
KDnuggets: https://www.kdnuggets.com/2018/03/introduction-optimization-with-genetic-algorithm.html
TowardsDataScience: https://towardsdatascience.com/introduction-to-optimization-with-genetic-algorithm-2f5001d9964b
SlideShare: https://www.slideshare.net/AhmedGadFCIT/introduction-to-optimization-with-genetic-algorithm-ga

شروع کدنویسی با پایتون

معادله‌ایی که قصد داریم آن را با پایتون پیاده‌سازی کنیم به اینصورت است.

Y = w1x1 + w2x2 + w3x3 + w4x4 + w5x5 + w6x6

معادله دارای ۶ ورودی (x1 to x6) و ۶ وزن (w1 to w6) است و همانطور که نشان داده شده است مقادیر ورودی به این صورت می‌باشد (7,5,11,1,-4,2) = (x1,x2,x3,x4,x5,x6). ما به دنبال پیدا کردن پارامترهای (وزن‌ها) هستیم که جواب چنین معادله‌ایی را حداکثر (maximize) کند. ایده به حداکثر رساندن چنین معادله‌ایی به نظر ساده می‌رسد، ورودی مثبت با بزرگترین عدد مثبت ممکن ضرب شود و عدد منفی نیز با کوچکترین عدد منفی ممکن ضرب شود. اما ایده‌ایی که ما درصدد اجرای آن هستیم این است که چگونه الگوریتم ژنتیک این کار را انجام دهد تا بدانیم بهتر است از وزن مثبت با اعداد مثبت در ورودی استفاده شود یا وزن‌های منفی با اعداد منفی در ورودی مورد استفاده قرار بگیرد. بگذارید پیاده‌سازی الگوریتم ژنتیک را شروع کنیم.

در ابتدا، اجازه دهید یک لیست با ۶ ورودی و یک متغییر جهت ذخیره تعداد وزن‌ها ایجاد کنیم:

# Inputs of the equation.
 equation_inputs = [4,-2,3.5,5,-11,-4.7]
 # Number of the weights we are looking to optimize.
 num_weights = 6

مرحله بعد تعریف جمعیت اولیه است. بر اساس تعداد وزن‌ها، هر کروموزوم (راه‌حل یا فرد نیز گفته می‌شود) در جمعیت دارای ۶ ژن است که به ازای هر وزن یک ژن داریم. اما سوال اینجایت که برای هر جمعیت چند راه‌حل وجود دارد؟ هیچ مقدار ثابتی برای آن وجود ندارد و ما می‌توانیم مقدار متناسب را با توجه به مسئله خود انتخاب کنیم. اینکار را می‌توانیم در کد قرار دهیم تا بتوانیم تغییرش دهیم.

در مرحله بعد، ما یک متغییر ایجاد می‌کنیم که تعداد راه‌حل‌ها در هر جمعیت را در اختیارمان می‌گذارد. متغییر بعدی برای ذخیره اندازه جمعیت است و در نهایت متغییری جهت نگه داری جمعیت اولیه ایجاد می‌کنیم.

import numpy

sol_per_pop = 8# Defining the population size.

pop_size = (sol_per_pop,num_weights) # The population will have sol_per_pop chromosome where each chromosome has num_weights genes.

#Creating the initial population.

new_population = numpy.random.uniform(low=-4.0, high=4.0, size=pop_size)

بعد از وارد کردن کتابخانه numpy، ما می‌توانیم با استفاده تابع numpy.random.uniform جمعیت اولیه را به صورت تصادفی ایجاد کنیم.شکل آن به صورت (6,8) خواهد بود. این به معنی ۸ کروموزوم است که هرکدام ۶ ژن (یکی برای هر وزن) دارند. پس از اجرای کد بالا، جمعیت به شرح زیر است:

توجه داشته باشید که داده‌ها به صورت تصادفی تولید می‌شوند بنابراین با اجرای دوباره کد داده‌ها تغییر می‌کنند.

بعد از آماده‌سازی جمعیت، مرحله بعدی با توجه به روندنما، نوشتن تابع برازش(fitness) است. ما قصد داریم بهترین افراد را از جمعیت کنونی به عنوان والد برای جفت‌گیری انتخاب کنیم.در مرحله بعد با استفاده از عملگرهای (crossover and mutation) فرزندان (نسل بعدی) را تولید می‌کنیم.این کار با استفاده از فرزندان و والدین انجام می‌شود. و این مراحل برای تعداد نسل‌هایی که می‌خواهدی تولید شوند تکرار می‌شود. کد بعدی این مراحل را پیاده‌سازی می‌کند:

import ga

num_generations = 5

num_parents_mating = 4
for generation in range(num_generations):
     # Measuring the fitness of each chromosome in the population.
     fitness = ga.cal_pop_fitness(equation_inputs, new_population)
    # Selecting the best parents in the population for mating.
     parents = ga.select_mating_pool(new_population, fitness, num_parents_mating)                               
 
     # Generating next generation using crossover.
     offspring_crossover = ga.crossover(parents,
                                        offspring_size=(pop_size[0]-parents.shape[0], num_weights))
 
     # Adding some variations to the offsrping using mutation.
     offspring_mutation = ga.mutation(offspring_crossover)
# Creating the new population based on the parents and offspring.
     new_population[0:parents.shape[0], :] = parents
     new_population[parents.shape[0]:, :] = offspring_mutation

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

اولین مرحله این است که مقدار برازش (fitness value) برای هر راه‌حل در بین جمعیت را با استفاده از تابع ga.cal_pop_fitness محاسبه کند. کد این تابع در ماژول GA به صورت زیر است:

def cal_pop_fitness(equation_inputs, pop):
     # Calculating the fitness value of each solution in the current population.
     # The fitness function calculates the sum of products between each input and its corresponding weight.
     fitness = numpy.sum(pop*equation_inputs, axis=1)
     return fitness

پارامترهای ورودی تابع برازش شامل جمعیت و مقادیر ورودی معادله(x1 تا x6) می‌باشد. این تابع هر مقدار ورودی معادله را با ژن مربوطه(وزن) ضرب می‌کند و در نهایت با هم جمع می‌کند. با توجه به تعداد راه‌حل‌ها (کروموزوم) در هر جمعیت، تعدادی SOPs (مجموع حاصلضرب) وجود خواهد داشت. پس با توجه به مقدار متغییر sol_per_pop که قبلا مقدار ۸ قرار داده‌ایم، مقادیر بازگشتی از تابع برازش ما ۸ تا خواهد بود.

توجه داشته باشید که هرچه مقدار برازش بالاتر باشد، راه‌حل بهتر خواهد بود.

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

def select_mating_pool(pop, fitness, num_parents):

    # Selecting the best individuals in the current generation as parents for producing the offspring of the next generation.

    parents = numpy.empty((num_parents, pop.shape[1]))

    for parent_num in range(num_parents):

        max_fitness_idx = numpy.where(fitness == numpy.max(fitness))

        max_fitness_idx = max_fitness_idx[0][0]

        parents[parent_num, :] = pop[max_fitness_idx, :]

        fitness[max_fitness_idx] = -99999999999

    return parents

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

parents = numpy.empty((num_parents, pop.shape[1]))

با توجه به جمعیت فعلی، این تابع ایندکس بالاترین مقدار برازش را بدست می‌آورد.

بهترین راه‌حل برای انتخاب با توجه به این خط از کد بدست می‌آید:

max_fitness_idx = numpy.where(fitness == numpy.max(fitness))

برای بازیابی راه‌حلی که از این مقدار برازش برگزیده (با توجه به ایندکس بدست آمده) از کد دستوری زیر استفاده می‌کنیم:

parents[parent_num, :] = pop[max_fitness_idx, :]

برای جلوگیری از انتخاب مجدد چنین راه‌حلی، مقدار برازش را روی مقدار بسیار کمی تنظیم می‌کنیم که احتمالا مجددا انتخاب نخواهد شد. این مقدار 99999999999− است. در نهایت آرایه‌ای از والدین انتخاب شده به عنوان مقدار بازگشتی تابع برگردانده می‌شود. که مطابق مثال به شرح زیر خواهد بود:

توجه داشته باشید که این چهار والد بر اساس مقادیر برازش به ترتیب (18.24112489, 17.0688537, 15.99527402, 14.40299221) بهترین افراد در جمعیت فعلی هستند.

گام بعدی استفاده از والدین انتخاب شده برای جفت‌گیری به منظور تولید فرزندان است.عملیات جفت‌گیری با عملگر برش (crossover) شروع می‌شود. تابع ga.crossover این عملیات را انجام می‌دهد. پارامترهای ورودی این تابع، والدین و اندازه فرزندان است.از اندازه فرزندان برای شناخت تعداد فرزندانی که باید از والدین تولید شوند استفاده می‌کنیم.این تابع در ماژول GA به صورت زیر پیاده‌سازی شده است.

def crossover(parents, offspring_size):
     offspring = numpy.empty(offspring_size)
     # The point at which crossover takes place between two parents. Usually, it is at the center.
     crossover_point = numpy.uint8(offspring_size[1]/2)
 
     for k in range(offspring_size[0]):
         # Index of the first parent to mate.
         parent1_idx = k%parents.shape[0]
        # Index of the second parent to mate.
        parent2_idx = (k+1)%parents.shape[0]
        # The new offspring will have its first half of its genes taken from the first parent.
        offspring[k, 0:crossover_point] = parents[parent1_idx, 0:crossover_point]
        # The new offspring will have its second half of its genes taken from the second parent.
        offspring[k, crossover_point:] = parents[parent2_idx, crossover_point:]
     return offspring

تابع با ایجاد یک آرایه خالی بر اساس اندازه فرزندان به صورت زیر شروع می‌شود:

offspring = numpy.empty(offspring_size)

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

crossover_point = numpy.uint8(offspring_size[1]/2)

سپس باید دو والد را برای انجام عمل برش انتخاب کنیم. شاخص‌های این والدین مطابق با این دو خط در کد انتخاب می‌شوند:

parent1_idx = k%parents.shape[0]
parent2_idx = (k+1)%parents.shape[0]

والدین به روشی مشابه حلقه انتخاب می‌شوند.در ابتدا اندیس‌های ۰ و ۱ برای تولید فرزند انتخاب می‌شوند، اگر هنوز ظرفیت تولید فرزند وجود داشته باشد، والدین با اندیش ۱ و ۲ را برای تولید فرزند انتخاب می‌شوند. اگر به فرندان بیشتر نیاز باشد پس والدین با اندیس ۲ و ۳ را برای این کار انتخاب می‌کنیم. اندیس ۳ والد آخر ما است، اگر بازهم نیاز به تولید فرزند داریم پس والدین را با اندیس ۳ و ۰ را انتخاب می‌کنیم و الاآخر.

راه‌حل‌ها پس از اعمال عملگر برش روی والد در متغییر فرزندان ذخیره می‌شوند که به شرح زیر است:

گام بعدی اعمال عمگر پرش (mutation) روی نتایج ذخیره شده در متغییر فرزندان است. این کار با استفاده از تابع ga.mutation که در ماژول GA قرار دارد انجام می‌شود. پارامتر ورودی این تابع فرزندانی که با استفاده از عملگر برش بدست آمده‌اند می‌باشد و پس از اعمال عملگر جهش یکنواخت فرزندان را به عنوان خروجی برمی‌گرداند.کد این تابع به شرح زیر می‌باشد:

def mutation(offspring_crossover):
    
    # Mutation changes a single gene in each offspring randomly.

     for idx in range(offspring_crossover.shape[0]):

         # The random value to be added to the gene.

         random_value = numpy.random.uniform(-1.0, 1.0, 1)
         offspring_crossover[idx, 4] = offspring_crossover[idx, 4] + random_value
    return offspring_crossover

این حلقه به ازای هر فرزند اجرا می‌شود به اینصورت که یک عدد تصادفی یکنواخت در بازه -۱ تا ۱ ایجاد می‌شود.

random_value = numpy.random.uniform(-1.0, 1.0, 1)

چنین عدد تصادفی پس از این خط با شاخص 4 فرزندان به ژن اضافه می شود:

offspring_crossover[idx, 4] = offspring_crossover[idx, 4] + random_value

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

چنین نتایجی توسط تابع برمی‌گردد و به متغیر offspring_crossover اضافه می‌شود.

در این مرحله ، ما 4 فرزند از 4 والدین منتخب با موفقیت تولید کردیم و آماده هستیم تا جمعیت جدید از نسل بعدی را ایجاد کنیم.

توجه داشته باشید که GA یک روش بهینه سازی مبتنی بر تصادف است. سعی می شود با اعمال برخی تغییرات تصادفی روی آنها ، راه حلهای فعلی را ارتقا دهد. از آنجا که چنین تغییراتی تصادفی هستند ، ما مطمئن نیستیم که آنها راه حل های بهتری را ارائه می دهند. به همین دلیل ، ترجیح داده می شود بهترین راه حل های قبلی (والدین) در جمعیت جدید حفظ شود. در بدترین حالت وقتی همه فرزندان جدید نسبت به والدین از این بدتر باشند ، ما به استفاده از چنین والدینی ادامه خواهیم داد. در نتیجه تضمین می کنیم که نسل جدید حداقل نتایج خوب قبلی را حفظ کرده و بدتر نمی شود. جمعیت جدید 4 راه حل اول خود را از والدین قبلی خواهد داشت. 4 راه حل آخر از فرزندان حاصل از اعمال متقاطع و جهش حاصل می شود:

new_population[0:parents.shape[0], :] = parents
new_population[parents.shape[0]:, :] = offspring_mutation

با محاسبه برازش کلیه راه حل ها (والدین و فرزندان) از نسل اول ، برازش آنها به شرح زیر است:

بالاترین برازش قبلی 18.24112489 بود اما اکنون 31.7328971158 است. این بدان معنی است که تغییرات تصادفی به سمت یک راه حل بهتر حرکت کردند. این عالی است. اما با گذشت نسل های بیشتری می توان چنین نتایج را افزایش داد. در زیر نتایج هر مرحله برای 4 نسل دیگر آورده شده است: