الگوريتم ژنتيك (GA)

[ravegoat]

رمز گشايي:
پس از توليد جمعيت اوليه بايد آن ها را رمز گشايي (Decode) كرد. رمز گشايي دقيقا" عكس عمل كد كردن است و هر كروموزوم را به عضوي از فضاي جست و جوي متغير هاي طراحي بر مي گرداند.
طبق مثال هاي گذشته، ما طول تير را براي آن كه تبديل به رشته كنيم، آن را به مبناي 2 برده و با يك 8 بيتي نمايش مي داديم. جمعيت اوليه ي ما در اين مثال، 8 بيتي هاي تصادفي خواهند بود كه اگر رمز گشايي شوند، هر كدام مقدار يك طول را بيان مي كنند. مثلا":

1|1|0|1|0|0|0|0

يكي از كرموزوم هاي جمعيت اوليه در مثال طراحي تير باشد. چون به هنگام كد كردن طول، عدد را از مبناي 10 به مبناي 2 برديم، براي رمز گشايي بايد رشته را از مبناي 2 به مبناي 10 برگردانيم:

2⁰ * 1 + 2¹ * 1 + 2² * 0 + 2³ * 1 + 2⁴ * 0 + 2⁵ * 0 + 2⁶ * 0 + 2⁷ * 0 = طول تير

<=

13 = طول تير

تعيين مقدار تابع هدف و برازندگي:
پس از رمز گشايي تمام كروموزوم هاي جمعيت اوليه، مقادير تابع هدف را براي آن ها مي يابيم. اگر به خاطر داشته باشيد، تابع هدف همان تابعي است كه قرار است مقدار آن اكسترمم شود. پس:

Chromosome -Decode-> X -> F(X)

مثال:
فرض كنيد مي خواهيم مقدار مقاومت يك مدار الكتريكي (R) را به گونه اي تعيين كنيم كه بازده ي آن- F(R) -بيشينه شود. رابطه ي بين مقاومت الكتريكي مدار و بازده با استفاده از نظريه ي مدار ها تييعن شده است. جمعيت اوليه ي ما شامل 5 كروموزوم تصادفي است. اين كروموزوم ها را رمز گشايي مي كنيم و به مقادير زير مي رسيم:

Fitness	F(R)	R
0.1	10	25
0.17	17	50
0.13	13	100
0.2	20	200
0.4	40	500

برازندگي (Fintness) عبارت است از برتري يك گونه نسبت به ساير گونه ها در يك جمعيت كه به شكل زير به دست مي آيد:

Fitness_i=F(X_i)/(F(X₁) + F(X₂) + ... F(X_i) + ... +F(X_n))

كه n تعداد جمعيت اوليه است.
براي مثال فوق براي R=25 آن گاه F(R)=F(25)=10 ؛ در اين صورت برازندگي اين عضو برابر خواهد شد با:

(40 + 20 + 13 + 17 + 10)/10 = 0.1

به همين شكل برازندگي ساير عضو ها هم تعيين مي شود كه نتيجه ي آن در جدول بالا آورده شده است. برترين گونه R=500 است زيرا بازده ي مدار در اين حالت نسبت به ساير حالت ها بيشينه است و در نتيجه برازندگي اين گونه نيز نسبت به بقيه بيش تر خواهد بود.