يكي از مزاياي روش الگوريتم ژنتيك ايناست كه فقط با مقدار تابع سرو كار دارد و نيازي به دانستن رابطه بين متغيرها و تابع نيست لذا براي انتخاب تابع نيازي به دانستن معادله دقيق آن نداريم و فقط اگر روشي بيابيم كه بهوسيله وارد كردن متغيرهاي مساله مقدار عددي تابع را بتوانيم پيدا كنيم كفايت ميكند.
مثلا اگر بتوانيم بهوسيله روشي از روشهاي ترسيمي در مورد مسالهاي خاص به ازاي متغيرهاي مختلف مقدار تابع را پيدا كنيم يا اينكه اگر نرم افزاري براي تحليل يك مساله مهندسي وجود دارد كه متغيرها را از ما ميگيرد و جواب را به ما ميدهد ميتوانيم بدون دانستن اتفاقاتي كه در طي آن به جواب ميرسيم، فقط با دانستن مقدار آن به ازاي متغيرهاي ورودي مقدار بهين تابع را بهوسيله الگوريتم ژنتيك بهدست آوريم.
اگر تابع هدف ما داراي قيود طراحي بود كه معمولا هم چنين است ميتوانيم به وسيله تابع جريمه، مجموعه قيود مساوي و نامساوي را به يك رابطه تبديل كنيم و به بهينه كردن رابطه مورد نظر بپردازيم. برای مثال اگر براي مسالهای سه قيد نامساوي و يك قيد مساوي مانند زیر داشته باشیم:
1/6 x_1^2+1/6 x_1^2≤1
x_1≥0
x_2≥0
5x_1+3x_2=8
ميتوان آنرا به صورت استاندارد زیر نوشت :
g_1 (x)=1/6 x_1^2+1/6 x_1^2-1≤0
g_2 (x)=-x_1≤0
g_3 (x)=-x_2≤0
g_4 (x)=5x_1+3x_2-8=0
بردار V را بهصورت زير تعريف ميكنيم:
V= max [0,g_1 (x), g_2 (x), g_3 (x), abs(g_4 (x))]
و تابع جریمه را بهصورت زير تعريف ميكنيم:
φ=f_0+RV
كه در آن φ تابع هدف نامقيد بوده و R ضريب جريمه است كه انتخاب آن به عهده طراح ميباشد و بردار V ماكزيمم نقض قيد توسط متغيرها ميباشد و از اين پس تابع φكه تابع پنالتي ما ميباشد به عنوان تابع هزينه بهينه ميگردد.
2-1-2-2 تعيين طول كروموزوم
كروموزوم يك رشته از 0 و 1 است كه مقدار n متغير تابع هدف ما را دربردارد. مثلا اگر طول هر متغير را α بيت در نظر بگيريم طول كل كروموزوم برابر است با: L=n*α (به هر بيت از كروموزوم يك ژن گويند).
ميتوان براي تعيين α از رابطه زير استفاده كرد: α=[(log⁡(b-a)*〖10〗^m )+1] كه m دقت متغيرها بر حسب تعداد رقم اعشار و a حد پايين وb حد بالای متغيرها در مبناي 10 ميباشد.
در جاهايي كه لازم است براي اعداد منفي بايد يك بيت به علامت آنها اختصاص داد و در مورد اعداد اعشاري بايد ابتدا آنها را با ضرب در يك عدد به عدد صحيح تبديل كرده و سپس به باينري تبديل كرد.
2-1-2-3 توليد جمعيت اوليه
پس از تعين طول كروموزوم بايد آنرا به طور اتفاقي از 0 و 1 پركنيم. اينكار بهوسيله دستور زیر انجام ميشود:
L= round (rand)
با توجه به اینکه تعداد تركيبهاي جايگيري 0 و 1 براي كروموزوم به طول L برابر است با لذا بهتر است تعداد كروموزومهاي يك جمعيت را، از تعداد تركيبهاي نشستن صفر و يكها در يك كروموزوم بيشتر نگيريم، چرا كه در بعضي از كروموزومها به ناچار تكرار ميگردند.
مقدار بهينه تعداد كروموزومها در يك جمعيت بهطور تقريبي از رابطه n_pop=1.65*2^(0.21 L) بهدست میآید که در آن L، طول رشته است.
فرض كنيد براي یک تابع دومتغيره5 كروموزوم با تعداد 10ژن در هركدام انتخاب كردهايم. مانند جدول (2-1)

