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

۵۱۴۳ بازدید
آخرین به‌روزرسانی: ۰۳ بهمن ۱۴۰۱
زمان مطالعه: ۲۶ دقیقه
پیاده سازی الگوریتم ژنتیک در پایتون – راهنمای گام به گام

در این مطلب قصد داریم الگوریتم ژنتیک را در پایتون پیاده‌سازی کرده و از آن برای بیشینه‌سازی (Maximization) (که نوعی بهینه‌سازی (Optimization) است) یک تابع دلخواه استفاده کنیم. از مطالب پیش‌نیاز و مفید برای یادگیری این مطلب می‌توان به «مولکول DNA چیست؟ - از صفر تا صد»، «ژن چیست؟ - به زبان ساده»، «الگوریتم ژنتیک – از صفر تا صد»، «میانگین متحرک چیست؟ + پیاده سازی Moving Average در پایتون» و «بررسی معیارهای ارزیابی رگرسیون در پایتون – پیاده سازی + کد» اشاره کرد.

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

الگوریتم ژنتیک (Genetic Algorithm یا GA) یک الگوریتم از خانواده الگوریتم‌های تکاملی (Evolutionary Algorithms یا EA) است. این الگوریتم با الهام گرفتن از روند تکامل ژن برای افزایش شانس زیستن موجودات طراحی شده است. ویژگی‌های فیزیکی موجودات توسط ماده ژنتیک که DNA (Deoxyribonucleic Acid) نام دارد تنظیم می‌شود. DNA شامل تعداد زیادی ژن (Gene) است که هرکدام کنترل یک فرآیند را بر عهده دارد. ژن‌ها در طول زمان در نتیجه انتخاب طبیعی (Natural Selection) تغییر یافته و بهینه می‌شوند.

برای مثال اگر ژن A مسئول تولید زهر برای یک گونه مار باشد، روشن بودن آن به نفع موجود خواهد بود، بنابراین در طول زمان مارهایی با ژن A خاموش، از چرخه رقابت حذف خواهند شد. در این مطلب قصد داریم الگوریتم ژنتیک را پیاده‌سازی کرده و از آن برای بیشینه‌سازی (Maximization) (که نوعی بهینه‌سازی (Optimization) است) یک تابع دلخواه استفاده کنیم. فرض کنید که تابعی به شکل زیر داریم که در ورودی یک بردار x به طول n دریافت کرده و در خروجی یک عدد برمی‌گرداند:

$$
f(x)=\sum_{i=1}^n e^{-x_i^2}=e^{-x_1{ }^2}+e^{-x_2{ }^2}+\cdots+e^{-x_n^2}
$$

می‌دانیم که این تابع از تعداد زیادی تابع گوسی تشکیل شده است. هر جزء مستقل از یکدیگر است و در نقطه x_i=0 به بیشترین مقدار ممکن خود می‌رسد. بنابراین اگر تمامی درایه‌های آرایه (Array) x برابر با 0 باشد، این تابع بیشینه خواهد بود و مقدار بیشینه برابر با n خواهد بود.

نمودار توزیع گوسی

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

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

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

1import numpy as np
2import typing as typ
3import matplotlib.pyplot as plt

این 3 کتابخانه به ترتیب برای موارد زیر استفاده خواهند شد:

  1. کتابخانه Numpy  به دلیل تسهیل کار با آرایه، ماتریس و تولید اعداد تصادفی، به عنوان کتابخانه اصلی پیاده‌سازی استفاده خواهد شد.
  2. ماژول Typing  برای تعریف جنس ورودی توابع کاربرد دارد. این مورد لزومی نیست اما در استفاده از آن خوانایی کد را بالا می‌برد.
  3. کتابخانه Matplotlib   برای رسم نمودار نتایج الگوریتم استفاده خواهد شد. مصورسازی (Visualization) نتایج الگوریتم، برای نمایش عملکرد آن و حتی دریافتن مشکلات آن الزامی است.

با توجه به اینکه از کلاس‌ها (Class) و برنامه‌نویسی شی‌گرا (Object Oriented Programming یا OOP) برای پیاده‌سازی الگوریتم استفاده خواهیم کرد، ممکن است در فرآیند انتقال کدها خطایی صورت گیرد، به همین دلیل کدهای نهایی از این لینک در دسترس است.

در اولین مرحله، دو تنظیمات زیر را اعمال می‌کنیم:

1np.random.seed(0)
2plt.style.use('ggplot')

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

پیاده‌سازی الگوریتم

برای پیاده‌سازی الگوریتم ژنتیک در پایتون، در اولین قدم، یک کلاس با نام GA ایجاد می‌کنیم:

1class GA:

پیاده‌سازی متد سازنده

برای کامل شدن این کلاس، به 8 متد (Method) نیاز داریم. به عنوان اولین متد، متد سازنده را ایجاد می‌کنیم که با نام __init__  می‌شناسیم. این متد در ورودی 6 عدد دریافت می‌کند که تنظیمات کار الگوریتم است:

1def __init__(self,
2MaxGeneration:int=100,
3PopulationSize:int=100,
4MatingFraction:float=0.1,
5MutationFraction:int=0.2,
6MutationProbability:float=0.1,
7MutationScale:float=0.04):

6 ورودی به ترتیب موارد زیر را تنظیم می‌کنند:

  1. ورودی MaxGeneration  بیشترین تعداد نسل‌ها را نشان می‌دهد. افزایش تعداد نسل‌ها، احتمال بهینه‌تر شدن بهترین عضو جمعیت را افزایش می‌دهد. افزایش MaxGeneration زمان اجرای الگوریتم و تعداد دفعات فراخوانی تابع هدف (Function Evaluation) را نیز افزایش می‌دهد. در طبیعت نیز با گذر زمان، در نسل‌های جدیدتر، کروموزوم‌های (Chromosome) برازنده‌تر ایجاد می‌شود. این ورودی به مقدار پیش‌فرض 100 نسل تنظیم شده است.
  2. ورودی PopulationSize  اندازه جمعیت را نشان می‌دهد. در هر مرحله از کار الگوریتم، تعداد مشخصی از بهترین کروموزوم‌ها انتخاب و به نسل بعد منتقل می‌شود. با توجه به روش پیاده‌سازی الگوریتم، با افزایش این عدد نیز زمان اجرای الگوریتم افزایش خواهد داشت. در طبیعت نیز به دلیل محدود بودن منابع (Resource)، ظرفیت ادامه حیات برای تعداد محدودی از موجودات یک گونه وجود دارد. این ورودی به مقدار پیش‌فرض 100 کروموزوم تنظیم شده است.
  3. ورودی MatingFraction  کسر (Fraction) مربوط به تعداد آمیزش (Mating) در هر نسل را نشان می‌دهد. این عدد بهتر است در بازه [0,1] باشد. برای مثال اگر این عدد برابر با 0.2 باشد و اندازه جمعیت 80 باشد، در هر نسل به تعداد 0.2×80=16 آمیزش صورت خواهد گرفت و 32 فرزند حاصل خواهد شد. بنابراین، افزایش این عدد باعث افزایش زمان اجرای الگوریتم ژنتیک در پایتون می‌شود. این ورودی به مقدار پیش‌فرض 0.1 تنظیم شده است.
  4. ورودی MutationFraction  مشابه ورودی قبل، تعداد جهش (Mutation) در هر نسل را تنظیم می‌کند. با افزایش این ورودی نیز زمان اجرای الگوریتم افزایش خواهد یافت. این ورودی به مقدار پیش‌فرض 0.2 تنظیم شده است.
  5. ورودی MutationProbability  احتمال جهش در ژن‌ها را تعیین می‌کند. برای مثال اگر مقدار این ورودی 0.5 تعیین شود و از جمعیت موجود، یک کروموزوم انتخاب شود و شامل 40 ژن باشد، هر ژن با احتمال 50% خواهد توانست جهش کند. کم بودن این ورودی باعث می‌شود الگوریتم نتواند به خوبی حول جواب‌های بهینه موجود تا آن نسل جستجو کند. زیاد بودن این ورودی باعث می‌شود احتمال بهبود برازندگی در کروموزوم جهش‌یافته کاهش یابد. به همین دلیل بهتر است مقدار آن در حد بهینه حفظ شود. مقدار این ورودی به مقدار پیش‌فرض 0.1 تنظیم شده است.
  6. ورودی MutationScale  حدود بزرگی (Scale) جهش را تعیین می‌کند. برای مثال اگر حدود ژن K بازه [-2,+6] باشد، در صورتی که MutationScale   برابر با 0.2 باشد، بیشترین بزرگی ممکن برای جهش آن ژن برابر خواهد بود با:

