کمیل آقابابایی ارشد نرم افزار
پیش نیار: آشنا با مفاهیم الگوریتم ژنتیک و پایتون
کتابخانه geneticalgorithm یک کتابخانه پایتون است که برای پیاده سازی الگوریتم ژنتیک استاندارد توزیع شده است.
#version 1.0.2 updates
یک مثال ساده:
فرض کنید یک مجموعه از X=(x1,x2,x3) که می خواهیم تابع f(X)=x1+x2+x3 را به حداقل برسانیم.
که در آن X می تواند هر عدد واقعی در [0،10] باشد.
این یک مساله پیش‌پاافتاده است و ما می‌دانیم پاسخ آن X=(0,0,0) که در نتیجه f(X)=0 می باشد.
ما فقط از این مثال ساده استفاده می کنیم تا نحوه اجرای گوریتم ژنتیک را ببینیم:
ابتدا اگوریتم ژنتیک و numpy را وارد می کنیم. سپس، تابع f را که می‌خواهیم کمینه کنیم و محدوده متغیرها. سپس به سادگی می توان مساله بهینه‌سازی تعریف‌شده زیر را با استفاده از الگوریتم ژنتیک حل کرد :
return np.sum(X)
توجه داشته باشید که ما تابع f را طوری تعریف می کنیم که بتوانیم خروجی تابع را با ورودی مجموعه X به حداقل برسانیم.
متغیرها باید به صورت یک آرایه numpy تعریف شوند و برای هر متغیر به یک محدوده جداگانه نیاز داریم. در اینجا من سه متغیر دارم و همه آنها محدوده های یکسانی دارند.
الگوریتم ژنتیک چند آرگومان دارد:
اگر کد را اجرا کنید، باید یک نوار پیشرفت ببینید که نماینگر پیشرفت الگوریتم ژنتیک (GA) می باشد و سپس راه حل، مقدار تابع هدف و منحنی همگرایی را به صورت زیر نشان می دهد:
همچنین ما می‌توانیم به بهترین پاسخ مساله بهینه‌سازی تعریف‌شده توسط geneticalgorithm به عنوان یک دیکشنری و گزارش پیشرفت الگوریتم ژنتیک دسترسی داشته باشیم . برای انجام این کار , کد را به صورت زیر تکمیل می‌کنیم :
دقت کنید output_dict فرهنگ لغتی شامل بهترین مجموعه از متغیرهای یافت شده می باشد و مقدار تابع داده شده مرتبط با آن است output_dict({'variable': , 'function': }).
گزارش فهرستی است شامل همگرایی الگوریتم بر روی تکرارها
مثال ساده با متغیرهای عدد صحیح:
return np.sum(X)
مثال ساده با متغیرهای مختلط:
توجه داشته باشید که برای متغیرهای مختلط باید وحدوده را تعریف کنیم همچنین باید یک آرایه numpy از انواع متغیرها مانند بالا (vartype) ایجاد کنیم.
بدیهی است که ترتیب متغیرها در هر دو آرایه باید مطابقت داشته باشد.
همچنین توجه داشته باشید که در چنین حالتی برای متغیرهای اینتجر از رشته 'int' و متغیرهای بویلی از محدوده [0,1] استفاده می کنیم.
توجه داشته باشید که ما از آرگومان variable_type_mixed برای وارد کردن یک آرایه numpy از انواع متغیر برای توابع با متغیرهای مختلط استفاده می کنیم.
return np.sum(X)
مساله بیشینه سازی(ماکسیمم):
اگوریتم ژنتیک برای به حداقل رساندن تابع داده شده طراحی شده است.
یک ترفند ساده برای حل مسائل بیشینه سازی، ضرب تابع هدف در علامت منفی است. سپس قدر مطلق خروجی حداکثر تابع است. مثال ساده بالا را در نظر بگیرید. اکنون اجازه می‌دهیم حداکثر f(X)=x1+x2+x3 را پیدا کنیم که در آن X مجموعه‌ای از متغیرهای واقعی در [0,10] است. ما قبلاً می دانیم که پاسخ X=(10,10,10) است که در آن f(X)=30 است.
return -np.sum(X) # در منفی ضرب شده
مشکلات بهینه سازی با محدودیت ها
در تمام مثال های بالا، مسئله بهینه سازی بدون محدودیت(قید و شرط) بود.
حالا توجه کنید که می‌خواهیم f (X) = x۱ + x۲ + x۳ را که X مجموعه‌ای از متغیرهای حقیقی در [۰، ۱۰] است را به حداقل برسانیم. همچنین ما یک محدودیت دیگری داریم به طوری که مجموع x۱ و x۲ برابر یا بزرگ‌تر از ۲ باشند. حداقل f(X) نیز 2 است. در چنین حالتی، یک ترفند تعریف تابع پنالتی(ضرر) است. بنابراین از کد زیر استفاده می کنیم:
pen=0
if X[0]+X[1]<2:
pen=500+1000*(2-X[0]-X[1])
return np.sum(X)+pen
همانطور که در بالا مشاهده شد، هر زمان که محدودیت برآورده نشد، یک جریمه به تابع هدف اضافه می کنیم.
چند نکته در مورد نحوه تعریف تابع پنالتی:
۱ - معمولا ً شما می‌توانید از یک مقدار ثابت بزرگ‌تر از حداکثر مقدار ممکن تابع هدف استفاده کنید اگر حداکثر شناخته شده‌باشد یا اگر احتمال آن را داشته باشیم . در اینجا بالاترین مقدار ممکن از تابع ما ۳۰۰ است ( به عنوان مثال اگر همه متغیرها ۱۰ , f ( X ) = ۳۰۰ باشد . بنابراین من یک ثابت ۵۰۰ را انتخاب کردم . بنابراین , اگر یک راه‌حل آزمایشی در منطقه امکان پذیر نباشد , حتی اگر تابع هدف آن کوچک باشد , تابع هدف پاداش ( تابع تناسب ) از هر راه‌حل عملی بدتر است .
2- از یک ضریب به اندازه کافی بزرگ استفاده کنید و آن را با مقدار تخلف ضرب کنید . این کار به الگوریتم کمک می‌کند تا یاد بگیرد چطور به حوزه امکان پذیر نزدیک شود .
3- نحوه تعریف تابع جریمه معمولاً بر نرخ همگرایی یک الگوریتم تکاملی تأثیر می گذارد.
4- در نهایت پس از حل مسئله، راه حل را تست کنید تا ببینید آیا محدوده ها رعایت شده اند یا خیر. اگر راه حل محدودیت ها را برآورده نکند، نشان می دهد که جریمه بزرگتری مورد نیاز است. با این حال، در مسائلی که بهینه دقیقاً در مرز منطقه امکان پذیر است (یا بسیار نزدیک به محدودیت ها) که در برخی از مشکلات رایج است، یک جریمه بسیار سخت و بزرگ ممکن است مانع از نزدیک شدن الگوریتم ژنتیک به منطقه بهینه شود. در چنین حالتی طراحی یک تابع جریمه مناسب ممکن است چالش برانگیزتر باشد. در واقع کاری که باید انجام دهیم این است که یک تابع جریمه طراحی کنیم که به الگوریتم اجازه دهد دامنه غیرقابل اجرا را جستجو کند و در نهایت به یک راه حل عملی همگرا شود. از این رو ممکن است به عملکردهای پنالتی پیچیده تری نیاز داشته باشید. اما در بیشتر موارد فرمول فوق به خوبی کار می کند.
پارامترهای الگوریتم ژنتیکی:
هر الگوریتم تکاملی (فرا ابتکاری) چند پارامتر دارد که باید تنظیم شود. الگوریتم ژنتیک نیز دارای برخی پارامترها است. پارامترها به عنوان یک دیکشنری تعریف می‌شوند:
algorithm_param = {'max_num_iteration': None,\
'population_size':100,\
'mutation_probability':0.1,\
'elit_ratio': 0.01,\
'crossover_probability': 0.5,\
'parents_portion': 0.3,\
'crossover_type':'uniform',\
'max_iteration_without_improv':None}
دیکشنری فوق به مقادیر پیش‌فرض که قبلا ً تنظیم شده‌است اشاره دارد . ممکن است به سادگی این کد را از اینجا کپی کرده و مقادیر را تغییر داده و از دیکشنری تغییر یافته به عنوان آرگومان های geneticalgorithm استفاده کند . راه دیگر دسترسی به این فرهنگ لغت با استفاده از فرمان زیر است :
return np.sum(X)
'population_size':100,\
'mutation_probability':0.1,\
'elit_ratio': 0.01,\
'crossover_probability': 0.5,\
'parents_portion': 0.3,\
'crossover_type':'uniform',\
'max_iteration_without_improv':None}
dimension=3,\
variable_type='real',\
variable_boundaries=varbound,\
algorithm_parameters=algorithm_param)
model.run()
توجه داشته باشید که max_num_iteration به 3000 تغییر کرده است (قبلا None بود). در بالا دیدیم که الگوریتم برای 1500 تکرار اجرا می شود. از آنجایی که ما پارامترها را تعریف نکردیم، اگوریتم ژنتیک مقادیر پیش فرض را اعمال می کرد. اما اگر این کد را اجرا کنید اگوریتم ژنتیک این بار 3000 تکرار را اجرا می کند.
برای تغییر سایر پارامترها می توان به سادگی مقادیر را مطابق با Arguments جایگزین کرد.
@ بیش‌ترین تعداد تکرار(max_num_iteration):
اگر این معیار دارای مقدار نباشد , الگوریتم حداکثر تعداد تکرارها را به صورت تابع بعد , حدود و اندازه جمعیت تنظیم می‌کند . کاربر ممکن است هر تعداد تکرار را که می‌خواهند وارد کند . به شدت توصیه می‌شود که خود کاربر بیش‌ترین تعداد تکرار را تعیین کند و از None استفاده نکند .
@ سایز جمعیت (population_size):
تعداد راه حل های(جمعیت/فرضیه) آزمایشی را در هر تکرار تعیین می کند. مقدار پیش فرض 100 است.
@ جهش (mutation_probability):
مشخص می‌کند که شانس هر ژن در هر راه‌حل مجزا با یک مقدار تصادفی جایگزین می‌گردد . پیش‌فرض ۰.۱ ( یعنی ۱۰ درصد ) است .
@ نرخ_نخبگی (elit_ration):
تعداد نخبگان جامعه را تعیین می کند. مقدار پیش فرض 0.01 (یعنی 1 درصد) است. به عنوان مثال وقتی اندازه جمعیت 100 است و نسبت elit 0.01 است، یک نخبه در جمعیت وجود دارد. اگر این پارامتر روی صفر تنظیم شود، اگوریتم ژنتیک یک الگوریتم ژنتیک استاندارد را به جای GA نخبه‌گرا پیاده‌سازی می‌کند.
@ترکیب(crossover _ probability):
مشخص می‌کند که شانس یک راه‌حل وجود دارد تا ژنوم آن ( ملقب به ویژگی ) را به راه‌حل‌های آزمایشی جدید ( ملقب به فرزندان ) منتقل کند; مقدار پیش‌فرض ۰.۵ است ( یعنی ۵۰ درصد )
@پارامتر(parents _ portion):
بخش جمعیتی که توسط اعضای نسل قبلی ( معروف به والدین ) پر شده بود , ۰.۳ درصد ( یعنی ۳۰ درصد جمعیت ) است .
@ نوع ترکیب(crossover _ type :):
شامل سه نوع می باشد: one_point; two_point, and uniform crossover functions که پیش فرض uniform crossover می باشد.
@پارامتر(max_iteration_without_improv):
اگر الگوریتم‌ها تابع هدف را بیش از تعداد تکرارهای متوالی تعیین‌شده توسط این پارامتر بهبود ندهند، آنگاه گوریتم ژنتیکی متوقف می‌شود و بهترین راه‌حل پیدا شده را قبل از برآورده شدن max_num_iterations گزارش می‌کند. مقدار پیش فرض None است.
تابع داده‌شده باید تنها باید یک آرگومان را بپذیرد و عددی را باز گرداند . آرگومان یک تابع خاص ، آرایه numpy است که توسط geneticalgorithm وارد می‌شود . به هر دلیلی اگر نمی‌خواهید با numpy در عملکرد خود کار کنید ، ممکن است آرایه numpy را به یک لیست تبدیل کنید .
Arguments
@param function <Callable> - به حداقل رساندن تابع هدف داده‌شده
توجه: این پیاده سازی تابع هدف داده شده را به حداقل می رساند. (برای بیشینه سازی، تابع را در علامت منفی ضرب کنید: قدر مطلق خروجی تابع هدف واقعی خواهد بود)
@param dimension <integer>:
- the number of decision variables
@param variable_type <string>:
- 'bool' if all variables are Boolean; 'int' if all variables are integer; and 'real' if all variables are real value or continuous (for mixed type see @param variable_type_mixed).
@param variable_boundaries <numpy array/None>:
- Default None; leave it None if variable_type is 'bool'; otherwise provide an array of tuples of length two as boundaries for each variable; the length of the array must be equal dimension. For example, np.array([0,100],[0,200]) determines lower boundary 0 and upper boundary 100 for first and upper boundary 200 for second variable where dimension is 2.
@param variable_type_mixed <numpy array/None>:
- Default None; leave it None if all variables have the same type; otherwise this can be used to specify the type of each variable separately. For example if the first variable is integer but the second one is real the input is: np.array(['int'],['real']). NOTE: it does not accept 'bool'. If variable type is Boolean use 'int' and provide a boundary as [0,1] in variable_boundaries. Also if variable_type_mixed is applied, variable_boundaries has to be defined.
@param function_timeout <float>:
- if the given function does not provide output before function_timeout (unit is seconds) the algorithm raise error. For example, when there is an infinite loop in the given function.
@param algorithm_parameters:
@ max_num_iteration <int/None>:
- stoping criteria of the genetic algorithm (GA)
@ population_size <int>
@ mutation_probability <float in [0,1]>
@ elit_ration <float in [0,1]>
@ crossover_probability <float in [0,1]>
@ parents_portion <float in [0,1]>
@ crossover_type <string>:
- Default is 'uniform'; 'one_point' or 'two_point' are other options
@ max_iteration_without_improv <int/None> -
maximum number of successive iterations without improvement. If None it is ineffective
منبع :
https://pypi.org/project/geneticalgorithm/