جدول 2-1: تشکیل کروموزم
x_2
x_1
كروموزم ش 1
0
0
1
1
1
0
0
1
0
1
ادامه جدول 2-1: تشکیل کروموزم

x_2

x_1

كروموزم ش2
0
1
1
1
1
0
0
1
1
1
كروموزم ش3
0
0
1
0
1
0
0
1
1
0
كروموزم ش4
1
1
0
1
0
1
1
0
0
0
كروموزم ش5
0
1
0
1
0
1
1
0
1
0

در جدول (2-1)، 5 بيت اول هر كروموزوم، مربوط به مقدار باينري x_1 و 5 بيت دوم هر كروموزوم مربوط به مقدار باينريx_2 ميباشد.
2-2-2-4 تبدیل کروموزمها به اعدادی در بازهی دامنهی همان متغیرها
اگر محدوده متغيرx_1 برابر است با: ≤ b x_1 ≥ a بايد 0 و 1 هاي كروموزوم را به اعدادي در بازهی مورد نظر تبديل كنيم. فرض كنيد يك تكه ژني از كروموزومي به طول L را كه متعلق بهx_1 است ميخواهيم به بازه 〖a≤x〗_1≤b تبديل كنيم. اگر ∝=5. كوچكترين عددي كه با 5 ژن در مبناي 2 ميتوان ساخت بهصورت زیر است:
0
0
0
0
0

كوچكترين عدد از بردن يك تكه كروموزوم ژني به مبناي 10 برابر است با:
u=0*2^0+0*2^1+0*2^2+…+0*2^(∝-1)=0
1
1
1
1
1
بزرگترين عددي كه در 5 ژن از يك كروموزوم ميتوان داشت برابر است با:
و با بردن بزرگترین كروموزوم ∝ژني به مبناي 10 داريم:
u=1*2^0+1*2^1+1*2^2+…+1*2^(∝-1)=2^∝-1
تمامي جايگشتهاي 0 و 1 در يك بايت ∝ بيتي ميتوانند اعدادي بين 0 تا 2^∝-1 در مبناي 10 توليد كند. در حاليكه مجموعه x_1 ما اعدادي در بازه a تا b ميخواهد. تبديل اين دو مجموعه بهوسيله نگاشت انجام ميشود. نگاشت خطي كه بازهها را بههم تبديل مي كند. (u یک عدد در مبنای 10 است).
[0,2^∝-1] □(→┴(r=c_1+c_2 u) ) [a,b]
u=0 , r=a →c_1=a
u=2^l-1 , r=b →c_2=((b-a))/((2^∝-1) )
⇒r=a+((b-a)/(2^∝-1))*u
بههمين ترتيب ميتوانيم براي x_2با دامنه مختص به خودش نگاشتي بنويسيم و اعداد باينري هر متغير را به مقداري در مبناي 10 در بازه مجاز همان متغير تبديل كنيم.
جدول2-2: مثالی از تبدیل کد گذاری

متغير x_1
متغير x_2
كروموزم ش 1
0
1
1
0
0
1
1
1
0
1
مقداردرمبناي 10
6
23

2-1-2-5 بهدست آوردن مقدار تابع تناسب
مقدار متغيرها را در تابع هدف قرار داده و مقدار تابع را به ازاي هر بردار x=[x_1, x_2,…, x_n] بهدست ميآوريم بدين ترتيب براي مجموعه 5 كروموزومي و تابع هدف زير داريم:
f(x)=x_1^2+x_2^2+3x_1 x_2

جدول2-3: محاسبه تابع بهینه
كروموزم ها
متغير x_1به صورت باينري
متغير x_2 به صورت باينري
x_1
x_2
f(x)
كروموزمش1
0
0
1
1
1
0
0
1
0
1
28
20
2864
كروموزم ش2
0
1
1
1
1
0
0
1
1
1
30
28
4204
كروموزم ش 3
1
0
1
0
1
0
0
1
1
0
21
12
1341
كروموزم ش 4
1
1
0
1
0
1
1
0
0
0
11
3
229
كروموزم ش 5
0
1
0
1
0
1
1
0
1
1
10
27
1639

2-1-2-6 محاسبه درصد برازندگی
درصد برازندگي هر كروموزوم را حساب ميكنيم مثلا براي يك تابع دو متغيره درصد برازندگي برابر است با:
100* (جمع تمام برازندگيها / مقدار تابع به ازاي )
كه براي مجموعه 6 كروموزمي بالا و f(x)=x_1^2+x_2^2+3x_1 x_2 به صورت جدول (2-4) درمیآید:
جدول2-4: محاسبه درصد برازندگی
كروموزم ها
متغير x_1 به صورت باينري
متغير x_2به صورت باينري
f(x)
درصد برازندگي
كروموزم ش 1
0
0
1
1
1
0
0
1
0
1
2864
28%
كروموزم ش 2
0
1
1
1
1
0
0
1
1
1
4204
1/41%

ادامه جدول 2-4
كروموزم ها
متغير x_1 به صورت باينري
متغير x_2به صورت باينري
f(x)
درصد برازندگي
كروموزم ش 3
1
0
1
0
1
0
0
1
1
0
1341
1/13%
كروموزم ش 4
1
1
0
1
0
1
1
0
0
0
229
2/2%
كروموزم ش 5
0
1
0
1
0
1
1
0
1
1
1639
16%
جمع:
10227
100%

2-1-2-7 تعيين تعداد كروموزوم شركت كننده در عمل پيوند
تا اينجا، جمعيت اوليه توليد و درصد برازندگي هر كروموزوم محاسبه گرديد. حال بايد تعدادي از اين كروموزومها در عمل پيوند شركت كنند براي تعيين تعداد كروموزومها از فرمول زیر استفاده ميكنيم:
N_c=2*round((p_0*c_p)⁄2)
که در آن p_0، تعداد جمعيت اوليه، c_p، ضريب پيوند كه معمولا حدود 0.6 ميباشد وN_c تعداد كروموزومهايي از جمعيت اوليه است که در عمل پيوند شركت ميكنند.
2-1-2-8 انتخاب كروموزومهايي كه در عمل پيوند شركت ميكنند
براي اينكه نسل بعدي از نسل قبلي بهتر باشد بايد كروموزومهايي با درصد برازندگي بيشتر، شانس بيشتري براي شركت در عمل پيوند داشته باشند. لذا براي تعيين اينكه چه كروموزومهايي در عمل پيوند شركت ميكنند مكانيزمي به نام چرخرولت انتخاب ميكنيم كه متناسب با درصد برازندگي هر كروموزوم، آن را در عمل پيوند شركت ميدهد. اين مكانيزم به اينصورت است كه درصد برازندگي هر كروموزوم را روي دايرهاي به صورت قطاعي مشخص ميكند. در مثال ما كه 5 كروموزوم داريم بايد 5 قطاع به اندازههاي مختلف داشته باشيم.
جدول 2-5: تشکیل چرخ رولت
كروموزم ها
درصدبرازندگي
كروموزم ش1
28%
كروموزم ش2
1/41%
كروموزم ش3
1/13%
كروموزم ش4
2/2%
كروموزم ش5
16%

حال فرض كنيد چرخ را به گردش در آورده و نقطهاي را به عنوان شاخص در نظر ميگيريم. پس از توقف چرخ، قطاعي كه در مقابل شاخص قرار گرفت نشاندهنده كروموزومي است كه بايد در عمل پيوند شركت كند. اين كار را Nc بار انجام میدهیم تا به تعداد كافي كروموزوم براي پيوند بهدست آوريم. ملاحظه ميكنيم كه در اين مكانيزم كروموزومهاي با درصد برازندگي بالاتر شانس بيشتري براي انتخاب شدن دارند . که در شکل 2-2 نشان داده شدهاست.

↑مربوط به کروموزم بادرصد برازندگی 41.1%
شکل 2-2: نمونه ای از انتخاب در چرخ رولت
2-1-2-8-الف: انتخاب به روش چرخ رولت

در اين روش هر رشته، قطاعي از چرخرولت با شعاع 2π*f_i⁄f_tot از مركز چرخ را به خود اختصاص ميدهد.
انتخاب چرخرولت، خطاي نمونه برداري زيادي توليد ميكند. از اينجهت كه تعداد نهايي فرزندان تخصيص داده شده به يك رشته با ميزان مورد نظر خيلي تفاوت دارد. تعداد فرزندان زماني به ميزان مورد نظر ميرسد كه اندازه جمعيت خيلي زياد باشد. در مسائل كاربردي از چرخ استفاده نميشود بلكه مقدار f_i⁄(∑▒f_i ) را به هر رشته تخصيص ميدهند و با توليد يك عدد تصادفي در بازه (0,∑▒f_i ) رشته را انتخاب ميكنند.
2-1-2-9 تقاطع(پيوند):
عمل تركيب دو كروموزوم (والدين) و بهدست آوردن دو كروموزوم جديد (فرزندان) را پيوند مينامند. براي انجام عمل پيوند روي دو كروموزوم L ژني ابتدا بايد نقطه پيوند را مشخص كنيم. اين كار با فراخواني عددي تصادفي بين 1 و L-1 صورت ميپذيرد.
round ((L*rand) +1)
سپس ژنهاي دو كروموزوم را از نقطه پيوند با هم عوض ميكنيم. عمل پيوندي كه در فوق انجام شد تقاطع تكنقطهاي نام دارد. بهعنوان مثال براي دو كروموزوم 10 ژني با نقطه پيوند 4 داريم:
جدول 2-6: عمل پیوند
كروموزم ش1
1
1
1
1
1
1
1
1
1
1
كروموزم ش2
0
0
0
0
0
0
0
0
0
0
اگر پيوند را از نقطه 4 آغاز كنيم داريم
كروموزم جديد ش 1
0
0
0
0
1
1
1
1
1
1
كروموزم جديد ش2
1
1
1
1
0
0
0
0
0
0
2-1-2-10جهش
جهش يكي از پديدههاي علم ژنتيك است كه بهندرت در برخي از كروموزومها رخ ميدهد و در طي آن فرزندان خصوصياتي پيدا ميكنند كه متعلق به هيچ يك از والدين نميباشد.
نقش جهش در الگوريتم ژنتيك بازگرداندن مواد ژنتيكي گمشده و يا پيدا نشده داخل جمعيت است. تا از همگرايي زودرس الگوريتم به جوابهاي بهينه محلي جلوگيري شود. در جهش يكسري از ژنها را بهطور تصادفي برگزيده، صفرها را به يك و يكها را به صفر تبديل ميكنيم. يكي از روشهاي جهش بدين صورت است كه ابتدا با توجه به يك عدد كوچكتر از يك، به نام احتمال جهش، براي هر ژن از جمعيت، يك عدد تصادفي فراخواني ميشود. اگر اين عدد تصادفي از احتمال جهش كوچكتر بود، در آن ژن جهش رخ ميدهد.
چون عمل جهش در طبيعت بهندرت رخ ميدهد لذا در الگوريتم ژنتيك هم با احتمال بسيار كم(كمتر از 0.05) عمل جهش را انجام ميدهيم. همانطور كه گفته شد مزيت عملگر جهش ايناست كه توان دسترسي به همه فضاي جستجو را به ما ميدهد.
در صورتي كه كاراكترها اعداد پيوسته باشند جهش را ميتوان بهصورت نمو تصادفي مثبت يا منفي حول مقدار قبلي كاراكتر انجام داد. اين

دسته بندی : No category

دیدگاهتان را بنویسید