$$
0.2×(+6-(-2))=0.2×(+6+2)=0.2×8=1.6
$$

نصف این تغییرات برای افزایش و نصف دیگر آن برای کاهش خواهد بود. در این صورت میزان جهش برای ژن K در بازه [-0.8,+0.8] خواهد بود. برای جهش یک عدد از این بازه انتخاب و به مقدار قبلی ژن اضافه می‌شود. این ورودی باید در بازه [0,2] باشد، اما مقادیر نزدیک به صفر مناسب است.

مقادیر بالای این ورودی در نسل‌های ابتدایی ممکن است مناسب باشد اما در نسل‌های انتهای چندان مناسب نخواهد بود. مقدار این ورودی به مقدار پیش‌فرض 0.04 تنظیم شده است. پس از دریافت این مقادیر، آن‌ها را در شی (Object) که با نام self  می‌شناسیم ذخیره می‌کنیم. به این ترتیب شش Attribute به شی اضافه خواهد شد:

1        def __init__(self,
2                 MaxGeneration:int=100,
3                 PopulationSize:int=100,
4                 MatingFraction:float=0.1,
5                 MutationFraction:int=0.2,
6                 MutationProbability:float=0.1,
7                 MutationScale:float=0.04):
8        self.MaxGeneration = MaxGeneration
9        self.PopulationSize = PopulationSize
10        self.MatingFraction = MatingFraction
11        self.MutationFraction = MutationFraction
12        self.MutationProbability = MutationProbability
13        self.MutationScale = MutationScale

حال نیاز است دو عدد دیگر نیز محاسبه کنیم. در ابتدا باید عددی به نام MatingCount  را حساب کنیم. این عدد تعداد آمیزش در هر نسل را نشان خواهد داد. به این منظور باید اندازه جمعیت در کسر آمیزش ضرب شود:

1    def __init__(self,
2                 MaxGeneration:int=100,
3                 PopulationSize:int=100,
4                 MatingFraction:float=0.1,
5                 MutationFraction:int=0.2,
6                 MutationProbability:float=0.1,
7                 MutationScale:float=0.04):
8        self.MaxGeneration = MaxGeneration
9        self.PopulationSize = PopulationSize
10        self.MatingFraction = MatingFraction
11        self.MutationFraction = MutationFraction
12        self.MutationProbability = MutationProbability
13        self.MutationScale = MutationScale
14        self.MatingCount = round(PopulationSize * MatingFraction)

توجه داشته باشید که عدد حاصل از نوع اعشاری (Float) است، به همین دلیل از تابع Round   برای گرد کردن آن به نزدیک‌ترین عدد صحیح (Integer) استفاده می‌کنیم. این فرآیند را برای محاسبه تعداد جهش در هر نسل هم استفاده می‌کنیم:

1    def __init__(self,
2                 MaxGeneration:int=100,
3                 PopulationSize:int=100,
4                 MatingFraction:float=0.1,
5                 MutationFraction:int=0.2,
6                 MutationProbability:float=0.1,
7                 MutationScale:float=0.04):
8        self.MaxGeneration = MaxGeneration
9        self.PopulationSize = PopulationSize
10        self.MatingFraction = MatingFraction
11        self.MutationFraction = MutationFraction
12        self.MutationProbability = MutationProbability
13        self.MutationScale = MutationScale
14        self.MatingCount = round(PopulationSize * MatingFraction)
15        self.MutationCount = round(PopulationSize * MutationFraction)

نتایج الگوریتم ژنتیک در پایتون باید در طول آموزش ذخیره شود. به همین منظور یک دیکشنری (Dictionary) به شکل زیر ایجاد می‌کنیم تا در ادامه کار الگوریتم نتایج در آن ذخیره شود:

1    def __init__(self,
2                 MaxGeneration:int=100,
3                 PopulationSize:int=100,
4                 MatingFraction:float=0.1,
5                 MutationFraction:int=0.2,
6                 MutationProbability:float=0.1,
7                 MutationScale:float=0.04):
8        self.MaxGeneration = MaxGeneration
9        self.PopulationSize = PopulationSize
10        self.MatingFraction = MatingFraction
11        self.MutationFraction = MutationFraction
12        self.MutationProbability = MutationProbability
13        self.MutationScale = MutationScale
14        self.MatingCount = round(PopulationSize * MatingFraction)
15        self.MutationCount = round(PopulationSize * MutationFraction)
16        self.History = {'Best': [],
17                        'Best F': [],
18                        'Worst F': [],
19                        'Average F': [],
20                        'FEs': []}

لیست (List) مربوط به کلید Best  بهترین کروموزوم هر نسل را ذخیره خواهد کرد. بیشترین، کمترین و میانگین برازندگی کروموزوم‌های هر نسل نیز به ترتیب در لیست مربوط به کلید‌های Best F  ، Worst F   و Average F  ذخیره خواهد شد. به این ترتیب خواهیم توانست روند بهبود نتایج الگوریتم را در نهایت با یک نمودار نشان دهیم. لیست مربوط به کلید FEs نیز مقدار تابع برازندگی در هر بار فراخوانی آن را ذخیره خواهد کرد. به این ترتیب متد __init__   کامل می‌شود.

پیاده‌سازی متد محاسبه برازش

متد بعدی که باید پیاده‌سازی شود، مربوط به محاسبه تابع برازندگی است. این تابع با دریافت یک مجموعه از کروموزوم‌ها (جمعیت یا Population)، برازندگی هر کروموزوم را محاسبه و در خروجی برخواهد گرداند. یک متد با نام GetFitnessees  ایجاد می‌کنیم و در ورودی تابع، آرایه مربوط به جمعیت را دریافت می‌کنیم:

1    def GetFitnesses(self,
2                     Population:np.ndarray) -> np.ndarray:

حال به ازای هر کروموزوم در جمعیت، تابع برازندگی را فراخوانی می‌کنیم، خروجی را در یک لیست ذخیره و در نهایت با استفاده از تابع numpy.array  آن را به آرایه تبدیل می‌کنیم:

1    def GetFitnesses(self,
2                     Population:np.ndarray) -> np.ndarray:
3        Fitnesses = np.array([self.F(i) for i in Population])

توجه داشته باشید که برخی توابع، به جز متغیرهای تصمیم (Decision Variable)، ورودی‌های دیگری نیز دریافت می‌کنند، به همین دلیل یک Attribute به نام Args  نیز در شی ایجاد خواهیم کرد و در ورودی تابع وارد خواهیم کرد:

1    def GetFitnesses(self,
2                     Population:np.ndarray) -> np.ndarray:
3        Fitnesses = np.array([self.F(i, *self.Args) for i in Population])

به این ترتیب الگوریتم نوشته شده توانایی بهینه‌سازی توابع متنوعی را خواهد داشت. می‌توان یک Attribute به عنوان self.kwArgs  نیز اضافه کنیم که فعلاً از آن صرف نظر می‌کنیم. قبل از اینکه آرایه Fitnesses  در خروجی برگردانده شود، مقادیر آن را به لیست کلید FEs  در دیکشنری self.History  اضافه می‌کنیم:

1    def GetFitnesses(self,
2                     Population:np.ndarray) -> np.ndarray:
3        Fitnesses = np.array([self.F(i, *self.Args) for i in Population])
4        self.History['FEs'].extend(Fitnesses)

در نهایت آرایه برازندگی‌های محاسبه شده را به عنوان خروجی برمی‌گردانیم:

1    def GetFitnesses(self,
2                     Population:np.ndarray) -> np.ndarray:
3        Fitnesses = np.array([self.F(i, *self.Args) for i in Population])
4        self.History['FEs'].extend(Fitnesses)
5        return Fitnesses

