مقدمه‌ای بر الگوریتم ژنتیک

مطلب جدیدی تحت عنوان «الگوریتم ژنتیک — از صفر تا صد» در مجله فرادرس به انتشار رسیده است که به طور کامل مباحث مرتبط با الگوریتم ژنتیک، نمایش کدبندی کروموزوم‌ها، عملگرهای ژنتیک، تابع هدف و تابع برازندگی را به همراه یک مثال کاربردی شرح می‌دهد. خوانندگان و مخاطبان عزیز مجله فرادرس برای مطالعه این مطلب می‌توانند به اینجا مراجعه کنند.

یکی از الگوریتم‌های موفق در مسائل بهینه‌سازی، الگوریتم ژنتیک(GA) است. در پایان این مطلب نحوه کار با این تکنیک را فرا‌خواهید گرفت.

1. منبع الهام الگوریتم ژنتیک

چارلز داروین (Charles Darwin) یک نقل‌قول معروف دارد: "نه قوی‌ترین فرد یک گونه زنده می‌ماند نه باهوش‌ترین آنها، بلکه فردی که بهتر با تغییرات همراه باشد، زنده می‌ماند." در واقع کل مفهوم الگوریتم ژنتیک بر‌اساس این نقل ‌قول است. برای فهم بهتر به مثال زیر توجه کنید:

فرض کنید شما رهبر یک شهر هستید و می‌خواهید شهرتان را از اتفاقات بد مصون نگه‌دارید. پس سیاست زیر را درپیش بگیرید:

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

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

2. ارتباط با زیست‌شناسی

می‌دانیم، سلول‌ها بلوک ساختمانی اصلی همه موجودات زنده هستند. بنابراین در هر سلول، یک مجموعه واحد کروموزوم(Chromosome) وجود دارد. کروموزوم رشته‌های DNA هستند.

عموماً، این کروموزوم‌ها به‌صورت رشته‌های صفر‌و‌یکی نمایش داده می‌شوند.

کروموزوم از ژن‌ (Gene) تشکیل شده‌است. هر ژن یک ویژگی خاص را رمزگذاری می‌کند. مثل رنگ مو و چشم.

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

به مثال ابتدایی برمی‌گردیم و خلاصه عملکرد را بررسی می‌کنیم.

• ابتدا جمعیت (population) اولیه را به عنوان هموطنان‌مان تعریف کردیم.
• یک تابع برای تعیین خوب/بد بودن هر شخص تعریف کردیم.
• افراد خوب را برای ازدواج (mating) و فرزندآوری انتخاب کردیم.
• در پایان، فرزندان (off-spring) جایگزین افراد بد می‌شوند و این فرایند تکرار می‌شود.

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

منظور از initialization مقداردهی اولیه، Fitness assignment  تخصیص مقدار شایستگی، Selection انتخاب، Crossover تقاطع و Mutation جهش است.

4. گام‌های الگوریتم ژنتیک

برای درک بهتر موضوع از مسأله مشهور کوله‌پشتی (Knapsack problem) استفاده می‌کنیم.

تعریف مسأله: قصد داریم یک ماه را در بیابان بگذرانیم. تنها چیزی که حمل می‌کنیم یک کوله‌پشتی است. حداکثر وزن قابل حمل توسط کوله‌پشتی 30 گیلوگرم است. چند آیتم برای بقا در بیابان داریم. هر یک "امتیاز بقا" مخصوص خود را دارند. (جدول زیر) بنابراین هدف ما بیشینه‌کردن امتیازات است.

1. مقداردهی اولیه

برای حل این مسأله با استفاده از الگوریتم ژنتیک، گام اول تعریف جمعیت است. می‌دانیم کروموزوم‌ها رشته‌های دوتایی هستند. در این مسأله 1 به معنای برداشتن آن آیتم و 0 کنار‌گذاشتن آن است. مجموعه کروموزوم زیر جمعیت اولیه ماست.

2. تابع شایستگی

در اینجا امتیازات شایستگی(fitness points) را برای دو کروموزوم اول حساب می‌کنیم.

برای کروموزوم اول  [100110]

مشابه آن برای کروموزوم دوم [001110]

بنابراین برای این مسأله، کروموزومی که امتیاز بقای بالاتری دارد، شایسته‌تر است. کروموزوم A1 شایسته‌تر از کروموزوم A2 است.

3. انتخاب

شاید فکر کنید باید کروموزوم‌های مناسب جمعیت را انتخاب کنیم و به آنها اجازه فرزندآوری بدهیم. اما این کار موچب تولید کروموزوم‌های کاملاً مشابه در چند نسل آینده می‌شود. این موضوع تنوع را کاهش می‌دهد. بنابراین به‌طور کلی از روش انتخاب چرخ رولت (Roulette Wheel Selection method) استفاده می‌کنیم.

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

حال این چرخ می‌چرخد و ناحیه‌ای از چرخ که درمقابل نقطه ثابت (fixed point) می‌ایستد، به‌عنوان والد (parent) انتخاب می‌شود. برای والد دوم این فرایند تکرار می‌شود.  بنابراین در حالت دوم می‌توانیم هر دو والد را یکباره پیدا کنیم.

4. تقاطع

در گام قبل، کروموزوم‌های والد را یافتیم. آنها فرزندان را به‌وجود می‌آورند. بنابراین به‌بیان زیست‌شناسی، تقاطع چیزی جز "تولید مثل" نیست. تقاطع دو کروموزوم 1 و 4 در مثال قبل:

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

5. جهش

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

کل این فرایند در شکل زیر خلاصه می‌شود.

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

• وقتی برای x مرحله متوالی هیچ بهبودی در جواب حاصل نشود.
• وقتی به تعداد نسل(Generation)  از‌پیش‌ تعیین‌شده رسیدیم.
• وقتی تابع شایستگی به یک مقدار از‌پیش‌ تعیین‌شده رسید.

کاربرد الگوریتم ژنتیک در مسائل ریاضی و آمار

1. انتخاب ویژگی

در پیش‌بینی متغیر هدف چگونه ویژگی‌های مهم را شناسایی می‌کنید؟ یکی از پیشرفته‌ترین الگوریتم‌های انتخاب ویژگی (Feature Selection)، الگوریتم ژنتیک است. روش استفاده از آن کاملاً شبیه روش حل مسأله کوله‌پشتی است. مجدداً با جمعیتی از کروموزوم‌ها آغاز می‌کنیم. هر کروموزوم رشته‌ای دوتایی است. در اینجا 1 نشان‌دهنده وجود آن ویژگی در مدل و 0 نشان‌دهنده حذف آن از مدل است. تابع شایستگی در اینجا معیار دقت در پیش‌بینی است. هر چه مجموعه کروموزوم‌ها در پیش‌بینی دقیق‌تر عمل کنند، آن مجموعه شایسته‌تر است.

2. پیاده‌سازی با استفاده از کتابخانه TPOT

در اینجا مروری سریع روی Tree-based Pipeline Optimization Technique) TPOT) خواهیم داشت. TPOT برمبنای کتابخانه scikit-learn است. ساختار خط لوله (Pipeline) را در شکل زیر می‌بینید:

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

1# installing DEAP, update_checker and tqdm 
2pip install deap update_checker tqdm
3# installling TPOT 
4pip install tpot

برای بخش پیاده‌سازی از مجموعه داده Big Mart Sales استفاده کردیم. فایل آموزش و تست را دانلود کنید و کد پایتون آن را مطالعه کنید.

1# import basic libraries
2import numpy as np 
3import pandas as pd 
4import matplotlib.pyplot as plt 
5%matplotlib inline 
6from sklearn import preprocessing 
7from sklearn.metrics import mean_squared_error 
8## preprocessing 
9### mean imputations 
10train['Item_Weight'].fillna((train['Item_Weight'].mean()), inplace=True)
11test['Item_Weight'].fillna((test['Item_Weight'].mean()), inplace=True)
12 ### reducing fat content to only two categories 
13train['Item_Fat_Content'] = train['Item_Fat_Content'].replace(['low fat','LF'], ['Low Fat','Low Fat']) 
14train['Item_Fat_Content'] = train['Item_Fat_Content'].replace(['reg'], ['Regular']) 
15test['Item_Fat_Content'] = test['Item_Fat_Content'].replace(['low fat','LF'], ['Low Fat','Low Fat']) 
16test['Item_Fat_Content'] = test['Item_Fat_Content'].replace(['reg'], ['Regular']) 
17train['Outlet_Establishment_Year'] = 2013 - train['Outlet_Establishment_Year'] 
18test['Outlet_Establishment_Year'] = 2013 - test['Outlet_Establishment_Year'] 
19
20train['Outlet_Size'].fillna('Small',inplace=True)
21test['Outlet_Size'].fillna('Small',inplace=True)
22
23train['Item_Visibility'] = np.sqrt(train['Item_Visibility'])
24test['Item_Visibility'] = np.sqrt(test['Item_Visibility'])
25
26col = ['Outlet_Size','Outlet_Location_Type','Outlet_Type','Item_Fat_Content']
27test['Item_Outlet_Sales'] = 0
28combi = train.append(test)
29for i in col:
30 combi[i] = number.fit_transform(combi[i].astype('str'))
31 combi[i] = combi[i].astype('object')
32train = combi[:train.shape[0]]
33test = combi[train.shape[0]:]
34test.drop('Item_Outlet_Sales',axis=1,inplace=True)
35
36## removing id variables 
37tpot_train = train.drop(['Outlet_Identifier','Item_Type','Item_Identifier'],axis=1)
38tpot_test = test.drop(['Outlet_Identifier','Item_Type','Item_Identifier'],axis=1)
39target = tpot_train['Item_Outlet_Sales']
40tpot_train.drop('Item_Outlet_Sales',axis=1,inplace=True)
41
42# finally building model using tpot library
43from tpot import TPOTRegressor
44X_train, X_test, y_train, y_test = train_test_split(tpot_train, target,
45 train_size=0.75, test_size=0.25)
46
47tpot = TPOTRegressor(generations=5, population_size=50, verbosity=2)
48tpot.fit(X_train, y_train)
49print(tpot.score(X_test, y_test))
50tpot.export('tpot_boston_pipeline.py')

وقتی اجرای این کد تمام شد، tpot_exported_pipeline.py شامل کد پایتون برای خط لوله بهینه خواهد ‌بود. می‌توان دید که ExtraTreeRegressor بهترین عملکرد را برای این مسأله دارد.

1## predicting using tpot optimised pipeline
2tpot_pred = tpot.predict(tpot_test)
3sub1 = pd.DataFrame(data=tpot_pred)
4#sub1.index = np.arange(0, len(test)+1)
5sub1 = sub1.rename(columns = {'0':'Item_Outlet_Sales'})
6sub1['Item_Identifier'] = test['Item_Identifier']
7sub1['Outlet_Identifier'] = test['Outlet_Identifier']
8sub1.columns = ['Item_Outlet_Sales','Item_Identifier','Outlet_Identifier']
9sub1 = sub1[['Item_Identifier','Outlet_Identifier','Item_Outlet_Sales']]
10sub1.to_csv('tpot.csv',index=False)

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

کاربرد الگوریتم ژنتیک در دنیای واقعی

1. طراحی مهندسی

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

2. مسیریابی ترافیک و حمل‌ونقل (مسأله فروشنده دوره‌گرد)

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

3. رباتیک

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

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

• آموزش های تئوری و عملی الگوریتم ژنتیک
• فیلم آموزشی حل مسأله کوله پشتی با الگوریتم ژنتیک
• فیلم آموزشی حل مسائل گسسته با استفاده از الگوریتم PSO

#