به این ترتیب متد GetFitnesses   کامل می‌شود.

پیاده‌سازی متد مرتب‌سازی جمعیت

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

1    def Sort(self):
2        I = np.argsort(self.Fitnesses)

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

1    def Sort(self):
2        I = np.argsort(self.Fitnesses)
3        I = np.flip(I)

حال دو آرایه self.Population  و self.Fitnesses  را به کمک آرایه I  مرتب می‌کنیم:

1    def Sort(self):
2        I = np.argsort(self.Fitnesses)
3        I = np.flip(I)
4        self.Population = self.Population[I]
5        self.Fitnesses = self.Fitnesses[I]

به این ترتیب، هربار که کد self.Sort()  اجرا شود، آرایه self.Fitnesses  به صورت نزولی مرتب شده و آرایه self.Population  با توجه به ترتیب self.Fitnesses  مرتب می‌شود. به این ترتیب متد Sort  کامل می‌شود.

پیاده‌سازی متد تولید کروموزوم‌های جهش یافته

متدی نیاز داریم تا در صورت فراخوانی، با توجه به تعداد تعریف شده، از جمعیت موجود کروموزوم جهش‌یافته (Mutants) تولید کند. متدی با نام GetMutants  ایجاد می‌کنیم. این متد در ورودی چیز دریافت نمی‌کند ولی در خروجی آرایه مربوط به کروموزوم‌های جهش‌یافته را برمی‌گرداند:

1    def GetMutants(self) -> np.ndarray:

در تولید کروموزوم‌های جهش‌یافته، تمایل داریم تا بیشتر از کروموزوم‌های برازنده‌تر استفاده کنیم، زیر احتمال تولید کروموزوم‌های بهتر زیاد است. به این دلیل، احتمال انتخاب هر کروموزوم برای جهش دادن آن را، با توجه به میزان برازندگی آن تعیین می‌کنیم. اگر میزان برازندگی تمامی اعضای جمعیت، در آرایه F موجود باشد، ابتدا آن را به شکل زیر در بازه بین [0,1] مقیاس‌بندی (Scaling) می‌کنیم:

$$
F _ i ^ { ' } = \frac { F _ i - \min (F)}{ \max (F) - \min (F)}
$$

سپس برای توزیع احتمال بین هر عضو، از رابطه زیر استفاده می‌کنیم:

$$
P _ i ^ { ' } = \frac { F _ i ^ { ' } }{ \sum _ { j = 1 } ^ { n } F _ j ^ { ' } } = \frac { F _ i ^ { ' } }{ sum ( F ^ {'} ) }
$$

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

1    def GetMutants(self) -> np.ndarray:
2        p = (self.Fitnesses - self.Fitnesses.min()) / (self.Fitnesses.max() - self.Fitnesses.min())
3        p /= p.sum()

حال می‌توانیم با توجه به آرایه p و به کمک تابع numpy.random.choice  کروموزوم‌هایی که می‌خواهیم جهش دهیم را انتخاب کنیم:

1    def GetMutants(self) -> np.ndarray:
2        p = (self.Fitnesses - self.Fitnesses.min()) / (self.Fitnesses.max() - self.Fitnesses.min())
3        p /= p.sum()
4        I = np.random.choice(a=self.PopulationSize,
5                             size=self.MutationCount,
6                             p=p)

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

1    def GetMutants(self) -> np.ndarray:
2        if self.Fitnesses.var() > 1e-9:
3            p = (self.Fitnesses - self.Fitnesses.min()) / (self.Fitnesses.max() - self.Fitnesses.min())
4            p /= p.sum()
5            I = np.random.choice(a=self.PopulationSize,
6                                 size=self.MutationCount,
7                                 p=p)
8        else:
9            I = np.random.choice(a=self.PopulationSize,
10                                 size=self.MutationCount)

به این ترتیب کروموزوم‌های مورد نظر انتخاب می‌شود. توجه داشته باشید که ورودی a مربوط به تابع numpy.random.choice  می‌تواند یک آرایه باشد و از داخل آن موارد انتخاب شود. در صورتی که به جای آرایه، یک عدد صحیح وارد کنیم، اعدادی در بازه [0,a) انتخاب می‌شود.

در این مورد چون قصد داریم تعدادی کروموزوم از کل جمعیت انتخاب کنیم، مقدار a را برابر با self.PopulatinSize  قرار می‌دهیم. تعدد موارد انتخاب نیز با ورودی size تعیین می‌شود که به تعداد self.MutationCount  کروموزوم انتخاب می‌کنیم. حال کروموزوم‌های انتخاب شده را انتخاب و با اسم newP  می‌شناسیم:

1    def GetMutants(self) -> np.ndarray:
2        if self.Fitnesses.var() > 1e-9:
3            p = (self.Fitnesses - self.Fitnesses.min()) / (self.Fitnesses.max() - self.Fitnesses.min())
4            p /= p.sum()
5            I = np.random.choice(a=self.PopulationSize,
6                                 size=self.MutationCount,
7                                 p=p)
8        else:
9            I = np.random.choice(a=self.PopulationSize,
10                                 size=self.MutationCount)
11        newP = self.Population[I]

در این مرحله، آرایه newP  دارای self.MutationCount  عدد سطر (کروموزوم) و self.DimensionCount  عدد ستون (ژن) خواهد بود. تعداد ژن‌ها در فراخوانی متد Maximize تعیین خواهد شد. حال باید به ازای هر کروموزوم یک حلقه ایجاد کنیم:

1    def GetMutants(self) -> np.ndarray:
2        if self.Fitnesses.var() > 1e-9:
3            p = (self.Fitnesses - self.Fitnesses.min()) / (self.Fitnesses.max() - self.Fitnesses.min())
4            p /= p.sum()
5            I = np.random.choice(a=self.PopulationSize,
6                                 size=self.MutationCount,
7                                 p=p)
8        else:
9            I = np.random.choice(a=self.PopulationSize,
10                                 size=self.MutationCount)
11        newP = self.Population[I]
12        for i in range(self.MutationCount):

حال باید به ازای هر ژن نیز تصمیم‌گیری کنیم، به همین دلیل حلقه دیگری نیز ایجاد می‌کنیم:

1    def GetMutants(self) -> np.ndarray:
2        if self.Fitnesses.var() > 1e-9:
3            p = (self.Fitnesses - self.Fitnesses.min()) / (self.Fitnesses.max() - self.Fitnesses.min())
4            p /= p.sum()
5            I = np.random.choice(a=self.PopulationSize,
6                                 size=self.MutationCount,
7                                 p=p)
8        else:
9            I = np.random.choice(a=self.PopulationSize,
10                                 size=self.MutationCount)
11        newP = self.Population[I]
12        for i in range(self.MutationCount):
13            for j in range(self.DimensionCount):

حال یک عدد تصادفی در بازه [0,1] ایجاد می‌کنیم. در صورتی که این عدد بزرگ‌تر از self.MutationProbability  باشد، برای ژن j جهشی رخ نخواهد داد، در غیر این صورت یک جهش رخ خواهد داد:

1    def GetMutants(self) -> np.ndarray:
2        if self.Fitnesses.var() > 1e-9:
3            p = (self.Fitnesses - self.Fitnesses.min()) / (self.Fitnesses.max() - self.Fitnesses.min())
4            p /= p.sum()
5            I = np.random.choice(a=self.PopulationSize,
6                                 size=self.MutationCount,
7                                 p=p)
8        else:
9            I = np.random.choice(a=self.PopulationSize,
10                                 size=self.MutationCount)
11        newP = self.Population[I]
12        for i in range(self.MutationCount):
13            for j in range(self.DimensionCount):
14                if np.random.rand() < self.MutationProbability:

توجه داشته باشید که numpy.random.rand   یک عدد تصادفی در بازه بین 0 و 1 برمی‌گرداند. حال اگر شرط برقرار شد، ژن j از کروموزوم i را جهش می‌دهیم. مقدار جهش به صورت تصادفی در بازه Scaleهای محاسبه شده رخ خواهد داد:

1    def GetMutants(self) -> np.ndarray:
2        if self.Fitnesses.var() > 1e-9:
3            p = (self.Fitnesses - self.Fitnesses.min()) / (self.Fitnesses.max() - self.Fitnesses.min())
4            p /= p.sum()
5            I = np.random.choice(a=self.PopulationSize,
6                                 size=self.MutationCount,
7                                 p=p)
8        else:
9            I = np.random.choice(a=self.PopulationSize,
10                                 size=self.MutationCount)
11        newP = self.Population[I]
12        for i in range(self.MutationCount):
13            for j in range(self.DimensionCount):
14                if np.random.rand() < self.MutationProbability:
15                    newP[i, j] += np.random.uniform(low=-self.MutationScales[j],
16                                                    high=+self.MutationScales[j])

توجه داشته باشید که آرایه self.MutationScales  تعریف نشده است، و در متد Maximize  مقدار آن را تعریف خواهیم کرد. در این آرایه به ازای هر ژن بیشترین شدت از جهش ذخیره شده است.

پس از اتمام جهش‌های کروموزوم i باید بررسی کنیم تا ژنی از حد بالا (Upper Bound) و حد پایین (Lower Bound) خود خارج نشود. به این منظور چهار سطر کد نیاز داریم که در ابتدا Maskهایی برای تعیین ژن‌های خارج از بازه تولید کند و سپس موارد مشکل‌دار را اصلاح کند:

1    def GetMutants(self) -> np.ndarray:
2        if self.Fitnesses.var() > 1e-9:
3            p = (self.Fitnesses - self.Fitnesses.min()) / (self.Fitnesses.max() - self.Fitnesses.min())
4            p /= p.sum()
5            I = np.random.choice(a=self.PopulationSize,
6                                 size=self.MutationCount,
7                                 p=p)
8        else:
9            I = np.random.choice(a=self.PopulationSize,
10                                 size=self.MutationCount)
11        newP = self.Population[I]
12        for i in range(self.MutationCount):
13            for j in range(self.DimensionCount):
14                if np.random.rand() < self.MutationProbability:
15                    newP[i, j] += np.random.uniform(low=-self.MutationScales[j],
16                                                    high=+self.MutationScales[j])
17            Mask1 = newP[i] > self.UB
18            Mask2 = newP[i] < self.LB
19            newP[i, Mask1] = self.UB[Mask1]
20            newP[i, Mask2] = self.LB[Mask2]

دو آرایه Mask1  و Mask2  طولی برابر با newP[i]  خواهند داشت و مقادیر آن‌ها True و یا False خواهد بود. در نهایت در دو سطر آخر، ژن‌هایی که از حد بالا گذشته‌اند را به حد بالای خود و ژن‌هایی که از حد پایین خود گذشته‌اند را به حد پایین خود منتقل می‌کنیم. توجه داشته باشید که دو آرایه self.LB  و self.UB  به ترتیب حد پایین و بالای ژن‌ها را تعیین می‌کند که در متد Maximize  به عنوان ورودی‌های مسئله دریافت خواهیم کرد.
در انتهای این تابع، آرایه newP  را برمی‌گردانیم:

1    def GetMutants(self) -> np.ndarray:
2        if self.Fitnesses.var() > 1e-9:
3            p = (self.Fitnesses - self.Fitnesses.min()) / (self.Fitnesses.max() - self.Fitnesses.min())
4            p /= p.sum()
5            I = np.random.choice(a=self.PopulationSize,
6                                 size=self.MutationCount,
7                                 p=p)
8        else:
9            I = np.random.choice(a=self.PopulationSize,
10                                 size=self.MutationCount)
11        newP = self.Population[I]
12        for i in range(self.MutationCount):
13            for j in range(self.DimensionCount):
14                if np.random.rand() < self.MutationProbability:
15                    newP[i, j] += np.random.uniform(low=-self.MutationScales[j],
16                                                    high=+self.MutationScales[j])
17            Mask1 = newP[i] > self.UB
18            Mask2 = newP[i] < self.LB
19            newP[i, Mask1] = self.UB[Mask1]
20            newP[i, Mask2] = self.LB[Mask2]
21        return newP

به این ترتیب پیاده‌سازی متد GetMutants  به اتمام می‌رسد.

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

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

1    def GetChilds(self) -> np.ndarray:

حال مشابه قبل، با توجه به برازندگی هر کروموزوم، والدین را انتخاب می‌کنیم:

1    def GetChilds(self) -> np.ndarray:
2        if self.Fitnesses.var() > 1e-9:
3            p = (self.Fitnesses - self.Fitnesses.min()) / (self.Fitnesses.max() - self.Fitnesses.min())
4            p /= p.sum()
5            I = np.random.choice(a=self.PopulationSize,
6                                 size=2 * self.MatingCount,
7                                 p=p)
8        else:
9            I = np.random.choice(a=self.PopulationSize,
10                                 size=2 * self.MatingCount)

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

1    def GetChilds(self) -> np.ndarray:
2        if self.Fitnesses.var() > 1e-9:
3            p = (self.Fitnesses - self.Fitnesses.min()) / (self.Fitnesses.max() - self.Fitnesses.min())
4            p /= p.sum()
5            I = np.random.choice(a=self.PopulationSize,
6                                 size=2 * self.MatingCount,
7                                 p=p)
8        else:
9            I = np.random.choice(a=self.PopulationSize,
10                                 size=2 * self.MatingCount)
11        I1s = I[:self.MatingCount]
12        I2s = I[self.MatingCount:]

به این ترتیب I1s  شماره مربوط به کروموزوم‌های والد اول و I2s  شماره مربوط به کروموزوم‌های والد دوم را نشان خواهد داد. حال برای ذخیره فرزندان، دو آرایه خالی ایجاد می‌کنیم:

1    def GetChilds(self) -> np.ndarray:
2        if self.Fitnesses.var() > 1e-9:
3            p = (self.Fitnesses - self.Fitnesses.min()) / (self.Fitnesses.max() - self.Fitnesses.min())
4            p /= p.sum()
5            I = np.random.choice(a=self.PopulationSize,
6                                 size=2 * self.MatingCount,
7                                 p=p)
8        else:
9            I = np.random.choice(a=self.PopulationSize,
10                                 size=2 * self.MatingCount)
11        I1s = I[:self.MatingCount]
12        I2s = I[self.MatingCount:]
13        newP1 = np.zeros((self.MatingCount, self.DimensionCount))
14        newP2 = np.zeros((self.MatingCount, self.DimensionCount))

توجه داشته باشید که به تعداد دو برابر آمیزش‌ها فرزند و self.DimensionCount  ژن داریم. حال برای هر آمیزش یک حلقه ایجاد می‌کنیم:

1    def GetChilds(self) -> np.ndarray:
2        if self.Fitnesses.var() > 1e-9:
3            p = (self.Fitnesses - self.Fitnesses.min()) / (self.Fitnesses.max() - self.Fitnesses.min())
4            p /= p.sum()
5            I = np.random.choice(a=self.PopulationSize,
6                                 size=2 * self.MatingCount,
7                                 p=p)
8        else:
9            I = np.random.choice(a=self.PopulationSize,
10                                 size=2 * self.MatingCount)
11        I1s = I[:self.MatingCount]
12        I2s = I[self.MatingCount:]
13        newP1 = np.zeros((self.MatingCount, self.DimensionCount))
14        newP2 = np.zeros((self.MatingCount, self.DimensionCount))
15        for i, (i1, i2) in enumerate(zip(I1s, I2s)):

این حلقه، با i شماره آمیزش، با i1  شماره کروموزوم والد اول و با i2  شماره کروموزوم وارد دوم را تعیین خواهد کرد. حال به ازای هر ژن حلقه دیگری ایجاد می‌کنیم:

1    def GetChilds(self) -> np.ndarray:
2        if self.Fitnesses.var() > 1e-9:
3            p = (self.Fitnesses - self.Fitnesses.min()) / (self.Fitnesses.max() - self.Fitnesses.min())
4            p /= p.sum()
5            I = np.random.choice(a=self.PopulationSize,
6                                 size=2 * self.MatingCount,
7                                 p=p)
8        else:
9            I = np.random.choice(a=self.PopulationSize,
10                                 size=2 * self.MatingCount)
11        I1s = I[:self.MatingCount]
12        I2s = I[self.MatingCount:]
13        newP1 = np.zeros((self.MatingCount, self.DimensionCount))
14        newP2 = np.zeros((self.MatingCount, self.DimensionCount))
15        for i, (i1, i2) in enumerate(zip(I1s, I2s)):
16            for j in range(self.DimensionCount):

در این نقطه باید کراسینگ اور (Crossing Over) را پیاده‌سازی می‌کنیم. روش‌های متنوعی برای انجام کراسینگ اور وجود دارد که در این حالت روش Uniform را استفاده خواهیم کرد.

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

در این حالت برای هر ژن مستقل از سایرین تصمیم می‌گیریم. یک عدد تصادفی در بازه [0,1] ایجاد می‌کنیم. در صورتی که عدد حاصل کمتر از 0.5 باشد، فرزند اول آمیزش i ژن شماره j را از والد اول دریافت خواهد کرد. در صورتی که عکس این حالت رخ دهد، ژن j فرزند اول آمیزش i از والد دوم دریافت خواهد شد:

1    def GetChilds(self) -> np.ndarray:
2        if self.Fitnesses.var() > 1e-9:
3            p = (self.Fitnesses - self.Fitnesses.min()) / (self.Fitnesses.max() - self.Fitnesses.min())
4            p /= p.sum()
5            I = np.random.choice(a=self.PopulationSize,
6                                 size=2 * self.MatingCount,
7                                 p=p)
8        else:
9            I = np.random.choice(a=self.PopulationSize,
10                                 size=2 * self.MatingCount)
11        I1s = I[:self.MatingCount]
12        I2s = I[self.MatingCount:]
13        newP1 = np.zeros((self.MatingCount, self.DimensionCount))
14        newP2 = np.zeros((self.MatingCount, self.DimensionCount))
15        for i, (i1, i2) in enumerate(zip(I1s, I2s)):
16            for j in range(self.DimensionCount):
17                if np.random.rand() < 0.5:
18                    newP1[i, j] = self.Population[i1, j]
19                    newP2[i, j] = self.Population[i2, j]
20                else:
21                    newP1[i, j] = self.Population[i2, j]
22                    newP2[i, j] = self.Population[i1, j]

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

1    def GetChilds(self) -> np.ndarray:
2        if self.Fitnesses.var() > 1e-9:
3            p = (self.Fitnesses - self.Fitnesses.min()) / (self.Fitnesses.max() - self.Fitnesses.min())
4            p /= p.sum()
5            I = np.random.choice(a=self.PopulationSize,
6                                 size=2 * self.MatingCount,
7                                 p=p)
8        else:
9            I = np.random.choice(a=self.PopulationSize,
10                                 size=2 * self.MatingCount)
11        I1s = I[:self.MatingCount]
12        I2s = I[self.MatingCount:]
13        newP1 = np.zeros((self.MatingCount, self.DimensionCount))
14        newP2 = np.zeros((self.MatingCount, self.DimensionCount))
15        for i, (i1, i2) in enumerate(zip(I1s, I2s)):
16            for j in range(self.DimensionCount):
17                if np.random.rand() < 0.5:
18                    newP1[i, j] = self.Population[i1, j]
19                    newP2[i, j] = self.Population[i2, j]
20                else:
21                    newP1[i, j] = self.Population[i2, j]
22                    newP2[i, j] = self.Population[i1, j]
23        newP = np.vstack((newP1, newP2))
24        return newP

به این ترتیب متد GetChilds  کامل می‌شود.

پیاده‌سازی متد افزودن جمعیت

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

1    def Append(self,
2               Ps:list):

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

1    def Append(self,
2               Ps:list):
3        Fs = [self.GetFitnesses(i) for i in Ps]

حال نیاز داریم تا جمعیت‌های موجود را به انتهای جمعیت قبلی اضافه و به عنوان self.Population  ذخیره کنیم:

1    def Append(self,
2               Ps:list):
3        Fs = [self.GetFitnesses(i) for i in Ps]
4        self.Population = np.vstack([self.Population] + Ps)

در نهایت نیاز است تا برازندگی جمعیت‌های جدید را نیز به انتهای آرایه self.Fitnesses  اضافه کرده و آن را به‌روزرسانی کنیم:

1    def Append(self,
2               Ps:list):
3        Fs = [self.GetFitnesses(i) for i in Ps]
4        self.Population = np.vstack([self.Population] + Ps)
5        self.Fitnesses = np.hstack([self.Fitnesses] + Fs)

به این ترتیب متد Append  کامل می‌شود.

پیاده‌سازی متد اصلاح اندازه جمعیت

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

1    def Cut(self):
2        self.Population = self.Population[:self.PopulationSize]
3        self.Fitnesses = self.Fitnesses[:self.PopulationSize]

توجه داشته باشید که باید قبل از فراخوانی این متد، متد Sort  فراخوانی شود تا کروموزوم‌ها به ترتیب نزولی مرتب شوند. به این ترتیب متد Cut کامل می‌شود و در صورتی که به شکل self.Cut()  فراخوانی شود، اندازه جمعیت را اصلاح خواهد کرد.

پیاده‌سازی متد بیشینه‌سازی

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

1    def Maximize(self,
2                 F:typ.Callable,
3                 LB:np.ndarray,
4                 UB:np.ndarray,
5                 Args:tuple=()) -> dict:

در ابتدای متد، موارد ورودی را ذخیره می‌کنیم:

1    def Maximize(self,
2                 F:typ.Callable,
3                 LB:np.ndarray,
4                 UB:np.ndarray,
5                 Args:tuple=()) -> dict:
6        self.F = F
7        self.LB = LB
8        self.UB = UB
9        self.Args = Args

حال تعداد متغیرهای تصمیم، یا به عبارتی تعداد ژن‌ها را محاسبه می‌کنیم:

1    def Maximize(self,
2                 F:typ.Callable,
3                 LB:np.ndarray,
4                 UB:np.ndarray,
5                 Args:tuple=()) -> dict:
6        self.F = F
7        self.LB = LB
8        self.UB = UB
9        self.Args = Args
10        self.DimensionCount = LB.size

همانطور که در پیاده‌سازی‌ها دیدیم، این عدد در عملیات سایر متدها استفاده می‌شود. حال نیاز داریم تا بیشترین بزرگی جهش برای هر ژن را محاسبه کنیم. به این منظور رابطه زیر را تعریف می‌کنیم:

$$
S _ i = S _ 0 \times \frac { U B _ i - L B _ i }{ 2 }
$$

در این رابطه، i شماره ژن، $$ S _ 0 $$ ورودی MutationScale  الگوریتم و LB  و UB  به ترتیب حد پایین و حد بالای متغیرهای تصمیم است. در متد GetMutants   اعداد تصادفی در بازه $$ [-S _ i , + S _ i] $$ انتخاب شدند، به همین دلیل به مخرج رابطه فوق عدد 2 اضافه شده است. حال نیاز داریم تا یک جمعیت اولیه ایجاد کنیم. به این منظور از numpy.random.uniform  استفاده می‌کنیم:

1    def Maximize(self,
2                 F:typ.Callable,
3                 LB:np.ndarray,
4                 UB:np.ndarray,
5                 Args:tuple=()) -> dict:
6        self.F = F
7        self.LB = LB
8        self.UB = UB
9        self.Args = Args
10        self.DimensionCount = LB.size
11        self.MutationScales = self.MutationScale * (self.UB - self.LB) / 2
12        self.Population = np.random.uniform(low=self.LB,
13                                            high=self.UB,
14                                            size=(self.PopulationSize,
15                                                  self.DimensionCount))

حال برای جمعیت ایجاد شده، مقادیر برازندگی را محاسبه و به عنوان self.Fitnesses  ذخیره می‌کنیم:

1    def Maximize(self,
2                 F:typ.Callable,
3                 LB:np.ndarray,
4                 UB:np.ndarray,
5                 Args:tuple=()) -> dict:
6        self.F = F
7        self.LB = LB
8        self.UB = UB
9        self.Args = Args
10        self.DimensionCount = LB.size
11        self.MutationScales = self.MutationScale * (self.UB - self.LB) / 2
12        self.Population = np.random.uniform(low=self.LB,
13                                            high=self.UB,
14                                            size=(self.PopulationSize,
15                                                  self.DimensionCount))
16        self.Fitnesses = self.GetFitnesses(self.Population)

به این ترتیب self.Population  و self.Fitnesses  مقداردهی اولیه (Initialization) می‌شوند. حال جمعیت را به صورت نزولی مرتب می‌کنیم:

1    def Maximize(self,
2                 F:typ.Callable,
3                 LB:np.ndarray,
4                 UB:np.ndarray,
5                 Args:tuple=()) -> dict:
6        self.F = F
7        self.LB = LB
8        self.UB = UB
9        self.Args = Args
10        self.DimensionCount = LB.size
11        self.MutationScales = self.MutationScale * (self.UB - self.LB) / 2
12        self.Population = np.random.uniform(low=self.LB,
13                                            high=self.UB,
14                                            size=(self.PopulationSize,
15                                                  self.DimensionCount))
16        self.Fitnesses = self.GetFitnesses(self.Population)
17        self.Sort()

به این ترتیب مرحله 0 به اتمام رسیده است. نتایج این مرحله را ذخیره و در خروجی بیشترین برازندگی حاصل تا آن مرحله را نمایش می‌دهیم:

1    def Maximize(self,
2                 F:typ.Callable,
3                 LB:np.ndarray,
4                 UB:np.ndarray,
5                 Args:tuple=()) -> dict:
6        self.F = F
7        self.LB = LB
8        self.UB = UB
9        self.Args = Args
10        self.DimensionCount = LB.size
11        self.MutationScales = self.MutationScale * (self.UB - self.LB) / 2
12        self.Population = np.random.uniform(low=self.LB,
13                                            high=self.UB,
14                                            size=(self.PopulationSize,
15                                                  self.DimensionCount))
16        self.Fitnesses = self.GetFitnesses(self.Population)
17        self.Sort()
18        self.History['Best'].append(self.Population[0])
19        self.History['Best F'].append(self.Fitnesses[0])
20        self.History['Worst F'].append(self.Fitnesses[-1])
21        self.History['Average F'].append(self.Fitnesses.mean())
22        print('Generation 0 Best: {:.2f}'.format(self.Fitnesses[0]))

توجه داشته باشید که پس از مرتب‌سازی، اولین عضو self.Population  بهترین جواب حاصل تا آن مرحله، اولین عضو self.Fitnesses  بیشترین برازندگی حاصل تا آن مرحله و آخرین عضو آن کمترین برازندگی موجد در آن مرحله است. به عنوان معیاری از کل جمعیت نیز میانگین برازندگی جمعیت به عنوان Average F  در نظر گرفته شده است. با توجه به اینکه self.Fitnesses  یک آرایه Numpy  است، می‌توانیم از متد mean  برای محاسبه میانگین آرایه استفاده کرد. پس از اتمام مرحله مقداردهی اولیه، یک حلقه به طول self.MaxGeneration  ایجاد می‌کنیم:

1    def Maximize(self,
2                 F:typ.Callable,
3                 LB:np.ndarray,
4                 UB:np.ndarray,
5                 Args:tuple=()) -> dict:
6        self.F = F
7        self.LB = LB
8        self.UB = UB
9        self.Args = Args
10        self.DimensionCount = LB.size
11        self.MutationScales = self.MutationScale * (self.UB - self.LB) / 2
12        self.Population = np.random.uniform(low=self.LB,
13                                            high=self.UB,
14                                            size=(self.PopulationSize,
15                                                  self.DimensionCount))
16        self.Fitnesses = self.GetFitnesses(self.Population)
17        self.Sort()
18        self.History['Best'].append(self.Population[0])
19        self.History['Best F'].append(self.Fitnesses[0])
20        self.History['Worst F'].append(self.Fitnesses[-1])
21        self.History['Average F'].append(self.Fitnesses.mean())
22        print('Generation 0 Best: {:.2f}'.format(self.Fitnesses[0]))
23        for i in range(self.MaxGeneration):

داخل حلقه، به ترتیب جمعیت جهش‌یافته‌ها و جمعیت فرزندان را ایجاد می‌کنیم:

1    def Maximize(self,
2                 F:typ.Callable,
3                 LB:np.ndarray,
4                 UB:np.ndarray,
5                 Args:tuple=()) -> dict:
6        self.F = F
7        self.LB = LB
8        self.UB = UB
9        self.Args = Args
10        self.DimensionCount = LB.size
11        self.MutationScales = self.MutationScale * (self.UB - self.LB) / 2
12        self.Population = np.random.uniform(low=self.LB,
13                                            high=self.UB,
14                                            size=(self.PopulationSize,
15                                                  self.DimensionCount))
16        self.Fitnesses = self.GetFitnesses(self.Population)
17        self.Sort()
18        self.History['Best'].append(self.Population[0])
19        self.History['Best F'].append(self.Fitnesses[0])
20        self.History['Worst F'].append(self.Fitnesses[-1])
21        self.History['Average F'].append(self.Fitnesses.mean())
22        print('Generation 0 Best: {:.2f}'.format(self.Fitnesses[0]))
23        for i in range(self.MaxGeneration):
24            M = self.GetMutants()
25            C = self.GetChilds()

حال جمعیت‌های جدید را به جمعیت موجود اضافه می‌کنیم:

1    def Maximize(self,
2                 F:typ.Callable,
3                 LB:np.ndarray,
4                 UB:np.ndarray,
5                 Args:tuple=()) -> dict:
6        self.F = F
7        self.LB = LB
8        self.UB = UB
9        self.Args = Args
10        self.DimensionCount = LB.size
11        self.MutationScales = self.MutationScale * (self.UB - self.LB) / 2
12        self.Population = np.random.uniform(low=self.LB,
13                                            high=self.UB,
14                                            size=(self.PopulationSize,
15                                                  self.DimensionCount))
16        self.Fitnesses = self.GetFitnesses(self.Population)
17        self.Sort()
18        self.History['Best'].append(self.Population[0])
19        self.History['Best F'].append(self.Fitnesses[0])
20        self.History['Worst F'].append(self.Fitnesses[-1])
21        self.History['Average F'].append(self.Fitnesses.mean())
22        print('Generation 0 Best: {:.2f}'.format(self.Fitnesses[0]))
23        for i in range(self.MaxGeneration):
24            M = self.GetMutants()
25            C = self.GetChilds()
26            self.Append([M, C])

حال نیاز داریم تا جمعیت را براساس برازندگی مرتب کرده و اندازه آن را اصلاح کنیم:

1    def Maximize(self,
2                 F:typ.Callable,
3                 LB:np.ndarray,
4                 UB:np.ndarray,
5                 Args:tuple=()) -> dict:
6        self.F = F
7        self.LB = LB
8        self.UB = UB
9        self.Args = Args
10        self.DimensionCount = LB.size
11        self.MutationScales = self.MutationScale * (self.UB - self.LB) / 2
12        self.Population = np.random.uniform(low=self.LB,
13                                            high=self.UB,
14                                            size=(self.PopulationSize,
15                                                  self.DimensionCount))
16        self.Fitnesses = self.GetFitnesses(self.Population)
17        self.Sort()
18        self.History['Best'].append(self.Population[0])
19        self.History['Best F'].append(self.Fitnesses[0])
20        self.History['Worst F'].append(self.Fitnesses[-1])
21        self.History['Average F'].append(self.Fitnesses.mean())
22        print('Generation 0 Best: {:.2f}'.format(self.Fitnesses[0]))
23        for i in range(self.MaxGeneration):
24            M = self.GetMutants()
25            C = self.GetChilds()
26            self.Append([M, C])
27            self.Sort()
28            self.Cut()

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

1    def Maximize(self,
2                 F:typ.Callable,
3                 LB:np.ndarray,
4                 UB:np.ndarray,
5                 Args:tuple=()) -> dict:
6        self.F = F
7        self.LB = LB
8        self.UB = UB
9        self.Args = Args
10        self.DimensionCount = LB.size
11        self.MutationScales = self.MutationScale * (self.UB - self.LB) / 2
12        self.Population = np.random.uniform(low=self.LB,
13                                            high=self.UB,
14                                            size=(self.PopulationSize,
15                                                  self.DimensionCount))
16        self.Fitnesses = self.GetFitnesses(self.Population)
17        self.Sort()
18        self.History['Best'].append(self.Population[0])
19        self.History['Best F'].append(self.Fitnesses[0])
20        self.History['Worst F'].append(self.Fitnesses[-1])
21        self.History['Average F'].append(self.Fitnesses.mean())
22        print('Generation 0 Best: {:.2f}'.format(self.Fitnesses[0]))
23        for i in range(self.MaxGeneration):
24            M = self.GetMutants()
25            C = self.GetChilds()
26            self.Append([M, C])
27            self.Sort()
28            self.Cut()
29            self.History['Best'].append(self.Population[0])
30            self.History['Best F'].append(self.Fitnesses[0])
31            self.History['Worst F'].append(self.Fitnesses[-1])
32            self.History['Average F'].append(self.Fitnesses.mean())
33            print('Generation {} Best: {:.2f}'.format(i + 1, self.Fitnesses[0]))

به این ترتیب روند کار الگوریتم ژنتیک در پایتون کامل خواهد بود. در انتهای متد، لیست‌های موجود در دیکشنری self.History  را به آرایه Numpy  تبدیل می‌کنیم و در نهایت آن را برمی‌گردانیم:

1    def Maximize(self,
2                 F:typ.Callable,
3                 LB:np.ndarray,
4                 UB:np.ndarray,
5                 Args:tuple=()) -> dict:
6        self.F = F
7        self.LB = LB
8        self.UB = UB
9        self.Args = Args
10        self.DimensionCount = LB.size
11        self.MutationScales = self.MutationScale * (self.UB - self.LB) / 2
12        self.Population = np.random.uniform(low=self.LB,
13                                            high=self.UB,
14                                            size=(self.PopulationSize,
15                                                  self.DimensionCount))
16        self.Fitnesses = self.GetFitnesses(self.Population)
17        self.Sort()
18        self.History['Best'].append(self.Population[0])
19        self.History['Best F'].append(self.Fitnesses[0])
20        self.History['Worst F'].append(self.Fitnesses[-1])
21        self.History['Average F'].append(self.Fitnesses.mean())
22        print('Generation 0 Best: {:.2f}'.format(self.Fitnesses[0]))
23        for i in range(self.MaxGeneration):
24            M = self.GetMutants()
25            C = self.GetChilds()
26            self.Append([M, C])
27            self.Sort()
28            self.Cut()
29            self.History['Best'].append(self.Population[0])
30            self.History['Best F'].append(self.Fitnesses[0])
31            self.History['Worst F'].append(self.Fitnesses[-1])
32            self.History['Average F'].append(self.Fitnesses.mean())
33            print('Generation {} Best: {:.2f}'.format(i + 1, self.Fitnesses[0]))
34        for k, v in self.History.items():
35            self.History[k] = np.array(v)
36        return self.History

به این ترتیب متد Maximize  نیز کامل می‌شود و الگوریتم آماده استفاده است.

تعریف تابع هدف

در ابتدای مطلب یک تابع هدف تعریف شد. تابع گفته شده را به شکل زیر تعریف می‌کنیم:

1def F(x:np.ndarray) -> float:
2    y = (np.exp(-np.power(x, 2))).sum()
3    return y

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

$$
f ( x ) = \sum _ {} ^ {} e ^ { - x _ i ^ 2 } = e ^ { - x _ 1 ^ 2 } + e ^ { - x _ 2 ^ 2 } + ... + e ^ { - x _ n ^ 2 }
$$ٰ

تعریف حد بالا و پایین

حال حد بالا و پایین متغیرهای تصمیم را تعیین می‌کنیم:

1LB = -2 * np.ones(10)
2UB = +2 * np.ones(10)

توجه داشته باشید که برای بررسی عملکرد، 10 متغیر تصمیم در نظر گرفته‌ایم. ابعاد دو آرایه فوق، نشان‌دهنده ابعاد فضای جستجو و تعداد متغیرهای تصمیم است.

ایجاد الگوریتم و بهینه‌سازی تابع هدف

حال الگوریتم را ایجاد می‌کنیم:

1Algorithm = GA()

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

1History = Algorithm.Maximize(F, LB, UB)

با اجرای کد فوق، الگوریتم شروع به کار کرده و در نهایت گزارش مراحل را در دیکشنری History  برخواهدگرداند.

پس از اجرای کد، نتایج زیر نشان داده خواهد شد:

1Generation 0 Best: 8.26
2Generation 1 Best: 8.26
3...
4...
5Generation 99 Best: 10.00
6Generation 100 Best: 10.00

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

رسم نمودارهای نتایج

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

1plt.plot(History['FEs'],
2         ls='-',
3         lw=0.8,
4         c='crimson',
5         label='Function Evaluations')
6plt.title('Function Value Over Evaluations')
7plt.xlabel('Function Evaluation')
8plt.ylabel('Value')
9plt.show()

با اجرای کد فوق، نمودار زیر حاصل می‌شود:

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

با توجه به نمودار می‌توان گفت که مقادیر تابع هر در کمترین مقدار از 2.2 شروع شده است. با توجه به روند بهبود می‌توان گفت که اجزای الگوریتم ژنتیک در پایتون به درستی کار خود را انجام داده‌اند. آخرین داده در $$ x=4200 $$ قرار داده که به معنی 4200 بار فراخوانی تابع هدف است. پس از فراخوانی 2800، بهبود چندان بزرگی رخ نداده است، بنابراین می‌توان با صرف نظر از اندکی امتیاز، زمان اجرای کد را کاهش داد. جالب توجه است که کد بهینه‌سازی، در زمانی حدود 200 میلی‌ثانیه کار خود را به اتمام رسانده است.

برای بررسی این زمان، می‌توان از تابع time  موجود در کتابخانه time  استفاده کرد. به عنوان نمودار دوم، سه خط مربوط به بیشترین برازندگی، کمترین برازندگی و میانگین برازندگی در طول نسل‌ها را رسم می‌کنیم:

1plt.plot(History['Best F'],
2         ls='--',
3         lw=1.1,
4         c='teal',
5         label='Best')
6plt.plot(History['Average F'],
7         ls='-',
8         lw=0.9,
9         c='k',
10         label='Average')
11plt.plot(History['Worst F'],
12         ls='--',
13         lw=1.1,
14         c='crimson',
15         label='Worst')
16plt.title('Best Function Value Over Generations')
17plt.xlabel('Generation')
18plt.ylabel('Value')
19plt.legend()
20plt.show()

کد فوق، نمودار زیر را ایجاد می‌کند:

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

این نمودار به جهت نمایش بهترین، بدترین و میانگین جمعیت، حائز اهمیت است.

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

نمودار مربوط به فراخوانی‌های تابع هدف، به دلیل تعداد داده‌های زیاد، نوسانات شدید دارد و این اتفاق باعث می‌شوند تا روند کلی دیده نشود. به همین دلیل قصد داریم یک میانگین متحرک ساده (Simple Moving Average یا SMA) بر روی آن اعمال کنیم. برای آشنایی بیشتر با میانگین‌های متحرک می‌توانید به مطلب «میانگین متحرک چیست؟ + پیاده سازی Moving Average در پایتون» مراجعه نمایید. به این منظور تابعی به شکل زیر برای محاسبه میانگین متحرک ساده ایجاد می‌کنیم:

1def SMA(S:np.ndarray,
2        L:int) -> np.ndarray:
3    nD0 = S.size # Getting Input Series Size
4    nD = nD0 - L + 1 # Calculating Output Series Size
5    M = np.zeros(nD) # Creating Placeholder Array
6    for i in range(nD): # For Each Output Data
7        M[i] = S[i:i + L].mean() # Mean Over Window
8    return M

از این تابع برای محاسبه میانگین متحرک ساده آرایه History[‘FEs’]  استفاده می‌کنیم و سپس نمودار آن را رسم می‌کنیم:

1smaFEs = SMA(History['FEs'], 100)

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

1T1 = np.arange(start=0,
2               stop=History['FEs'].size,
3               step=1)
4T2 = T1[-smaFEs.size:]
5
6plt.plot(T1,
7         History['FEs'],
8         ls='-',
9         lw=0.8,
10         c='crimson',
11         label='Function Evaluations')
12plt.plot(T2,
13         smaFEs,
14         ls='-',
15         lw=1.3,
16         c='k',
17         label='SMA(100)')
18plt.title('Function Value Over Evaluations + SMA(100)')
19plt.xlabel('Function Evaluation')
20plt.ylabel('Value')
21plt.show()

کد فوق پس از اجرا، نمودار زیر را نمایش خواهد داد.

نمودار میانگین 100 نقطه اخیر الگوریتم ژنتیک در پایتون

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

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

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

1BestSolution = History['Best'][-1]

اگر این جواب را نمایش دهیم، خواهیم داشت:

1[+0.0078, -0.0087, -0.0095, +0.0058, -0.0128, +0.0034, +0.0061, -0.0201, +0.0074, +0.0086]

به این ترتیب مشاهده می‌کنیم که اغلب موارد تا 2 رقم اعشار به 0 نزدیک شده‌اند. می‌توانیم در طول نسل‌ها، فاصله بهترین جواب از جواب صحیح را محاسبه و به شکل نمودار نمایش دهیم. به این منظور ابتدا جواب بهینه را از تک تک بهترین جواب‌های هر نسل کم می‌کنیم:

1Bests = History['Best']
2
3D = Bests - np.zeros(10)

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

1Bests = History['Best']
2
3D = Bests - np.zeros(10)
4
5D2 = D ** 2
6
7SD2 = np.sum(D2, axis=1)

در نهایت باید جذر مقادیر را حساب کنیم تا فواصل اقلیدسی به دست آید:

1Bests = History['Best']
2
3D = Bests - np.zeros(10)
4
5D2 = D ** 2
6
7SD2 = np.sum(D2, axis=1)
8
9Distances = np.sqrt(SD2)

حال می‌توانیم نمودار این فواصل را نیز رسم کنیم:

1plt.plot(Distances,
2         ls='-',
3         lw=0.8,
4         c='crimson',
5         label='Distance')
6plt.title('Generation\'s Best Solution Distance From Target Solution')
7plt.xlabel('Generation')
8plt.ylabel('Distance')
9plt.show()

با اجرای کد، نمودار زیر نمایش داده می‌شود.

نمودار فواصل اقلیدسی

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

نمودار لگاریتمی فواصل اقلیدسی

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

افزایش تعداد متغیرهای تصمیم الگوریتم ژنتیک در پایتون

اگر تعداد متغیرهای تصمیم را از 10 به 100 افزایش دهیم، نمودار فراخوانی تابع هدف به شکل زیر درمی‌آید.

خروجی اجرای الگوریتم ژنتیک در پایتون با متغیرهای تصمیم بیشتر

می‌توان مشاهده کرد که الگوریتم با 4200 بار فراخوانی تابع هدف، توانسته به خوبی به عدد 82 برسد. توجه داشته باشید که در این شرایط بیشترین مقدار ممکن برای تابع هدف برابر با 100 است. زمان اجرای الگوریتم برای این شرایط، حدود 1100 میلی‌ثانیه است.

چگونه یک مدل رگرسیون خطی را با استفاده از الگوریتم ژنتیک در پایتون آموزش دهیم ؟

به این منظور یک مجموعه داده مصنوعی براساس ضابطه زیر ایجاد می‌کنیم:

$$
y=b+w_1×x_1+w_2×x_2+w_3×x_3+w_4×x_4
$$

برای تولید مجوعه داده به عنوان b از عدد 1.3 استفاده می‌کنیم و به عنوان ضرایب از اعداد زیر:

$$
W=[1.2 , -2.1 , 1.6 , -0.8]
$$

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

1N = 1000
2nX = 4
3
4W = np.array([1.2, -2.1, 1.6, -0.8])
5B = 1.3
6
7X = np.random.uniform(low=-5, high=+5, size=(N, 4))
8
9Y = np.dot(X, W) + B

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

1LB = -10 * np.ones(nX + 1)
2UB = +10 * np.ones(nX + 1)

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

1def R2(x:np.ndarray,
2       X:np.ndarray,
3       Y:np.ndarray) -> float:
4    B = x[0]
5    W = x[1:]
6    P = np.dot(X, W) + B
7    MSE = ((Y - P) ** 2).mean()
8    Variance = Y.var()
9    r2 = 100 * (1 - MSE / Variance)
10    return r2

این تابع در خروجی ضریب تعیین (Coefficient of Determination یا R^2 Score) که یک معیار ارزیابی برای رگرسیون است را برمی‌گرداند. برای آشنایی بیشتر با معیارهای ارزیابی رگرسیون، می‌توانید به مطلب «بررسی معیارهای ارزیابی رگرسیون در پایتون – پیاده سازی + کد» مراجعه نمایید. برای ایجاد و اجرای الگوریتم نیز کد زیر را استفاده می‌کنیم:

1Algorithm = GA()
2
3History = Algorithm.Maximize(R2, LB, UB, Args=(X, Y))

توجه داشته باشید که در این مثال، تابع هدف بیش از یک ورودی دریافت می‌کند، به همین دلیل لازم است که ورودی‌های به جز ورودی اول به عنوان Args  در ورودی متد Maximize  اضافه شود. کد در مدت 250 میلی‌ثانیه، بهینه‌سازی مدل رگرسیون را به اتمام می‌رساند. دقت نهایی مدل به 99.99% می‌رسد که بسیار جالب توجه است. نمودار فراخوانی توابع به شکل زیر است.

مودار فراخوانی توابع اجرای الگوریتم ژنتیک در پایتون

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

1B = +1.2869
2W = [+1.2034, -2.0827, +1.6022, -0.7886]

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

  1. در طول روند کار الگوریتم، جهش و آمیزش هرکدام در ابتدا و انتهای اجرا چه مقدار به بهبود عملکرد الگوریتم کم کرده‌اند؟
  2. یک مدل غیرخطی را با استفاده از الگوریتم ژنتیک پیاده‌سازی شده، آموزش دهید.
  3. در برخی موارد، Max Generation   تعیین شده، بیشتر از مقدار مورد نیاز مسئله است و در نسل‌های انتهایی، بهبود چندانی رخ نمی‌دهد. در این شرایط، پراکندگی بین بهترین کروموزوم‌های آخرین نسل‌ها کاهش می‌یابد. کد نوشته شده را به گونه‌ای تغییر دهید که به صورت خودکار در صورت مواجه با چنین شرایطی، اجرای الگوریتم را ادامه ندهد.
  4. برخی توابع هدف Keyword Argument دریافت می‌کنند. برای رفع این مشکل، کد را بهبود ببخشید.
  5. ممکن است کاربر، اشتباها حد بالا و حد پایین‌ها را به صورت جابه‌جا وارد نماید (برای یک یا چند متغیر تصمیم، حد بالا کوچک‌تر از حد پایین باشد). برای به اطلاع رساندن این مشکل و جلوگیری از ادامه کار کد، از دستور assert  استفاده کنید.
  6. در برخی موارد، انتخاب والدین یا کروموزوم اولیه برای جهش، بدون جایگذاری انجام می‌شود. الگوریتم را برای کار در این شرایط اصلاح کنید.
  7. اثر هریک از پارامترهای تنظیم‌کننده الگوریتم بر روی عملکرد الگوریتم را بررسی نمایید.
  8. چه رابطه‌ای بین دفعات فراخوانی تابع هدف با تنظیمات الگوریتم وجود دارد؟
بر اساس رای ۱۹ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
مجله فرادرس
۲ دیدگاه برای «پیاده سازی الگوریتم ژنتیک در پایتون – راهنمای گام به گام»

عالی بود باریکلااا مرسی از شما و تیم فرادرس

سلام، خیلی ممنون از بازخورد و همراهی شما. موفق باشید.

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *